algorithms

Process Synchronization Algorithms

altanaiLeave a comment

Facing numerous and possibly conflicting requests for resources(CPU time, memory space,file-storage space, I/0 devices etc ), an operating system must decide how to allocate them to specific tasks so that it can operate the computer system efficiently and
fairly. To avoid deadlocks and starvations, an OS used process synchronization algorithm and ensures that mutual exclusion is carried out for critical section problems .

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

  • Mutual Exclusion
  • Progress
  • Bounded Waiting

Peterson’s Algorithm in Process Synchronization

The producer consumer problem (or bounded buffer problem) which share a fixed size buffer queue.
// producer j is ready to produce an item
flag[j] = true;

// consumer (i) can consume an item
turn = i;

When a process wants to execute it’s critical section, it sets it’s flag to true and turn as the index of the other process, allowing it to run first and performing busy waiting until it has finished it’s critical section.

// if consumer is ready to consume an item and if its consumer’s turn
while (flag[i] == true && turn == i)
{ // then producer will wait }

Once after the current process enters and completes its own crticial section, it sets it’s own flag to false, indication it does not wish to execute anymore.
// producer will produce an item and put it into buffer (critical Section)

// Now, producer is out of critical section
flag[j] = false;

Similarly for consumer.

Dekker’s algorithm in Process Synchronization

allows two threads to share a single-use resource without conflict, using only shared memory for communication.

algorithm requires both an array of Boolean values and an integer variable:

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

Bakery Algorithm in Process Synchronization

critical section solution for N processes and preserves first come first server priority
A inceasing lexicographical order (ticket #, process id #) is assigned to incoming task. Tasks with smalles number is executed first. Firstly the ticket number is compared. If same then the process ID is compared next, i.e.-

```
repeat
choosing[i] := true;
number[i] := max(number[0], number[1], ..., number[n - 1])+1;
choosing[i] := false;

for j := 0 to n - 1
do begin
while choosing[j] do no-op;
while number[j] != 0
and (number[j], j) < (number[i], i) do no-op;
end;

critical section

number[i] := 0;

remainder section

until false;
```

If task i wants to execute critical section , set choosing to true then assign max ticket from correspodning and set choose to false after assignment .

Then find least ticket number/process id fr critical section and after its done ,resets the ticket value to zero.

Sleeping Barber problem in Process Synchronization

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.

The solution to this problem includes 3 semaphores.
– First is for the customer which counts the number of customers present in the waiting room
– Second mutex, barber 0 or 1 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.

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

Leave a comment