Trying to understand the Peterson's N-Process Algorithm

Question

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.

Answer 1

Since you didn't ask for the answer to the question, and you asked a reasonable and sensible question I feel confident I can point you in the right direction without outright doing your homework (or whatever) for you.

First, the key part of the question is here:

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.

From this we can assume that the system was started normally and arrived at that state during it's execution. So we need to find a point where the system can be in that state and process 0 is executing. The next part gives us some wiggle room:

Show one particular way for three processes to run to completion starting from this state.

So, there may be multiple ways to get to those variable values with process 0 executing but it's OK to find any one and go from there to complete the system.

Further, we can see that all of the processes run once and exit -- there is a loop but we can also see that it increments the values of flags on each turn so we can take a good guess that we only hit this scenario for the variable values once. But we should work through it to find out.

The processes are running concurrently, but on a single processor. So in reality only one is ever executing but some higher power (an operating system for instance) is switching between them in a way we can't determine. You say:

While a process is executing on the CPU it may execute any part of its code.

I think you just worded this badly, I suspect you understand the reality is that each process starts at the beginning and runs until it's end, therefore "While a process is executing on the CPU it starts where it left off and may run any number of instructions until it loses the right to run on the CPU (the number of instructions is up to whatever is controlling the system)" is a more accurate statement.

So the easiest way is just to start at the beginning and turn the handle. The question doesn't say this but flags and turn are normally initialized to -1 so at the beginning we have:

flags = [ -1, -1, -1 ]; turn = [ -1, -1 ] 

Since things are running concurrently let's just assume that each process effectively executes each line at the same time. It doesn't make any difference, as you will hopefully be able to see for yourself later.

for (count = 0; count < (NUMPROCS-1); count++) {

OK, count = 0 for all processes and they all go to the next line:

flags[i] = count;

So now:

flags = [ 0, 0, 0 ]; turn = [ -1, -1 ]

So far, so good -- next line:

turn[count] = i;

OK, that's problematic -- each process tries to set the same variable. One of them will win but we don't know which one:

flags = [ 0, 0, 0 ]; turn = [ ?, -1 ]

Except we do, as it's in the question. We can make turn[0] = 2. So we're in a suitable state with the variables, we can assume process 0 is in control and we know it's on this line:

"wait until (for all k != i, flags[k]<count) or (turn[count] != i)"

To get you started, for process 0, count = 0 and i = 0 so

"wait until (for all k in {1,2}, flags[k]<0) or (turn[0] != i)"

You can see that the or clause is false, so process 0 will go round the loop again. So will process 1. The for all k clause is not true for anyone. So process 2 will wait because of the value of turn[0] -- you can also see that this will never change, so process 2 is now locked waiting for the for all k clause to become true -- in fact that's key to how this system works. If you follow the logic through to answer the question you'll see how the processes lock each other out so that only one ever executes the critical section at a time. Just keep doing what I did above, since you only need to find one pathway you can execute lines at the same time and when there's a potential clash just pick a value and go from there.

You can also see that if process 2 had executed all it's lines at once before the others had a chance, and then process 1 and then process 0 you'd end up in the same place. If you work through the whole system in various ways you'll find the pattern similar (note that there's no guarantee about the order the processes will execute their critical sections, it depends who 'wins' on the contested lines).

So back to the original question, there are only a few places where process 0 can be in control with that system state. Either on the wait line, or on the for line when count is increased to 1 (after it loops round) or on the line where it sets flag[0]. After that the system state isn't the same. Best to assume the earliest one as process 1 isn't blocked (yet) and could also change the state.

One final wrinkle, for completeness. There is one other place where that process one can be in control and the system state can be like that. And it's just before the turn[count] = i; line. In this scenario process 2 has just set the variable and process 0 is about to overwrite it. You can continue from here but it'll be processes 1 and 2 that go round the loop. I include this anticipating a comment about it, I'm not actually suggesting you use this as the starting point although it's completely valid. The question almost certainly expects you to start from processes 0 and 1 going round the loop, with 2 blocked in the busy wait to see what happens from there.

Good luck with it.