Chapter 2

Mutual Exclusion Problem

2.1 Introduction

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 ...

Get Concurrent and Distributed Computing in Java now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.