Mutual exclusion

Mutual exclusion is a property of concurrency control, adopted to prevent race conditions. It is the requirement that one thread of execution never enters a critical section while a concurrent thread is already accessing it, where a critical section is the interval of time during which a thread uses a shared resource or shared memory. The problem it addresses is one of resource sharing: how can a software system control several processes' access to a shared resource when each process needs exclusive control of it while doing its work. A successful solution must provide mutual exclusion itself, so only one process is in the critical section at a time, and must also be free of deadlock. The requirement was first identified and solved by Edsger W. Dijkstra in his 1965 paper "Solution of a problem in concurrent programming control", which is credited as the first topic in the study of concurrent algorithms. A shared linked list from which two threads remove neighbouring nodes at once is the classic example of the race condition that the requirement avoids.