reader/writer semaphores and spinlocks:
- situation: many reader, few writers
- allow multiple readers to access the data simultaneously, but only one writer
completions:
- situation: start something and be notified once it completes
- previously done with semaphores (deprecated in favor of mutexes)
RCU: read-copy-update:
- detailed LWN article
- advanced, high performance lock-free mechanism
- situation: many reads, few writes
- mechanism (extremely simplified):
- references to protected data must be held only by atomic code
- when protected data must be changed, writer makes copy, changes it and then updates pointer
- problem: code on other CPUs might hold reference to old version
- solution: because code holding rcu reference must be atomic, old ref must be gone after reschedule of all CPUs
PI mutexes:
- situation: low priority threads holding a lock shared with an important high priority thread is preempted by a CPU intensive medium priority thread: low priority thread can't finish and free-lock so high priority thread starves.
- mechanism: a thread holding a pi-mutex inherits priority of highest waiter
- interesting: Mars Pathfinder experienced this problem. read here
seqlocks:
- provide fast lockless access to shared resource
- situation: resource is small, simple and frequently read. write access is rare but must be fast
- mechanism: readers have free access, but must check for collisions with writers (and then retry)