Mutual exclusion (often abbreviated to mutex) algorithms are used in concurrent programming to avoid the concurrent use of un-shareable resources by pieces of computer code called critical sections.

Most such resources are the fine-grained flags, counters, queues and other data used to communicate between code that runs when an interrupt is being serviced, and code that runs the rest of the time. The problem is acute because a task or thread can be switched at any time offering another task or thread to change shared data of the first task or thread which may lead to inconsistent data. The critical sections therefore must be executed protected.

On a single processor system the common way to achieve mutual exclusion is to disable interrupts for the smallest possible number of instructions that will prevent corruption of the shared data structure, the so-called "critical region". This prevents interrupt code from running in the critical region. Beside this hardware supported solution there exist some software solutions that use "busy-wait" to achieve the goal. Examples of these algorithms include:

• Dekker's algorithm
• Peterson's algorithm

In a computer in which several processors share memory, an indivisible test-and-set of a flag is used in a tight loop to wait until the other processor clears the flag. The test-and-set performs both operations without releasing the memory bus to another processor. When the code leaves the critical region, it clears the flag. This is called a "spinlock" or "busy-wait."

Some computers have similar indivisible multiple-operation instructions for manipulating the linked lists used for event queues and other data structures commonly used in operating systems.

Most classical mutual exclusion methods attempt to reduce latency and busy-waits by using queuing and context switches. Some persons claim that benchmarks indicate that these special algorithms waste more time than they save.

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 forever for the other semaphore to be released. Other common side-effects include starvation, in which an essential process does not run enough, priority inversion in which a higher priority task waits for a lower-priority task, and "high latency" in which response to interrupts is not prompt.

Much research attempts to eliminate the above effects. No perfect scheme is known. One intriguing non-classical scheme sends messages between pieces of code. This permits priority inversions, and increases latency but makes deadlocks unlikely.

See also

• Edsger Dijkstra's Semaphores
• C. A. R. Hoare's Monitors
• Condition variable
• Spurious wakeup
• Futex
• Read-copy-update
• Lock-free and wait-free algorithms

References

• Michel Raynal: Algorithms for Mutual Exclusion, MIT Press, ISBN 0-262-18119-3
• Sunil R. Das, Pradip K. Srimani: Distributed Mutual Exclusion Algorithms, IEEE Computer Society, ISBN 0818633808
• Thomas W. Christopher, George K. Thiruvathukal: High-Performance Java Platform Computing, Prentice Hall, ISBN 0130161640

External links

• Article "Common threads: POSIX threads explained - The little things called mutexes (http://www-106.ibm.com/developerworks/library/l-posix2/)" by Daniel Robbins
• Citations by CiteSeer (http://citeseer.ist.psu.edu/cis?q=mutual+exclusion)
• Mutual exclusion algorithm discovery (http://bardavid.com/mead/)
• Mutual Exclusion Petri Net (http://www.cs.adelaide.edu.au/users/esser/mutual.html)