Channels ▼
RSS

Parallel

Break Up and Interleave Work to Keep Threads Responsive


What About Yield?

The Yield call contains a message pump loop that will process some or all waiting messages. Here's the most straightforward way to implement it:


// Example 3(a): A simple Yield that pumps all waiting messages
// (note: contains a subtle issue)
//
void Yield() {
   while( queue.size() > 1 ) { // do message pump
      message = queue.pop();
      message->run();
   }
}

Quick: Is there anything that's potentially problematic about this implementation? Hint: Consider the context of how it's used in Example 2(c) and the order in which messages will be handled.

The potential issue is this: With this Yield, Option 2 has a subtle but significant semantic difference from Option 1. In Option 1, the continuation was pushed on the current end of the queue and so enjoyed the fairness guarantee of being executed right after whatever waiting items were in the queue at the time it relinquished control. If more messages arrive while the continuation waits in line, they will get enqueued behind the continuation and be serviced after it in a pure first-in/first-out (FIFO) queue order—modulo priority order if the queue is a priority queue.

Using the Yield in Example 3(a), however, we've traded away these pure FIFO queue semantics because we will also execute any new messages that arrive after we call Yield but before we completely drain the queue. This might seem innocuous at first; after all, it's usually just "as if" we had called Yield slightly later. But notice what happens in the worst case: If messages arrive quickly enough so that the queue never gets completely empty, the operation that yielded might never get control again; it could starve. Starvation is usually unlikely, because normally we don't give a thread more work than it can ever catch up with. But it can arise in practice in systems designed to always keep just enough work ready to keep a thread busy and avoid making it have to wait, and so by design the thread always has a little backlog of work ready to do and the queue stays in a small-but-not-empty steady state. In that kind of situation, beware the possibility of starvation.

The simplest way to prevent this potential problem is to remember how many messages are in the queue and then pump only that many messages:


// Example 3(b): A Yield that pumps only the messages
// that were already in the queue at the time it began
//
void Yield() {
 <font color="#FF0000">int n = queue.size();</font>
while( <font color="#FF0000">n--</font> > 0 ) {
                    // pump 'n' messages
      message = queue.Pop();
      message->run();
   }
}

This avoids pumping newer messages that arrive during the Yield processing and usually guarantees progress (non-starvation) for the function that called Yield, as long as we avoid pathological cases where the nested messages Yield again. (Exercise for the reader: Instrument Yield to detect starvation due to nesting.)

Incidentally, note that once again we're applying the technique of taking a snapshot of the state of the system as it was when we began the operation, just like we did in Examples 1(b) and 2(c) where we took a copy of the items collection. In this case, thanks to the FIFO nature of the queue, we don't need to physically copy the queue; it's sufficient to remember just the number of items to pump.

Summary

Sometimes a thread has to interleave its work in order to stay responsive, and avoid blocking new time-sensitive requests that may arrive while it's already processing a longer but lower-priority operation.

There are two main ways to interleave: Option 1 is to use continuations, which means saving the operation's intermediate local state in an object on the heap and creating a new message containing "the rest of the work left to do," which gets inserted into the queue so that we can handle other messages and then pick up and resume the original work where we left off. Option 2 is to use cooperative multitasking and reentrancy by yielding to a function that will pump waiting messages; this yields simpler code and avoids some allocation and queueing overhead because the locals can stay on the stack where they already are, but it also allows deeper stack growth.

In both cases, remember: The issues of interleaving other work are really nasty and it's all too easy to get things wrong, especially when Yield calls are sprinkled around and make the program very hard to reason about locally. Always be careful to remember that the interleaved work could have side effects, and make sure the longer work is resilient to changes to the data it cares about. If we don't do that correctly and consistently, we'll expose ourselves to a class of subtle and timing-dependent surprises. Next month, we'll consider a way to avoid this class of problems by making sure the state of the system is valid at all times, even with partially done work outstanding. Stay tuned.

Notes

[1] H. Sutter. "Use Threads Correctly = Isolation + Asynchronous Messaging (Dr. Dobb's Digest, March 2009).

Acknowledgments

Thanks to Terry Crowley for his insightful comments on drafts of this article.


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