Sleeping Barber problem in Process Synchronization

The Sleeping Barber problem is a classic problem in process synchronization that is used to
illustrate synchronization issues that can arise in a concurrent system. The problem is as
follows:

There is a barber shop with one barber and a number of chairs for waiting customers. Customers
arrive at random times and if there is an available chair, they take a seat and wait for the barber
to become available. If there are no chairs available, the customer leaves. When the barber
finishes with a customer, he checks if there are any waiting customers. If there are, he begins
cutting the hair of the next customer in the queue. If there are no customers waiting, he goes to
sleep.

The problem is to write a program that coordinates the actions of the customers and the barber
in a way that avoids synchronization problems, such as deadlock or starvation.

One solution to the Sleeping Barber problem is to use semaphores to coordinate access to the
waiting chairs and the barber chair. The solution involves the following steps:

Initialize two semaphores: one for the number of waiting chairs and one for the barber chair.
The waiting chairs semaphore is initialized to the number of chairs, and the barber chair
semaphore is initialized to zero.

Customers should acquire the waiting chairs semaphore before taking a seat in the waiting
room. If there are no available chairs, they should leave.
When the barber finishes cutting a customer’s hair, he releases the barber chair semaphore and
checks if there are any waiting customers. If there are, he acquires the barber chair semaphore
and begins cutting the hair of the next customer in the queue.

The barber should wait on the barber chair semaphore if there are no customers waiting.
The solution ensures that the barber never cuts the hair of more than one customer at a time,
and that customers wait if the barber is busy. It also ensures that the barber goes to sleep if there
are no customers waiting.

However, there are variations of the problem that can require more complex synchronization
mechanisms to avoid synchronization issues. For example, if multiple barbers are employed, a
more complex mechanism may be needed to ensure that they do not interfere with each other.
Prerequisite – Inter Process Communication 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
}
}
}
The Sleeping Barber Problem is a classical synchronization problem in which a barber shop
with one barber, a waiting room, and a number of customers is simulated. The problem involves
coordinating the access to the waiting room and the barber chair so that only one customer is
in the chair at a time and the barber is always working on a customer if there is one in the chair,
otherwise the barber is sleeping until a customer arrives.

Dekker’s algorithm in Process Synchronization

To obtain such a mutual exclusion, bounded waiting, and progress there have been several
algorithms implemented, one of which is Dekker’s Algorithm. To understand the algorithm
let’s understand the solution to the critical section problem first.

A process is generally represented as

do {
//entry section
critical section
//exit section
remainder section
} while (TRUE);

The solution to the critical section problem must ensure the following three conditions:

1. Mutual Exclusion

2. Progress
3. Bounded Waiting

One of the solutions for ensuring above all factors is Peterson’s solution.
Another one is Dekker’s Solution. Dekker’s algorithm was the first probably-correct solution
to the critical section problem. It allows two threads to share a single-use resource without
conflict, using only shared memory for communication. It avoids the strict alternation of a
naïve turn-taking algorithm, and was one of the first mutual exclusion algorithms to be
invented.
Although there are many versions of Dekker’s Solution, the final or 5th version is the one that
satisfies all of the above conditions and is the most efficient of them all.
Note – Dekker’s Solution, mentioned here, ensures mutual exclusion between two processes
only, it could be extended to more than two processes with the proper use of arrays and
variables.
Algorithm – It requires both an array of Boolean values and an integer variable:

var flag: array [0..1] of boolean;

turn: 0..1;
repeat
flag[i] := true;
while flag[j] do
if turn = j then
begin
flag[i] := false;
while turn = j do no-op;
flag[i] := true;
end;
critical section
turn := j;
flag[i] := false;
remainder section
until false;
Bakery Algorithm in Process Synchronization

The Bakery algorithm is one of the simplest known solutions to the mutual exclusion problem
for the general case of N process. Bakery Algorithm is a critical section solution
for N processes. The algorithm preserves the first come first serve property.

How does the Bakery Algorithm work?

In the Bakery Algorithm, each process is assigned a number (a ticket) in a lexicographical
order. Before entering the critical section, a process receives a ticket number, and the process
with the smallest ticket number enters the critical section. If two processes receive the same
ticket number, the process with the lower process ID is given priority.

How does the Bakery Algorithm ensure fairness?

The Bakery Algorithm ensures fairness by assigning a unique ticket number to each process
based on a lexicographical order. This ensures that processes are served in the order they
arrive, which guarantees that all processes will eventually enter the critical section.

• Before entering its critical section, the process receives a number. Holder of the smallest
number enters the critical section.

• If processes Pi and Pj receive the same number,

if i < j
Pi is served first;
else
Pj is served first.

• The numbering scheme always generates numbers in increasing order of enumeration;

i.e., 1, 2, 3, 3, 3, 3, 4, 5, …

Notation – lexicographical order (ticket #, process id #) – Firstly the ticket number is

compared. If same then the process ID is compared next,

Firstly the process sets its “choosing” variable to be TRUE indicating its intent to enter critical
section. Then it gets assigned the highest ticket number corresponding to other processes. Then
the “choosing” variable is set to FALSE indicating that it now has a new ticket number. This is
in-fact the most important and confusing part of the algorithm. It is actually a small critical
section in itself ! The very purpose of the first three lines is that if a process is modifying its
TICKET value then at that time some other process should not be allowed to check its old ticket
value which is now obsolete. This is why inside the for loop before checking ticket value we
first make sure that all other processes have the “choosing” variable as FALSE. After that we
proceed to check the ticket values of processes where process with least ticket number/process
id gets inside the critical section. The exit section just resets the ticket value to zero.

Advantages of Bakery Algorithm:

• Fairness: The Bakery Algorithm provides fairness, as it ensures that all processes get
a fair chance to access the critical section, and no process will be left waiting
indefinitely.

• Easy to Implement: The algorithm is easy to understand and implement, as it uses

simple concepts such as turn numbers and flags to ensure mutual exclusion.

• No Deadlock: The Bakery Algorithm ensures that there is no deadlock situation in the
system.

• No starvation: The algorithm also ensures that there is no starvation of any process, as
every process gets a fair chance to enter the critical section.

Disadvantages Bakery Algorithm:

• Not Scalable: The Bakery Algorithm is not scalable, as the overhead of the algorithm
increases with the number of processes in the system.
• High Time Complexity: The algorithm has a high time complexity, which increases as
the number of processes in the system increases. This can result in performance issues
in systems with a large number of processes.

• Busy Waiting: The algorithm requires busy waiting, which can lead to wastage of CPU
cycles and increased power consumption.

• Memory Overhead: The algorithm requires extra memory to store the turn number
and flag values, which can lead to increased memory overhead in systems with a large
number of processes.