Effective Concurrency
by Herb Sutter


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


// K Consumer threads
//
while( true ) {
  myTask = null;
  mut.lock();		// enter critical section
  if( queue.first() == done ) 	// check sentinel, but leave it there
    myTask = done;		//  for other to see
  else if( !queue.empty() ) 	// take a task if there is one
    myTask = queue.pop();
  mut.unlock();		// exit critical section
  if( myTask == done )
    break;
  else if( myTask != null )
    DoWork( myTask ); 
}



// One Producer thread: Changes any box from null to non-null
//
curr = 0;			// keep a finger on the current mailbox
// Phase 1: Build and distribute tasks (use next available mailbox)
while( there are more tasks ) {
  task = AllocateAndBuildNewTask();
  while( slot[curr] != null )// acquire: look for next empty slot
    curr = (curr+1)%K;
  slot[curr] = task;		// release: "You have mail!"
}
// Phase 2: Stuff the mailboxes with "done" signals
numNotified = 0;
while( numNotified < K ) {
  while( slot[curr] == done )	// acquire: look for next not-yet-notified slot
    curr = (curr+1)%K;
  if( slot[curr] = null ) {	// acquire: check that the mailbox is empty
    slot[curr] = done;	// release: write sentinel = "you're done, go home"
    ++numNotified;
  }
}



// K Consumer threads (mySlot = 0..K-1):
// Each changes its own box from non-null to null
//
while( true ) {
  myTask = slot[mySlot];	// acquire: look in mySlot for mail
  if( myTask == done )
    break;
  else if( myTask != null ) {
    slot[mySlot] = null;	// release: signal we took ownership
    DoWork( myTask );
  } 
}




// Thread 1
x = 1;			// a
mut.lock();            // b
 ... etc. ...
// Thread 2: wait for Thread 1 to take the lock, then use x
while( mut.trylock() )	// try to take the lock...
  mut.unlock();		//   .. if we succeeded, unlock and loop
r2 = x;			// read x... not guaranteed to see the value 1!



