Editing Mutual exclusion (section)

==Problem description==

The problem which mutual exclusion addresses is a problem of resource sharing: how can a software system control multiple processes' access to a shared resource, when each process needs exclusive control of that resource while doing its work? 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]]. It controls access to the shared resource by controlling each mutual execution of that part of its program where the resource would be used.

A successful solution to this problem must have at least these two properties:
* It must implement ''mutual exclusion'': only one process can be in the critical section at a time.
* It must be free of ''[[deadlock (computer science)|deadlock]]s'': if processes are trying to enter the critical section, one of them must eventually be able to do so successfully, provided no process stays in the critical section permanently.

Deadlock freedom can be expanded to implement one or both of these properties:
* ''Lockout-freedom'' guarantees that any process wishing to enter the critical section will be able to do so eventually. This is distinct from [[deadlock avoidance]], which requires that ''some'' waiting process be able to get access to the critical section, but does not require that every process gets a turn. If two processes continually trade a resource between them, a third process could be locked out and experience [[starvation (computer science)|resource starvation]], even though the system is not in deadlock. If a system is free of lockouts, it ensures that every process can get a turn at some point in the future.
* A ''k-bounded waiting property'' gives a more precise commitment than lockout-freedom. Lockout-freedom ensures every process can access the critical section eventually: it gives no guarantee about how long the wait will be. In practice, a process could be overtaken an arbitrary or unbounded number of times by other higher-priority processes before it gets its turn. Under a ''k''-bounded waiting property, each process has a finite maximum wait time. This works by setting a limit to the number of times other processes can cut in line, so that no process can enter the critical section more than ''k'' times while another is waiting.<ref name="Distributed computing: fundamentals, simulations, and advanced topics">{{cite book|last1=Attiya|first1=Hagit|last2=Welch|first2=Jennifer|title=Distributed computing: fundamentals, simulations, and advanced topics|date=25 March 2004|publisher=John Wiley & Sons, Inc.|isbn=978-0-471-45324-6|url=http://ca.wiley.com/WileyCDA/WileyTitle/productCd-0471453242.html}}</ref>

Every process's program can be partitioned into four sections, resulting in four states. Program execution cycles through these four states in order:<ref>{{Citation | url=http://research.microsoft.com/en-us/um/people/lamport/pubs/mutual2.pdf | last=Lamport | first=Leslie | title = The Mutual Exclusion Problem Part II: Statement and Solutions | journal=Journal of the Association for Computing Machinery |date = 26 June 2000| volume=33 | issue=2 | pages=313–348 | doi=10.1145/5383.5384 | s2cid=12012739 }}</ref>
[[File:State graph 2.png|thumb|the cycle of sections of a single process]]

;Non-Critical Section: Operation is outside the critical section; the process is not using or requesting the shared resource.

;Trying: The process attempts to enter the critical section.

;Critical Section: The process is allowed to access the shared resource in this section.

;Exit: The process leaves the critical section and makes the shared resource available to other processes.

If a process wishes to enter the critical section, it must first execute the trying section and wait until it acquires access to the critical section. After the process has executed its critical section and is finished with the shared resources, it needs to execute the exit section to release them for other processes' use. The process then returns to its non-critical section.