Mutual Exclusion

In computer science, mutual exclusion refers to the problem of ensuring that no two processes or threads (henceforth referred to only as processes) can be in their critical section at the same time. Here, a critical section refers to a period of time when the process accesses a shared resource, such as shared memory. The problem of mutual exclusion was first identified and solved by Edsger W. Dijkstra in his seminal 1965 paper titled: Solution of a problem in concurrent programming control.

A simple example of why mutual exclusion is important in practice can be visualized using a singly linked list. (See Figure 1.) In such a linked list the removal of a node is done by changing the “next” pointer of the preceding node to point to the subsequent node (e.g., if node i is being removed then the “next” pointer of node i-1 will be changed to point to node i+1). In an execution where such a linked list is being shared between multiple processes, two processes may attempt to remove two different nodes simultaneously resulting in the following problem: let nodes i and i+1 be the nodes to be removed; furthermore, let neither of them be the head nor the tail; the next pointer of node i-1 will be changed to point to node i+1 and the next pointer of node i will be changed to point to node i+2. Although both removal operations complete successfully, node i+1 remains in the list since i-1 was made to point to i+1 skipping node i (which was made to point to i+2). This can be seen in the Figure 1. This problem can be avoided using mutual exclusion to ensure that simultaneous updates to the same part of the list cannot occur.

Read more about Mutual Exclusion:  Enforcing Mutual Exclusion, Advanced Mutual Exclusion, Further Reading

Famous quotes containing the words mutual and/or exclusion:

    Ties of blood are not always ties of friendship; but friendship founded on merit, on esteem, and on mutual trust, becomes more vital and more tender when strengthened by the ties of blood.
    Philip Dormer Stanhope, 4th Earl Chesterfield (1694–1773)

    We belong to the community. It is not the tailor alone who is the ninth part of a man; it is as much the preacher, and the merchant, and the farmer. Where is this division of labor to end? and what object does it finally serve? No doubt another may also think for me; but it is not therefore desirable that he should do so to the exclusion of my thinking for myself.
    Henry David Thoreau (1817–1862)