PROCESS SYNCHRONIZATION
Process Synchronization
Process Synchronization means sharing system resources
by processes in a such a way that, Concurrent access to shared data is
handled thereby minimizing the chance of inconsistent data. Maintaining
data consistency demands mechanisms to
ensure synchronized execution of cooperating processes.
Critical Section problem: Critical Section is the part of a program
which tries to access shared resources. ... The critical section cannot be
executed by more than one process at the same time; operating
system faces the difficulties in allowing and disallowing the processes
from entering the critical section.
General structure of a Process:
Requirements for Critical-Section Solutions:
1. Mutual Exclusion. If process Pi is executing in its critical section (CS), then no
other process can execute in its CS.
2. Progress. If no process is executing in its CS and there exist some processes
that wish to enter their CS, then the selection of the process that will enter the
CS next cannot be postponed indefinitely.
3. Bounded Waiting. There exist a bound on the number of times that other
processes are allowed to enter their CS after a process has made a request to
enter its CS and before that request is granted.
Two general approaches are used to handle critical sections in operating
systems:
MANJULA PRASAD 1
PROCESS SYNCHRONIZATION
• preemptive kernels: A preemptive kernel allows a process to be
preempted while it is running in kernel mode.
• nonpreemptive kernels:A nonpreemptive kernel does not allow a
process running in kernel mode to be preempted; a kernel-mode process
will run until it exits kernel mode, blocks, or voluntarily yields control of
the CPU.
Peterson's algorithm
Boolean readyflag[2];
int turn;
void p0()
{
while(true)
{
readyflag[0]=true;
turn=1;
while(readyflag[1] && turn==1)
/*do nothing & wait*/
/*critical section*/
readyflag[0]=false;
/*reminder section*/
}}
void p1()
{
while(true)
{
readyflag[1]=true;
turn=0;
while(readyflag[0] && turn==0)
/*do nothing & wait*/
/*critical section*/
readyflag[1]=false;
/*reminder section*/
}}
Void main()
{
readyflag[0]=false;
readyflag[1]=false;
Parbegin(p0,p1);}
MANJULA PRASAD 2
PROCESS SYNCHRONIZATION
Peterson’s Algorithm Explanation
Peterson’s Algorithm is used to synchronize two processes. It uses two variables,
a bool array flag of size 2 and an int variable turn to accomplish it.
Initially the flags are false. When a process wants to execute it’s critical section,
it sets it’s flag to true and turn as the index of the other process. This means that
the process wants to execute but it will allow the other process to run first. The
process performs busy waiting until the other process has finished it’s own
critical section.
After this the current process enters it’s critical section and adds or removes a
random number from the shared buffer. After completing the critical section, it
sets it’s own flag to false, indication it does not wish to execute anymore.
Synchronization hardware
Process synchronization is the task of coordinating the execution of processes
in a way that no two processes can have access to the same shared data and
resources. ... Synchronization hardware is not a simple method to implement
for everyone, so the strict software method known as Mutex Locks was also
introduced.
Two mostly commonly implemented instructions are:
• TEST & SET Instruction
• Swap Instruction
TEST & SET Instruction
boolean TestAndSet (int i)
{
if(i==0)
{
i=1;
return true:
}
else
return false;
}
MANJULA PRASAD 3
PROCESS SYNCHRONIZATION
Mutual –Exclusion implementation with TestAndSet
Swap Instruction
void Swap(int reg, int memory)
{
int temp;
temp=memory;
memory=reg;
reg=temp;
}
Mutual –Exclusion implementation with Swap()
MANJULA PRASAD 4
PROCESS SYNCHRONIZATION
Advantages Synchronization hardware
• The use of machine instruction is applicable to any number of
processes
• It is simple & easy to multi-processor environment
• It supports multiple critical sections.
Disadvantages Synchronization hardware
• Busy waiting: A process waiting to its critical section consumes
processor time.
• Starvation: when a process leaves its critical section & more than
one process is waiting. therefore some processes may be denied
access, indefinitely leading starvation.
• Deadlock: Suppose process P1 enters its critical section but is
interrupted to give the processor to P2 which has higher priority.
If P2 tries to use the same resource as P1, it will be denied due
to mutual exclusion & keep waiting.
Semaphore
• Synchronization tool that does not require busy waiting
MANJULA PRASAD 5
PROCESS SYNCHRONIZATION
• Semaphore S – integer variable
• Two standard operations modify S: wait() and signal()
• Originally called P() and V()
• Less complicated
• Can only be accessed via two indivisible (atomic) operations
• wait (S) {
while S <= 0
; // no-op
S--;
}
• signal (S) {
S++;
}
Semaphore as General Synchronization Tool
• Counting semaphore – integer value can range over an
unrestricted domain
• Binary semaphore – integer value can range only between 0
and 1; can be simpler to implement
• Also known as mutex locks
• Can implement a counting semaphore S as a binary semaphore
• Provides mutual exclusion
Semaphore is simply a variable that is non-negative and
shared between threads. A semaphore is a signaling
mechanism, and a thread that is waiting on a semaphore can
be signaled by another thread. It uses two atomic operations,
1)wait, and 2) signal for the process synchronization.
A semaphore is simply a variable. This variable is used to solve critical section
problems and to achieve process synchronization in the multi processing
environment. A trivial semaphore is a plain variable that is changed (for
example, incremented or decremented, or toggled) depending on programmer-
defined conditions.
Semaphores are of two types:
MANJULA PRASAD 6
PROCESS SYNCHRONIZATION
1. Binary Semaphore – This is also known as mutex lock. It can
have only two values – 0 and 1. Its value is initialized to 1. It is
used to implement the solution of critical section problem with
multiple processes.
2. Counting Semaphore – Its value can range over an
unrestricted domain. It is used to control access to a resource
that has multiple instances.
Semaphore mutex; // initialized to 1
do {
wait (mutex);
// Critical Section
signal (mutex);
// remainder section
} while (TRUE);
Semaphore Implementation
• Must guarantee that no two processes can execute wait () and
signal () on the same semaphore at the same time
• Thus, implementation becomes the critical section problem
where the wait and signal code are placed in the critical section.
• Could now have busy waiting in critical section
implementation
• But implementation code is short
• Little busy waiting if critical section rarely occupied
• Note that applications may spend lots of time in critical sections
and therefore this is not a good solution.
Semaphore Implementation with no Busy waiting (Cont.)
• Implementation of wait:
wait(semaphore *S) {
S->value--;
if (S->value < 0) {
add this process to S->list;
MANJULA PRASAD 7
PROCESS SYNCHRONIZATION
block();
}
}
• Implementation of signal:
signal(semaphore *S) {
S->value++;
if (S->value <= 0) {
remove a process P from S->list;
wakeup(P);
}
}
Classical Problems of Synchronization
• Producer-Consumer problem or Bounded-Buffer Problem
• Readers and Writers Problem
• Dining-Philosophers Problem
Producer-Consumer problem or Bounded-Buffer Problem
• This problem is generalized in terms of the Producer Consumer
problem, where a finite buffer pool is used to exchange
messages between producer and consumer processes.
• Because the buffer pool has a maximum size, this problem is
often called the Bounded buffer problem.
• Solution to this problem is, creating two counting semaphores
"full" and "empty" to keep track of the current number of full
and empty buffers respectively.
Producer
int ItemCount=0;
void producer()
{
while (true)
{
item=produce_item();
if(ItemCount==BUFFER_SIZE)
MANJULA PRASAD 8
PROCESS SYNCHRONIZATION
sleep();
putItemIntoBuffer(item);
iItemCount=ItemCount+1;
If(ItemCount==1)
wakeup(consumer);
}
}
Consumer
void consumer()
{
while (true)
{
if(ItemCount==0)
sleep();
item=removeItemFromBuffer();
itemCount--;
If(ItemCount==BUFFER_SIZE-1)
wakeup(producer);
consume_item(item);
}
}
Producer Using Semaphore
MANJULA PRASAD 9
PROCESS SYNCHRONIZATION
Consumer Using Semaphore
Readers –Writers Problem
Consider a situation where we have a file shared between many
people.
If one of the people tries editing the file, no other person should be
reading or writing at the same time, otherwise changes will not be
visible to him/her.
MANJULA PRASAD 10
PROCESS SYNCHRONIZATION
However if some person is reading the file, then others may read it at
the same time.
• Precisely in OS we call this situation as the readers-writers
problem
Problem parameters:
• One set of data is shared among a number of processes
• Once a writer is ready, it performs its write. Only one writer may
write at a time
• If a process is writing, no other process can read it
• If at least one reader is reading, no other process can write
• Readers may not write and only read
Types of Readers –Writers Problem
• First readers –writers problem: readers preference
• Second readers –writers problem: writer preference
• Third readers –writers problem: both preference
Solution for First readers –writers problem
There is a shared resource which should be accessed by multiple
processes. There are two types of processes in this context. They
are reader and writer. Any number of readers can read from the
shared resource simultaneously, but only one writer can write to
the shared resource. When a writer is writing data to the
resource, no other process can access the resource.
A writer cannot write to the resource if there are non zero
number of readers accessing the resource at that time.
MANJULA PRASAD 11
PROCESS SYNCHRONIZATION
Dining philosopher problem
• The dining philosophers problem states that there are
5 philosophers sharing a circular table and they eat and think
alternatively.
• 5 philosophers sitting at a table doing one of two things – eating
or thinking. While eating they are not thinking, & while thinking
they are not eating.
MANJULA PRASAD 12
PROCESS SYNCHRONIZATION
Dining philosopher problem: Monitors
The monitor is the abstract data type which allows only one process
to execute in critical section at a time.
• 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
MANJULA PRASAD 13
PROCESS SYNCHRONIZATION
example Java Synchronized methods. Java provides wait() and
notify() constructs.
1. It is the collection of condition variables and procedures
combined together in a special kind of module or a package.
2. The processes running outside the monitor can’t access the
internal variable of the monitor but can call procedures of the
monitor.
3. Only one process at a time can execute code inside monitors.
Dining philosopher problem: Monitors
Condition Variables:
Two different operations are performed on the condition variables of
the monitor.
• Wait
• Signal
Dining philosopher problem: Monitors
• Wait operation
[Link]() : Process performing wait operation on any condition
variable are suspended. The suspended processes are placed in
block queue of that condition variable.
• Note: Each condition variable has its unique block queue.
• Signal operation
[Link](): When a process performs signal operation on
condition variable, one of the blocked processes is given
chance.
monitor philosopher
MANJULA PRASAD 14
PROCESS SYNCHRONIZATION
{
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((i +1)% 5);
test((i-1)% 5);
}
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;}}
MANJULA PRASAD 15