Selecting Locking Primitives for Parallel Programming


By: P.E. McKenney
Published in: CACM, Oct. 1996
Pages: 75-82
Category: Parallel Programming

Summary: Selection of locking primitives for parallel programs assuming a locking design has already been chosen (see Selecting Locking Designs for Parallel Programs).

Selection of locking primitives for parallel programs assuming a locking design has already been chosen

Url: http://c2.com/ppr/mutex/mutexpat.html

Pattern: Test-and-Set Lock

Pages: 78-79

In a parallel program where contention is low and fairness and performance are not crucial, but memory size is a limiting factor, use a locking primitive based on test-and-set.

Pattern: Queued Lock

Pages: 79-80

In a parallel program where contention is high and fair access to critical sections is important, use a queued-lock primitive. Since each CPU has its own queue element, only the CPU most recently granted the lock will consume memory bandwidth to access the new lock state.

Pattern: Queued Reader/Writer Lock

Pages: 80

In a parallel program where contention is high, read-to-write ratio is moderate or high, and where fair access to critical sections is important, use a queued reader/writer lock. When a reader is granted the lock, it first checks to see if the next element on the queue also corresponds to a reader. If so, it grants the lock to this next reader. When the last reader leaves the critical section, it grants the lock to the writer at the head of the queue.

Pattern: Counter Reader/Writer Lock

Pages: 80-81

In a parallel program with a moderate-to-high read-to-write ratio, high contention, and coarse-grained parallelism, use a counter reader/writer lock primitive. The lock maintains the cumulative number of requests and completions for readers/writers. Each requester takes a snapshot of the number of requests so far, increments the appropriate request counter, and then waits for all prior conflicting requests to complete. A read request waits for all prior write requests to complete, while a write request waits for all prior requests to complete.

Pattern: Distributed Reader/Writer Lock

Pages: 81

In a parallel program with a high read-to-write ratio and high read-side contention, use a distributed reader/writer lock primitive. Use a per-CPU lock for readers and an additional lock to gate writers. A reader acquires only its CPU's lock, while a writer must acquire the writer-gate lock as well as each of the reader-side per-CPU locks.