Chapter 6

Process Synchronization

Module 6: Process Synchronization

6.1 Background 6.2 The Critical-Section Problem 6.3 Petersons Solution

6.4 Synchronization Hardware

6.5 Semaphores 6.6 Classic Problems of Synchronization 6.7 Monitors 6.8 Synchronization Examples

6.9 Atomic Transactions (skip)

Operating System Concepts 7th Edition, Feb 8, 2005

6.2

Silberschatz, Galvin and Gagne 2005

6.1 Background

Background

Concurrent access of two or more processes to shared data may result in data inconsistency Maintaining data consistency requires mechanisms to ensure the orderly execution of cooperating processes Suppose that we wanted to provide a solution to the consumer-producer problem that can potentially fill all of the locations in a buffer

An integer variable count is used to keep track of the number of filled locations. Initially, count is set to 0. It is incremented by the producer when it produces a new item and places it in a buffer location and is decremented by the consumer when it consumes an item from a buffer location The integer variables in and out are used as indexes into the buffer

Buffer

count

in
6.4

out

Operating System Concepts 7th Edition, Feb 8, 2005

Silberschatz, Galvin and Gagne 2005

Producer and Consumer

// Producer item nextProduced; while (true) { /* produce an item and put in nextProduced */ . . . while (count == BUFFER_SIZE); // do nothing buffer [in] = nextProduced;

in = (in + 1) % BUFFER_SIZE;
count++; } // End while

#define BUFFER_SIZE 10 typedef struct {. . .} item;

// Consumer item nextConsumed; while (true) { while (count == 0); // do nothing

item buffer[BUFFER_SIZE];
int in = 0; int out = 0; int count = 0;

nextConsumed =
count--; /*

buffer[out];

out = (out + 1) % BUFFER_SIZE; consume the item in nextConsumed

. . . } // End while
Operating System Concepts 7th Edition, Feb 8, 2005 6.5 Silberschatz, Galvin and Gagne 2005

Race Condition

Although both the producer and consumer code segments are correct when each runs sequentially, they may not function correctly when executed concurrently count++ could be implemented as register1 = count register1 = register1 + 1 count = register1 count-- could be implemented as register2 = count register2 = register2 - 1 count = register2

One execution may interleave the above statements in an arbitrary order, where count initially is 5: T0: T1: T2: T3: T4: T5: producer producer consumer consumer producer consumer executes executes executes executes executes executes register1 = count register1 = register1 + 1 register2 = count register2 = register2 - 1 count = register1 count = register2 {register1 = {register1 = {register2 = {register2 = {count = 6 } {count = 4} 5} 6} 5} 4}

This results in the incorrect state of counter == 4, indicating that 4 locations are full in the buffer, when, in fact, 5 locations are full

Operating System Concepts 7th Edition, Feb 8, 2005

6.6

Silberschatz, Galvin and Gagne 2005

Race Condition (continued)

A race condition has occurred

Several processes are able to access and manipulate the same data concurrently The outcome of the execution depends on the particular order in which the data access and manipulation takes place

To guard against the race condition shown in the previous example, we

need to guarantee that only one process at a time can manipulate the counter variable

Operating System Concepts 7th Edition, Feb 8, 2005

6.7

Silberschatz, Galvin and Gagne 2005

6.2 The Critical Section Problem

The Critical Section Problem

Consider a system consisting of n processes in which each process has a segment of code called a critical section

In the critical section, the process may change a common variable, update a table, write to a file, etc. When one process is updating in its critical section, no other process can be allowed to execute in its critical section (i.e., no two processes may execute in their critical sections at the same time)

The critical section problem is to design a protocol that the processes can use to cooperate in manipulating common data

A solution is to use three code sections

Entry section: Contains the code where each process requests permission to enter its critical section; this code can be run concurrently Critical section: Contains the code for data manipulation; this code is only allowed to run exclusively for one process at a time Remainder section: Contains any remaining code that can execute concurrently

Operating System Concepts 7th Edition, Feb 8, 2005

6.9

Silberschatz, Galvin and Gagne 2005

General structure of a process with a critical section

while (TRUE) {
entry section

critical section

remainder section

} // End while

Operating System Concepts 7th Edition, Feb 8, 2005

6.10

Silberschatz, Galvin and Gagne 2005

Solution to Critical-Section Problem

A solution to the critical section problem must satisfy the following three requirements:
1. Mutual Exclusion - If process Pi is executing in its critical section, then no other processes can be executing in their critical sections 2. Progress - If no process is executing in its critical section and there exist some processes that wish to enter their critical sections, then only those processes that are not executing in their remainder sections can participate in the decision on who will enter its critical section next; this selection cannot be postponed indefinitely

Bounded Waiting - There exists a bound, or limit, on the number of times that other processes are allowed to enter their critical sections after a process has made a request to enter its critical section, and before that request is granted

We assume that each process executes at a nonzero speed We make no assumption concerning relative speed of the N processes

Operating System Concepts 7th Edition, Feb 8, 2005

6.11

Silberschatz, Galvin and Gagne 2005

Protecting Kernel Code from Race Conditions

Various kernel code processes that perform the following activities must be safeguarded from possible race conditions

Maintaining a common list of open files Updating structures for maintaining memory allocation Updating structures for maintaining process lists Updating structures used in interrupt handling

Two general approaches are used to handle critical sections in operating systems

Preemptive kernels Non-preemptive kernels

Operating System Concepts 7th Edition, Feb 8, 2005

6.12

Silberschatz, Galvin and Gagne 2005

Preemptive and Non-preemptive Kernels

Preemptive kernel

Allows a process to be preempted while it is running in kernel mode Must be carefully designed to ensure that shared kernel data are free from race conditions Is more suitable for real-time programming May be more responsive because it wont be waiting for a kernel mode process to relinquish the CPU Is implemented in Linux and Solaris Does not allow a process to be preempted while it is running in kernel mode Allows a process to run until the process does one of the following: exits kernel mode, blocks, or voluntarily gives up the CPU (i.e., terminates)

Non-preemptive kernel

Is essentially free from race conditions on kernel data structure

Is implemented in Windows XP and traditional UNIX

Operating System Concepts 7th Edition, Feb 8, 2005

6.13

Silberschatz, Galvin and Gagne 2005

6.3 Petersons Solution

Petersons Solution
Petersons solution is a classic software-based solution to the critical

section problem

It provides a good algorithm description of solving the critical section problem It illustrates some of the complexities involved in designing software that addresses the three solution requirements (mutual exclusion, progress, and bounded waiting) Unfortunately, the assembly language implementations in modern computer architectures will not guarantee that Petersons solution will work (i.e., LOAD and STORE are not atomic)

Operating System Concepts 7th Edition, Feb 8, 2005

6.15

Silberschatz, Galvin and Gagne 2005

Petersons Solution (continued)

The solution is restricted to two processes that alternate execution between their critical sections and remainder sections It assumes that the LOAD and STORE instructions are atomic (they cannot be interrupted)

The processes are numbered P0 and P1

For convenience, Pj denotes the other process, that is, j equals 1 - i

The processes share two variables: int turn;

boolean flag[2];
It turn == i, then process Pi is allowed to execute in its critical section If flag[i] == true, then Pi is ready to enter its critical section

The variable turn indicates whose turn it is to enter the critical section

The flag array is used to indicate if a process is ready to enter its critical section

Operating System Concepts 7th Edition, Feb 8, 2005

6.16

Silberschatz, Galvin and Gagne 2005

Algorithm for Process Pi

int turn;
boolean flag[2];

while (TRUE) { flag[i] = TRUE; // I am ready to enter my critical section turn = j; // But you can go first if you are ready

while ( flag[j] && turn == j); // Youre in your critical section

// so I will just wait CRITICAL SECTION // I am now in my critical section flag[i] = FALSE; // I am done with my critical section REMAINDER SECTION // I have other processing to do now } // End while
Operating System Concepts 7th Edition, Feb 8, 2005 Silberschatz, Galvin and Gagne 2005

6.17

6.4 Synchronization Hardware

The Concept of a Lock

In general, any solution to the critical section problem requires

some form of lock

Race conditions are prevented by requiring that critical regions be

protected by locks

A process must acquire a lock before entering its critical section A process releases the lock when it exits its critical section while (TRUE)

{
// Acquire lock // Critical section // Release lock // Remainder section } // End while
Operating System Concepts 7th Edition, Feb 8, 2005 6.19 Silberschatz, Galvin and Gagne 2005

Synchronization Hardware
Many systems provide hardware support for critical section code Single processor could disable interrupts

Currently running code would execute without preemption Generally too inefficient on multiprocessor systems
Operating

systems using this are not broadly scalable

Modern machines provide special atomic hardware instructions

Atomic

= non-interruptible

Either test memory word and set value boolean TestAndSet (boolean *target); Or swap contents of two memory words void Swap (boolean *a, boolean *b);

Operating System Concepts 7th Edition, Feb 8, 2005

6.20

Silberschatz, Galvin and Gagne 2005

TestAndSet Instruction
Definition:

boolean TestAndSet (boolean *target) { boolean originalValue = *target; *target = TRUE; return originalValue; } // End TestAndSet
The function always sets the lock parameter to TRUE, but

returns the original value of the lock

Operating System Concepts 7th Edition, Feb 8, 2005

6.21

Silberschatz, Galvin and Gagne 2005

Solution using TestAndSet

Shared Boolean variable named lock, initialized to FALSE Solution:

while (TRUE) { while ( TestAndSet (&lock )) ; // Critical section . . . lock = FALSE; // Remainder section . . . } // End while // do nothing

Operating System Concepts 7th Edition, Feb 8, 2005

6.22

Silberschatz, Galvin and Gagne 2005

Swap Instruction

Definition:

void Swap (boolean *a, boolean *b) {

boolean temp = *a;

*a = *b; *b = temp: } // End Swap

Operating System Concepts 7th Edition, Feb 8, 2005

6.23

Silberschatz, Galvin and Gagne 2005

Solution using Swap

Shared Boolean variable lock initialized to FALSE; Each process has a local Boolean variable key.
Solution: while (TRUE) { key = TRUE; while ( key == TRUE) Swap (&lock, &key ); // critical section

. . .
lock = FALSE; // . . . remainder section

} // End while

Operating System Concepts 7th Edition, Feb 8, 2005

6.24

Silberschatz, Galvin and Gagne 2005

6.5 Semaphores

Semaphore

Another possible synchronization tool that is less complicated than TestAndSet() or Swap() is a semaphore
A semaphore S is an integer variable that, apart from initialization, is accessed only through two standard atomic operations: wait() and signal()

Originally these operations were called P() and V() wait(S) { while S <= 0 ; // do nothing

The wait() and signal() operations are each executed indivisibly

S--;
} // End wait

signal(S) { S++; } // End signal

Operating System Concepts 7th Edition, Feb 8, 2005

6.26

Silberschatz, Galvin and Gagne 2005

Semaphore as General Synchronization Tool

Operating systems often distinguish between counting and binary

semaphores

The value of a counting semaphore can range over an unrestricted domain

The value of a binary semaphore can range only between 0 and 1

On some systems, a binary semaphore is known as a mutex lock

Binary semaphores can be used to deal with the critical section problem for

multiple processes

The n processes share a semaphore, mutex, initialized to 1

while (TRUE) { wait(mutex); // Critical section signal(mutex); // Remainder section } // End while
Operating System Concepts 7th Edition, Feb 8, 2005 6.27 Silberschatz, Galvin and Gagne 2005

Semaphore as General Synchronization Tool (continued)

Counting semaphores can be used to control access to a given resource

consisting of a finite number of instances

The semaphore is initialized to the number of resources available Each process that wishes to use a resource performs a wait() operation

on the semaphore (i.e., a decrement)

When a process releases a resource, it performs a signal() operation on

the semaphore (i.e., an increment)

When the count for the semaphore reaches 0, all the resources are in use

Processes wanting to use a resource will block until the semaphore value becomes greater than 0

Semaphores can also be used to solve various synchronization problems

for concurrently running processes

Operating System Concepts 7th Edition, Feb 8, 2005

6.28

Silberschatz, Galvin and Gagne 2005

Semaphore Implementation

The main disadvantage of the semaphore definition given here so far is that is requires busy waiting

While a process is in its critical section, any other process that tries to enter its critical section must loop continuously in the entry section code

This semaphore implementation is called a spinlock because the process spins while waiting for the lock

To overcome the need for busy waiting, we can modify the definition of the wait() and signal() semaphore operations

When a process executes the wait() operation and finds that the semaphore value is not positive, it must wait

However, rather than engaging in busy waiting, the process can block itself The block() operation places a process into a waiting queue associated with the semaphore, and the state of the process is switched to the waiting state

A process that is blocked, waiting on a semaphore, is restarted when some other process executes a signal() operation

The process is restarted by a wakeup() operation, which changes the process from the waiting state to the ready state, and places it in the ready queue
6.29 Silberschatz, Galvin and Gagne 2005

Operating System Concepts 7th Edition, Feb 8, 2005

Semaphore Implementation with no busy waiting

To implement semaphores under this new definition, we define

a semaphore as a structure in C typedef struct { int value; struct process *list; } semaphore;
Each semaphore has an integer value and a list of processes

When a process must wait on a semaphore, the wait()

operation adds it to the list of processes A signal() operation removes one process from the list of waiting processes and awakens that process

Operating System Concepts 7th Edition, Feb 8, 2005

6.30

Silberschatz, Galvin and Gagne 2005

Semaphore Implementation with no busy waiting (Continued)

Implementation of wait() function: void wait (semaphore *S) { S->value--; if (S->value < 0) { add this process to waiting queue block(); } } // End wait

Implementation of signal() function: void signal (semaphore *S) { S->value++; if (S->value <= 0) { remove a process P from the waiting queue wakeup(P); } } // End signal

Operating System Concepts 7th Edition, Feb 8, 2005

6.31

Silberschatz, Galvin and Gagne 2005

Semaphore Implementation with no busy waiting (Continued)

The block() operation suspends the process that invokes it The wakeup() operation resumes the execution of a blocked process P These two operations would be provided by the operating system as basic system calls

The critical aspect of semaphores is that they be executed atomically

We must guarantee that no two processes can execute the wait() and signal() operations on the same semaphore at the same time In a single processor environment, we can solve this by simply inhibiting interrupts during the time the wait() and signal() operations are executing In a multi-processor environment, interrupts must be disabled on every processor

This can be a difficult task and can seriously diminish performance Consequently, alternative locking such as spinlocks are used instead

Operating System Concepts 7th Edition, Feb 8, 2005

6.32

Silberschatz, Galvin and Gagne 2005

Process Deadlock

The implementation of a semaphore with a waiting queue may result in a situation where two or more processes are waiting indefinitely for an event that can be caused only by one of the waiting processes The event in question is the execution of a signal() operation This situation is called a deadlock To illustrate, let S and Q be two semaphores initialized to 1

P0
wait (S); wait (Q); . . signal (S); signal (Q);

P1
wait (Q); wait (S); . . signal (Q); signal (S);

P0 executes wait(S) and then P1 executes wait(Q) When P0 then executes wait(Q), it must wait until P1 executes signal(Q) Similarly, when P1 executes wait(S), it must wait until P0 executes
signal(S)
Since these signal() operations cannot be executed, P0 and P1 are deadlocked
6.33 Silberschatz, Galvin and Gagne 2005

Operating System Concepts 7th Edition, Feb 8, 2005

Process Starvation
Another problem related to deadlocks is indefinite blocking, or

starvation
This is a situation in which processes wait indefinitely within the

semaphore
Starvation may occur if we add and remove processes from the list

associated with a semaphore in a last in, first out (LIFO) order

Operating System Concepts 7th Edition, Feb 8, 2005

6.34

Silberschatz, Galvin and Gagne 2005

6.6 Classic Problems of Synchronization

Classical Problems of Synchronization

Bounded-Buffer Problem Readers and Writers Problem Dining-Philosophers Problem

Operating System Concepts 7th Edition, Feb 8, 2005

6.36

Silberschatz, Galvin and Gagne 2005

Bounded-Buffer Problem
N buffers, each can hold one item Semaphore mutex initialized to the value 1 Semaphore full initialized to the value 0

Semaphore empty initialized to the value N.

Operating System Concepts 7th Edition, Feb 8, 2005

6.37

Silberschatz, Galvin and Gagne 2005

Bounded Buffer Problem (Cont.)

The structure of the producer process while (true) { // produce an item wait (empty); wait (mutex);

The structure of the consumer process while (true) { wait (full); wait (mutex); // remove an item from buffer signal (mutex);

// add the item to the buffer signal (mutex); signal (full); } }

signal (empty); // consume the removed item

Operating System Concepts 7th Edition, Feb 8, 2005

6.38

Silberschatz, Galvin and Gagne 2005

Readers-Writers Problem
A data set is shared among a number of concurrent processes

Readers only read the data set; they do not perform any updates Writers can both read and write.

Problem allow multiple readers to read at the same time. Only

one single writer can access the shared data at the same time.
Shared Data

Data set
Semaphore mutex initialized to 1. Semaphore wrt initialized to 1. Integer readcount initialized to 0.

Operating System Concepts 7th Edition, Feb 8, 2005

6.39

Silberschatz, Galvin and Gagne 2005

Readers-Writers Problem (Cont.)

The structure of a writer process while (true) { wait (wrt) ; // writing is performed

The structure of a reader process while (true) { wait (mutex) ; readcount ++ ; if (readercount == 1) wait (wrt) ; signal (mutex);

signal (wrt) ; } // reading is performed wait (mutex) ; readcount - - ; if (readcount == 0) signal (wrt) ; signal (mutex) ; }

Operating System Concepts 7th Edition, Feb 8, 2005

6.40

Silberschatz, Galvin and Gagne 2005

Dining-Philosophers Problem

Shared data

Bowl of rice (data set)

Semaphore chopstick [5] initialized to 1

Operating System Concepts 7th Edition, Feb 8, 2005

6.41

Silberschatz, Galvin and Gagne 2005

Dining-Philosophers Problem (Cont.)

The structure of Philosopher i:

while (true) { wait ( chopstick[i] ); wait ( chopStick[ (i + 1) % 5] ); // eat signal ( chopstick[i] );

signal (chopstick[ (i + 1) % 5] );
// think

}
Operating System Concepts 7th Edition, Feb 8, 2005 Silberschatz, Galvin and Gagne 2005

6.42

6.7 Monitors

Problems with Incorrect Use of Semaphores

Incorrect use; order of signal and wait are reversed; several processes are in the critical section at the same time; this violates the mutual exclusion requirement

signal (mutex) // Critical section wait (mutex)

Incorrect use; signal call replaced with wait call; deadlock will occur wait (mutex) // Critical section wait (mutex) // This should have correctly been signal(mutex) Incorrect use; omitting of wait (mutex) or signal (mutex) (or both); mutual exclusion is violated or deadlock will occur Normal section // Critical section Normal section

Operating System Concepts 7th Edition, Feb 8, 2005

6.44

Silberschatz, Galvin and Gagne 2005

Monitors

A high-level abstraction that provides a convenient and effective mechanism for process synchronization Only one process may be active within the monitor at a time monitor monitor-name { // shared variable declarations

procedure P1 () { . }
procedure Pn () {} initialization code ( .) { } }
Operating System Concepts 7th Edition, Feb 8, 2005 Silberschatz, Galvin and Gagne 2005

6.45

Schematic view of a Monitor

Operating System Concepts 7th Edition, Feb 8, 2005

6.46

Silberschatz, Galvin and Gagne 2005

Condition Variables
condition x, y;

Two operations can occur on a condition variable:

x.wait () a process that invokes the operation is suspended. x.signal () resumes one of the processes (if any) that invoked x.wait ()

Operating System Concepts 7th Edition, Feb 8, 2005

6.47

Silberschatz, Galvin and Gagne 2005

Monitor with Condition Variables

Operating System Concepts 7th Edition, Feb 8, 2005

6.48

Silberschatz, Galvin and Gagne 2005

Solution to Dining Philosophers

monitor DiningPhilosophers { enum { THINKING, HUNGRY, EATING} state [5] ; condition self [5]; void pickup (int i) { state[i] = HUNGRY; test(i); if (state[i] != EATING) self [i].wait; } void putdown (int i) { state[i] = THINKING; // test left and right neighbors test((i + 4) % 5); test((i + 1) % 5); } }
Operating System Concepts 7th Edition, Feb 8, 2005 6.49 Silberschatz, Galvin and Gagne 2005

Solution to Dining Philosophers (cont)

void test (int i) { if ( (state[(i + 4) % 5] != EATING) && (state[i] == HUNGRY) && (state[(i + 1) % 5] != EATING) ) { state[i] = EATING ; self[i].signal () ; } } initialization_code() { for (int i = 0; i < 5; i++) state[i] = THINKING; } }

Operating System Concepts 7th Edition, Feb 8, 2005

6.50

Silberschatz, Galvin and Gagne 2005

Solution to Dining Philosophers (cont)

Each philosopher I invokes the operations pickup()

and putdown() in the following sequence: dp.pickup (i) EAT dp.putdown (i)

Operating System Concepts 7th Edition, Feb 8, 2005

6.51

Silberschatz, Galvin and Gagne 2005

Monitor Implementation Using Semaphores

Variables semaphore mutex; // (initially = 1) semaphore next; // (initially = 0) int next-count = 0; Each procedure F will be replaced by wait(mutex); body of F; if (next-count > 0) signal(next) else signal(mutex);

Mutual exclusion within a monitor is ensured.

Operating System Concepts 7th Edition, Feb 8, 2005

6.52

Silberschatz, Galvin and Gagne 2005

Monitor Implementation

For each condition variable x, we have: semaphore x-sem; // (initially = 0) int x-count = 0;

The operation x.wait can be implemented as: x-count++; if (next-count > 0) signal(next); else signal(mutex); wait(x-sem); x-count--;

Operating System Concepts 7th Edition, Feb 8, 2005

6.53

Silberschatz, Galvin and Gagne 2005

Monitor Implementation
The operation x.signal can be implemented as:

if (x-count > 0) { next-count++; signal(x-sem); wait(next); next-count--; }

Operating System Concepts 7th Edition, Feb 8, 2005

6.54

Silberschatz, Galvin and Gagne 2005

6.8 Synchronization Examples

Synchronization Examples
Solaris Windows XP Linux Pthreads

Operating System Concepts 7th Edition, Feb 8, 2005

6.56

Silberschatz, Galvin and Gagne 2005

Solaris Synchronization
Implements a variety of locks to support multitasking,

multithreading (including real-time threads), and multiprocessing

Uses adaptive mutexes for efficiency when protecting data from

short code segments

Uses condition variables and readers-writers locks when longer

sections of code need access to data

Uses turnstiles to order the list of threads waiting to acquire either

an adaptive mutex or reader-writer lock

Operating System Concepts 7th Edition, Feb 8, 2005

6.57

Silberschatz, Galvin and Gagne 2005

Windows XP Synchronization
Uses interrupt masks to protect access to global resources on

uniprocessor systems
Uses spinlocks on multiprocessor systems

Also provides dispatcher objects which may act as either mutexes

and semaphores
Dispatcher objects may also provide events

An event acts much like a condition variable

Operating System Concepts 7th Edition, Feb 8, 2005

6.58

Silberschatz, Galvin and Gagne 2005

Linux Synchronization
Linux:

disables interrupts to implement short critical sections

Linux provides:

semaphores spin locks

Operating System Concepts 7th Edition, Feb 8, 2005

6.59

Silberschatz, Galvin and Gagne 2005

Java Synchronization between threads

public class SomeClass
{ . . . public synchronized void safeMethod() {

. . .
} }

SomeClass myObject = new SomeClass(); myObject.safeMethod();

Operating System Concepts 7th Edition, Feb 8, 2005

6.60

Silberschatz, Galvin and Gagne 2005

Pthreads Synchronization
Pthreads API is OS-independent It provides:

mutex locks condition variables

Non-portable extensions include:

read-write locks spin locks

Operating System Concepts 7th Edition, Feb 8, 2005

6.61

Silberschatz, Galvin and Gagne 2005

Pthreads Synchronization (continued)

#include <pthread.h>
int pthread_mutex_init(pthread_mutex_t *mutex, NULL); int pthread_mutex_lock(pthread_mutex_t *mutex); int pthread_mutex_unlock(pthread_mutex_t *mutex); int pthread_mutex_trylock(pthread_mutex_t *mutex);

int pthread_mutex_destroy(pthread_mutex_t *mutex);

Operating System Concepts 7th Edition, Feb 8, 2005

6.62

Silberschatz, Galvin and Gagne 2005

End of Chapter 6