Mutual exclusion
Encyclopedia
Mutual exclusion algorithm
s 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 section
s. A critical section is a piece of code in which a process
or thread
accesses a common resource. The critical section by itself is not a mechanism or algorithm for mutual exclusion. A program, process, or thread can have the critical section in it without any mechanism or algorithm which implements mutual exclusion.
Examples of such resources are fine-grained flag
s, counters or queues, used to communicate between code that runs concurrently, such as an application and its interrupt handler
s. The synchronization of access to those resources is an acute problem because a thread
can be stopped or started at any time.
To illustrate: suppose a section of code is altering 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, which is 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 shared data being accessed by critical sections of code must, therefore, be protected, so that other processes which read from or write to the chunk of data are excluded from running.
system a common way to achieve mutual exclusion inside kernel
s is to disable interrupt
s 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, that also protects against interrupt-based process-change.
In a computer in which several processors share memory, an indivisible test-and-set
of a flag
could be 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".
Similar atomic multiple-operation instructions, e.g., compare-and-swap
, are commonly used for lock-free
manipulation of linked list
s and other data structure
s
Examples of these include the following:
Spin locks and busy waiting take up excessive processor time and power and are considered anti-pattern
s in almost every case. In addition, these algorithms do not work if Out-of-order execution
is utilized on the platform that executes them. Programmers have to specify strict ordering on the memory operations within a thread.
The solution to these problems is to use synchronization facilities provided by an operating system'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 library is used and a thread tries to acquire an already acquired lock, the operating system will suspend the thread using a context switch
and swaps 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 spinlocks are a fine solution for that situation only.
Many forms of mutual exclusion have side-effects. For example, classic semaphores
permit deadlock
s, 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.
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
s are used in concurrent programming to avoid the simultaneous use of a common resource, such as a global variable
Global variable
In computer programming, a global variable is a variable that is accessible in every scope . Interaction mechanisms with global variables are called global environment mechanisms...
, by pieces of computer code called critical section
Critical section
In concurrent programming a critical section is a piece of code that accesses a shared resource that must not be concurrently accessed by more than one thread of execution. A critical section will usually terminate in fixed time, and a thread, task or process will have to wait a fixed time to...
s. A critical section is a piece of code in which a process
Process (computing)
In computing, a process is an instance of a computer program that is being executed. It contains the program code and its current activity. Depending on the operating system , a process may be made up of multiple threads of execution that execute instructions concurrently.A computer program is a...
or thread
Thread (computer science)
In computer science, a thread of execution is the smallest unit of processing that can be scheduled by an operating system. The implementation of threads and processes differs from one operating system to another, but in most cases, a thread is contained inside a process...
accesses a common resource. The critical section by itself is not a mechanism or algorithm for mutual exclusion. A program, process, or thread can have the critical section in it without any mechanism or algorithm which implements mutual exclusion.
Examples of such resources are fine-grained flag
Flag (computing)
In computer programming, flag can refer to one or more bits that are used to store a binary value or code that has an assigned meaning, but can refer to uses of other data types...
s, counters or queues, used to communicate between code that runs concurrently, such as an application and its interrupt handler
Interrupt handler
An interrupt handler, also known as an interrupt service routine , is a callback subroutine in microcontroller firmware, operating system or device driver whose execution is triggered by the reception of an interrupt...
s. The synchronization of access to those resources is an acute problem because a thread
Thread (computer science)
In computer science, a thread of execution is the smallest unit of processing that can be scheduled by an operating system. The implementation of threads and processes differs from one operating system to another, but in most cases, a thread is contained inside a process...
can be stopped or started at any time.
To illustrate: suppose a section of code is altering 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, which is 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 shared data being accessed by critical sections of code must, therefore, be protected, so that other processes which read from or write to the chunk of data are excluded from running.
Enforcing mutual exclusion
There are both software and hardware solutions for enforcing mutual exclusion. The different solutions are shown below.Hardware solutions
On a uniprocessorUniprocessor
A uniprocessor system is a computer system with a single central processing unit. As more and more computers employ multiprocessing architectures, such as SMP and MPP, the term is used to refer to systems that still have only one CPU. Most desktop computers are now shipped with multiprocessing...
system a common way to achieve mutual exclusion inside kernel
Kernel (computing)
In computing, the kernel is the main component of most computer operating systems; it is a bridge between applications and the actual data processing done at the hardware level. The kernel's responsibilities include managing the system's resources...
s is to disable interrupt
Interrupt
In computing, an interrupt is an asynchronous signal indicating the need for attention or a synchronous event in software indicating the need for a change in execution....
s 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, that also protects against interrupt-based process-change.
In a computer in which several processors share memory, an indivisible test-and-set
Test-and-set
In computer science, the test-and-set instruction is an instruction used to write to a memory location and return its old value as a single atomic operation. If multiple processes may access the same memory, and if a process is currently performing a test-and-set, no other process may begin...
of a flag
Flag (computing)
In computer programming, flag can refer to one or more bits that are used to store a binary value or code that has an assigned meaning, but can refer to uses of other data types...
could be 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
Spinlock
In software engineering, a spinlock is a lock where the thread simply waits in a loop repeatedly checking until the lock becomes available. Since the thread remains active but isn't performing a useful task, the use of such a lock is a kind of busy waiting...
" or "busy-wait".
Similar atomic multiple-operation instructions, e.g., compare-and-swap
Compare-and-swap
In computer science, the compare-and-swap CPU instruction is a special instruction that atomically compares the contents of a memory location to a given value and, only if they are the same, modifies the contents of that memory location to a given new value...
, are commonly used for lock-free
Non-blocking synchronization
In computer science, a non-blocking algorithm ensures that threads competing for a shared resource do not have their execution indefinitely postponed by mutual exclusion...
manipulation of linked list
Linked list
In computer science, a linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a datum and a reference to the next node in the sequence; more complex variants add additional links...
s and other data structure
Data structure
In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks...
s
Software solutions
Beside the hardware supported solution, some software solutions exist that use "busy-wait" to achieve the goal.Examples of these include the following:
- Dekker's algorithmDekker's algorithmDekker's algorithm is the first known correct solution to the mutual exclusion problem in concurrent programming. The solution is attributed to Dutch mathematician Th. J. Dekker by Edsger W. Dijkstra in his manuscript on cooperating sequential processes...
- Peterson's algorithmPeterson's algorithmPeterson's algorithm is a concurrent programming algorithm for mutual exclusion that allows two processes to share a single-use resource without conflict, using only shared memory for communication. It was formulated by Gary L. Peterson in 1981...
- Lamport's bakery algorithmLamport's bakery algorithmLamport's bakery algorithm is a computer algorithm devised by computer scientist Leslie Lamport, which is intended to improve the safety in the usage of shared resources among multiple threads by means of mutual exclusion....
- Szymanski's AlgorithmSzymanski's AlgorithmSzymanski's Mutual Exclusion Algorithm is a mutual exclusion algorithm devised by computer scientist Dr. Boleslaw Szymanski, which has many favorable properties including linear wait, and which extension solved the open problem posted by Leslie Lamport whether there is an algorithm with a constant...
Spin locks and busy waiting take up excessive processor time and power and are considered anti-pattern
Anti-pattern
In software engineering, an anti-pattern is a pattern that may be commonly used but is ineffective and/or counterproductive in practice.The term was coined in 1995 by Andrew Koenig,...
s in almost every case. In addition, these algorithms do not work if Out-of-order execution
Out-of-order execution
In computer engineering, out-of-order execution is a paradigm used in most high-performance microprocessors to make use of instruction cycles that would otherwise be wasted by a certain type of costly delay...
is utilized on the platform that executes them. Programmers have to specify strict ordering on the memory operations within a thread.
The solution to these problems is to use synchronization facilities provided by an operating system'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 library is used and a thread tries to acquire an already acquired lock, the operating system will suspend the thread using a context switch
Context switch
A context switch is the computing process of storing and restoring the state of a CPU so that execution can be resumed from the same point at a later time. This enables multiple processes to share a single CPU. The context switch is an essential feature of a multitasking operating system...
and swaps 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
Latency (engineering)
Latency is a measure of time delay experienced in a system, the precise definition of which depends on the system and the time being measured. Latencies may have different meaning in different contexts.-Packet-switched networks:...
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 spinlocks are a fine solution for that situation only.
Advanced mutual exclusion
Synchronization primitives can be built like the examples below by using the solutions explained above:- LocksLock (computer science)In computer science, a lock is a synchronization mechanism for enforcing limits on access to a resource in an environment where there are many threads of execution. Locks are one way of enforcing concurrency control policies.-Types:...
- Reentrant mutexReentrant mutexA reentrant mutex is a mutual exclusion mechanism. In a reentrant mutex, the same thread can acquire the lock multiple times. However, the lock must be released the same number of times or else other threads will be unable to acquire the lock....
es - SemaphoresSemaphore (programming)In computer science, a semaphore is a variable or abstract data type that provides a simple but useful abstraction for controlling access by multiple processes to a common resource in a parallel programming environment....
- MonitorsMonitor (synchronization)In concurrent programming, a monitor is an object or module intended to be used safely by more than one thread. The defining characteristic of a monitor is that its methods are executed with mutual exclusion. That is, at each point in time, at most one thread may be executing any of its methods...
- Message passingMessage passingMessage passing in computer science is a form of communication used in parallel computing, object-oriented programming, and interprocess communication. In this model, processes or objects can send and receive messages to other processes...
- Tuple spaceTuple spaceA 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 processors that produce pieces of data and a group of...
Many forms of mutual exclusion have side-effects. For example, classic semaphores
Semaphore (programming)
In computer science, a semaphore is a variable or abstract data type that provides a simple but useful abstraction for controlling access by multiple processes to a common resource in a parallel programming environment....
permit deadlock
Deadlock
A deadlock is a situation where in two or more competing actions are each waiting for the other to finish, and thus neither ever does. It is often seen in a paradox like the "chicken or the egg"...
s, 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
Resource starvation
In computer science, starvation is a multitasking-related problem, where a process is perpetually denied necessary resources. Without those resources, the program can never finish its task....
, in which a process never gets sufficient resources to run to completion, priority inversion
Priority inversion
In computer science, priority inversion is a problematic scenario in scheduling when a higher priority task is indirectly preempted by a lower priority task effectively "inverting" the relative priorities of the two tasks....
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
Non-blocking synchronization
In computer science, a non-blocking algorithm ensures that threads competing for a shared resource do not have their execution indefinitely postponed by mutual exclusion...
. No perfect scheme is known.
Further reading
- 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
See also
- Atomicity (programming)
- Concurrency controlConcurrency controlIn 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 operations are generated, while getting those results as quickly as possible.Computer...
- Mutually exclusive events
- SemaphoreSemaphore (programming)In computer science, a semaphore is a variable or abstract data type that provides a simple but useful abstraction for controlling access by multiple processes to a common resource in a parallel programming environment....
- Dining philosophers problemDining philosophers problemIn 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....
- Reentrant mutexReentrant mutexA reentrant mutex is a mutual exclusion mechanism. In a reentrant mutex, the same thread can acquire the lock multiple times. However, the lock must be released the same number of times or else other threads will be unable to acquire the lock....
External links
- Article "Common threads: POSIX threads explained - The little things called mutexes" by Daniel RobbinsDaniel RobbinsDaniel Robbins is a computer programmer and consultant best known as the founder and former chief architect of the Gentoo Linux project. In 2008, he launched the Funtoo project, a free GNU/Linux distribution based on Gentoo, and is the project's lead hacker and organizer...
- Mutual exclusion algorithm discovery
- Mutual Exclusion Petri Net
- Mutual Exclusion with Locks - an Introduction
- Mutual exclusion variants in OpenMP
- The Black-White Bakery Algorithm