Process Synchronization
Galvin 6th Edition Chap 7
Coopering Process
• One that can affect or be affected by other
processes executing in the system
• Cooperating processes can directly share
logical address space(both code and data) or
share data only through file.
• Concurrent access of shared data may result
in data inconsistencies
• Real time OS or Multiprocessing OS with
preemptive scheduling may result in data
inconsistency
– successive processes P1 and P2 sharing data or
same file record
– when the first write operation of P1 is not
completed fully
– P2 coming in may again try writing on it thus
loosing input or overwriting output
Producer Consumer Example
• A Count variable shared by producer and
consumer process
Producer Consumer
Count++ for each time Count-- for each time
produced,Count=5 consumed
Producing 1 more
Count=6
Then consuming 1
Count =5
Count++ and Count-- in Assembly
Lang(m/c Lang)-the atomic operation
Producer Consumer
reg1 = Count reg2 = Count
reg1 = reg1 + 1 reg2 = reg2 - 1
Count = reg1 Count = reg2
//reg1 ,reg2 CPU register
Concurrent Execution
Interleaving happens:
Time
Process Statement Value
T0 Producer executes reg1=Count reg1=5
T1 Producer executes reg1 = reg1 + 1 reg1=6
T2 Consumer executes reg2 = Count reg2=5
T3 Consumer executes reg2 = reg2 - 1 reg2=4
T4 Producer executes Count = reg1 Count=6
T5 Consumer executes Count = reg2 Count=4
Outcome depends on the Order in
which Access takes place
• Def: Several processes access and manipulate
same data concurrently
– then outcome depends on the order in which
access takes place – This is called race condition.
• Synchronization of Process
– ensures correct order of processes accessing
shared data
• Control access to shared resource
– one at a time to maintain data consistency
Critical Sections of a Program
a=a+1; a= a+1;
b=b+1; b=2*b;
b=b+1;
b=2*b; a=2*a;
a=2*a;
Critical Section Problem
• System of n processes {p0, p1, … pn-1} sharing
data or table or file entries.
• Def:-Each process has critical section segment
of code which may be changing common
variables, updating table, writing file
• When one process in critical section, no other
may be in its critical section
(If multiple processes in their respective critical
sections simultaneously then racing condition)
Critical Section
Critical Section Description
• Each process must ask permission to enter
critical section in entry section
• critical section – value shared data/files
/tables changed
• exit section –set values to let other processes
enter critical section
• remainder section
Solution to Critical Section Problem
• Solution must satisfy 3 requirements:
1. Mutual Exclusion: If process Pi is executing in its
critical section then no other process can execute
in their critical section
2. Progress : If no process is executing in its critical
section and there exist some processes that wish
to enter their critical section, then the selection
of the processes that will enter the critical
section next cannot be postponed indefinitely
Solution to Critical Section Problem
• Solution must satisfy 3 requirements(contd..):
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
Assumptions in
Solutions to Critical Sections
• Assume that each process executes at a
nonzero speed
• Machine language instructions – load ,store,
test are executed atomically(cannot be
interrupted)
(Two process executing concurrently result in
executing the critical section sequentially in
some unknown order)
Peterson’s Solution
(Software Solution)
• 2 Process Solution:
• The two processes share two variables:
– int turn;
– Boolean wants[2]
• turn :- indicates whose turn it is to enter the
critical section
• wants array:-indicate if a process is ready to
enter the critical section.( wants[i] = true
implies that process Pi is ready)
Peterson’s Algorithm
Process 1 Process2
EntrySection EntrySection
wants[1]=true wants[2]=true
turn=2 turn=1
while (wants[2]&& while (wants[1]&&
turn==2); turn==1);
Critical Section Critical Section
Exit Section Exit Section
wants[1]=false wants[2]=false
Multiple Process Solution
(Bakery Algorithm)
(Bakery token Number – the lower number gets turn)
Sharing data:
/*n==Maximum number of processes sharing critical
section*/
boolean choosing[n]//initialize all to false
int Tno[n] // initialize all to 0
Process identified by local variable int pi
Entry Section:
Choosing[pi]=true
Tno[pi]=max +1//max is the maximum token
yet allotted
Bakery Algorithm contd…
Entry Section Contd…:
for( indx=0;indx<n; indx++)// the maximum in
{ queue possible=n
while (choosing[indx]);
while(( (Tno[indx] !=0) && (Tno[indx]) < Tno[Pi]) ||
(Tno[indx]==Tno[Pi] && Pi < j);}
Critical Section:-
…………………
……………………
Exit Section Tno[Pi]=0
// if again critical section required, process will again take a number (higher token and //try to
get in
n=3
P0 P1 P2 P3
choosing[0]=f choosing[1]=t choosing[P3]=
alse rue true
Tno[0]=1 Tno[1]=2 4 Tno[P3]=3
false while(choosin
g[ind]=true;
Tno[ind]<>o Tno[1]&&Tno[
&& 0]<Tno[1]||
Tno[inx]< ind < 1
Tno[0]||ind<0
Synchronization Hardware
• Many systems provide hardware support for
critical section code
• Uniprocessors – could disable interrupts
Currently running code would execute
without preemption
• Modern machines provide special atomic
hardware instructions Atomic = non-
interruptable
– 1. test memory word and set value
– 2.swap contents of two memory words
1.TestAndSet Instruction
• Definition:
boolean TestAndSet (boolean *target)
{
boolean rv = *target;
*target = TRUE;
return rv:
}
Solution using TestAndSet
• Shared boolean variable lock, initialized to
FALSE
Solution:
do { Does not
while ( TestAndSet (&lock )) satisfy
; // do nothing bounded
// critical section waiting
condition of
lock = FALSE;
solution
// remainder section
} while (TRUE);
Process Synchronization 2
Boolean waiting[n];
Boolean lock;
//initialized to false
Bounded-waiting Mutual
Exclusion with TestandSet()
do { // critical section
j = (i + 1) % n;
waiting[i] = TRUE;
while ((j != i) && !waiting[j])
key = TRUE; j = (j + 1) % n;
while (waiting[i] && key) if (j == i)
lock = FALSE;
key = TestAndSet(&lock); else
waiting[i] = FALSE; waiting[j] = FALSE;
// remainder section
} while (TRUE);
Compare and Swap
do{
while (compare_and_swap(&lock,0,1)!=0);
//global variable lock initialized 0
//First process sets lock to 1, enter critical section
//because initial value of lock=0
//next compare_and_swap return 1
Critical section
.
.
Lock=0;} while (true);
compare_and_swap
int compare_and_swap(int *value, int
expted,int new_value)
{ int temp = *value;
if (* value == expted)
*value =new_value;
return temp;
}
Semaphore
Semaphore
• A special type of integer object provided by many
OS to use for
– setting sequence of 2 processes
– mutual exclusion of execution of critical sections of
several processes
i.e. Synchronizing several processes that are running in
the system sharing some resource(concurrency
management)
• Operations on semaphore ,s (are atomic-when one
process changes s ,no other process can change s)
Three Operations on Semaphore S Defined
1. Initialization
#include <semaphore.h>
sem_t s;
sem_init(&s, 0, 1);
// s initialized to 1 , 0 if s shared between threads in a single process)
2. Atomic operation of wait(S) ( also classically called P
from Dutch word for test)
wait(S){
while (S<=0) ; // do nothing
S--;
}
(In POSIX standard, these routines are sem_wait(&S))
Three Operations on Semaphore S
Defined
3. Atomic operation of signal(S) ( also classically
called V from Dutch word for increment)
signal(S){
S++;
}
(POSIX standard, these routines are sem_post(&S))
Semaphore: POSIX standard Definitions of
Wait And Post (as used in LINUX)
int sem_wait(sem_t *s) {
decrement the value of semaphore s by one
wait if value of semaphore s is positive
}
int sem_post(sem_t *s) {
increment the value of semaphore s by one
if there are one or more threads waiting, wake one
}
History of P() and V()
• sem_wait() was called P() by Dijkstra and
• sem_post() called V().
• P() comes from “prolaag”, a contraction of “probeer”
(Dutch for “try”) and “verlaag” (“decrease”);
• V() comes from the Dutch word “verhoog” which
means “increase” (thanks to Mart Oskamp for this
information). Sometimes, people call them down and
up. Use the Dutch versions to impress your friends,
or confuse them, or both.
Usage of Semaphore
• Use semaphore to synchronize 2 processes
running concurrently
Stm1 statements of process P1 needs to be done
before Stm2 statements of process P2
P1 and P2 share semaphore sync
Semaphore sync equal to 0;//initialize
P1 P2
Stm1 wait(sync)
signal(sync); Stm2
Usage of Semaphore S to implement mutex
(Mutual Exclusion)
n processes share a semaphore mutex, initialized to 1
Each process proci has following code before and after
critical section
do{
wait(mutex); //if mutex <=0 cannot proceed
critical section statements
signal(mutex); // mutex++
} while (1)
Three Operations on Semaphore S Defined
1. Initialization
#include <semaphore.h>
sem_t s;
sem_init(&s, 0, 1);
// s initialized to 1 , 0 if s shared between threads in a single process)
2. Atomic operation of wait(S) ( also classically called P for
wait from Dutch word for test)
wait(S){
while (S<=0); // do nothing
S--;
}
(POSIX standard, these routines are sem_wait(&S))
From Operating System : M.Milenkovic
Usage of Semaphore
• Busy waiting(or spin lock)
– Advantage : No context switching therefore no
time wasted in context switching
• Useful in multiprocessor system
Types of Semaphore
• 1.Classical Semaphore/Binary Semaphore:
• Operation wait (atomic operation ):
while (s== 0);//busy waiting ,CPU cycles wasted
s--
• signal Operation (atomic operation ):
S++
(Advantage : no context switching)
Value of semaphore never less than zero
Types of Semaphore contd..
• – integer value can range only between 0 and
1; can be simpler to implement in hardware
– With an integer counter C and binary semaphore
counting semaphore implementation
Types of Semaphore
Binary Semaphore contd..
(POSIX standard)
sem_t m;
sem_init(&m, 0, X);
// initialize semaphore to X; what should X be?
sem_wait(&m);
// critical section here
sem_post(&m);
Types of Semaphore contd..
• 2. Counting semaphore –
– integer value can range over an unrestricted
domain
(No busy waiting Implementation) :
– Processes put in semaphore queue if critical
section not available
Usage of Semaphore …
• In single CPU system: busy waiting wastes CPU cycles
that some other process can use productively.(Spin locks
useful only when locks expected to be held for short times)
• Signal(S)- Increment semaphore S by 1
if semaphore S<=0 transfer one process in semaphore
queue to ready queue by marking it runnable and
handing it to scheduler
Semaphore Implementation with
less Busy waiting
Implementation of wait: Implementation of signal:
wait(semaphore *S) { signal(semaphore *S) {
S--; S++;
if (S <= 0) {
if (S < 0) {
remove a process P from S-
add this process to S->FIFO or >FIFO or other list;
any other list; wakeup(P);//put in ready queue
block(P); }
}
} -tive value here is the
number of processes
waiting in queue
• Semaphore variable can take any integer
value called counting semaphore
• Semaphore variable that take values 0 and 1
only are called binary semaphore
– Classical semaphore cannot be negative (similar to
binary semaphore)
Semaphore declaration and operations done by
system call when programming in LINUX
environment
Semaphore with waiting queue
• May result in situation of Deadlock
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 – if the queue is FILO
Classical Problems of Synchronization
• Classical problems used to test newly-
proposed synchronization schemes
– 1) Bounded-Buffer Problem
– 2) Readers and Writers Problem
– 3) Dining-Philosophers Problem
Bounded-Buffer Problem
• n buffers, each can hold one item
• Semaphore mutex initialized to the value 1 –
provides mutual exclusion for access to buffer
pool
• Semaphore full initialized to the value 0 – keeps
count of full buffers
• Semaphore empty initialized to the value n-
keeps count of empty buffers
(Producer produces full buffer for consumer
Consumer produces empty buffer for producer)
Bounded-Buffer Problem contd…
• The structure of the producer
process
do { while (empty <= 0);
// produce an item in nextp empty--
wait (empty);
wait (mutex);
while (mutex<=0);
mutex - -
// add the item to the buffer
signal (mutex);
signal (full); mutex++
} while (TRUE); full++
Bounded-Buffer Problem contd…
• The structure of the consumer
process
do {
wait (full); while (full <= 0);
wait (mutex); full--
// remove an item from //buffer to
nextc
signal (mutex);
while (mutex<=0);
signal (empty);
mutex - -
// consume the item in //nextc
} while (TRUE);
mutex++
empty++
Readers-Writers Problem
• A data set(file or record) shared among a number of
concurrent processes
2 types of process:
1. Readers – only read the data set, perform no updates
Can access data simultaneously
2. Writers – write :- Need exclusive access to shared object
• Problem – allow multiple readers to read at the same time
Only one single writer can access the shared data at the
same time
– Several variations of how readers and writers are treated – all
involve priorities
2 Types of Readers-Writers Problem
• First reader writer problem
– No reader should wait for other readers to finish
because a writer is waiting (writers may starve)
• Second reader writer problem
– If a writer is waiting to access the object , no new
readers may start reading(readers may starve)
• Shared Data:- Data set (file or record)
• Semaphore mutex initialized to 1
• Semaphore wrt(writer) initialized to 1
• Integer readcount initialized to 0
First Reader-Writer Problem –solution 1
do { Structure of Reader Process
wait (mutex) ; mutex semaphore ensures
readcount ++ ; mutual exclusion when the
readcount is updated
if (readcount == 1)
wait (wrt) ; readcount variable– keeps
signal (mutex) track of how processes are
// reading is performed reading the object
wait (mutex) ;
Semaphore wrt is mutual
readcount - - ;
exclusion semaphore for writers.
if (readcount == 0)
signal (wrt) ; wrt used by first and last reader
signal (mutex) ; that enter or exit the critical
} while (TRUE); section . Readers in between do
not use wrt semaphore
Readers-Writers Problem (Cont.)
• The structure of a writer
process
do { while ( wrt <= 0);
wrt - -
wait (wrt) ;
// writing is performed
signal (wrt) ; wrt++
} while (TRUE);
The dining philosophers problem -- an example
problem used in concurrent algorithm design
to show synchronization issues and
techniques for resolving them.
It was originally formulated in 1965 by Edsger
Dijkstra , as a student exam exercise,
presented in terms of computers competing
for access to tape drive peripherals. Soon
after, Tony Hoare gave the problem its
present formulation
•Problem designed to illustrate the challenges of avoiding
deadlock,
This is a system state in which no progress is possible.
Instructions leading to Deadlock:
Each philosopher is instructed to behave as follows:
think until the left fork is available; when it is, pick it up;
think until the right fork is available; when it is, pick it up;
when both forks are held, eat for a fixed amount of time;
then, put the right fork down ; then, put the left fork down;
repeat from the beginning.
•solution fails because it allows the system
to reach a deadlock state, in which no progress is possible.
-state in which each philosopher has picked up the fork to
the left, and is waiting for the fork to the right to become
available.
- the philosophers will eternally wait for each other to release a
fork
Dining-Philosophers Problem
Philosophers spend their lives thinking and eating
• Don’t interact with their neighbors,
occasionally try to pick up forks (one at a time)
to eat from bowl
• Need both to eat, then release both when
done
Solution to Critical Section Problem
• Solution must satisfy 3 requirements:
1. Mutual Exclusion: If process Pi is executing in its
critical section then no other process can execute
in their critical section
2. Progress : If no process is executing in its critical
section and there exist some processes that wish
to enter their critical section, then the selection
of the processes that will enter the critical
section next cannot be postponed indefinitely
Solution to Critical Section Problem
• Solution must satisfy 3 requirements(contd..):
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
Resource starvation can occur if a particular philosopher is
unable to acquire both forks because of a timing problem.
Rules:
The philosophers put down a fork after waiting ten
minutes for the other fork to become available
Wait a further ten minutes before making their next
attempt.
•System always advance to a different state –Progress
•But suffers from the problem of livelock.
1. If all five philosophers appear in the dining room
at exactly the same time and each picks up the
left fork at the same time
2. the philosophers will wait ten minutes until they
all put their forks down
3. wait a further ten minutes before they all pick
them up again
Mutual exclusion When multiple programs need
exclusive access to shared resources. (
concurrent programming).
The difficulties exemplified by the dining philosophers
problem arise when multiple processes write sets of
same data (resources:-forks in Dining Philosophers’
Problem)
Systems such as operating system kernels use
thousands of locks and synchronizations that require
strict adherence to methods and protocols if such
problems as deadlock, starvation, or data corruption
are to be avoided
Resource hierarchy solution
proposed by Dijkstra
Assigns a partial order to the resources (the forks),
•Rules:-
• all resources(forks) will be requested in order,
• no two resources (forks) unrelated by order will ever be
used by a single process(philosopher) at the same time.
(i.e forks will be numbered 1 through 5) Each
process(philosopher) pick up the lower-numbered fork first,
and then the higher-numbered fork, from among the two
forks he plans to use.
• order in which each philosopher puts down the forks does
not matter. if four of the five philosophers simultaneously
pick up their lower-numbered fork, only the highest
numbered fork will remain on the table, so the fifth
philosopher will not be able to pick up any fork. And only
one philosopher will have access to that highest-numbered
fork, so he will be able to eat using two forks.
Resource hierarchy solution avoids deadlocks, it is
not always practical, especially when the list of
required resources is not completely known in
advance.
For example, if a unit of work holds resources 3
and 5 and then determines it needs resource 2,
it must release 5, then 3 before acquiring 2, and
then it must re-acquire 3 and 5 in that order.
Computer programs that access large numbers of
database records would not run efficiently if they
were required to release all higher-numbered
records before accessing a new record, making
the method impractical for that purpose.
Arbitrator solution
A philosopher can only pick up both forks or none
by introducing an arbitrator, e.g., a waiter. In order
to pick up the forks, a philosopher must ask
permission of the waiter. The waiter gives
permission to only one philosopher at a time to pick
up both his forks. Putting down a fork is always
allowed. The waiter can be implemented as a
mutex. In addition to introducing a new central
entity (the waiter), this approach can result in
reduced parallelism: if a philosopher is eating and
one of his neighbors is requesting the forks, all
other philosophers must wait until this request has
been fulfilled
Dining-Philosophers Problem
Semaphore Solution
• ith philosopher running in ith thread
(processes)
• Array of 5 semaphore forks (resources) to be
waited by ith philosopher when claiming two
consecutive forks
• All fork semaphores initialized to 1
Pseudo Code Dining-Philosophers
ProblemSemaphore Solution -
For ith Philosopher thread:-
Do{
wait( fork[i]);
wait(fork[i+1]%5);
.
eat
signal( fork[i]);
signal(fork[i+1]%5);
……think
}while (1);
//no two neighbours eat simultaneously
Pseudo Code Dining-Philosophers Problem
Semaphore Solution Fails
-Results in deadlock
• When all philosopher threads wait the first
fork simultaneously !!!
