Editing Mutual exclusion (section)

{{short description|In computing, restricting data to be accessible by one thread at a time}}
{{For|the concept in logic and probability theory|Mutual exclusivity}}
{{Use dmy dates|date=December 2019}}
[[File:Mutual exclusion example with linked list.png|thumb|Two nodes, {{mvar|i}} and {{math|''i'' + 1}}, being removed simultaneously results in node {{math|''i'' + 1}} not being removed.]]

In [[computer science]], '''mutual exclusion''' is a property of [[concurrency control]], which is instituted for the purpose of preventing [[race condition]]s. It is the requirement that one [[thread (computing)|thread of execution]] never enters a [[critical section]] while a [[Concurrent computing|concurrent]] thread of execution is already accessing said critical section, which refers to an interval of time during which a thread of execution accesses a [[shared resource]] or [[shared memory]].

The shared resource is a [[data object]], which two or more concurrent threads are trying to modify (where two concurrent read operations are permitted but, no two concurrent write operations or one read and one write are permitted, since it leads to data inconsistency). Mutual exclusion algorithms ensure that if a process is already performing write operation on a data object [critical section] no other process/thread is allowed to access/modify the same object until the first process has finished writing upon the data object [critical section] and released the object for other processes to read and write upon.

The requirement of mutual exclusion was first identified and solved by [[Edsger W. Dijkstra]] in his seminal 1965 paper "Solution of a problem in concurrent programming control",<ref>{{cite journal|last=Dijkstra|first=E. W.|title=Solution of a problem in concurrent programming control|journal=Communications of the ACM|volume=8|issue=9|pages=569|doi=10.1145/365559.365617|year=1965|s2cid=19357737|doi-access=free}}</ref><ref name="Taubenfeld:2004">Taubenfeld, [http://www.cs.tau.ac.il/~afek/gadi.pdf "The Black-White Bakery Algorithm"]. In Proc. Distributed Computing, 18th international conference, DISC 2004. Vol 18, 56–70, 2004</ref> which is credited as the first topic in the study of concurrent algorithms.<ref>{{Citation | url=http://www.podc.org/influential/2002.html | title=PODC Influential Paper Award: 2002 | work=ACM Symposium on Principles of Distributed Computing | access-date=24 August 2009}}</ref>

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. The removal of a node that sits between two other nodes is performed by changing the ''next'' [[Pointer (computer programming)|pointer]] of the previous node to point to the next node (in other words, if node {{mvar|i}} is being removed, then the ''next'' pointer of node {{math|''i'' – 1}} is changed to point to node {{math|''i'' + 1}}, thereby removing from the linked list any reference to node {{mvar|i}}). When such a linked list is being shared between multiple threads of execution, two threads of execution may attempt to remove two different nodes simultaneously, one thread of execution changing the ''next'' pointer of node {{math|''i'' – 1}} to point to node {{math|''i'' + 1}}, while another thread of execution changes the ''next'' pointer of node {{mvar|i}} to point to node {{math|''i'' + 2}}. Although both removal operations complete successfully, the desired state of the linked list is not achieved: node {{math|''i'' + 1}} remains in the list, because the ''next'' pointer of node {{math|''i'' – 1}} points to node {{math|''i'' + 1}}.

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 term mutual exclusion is also used in reference to the simultaneous writing of a memory address by one thread while the aforementioned memory address is being manipulated or read by one or more other threads.