Channels ▼
RSS

Parallel

Use Thread Pools Correctly: Keep Tasks Short and Nonblocking


Tasks Should Avoid Waiting For Each Other

The worst kind of blocking is when tasks block to wait on other tasks in the pool. To see why, consider the following code:


// Example 2: Launching pathologically interdependent tasks
//
// First, launch N tasks into the thread pool. Each task
// performs some work while blocking twice in the middle.
for( i = 0; i < N; ++i ) {
  pool.run( [=] {
    // <b>… do some work …
    phase1[i].wait();        // A: wait point #1
    // … and more work …
    phase1[i+1].signal();        // B
    // … and more here …
    phase2[i].wait();        // C: wait point #2
    // … and still more …
    phase2[i+1].signal();        // D
  }</b> );
}
// back on the parent thread…
phase1[0].signal();    // release phase 1
phase1[N].wait();    // wait for phase 1 to complete
<b>// E: what is the state of the system at this point?</b>
phase2[0].signal();    // release phase 2
phase2[N].wait();    // wait for phase 2 to complete

This code launches N tasks into the pool. Each task performs work, much of which can execute in parallel. For example, there is no reason why the first "do some work" section of all N tasks couldn't run at the same time because those pieces of work are independent and not subject to any mutual synchronization.

There is some mutual synchronization, though. Each task has two points where it waits for the previous task—in this toy example it's just a simple wait; but in real code, this can happen when the task needs to wait for an intermediate result, for a synchronization barrier between processing stages, or for some other purpose. Here, there are two phases of processing. In each phase, each ith task waits to be signaled, does more work, then signals the following i+1th task.

Execution proceeds as follows: After launching the tasks, the parent thread kicks them past the first wait simply by signaling the first task. The first task can then proceed to do more work, and signal the next task, and so on until the last task signals the parent that phase 1 is now complete. The parent then signals the first task to wake it up from its second wait, and the phase 2 wakeups proceed similarly. Finally, all tasks are complete and the parent is notified of the "join" and continues onward.

Now stop for a moment and consider these questions:

  • What is the state of the system when we reach line E?
  • How many threads must the thread pool have to execute this program correctly? What happens if it doesn't have enough threads?

Let's consider the answers.

First, the state of the system at line E is that we have N tasks each of which is partway through its execution. All N tasks must have started, because phase1[N] has been signaled by the last task, which can only happen if the previous task signaled phase 1[N-1], and so on. Therefore, each of the N tasks must have performed its line B, and is either still performing the processing between B and C, or else is waiting at line C. (No task can be past C because the parent thread hasn't kicked off the phase 2 signal cascade yet.)

So, then, how many threads must the thread pool have to execute this program? The answer is that it must have at least N threads, because we know there is a point (line E) at which every one of the N tasks must have started running and therefore each must be assigned to its own pool thread. And there's the rub: If the thread pool has fewer than N threads and cannot create any more, typically because a maximum size has been reached, the program will deadlock because it cannot make progress unless all tasks are running.

Just make N sufficiently large, and you can deadlock on most production thread pools. For example, .NET's ThreadPool.GetMaxThreads returns the maximum number of threads available; the current default is 250 threads per core, so to inject deadlock on a default-configured pool, let N be 250 × #cores + 1. Similarly, Java's ThreadPoolExecutor lets you set the maximum number of pool threads via a constructor parameter or setMaximumPoolSize; the pool may also fail to grow if the active ThreadFactory fails to create a new thread by returning null from newThread.

At this point you may legitimately wonder: "But isn't Example 2 pathological in the first place? It even says so in the comment!" Actually, Example 2 is fairly typical of many kinds of concurrent algorithms that can proceed in parallel much of the time but occasionally need synchronization points as barriers to exchange intermediate results or enter a new stage of processing. The only thing that's pathological about Example 2 is that the program is trying to run each work item as a thread pool task; instead, each work item should run on its own thread, and everything would be fine.

Summary

Thread pool tasks should be as small as possible, but no smaller. The shorter the tasks, the more evenly they will spread across the pool and the machine, but the more the per-task overhead will start to dominate. Thread pool tasks should still be big enough to be worth the round-trip overhead of shipping them off to a pool thread to execute and shipping the result back, without having the overhead dominate the work itself. Thread pool tasks should also avoid blocking, or waiting for other things to happen, because blocking interferes with the ability of the pool to keep the right number of ready threads available to match the number of cores. Tasks should especially avoid blocking to wait for other tasks in the pool, because when that happens it can lead to worse performance penalties -- and, in the extreme worst case, having a large number of tasks that block waiting for each other can deadlock the entire pool, and with it your application.

Notes

[1] I'll use the term "cores" for convenience to denote the hardware parallelism. Some CPUs have more than one hardware thread per core, and so the actual amount of hardware parallelism available = #processors × #cores/processor × #hardware threads/core. But "total number of hardware threads" is a mouthful, not to mention potentially confusing with software threads, so for now I'll stick with talking about the "total number of cores."

[2] H. Sutter. "Use Threads Correctly = Isolation + Asynchronous Messages" (Dr. Dobb's Digest, April 2009).

[3] H. Sutter. "Sharing Is the Root of All Contention" (Dr. Dobb's Digest, March 2009).

[4] Single UNIX Specification (IEEE Standard 1003.1, 2004).

[5] Windows Fibers (MSDN).


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 

Video