![Mutual exclusion example with linked list](https://upload.wikimedia.org/wikipedia/commons/2/2f/Mutual_exclusion_example_with_linked_list.png)
In
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, mutual exclusion is a property of
concurrency control
In information technology and computer science, especially in the fields of computer programming, operating systems, multiprocessors, and databases, concurrency control ensures that correct results for Concurrent computing, concurrent operations a ...
, which is instituted for the purpose of preventing
race condition
A race condition or race hazard is the condition of an electronics, software, or other system where the system's substantive behavior is dependent on the sequence or timing of other uncontrollable events. It becomes a bug when one or more of t ...
s. It is the requirement that one
thread of execution never enters a
critical section
In concurrent programming, concurrent accesses to shared resources can lead to unexpected or erroneous behavior, so parts of the program where the shared resource is accessed need to be protected in ways that avoid the concurrent access. One way to ...
while a
concurrent
Concurrent means happening at the same time. Concurrency, concurrent, or concurrence may refer to:
Law
* Concurrence, in jurisprudence, the need to prove both ''actus reus'' and ''mens rea''
* Concurring opinion (also called a "concurrence"), a ...
thread of execution is already accessing said critical section, which refers to an interval of time during which a thread of execution accesses a
shared resource
In computing, a shared resource, or network share, is a computer resource made available from one host to other hosts on a computer network.
It is a device or piece of information on a computer that can be remotely accessed from another compu ...
or
shared memory
In computer science, shared memory is memory that may be simultaneously accessed by multiple programs with an intent to provide communication among them or avoid redundant copies. Shared memory is an efficient means of passing data between progr ...
.
The shared resource is a data object, which two or more concurrent threads are trying to modify (where two concurrent read operations are permitted but, no two concurrent write operations or one read and one write are permitted, since it leads to data inconsistency). Mutual exclusion algorithm ensures that if a process is already performing write operation on a data object
ritical sectionno other process/thread is allowed to access/modify the same object until the first process has finished writing upon the data object
ritical sectionand released the object for other processes to read and write upon.
The requirement of mutual exclusion was first identified and solved by
Edsger W. Dijkstra in his seminal 1965 paper "Solution of a problem in concurrent programming control",
[Taubenfeld]
"The Black-White Bakery Algorithm"
In Proc. Distributed Computing, 18th international conference, DISC 2004. Vol 18, 56–70, 2004 which is credited as the first topic in the study of
concurrent algorithm
Concurrent computing is a form of computing in which several computations are executed '' concurrently''—during overlapping time periods—instead of ''sequentially—''with one completing before the next starts.
This is a property of a sys ...
s.
A simple example of why mutual exclusion is important in practice can be visualized using a
singly linked list
In computer science, a linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes which ...
of four items, where the second and third are to be removed. The removal of a node that sits between 2 other nodes is performed by changing the ''next''
pointer of the previous node to point to the next node (in other words, if node
is being removed, then the ''next'' pointer of node
is changed to point to node
, thereby removing from the linked list any reference to node
). When such a linked list is being shared between multiple threads of execution, two threads of execution may attempt to remove two different nodes simultaneously, one thread of execution changing the ''next'' pointer of node
to point to node
, while another thread of execution changes the ''next'' pointer of node
to point to node
. Although both removal operations complete successfully, the desired state of the linked list is not achieved: node
remains in the list, because the ''next'' pointer of node
points to node
.
This problem (called a ''race condition'') can be avoided by using the requirement of mutual exclusion to ensure that simultaneous updates to the same part of the list cannot occur.
The term mutual exclusion is also used in reference to the simultaneous writing of a memory address by one thread while the aforementioned memory address is being manipulated or read by one or more other threads.
Problem description
The problem which mutual exclusion addresses is a problem of resource sharing: how can a software system control multiple processes' access to a shared resource, when each process needs exclusive control of that resource while doing its work? The mutual-exclusion solution to this makes the shared resource available only while the process is in a specific code segment called the
critical section
In concurrent programming, concurrent accesses to shared resources can lead to unexpected or erroneous behavior, so parts of the program where the shared resource is accessed need to be protected in ways that avoid the concurrent access. One way to ...
. It controls access to the shared resource by controlling each mutual execution of that part of its program where the resource would be used.
A successful solution to this problem must have at least these two properties:
* It must implement ''mutual exclusion'': only one process can be in the critical section at a time.
* It must be free of ''
deadlock
In concurrent computing, deadlock is any situation in which no member of some group of entities can proceed because each waits for another member, including itself, to take action, such as sending a message or, more commonly, releasing a lo ...
s'': if processes are trying to enter the critical section, one of them must eventually be able to do so successfully, provided no process stays in the critical section permanently.
Deadlock freedom can be expanded to implement one or both of these properties:
* ''Lockout-freedom'' guarantees that any process wishing to enter the critical section will be able to do so eventually. This is distinct from deadlock avoidance, which requires that ''some'' waiting process be able to get access to the critical section, but does not require that every process gets a turn. If two processes continually trade a resource between them, a third process could be locked out and experience
resource starvation
In computer science, resource starvation is a problem encountered in concurrent computing where a process is perpetually denied necessary resources to process its work. Starvation may be caused by errors in a scheduling or mutual exclusion algori ...
, even though the system is not in deadlock. If a system is free of lockouts, it ensures that every process can get a turn at some point in the future.
* A ''k-bounded waiting property'' gives a more precise commitment than lockout-freedom. Lockout-freedom ensures every process can access the critical section eventually: it gives no guarantee about how long the wait will be. In practice, a process could be overtaken an arbitrary or unbounded number of times by other higher-priority processes before it gets its turn. Under a ''k''-bounded waiting property, each process has a finite maximum wait time. This works by setting a limit to the number of times other processes can cut in line, so that no process can enter the critical section more than ''k'' times while another is waiting.
Every process's program can be partitioned into four sections, resulting in four states. Program execution cycles through these four states in order:
![State graph 2](https://upload.wikimedia.org/wikipedia/commons/f/f8/State_graph_2.png)
;Non-Critical Section: Operation is outside the critical section; the process is not using or requesting the shared resource.
;Trying: The process attempts to enter the critical section.
;Critical Section: The process is allowed to access the shared resource in this section.
;Exit: The process leaves the critical section and makes the shared resource available to other processes.
If a process wishes to enter the critical section, it must first execute the trying section and wait until it acquires access to the critical section. After the process has executed its critical section and is finished with the shared resources, it needs to execute the exit section to release them for other processes' use. The process then returns to its non-critical section.
Enforcing mutual exclusion
Hardware solutions
On
uni-processor systems, the simplest solution to achieve mutual exclusion is to disable
interrupt
In digital computers, an interrupt (sometimes referred to as a trap) is a request for the processor to ''interrupt'' currently executing code (when permitted), so that the event can be processed in a timely manner. If the request is accepted, ...
s during a process's critical section. This will prevent any
interrupt service routine
In computer systems programming, an interrupt handler, also known as an interrupt service routine or ISR, is a special block of code associated with a specific interrupt condition. Interrupt handlers are initiated by hardware interrupts, softwar ...
s from running (effectively preventing a process from being
preempted). Although this solution is effective, it leads to many problems. If a critical section is long, then the
system clock will drift every time a critical section is executed because the timer interrupt is no longer serviced, so tracking time is impossible during the critical section. Also, if a process halts during its critical section, control will never be returned to another process, effectively halting the entire system. A more elegant method for achieving mutual exclusion is the
busy-wait
In computer science and software engineering, busy-waiting, busy-looping or spinning is a technique in which a process repeatedly checks to see if a condition is true, such as whether keyboard input or a lock is available. Spinning can also be used ...
.
Busy-waiting is effective for both uniprocessor and
multiprocessor
Multiprocessing is the use of two or more central processing units (CPUs) within a single computer system. The term also refers to the ability of a system to support more than one processor or the ability to allocate tasks between them. There ar ...
systems. The use of shared memory and an
atomic test-and-set In computer science, the test-and-set instruction is an instruction used to write (set) 1 to a memory location and return its old value as a single atomic (i.e., non-interruptible) operation. The caller can then "test" the result to see if the stat ...
instruction provide the mutual exclusion. A process can
test-and-set In computer science, the test-and-set instruction is an instruction used to write (set) 1 to a memory location and return its old value as a single atomic (i.e., non-interruptible) operation. The caller can then "test" the result to see if the stat ...
on a location in shared memory, and since the operation is atomic, only one process can set the flag at a time. Any process that is unsuccessful in setting the flag can either go on to do other tasks and try again later, release the processor to another process and try again later, or continue to loop while checking the flag until it is successful in acquiring it.
Preemption is still possible, so this method allows the system to continue to function—even if a process halts while holding the lock.
Several other atomic operations can be used to provide mutual exclusion of data structures; most notable of these is
compare-and-swap
In computer science, compare-and-swap (CAS) is an atomic instruction used in multithreading to achieve synchronization. It compares the contents of a memory location with a given value and, only if they are the same, modifies the contents of tha ...
(CAS). CAS can be used to achieve
wait-free
In computer science, an algorithm is called non-blocking if failure or suspension of any thread cannot cause failure or suspension of another thread; for some operations, these algorithms provide a useful alternative to traditional blocking im ...
mutual exclusion for any shared data structure by creating a
linked list
In computer science, a linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes whic ...
where each node represents the desired operation to be performed. CAS is then used to change the
pointers
Pointer may refer to:
Places
* Pointer, Kentucky
* Pointers, New Jersey
* Pointers Airport, Wasco County, Oregon, United States
* The Pointers, a pair of rocks off Antarctica
People with the name
* Pointer (surname), a surname (including a l ...
in the linked list during the insertion of a new node. Only one process can be successful in its CAS; all other processes attempting to add a node at the same time will have to try again. Each process can then keep a local copy of the data structure, and upon traversing the linked list, can perform each operation from the list on its local copy.
Software solutions
In addition to hardware-supported solutions, some software solutions exist that use
busy waiting
In computer science and software engineering, busy-waiting, busy-looping or spinning is a technique in which a process repeatedly checks to see if a condition is true, such as whether keyboard input or a lock is available. Spinning can also be use ...
to achieve mutual exclusion. Examples include:
*
Dekker's algorithm Dekker's algorithm is the first known correct solution to the mutual exclusion problem in concurrent programming where processes only communicate via shared memory. The solution is attributed to Dutch mathematician Th. J. Dekker by Edsger W. Dijks ...
*
Peterson's algorithm Peterson's algorithm (or Peterson's solution) is a concurrent programming algorithm for mutual exclusion that allows two or more processes to share a single-use resource without conflict, using only shared memory for communication. It was formulated ...
*
Lamport's bakery algorithm
Lamport's bakery algorithm is a computer algorithm devised by computer scientist Leslie Lamport, as part of his long study of the formal correctness of concurrent systems, which is intended to improve the safety in the usage of shared resource ...
*
Szymański's algorithm
* Taubenfeld's black-white bakery algorithm
*
Maekawa's algorithm Maekawa's algorithm is an algorithm for mutual exclusion on a distributed system. The basis of this algorithm is a quorum-like approach where any one site needs only to seek permissions from a subset of other sites.
Algorithm Terminology
* A ''s ...
These algorithms do not work if
out-of-order execution
In computer engineering, out-of-order execution (or more formally dynamic execution) is a paradigm used in most high-performance central processing units to make use of instruction cycles that would otherwise be wasted. In this paradigm, a proce ...
is used on the platform that executes them. Programmers have to specify strict ordering on the memory operations within a thread.
It is often preferable to use synchronization facilities provided by an
operating system
An operating system (OS) is system software that manages computer hardware, software resources, and provides common services for computer programs.
Time-sharing operating systems schedule tasks for efficient use of the system and may also in ...
's multithreading library, which will take advantage of hardware solutions if possible but will use software solutions if no hardware solutions exist. For example, when the operating system's
lock
Lock(s) may refer to:
Common meanings
*Lock and key, a mechanical device used to secure items of importance
*Lock (water navigation), a device for boats to transit between different levels of water, as in a canal
Arts and entertainment
* ''Lock ...
library is used and a thread tries to acquire an already acquired lock, the operating system could suspend the thread using a
context switch
In computing, a context switch is the process of storing the state of a process or thread, so that it can be restored and resume execution at a later point, and then restoring a different, previously saved, state. This allows multiple processes ...
and swap it out with another thread that is ready to be run, or could put that processor into a low power state if there is no other thread that can be run. Therefore, most modern mutual exclusion methods attempt to reduce
latency and busy-waits by using queuing and context switches. However, if the time that is spent suspending a thread and then restoring it can be proven to be always more than the time that must be waited for a thread to become ready to run after being blocked in a particular situation, then
spinlock
In software engineering, a spinlock is a lock that causes a thread trying to acquire it to simply wait in a loop ("spin") while repeatedly checking whether the lock is available. Since the thread remains active but is not performing a useful task, ...
s are an acceptable solution (for that situation only).
Bound on the mutual exclusion problem
One binary
test&set register is sufficient to provide the deadlock-free solution to the mutual exclusion problem. But a solution built with a test&set register can possibly lead to the starvation of some processes which become caught in the trying section.
In fact,
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
Lock(s) may refer to:
Common meanings
*Lock and key, a mechanical device used to secure items of importance
*Lock (water navigation), a device for boats to transit between different levels of water, as in a canal
Arts and entertainment
* ''Lock ...
(mutexes)
*
Readers–writer lock
In computer science, a readers–writer (single-writer lock, a multi-reader lock, a push lock, or an MRSW lock) is a Synchronization (computer science), synchronization primitive that solves one of the readers–writers problems. An RW lock allo ...
s
*
Recursive locks
*
Semaphores
*
Monitors
Monitor or monitor may refer to:
Places
* Monitor, Alberta
* Monitor, Indiana, town in the United States
* Monitor, Kentucky
* Monitor, Oregon, unincorporated community in the United States
* Monitor, Washington
* Monitor, Logan County, West Vir ...
*
Message passing
In computer science, message passing is a technique for invoking behavior (i.e., running a program) on a computer. The invoking program sends a message to a process (which may be an actor or object) and relies on that process and its supporting i ...
*
Tuple space
A tuple space is an implementation of the associative memory paradigm for parallel/distributed computing. It provides a repository of tuples that can be accessed concurrently. As an illustrative example, consider that there are a group of process ...
Many forms of mutual exclusion have side-effects. For example, classic
semaphores permit
deadlock
In concurrent computing, deadlock is any situation in which no member of some group of entities can proceed because each waits for another member, including itself, to take action, such as sending a message or, more commonly, releasing a lo ...
s, 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
Starvation is a severe deficiency in caloric energy intake, below the level needed to maintain an organism's life. It is the most extreme form of malnutrition. In humans, prolonged starvation can cause permanent organ damage and eventually, dea ...
, in which a process never gets sufficient resources to run to completion;
priority inversion
In computer science, priority inversion is a scenario in scheduling in which a high priority task is indirectly superseded by a lower priority task effectively inverting the assigned priorities of the tasks. This violates the priority model that h ...
, 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
Poll, polled, or polling may refer to:
Figurative head counts
* Poll, a formal election
** Election verification exit poll, a survey taken to verify election counts
** Polling, voting to make decisions or determine opinions
** Polling places o ...
).
See also
*
Atomicity (programming)
Atomicity may refer to:
Chemistry
* Atomicity (chemistry), the total number of atoms present in 1 molecule of a substance
* Valence (chemistry), sometimes referred to as atomicity
Computing
* Atomicity (database systems), a property of database t ...
*
Concurrency control
In information technology and computer science, especially in the fields of computer programming, operating systems, multiprocessors, and databases, concurrency control ensures that correct results for Concurrent computing, concurrent operations a ...
*
Dining philosophers problem
In computer science, the dining philosophers problem is an example problem often used in concurrent algorithm design to illustrate synchronization issues and techniques for resolving them.
It was originally formulated in 1965 by Edsger Dijkstra ...
*
Exclusive or
Exclusive or or exclusive disjunction is a logical operation that is true if and only if its arguments differ (one is true, the other is false).
It is symbolized by the prefix operator J and by the infix operators XOR ( or ), EOR, EXOR, , ...
*
Mutually exclusive events
In logic and probability theory, two events (or propositions) are mutually exclusive or disjoint if they cannot both occur at the same time. A clear example is the set of outcomes of a single coin toss, which can result in either heads or tails ...
*
Reentrant mutex
In computer science, the reentrant mutex (recursive mutex, recursive lock) is a particular type of mutual exclusion (mutex) device that may be locked multiple times by the same process/thread, without causing a deadlock.
While any attempt to per ...
*
Semaphore
*
Spinlock
In software engineering, a spinlock is a lock that causes a thread trying to acquire it to simply wait in a loop ("spin") while repeatedly checking whether the lock is available. Since the thread remains active but is not performing a useful task, ...
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
* {{webarchive , url=https://web.archive.org/web/20160602235210/http://cs.adelaide.edu.au/users/esser/mutual.html , title=Mutual Exclusion Petri Net
Mutual Exclusion with Locks – an IntroductionMutual exclusion variants in OpenMP
Concurrency control