Describe Peterson's solution for solving critical section problem
Peterson's algorithm (AKA Peterson's solution) is a concurrent programming algorithm for mutual exclusion that allows two processes to share a single-use resource without conflict, using only shared memory for communication.
The Algorithm:
The algorithm uses two variables, flag and turn. A flag[n] value of true indicates that the process wants to enter the critical section. The variable turn holds the ID of the process whose turn it is. Entrance to the critical section is granted for process P0 if P1 does not want to enter its critical section or if P1 has given priority to P0 by setting turn to 0.The algorithm does satisfy the three essential criteria[Mutual Exclusion,Progress,Bounded waiting] to solve the critical section problem.
Useful Links:
http://en.wikipedia.org/wiki/Peterson%27s_algorithm
Peterson's algorithm (AKA Peterson's solution) is a concurrent programming algorithm for mutual exclusion that allows two processes to share a single-use resource without conflict, using only shared memory for communication.
The Algorithm:
//flag[] is boolean array; and turn is an integer flag[0] = false; flag[1] = false; turn; | |
P0: flag[0] = true; turn = 1; while (flag[1] == true && turn == 1) { // busy wait } // critical section ... // end of critical section flag[0] = false; | P1: flag[1] = true; turn = 0; while (flag[0] == true && turn == 0) { // busy wait } // critical section ... // end of critical section flag[1] = false; |
Useful Links:
http://en.wikipedia.org/wiki/Peterson%27s_algorithm
Restricted to TWO processes that alternate execution between their critical sections and remainder sections
ReplyDeleteTo enter critical scetion Process Pi first sets flag i to be true and then sets turn to the vale of j,thereby asserting that if the other process wishes to enter the critical section it can do so
int turn;
boolean flag[2];
do{
flag[i]=TRUE;
turn=j;
while (flag[j] && turn ==j);
critical section
flag[i]=FALSE;
remainder se ction;
}while(TRUE);