In a previous post, we made the argument that do-it-yourself multithreading makes it hard to obtrain three desirable properties of multicore software: scalability, code simplicity, and modularity. So if not DIY, what other options are available to us? The answer is, a concurrency platform - an abstraction layer of software that coordinates, schedules, and manages the multicore resources.
There are a variety of concurrency platforms available
today, each with their strengths and weaknesses. (The Wikipedia entry
for “parallel programming model” has a nice summary.) In the next series of blog posts, we will summarize some of the more popular ones, starting (today) with Thread Pools:
- Thread pools
- OpenMP
- Intel's Threading Building Blocks
- Message passing
- Data-parallel languages
- Cilk++
Thread Pools
One of the problems with
programming Pthreads or WinAPI threads directly is the overhead associated with
creating and destroying them. A thread
pool is a strategy for minimizing that overhead and is possibly the simplest
concurrency platform. The basic idea of
a thread pool is to create a set of threads once and for all at the beginning
of the program. When a task is created, it
executes on a thread in the pool, returning the thread to the pool when the
task is done.
As a practical matter, however, few thread pools are
organized in this fashion. The problem
is, what happens when a task arrives to find that there are no threads left in
the pool? Consequently, most thread
pools are implemented so that the newly created tasks are placed into a work queue, and when a thread finishes a
task, it fetches a new task to execute from the work queue. If the work queue is empty, it suspends and
is woken up when a new task is placed on the work queue. Synchronization using, for example, a
mutual-exclusion lock, is necessary to ensure that tasks are removed atomically
so that threads cooperate safely when removing tasks from the work queue.
Great for Independent Tasks
Thread pools are commonly used for Internet servers, where
the tasks represent independent client transactions executing on the
server. In this context, the main issue
is scalability, since the work queue represents a bottleneck in the
system. Suppose that the average time to
execute a task is x and that the time to
remove a task from the queue is y. Then, the number of threads that can
productively use the thread pool is at most x/y,
assuming each thread has a processing core to run on. More than that, and some threads will be
starved waiting on the work queue. For
small-scale systems, this limitation is unlikely to matter much, but most
thread-pool implementations are not really “future-proof” for this reason.
Risk of Deadlocks
For application programming, as opposed to server
implementation, thread pools pose some concurrency risks. The reason is that the tasks making up an
application tend to be dependent on each other.
In particular, deadlock is a significant concern. A deadlock occurs when a set of threads
creates a cycle of waiting. For example,
suppose that thread 1 holds mutex lock A and is waiting to acquire mutex B, thread 2 is
holding mutex B and is waiting to acquire
mutex C, and thread 3
holds lock C and is waiting to acquire mutex
A. In
this situation, none of the three threads can proceed. Although deadlock is a concern in any
asynchronous concurrency platform, thread pools escalate the concern. In particular, a deadlock can occur if all
threads are executing tasks that are waiting for another task on the work queue
in order to produce a result, but the
other task cannot run because all threads are occupied with tasks that are
waiting.
Next Time: OpenMP
Questions for You...
- What has been your experience with Thread Pools?
- When have you had good luck with them? Bad luck?
- What's your favorite concurrency platform?