From Wikipedia, the free encyclopedia

Mutual exclusion (often abbreviated to mutex) algorithms are used in concurrent programming to avoid the simultaneous use of a common resource, such as a global variable, by pieces of computer code called critical sections.

Examples of such resources are fine-grained flags, counters or queues, used to communicate between code that runs concurrently, such as an application and its interrupt handlers. The problem is acute because a thread can be stopped or started at any time.

To illustrate: suppose a section of code is mutating a piece of data over several program steps, when another thread, perhaps triggered by some unpredictable event, starts executing. If this second thread reads from the same piece of data, the data, in the process of being overwritten, is in an inconsistent and unpredictable state. If the second thread tries overwriting that data, the ensuing state will probably be unrecoverable. These critical sections of code accessing shared data must therefore be protected, so that other processes which read from or write to the chunk of data are excluded from running.

A mutex is also a common name for a program object that negotiates mutual exclusion among threads, also called a lock.

There exist both software and hardware solutions for enforcing mutual exclusion. The different solutions are presented below.

On a uniprocessor 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 critical section. This prevents interrupt code from running in the critical section.

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 section, it clears the flag. This is called a "spinlock" or "busy-wait."

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

Beside the hardware supported solution, some software solutions exist that use "busy-wait" to achieve the goal. Examples of these include:

• Dekker's algorithm
• Peterson's algorithm
• Lamport's bakery algorithm
• The Black-White Bakery Algorithm
• Semaphores
• Monitor (synchronization)
• Message passing
• Tuple space

Most classical mutual exclusion methods attempt to reduce latency and busy-waits by using queuing and context switches. Some 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 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, such as by guaranteeing non-blocking progress. No perfect scheme is known.

• 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 0-8186-3380-8
• Thomas W. Christopher, George K. Thiruvathukal: High-Performance Java Platform Computing, Prentice Hall, ISBN 0-13-016164-0
• Gadi Taubenfeld, Synchronization Algorithms and Concurrent Programming, Pearson/Prentice Hall, ISBN 0-13-197259-6

• Mutually exclusive
• Semaphore
• Dining philosophers problem

• Article "Common threads: POSIX threads explained - The little things called mutexes" by Daniel Robbins
• Mutual exclusion algorithm discovery
• Mutual Exclusion Petri Net
• Mutual Exclusion with Locks - an Introduction
• Mutual exclusion variants in OpenMP
• The Black-White Bakery Algorithm