CHAPTER 4
PROCESS SYNCHRONIZATION
Critical-Section Problem (CSP), Conditions of CSP, Semaphores, Classic
Synchronization Problems
Process Synchronization
As we understand in a multiprogramming environment a large number of
processes compete for limited number of resources. Concurrent access to
shared data at some time may result in data inconsistency
Process synchronization ensures that multiple processes access shared resources
without interfering with each other to prevent the possibility of inconsistency of data
due to concurrent access.
Lack of synchronization
Inconsistency: in IPC leads
When two orto:
more resources access shared data at same time
without synchronization. This can lead to conflicting changes, when one
process’s update is overwritten by another, causing data to become unreliable
and incorrect.
Loss of Data: When multiple processes try to write or modify the same shared
resource, if one process overwrites the data before another process finishes,
important data can be lost leading to incomplete and corrupted data.
Deadlock: When two or more processes get stuck, waiting for each other to
release their resources. None of the processes can continue and complete their
tasks so the system becomes unresponsive.
Need of Synchronization
Critical Section: It is the part of program where shared resources are
accessed by processes, only one process can execute critical section at a
time. If there are no shared resources then there is no need of
synchronization.
Race Condition: It is a situation where multiple processes are trying to
access the critical section and final result depends on the order in which
they finish their updates. Process Synchronization mechanism needs to
ensure that instructions are being executed in a required order only.
Pre-emption: If the process has not finished its job on shared resource and
gets pre-empted, the other process might end up reading an inconsistent
value if process synchronization is not done.
Race Condition
Race condition is a situation in which the output of a process depends on the execution sequence of process. i.e.
if we change the order of execution of different process with respect to other process the output may change.
Concurrent access to shared data at some time may result in data inconsistency for e.g.
P ()
{
Read(i);
i=i+1;
Write(i)
}
In above example, if initial value of i = 10. A process P1 comes reads ‘i’, updates ‘i’ to 11, but before performing
write operation on ‘i’ context switch occurs and control is transferred to Process P2 which is copy of P, P2 reads ‘i’,
updates ‘i’ to 11 and performs write operation on ‘i’. So, the value of i = 11 is saved in memory. Context switch
occurs again and control is transferred back to P1, P1 will not again execute the statements already executed, it
will only read left over statement and perform write operation on ‘i’, and same value i = 11 is saved in memory.
The problem here is that we perform two increment operations on ‘i’ but value of ‘i’ effectively increments only
one time from 10 to 11. But if the processes P1 and P2 are executed one after the other then final value of ‘i’ will
be 12.
General Structure of a Process
Initial Section: Where process is accessing
P()
private resources. {
Entry Section: Entry Section is that part of While(T)
code where, each process request for {
permission to enter its critical section.
Initial Section
Critical Section: Where process is
accessing shared resources. Entry Section
Exit Section: It is the section where a Critical Section
process will exit from its critical section. Exit Section
Remainder Section: Remaining Code. Remainder Section
}
}
Critical Section Problem
Critical Section is a code segment that can be accessed by only one process at a time. The critical
section contains shared variables that need to be synchronized to maintain the consistency of data
variables.
The critical section problem means designing a way for co-operative processes to access shared
resources without creating data inconsistency.
Criterion to Solve Critical Section Problem
1. Mutual Exclusion: No two processes should be present inside the critical section at the same time,
i.e. only one process is allowed in the critical section at an instant of time.
2. Progress: If no process is executing in its critical section and some processes wish to enter their
critical sections, then only those processes that are not executing in their remainder sections can
participate in deciding which will enter its critical section next(means other process will participate
which actually wish to enter) & there should be no deadlock.
3. Bounded Waiting: There exists a bound or a limit on the number of times a process is allowed to
enter its critical section and no process should wait indefinitely to enter the CS.
Mutual Exclusion and Progress are mandatory requirements that needs to be followed in order to write
a valid solution for critical section problem. Bounded waiting is optional criteria, if not satisfied then it
may lead to starvation.
Solutions to Critical Section Problem
We generally have the following solutions
to a Critical Section Problems:
Two Process Solution Hardware Solution
1. Using Boolean variable turn 1. Test and Set Lock
2. Using Boolean array flag 2. Disable interrupt
3. Peterson’s Solution
Operating System Solution
4. Counting Semaphore
5. Binary Semaphore
Two Process Solution
In general, it will be difficult to write a valid solution in the first go to solve
critical section problem among multiple processes, so it will be better to first
attempt two process solution and then generalize it to N-Process solution.
There are 3 different idea to achieve valid solution, in which some are invalid
while some are valid.
1. Using Boolean variable ‘turn’
2. Using Boolean array ‘flag’
3. Peterson’s Solution
Using Boolean variable ‘turn’
Here we will use a Boolean variable ‘turn’, which is initialize randomly(0/1).
The solution follows Mutual Exclusion as the two processes cannot enter the CS at
the same time.
The solution does not follow the Progress and Bounded Wait, as it is suffering
from the strict alternation. Because we never asked the process whether it wants
to enter the CS or not
P0 P1
while (1) while (1)
{ {
while (turn! = 0); while (turn! = 1);
Critical Section Critical Section
turn = 1; turn = 0;
Remainder section Remainder Section
} }
Using Boolean array flag
Here we will use a Boolean array ‘flag’ with two cells, where each cell is
initialized to F
This solution follows the Mutual Exclusion criteria but not Bounded Wait and
Progress. In order to achieve the progress, the system ended up being in a
deadlock state, deadlock occurs when ‘flag[0]’ becomes True and then
context switch occurs and ‘flag[1]’ also becomes True, therefore none of the
process P0 and P1 can continue its execution.
P0 P1
while (1) while (1)
{ {
flag [0] = T; flag [1] = T;
while (flag [1]); while (flag [0]);
Critical Section Critical Section
flag [0] = F; flag [1] = F;
Remainder section Remainder Section
} }
Peterson’s Solution
Peterson's solution is a classic software-based solution to the critical-section
problem for two process in which we use both: ‘turn’ and Boolean ‘flag’
This solution ensures Mutual Exclusion, Progress and Bounded Wait.
P0 P1
while (1) while (1)
{ {
flag [0] = flag [1] =
T; T; turn =
turn = 1;
while 0;
(turn = = while
1 && flag (turn = =
[1] = = 0 && flag
T); [0] = =T);
Critical Section Critical Section
flag [0] = F; flag [1] = F;
Dekker's algorithm
Pi Pj
do do
{ {
flag[i] = true; flag[j] = true;
while (flag[j]) while (flag[i])
{ {
if (turn == j) if (turn == i)
{ {
flag[i] = false; flag[j] = false;
while (turn== while (turn==
j) ; flag[i] = i) ; flag[j] =
true; true;
} }
} }
/* critical section /* critical section
*/ turn = j; */ turn = i;
flag[i] = false; flag[j] = false;
/* remainder section */ /* remainder
} section */
while (true); }
while (true);
Semaphores
Semaphores are synchronization tools using which we will attempt N-Process solution.
A semaphore S is a simple integer variable that helps coordinate processes by signaling
when a shared resources is free or busy, but apart from initialization it can be accessed
only through two standard atomic operations: wait(S) and signal(S).
The wait(S) operation was originally termed as P(S) and signal(S) was originally called
V(S).
Wait (P operation): It is used to test if another
process is executing critical section. If S >0
Wait(S) Signal(S)
then process is allowed to continue and S is {
decremented by 1. If S <= 0, the process {
waits until S becomes > 0. while(s<=0);
Signal (V operation): Used to increment value s++;
of S by 1, potentially unblocking other waiting
s--;
resources and allowing then to access the } }
resource.
Types of Semaphores
1. Binary Semaphore: Also known as mutex lock (mutual exclusion), its value
can range only b/w 0 and 1. It is used to implement the solution of critical
section problem with multiple processes and single resource.
2. Counting Semaphore: Its value can range over an unrestricted domain. It is
used to control access to a resource that has multiple instances. Counting
Semaphore S is initialized to the number of resources available.
Disadvantage
Busy Waiting: If a process is in critical section, then other processes trying to
enter the critical section will be waiting until the critical section is freed.
Busy waiting is looping continuously for S <= 0, that wastes CPU cycle.
Spin Lock: processes keep on spinning while waiting for the lock.
Solution to CS using Semaphores
Peterson’s Solution was confined to just two Pi()
processes, and since in a general system
can have N processes, Semaphores {
provides N-Processes solution. While(T)
While solving Critical Section Problem only {
we initialize semaphore S = 1.
Initial Section
Semaphores are going to ensure Mutual
Exclusion and Progress but does not ensure wait(s)
bounded waiting. Critical Section
signal(s)
Remainder Section
}
}
Classical Problems on Synchronization
There are number of actual industrial problem we try to solve in order to
improve our understand of Semaphores and their power of solving problems.
Here in this section, we will discuss a number of problems like
Producer consumer problem/ Bounder Buffer Problem
Reader-Writer problem
Dining Philosopher problem
The Sleeping Barber problem
Producer-Consumer Problem
Problem Definition – There are two process Producer and Consumers, producer
produces information and put it into a buffer which have n cell, that is consumed
by a consumer. Both Producer and Consumer can produce and consume only
one article at a time.
A producer needs to check whether the buffer is overflowed or not after
producing an item, before accessing the buffer.
Similarly, a consumer needs to check for an underflow before accessing the
buffer and then consume an item.
Also, the producer and consumer must be synchronized, so that once a producer
and consumer it accessing the buffer the other must wait.
Now to solve the problem we will be using three semaphores:
Semaphore S = 1 // CS
Semaphore E = n // Count Empty cells
Semaphore F = 0 // Count Filled cells
Producer() Consumer() Producer() Consumer()
Producer() Consumer() Producer() Consumer()
{ { { {
while(T) while(T) while(T) while(T)
{ { { {
// Produce an item
// Pick item from buffer
// Add item to
buffer
// Consume item
} } } }
Producer() Consumer()
Producer() Consumer()
{ {
while(T) while(T)
{ {
// Produce an item
wait(S)
wait(S) // Pick item from buffer
// Add item to buffer signal(S)
signal(S)
// Consume item
} }
Producer() Consumer()
Total three resources are { {
used while(T) while(T)
Semaphore E take count { {
of empty cells and over
// Produce an item wait(F)//UnderFlow
flow
wait(E)//OverFlow wait(S)
Semaphore F take count
of filled cells and under wait(S) // Pick item from buffer
flow
// Add item to buffer signal(S)
Semaphore S take care of
signal(S) wait(E)
buffer
wait(F) Consume item
} }
} }
Reader-Writer Problem
Suppose that a database is to be shared among several concurrent
processes. Some of these processes may want only to read the database
(readers), whereas others may want to update (that is, to read and write)
the database(writers).
If two readers access the shared data simultaneously, no adverse effects will
result. But, if a writer and some other process (either a reader or a writer)
access the database simultaneously, chaos may ensue.
To ensure that these difficulties do not arise, we require that the writers
have exclusive access to the shared database while writing to the database.
Solution using Semaphores
Points that needs to be taken care for generating a solution:
The solution may allow more than one reader at a time, but should not allow any
writer.
The solution should strictly not allow any reader or writer, while a writer is
performing a write operation.
The reader processes share the following data structures:
semaphore mutex = 1, wrt =1; // Two semaphores
int readcount = 0; // Variable
Three resources are used:
Semaphore ‘wrt’ is used for synchronization between WW, WR, RW
Semaphore ‘reader’ is used to synchronize between RR
‘Readcount’ is simple int variable which keep counts of number of readers
Writer() Reader() Writer() Reader()
Wait(wrt)
CS //Write CS //Read CS //Write CS //Read
Signal(wrt)
Writer() Reader()
Readcount++
Wait(wrt)
CS //Write CS //Read
Signal(wrt)
Readcount--
Writer() Reader()
Wait(mutex)
Readcount++
If(readcount ==1)
wait(wrt) // first
Wait(wrt) signal(mutex)
CS //Write CS //Read
Signal(wrt) Wait(mutex)
Readcount--
If(readcount ==0)
signal(wrt) // last
signal(mutex)
Dining Philosopher Problem
Scenario Setup: Five philosophers share a circular table
surrounded by five chairs, each belonging to one
philosopher. In the center of the table is a bowl of rice, and
the table is laid with five single chopsticks b/w each pair of
philosophers.
Activity Cycle: Philosopher alternate b/w thinking and
eating. They do not interact with each other while thinking.
Eating Process: From time to time, a philosopher gets
hungry and tries to pick up the two chopsticks that are
closest to her (the chopsticks that are between her and her
left and right neighbors).A philosopher may pick up only
one chopstick at a time. Obviously, he can’t pick up a
chopstick that is already held by a neighbor. Once a hungry
philosopher has both her chopsticks at the same time, she
eats without releasing the chopsticks.
Post Eating: After eating, the philosopher puts down both
of her chopsticks and starts thinking again.
Solution for Dining Philosophers
Void Philosopher (void)
{
while ( T )
{
Thinking ( ) ;
wait(chopstick [i]);
wait(chopstick([(i+1)%5]);
Eat( );
signal(chopstick [i]);
signal(chopstick([(i+1)%5]);
}
}
Here we have used an array of semaphores called chopstick[]
The above solution is not valid because there is a possibility of deadlock, when
every philosopher picks up a single chopstick, all chopsticks are acquired and
no chopstick is free. As a result, none of the philosophers can eat with single
chopstick and none will release chopstick resulting to a deadlock state.
The proposed solution for deadlock problem is
1. Allow at most four philosophers to be sitting simultaneously at the table.
2. Allow six chopstick to be used simultaneously at the table.
3. Allow a philosopher to pick up her chopsticks only if both chopsticks are
available (to do this, she must pick them up in a critical section).
4. One philosopher picks up her right chopstick first and then left chop stick,
i.e. reverse the sequence of any philosopher.
5. Odd philosopher picks up first her left chopstick and then her right
chopstick, whereas an even philosopher picks up her right chopstick and
then her left chopstick
The Sleeping Barber problem
Barbershop: A barbershop consists of a
waiting room with n chairs and a barber
room with one barber chair.
Customers: Customers arrive at random
intervals. If there is an available chair in the
waiting room, they sit and wait. If all chairs
are taken, they leave.
Barber: The barber sleeps if there are no
customers. If a customer arrives and the
barber is asleep, they wake the barber up.
Synchronization: The challenge is to
coordinate the interaction between the
barber and the customers using concurrent
programming mechanisms.
semaphore barber = 0; // Indicates if the barber is available
semaphore customer = 0; // Counts the waiting customers
semaphore mutex = 1; // Mutex for critical section
int waiting = 0; // Number of waiting customers
Disable Interrupt
This could be a hardware solution where
processes have a privilege instruction, i.e.
before entering into critical section , process
will disable all the interrupts and at time of
exit, it again enables the interrupts.
This solution is only used by OS, as if some
user process enter into critical section, then
can block the entire system.
Unfortunately, this solution is not as feasible
in a multiprocessor environment. Disabling
interrupts on a multiprocessor can be time
consuming, since the message is passed to all
the processors. This message passing delays
entry into each critical section and system
efficiency decreases.
Hardware Type Solution Test and Set
Software-based solutions such as Peterson’s are not guaranteed to work on
modern computer architectures. In the following discussions, we explore
several more solutions to the critical section problem using techniques
ranging from hardware to software, all these solutions are based on the
premise of locking – that is, protecting critical regions through the use of
locks.
The critical-section problem could be solved simply in a single-processor
environment if we could prevent interrupts from occurring while a shared
variable was being modified.
Many modern computer systems therefore provide special hardware
instructions that allow us either to test and modify the content of a word
atomically —that is, as one uninterruptible unit. We can use these special
instructions to solve the critical-section problem in a relatively simple
manner.
The important characteristic of this instruction is that it is executed
atomically. Thus, if two test and set() instructions are executed
simultaneously (each on a different CPU), they will be executed sequentially
in some arbitrary order.