Mutual Exclusion: n-process solution
Semaphores
• Synchronization tool proposed by Dijkstra, that does not
require busy waiting.
• Semaphore S – integer variable
• can only be accessed via two indivisible (atomic) operations
wait (S): [Also called P() – Proberen – “to test”]
while (S <= 0) do nop ;
S = S – 1;
signal (S): [Also called V() – Verhogen – “to increment”]
S = S + 1;
Critical Section of n Processes
• Shared data:
semaphore mutex = 1;
• Process Pi
do {
wait(mutex);
critical section
signal(mutex);
remainder section
} while (true);
Semaphore Implementation
• The semaphore definition above and all other mutual exclusion solutions given so far
require ‘busy waiting’ (looping continuously in entry code). Busy waiting wastes CPU
cycles so must be dealt with.
• To avoid busy waiting: When a process has to wait, it will be put in a blocked queue of
processes waiting for the same event.
• Define a semaphore as a structure,
struct Semaphore
{
int value;
int List[n];
};
Semaphore S;
• Assume two simple operations:
– block suspends the process that invokes it.
– wakeup(P) resumes the execution of a blocked process P.
Implementation
• Semaphore operations on variable S are now defined as,
wait(S):
[Link]--;
if ([Link] < 0) {
add this process to [Link];
block;
}
signal(S):
[Link]++;
if ([Link] <= 0) {
remove a process P from [Link];
wakeup(P);
}
abs(value) shows the number of blocked processes. value < 0
means that there is a process to wakeup.
Semaphore as a General Synchronization Tool
• Execute instruction B in Pj only after
instruction A executed in Pi
• Use semaphore flag initialized to 0
process Pi process Pj
M M
instruction A wait(flag);
signal(flag); instruction B
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);
M M
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.
Classical Problems of
Synchronization
• Bounded-Buffer Problem
• Readers and Writers Problem
• Dining-Philosophers Problem
Producer-Consumer with a Bounded
Buffer
• A classic problem
• A producer put things into a shared buffer
• A consumer takes them out
Problem Constraints
• The solution involves both scheduling and
mutual exclusion
• Constraints
– The consumer must wait if buffers are empty
(scheduling constraint)
– The producer must wait if buffers are full
(scheduling constraint)
– Only one thread can manipulate the buffer at a
time (mutual exclusion)
Bounded-Buffer Producer-Consumer Problem
Shared data
semaphore full = 0, empty = n, mutex = 1;
Producer process Consumer process
do { do {
… wait(full);
produce an item in nextp wait(mutex);
…
…
wait(empty);
wait(mutex); remove an item from buffer to nextc
… …
add nextp to buffer signal(mutex);
… signal(empty);
signal(mutex); …
signal(full); consume the item in nextc
…
} while (true); } while (true);
Readers-Writers Problem
• Models access to a database
– A reader is a thread that needs to look at the database but won’t
change it.
– A writer is a thread that modifies the database
• Example: making an airline reservation
– When you browse to look at flight schedules the web site is acting as a
reader on your behalf
– When you reserve a seat, the web site has to write into the database
to make the reservation
Readers-Writers Problem
• Many threads share an object in memory
– Some write to it, some only read it
– Only one writer can be active at a time
– Any number of readers can be active simultaneously
• Key insight: generalizes the critical section concept
• One issue we need to settle, to clarify problem statement.
– Suppose that a writer is active and a mixture of readers and writers
now shows up. Who should get in next?
– Or suppose that a writer is waiting and an endless of stream of readers
keeps showing up. Is it fair for them to become active?
• We’ll favor a kind of back-and-forth form of fairness:
– Once a reader is waiting, readers will get in next.
– If a writer is waiting, one writer will get in next.
Readers-Writers Problem
Shared data
semaphore mutex = 1, wrt = 1;
int readcount = 0;
Writer process Reader process
do{
do{ wait(mutex);
readcount++;
wait(wrt); if (readcount == 1)
… wait(wrt);
signal(mutex);
writing is performed
…
… reading is performed
signal(wrt); …
wait(mutex);
} while (true); readcount--;
if (readcount == 0)
signal(wrt);
signal(mutex);
} while(true);
Dining-Philosophers Problem
Five philosophers are sitting
around a table. Each
philosopher has a plate in front
him/her. Between each plate is
a chopstick.
A philosopher is either
“thinking” or “eating”. When a
philosopher gets hungry
he/she tries to get the two
chopsticks on his/her left and
right. Having obtained both
chopsticks the philosopher
can eat.
When finished eating, the
philosopher puts both
chopsticks down, and resumes
thinking
Dining-Philosophers
Shared data
Problem
semaphore chopstick[5]={1,1,1,1,1};
• Philosopher i:
do {
wait(chopstick[i]);
wait(chopstick[(i+1) % 5]);
…
eat
…
signal(chopstick[i]);
signal(chopstick[(i+1) % 5]);
…
think
…
} while (true);
Dining-Philosophers Problem
• Deadlock occurs if each philosopher
starts by picking his/her left chopstick!
• There are several methods that ensure
freedom from deadlocks:
– Allow at most four philosophers to be
sitting simultaneously at the table while
maintaining five chopsticks!
– Allow a philosopher to pick up his/her
chopsticks only if both chopsticks are
available.