A Concise Guide to Concurrent Programming
Summer II 2010, David Matuszek

Fundamental Concepts

The purpose of doing parallel/concurrent programming is to take advantage of multiple cores (processors) in order to make programs run faster. That said, however,

• Some problems are more easily and naturally solved with concurrency, and
• There are qualitative, as well as quantitative, benefits to faster programs (that is, we can do things we couldn't do before).

The terms thread and process each refer to a single sequential flow of execution. Separate threads run in the same memory space, and interact by reading from and writing to shared memory locations. Separate processes each have their own memory, and interact by sending messages.

Parallel processing refers to two or more threads running simultaneously, on different cores (processors), in the same computer. It is essentially a hardware term.

Concurrent processing refers to two or more threads running asynchronously, on one or more cores, usually in the same computer. It is essentially a software term.

Asynchronous means that you cannot tell whether operation A in thread #1 happens before, during, or after operation B in thread #2. Asynchronous processes may be running simultaneously, on different cores, or they may be sharing time on the same core.

An asynchronous function call is a call that starts another function executing but does not wait for it to return. Instead, the calling thread continues processing, and some other mechanism is used for retrieving the function result later.

There are two primary approaches to concurrent programming:

• Shared state -- Threads run in the same memory space. Since modifying a piece of data while another thread is attempting to read or modify it will result in inconsistent state, synchronization must be used to temporarily lock data to give one thread exclusive access to it. (Immutable data need not be locked.) This is the approach used by the C family of languages, including Java (and therefore available in Scala).
  • An operation, or block of code, is atomic if it happens “all at once,” that is, no other thread can access the same data while the operation is being performed. In a higher-level language, there are essentially no atomic actions; synchronization is used to make actions atomic.
  • Check-then-act is a common error pattern: if(check(x))act(x) where check(x) and act(x) are each synchronized, but another process may modify x in the "gap" between them.
• Message passing -- Processes run in disjoint memory spaces, and all communication is by sending messages from one process to another. Each process has a queue of received messages. This approach avoids many of the problems of the shared state model, but requires processes to be very lightweight (cheap). Message passing is the approach used by Erlang, and subsequently by Clojure and Scala.

Shared state is appropriate when the problem has fine granularity--that is, threads must work closely together and communicate often. Message passing is appropriate for problems with coarse granularity, that is, they can work independently for long periods of time.

Problems

Concurrency introduces a new set of possible errors:

• Race conditions: If two or more processes try to write to the same data space, or one tries to write and one tries to read, it is indeterminate which happens first. The processes may even interleave, to produce inconsistent data.
• Deadlock: Two or more processes are each waiting for data from the other, or are waiting for a lock held by the other.
• Livelock: Two or more processes each repeatedly change state in an attempt to avoid deadlock, but in so doing continue to block one another.
• Starvation: A process never gets an opportunity to run, possibly because other processes have higher priority.

Analysis

When analyzing the running time of a non-parallel, sequential process, we use the RAM (Random Access Memory) model, which assumes that access to any location in memory takes the same amount of time as access to any other location. This assumption is typically false, but is a very useful simplification--for sequential programs.

The PRAM (Parallel Random Access Memory) model is the obvious extension of the RAM model. It is, however, horribly inappropriate on many architectures.

More suitable for concurrent programs is the CTA (Candidate Type Architecture) model, which assumes:

• There are some number of processors, each executing a standard sequential program in local memory.
• Non-local memory access time, denoted by λ, can be between 100 and 10000 times slower than access to local memory.
• A processor can make only a very small number (usually not more than two) of non-local memory references at a time.
• Basic control of process initiation and synchronization is handled by the system, not by the program.

Locality rule: Minimize the number of non-local references.

Multicore architectures vary greatly. There is not really any substitute for knowing the specific architecture and designing and tweaking programs accordingly. Nevertheless, the CTA model can provide a rough guide to the general quality of an algorithm.

Parallelism does not necessarily make a program run faster; it may even make it slower. Here's why:

• Overhead is work that a sequential program does not need to do.
  • Creating, initializing, and destroying threads adds overhead, and may result in a slower program. Using thread pools (groups of reuseable threads) may reduce the overhead somewhat.
  • Processes are more expensive to create than threads. Message passing is not "free," either, as the messages must be marshalled (packaged) for transmission, a connection must be established, and the messages must be unmarshalled when received.
• Non-parallelizable computation. Some things can only be done sequentially.
  • Amdahl's law states that if 1/S of a computation is inherently sequential, then the computation can be speeded up by at most a factor of S. For example, if 1/5 of a computation must be done sequentially and 4/5 can be done in parallel, then (assuming unlimited parallelism with zero additional overhead) the 4/5 can be done "instantaneously", the 1/5 is not speeded up at all, and the program can execute 5 times faster.
• Idle processors. Unless all processors get exactly the same amount of work, some will be idle. Threads may need to wait for a lock, processes may need to wait for a message.
• Contention for resources. Shared state requires synchronization, which is expensive.

Writing concurrent programs

One approach is to write and debug the program as a sequential program, then look for potential concurrency; this avoids having to debug sequential errors and concurrency errors at the same time. However, there are some known good concurrent algorithms, and there are operations (map, scan, reduce) that are especially useful in creating opportunities for concurrency.

The "90/10 rule" states that a program spends 90% of its time in 10% of its code. Humans are very bad at guessing where that 10% lies. Use a profiler (a program that samples your program at frequent intervals to determine where it is spending most of its time) so that you don't waste your efforts where they won't make any difference.

Intel's "Threading Methodology" is:

1. Analysis. Determine where concurrency might be used and would be helpful.
2. Design and implementation.
3. Test for correctness. Be aware that "Testing can show the presence of errors, but never their absence." (Dijkstra)
4. Tune for performance.

References

Principles of Parallel Programming, by Calvin Lin and Lawrence Snyder. Addison-Wesley, 2008.

The Art of Concurrency: A Thread Monkey's Guide to Writing Parallel Applications, by Clay Breshears. O'Reilly, 2009.

Java Concurrency in Practice, by Brian Goetz. Addison-Wesley, 2006.