Chapter 5: Process

Synchronization

Operating System Concepts – 9th Edition Silberschatz, Galvin and Gagne

 Chapter 5: Process Synchronization
 Background
 The Critical-Section Problem
 Peterson’s Solution
 Synchronization Hardware
 Mutex Locks
 Semaphores
 Classic Problems of Synchronization
 Monitors
 Synchronization Examples
 Alternative Approaches

Operating System Concepts – 9th Edition 5.2 Silberschatz, Galvin and Gagne
 Background
 Processes can execute concurrently
 May be interrupted at any time, partially
completing execution
 Concurrent access to shared data may result in
data inconsistency
 Maintaining data consistency requires
mechanisms to ensure the orderly execution of
cooperating processes

Operating System Concepts – 9th Edition 5.3 Silberschatz, Galvin and Gagne
 Process Synchronization
 Coordination of process execution so that no two
processes can access the same shared data and
resources.
 Ensures that processes can safely share resources
without interfering with one another.
 Generally used in multiprocessor systems
 Tools: Semaphores, Mutex, Monitors

Operating System Concepts – 9th Edition 5.4 Silberschatz, Galvin and Gagne
 Process Synchronization
 Advantages:
 Data consistency
 Integrity
 To avoid the risk of deadlocks
 Based on synchronization, the processes can be
categorized as
 Independent : The execution of one process does not
affect the execution of other processes.
 Cooperative: A process that can affect or be affected
by other processes executing in the system.

Operating System Concepts – 9th Edition 5.5 Silberschatz, Galvin and Gagne
 Race condition
 When more than one process executes the same code
or accesses the same memory or any shared variable in
that condition, there is a chance that the output or
value of the shared variable is incorrect, so all of the
processes must race to say that my output is correct.
This is known as a race condition.
 A race condition is a situation that may occur inside a
critical section. This happens when the result of
multiple thread execution in the critical section differs
according to the order in which the threads execute.

Operating System Concepts – 9th Edition 5.6 Silberschatz, Galvin and Gagne
 Race condition
Different execution order may
give different results for B
Initial Value of B=2
 Case 1: P1(1), P1(2),
P2(1),P2(2)
C=1, B=2, D= 4, B=3
 Case 2: P2(1),P2(2), P1(1),
P1(2)
D=4,B=3,C=2,B=4
 Case 3: P1(1), P2(1),P2(2),
P1(2)
C=1, D= 2, B=1, B=2
 Case 4: P2(1), P1(1),P1(2),
P2(2)
D= 4, C=1, B=2, B=3

Operating System Concepts – 9th Edition 5.7 Silberschatz, Galvin and Gagne
 Critical Section Problem
 Consider system of n processes {p0, p1, … pn-1}
 Each process has critical section segment of code
 Process may be changing common variables,
updating table, writing file, etc
 When one process in critical section, no other
may be in its critical section
 Critical section problem is to design protocol to
solve this
 Each process must ask permission to enter critical
section in entry section, may follow critical
section with exit section, then remainder section

Operating System Concepts – 9th Edition 5.8 Silberschatz, Galvin and Gagne
 Critical Section
 Four essential elements of the critical section:
 Entry Section: It is part of the process which decides
the entry of a particular process.
 Critical Section: This part allows one process to enter
and modify the shared variable.
 Exit Section: Exit section allows the other process that
are waiting in the Entry Section, to enter into the
Critical Sections. It also checks that a process that
finished its execution should be removed through this
Section.
 Remainder Section: All other parts of the Code, which is
not in Critical, Entry, and Exit Section, are known as the
Remainder Section.

Operating System Concepts – 9th Edition 5.9 Silberschatz, Galvin and Gagne
 Critical Section

Operating System Concepts – 9th Edition 5.10 Silberschatz, Galvin and Gagne
 Algorithm for Process Pi

do {

while (turn == j);

critical section
turn = j;
remainder section
} while (true);

Operating System Concepts – 9th Edition 5.11 Silberschatz, Galvin and Gagne
 Solution to Critical-Section Problem
The critical section problem needs a solution to synchronize the
different processes. The solution to the critical section
problem must satisfy the following conditions
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 - Progress means that if a process is not using the
critical section, then it should not stop any other process from
accessing it. In other words, any process can enter a critical
section if it is free.
3. Bounded Waiting - A bound must exist 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
 Assume that each process executes at a nonzero speed
 No assumption concerning relative speed of the n
processes

Operating System Concepts – 9th Edition 5.12 Silberschatz, Galvin and Gagne
 Critical-Section Handling in OS
Two approaches depending on if kernel is
preemptive or non- preemptive
 Preemptive – allows preemption of process
when running in kernel mode
 Non-preemptive – runs until exits kernel mode,
blocks, or voluntarily yields CPU
Essentially free of race conditions in kernel
mode

Operating System Concepts – 9th Edition 5.13 Silberschatz, Galvin and Gagne
 Critical-Section Handling in OS
Widely used solutions to critical section problems:
 Synchronization hardware
 Lock and unlock
 Test and set
 2-process solution
 Mutex locks
 Semaphores solution
 Monitors
 Spinlocks

Operating System Concepts – 9th Edition 5.14 Silberschatz, Galvin and Gagne
 Synchronization Hardware solution: Using Locks

do {
acquire lock
critical section
release lock
remainder section
} while (TRUE);

While(lock!=0);
Lock=1 Entry Section

Critical Section

Lock=0 EXit Section

Operating System Concepts – 9th Edition 5.15 Silberschatz, Galvin and Gagne
 Solution to CS Problem Using Test and Set
Case1
1 While(test_and P1 P2
2 _set(&lock); Entry Section
Initially,
3 lock=false
Critical Section
target= true=
4 Lock=false Exit Section lock
r=false
Line 2
boolean test_and_set(boolean executes,
*target) lock=1
{ P1 in critical Try to enter
boolean r=*target; section into C.S, so
target=true; entry code
return r;
will run but
}
lock =, but
now line 1 is
true as 1==1,
So cannot
Operating System Concepts – 9th Edition 5.16
enter
Silberschatz, C.S
Galvin and Gagne
 Solution to Critical-section Problem Using Turn

1 int turn=0;
2 while(turn!=0); Entry Section

3 Critical Section

4 turn=1 Exit Section

• Mutual exclusion
• Progress

Operating System Concepts – 9th Edition 5.17 Silberschatz, Galvin and Gagne
 Mutex Locks
 Mutexes are binary variables that serve as locks. When a process locks a mutex,
it signifies that it has access to a critical section. Other processes attempting to
lock the same mutex will be blocked until it is released.
 Execute in user mode
 Simplest is mutex lock
 Protect a critical section by first acquire() a lock then
release() the lock
 Boolean variable indicating if lock is available or not
 Calls to acquire() and release() must be atomic
 Usually implemented via hardware atomic instructions
 But this solution requires busy waiting
 This lock therefore called a spinlock

Operating System Concepts – 9th Edition 5.18 Silberschatz, Galvin and Gagne
 acquire() and release()
 acquire() {
while (!available)
; /* busy wait */
available = false;
}
 release() {
available = true;
}
 do {
acquire lock
critical section
release lock
remainder section
} while (true);

Operating System Concepts – 9th Edition 5.19 Silberschatz, Galvin and Gagne
 Semaphore Usage
 Counting semaphore – integer value can range over an
unrestricted domain
 Binary semaphore – integer value can range only between 0
and 1
 Same as a mutex lock
 Can solve various synchronization problems
 Consider P1 and P2 that require S1 to happen before S2
Create a semaphore “synch” initialized to 0
P1:
S1;
signal(synch);
P2:
wait(synch);
S2;
 Can implement a counting semaphore S as a binary
semaphore

Operating System Concepts – 9th Edition 5.20 Silberschatz, Galvin and Gagne
 Semaphore
 Can only be accessed via two indivisible (atomic) operations
 Used in entry section
 wait() and signal()
 Originally called P() and V()
 Definition of the wait() operation
wait(S) {
while (S <= 0)
; // busy wait
S--;
}
 Definition of the signal() operation
signal(S) {
S++;
}

Operating System Concepts – 9th Edition 5.21 Silberschatz, Galvin and Gagne
 Semaphore Implementation with no Busy waiting

 With each semaphore there is an associated

waiting queue
 Each entry in a waiting queue has two data items:
 value (of type integer)
 pointer to next record in the list
 Two operations:
 block – place the process invoking the
operation on the appropriate waiting queue
 wakeup – remove one of processes in the
waiting queue and place it in the ready queue
 typedef struct{
int value;
struct process *list;
} semaphore;

Operating System Concepts – 9th Edition 5.22 Silberschatz, Galvin and Gagne
 Implementation with no Busy waiting (Cont.)

wait(semaphore *S) {
S->value--;
if (S->value < 0) {
add this process to S->list;
block();
}
}

signal(semaphore *S) {
S->value++;
if (S->value <= 0) {
remove a process P from S->list;
wakeup(P);
}
}

Operating System Concepts – 9th Edition 5.23 Silberschatz, Galvin and Gagne
 Semaphore
 To enter into the critical Assume s=3; P1,P2,P3,P4,P5
section, first the process
P1, s=3-1=2
needs to go through entry
section if(2<0) no, means P1 can enter C.S
 s is integer variable/
P2, s=2-1=1
if(0<0) no, means P2 can enter C.S
semaphore.
P3, s=1-1=0
Wait(Semaphore S) if(0<0) no, means P3 can enter C.S
{ P4, s=0-1=-1
s.value= s.value -1; if(-1<0) yes, means P4 cannot enter C.S
If(s.value<0) P4 block
{ P5, s=-1-1=-2
if(-2<0) yes, means P5 cannot enter C.S
Put process(PCB) in suspended
P5 block
list block();
}
else
return;
}

C. S P1, P2,P3

Operating System Concepts – 9th Edition 5.24 Silberschatz, Galvin and Gagne
 Semaphore
 To exit from critical section, Suspended list[ P4,P5]
the process needs to go
Let P1 has completed its work
through exit section
While exit
 s is integer variable/
S= -2+1= -1
semaphore.
-1<0 thus P4 will be picked from
Signal(Semaphore S) suspended list and put into ready queue
{ according to FCFS
s.value= s.value +1; Similarly,
If(s.value<=0) P2 has completed its work
While exit
{ S= -1+1= 0
Select process from suspended 0<0 thus P5 will be picked from
list
suspended list and put into ready
Wakeup() queue according to FCFS
}
Now, p4, p5 ready then they have to
run entry code
return;
}
C. S P3

Operating System Concepts – 9th Edition 5.25 Silberschatz, Galvin and Gagne
 Binary Semaphore

wait(semaphore *S) {
S.value--;
if (S.value ==1 ) {
S.value=0; }
else
block();
}
}
signal(semaphore *S) {
if (Suspended list is empty) {
s.value=1;}
else
remove a process P from S->list;
wakeup(P);
}
x

Operating System Concepts – 9th Edition 5.26 Silberschatz, Galvin and Gagne
 Synchronization Hardware
 Many systems provide hardware support for
implementing the critical section code.
 All solutions below based on idea of locking
 Protecting critical regions via locks
 Uniprocessors – could disable interrupts
 Currently running code would execute without
preemption
 Generally too inefficient on multiprocessor
systems
 Operating systems using this not broadly
scalable
 Modern machines provide special atomic hardware
instructions
 Atomic = non-interruptible
 Either test memory word and set value
 Or swap contents of two memory words

Operating System Concepts – 9th Edition 5.27 Silberschatz, Galvin and Gagne
 Deadlock and Starvation
 Deadlock – two or more processes are waiting
indefinitely for an event that can be caused by only one
of the waiting processes
 Let S and Q be two semaphores initialized to 1
P0 P1
wait(S); wait(Q);
wait(Q); wait(S);
... ...
signal(S); signal(Q);
signal(Q); signal(S);

 Starvation – indefinite blocking

 A process may never be removed from the semaphore queue
in which it is suspended
 Priority Inversion – Scheduling problem when lower-
priority process holds a lock needed by higher-priority
process
 Solved via priority-inheritance protocol

Operating System Concepts – 9th Edition 5.28 Silberschatz, Galvin and Gagne
 Classical Problems of Synchronization
 Classical problems used to test newly-proposed
synchronization schemes
 Bounded-Buffer Problem
 Readers and Writers Problem
 Dining-Philosophers Problem

Operating System Concepts – 9th Edition 5.29 Silberschatz, Galvin and Gagne
 Bounded-Buffer Problem

 Also known as producer consumer problem

 Producers: These processes generate data items and put
them into the buffer. However, they must wait if the buffer is
full.
 Consumers: These processes consume data items from the
buffer. They must wait if the buffer is empty.
 The challenge is to ensure that producers and
consumers can safely access the buffer concurrently
without race conditions, deadlocks, or data
corruption.
 Solutions: Mutex, Semaphores.

Operating System Concepts – 9th Edition 5.30 Silberschatz, Galvin and Gagne
 Bounded-Buffer Problem

 n buffers, each can hold one item

 Semaphore mutex initialized to the value 1
 m, a binary semaphore which is used to acquire
and release the lock.
 Semaphore empty initialized to the value n
 empty, a counting semaphore whose initial value
is the number of slots in the buffer, since, initially
all slots are empty
 Track empty slots
 Semaphore full initialized to the value 0
 full, a counting semaphore whose initial value is
0.
 Track empty slots

Operating System Concepts – 9th Edition 5.31 Silberschatz, Galvin and Gagne
 Bounded Buffer Problem (Cont.)
Producer: • a producer first waits until there
do is atleast one empty slot.
{ • Then it decrements the empty
// wait until empty > 0 and semaphore because, there will
then decrement 'empty' now be one less empty slot,
wait(empty); since the producer is going to
// acquire lock insert data in one of those slots.
wait(mutex); • Then, it acquires lock on the
buffer, so that the consumer
/* perform the insert cannot access the buffer until
operation in a slot */ producer completes its operation.
• After performing the insert
// release lock operation, the lock is released
signal(mutex); and the value of full is
// increment 'full' incremented because the
signal(full); producer has just filled a slot in
} the buffer.
while(TRUE)

Operating System Concepts – 9th Edition 5.32 Silberschatz, Galvin and Gagne
 Bounded Buffer Problem (Cont.)
• The consumer waits until there is Consumer:
atleast one full slot in the buffer. do
• Then it decrements the full {
semaphore because the number // wait until full > 0 and
of occupied slots will be decreased then decrement 'full'
by one, after the consumer wait(full);
completes its operation. // acquire the lock
• After that, the consumer acquires wait(mutex);
lock on the buffer.
• Following that, the consumer /* perform the remove
completes the removal operation operation in a slot */
so that the data from one of the
full slots is removed. // release the lock
• Then, the consumer releases the signal(mutex);
lock. // increment 'empty'
• Finally, the empty semaphore is signal(empty);
incremented by 1, because the }
consumer has just removed data while(TRUE);
from an occupied slot, thus
making it empty.
Operating System Concepts – 9th Edition 5.33 Silberschatz, Galvin and Gagne
 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

Operating System Concepts – 9th Edition 5.34 Silberschatz, Galvin and Gagne
 Readers-Writers Problem
 Several variations of how readers and writers are
considered – all involve some form of priorities
 Shared Data
 Data set
 Semaphore rw_mutex initialized to 1
 Semaphore mutex initialized to 1
 Integer read_count initialized to 0

Operating System Concepts – 9th Edition 5.35 Silberschatz, Galvin and Gagne
 Readers-Writers Problem (Cont.)

 The structure of a writer process

do {
wait(rw_mutex);
...
/* writing is performed */
...
signal(rw_mutex);
} while (true);

Operating System Concepts – 9th Edition 5.36 Silberschatz, Galvin and Gagne
 Readers-Writers Problem (Cont.)
 The structure of a reader process
do {
wait(mutex);
read_count++;
if (read_count == 1)
wait(rw_mutex);
signal(mutex);
...
/* reading is performed */
...
wait(mutex);
read count--;
if (read_count == 0)
signal(rw_mutex);
signal(mutex);
} while (true);

Operating System Concepts – 9th Edition 5.37 Silberschatz, Galvin and Gagne
 Readers-Writers Problem Variations
 First variation – no reader kept waiting unless
writer has permission to use shared object
 Second variation – once writer is ready, it
performs the write ASAP
 Both may have starvation leading to even
more variations
 Problem is solved on some systems by kernel
providing reader-writer locks

Operating System Concepts – 9th Edition 5.38 Silberschatz, Galvin and Gagne
 Dining-Philosophers Problem

 Philosophers spend their lives alternating thinking and

eating
 Don’t interact with their neighbors, occasionally try to
pick up 2 chopsticks (one at a time) to eat from bowl
 Need both to eat, then release both when done
 In the case of 5 philosophers
 Shared data
 Bowl of rice (data set)
 Semaphore chopstick [5] initialized to 1

Operating System Concepts – 9th Edition 5.39 Silberschatz, Galvin and Gagne
 Dining-Philosophers Problem

 To eat a philosopher needs both their right and a left

chopstick. A philosopher can only eat if both immediate left
and right chopsticks of the philosopher is available.
 In case if both immediate left and right chopsticks of the
philosopher are not available then the philosopher puts down
their (either left or right) chopstick and starts thinking again.
 The dining philosopher demonstrates a large class of
concurrency control problems hence it's a classic
synchronization problem.

Operating System Concepts – 9th Edition 5.40 Silberschatz, Galvin and Gagne
 Dining-Philosophers Problem Algorithm

P1: i=1
Wait (chopstick[1])
Wait(chopstick[(1+1)
%5])=2

• Mutual Exclusion –yes

• But deadlock- may be

Operating System Concepts – 9th Edition 5.41 Silberschatz, Galvin and Gagne
 Dining-Philosophers Problem Algorithm (Cont.)

 Deadlock handling
 Allow at most 4 philosophers to be sitting
simultaneously at the table.
 Allow a philosopher to pick up the forks
only if both are available (picking must be
done in a critical section.
 Use an asymmetric solution -- an odd-
numbered philosopher picks up first the
left chopstick and then the right chopstick.
Even-numbered philosopher picks up first
the right chopstick and then the left
chopstick.

Operating System Concepts – 9th Edition 5.42 Silberschatz, Galvin and Gagne
 Dining-Philosophers Problem Algorithm (Cont.)

 Deadlock handling
 Allow at most 4 philosophers to be sitting
simultaneously at the table.
 Allow a philosopher to pick up the forks
only if both are available (picking must be
done in a critical section.
 Use an asymmetric solution -- an odd-
numbered philosopher picks up first the
left chopstick and then the right chopstick.
Even-numbered philosopher picks up first
the right chopstick and then the left
chopstick.

Operating System Concepts – 9th Edition 5.43 Silberschatz, Galvin and Gagne
 Problems with Semaphores

 Incorrect use of semaphore operations:

 signal (mutex) …. wait (mutex)

 wait (mutex) … wait (mutex)

 Omitting of wait (mutex) or signal (mutex) (or

both)

 Deadlock and starvation are possible.

Operating System Concepts – 9th Edition 5.44 Silberschatz, Galvin and Gagne
 References

 Modern Operating Systems Ed: 4 Author: Tanenbaum

Publisher: Prentice-Hall, Inc. ISBN-10: 013359162X
 Abraham Silberschatz, Peter Baer Galvin and Greg Gagne,
“Operating System Concepts”, Ninth Edition, John Wiley & Sons
(ASIA) Pvt. Ltd
 https://www.geeksforgeeks.org/introduction-of-proc
ess-synchronization/

Operating System Concepts – 9th Edition 5.45 Silberschatz, Galvin and Gagne
 End of Chapter 5

Operating System Concepts – 9th Edition Silberschatz, Galvin and Gagne