O'Reilly logo

Concurrent and Distributed Computing in Java by Vijay K. Garg

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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

images

Now the execution of P0 and P1 may get interleaved as follows:

images

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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required