Operating Systems

Classical Problems
of Concurrency

Shahzad Akbar Lecturer BZU Multan

2
 Classical Problems of Concurrency
• There are many of them –
let’s briefly see three
famous problems:
1. P/C Bounded-Buffer
2. Readers and Writers
3. Dining-Philosophers

3
 Reminder: P/C problem with race condition

4
 P/C Bounded-Buffer Problem
• We need 3 semaphores:
1. A semaphore mutex (initialized to 1) to
have mutual exclusion on buffer access.
2. A semaphore full (initialized to 0) to
synchronize producer and consumer on
the number of consumable items.
3. A semaphore empty (initialized to n) to
synchronize producer and consumer on
the number of empty spaces.
5
 Bounded-Buffer – Semaphores
• Shared data

semaphore full, empty, mutex;

Initially:

full = 0, empty = n, mutex = 1

6
 Bounded-Buffer – Producer Process
do {
…
produce an item in nextp
…
wait(empty);
wait(mutex);
…
add nextp to buffer
…
signal(mutex);
signal(full);
} while (TRUE);

7
 Bounded-Buffer – Consumer Process
do {
wait(full)
wait(mutex);
…
remove an item from buffer to nextc
…
signal(mutex);
signal(empty);
…
consume the item in nextc
…
} while (TRUE);

8
 Notes on P/C Bounded-Buffer Solution
• Remarks (from consumer point of view):
– Putting signal(empty) inside the CS of the
consumer (instead of outside) has no effect since
the producer must always wait for both semaphores
before proceeding.
– The consumer must perform wait(full) before
wait(mutex), otherwise deadlock occurs if
consumer enters CS while the buffer is empty.
• Conclusion: using semaphores is a
difficult art ... 
9
 Full P/C Bounded-Buffer Solution

10
 Readers-Writers Problem
• A data set/repository is shared among a number
of concurrent processes:
– Readers – only read the data set; they do not
perform any updates.
– Writers – can both read and write.
• Problem – allow multiple readers to read at the
same time. Only one single writer can access
the shared data at the same time.

11
 Readers-Writers Dynamics
• Any number of reader activities and writer
activities are running.
• At any time, a reader activity may wish to read
data.
• At any time, a writer activity may want to
modify the data.
• Any number of readers may access the data
simultaneously.
• During the time a writer is writing, no other
reader or writer may access the shared data.
12
 Readers-Writers with active readers

13
 Readers-Writers with an active writer

14
 ?Should readers wait for waiting writer

15
 Readers-Writers problem
• There are various versions with different
readers and writers preferences:
1. The first readers-writers problem, requires that no
reader will be kept waiting unless a writer has
obtained access to the shared data.
2. The second readers-writers problem, requires that
once a writer is ready, no new readers may start
reading.
3. In a solution to the first case writers may starve;
In a solution to the second case readers may starve.

16
 First Readers-Writers Solution (1)
• readcount (initialized to 0) counter keeps
track of how many processes are
currently reading.
• mutex semaphore (initialized to 1) provides
mutual exclusion for updating readcount.
• wrt semaphore (initialized to 1) provides mutual
exclusion for the writers; it is also used by the
first or last reader that enters or exits the CS.

17
 First Readers-Writers Solution (2)

• Shared data

semaphore mutex, wrt;

18
 First Readers-Writers – Writer Process

do {
wait(wrt);
…
writing is performed
…
signal(wrt);
} while(TRUE);

19
 First Readers-Writers – Reader Process
do {
wait(mutex);
readcount++;
if (readcount == 1)
wait(wrt);
signal(mutex);
…
reading is performed
…
wait(mutex);
readcount--;
if (readcount == 0)
signal(wrt);
signal(mutex);
} while(TRUE);
20
 Dining Philosophers Problem (1)
• Five philosophers are seated
around a circular table.
• There is a shared bowl of rice.
• In front of each one is a plate.
• Between each pair of people
there is a chopstick, so there
are five chopsticks.
• It takes two chopsticks to
take/eat rice, so while n is
eating neither n+1 nor n-1
can be eating.
21
 Dining Philosophers Problem (2)
• Each one thinks for a while, gets the
chopsticks/forks needed, eats, and puts the
chopsticks/forks down again, in an endless
cycle.
• Illustrates the difficulty of allocating resources
among process without deadlock and
starvation.

22
 Dining Philosophers Problem (3)
• The challenge is to grant requests for
chopsticks while avoiding deadlock and
starvation.
• Deadlock can occur if everyone tries to get
their chopsticks at once. Each gets a left
chopstick, and is stuck, because each right
chopstick is someone else’s left chopstick.

23
 Dining Philosophers Solution (1)
• Each philosopher
is a process. Process Pi:
repeat
• One semaphore think;
per fork: wait(fork[i]);
– fork: array[0..4] wait(fork[i+1 mod 5]);
eat;
of semaphores signal(fork[i+1 mod 5]);
– Initialization: signal(fork[i]);
fork[i].count := 1 forever
for i := 0..4
Note: deadlock if each philosopher starts by picking up
his left fork!
24
 Dining Philosophers Solution (2)
Possible solutions to avoid deadlock:
• Allow at most four philosophers to be sitting at
the table at same time.
• Pick up both forks at same time.
• Odd numbered philosopher picks up
left fork first, even one picks up right fork.

25
 Dining Philosophers Solution (4)
• A solution: admit only 4
philosophers at a time Process Pi:
that try to eat. repeat
• Then 1 philosopher can think;
always eat when the other wait(T);
3 are holding 1 fork. wait(fork[i]);
• Hence, we can use another wait(fork[i+1 mod 5]);
eat;
semaphore T that would
signal(fork[i+1 mod 5]);
limit at 4 the number of signal(fork[i]);
philosophers “sitting at signal(T);
the table”. forever
• Initialize: T.count := 4

26
 Dining Philosophers Solution (5)

...

27
 Dining Philosophers Problem (6)

28