Game Engine Gems 2

 449

29

ThreadCommunicationTechniques

Julien Hamaide

Fishing Cactus

Multithreaded systems are common nowadays. They usually involve synchroni-

zation and lock primitives implemented at the operating system level. Working

with those primitives is far from trivial and can lead to problems such as dead-

locks. This chapter introduces communication techniques that do not use such

primitives and rely on simple concepts. They can be applied to a lot of common

threading systems.

29.1LatencyandThreading

When writing multithreaded code, care should be taken to protect all data that

could be accessed simultaneously by several threads. Most of the time, by using a

mutex or a critical section, the problem is avoided. But this approach has a cost:

threads may stall waiting for a resource to be released. If the resource is heavily

accessed, it may put all threads to sleep, wasting cycles. On the other hand, this

approach has a low latency. When working on protected data, the thread waits

until the action can be executed and then executes it right away. But does the ac-

tion really need it to be executed instantaneously? Latency of some actions is not

critical (e.g., playing a sound). Fortunately, few problems in video games need a

very low-latency treatment. While writing multithreaded code, don’t try to solve

the general problem. Solve your particular problem. For example, if we use a

thread pool, we know the number of threads is limited and that a thread won’t be

destroyed.

Communication among threads is accomplished by simply sending data from

one thread to another, whether by using an operating system primitive, such as a

semaphore, or a piece of memory. A common practice is to send data through

shared variables, variables that should be protected by primitives such as critical

450 29.ThreadCommunicationTechniques

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.2SingleWriter,SingleReader

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.