Session 8 : Critical Section Problem: Semaphore Variable, Primitives

Critical Section Problem: Semaphore Variables,Primitives

Thought for today : “Invention is better than cure !”

Q?What is this Critical-Section problem

/>Here N processes are
competing to use some shared
resource or data. 

/>Each process has a code segment,
called critical-section, in which the shared resource or data is
accessed. 

Q?How do we ensure that when one process is executing in its ciritical
section, no other process is allowed to execute in its critical
section. 

/>we establish an access protocol
to enter the critical section in mutual
exclusion. 

Q?What is this Access Protocol to the Critical Section

/>It has two types of access protocol 

/1>Prologue : the process
execute a “reservation” code
before entering its critical section. This code will block other
process while my process is in its critical section

/2>Epilogue : the process
leaving its critical section executes a code to release
its critical section, and to inform other processes that the
critical section is no more busy.

Q?What are the specification of the Mutual exclusion

/>when one process executes
the shared variable, all other processes desiring to do so at that
same time moment must be kept waiting;
while that process has finished executing the shared variable, one of
the process waiting to do so should be allowed to proceed. This way
each process executes the shared data.

/>If the processes are performing operations that do
not conflict with one another they should be allowed to
proceed concurrently. 

/>the solution is symmetric:
the access do not depend on the relative priority of the process

/>the solution does not depend on the relative speed of the process 

/>the solution allows a process to access its critical section even
if another process is blocked outside its critical section 

/>the solution is deadlock free
and starvation free 

Example 1: Mutual exclusion Solution 1

/>In this solution only one process
executes at a time while other is waiting 

Process i:

while(TRUE){

while(turn==j); //nothing happens

Pi critical section

turn = j; // goes to the while loop where nothing happens

non critical section

}

Process j;

while(TRUE){

while(turn==i);

Pj critical section

turn = i;

non critical section

}

Note
*: always be careful that we have two processes i and j who are
trying to access the same critical region 

Example 2 : Mutual Exclusion : solution 2  

Process i:

while(TRUE){

while(flag[j]); //nothing happens

flag[i]= TRUE; //entry section

Pi critical section

flag[i]= FALSE; //exit section

non critical section

}

Process j;

while(TRUE){

while(flag[i]);

flag[j]= TRUE;

Pj critical section

flag[j]=FALSE;

non critical section

}

/>Here,both the process Pi and Pj are in critical region as the condition
satisfies : flag[i] == flag[j]== true; 

Example 3 : Mutual Exclusion : Solution 3 (Deadlock)

Process i:

while(TRUE){

flag[i]= TRUE; // flag[i] is set to true so always the condition

// satisfies

while(flag[j]); //entry section

Pi critical section

flag[i]= FALSE; // exit section

non critical section

}

Process j;

while(TRUE){

flag[j]= TRUE; //entry section

while(flag[i]); //deadlock occurs cos Pi and Pj both are inside

Pj critical section

flag[j] = FALSE; //exit section

non critical section

}

/>Each process Pi enters its critical section only if flag[j]== false

/>Here both process can be executing in their critical sections at the same
time, while flag[i]==flag[j]==true;so the dedlock occurs 

Example 4 : Mutual Exclusion Solution 4 

/>

Process i:

while(TRUE){

flag[i]= TRUE;

turn = j;

while(flag[j] && turn == j);

Pi critical section

flag[i]= FALSE;

non critical section

}

Process j;

while(TRUE){

flag[j]= TRUE;

turn = i;

while(flag[i] && turn == i);

Pj critical section

flag[j]= FALSE;

non critical section

}

/>Each Pi enters its critical section only if either flag[i]==flase or
turn == i;

/>Also note that, if both processes can be executing in their critical
sections at the same time, then flag[i]==flag[j]==true;

/>these two observations imply that Pi and Pj could not have successfully
executed their while statements at about the same time, since the
value of turn can be either i or j,
but not both. 

/>Hence, one of the processes, say Pj, must have successfully executed
the while statement, whereas Pi had to execute at least one
additional statement(“turn ==j”)

/>However, since at that time, flag[j]==true and turn==j, and this
condition will persist as long as Pj is in its critical section,
Mutual Exclusion is preserved. 

Q?What are the drawbacks of Solution 4 

/>this solution is valid for two processes, but cannot be generalized 

/>complex prologue (entry
code) and ineffective solution: busy
form of waiting(spin lock)

/>the complexity is due to the possibility that a process changes or
tests a variable, and this operation is “invisible” to the other
processes.(that means a process can react to a value of a variable
that mean while has been changed)

Q?What are other solutions to Mutual Exclusion in case of Single Processor
systems. 

/>Disable Interrupt as
prologue to the Critical Section

/>Enable Interrupt as epilogue
at the end of the Critical Section

Q?What are other solutions to Mutual Exclusion in case of Multiprocessor
systems with common memory

/>we use test-and-set special instruction on a lock variable

/>if the lock variable is 0
then the critical section is free 

/>if the lock variable is 1
then the critical section is busy 

/>the instruction test-and-set tests the content of a variable
and set it to 1 in a single atomic
cycle (atomic operations are one that cannot be divided into
any smaller parts)

Q?how is test-and-set pseudocode 

/>

char Test-and-Set(char
*target){

val= *target;

*targer = 1;

return val;

}

Q?How is mutual exclusion with Test-and-Set done 

/>

char s = 0 ; // initialization for all process Pi

while(TRUE){

while Test-and-Set(s); // LOCK(s) {i.e. sets the value to 1 }

critical section

s=0; //UNLOCK(s)

non critical section

}

Here the starvation might occur 

Q?How to do Mutual exclusion with Test-and-Set without starvation

/>

while(TRUE){

waiting[i] = TRUE;

key = TRUE;

while(waiting[i] && key) key= test_and_set(lock);// key = unlock

waiting[i] = FALSE;

critical section of Pi

j= (i+1) % N;

while((j <> i) and (! waiting[j])) j = (j+1) %N ;

// checks if next item of i is not waiting

if(j == i) lock= 0;

else waiting[j] = FALSE; //sets waiting false

non critical section

}

Q?what is the architecture of the multiprocessor system 

/>we have the main common memory
and all the processes will have their assigned independent
local memory 

Q?what are the drawbacks of spin lock 

/>busy form of waiting 

/>scheduling cannot be controlled by the programmer 

/>bus occupation ! 

YouTube : 

https://www.youtube.com/watch?v=1bxepBtcFFQ&index=8&list=PL2bE7itI_Ia5EalU1kCXtlNxJHAsUjZEB