I am trying to understand the Peterson's N-Process Algorithm and I came across this question.
Question: Suppose 3 processes have process IDs 0, 1 and 2
. These processes execute concurrently on a uni-processor and use Peterson's N-process algorithm to control execution of the critical section. Each process runs the following pseudo code:
lock(pid);
<critical section>;
unlock(pid
where lock()
and unlock()
functions are as defined as
lock(for Process i):
/* repeat for all partners */
for (count = 0; count < (NUMPROCS-1); count++) {
flags[i] = count;
turn[count] = i;
"wait until (for all k != i, flags[k]<count) or (turn[count] != i)"
}
Unlock (for Process i):
/* tell everyone we are finished */
flags[i] = -1;
Suppose the state of the system at any given time is defined by <flags[0], flags[1], flags[2], turn[0], turn[1]>
values and the id of the currently executing process. Further suppose that the current state of the system is <0,0,0,2,-1>
with process 0
currently executing. Show one particular way for three processes to run to completion starting from this state. As you trace the concurrent execution of three processes, show the state of the system at each step.
My observations
Processes running concurrently on a uni-processor can not execute on the CPU at the same time. Only one of them can execute on the CPU at a time. While a process is executing on the CPU it may execute any part of its code.
// NUMPROCS = 3
-- For i = 0
lock(for Process 0):
for (count = 0; count < 2; count++) {
flags[0] = count;
turn[count] = 0;
"wait until (for all k != 0, flags[k]<count) or (turn[count] != 0)"
}
Unlock (for Process 0):
flags[0] = -1;
-- For i = 1
lock(for Process 1):
for (count = 0; count < 2; count++) {
flags[1] = count;
turn[count] = 1;
"wait until (for all k != 1, flags[k]<count) or (turn[count] != 1)"
}
Unlock (for Process 1):
flags[1] = -1;
-- For i = 2
lock(for Process 2):
for (count = 0; count < 2; count++) {
flags[2] = count;
turn[count] = 2;
"wait until (for all k != 2, flags[k]<count) or (turn[count] != 2)"
}
Unlock (for Process 2):
flags[2] = -1;
My Question is that Where to start tracing the code? It is given that flags[0]=0, flags[1]=0, flags[2]=0, turn[0]=2, turn[1]=-1
but how it is going to help us where to start tracing the code?
If we start at just before the for loop of process
0
then all the turn values would be set to different values other than what is given to us.If we assume by executing question means process
0
is in it's critical section then the for loop of the next process will set the turn values to something else.
Why they are given us state values and how it can help us find where to start tracing the code.
It would be great if I get some hint to help me get started in tracing the code.
Thank you and sorry for the long question.