Channels ▼
RSS

Parallel

Apply Critical Sections Consistently

Source Code Accompanies This Article. Download It Now.


Example 1: One Producer, Many Consumers, Using Locks

Imagine we have a single Producer thread that produces a number of tasks for Consumer threads to perform. The Producer pushes the tasks into a shared queue, and finally pushes a special done sentinel to mark the end of the work. The queue object is protected at all times using mutex mut, which the Producer holds only as long as necessary for a single push, so that Consumers can start executing their tasks concurrently with the Producer. For further efficiency, to avoid making the Consumers busy-wait whenever the queue is initially or temporarily empty, the Producer will also signal condition variable cv every time something has been added to the queue:









// One Producer thread
//
while( ThereAreMoreTasks() ) {
  task = AllocateAndBuildNewTask();
  mut.lock();   	// enter critical section
  queue.push( task );	// add new task
  mut.unlock();	// exit critical section
  cv.notify();
}
mut.lock();     	// enter critical section
queue.push( done );	// add sentinel value; that's all folks
mut.unlock(); 	// exit critical section
cv.notify();


On the consumption side, the Consumer threads each pull individual tasks off the completed queue. Here, myTask is an ordinary variable local to each Consumer:

// K Consumer threads
//
myTask = null;
while( myTask != done ) {
  mut.lock();  	// enter critical section
  while( queue.empty() )	// if nothing's there, to avoid busy-waiting we'll
    cv.wait( mut );  	// release and reenter critical section
  myTask = queue.first();	// take a copy of the task
  if( myTask != done ) 	// remove it from queue unless it was the sentinel, 
    queue.pop();	// which we want to leave there for others to see
  mut.unlock();	// exit critical section
  if( myTask != done )
    DoWork( myTask ); 
}


All of these critical sections are easy to see. This code simply protects the data structure using the same mutex for its entire shared lifetime, and it's easy to check that you did it right—just look to make sure the code only refers to queue when inside some critical section that holds a lock on mut.

The primary expression of critical sections is the explicit locking done on the mutex. The condition variable is just icing on the cake—an optimization that lets us express an efficient wait point in the middle of a locked section so that the Consumer race cars don't have to expend needless energy spinning their tires (in this case, their lock/unlock loop) while waiting for the Producer to give them the green light.


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