450 29.ThreadCommunicationTechniques
sections. But most of the time, those variables are falsely shared. If a first-in-
first-out (FIFO) queue is used to communicate commands between threads, the
item count is a shared variable. If only a single thread writes to the collection,
and only a single thread is reading from the collection, should both threads share
that variable? The item count can always be expressed with two variables—one
that counts the inserted element and one that counts the removed element, the
difference being the item currently in the queue. This strategy is used in the sim-
ple structures presented here.
29.2SingleWriter,SingleReader
This problem is the classic producer-consumer model. A thread produces items
that are consumed by another thread. It is this example that is generally employed
to teach how semaphores are used. The goal is to provide a single writer, single
reader (SWSR) FIFO queue, without using synchronization objects. A fixed-size
item table is preallocated. This table serves as memory storage for the data trans-
fer. Two indices are used, one for the first object to be popped and the other for
the storage of the next item to be pushed. The object is “templatized” with item
type and maximum item count, as shown in Listing 29.1.
A variable must not be written to by two threads at the same time, but noth-
ing prevents two threads from reading that variable concurrently. If the producer
thread only writes to
WriteIndex, and the consumer thread only writes to Read-
Index
, then there should be no conflict [Acton 2009]. The code shown in List-
ing 29.2 introduces the
Push() method, used by the producer to add an item at
the end of the queue.
The method first tests if there is space available. If no, it simply returns false,
letting the caller decide what to do (retry after some sleep, delay to next frame,
etc.). If some space is available, the item is copied to the local item table using
the
WriteIndex, and then a write barrier is inserted. Finally, the WriteIndex is
incremented. The call to
WriteBarrier() is the most important step of this
method. It prevents both the compiler and CPU from reordering the writes to
template <typename Item, int ItemCount> class ProducerConsumerFIFO
{
Item ItemTable[ItemCount];
volatile unsigned int ReadIndex, WriteIndex;
};
Listing 29.1. FIFO class definition.