Email	Print Reprint
	add to:
	Del.icio.us Digg Google Furl	Slashdot Y! MyWeb Blink
	TABLE OF CONTENTS Introduction Option 1:Use Continuations Option 2:Use Reentrant Message Pumping What About Yield?

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() {
 int n = queue.size();
while( n-- > 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.

Previous Page | 1 Introduction | 2 Option 1:Use Continuations | 3 Option 2:Use Reentrant Message Pumping | 4 What About Yield?

RELATED ARTICLES Securing the Java Core Petascale Tools and Genomic Evolution Legal Compliance: Open Source and Quality Assurance SEI, Army Team Up on Software Testing Highly Scalable Parallel Sorting		TOP 5 ARTICLES No Top Articles.