Mutual exclusion

In computer science, mutual exclusion is a property of concurrency control, which is instituted for the purpose of preventing race conditions.

[3] A simple example of why mutual exclusion is important in practice can be visualized using a singly linked list of four items, where the second and third are to be removed.

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 mutual-exclusion solution to this makes the shared resource available only while the process is in a specific code segment called the critical section.

On uni-processor systems, the simplest solution to achieve mutual exclusion is to disable interrupts during a process's critical section.

CAS can be used to achieve wait-free mutual exclusion for any shared data structure by creating a linked list where each node represents the desired operation to be performed.

Therefore, most modern mutual exclusion methods attempt to reduce latency and busy-waits by using queuing and context switches.

[citation needed] 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.

[9] Most algorithms for mutual exclusion are designed with the assumption that no failure occurs while a process is running inside the critical section.

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.