Modifying the Producer-Consumer Code to Use Atomics

Modifying the Producer-Consumer Code to Use Atomics

Since adding an item into the circular list and removing an item from the list look like single operations, it is tempting to imagine that they could be implemented using atomic operations. We will explore this scenario using the modified code shown in Listing 8.28. In this code, each producer thread waits until the next entry in the buffer is free and then attempts to atomically add an item into that buffer location. If successful, it incre-ments the pointer to the next entry in the list. Similarly, all the consumer threads wait until an item is placed into the list and then try to atomically remove the new item. The thread that succeeds increments the pointer to the next entry in the list.

Listing 8.28   Using Atomic Operations to Handle a Circular List

void addtobuffer( int value )

{

int success = 0;

while ( !success )

{

if ( buffer[ next(addhere) ] == 0 )

{

if ( CAS( &buffer[ next(addhere) ], 0, value ) == 0 )

{

addhere = next(addhere);

success = 1;

}

}

}

}

int removefrombuffer()

{

int value;

int success = 0; while ( !success )

{

if ( ( value = buffer[removehere] ) != 0 )

{

if ( CAS( &buffer[removehere], value, 0 ) == value )

{

removehere = next(removehere); success = 1;

}

}

}

return value;

}

At first, it appears that this should work. Only one thread at a time can successfully add or remove an element. Only that thread will alter the pointer so that it points to the next entry.

However, this is not the case. It is critical to realize that although instructions will execute in the expected order, the gaps between the execution of adjacent instructions are random. A pair of instructions could be executed on the same cycle or with a separa-tion of only a few cycles. However, a thread may be context switched off the virtual CPU between the two instructions, and this would cause a gap of thousands of cycles to occur between the two operations.

Consider the situation shown in Figure 8.1 where multiple producer and consumer threads exist. At step A, two producer threads are attempting to add an item into the cir-cular buffer. They both reach the CAS instruction at nearly the same time, but one of the threads gets context switched off the CPU at that very moment. At step B, the other thread successfully enters its value into the circular list and is just about to move the addhere pointer onto the next element when it too is context switched off the virtual CPU.

While the first thread is off-processor, one of the consumer threads come along and removes the recently inserted element, as shown in step C. At that point, the first thread

is switched back onto the CPU, and it sees that the slot it was planning to use is now empty. It atomically inserts its item of data into the circular buffer and then increments the pointer to the next place to insert an element.

This is rapidly followed by the second producer thread being brought back onto a virtual CPU. It completes the operation it was performing when it was context switched off the virtual CPU, and it too increments the addhere pointer to the next place to insert an element. This causes the addhere pointer to skip a location, but the removehere pointer, which indicates where to remove elements from, is now pointing at the skipped location, as shown in step D. The skipped location is empty, so the consumer threads are left waiting for an element to be inserted there. This cannot happen until the producer threads have filled up the entire circular buffer. However, before the producer threads can fill the entire buffer, they hit a filled element in the buffer and cannot make progress until this element has been removed, which will never happen because of the stalled consumer threads.

Consequently, the application deadlocks with both the producer and consumer threads unable to make forward progress.