Channels ▼
RSS

Parallel

Break Up and Interleave Work to Keep Threads Responsive


Option 2:Use Reentrant Message Pumping

Option 2 could be subtitled: "Cooperative multitasking to the rescue!" It will be familiar to anyone who's worked on systems based on cooperative multitasking, such as early versions of MacOS and Windows.

Example 2 illustrates the simplest implementation of Option 2, where instead of "saving stack frames on the heap" in the form of continuations, we instead just keep our in-progress state right on the stack where it already is and use nesting (aka reentrancy) to pump additional messages.


// Example 2(a): Explicit yield-and-reenter (possibly flawed)
//
class LongOperation : public Message {
public:
   void run() {
      LongHelper helper = GetHelper();
      for( int i = 0; i < items.size(); ++i ) {
 <font color="#FF0000">if( i % ChunkSize == 0 ) // from time to time
             Yield();             // explicitly yield control</font>
         helper-> render( items[i] );
      }
      helper->print();
   }
}

In a moment we'll consider several options for implementing Yield. For now, the key is just that the Yield call contains a message pump loop that will process waiting messages, which is what gives them the chance to get unblocked and interleave with this loop.

Option 2 avoids the performance and memory overhead of separate allocation and queueing we saw in Option 1, but it leads to bigger stacks. Stack overflow shouldn't be a problem, however, unless stack frames are large and nesting is pathologically frequent (in which case, there are bigger problems; see next paragraph).

Probably the biggest advantage of this approach is that the code is simpler. We just have to call Yield every so often to allow other messages to be processed, and we're golden ... or so we think, because unfortunately it's not actually quite that easy. The code is simpler to write, but requires a little more care to write correctly. Why?

Remember: Beware State Changes When Interleaving, Really

Just as we saw with continuations, so with any other interleaving including Yield: Whenever the code Yields it must be aware that the thread's state can be changed by the code that executed on this thread during Yield operation. It cannot in general assume that any data that is private to the thread, including thread-local variables, remains unchanged across the Yield call. With continuations, the issue was a bit easier to remember because that style already requires the programmer to explicitly save the local state off to the side and then return, so that by the time we get to the code where the continuation resumes it's easy to remember that time has passed and the world might have changed.

When using Yield-reentrancy instead of continuations, it's easier to forget about this effect, in part because it really is (too) easy to just throw a Yield in anywhere. To see how this can cause problems, assume for a moment that semantically we don't care if nested messages change the contents of items (which was the case in the discussion around Example 1(b)). That is, assume we don't necessarily need to process a snapshot of the state, but only get through items until we're done. Even with those relaxed requirements, do you notice a subtle bug in Example 2?

Consider: What happens if a nested message changes the size of the items collection? If that's possible, then the collection contains at least i objects before the Yield and the expression items[i] is valid, but after the Yield the collection may no longer contain i objects and so items[i] could fail.

In this simple example, we can apply a simple fix. The issue is that we have a window between observing that i < items.size() and using items[i], so the simplest fix is to eliminate the problematic window by not yielding in between those points:


// Example 2(b): Explicit yield-and-reenter (immediate problem fixed)
//
class LongOperation : public Message {
public:
   void run() {
      LongHelper helper = GetHelper();
      for( int i = 0; i < items.size(); ++i ) {
 <font color="#FF0000">helper->render( items[i] );</font>
         if( i % ChunkSize == 0 )    // from time to time
            Yield();                                      // explicitly yield control
      }
      helper->print();
   }
}

Now the code is resilient to having the items collection change during the call.

Of course, as in the discussion around Example 1(b), it's possible that we may not want the collection to change at all, for example to ensure we're processing a consistent snapshot of the collection's state. If so, we may need to save even more off to the side just like we did in Example 1(b), except here it's easier to do because we don't have to mess with a continuation object:


// Example 2(c): As resilient as Example 1(b)
//
class LongOperation : public Message {
public:
   void run() {
 <font color="#FF0000">Collection myItems = items.copy();</font>
   LongHelper helper = GetHelper();
   for( int i = 0; i < <font color="#FF0000">myItems</font>.size(); ++i ) {
      if( i % ChunkSize == 0 )           // from time to time
         Yield();                                                        // explicitly yield control
      helper->render(<font color="#FF0000">myItems</font>[i] );   // ok now do to this here
   }
   helper->print();
 <font color="#FF0000">Free( myItems );</font>
  }
}

Notice that we can now correctly use myItems[i] both before and after Yield because we've insulated ourselves against the problematic state change.


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