Backtracking: Difficulties in Concurrency

Sorry for the delay, folks. I had intended last week to be supremely productive, and while I made certain advances that I hope to discuss soon, none of them were directly in line with my initial intentions. That said, it's probably time to get back to explaining in more detail what concurrency and parallelism are and why this is an issue worth reading about. In my previous Backtracking post, I explained briefly what is meant by concurrency in the field of computation and why it's becoming a more prominent issue in recent years. Now it's time to cover why the problem is difficult.

In slightly simplified terms, concurrency comes chiefly in two flavors at its lowest level. There is distributed memory concurrency and there is shared memory concurrency. These are centrally understood by two similar but distinct concepts: processes and threads.

Both threads and processes represent executing portions of a computer program. In simple terms, though, a process is effectively "bigger". It gets its own unique chunk of memory on the system and it gets its own slot in the operating system's scheduling system for deciding when which programs run. A thread lives within a process, meaning all of the threads that a process creates share that process' share of the memory and its CPU time.

As you may suspect from the terms "shared memory" and "distributed memory" that bit about threads living inside a process and having access to the same bit of memory is important. It has an essential impact on the way information is communicated between the different running parts of a program.

You see, a process isn't even aware that any memory exists outside of the bit it has access to. If it was, then it would be able to write information there and there would be a very real chance that your computer would crash because your browser unwittingly overwrote a piece of data that your operating system was currently using. So, when two processes need to communicate information, the system needs to actively set up channels of communication through which one process can see some tiny reserved area of the memory reserved for the second process. The first process then places whatever data it is trying to send in that space from which the second process can retrieve it.

Setting up these communication channels is costly, and there are other difficulties that arise when distinct processes need to be synchronized (i.e. if there are points where one process may need to wait for another one before moving on). When threads need to "communicate", however, they don't have to go through any of that nonsense. Since all threads share the same memory space, each one can, given the particular location, see anything that its siblings can without having to request permission or have the desire to share the data explicitly communicated. Instead, one thread writes information and another thread reads it if necessary without any other threads needing to be aware.

This saves all sorts of time and system resources, but it also creates problems. Remember how I mentioned that one process being aware of the entire memory space of the computer could potentially make your web browser kill your operating system? Well, now we have a situation where one thread can kill an entire process (or program) by reading or writing data at the wrong time. This can occur in a number of ways, but we'll only worry about the two most common.

First is something called race conditions. This occurs when two threads are trying to modify the same memory location for different purposes. Say thread A needs to write to memory location X and then retrieve data from X a little bit later. In the mean time, though, thread B writes to X. Instead of getting the value it expected, A gets the value that B wrote, possibly corrupting the result it was trying to compute.

This sort of problem can be solved by what are called locks. The basic idea is that thread A places a restriction on a chunk of memory (or a segment of code), and then no other thread can touch it until A says that it's done with whatever sensitive computation it was doing. This, however, creates more problems. Suppose we have two sensitive memory areas, X and Y, and two threads, A and B. Now, suppose B has a lock on X, but needs access to Y to finish its computation while A has a lock on Y but needs access to X. Neither can finish their computation, so neither can let go of their current lock, and the program will halt. This is called deadlock.

All of this is tricky business, and it only becomes trickier as you seek to optimize performance and fairness within the system. It's so easy to simply overlook possible trouble spots that asking programmers to handle all of this by themselves, even with helpful tools for synchronizing and monitoring their threads, is daunting. This is why we need simpler ways of understanding shared memory concurrency that solve and mitigate these problems with minimal added input from programmers.

Backtracking: What is Concurrency?

Update: light edits as of 2/28/2011

I kind of jumped in on the middle of my work with my first couple of posts. I suspect that there are some individuals who are not experienced Computer Scientists may find interest in what I'm doing -- there's at least one already following me according to Blogger. I'm firmly of the belief that any academic who cannot explain more than the surface details of his/her work to those without domain specific knowledge is a blight upon the earth. I'd rather not be a blight, and I'd also rather not leave anybody entirely alienated, so I'm going to start trying to explain the basic ideas of what it is I'm dealing with and what my larger goals are over a series of posts in the not too distant future. Starting now.

When Computer Scientists discuss concurrency, they are talking about the "simultaneous" performance of multiple tasks at once. I use quotation marks there because such simultaneous performance requires hardware capable of processing multiple instructions at once -- i.e. hardware containing multiple processing units. Historically, this has been limited mostly to so-called "super computers" used in scientific computation. As a result, consumer computers (or, technically, operating systems) kept a schedule of all currently running tasks and rapidly alternated between them, giving each a regular chunk of computation time. Because of the simulated nature of the simultaneous operation, there were only a handful of especially useful applications for concurrency in most consumer level products:

Running multiple distinct programs at once.
Retrieving data from peripherals attached to the computer system.
Handling user interaction.

The first use and most instances of the second are handled almost entirely by the operating system, leaving programmers to only worry about specialized, application-specific uses of concurrency. Times have changed, though, and as we are all well aware, even the lowliest laptop currently in production runs with at least two "cores" or processing units. If you want to break the bank, Apple will sell you a tower containing as many as 16 such cores (or, alternatively, you can build one yourself for a fairly reasonable fee). Within a hardware generation or two, even smartphones will be multi-core.

While users certainly see some benefit from this development in the ability to more efficiently run multiple programs simultaneously, the generally lower clock-speeds of multi-core processors can actually hinder the performance of a single application if it isn't written with multiple cores in mind. Suddenly, we live in a world where developers of consumer sorts of applications can generate performance increases by utilizing multiple processing units in a computer system to "parallelize" their execution. As I will discuss in a future post, this is a complicated task for a number of reasons.