Operating systems
Module-3
M 3.1 Process Synchronization
M 3.2 Deadlock
By: M Yogi Reddy
Assistant Professor
CSE Dept.
GITAM University, Hyd.
Process Synchronization
• Critical section problem
• Peterson’s solution
• Synchronization hardware
• Mutex locks
• Semaphores
• Classic problems of synchronization
• Monitors
What is Process Synchronization?
• In the OS, there are a number of processes present in a
particular state. At the same time, we have a limited
amount of resources present, so those resources need to be
shared among various processes. But you should make sure
that no two processes are using the same resource at the
same time because this may lead to data inconsistency. So,
this requires processes to be synchronized, handling system
resources and processes to avoid such situation is known as
Process Synchronization.
• Maintaining data consistency demands to ensure
synchronized execution of cooperating processes.
Classic Banking Example (My SBI Account)
Process A Process B Process A Process B
(ATM) (NetBanking) (ATM) (NetBanking)
Initial Balance is Initial Balance is Balance is Rs.100
Rs.100 Rs.100
Deposit Rs.50
Deposit Rs.50 Deposit Rs.100
Now Balance is
Now Balance is Now Balance is
Rs.150
Rs.150 Rs.200
Balance is Rs.150
Deposit Rs.100
Now Balance is
Rs.250
• On the basis of synchronization, processes are
categorized as one of the following two types:
– Independent Process : Execution of one process does
not affects the execution of other processes.
– Cooperative Process : Execution of one process affects
the execution of other processes.
• Process synchronization problem arises in the case
of Cooperative process also because resources
and variables are shared in Cooperative processes.
Example of Producer-Consumer Problem
count
P C
r o
o in out n
..
d s
u .. u
c m
e .. e
r r
I2
I1
Buffer (0,1, …….., n-1)
Producer Code Consumer Code
Producer(int itemP) Consumer(int itemC)
{ {
While(true) While(true)
{ {
while(count == buffersize); while(count == 0);
buffer[in] = itemP; itemC = buffer[out];
in = (in+1) mod buffersize; out = (out+1) mod buffersize;
count++; count--;
}Producer(itemP); }Consumer(itemC);
} }
Critical Section(CS) problem
• Critical section is a code segment that can be accessed by
only one process at a time. Critical section contains shared
variables which need to be synchronized to maintain
consistency of data variables.
• Critical section(CS): The portion of program text where the
shared variables or shared resources or shared data will be
placed. Example of variable is count
• Non-Critical section(NCS): The portion of program text
where the independent code of the process will be placed.
Example of variable is in
Process Synchronization solution using
Critical Section
• Entry Section – To enter the critical section code, a
process must request permission. Entry Section code
implements this request.
• Critical Section – This is the segment of code where
process changes common variables, updates a table,
writes to a file and so on. When 1 process is executing in
its critical section, no other process is allowed to execute
in its critical section.
• Exit Section – After the critical section is executed , this is
followed by exit section code which marks the end of
critical section code.
• Remainder Section – The remaining code of the process is
Main blocks of process
known as remaining section.
Any solution to the critical section problem must satisfy three requirements:
• Mutual Exclusion(M/E): If a process P1 is executing in its critical section,
no other process can execute in critical section. It means only one
process is allowed in critical section at any point of time.
• Progress: If no process is executing outside the critical section should
block and the other interested process from entering into critical section
when CS free. So any process running in CS will block because maybe that
process is going outside from the CS and other process trying to enter
the CS.
• Bounded Waiting: When a process makes a request for getting into
critical section, there is a specific time limit about number of processes
can get into their critical section. So, when the time limit is reached, the
system must allow request to the process to get into its CS.
Synchronization Solution Types
• Software Type:
Peterson’s solution
Lock Variables
• Hardware Type:
Test and Set Lock (TSL)
• OS Type(Semaphores):
Counting Semaphore
Binary Semaphore
• Compiler and Programming support Type:
Monitors
Synchronization Software
1. Peterson’s Solution
• This is a software based solution to Critical Section Problem.
• It’s for 2 processes which alternate execution between then critical section
and remainder section. Say, P1 is the first process and P2 is the second
process.
• The 2 processes should share 2 variables with each other. The variables are
turn, flag [2]
• Turn – It indicates the process who should enter into its critical section(initial
the turn value is 0).
• Flag Array – It tells whether a process is ready to enter its critical section.
• Let flag[0] indicate process P1. If flag[0] = F , then Process P1 is ready to
execute in its critical section.
• Let flag[1] indicates process P2. If flag[1] = F , then Process P2 is ready to
execute in its critical section.
• Now let’s take a look at peterson’s Algorithm –
P1 P2
While(1) While(1)
{ {
flag[0] = T; flag[1] = T;
turn = 1; turn = 0;
while(turn == 1 && flag[1] == T); while(turn == 0 && flag[0] == T);
Critical Section(CS) Critical Section(CS)
flag[0] = F; flag[1] = F;
} }
• Peterson’s Solution preserves all three conditions :
– Mutual Exclusion is assured as only one process can access
the critical section at any time.
– Progress is also assured, as a process outside the critical
section does not block other processes from entering the
critical section.
– Bounded Waiting is preserved as every process gets a fair
chance.
• Disadvantages of Peterson’s Solution
– It involves Busy waiting
– It is limited to 2 processes.
2. Lock Variables
• Lock variable is a software synchronization mechanism.
• It uses multiple processes (at least 2 process)
• It uses a lock variable to provide the synchronization among the
processes executing concurrently.
• However, it completely fails to provide the synchronization.
• Initially, lock value is set to 0. Void EnterySection(int process)
• Lock value = 0 means the {
while(lock != 0);
critical section is currently lock = 1;
vacant and no process is }
present inside it.
Critical Section(CS)
• Lock value = 1 means the
critical section is currently Void ExitSection(int process)
{
occupied and a process is lock = 0;
present inside it. }
Finally,
• Mutual exclusion is not satisfied in lock variable
solution
• Progress is satisfied in lock variable solution
• Bounded waiting is not satisfied in lock variable
solution
Synchronization Hardware
Test and Set Lock (TSL) problem
• Test and Set Lock (TSL) is a hardware synchronization
mechanism.
• It uses a test and set instruction to provide the
synchronization among the processes executing
concurrently.
• If one process is currently executing a test-and-set(),
no other process is allowed to begin another test-and-
set until the first process test-and-set() is finished. So
it is called test and set instruction.
Test-and-set(lock)
{
• Initially, lock value is set to 0. temp = lock;
• Lock value = 0 means the }
return temp;
critical section is currently
Void EnterySection(int process)
vacant and no process is {
present inside it. while(Test-and-set(lock));
Lock = 1;
• Lock value = 1 means the }
critical section is currently Critical Section(CS)
occupied and a process is Void ExitSection(int process)
present inside it. {
lock = 0;
}
Finally,
• Mutual exclusion is satisfied in TSL solution
• Progress is satisfied in TSL solution
• Bounded waiting is not satisfied in TSL solution
OS Type(Semaphores)
• The hardware-based solutions to the critical section
problems are complicated for application programmers to
use. To overcome this difficulty, we can use a
synchronization tool called a semaphore.
• Semaphore is denoted by S. S is an integer variable.
• Semaphore has two standard atomic operations:
– wait() or Down
– signal() or Up
• The wait() operation was originally termed P(To decrement).
• The Signal() was originally called V(To increment).
• The definition of wait() is as follows:
Wait(S)
{
While(S <= 0 ); II no-op
S-- ;
}
• The definition of signal() is as follows:
Signal(S)
{
S++ ;
}
1. Counting Semaphores
• Counting semaphores values from -∞ to +∞. For
example [-5,+5].
Wait(semaphore S) Signal(semaphore S)
{ {
S = S-1; S = S+1;
if(S < 0) if(S <= 0)
{ {
//put the process in suspend list //select the process from suspend
sleep(); list
} wakeup();
else }
return; else
} return;
}
• Down() operation is successful if the semaphore
value is greater than equal to 1.
• There is no unsuccessful up() operation, it always
successful.
• Consider a system where counting semaphore
value is initialized to +17, the various semaphore
operations like 23P, 18V, 16P, 14V, 1P are
performed, then what is the final value of
semaphore?
2. Binary Semaphores
• Binary semaphores values only between 0 and 1.
• binary semaphores are known as mutex locks, as
they are locks that provide mutual exclusion.
Wait(semaphore S) Signal(semaphore S)
{ {
if( S == 1) if(suspend list is empty)
S = 0; S = 1;
else else
{ {
//put the process in suspend list //select the process from suspend list
sleep(); wakeup();
} }
} }
• The down() operation is successful only when semaphore value is 1.
• There is no unsuccessful up() operation, it always successful.
• Four cases of binary semaphore:
Case 1: S=1
P(S);
Case 2: S=1
V(S);
Case 3: S=0
P(S);
Case 4: S = 0;
V(S);
• Consider each process(Pi) where i = 1 to 9, executes the below
code: Repeat
P(mutex);
CS
V(mutex);
Forever
The process P10 executes below code:
Repeat
V(mutex);
CS
V(mutex);
Forever
The initial value of binary semaphore mutex = 1, what is the max.
number of process that may be present inside the critical section(CS)
at any point of time?
Classic Problems on Synchronization
1. Bounded buffer (ProducerConsumer)
problem using semaphore
• In Bounded Buffer Problem there are
three entities storage buffer slots,
consumer and producer.
• The producer tries to store data in the
storage slots while the consumer tries
to remove the data from the buffer
storage.
• We need to make sure that the access to data buffer is only
either to producer or consumer, i.e. when producer is placing
the item in the buffer the consumer shouldn’t consume (or)
when consumer is removing the item from the buffer the
producer shouldn’t producer.
• We do that via three semaphore entities –
– mutex : used to lock and release critical section (mutex = 1).
– empty : Keeps tab on number empty slots in the buffer at any
given time
• Initialized as N as all slots are empty.(empty = N)
– full : Keeps tab on number of entities in buffer at any given time.
• Initialized as 0 (full = 0)
Producer Program Consumer Program
int itemP; int itemC;
While(1) While(1)
{ {
produce-item(itemP); Down(full);
Down(empty); Down(mutex);
Down(mutex); itemc = Buffer[out];
CS
Buffer[in] = itemP; out = (out+1)mod N;
CS
in = (in+1)mod N; Up(mutex);
Up(mutex); Up(empty);
Up(full); consumer-item(itemC)
} }
2. Readers Writers Problem
• The problem statement is, if a database(DB) or file
is to be shared among several concurrent process,
there can be broadly 2 types of users –
– Readers: Reader are those processes/users which only
read the data
– Writers: Writers are those processes which also write,
that is, they change the data.
• If reader is in the DB, then
writers are not allowed.
• If reader is in the DB, then
readers are allowed.
• If writer is in the DB, then
readers are not allowed.
• If writer is in the DB, then
writers are not allowed.
• We do that via three semaphore entities –
– mutex : used to lock and release critical section for
reader (mutex = 1).
– db : It is a binary semaphore used by readers and
writers ( db = 1)
– Reader counts(rc) : It represents the no of readers
presents in the DB at any point of time.
• Initialized as 0 (rc = 0)
Reader Program Writer Program
While(1)
{ While(1)
Down(mutex); {
rc = rc +1; Down(db);
if(rc == 1) DB CS
Down(db); Up(db)
Up(mutex); }
DB CS
Down(mutex);
rc = rc -1;
if( rc == 0)
Up(db);
Up(mutex);
}
3. Dining Philosophers
Problem
• The Scenario –
– 5 silent philosophers sit at a
round table
– A fork is placed between
each pair of adjacent
philosophers
– Eating is NOT limited
philosophers left: infinite
supply assumed
The Rules :–
• Each philosopher must ‘alternately’ think and eat
• A philosopher can only eat noodles when he has both left
and right forks
• Each fork can be held by only 1 philosopher
• After eating, he needs to put down both forks so they
become available to others
• A philosopher can grab the fork on left or right as they
become available
• He can’t start eating until he has both of them
Void Philosopher(int i)
{
While(1)
{
Thinking();
Take_fork(i);
Take_fork( (i+1) mod N);
Eat();
Put_fork(i);
Put_fork( (i+1) mod N)
}
}
Monitors
• The monitor is one of the ways to achieve Process
synchronization.
• The monitor is supported by programming
languages to achieve mutual exclusion between
processes.
• For example Java Synchronized methods. Java
provides wait() and notify() constructs.
• It is the collection of condition
variables and procedures combined
together in a special kind of module
or a package.
• The processes running outside the
monitor can’t access the internal
variable of the monitor but can call
procedures of the monitor.
• Only one process at a time can
execute code inside monitors.
Syntax of Monitor
• The figure shows a schematic of a monitor, with an
entry queue of processes waiting their turn to
execute monitor operations ( methods. )
• In order to fully realize the potential of monitors, we
need to introduce one additional new data type,
known as a condition.
– A variable of type condition has only two legal
operations, wait and signal. I.e. if X was defined as type
condition, then legal operations would be X.wait() and
X.signal( )
– The wait operation blocks a process until some other process
calls signal, and adds the blocked process onto a list
associated with that condition.
– The signal process does nothing if there are no processes
waiting on that condition. Otherwise it wakes up exactly one
process from the condition's list of waiting processes.
Let see the figure shows in the next slide
Monitor with condition variables
• But now there is a potential problem - If process P
within the monitor issues a signal that would wake up
process Q also within the monitor, then there would
be two processes running simultaneously within the
monitor, violating the exclusion requirement.
Accordingly there are two possible solutions to this
dilemma:
– Signal and wait - When process P issues the signal to wake
up process Q, P then waits, either for Q to leave the
monitor or on some other condition.
– Signal and continue - When P issues the signal, Q waits,
either for P to exit the monitor or for some other condition.
