ABSTRACT
The applications for producer and consumer queues extend beyond input messaging. Imagine a real-time strategy game where the user produces a list of tasks such as “build factory,” “move unit here,” “attack with hero,” etc. Each task is consumed by a separate game logic thread that uses pathfinding knowledge of the environment to execute each task in parallel. Suppose the particular consumer thread uses an A* algorithm to move a unit and hit a particularly worst-case performance path. The producer thread can still queue new tasks for the consumer without having to stall and wait for the algorithm to finish. The producer-consumer queue naturally extends to data parallelism. Imagine an animation engine that uses the CPU to update N animated bone-skin skeletons using data from static geometry to handle collision detection and response. As pictured in Figure 31.2, the animation engine can divide the work into several threads from a thread pool by producing multiple “update bone-skin” tasks, and the threads can consume the tasks in parallel. When the queue is empty, the animation thread can continue, perhaps to signal the rendering thread to draw all of the characters. In Figure 31.3, only one item at a time is consumed from the queue (since the queue is read atomically from the tail); however, the actual time the consumer thread starts or finishes the task may be out of order because the OS thread scheduler can preempt the consumer thread before useful work begins.
