Saturday, 26 May 2018

Solution of critical section problem in Operating System

Solution of critical section problem in Operating System

Two Process Solution:

  Two process solution for P0 and P1.

Algorithm 1:

 


Algorithm 1 satisfy the mutual exclusion condition because only one process can be execute in critical section but it can not satisfy the progress condition.

Algorithm 2:


Algorithm 1 can not retain the status of the process that are currently executing in critical section.

share variable: flag[0 or 1]
initially flag[0]=true;

for P0,
do 
{
  flag[0]=true; //process P0 is ready to enter in CS
while ( flag[1] != true; // check the status P1 process

C.S {P0}
flag [0]=false;
R.S
}



for P1,
do
{

flag[1]=true;
while (flag[0]!=true)
C.S {P1}
flag[1]=false
R.S
}

  

Algorithm 2 satisfy the mutual exclusion condition because only one process execute in the critical section but it can not satisfy the progress condition.



Algorithm 3:

  In Algorithm 3 we combined (Peterson's algorithm) the approach of both algorithm 1 and algorithm 2.

Shared Variable:


flag[0 or 1]=true or false
turn= 0 or 1;

initially-
                 flag[0]=flag[1]=false;
                turn=0 or1;




for P0

do
{
flag[0]true;
turn=0;      //P0 ready to enter in C.S
while(flag [1] =true && turn=1)
do not operation;
< C.S > P0
flag[0]=false;
< R.S >
}while(1);




for P1
do
{
flag[1]=true
turn=1; //P1 ready to enter in C.S
while (flag[0]=true  &&  turn=0)
turn=1;
while( flag[0]= true  &&  turn=0)

do not operation;
< C.S > P1 // P1 begin execution in CS
flag [1] = false
<R.S>
}while(1);



Problem : algorithm 3 satisfy all the three condition of C.S.
Solution:  that is mutual exclusion, progress & bounded waiting.


Mutual Exclusion:


  since at a time only flag [0]=true and turn=0 that is P0 is in critical section.

Progress: suppose both processes P0 and P1 want to enter in critical section.
flag[0]=true;
flag[1]=true;
then if turn=0;
then P0 execute in C.S
else if turn=1
then P1 execute in C.S
hence progress condition is satisfied.


Bounded waiting:


  from the above it is clear that bounded waiting is also satisfy because process must be participate in CS in there second attempt.








No comments:

Post a comment

Popular Posts