Solution to critical Section Problem

Peterson’s Solution
Peterson‟s Solution is a classical software based solution to the critical section problem.
In Peterson‟s solution, we have two shared variables:
 boolean flag[i] :Initialized to FALSE, initially no one is interested in entering the critical
section
 int turn : The process whose turn is to enter the critical section.

Peterson‟s Solution preserves all three conditions :

 Mutual Exclusion is assured as only one process can access the critical section at any
time.
 Progress is also assured, as a process outside the critical section does not block other
processes from entering the critical section.
 Bounded Waiting is preserved as every process gets a fair chance.

Disadvantages of Peterson‟s Solution

 It involves Busy waiting
 It is limited to 2 processes.
TestAndSet

TestAndSet is a hardware solution to the synchronization problem. In TestAndSet, we have a

shared lock variable which can take either of the two values, 0 or 1.
0 Unlock
1 Lock
Before entering into the critical section, a process inquires about the lock. If it is locked, it keeps
on waiting until it becomes free and if it is not locked, it takes the lock and executes the critical
section.
In TestAndSet, Mutual exclusion and progress are preserved but bounded waiting cannot be
preserved.

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;

Dekker’s Algorithm: Final and completed Solution – -Idea is to use favoured thread notion
to determine entry to the critical section. Favoured thread alternates between the thread
providing mutual exclusion and avoiding deadlock, indefinite postponement, or lockstep
synchronization.

Main()
{

// to denote which thread will enter next

int favouredthread = 1;

// flags to indicate if each thread is in

// queue to enter its critical section
boolean thread1wantstoenter = false;
boolean thread2wantstoenter = false;

startThreads();
}

Thread1()
{
do {

thread1wantstoenter = true;

// entry section
// wait until thread2 wants to enter
// its critical section
while (thread2wantstoenter == true) {

// if 2nd thread is more favored

if (favaouredthread == 2) {

// gives access to other thread

 thread1wantstoenter = false;

// wait until this thread is favored

while (favouredthread == 2)
;

thread1wantstoenter = true;
}
}

// critical section

// favor the 2nd thread

favouredthread = 2;

// exit section
// indicate thread1 has completed
// its critical section
thread1wantstoenter = false;

// remainder section

} while (completed == false)

}

Thread2()
{

do {

thread2wantstoenter = true;

// entry section
// wait until thread1 wants to enter
// its critical section
while (thread1wantstoenter == true) {

// if 1st thread is more favored

if (favaouredthread == 1) {

// gives access to other thread

thread2wantstoenter = false;

// wait until this thread is favored

while (favouredthread == 1)
 ;

thread2wantstoenter = true;
}
}

// critical section

// favour the 1st thread

favouredthread = 1;

// exit section
// indicate thread2 has completed
// its critical section
thread2wantstoenter = false;

// remainder section

} while (completed == false)

}

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.
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
}
 }
}

Classic Problems of Synchronization

Readers-Writers Problem

Problem parameters:
One set of data is shared among a number of processes
 Once a writer is ready, it performs its write. Only one writer may write at a time
 If a process is writing, no other process can read it
 If at least one reader is reading, no other process can write
 Readers may not write and only read

Solution when Reader has the Priority over Writer

Here priority means, no reader should wait if the share is currently opened for reading.
Three variables are used: mutex, wrt, readcnt to implement solution

1. semaphore mutex, wrt; // semaphore mutex is used to ensure mutual exclusion

when readcnt is updated i.e. when any reader enters or exit from the critical section and
semaphore wrt is used by both readers and writers
2. int readcnt; // readcnt tells the number of processes performing read in the critical
section, initially 0
Functions for semaphore :
– wait() : decrements the semaphore value.
– signal() : increments the semaphore value.
Writer process:

1. Writer requests the entry to critical section.

2. If allowed i.e. wait() gives a true value, it enters and performs the write. If not allowed, it
keeps on waiting.
3. It exits the critical section.

do {
// writer requests for critical section
 wait(wrt);

// performs the write

// leaves the critical section

signal(wrt);

} while(true);
Reader process:

1. Reader requests the entry to critical section.

2. If allowed:
 it increments the count of number of readers inside the critical section. If this reader is
the first reader entering, it locks the wrt semaphore to restrict the entry of writers if any
reader is inside.
 It then, signals mutex as any other reader is allowed to enter while others are already
reading.
 After performing reading, it exits the critical section. When exiting, it checks if no more
reader is inside, it signals the semaphore “wrt” as now, writer can enter the critical
section.
3. If not allowed, it keeps on waiting.

do {

// Reader wants to enter the critical section

wait(mutex);

// The number of readers has now increased by 1

readcnt++;

// there is atleast one reader in the critical section

// this ensure no writer can enter if there is even one reader
// thus we give preference to readers here
if (readcnt==1)
wait(wrt);

// other readers can enter while this current reader is inside

 // the critical section
signal(mutex);

// current reader performs reading here

wait(mutex); // a reader wants to leave

readcnt--;

// that is, no reader is left in the critical section,

if (readcnt == 0)
signal(wrt); // writers can enter

signal(mutex); // reader leaves

} while(true);
Thus, the semaphore „wrt„ is queued on both readers and writers in a manner such that
preference is given to readers if writers are also there. Thus, no reader is waiting simply
because a writer has requested to enter the critical section.

Dining Philospher Problem

The dining philosophers problem states that there are 5 philosophers sharing a circular table and
they eat and think alternatively. There is a bowl of rice for each of the philosophers and 5
chopsticks. A philosopher needs both their right and left chopstick to eat. A hungry philosopher
may only eat if there are both chopsticks available.Otherwise a philosopher puts down their
chopstick and begin thinking again.
The dining philosopher is a classic synchronization problem as it demonstrates a large class of
concurrency control problems.
Solution of Dining Philosophers Problem
A solution of the Dining Philosophers Problem is to use a semaphore to represent a chopstick. A
chopstick can be picked up by executing a wait operation on the semaphore and released by
executing a signal semaphore.
The structure of the chopstick is shown below −
semaphore chopstick [5];
Initially the elements of the chopstick are initialized to 1 as the chopsticks are on the table and
not picked up by a philosopher.
The structure of a random philosopher i is given as follows −
do {
wait( chopstick[i] );
 wait( chopstick[ (i+1) % 5] );
..
. EATING THE RICE
.
signal( chopstick[i] );
signal( chopstick[ (i+1) % 5] );
.
. THINKING
.
} while(1);
In the above structure, first wait operation is performed on chopstick[i] and chopstick[ (i+1) %
5]. This means that the philosopher i has picked up the chopsticks on his sides. Then the eating
function is performed.
After that, signal operation is performed on chopstick[i] and chopstick[ (i+1) % 5]. This means
that the philosopher i has eaten and put down the chopsticks on his sides. Then the philosopher
goes back to thinking.
Difficulty with the solution
The above solution makes sure that no two neighboring philosophers can eat at the same time.
But this solution can lead to a deadlock. This may happen if all the philosophers pick their left
chopstick simultaneously. Then none of them can eat and deadlock occurs.
Some of the ways to avoid deadlock are as follows −

 There should be at most four philosophers on the table.

 An even philosopher should pick the right chopstick and then the left chopstick while an odd
philosopher should pick the left chopstick and then the right chopstick.
 A philosopher should only be allowed to pick their chopstick if both are available at the same
time.