10th ed. chapter 07 [Link]

(Latest Revision: Mon Mar 16, 2020)

[2020/03/16: minor edits to discussion of the dining philosophers problem]
[2019/06/03: minor edits]
[2019/03/27: changed some image file formats]
[2019/03/21: corrected some format]
[2019/03/20: corrected a few typos]
[2019/03/17: added notes for up to the end of the chapter]

Chapter Seven -- Synchronization Examples -- Lecture Notes

• 7.0 Objectives

◦ Explain the bounded-buffer, readers-writers, and dining-philosophers synchronization problems.

◦ Describe specific tools used by Linux and Windows to solve process synchronization problems.
◦ Illustrate how POSIX and Java can be used to solve process synchronization problems.
◦ Design and develop solutions to process synchronization problems using POSIX and Java APIs.
(We won't do any actual design work)

• 7.1 Classic Problems of Synchronization

The authors present "classic" problems that are often used to test new synchronization tools.

◦ 7.1.1 The Bounded Buffer Problem

We can solve the bounded buffer problem by encapsulating the functionality of the counter in
semaphores, as illustrated by the code below.

---------------------
/* All these variables and types are shared */
#define BUFFER_SIZE 10
typedef struct
{
/* declare desired fields for the buffer item type */
} item ;

item buffer[BUFFER_SIZE] ; // the buffer implemented as an array of items

int in=0, /* in == where the next item is added */

out=0; /* out == where the next item is removed */
semaphore full(0), /* full->value == the number of full buffers */
empty(BUFFER_SIZE) ; /* empty->value == the number of empty buffers */
---------------------
Producer's Code
do
{
/* produce an item in nextp */
wait (empty) ;
buffer[in]= nextp ;
in = (in + 1) % BUFFER_SIZE ;
signal(full) ;
} while (true) ;
---------------------
Consumer's Code

1 of 9 16-09-2021, 17:57
10th ed. chapter 07 [Link]

do
{
wait (full) ;
nextc = buffer[out] ;
out = (out + 1) % BUFFER_SIZE ;
signal(empty) ;
/* consume nextc */
} while (true) ;
---------------------

◦ 7.1.2 The Readers-Writers Problem

Readers/Writers Problem Synopsis

Several processes share access to a file. Some of the processes (readers) never do anything but
read the file. Others (writers) may perform writes on the file when they access it. The problem is
to synchronize the processes so that readers can share the file concurrently but writers get
exclusive access. There are different versions of the problem, for example:

2 of 9 16-09-2021, 17:57
10th ed. chapter 07 [Link]

Solution to First Readers/Writers, Writer Code

Solution to First Readers/Writers, Reader Code

▪ The first readers-writers problem: no reader will be kept waiting unless a writer has
already obtained permission to access the file.

3 of 9 16-09-2021, 17:57
10th ed. chapter 07 [Link]

▪ The second readers-writers problem: once a writer is ready, that writer performs its
access as soon as possible.

A solution to either of the two problems above may result in starvation. (In the example code
provided in the text, writers can starve.)

A compromise might be a protocol that:

▪ allows all processes to be served in FIFO order, and
▪ allows groups of readers between writers to access the file concurrently.

Many operating systems now make reader-writer locks available to system programmers.
Processes that want only to read from a file can acquire a (shared) read-lock. Processes that want
to write request an exclusive writer's lock.

◦ 7.1.3 The Dining-Philosophers Problem

Figure 7.5: Dining Philosophers Problem

One way to understand this problem is to think of five processes and five disk drives arranged in
a circle, with the drives and the processes alternating. Each process occasionally needs to get
exclusive access to the disk drives on its 'left' and 'right' in order to transfer some data from one
to the other. The problem is to synchronize the processes so they get the access they need without
experiencing indefinite postponement. The protocol has to resolve competition between pairs of
processes that have to share the disk drive between them.

We can also think of the processes as philosophers, and the drives as chopsticks for eating rice.

▪ [Link] Semaphore Solution

4 of 9 16-09-2021, 17:57
10th ed. chapter 07 [Link]

Dining Philosopher Code That Can Deadlock

The example protocol proposed in this section allows deadlock to occur, an extreme form
of starvation.

There are several ways to solve the problem. Resource ordering provides a very simple
solution. A satisfactory solution to the problem would

1. make sure only one process at a time can access any any disk drive;
2. when some drive D is not being used, allow only processes that are trying to acquire
or release D to participate in the decision as to which process gets possession of D
next, and make sure this decision is not postponed indefinitely;
3. make sure there exists a bound on the number of times that other processes are
allowed to make a data transfer after one process P has made a request to begin a
transfer and before P is allowed to perform the transfer.

◦ [Link] Monitor Solution

▪ The text shows some code that employs a monitor and some client code to create a partial
solution to the dining philosophers problem. (Mutual exclusion is assured, and deadlock is
impossible, but starvation can occur.

▪ In order to eat, a philosopher P has to wait for this event: E = [both neighbors of P are not
eating]. There is no built-in, up-front limit to how many times a philosopher different from
P will eat before E happens. In other words, P can be postponed indefinitely.

• 7.2 Synchronization within the Kernel

5 of 9 16-09-2021, 17:57
10th ed. chapter 07 [Link]

◦ We look at examples of synchronization tools used in Windows and in Linux.

◦ 7.2.1 Synchronization in Windows

▪ The Windows kernel is multithreaded. It supports real-time applications and multiple

processors.

▪ On a uni-processor it relies to some extent on masking interrupts to insure exclusive access

to global shared data.

▪ On a multiprocessor, it uses spinlocks to guard short sections of code accessing global

resources. The OS ensures that a thread holding a spinlock will not be preempted. (This
helps allow the thread to quickly finish using the resource, and release it.)

▪ Threads outside the kernel can use dispatcher objects to synchronize.

▪ synchronization can take the form of mutex, semaphore, event, or timer.
▪ Events are used much like conditions -- to wait for a desired condition to occur.
▪ Timers are to notify thread(s) that a specific amount of time has expired.

▪ There's a Windows synchronization tool available in user-mode called a critical-section

object. If waiting is required, it starts off busy-waiting like a spinlock, but after waiting
"too long" it blocks. This method avoids the overhead of context switching when waits are
short, and also avoids excessive waste of CPU cycles.

◦ 7.2.2 Synchronization in Linux

▪ The Linux kernel was nonpreemptive through much of its development (like many
versions of unix). That means a kernel process could not be preempted. Since version 2.6,
the Linux kernel is fully preemptive.

▪ Linux supports atomic integers.

▪ Linux supports mutex locks that have a blocking wait operation.
▪ Linux has spinlocks for waits of short duration.
▪ Linux has semaphores for longer waits.
▪ Reader-writer versions of both spinlocks and semaphores are available.

▪ On uni-processors, Linux enforces exclusive access by temporarily disabling preemption

of the kernel.

• 7.3 POSIX Synchronization

Almost all of the synchronization tools discussed in the previous section are only available for use by
kernel code. The POSIX API discussed in this section provides tools for user-level application code.
(However, bear in mind that POSIX tools must be implemented using kernel-level synchronization
tools.)

▪ The Pthreads API offers mutex locks, condition variables, and read-write locks

▪ Semaphores and spinlocks are often available as extensions to the standard package.

6 of 9 16-09-2021, 17:57
10th ed. chapter 07 [Link]

◦ 7.3.1 POSIX Mutex Locks

The POSIX API offers mutex locks that have a blocking wait operation. They are used to solve
critical section problems in this manner:
#include <pthread.h>
pthread_mutex_t mutex ;
pthread_mutex_init (&mutex, NULL) ;
...
/* other stuff in the program */
...
pthread_mutex_lock (&mutex) ;
/* critical section */
pthread_mutex_unlock (&mutex) ;

◦ 7.3.2 POSIX Semaphores

Semaphores and spinlocks are often available as extensions to the standard package. There are
named and unnamed semaphores.

▪ [Link] POSIX Named Semaphores

Named semaphores are given a name when created, and it is easy for multiple processes to
share a named semaphore, because the system makes the semaphore available to any
process that 'knows' the name.

MacOS and Linux have named POSIX semaphores.

▪ [Link] POSIX Unnamed Semaphores

Unnamed semaphores are similar to named semaphores, but it's easier to guarantee that an
unnamed semaphore can be used only by threads belonging to a certain process.

However, it is possible for unnamed semaphores to be shared by threads from different

processes.

◦ 7.3.3 POSIX Condition Variables

POSIX condition variables work much like the condition variables that were presented in chapter
6 as part of the structure of monitors. However, POSIX does not support monitors, so POSIX
condition variables are implemented differently.

It is necessary to use a POSIX mutex lock with a POSIX condition variable. Using the two
together, it is possible for a process to wait on a condition variable for some Boolean value to
become true (like waiting until x == y, where x and y are two variables).

• 7.4 Synchronization in Java

Java has a kind of monitor, reentrant locks, semaphores, condition variables, atomic variables, and a
compare_and_swap instruction.

◦ 7.4.1 Java Monitors

7 of 9 16-09-2021, 17:57
10th ed. chapter 07 [Link]

Every Java object has an associated lock. Programmers can declare a method to be synchronized,
and that means a thread calling the method is required to hold the lock. Threads can block
waiting for the lock in a structure called the entry set.

When a thread begins executing in the monitor, it may need to wait for a condition to be met.
(One example: a consumer that waits when the buffer is empty.) There is a wait() function for
that purpose. There is also a notify() function that another thread can use to signal that the
condition may have changed. (For example, to signal to a waiting consumer, a producer can call
notify() after it puts an item in the buffer.) A thread that calls wait() is placed in a structure
called the wait set, and it blocks.

◦ 7.4.2 Java Reentrant Locks

The reentrant lock is an object used for enforcing mutual exclusion. There are lock() and
unlock() methods for acquiring and releasing access. If a thread calls lock() when the reentrant
lock is available, or if the thread already owns the lock, then the thread returns with possession
of the lock. Otherwise, the thread blocks.

◦ 7.4.3 Java Semaphores

Java has counting semaphores. The wait and signal operations are called acquire() and
release(). The semantics of these semaphores are different from those discussed in chapter 6. It
is possible to initialize a Java semaphore with a negative value. If so, threads must perform
releases before acquires can succeed.

◦ 7.4.4 Java Condition Variables

Java condition variables are similar to those described in section 6.7. Similar to the case with
POSIX condition variables, it is necessary to use a Java condition variable with a reentrant lock.
There are await() and signal() methods for waiting and signaling on Java condition variables.

• 7.5 Alternative Approaches

This section explores hardware and program language support for designing thread-safe concurrent
applications. Such support is increasingly important because of the widespread emphasis nowadays on
multicore and multithreaded computing.

◦ 7.5.1 Transactional Memory

▪ A transactional memory system is capable of insuring that a sequence of memory read-

write operations are atomic. Such a sequence is called a memory transaction.

▪ Given a transactional memory system to rely upon, a programmer can solve a mutual
exclusion problem simply by specifying that a critical section is to be treated as a memory
transaction.

▪ With software transactional memory (STM), the compiler generates code that insures the
atomicity of the memory transaction, resorting to the use of "low-level" locking, where
necessary.

8 of 9 16-09-2021, 17:57
10th ed. chapter 07 [Link]

▪ Hardware transactional memory (HTM) uses "hardware cache hierarchies and cache
coherency protocols."

◦ 7.5.2 OpenMP

▪ OpenMP has a #pragma omp critical compiler directive that marks a code region as a
critical section.

▪ The compiler generates code that protects the region. It works about the same as protecting
the region with a mutex.

◦ 7.5.3 Functional Programming Languages

▪ There has been a greater emphasis on functional programming languages because, unlike
imperative languages, they do not maintain state. Consequently most of the
synchronization problems discussed in this chapter are not at issue for functional language
programmers.

9 of 9 16-09-2021, 17:57