Functional and Concurrent Programming: Core Concepts and Features

Chapter 20

Case Study: Thread-Safe Queue

This first concurrent programming case study discusses several possible lock-based implementations of a thread-safe first-in-first-out queue. Of particular interest are the contrasts between public and private locks and between single and multiple locks.

20.1 Queues as Pairs of Lists

One classic design of a first-in-first-out queue uses two functional lists. The idea is to store the state of a queue into two lists: in and out. List out represents the front of the queue, in order, and list in is the back of the queue, in reverse order (Figure 20.1). Accordingly, the head of out is the oldest (first-inserted) element of the queue; the head of in is the youngest (last-inserted). Queue elements are removed ...