Classical Problems of Synchronization
In this tutorial we will discuss about various classic problem of synchronization.
Semaphore can be used in other synchronization problems besides Mutual Exclusion.
Below are some of the classical problem depicting flaws of process synchronaization in
systems where cooperating processes are present.
We will discuss the following three problems:
1. Bounded Buffer (Producer-Consumer) Problem
2. Dining Philosophers Problem
3. The Readers Writers Problem
1. Sleeping Barber Problem
Bounded Buffer Problem
● This problem is generalised 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.
Dining Philosophers Problem
● The dining philosopher's problem involves the allocation of limited resources to a
group of processes in a deadlock-free and starvation-free manner.
● There are five philosophers sitting around a table, in which there are five
chopsticks/forks kept beside them and a bowl of rice in the centre, When a
philosopher wants to eat, he uses two chopsticks - one from their left and one
from their right. When a philosopher wants to think, he keeps down both
chopsticks at their original place.
The Readers Writers Problem
● In this problem there are some processes(called readers) that only read the
shared data, and never change it, and there are other processes(called writers)
who may change the data in addition to reading, or instead of reading it.
● There are various type of readers-writers problem, most centred on relative
priorities of readers and writers.
Bounded Buffer Problem
Bounded buffer problem, which is also called producer consumer problem, is one of
the classic problems of synchronization. Let's start by understanding the problem here,
before moving on to the solution and program code.
What is the Problem Statement?
There is a buffer of n slots and each slot is capable of storing one unit of data. There
are two processes running, namely, producer and consumer, which are operating on
the buffer.
Bounded Buffer Problem
A producer tries to insert data into an empty slot of the buffer. A consumer tries to
remove data from a filled slot in the buffer. As you might have guessed by now, those
two processes won't produce the expected output if they are being executed
concurrently.
There needs to be a way to make the producer and consumer work in an independent
manner.
Here's a Solution
One solution of this problem is to use semaphores. The semaphores which will be used
here are:
● m, a binary semaphore which is used to acquire and release the lock.
● empty, a counting semaphore whose initial value is the number of slots in the
buffer, since, initially all slots are empty.
● full, a counting semaphore whose initial value is 0.
At any instant, the current value of empty represents the number of empty slots in the
buffer and full represents the number of occupied slots in the buffer.
The Producer Operation
The pseudocode of the producer function looks like this:
do
// wait until empty > 0 and then decrement 'empty'
wait(empty);
// acquire lock
wait(mutex);
/* perform the insert operation in a slot */
// release lock
signal(mutex);
// increment 'full'
signal(full);
while(TRUE)
● Looking at the above code for a producer, we can see that a producer first waits
until there is atleast one empty slot.
● Then it decrements the empty semaphore because, there will now be one less
empty slot, since the producer is going to insert data in one of those slots.
● Then, it acquires lock on the buffer, so that the consumer cannot access the
buffer until producer completes its operation.
● After performing the insert operation, the lock is released and the value of full is
incremented because the producer has just filled a slot in the buffer.
The Consumer Operation
The pseudocode for the consumer function looks like this:
do
// wait until full > 0 and then decrement 'full'
wait(full);
// acquire the lock
wait(mutex);
/* perform the remove operation in a slot */
// release the lock
signal(mutex);
// increment 'empty'
signal(empty);
while(TRUE);
● The consumer waits until there is atleast one full slot in the buffer.
● Then it decrements the full semaphore because the number of occupied slots will
be decreased by one, after the consumer completes its operation.
● After that, the consumer acquires lock on the buffer.
● Following that, the consumer completes the removal operation so that the data
from one of the full slots is removed.
● Then, the consumer releases the lock.
● Finally, the empty semaphore is incremented by 1, because the consumer has
just removed data from an occupied slot, thus making it empty.
Dining Philosophers Problem
The dining philosophers problem is another classic synchronization problem which is
used to evaluate situations where there is a need of allocating multiple resources to
multiple processes.
What is the Problem Statement?
Consider there are five philosophers sitting around a circular dining table. The dining
table has five chopsticks and a bowl of rice in the middle as shown in the below figure.
Dining Philosophers Problem
At any instant, a philosopher is either eating or thinking. When a philosopher wants to
eat, he uses two chopsticks - one from their left and one from their right. When a
philosopher wants to think, he keeps down both chopsticks at their original place.
Here's the Solution
From the problem statement, it is clear that a philosopher can think for an indefinite
amount of time. But when a philosopher starts eating, he has to stop at some point of
time. The philosopher is in an endless cycle of thinking and eating.
An array of five semaphores, stick[5], for each of the five chopsticks.
The code for each philosopher looks like:
while(TRUE)
wait(stick[i]);
/*
mod is used because if i=5, next
chopstick is 1 (dining table is circular)
*/
wait(stick[(i+1) % 5]);
/* eat */
signal(stick[i]);
signal(stick[(i+1) % 5]);
/* think */
When a philosopher wants to eat the rice, he will wait for the chopstick at his left and
picks up that chopstick. Then he waits for the right chopstick to be available, and then
picks it too. After eating, he puts both the chopsticks down.
But if all five philosophers are hungry simultaneously, and each of them pickup one
chopstick, then a deadlock situation occurs because they will be waiting for another
chopstick forever. The possible solutions for this are:
● A philosopher must be allowed to pick up the chopsticks only if both the left and
right chopsticks are available.
● Allow only four philosophers to sit at the table. That way, if all the four
philosophers pick up four chopsticks, there will be one chopstick left on the table.
So, one philosopher can start eating and eventually, two chopsticks will be
available. In this way, deadlocks can be avoided.
What is Readers Writer Problem?
Readers writer problem is another example of a classic synchronization problem. There
are many variants of this problem, one of which is examined below.
The Problem Statement
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.
The Solution
From the above problem statement, it is evident that readers have higher priority than
writer. If a writer wants to write to the resource, it must wait until there are no readers
currently accessing that resource.
Here, we use one mutex m and a semaphore w. An integer variable read_count is
used to maintain the number of readers currently accessing the resource. The variable
read_count is initialized to 0. A value of 1 is given initially to m and w.
Instead of having the process to acquire lock on the shared resource, we use the mutex
m to make the process to acquire and release lock whenever it is updating the
read_count variable.
The code for the writer process looks like this:
while(TRUE)
wait(w);
/* perform the write operation */
signal(w);
And, the code for the reader process looks like this:
while(TRUE)
//acquire lock
wait(m);
read_count++;
if(read_count == 1)
wait(w);
//release lock
signal(m);
/* perform the reading operation */
// acquire lock
wait(m);
read_count--;
if(read_count == 0)
signal(w);
// release lock
signal(m);
Here is the Code uncoded(explained)
● As seen above in the code for the writer, the writer just waits on the w semaphore
until it gets a chance to write to the resource.
● After performing the write operation, it increments w so that the next writer can
access the resource.
● On the other hand, in the code for the reader, the lock is acquired whenever the
read_count is updated by a process.
● When a reader wants to access the resource, first it increments the read_count
value, then accesses the resource and then decrements the read_count value.
● The semaphore w is used by the first reader which enters the critical section and
the last reader which exits the critical section.
● The reason for this is, when the first readers enters the critical section, the writer
is blocked from the resource. Only new readers can access the resource now.
● Similarly, when the last reader exits the critical section, it signals the writer using
the w semaphore because there are zero readers now and a writer can have the
chance to access the resource.
Sleeping Barber problem in Process Synchronization
Problem : The analogy is based upon a hypothetical barber shop with one barber. There
is a barber shop which has one barber, one barber chair, and n chairs for waiting for
customers if there are any to sit on the chair.
● If there is no customer, then the barber sleeps in his own chair.
● When a customer arrives, he has to wake up the barber.
● If there are many customers and the barber is cutting a customer’s hair, then
the remaining customers either wait if there are empty chairs in the waiting
room or they leave if no chairs are empty.
Solution : The solution to this problem includes three semaphores.First is for the
customer which counts the number of customers present in the waiting room
(customer in the barber chair is not included because he is not waiting). Second, the
barber 0 or 1 is used to tell whether the barber is idle or is working, And the third mutex
is used to provide the mutual exclusion which is required for the process to execute. In
the solution, the customer has the record of the number of customers waiting in the
waiting room if the number of customers is equal to the number of chairs in the waiting
room then the upcoming customer leaves the barbershop.
When the barber shows up in the morning, he executes the procedure barber, causing
him to block on the semaphore customers because it is initially 0. Then the barber goes
to sleep until the first customer comes up.
When a customer arrives, he executes customer procedure the customer acquires the
mutex for entering the critical region, if another customer enters thereafter, the second
one will not be able to anything until the first one has released the mutex. The customer
then checks the chairs in the waiting room if waiting customers are less then the
number of chairs then he sits otherwise he leaves and releases the mutex.
If the chair is available then customer sits in the waiting room and increments the
variable waiting value and also increases the customer’s semaphore this wakes up the
barber if he is sleeping.
At this point, customer and barber are both awake and the barber is ready to give that
person a haircut. When the haircut is over, the customer exits the procedure and if there
are no customers in waiting room barber sleeps.
Algorithm for Sleeping Barber problem:
Semaphore Customers = 0;
Semaphore Barber = 0;
Mutex Seats = 1;
int FreeSeats = N;
Barber {
while(true) {
/* waits for a customer (sleeps). */
down(Customers);
/* mutex to protect the number of available
seats.*/
down(Seats);
/* a chair gets free.*/
FreeSeats++;
/* bring customer for haircut.*/
up(Barber);
/* release the mutex on the chair.*/
up(Seats);
/* barber is cutting hair.*/
}
Customer {
while(true) {
/* protects seats so only 1 customer tries to sit
in a chair if that's the case.*/
down(Seats); //This line should not be here.
if(FreeSeats > 0) {
/* sitting down.*/
FreeSeats--;
/* notify the barber. */
up(Customers);
/* release the lock */
up(Seats);
/* wait in the waiting room if barber is
busy. */
down(Barber);
// customer is having hair cut
} else {
/* release the lock */
up(Seats);
// customer leaves
