distinct memory states are required to avoid lockout. To avoid unbounded waiting, n distinct memory states are required. Recoverable mutual exclusion Most algorithms for mutual exclusion are designed with the assumption that no failure occurs while a process is running inside the critical section. However, in reality such failures may be commonplace. For example, a sudden loss of power or faulty interconnect might cause a process in a critical section to experience an unrecoverable error or otherwise be unable to continue. If such a failure occurs, conventional, non-failure-tolerant mutual exclusion algorithms may deadlock or otherwise fail key liveness properties. To deal with this problem, several solutions using crash-recovery mechanisms have been proposed. Types of mutual exclusion devices The solutions explained above can be used to build the synchronization primitives below: Locks (mutexes) Readers–writer locks Recursive locks Semaphores Monitors Message passing Tuple space Many forms of mutual exclusion have side-effects. For example, classic semaphores permit deadlocks, in which one process gets a semaphore, another process gets a second semaphore, and then both wait till the other semaphore to be released. Other common side-effects include starvation, in which a process never gets sufficient resources to run to completion; priority inversion, in which a higher-priority thread waits for a lower-priority thread; and high latency, in which response to interrupts is not prompt. Much research is aimed at eliminating the above effects, often with the goal of guaranteeing non-blocking progress. No perfect scheme is known. Blocking system calls used to sleep an entire process. Until such calls became threadsafe, there was no proper mechanism for sleeping a single thread within a process (see polling). See also Atomicity (programming) Concurrency control Dining philosophers problem Exclusive or Mutually exclusive events Reentrant mutex Semaphore Spinlock References Further reading Michel Raynal: Algorithms for Mutual Exclusion, MIT Press, Sunil R. Das, Pradip K. Srimani: Distributed Mutual Exclusion Algorithms, IEEE Computer Society, Thomas W. Christopher, George K. Thiruvathukal: High-Performance Java Platform Computing, Prentice Hall, Gadi Taubenfeld, Synchronization Algorithms and Concurrent Programming, Pearson/Prentice Hall, External links Common threads: POSIX threads explained – The little things called mutexes" by Daniel Robbins Mutual Exclusion with Locks – an Introduction Mutual exclusion variants in OpenMP The Black-White Bakery Algorithm Concurrency control