Section 4

Semaphores

1
CSC3021 Concurrent Programming: §4 Semaphores
 Reading

 This section is based on

Ben-Ari, Principles of Concurrent and Distributed Programming
 Before the lecture, read:
 Chapter 6, section 6.1 – 6.9, 6.14

 Exercises and explanations:

 The Little Book of Semaphores (available on Canvas)

2
CSC3021 Concurrent Programming: §4 Semaphores
 Semaphores

A railway semaphore is a signal flag that indicates whether or

not the track ahead is clear or occupied by another train. As
the train proceeds, semaphores are set and cleared. They are
a mechanism which ensures mutual exclusive occupancy of
critical section of track.

Previously we considered algorithms which run on a bare

machine, i.e. they use only ordinary sequential programming
constructs. Here we introduce the notion of a semaphore
(first described by Dijkstra in 1968) as a programming
primitive on a higher level than machine instructions.

In concurrent programs semaphores provide a basic signalling

mechanism to implement mutual exclusion and condition
synchronization.

3
CSC3021 Concurrent Programming: §4 Semaphores
 4.1: Definition of a Semaphore

A semaphore is an integer-valued variable which can take only

non-negative values. Exactly two operations are defined on a
semaphore S:

down(S)
if S > 0 then
S=S-1
else
suspend the action of the process making the call. The
process is said to be suspended on S.
up(S)
if there are processes that have been suspended on S
wake one of them.
else
S=S+1

4
CSC3021 Concurrent Programming: §4 Semaphores
 Definition of a Semaphore

A semaphore has the following properties:

 down(S) and up(S) are atomic instructions. In particular, no
instructions can be interleaved between the test that S > 0
and the decrement of S or the suspension of the calling
process.
 A semaphore must be given a non-negative initial value.
 The up(S) operation must awaken one of the suspended
processes. The definition does not specify which process must
be awakened.

A general semaphore is a semaphore which can take any

non-negative value.
A binary semaphore is a semaphore which can take only the
values 0 and 1. In this case the definition of up(S) may be
replaced by if … else S = 1.
5
CSC3021 Concurrent Programming: §4 Semaphores
 Definition of a Semaphore

Show that a semaphore S satisfies the following two

invariants,

S>=0 (4.1)
S = S0+ #Up(S) - #Down(S) (4.2)

where,
S0 is the initial value of the semaphore,
#Up(S) is the number of Up operations executed on S,
#Down(S) is the number of completed Down operations
executed on S.

6
CSC3021 Concurrent Programming: §4 Semaphores
 4.2: Mutual Exclusion using a Semaphore

Semaphore S = new Semaphore(1);

Process P1 Process P2
while (true) { while (true) {
nonCriticalSection1; nonCriticalSection2;
down(S); down(S);
criticalSection1; criticalSection2;
up(S); up(S);
} }
end P1; end P2;

This algorithm is similar to the second attempt (see earlier) except

that the atomic implementation of the semaphore instruction
prevents interleaving between the test of S and the assignment to
S.
It differs from the test and set instruction in that a process
suspended on a semaphore no longer executes instructions checking
variables in a busy-wait loop. 7
CSC3021 Concurrent Programming: §4 Semaphores
 Mutual Exclusion using a Semaphore

The above algorithm generalises to N processes, N > 1. In

addition it satisfies all the desirable properties described
earlier in chapter 2.

Mutual exclusion is satisfied

Proof: Let #CS be the number of processes in their critical sections.
We will prove that
#CS + S = 1 (4.3)
is invariant. Then from invariant (4.1) #CS <= 1, which proves the
mutual exclusion property.

Proof that (4.3) is invariant.

1. #CS = #Down(S) - #Up(S) (show that this is an invariant)
2. S = 1 + #Up(S) - #Down(S) (4.2)
3. S = 1 - #CS

8
CSC3021 Concurrent Programming: §4 Semaphores
 Mutual Exclusion using a Semaphore

The solution cannot deadlock

Proof: For the program to deadlock both processes must be
suspended on Down(S). Then S=0 and #CS=0. This contradicts
the invariant (4.3) #CS + S =1, which is impossible.

There is no individual starvation (For N=2)

Proof: If P1 is suspended, S=0. By the invariant (4.3) P2 is in
the critical section. When P2 exits the critical section it will
execute up(S) which will wake some process suspended on S. P1
is the only process suspended on S.

There is no starvation in the absence of contention (For N=2)

Proof: In absence of contention, S=1 and no single process will
be delayed.
9
CSC3021 Concurrent Programming: §4 Semaphores
 4.3 Other Semaphore Definitions

Blocked-set
There semaphore
are many : of semaphore in the literature. It is
definitions
down(S) to be able to distinguish between them because the
important
if S > 0 then
correctness of a program will depend on the definition being used.
S=S-1
else
suspend the action of the process making the call.
up(S)
if there are processes that have been suspended on S
wake one of them.
else
S=S+1

A signaling process awakens one (unspecified) of the suspended

processes.
10
CSC3021 Concurrent Programming: §4 Semaphores
 Other Semaphore Definitions

Blocked-queue
There are many semaphore
definitions :of semaphore in the literature. It is
down(S) to be able to distinguish between them because the
important
if S > 0 then
correctness of a program will depend on the definition being
used. S=S-1
else
suspend the action of the process making the call and
append to a FIFO queue.
up(S)
if there are processes that have been suspended on S
wake the process at the head of the queue.
else
S = S + 1.

The suspended processes are kept in a FIFO queue and

awakened in the same order they were suspended.
11
CSC3021 Concurrent Programming: §4 Semaphores
 Other Semaphore Definitions

For a blocked-queue semaphore, starvation is impossible.

Suppose P1 is blocked on S. Then there are at most N – 1

processes ahead of P1 on the queue for S. Thus P1 will enter its
CS after at most N – 1 more executions of up (S).

For a blocked-set semaphore, starvation is possible for N > 2.

For N=2 we showed that starvation is impossible. For N > 2 it is

possible to construct an execution sequence where there will
always be at least two processes blocked on S. Since up (S) is
only required to wake one arbitrary process, it can conspire to
ignore one process, causing starvation. The construction is left
as an exercise.
12
CSC3021 Concurrent Programming: §4 Semaphores
 Exercise

Bill and Ben work in a cafe that specialises in a soup and

sandwich combination.

Bill makes two rounds of sandwiches while, at the same time,

Ben makes two bowls of soup. When the sandwiches and soup
are ready Bill and Ben each, at the same time, serve a soup and
sandwich combination to a customer. These actions are
repeated throughout the day.
[Note: Bill cannot serve until Ben has made the soup and Ben
cannot serve until Bill has made the sandwiches.]

15
CSC3021 Concurrent Programming: §4 Semaphores
 Exercise

Let Bill and Ben be represented by two processes with the

following structure:
Variable declarations

process Bill { process Ben {

while (true) { while (true) {
// Bill makes sandwiches // // Ben makes soup //
SYNCH 1; SYNCH 2;
// Bill delivers // // Ben delivers //
} }
} }

Provide variable declarations (including any initialization) and

code for SYNCH 1 and SYNCH 2 using semaphores so that
the above algorithm behaves correctly.
16
CSC3021 Concurrent Programming: §4 Semaphores
 Exercise

Solution

Semaphore first = 0;
Semaphore second = 0;

process Bill { process Ben {

while (true) { while (true) {
// Bill makes sandwiches // // Ben makes soup //
down(first); up(first);
up(second); down(second);
// Bill delivers // // Ben delivers //
} }
} }

17
CSC3021 Concurrent Programming: §4 Semaphores
 Exercise

OR …

Semaphore first = 0;
Semaphore second = 0;

process Bill { process Ben {

while (true) { while (true) {
// Bill makes sandwiches // // Ben makes soup //
down(second);
up(second); up(first);
down(first); // Ben delivers //
// Bill delivers // }
} }
}

18
CSC3021 Concurrent Programming: §4 Semaphores
 Exercise

Semaphore first = 0;
Semaphore second = 0;

process Bill { process Ben {

while (true) { while (true) {
// Bill makes sandwiches // // Ben makes soup //
up(first);
up(second); down(second);
down(first); // Ben delivers //
// Bill delivers // }
} }
}

19
CSC3021 Concurrent Programming: §4 Semaphores
 4.4 Producer – Consumer Problem

The mutual exclusion problem is an abstraction of

synchronization problems common in computer systems. Here
we consider an abstraction of communication problems called
the producer-consumer problem.

Producer: By executing an internal operation, produce, this

process creates a data element which must be sent to the
consumers.
Consumer: Upon receipt of a data element, this process performs
some computation in an internal operation consume.

For example this models an application producing a listing that

must be consumed by a printer.

20
CSC3021 Concurrent Programming: §4 Semaphores
 Producer – Consumer Problem

Whenever a data item is sent from one process to another an

elementary solution is synchronous communication : when one
process is ready to send and the other ready to receive the
data is sent.

If more flexibility is required a buffer is used to allow

asynchronous communication. The sending process appends data
elements to the tail of the queue, the receiving process removes
an element from the head of the queue.

A buffer is a
queue of data
elements
head tail

21
CSC3021 Concurrent Programming: §4 Semaphores
 Producer – Consumer Problem: infinite buffer

We begin by assuming an infinite buffer.

integer [] buffer = new integer [infinite];

integer head =0, tail = 0;

process producer process consumer

integer i; integer i;
while (true) { while (true) {
i=produce(); <wait until (tail > head);>
buffer[tail]=i; i=buffer[head];
tail=tail+1; head=head+1;
} consume(i);
end producer; }
end consumer;

Mutual exclusion is not an issue. Why ?

22
CSC3021 Concurrent Programming: §4 Semaphores
 Producer – Consumer Problem: infinite buffer

... The buffer has the following

invariants:
#E = 0+tail-head
head tail
#E >= 0

This suggests that the problem can be solved using a semaphore,

‘elements’, that counts the number of data elements in the
buffer.

23
CSC3021 Concurrent Programming: §4 Semaphores
 Producer – Consumer Problem: infinite buffer

integer [] buffer = new integer [infinite];

integer head =0, tail = 0;
Semaphore elements = new Semaphore(0);

process producer process consumer

integer i; integer i;
while (true) { while (true) {
i=produce(); down(elements);
buffer[tail]=i; i=buffer[head];
tail=tail+1; head=head+1;
up(elements); consume(i);
} }
end producer; end consumer;

The consumer executes down(elements) which suspends if the

number of elements in the buffer is 0. At the end of each loop
iteration the producer executes up(elements).
24
CSC3021 Concurrent Programming: §4 Semaphores
 Producer – Consumer Problem: circular buffer

We now extend the previous solution to the more practical

situation of a bounded-buffer. In particular, we consider a
circular buffer.
head In this example semaphores serve
as resource counters. One counts
the number of empty buffer slots
and the other counts the number
of occupied slots.
tail The synchronization problems are
to:

 suspend the producer when the buffer is full;

 to suspend the consumer when the buffer is empty;
 to make sure that only one process at a time manipulates a
buffer slot (this is left as an exercise).
25
CSC3021 Concurrent Programming: §4 Semaphores
 Producer – Consumer Problem: circular buffer
integer [] buffer = new integer [N];
integer head =0, tail = 0;
Semaphore elements = new Semaphore(0);
Semaphore spaces = new Semaphore(N);
process producer process consumer
integer i; integer i;
while (true) { while (true) {
down(spaces); down(elements);
i=produce(); i=buffer[head];
buffer[tail]=i; head=(head+1)% N;
tail=(tail+1)% N; consume(i);
up(elements); up(spaces);
} }
end producer; end consumer;

The producer now executes down(spaces) which suspends if the

buffer is full. At the end of each loop iteration the consumer
executes up(spaces). 26
CSC3021 Concurrent Programming: §4 Semaphores
 4:5 The Dining Philosophers

Five philosophers sit around a circular

table. Each philosopher spends his life
alternately thinking and eating. In the 2
2
1
centre of the table is a large bowl of
spaghetti. A philosopher needs two forks
1
to eat a helping of spaghetti. 3

One fork is placed between each

pair of philosophers and they 3 0
agree that each will only use the 4 0
fork to his immediate right and
left. 4

27
CSC3021 Concurrent Programming: §4 Semaphores
 The Dining Philosophers

The synchronization problem is to coordinate the use of the

forks so that:
 only one philosopher at a time uses a fork;
 there is no deadlock (each philosopher holding a fork and
refusing to relinquish it);
 no philosopher starves (as a result of neighbours
collaborating);

Because forks are a shared resource we will focus on acquiring

and releasing them. Each fork is like a critical section: it can
be held by at most one philosopher at a time.

28
CSC3021 Concurrent Programming: §4 Semaphores
 The Dining Philosophers – First Attempt

Semaphore[] fork = {1,1,1,1,1};

process philosopher[i=0..4]
while (true) {
down(fork[i]);
down(fork[(i+1)%5]);
eat;
up(fork[i]);
up(fork[(i+1)%5]);
think;
}
end philosopher;

Is this solution correct?

29
CSC3021 Concurrent Programming: §4 Semaphores
 The Dining Philosophers

Semaphore[] fork = {1,1,1,1,1};

process philosopher[i=0..3] process philosopher[4]

while (true) { while (true) {
down(fork[i]); down(fork[0]);
down(fork[i+1]); down(fork[4]);
eat; eat;
up(fork[i]); up(fork[0]);
up(fork[i+1]); up(fork[4]);
think; think;
} }
end philosopher; end philosopher;

Why does philosopher[4] have to be different from the rest ?

30
CSC3021 Concurrent Programming: §4 Semaphores
 4:5 The Dining Philosophers - Exercise

 In real life, a fork may be held by only one philosopher at

a time.
 Is this true for our solutions?
 Construct a proof using the semaphore invariant (4.2).

 Solution:
 Let #Pi be the number of philosophers holding fork i.
 Then: #Pi = #Down(fork[i]) - #Up(fork[i])
 By the semaphore invariant (4.2):
 fork[i] = 1 + #Up(fork[i]) - #Down(fork[i])
 fork[i] = 1 - #Pi
 The value of a semaphore is always non-negative (4.1), so
 #Pi <= 1
31
CSC3021 Concurrent Programming: §4 Semaphores
 Deadlock

32
CSC3021 Concurrent Programming: §4 Semaphores
 Deadlock can arise if four conditions hold
simultaneously

 Serially reusable resources:

the processes involved share resources which they use under
mutual exclusion.
Incremental acquisition (hold and wait):
processes hold on to resources already allocated to them
while waiting to acquire additional resources.
No pre-emption:
once acquired by a process, resources cannot be pre-empted
(forcibly withdrawn) but are only released voluntarily.
Wait-for cycle (circular wait):
a circular chain (or cycle) of processes exists such that each
process holds a resource which its successor in the cycle is
waiting to acquire.

33
CSC3021 Concurrent Programming: §4 Semaphores
 Wait-for cycle for the dining philosophers (1st attempt)

Has 0 awaits 1

0
Has 4 awaits 0

4
1 Has 1 awaits 2

3 2
Has 2 awaits 3
Has 3 awaits 4
34
CSC3021 Concurrent Programming: §4 Semaphores
 Breaking the wait-for cycle (correct version)

Has 0 awaits 1

0
Awaits 3

4
1 Has 1 awaits 2

3 2
Has 2 awaits 3
Has 3, can grab 4
35
CSC3021 Concurrent Programming: §4 Semaphores
 Deadlock Prevention

 Avoid mutual exclusion: have unlimited resources or unlimited access

 Do not hold and wait
 Must guarantee that whenever a process requests a resource, it
does not hold any other resources.
 Require process to request all its resources before it begins
execution
 Low resource utilization; starvation possible.
 Allow preemption
 If a process requests another resource that cannot be immediately
allocated to it, then all resources currently being held are released
 Preempted resources are added to the list of resources process
needs
 Process will be restarted only when it can regain all its resources
 Prevent circular wait
 Impose a total ordering of all resource types
 Require that each process requests resources in an increasing order
36
CSC3021 Concurrent Programming: §4 Semaphores
 4.6: The Readers and Writers Problem

In the readers and writers problem, readers may access a

database simultaneously as long as no writer writes, but only
one writer at a time may write, provided there are no active
readers.

reader

writer
reader database

reader

37
CSC3021 Concurrent Programming: §4 Semaphores
 The Readers and Writers Problem

Semaphore rw = 1;

process Reader[i=1..M] process Writer[i=1..N]

while (true) { while (true) {
down(rw); down(rw);
read_the_database; write_the_database;
up(rw); up(rw);
} }
end Reader; end Writer;

An over constrained solution.

38
CSC3021 Concurrent Programming: §4 Semaphores
 The Readers and Writers Problem

int nr =0;
Semaphore rw =1;
process Reader[i=1..M] Semaphore mutexr = 1;
while (true) {
down(mutexr); process Writer[i=1..N]
nr=nr+1; while (true) {
if (nr==1) down(rw); down(rw);
up(mutexr); write_the_database;
read_the_database; up(rw);
down(mutexr) }
nr=nr-1; end Writer;
if (nr==0) up(rw);
up(mutexr);
}
end Reader; Under what circumstances
is this solution unfair ?

39
CSC3021 Concurrent Programming: §4 Semaphores
 4.7: The Sleeping Barber

Customers who need a haircut enter the waiting room. If the

room is full, the customer comes back later. If the barber is
busy but there is a vacant chair the customer takes a seat. If
the waiting room is empty and the barber is daydreaming the
customer sits in the barber chair and wakes the barber.
When the barber finishes cutting a customer’s hair, the
barber fetches another customer from the waiting room. If
the waiting room is empty the barber daydreams.

40
CSC3021 Concurrent Programming: §4 Semaphores
 The Sleeping Barber

Semaphore mutex=1;
Semaphore customers=0, cutting=0, barber=0;
int waiting=0, numChairs= ..;

process Customer[i=1..M]
process SleepingBarber
while (true) {
while (true) {
down(mutex);
down(customers);
if (waiting<numChairs){
down(mutex);
waiting++;
waiting--;
up(customers);
up(barber);
up(mutex);
up(mutex);
down(barber);
down(cutting);
up(cutting);
}
}
end SleepingBarber;
else up(mutex);
}
end Customer;
41
CSC3021 Concurrent Programming: §4 Semaphores
 The Sleeping Barber

This example illustrates the use of semaphores for

both mutual exclusion and condition synchronization.
The customers and barber use semaphores to control
each other’s flow through the barber shop. This
interaction is an example of a client-server
relationship. The customer and barber rendezvous to
interact: each waits at a certain point for the other
to arrive.

42
CSC3021 Concurrent Programming: §4 Semaphores