Mutual Exclusion Problem
When processes share data, it is important to synchronize their access to the data so that updates are not lost as a result of concurrent accesses and the data are not corrupted. This can be seen from the following example. Assume that the initial value of a shared variable x is 0 and that there are two processes, P0 and P1 such that each one of them increments x by the following statement in some high-level programming language:
x = x + 1
It is natural for the programmer to assume that the final value of x is 2 after both the processes have executed. However, this may not happen if the programmer does not ensure that x = x + 1 is executed atomically. The statement x = x + 1 may compile into the machine-level code of the form
Now the execution of P0 and P1 may get interleaved as follows:
Thus both processes load the value 0 into their registers and finally store 1 into x resulting in the “lost update” problem.
To avoid this problem, the statement x = x + 1 should be executed
atomically. A section of the code that needs to be executed atomically is also called a critical region or a critical section. The problem of ensuring that a critical section is executed atomically is called the mutual exclusion problem. This is one of the most ...