By: P.E. McKenney
Published in: CACM, Oct. 1996
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
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.
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.
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.
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.
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.