Concurrent and Distributed Computing in Java

Chapter 3

Synchronization Primitives

3.1 Introduction

All of our previous solutions to the mutual exclusion problem were wasteful in one regard. If a process is unable to enter the critical section, it repeatedly checks for the entry condition to be true. While a process is doing this, no useful work is accomplished. This way of waiting is called busy wait. Instead of checking the entry condition repeatedly, if the process checked the condition only when it could have become true, it would not waste CPU cycles. Accomplishing this requires support from the operating system.

In this chapter we introduce synchronization primitives that avoid busy wait. Synchronization primitives are used for mutual exclusion as well as to provide order between various operations by different threads. Although there are many types of synchronization constructs in various programming languages, two of them are most prevalent: semaphores and monitors. We discuss these constructs in this chapter.

3.2 Semaphores

Dijkstra proposed the concept of semaphore that solves the problem of busy wait. A semaphore has two fields, its value and a queue of blocked processes, and two operations associated with it—P() and V(). The semantics of a binary semaphore is shown in Figure 3.1. The value of a semaphore (or a binary semaphore) can be only false or true. The queue of blocked processes is initially empty and a process may add itself to the queue when it makes a call to P(). When a process calls P() and value is ...