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:
“I describe family values as responsibility towards others, increase of tolerance, compromise, support, flexibility. And essentially the things I call the silent song of life—the continuous process of mutual accommodation without which life is impossible.”
—Salvador Minuchin (20th century)
“All men, in the abstract, are just and good; what hinders them, in the particular, is, the momentary predominance of the finite and individual over the general truth. The condition of our incarnation in a private self, seems to be, a perpetual tendency to prefer the private law, to obey the private impulse, to the exclusion of the law of the universal being.”
—Ralph Waldo Emerson (1803–1882)