The way the N-process Peterson's algorithm works is slightly different than how the 2-process version is presented above. We can reason about the N-process version a little more like this:
When a process wants to start running (i.e.: executes lock()), it imagines that it's joining an imaginary queue of processes. It doesn't know exactly how many processes are in the queue nor exactly what position in the queue it is in (because of the vagaries of concurrency). It does know that the queue can only have N possible positions because there are N total processes. The goal is for to only allow a process to exit the lock() procedure once it is sure that it is at the head of the queue.
To keep the notation consistent with the pseudocode listed above, we'll say that position 0 is the tail (back) of the queue, position N-1 is the head (front) of the queue, position N-2 is second from the front, etc... , and position -1 means you're not in the queue at all (i.e.: has not executed lock()).
What each process does is it makes an estimate of what its potential position is in this queue and declares that it is the most recent process to estimate that it is in that position (if that position is not -1). Initially, when a process first starts the lock() procedure, it will of course estimate that it is at the back of the queue (i.e.: position 0). These estimates of where each process thinks it is in the queue and who is the most recent process to think they are in each position is shared information. In the pseudocode the position estimates per process are stored in the flags
array and the list of most recent process per position is in the turn
array.
Then, each process looks around at this shared information to see if it can update its estimate of where it is in the queue. These updates can only move a process's estimate one position forward in the queue (i.e.: closer to the head). You can update your position in two situations: 1) if another process comes later than you and thinks it is in the same position as you, 2) if everyone else thinks they're strictly behind you. Whenever you see one of these situations happen, you can update your estimate of your position to move one step toward the head.
lock(for Process i):
/* repeat for all partners */
for (count = 0; count < (NUMPROCS-1); count++) {
flags[i] = count; // I think I'm in position "count" in the queue
turn[count] = i; // and I'm the most recent process to think I'm in position "count"
"wait until // wait until
(for all k != i, flags[k]<count) // everyone thinks they're behind me
or (turn[count] != i)" // or someone later than me thinks they're in position "count"
// now I can update my estimated position to "count"+1
} // now I'm at the head of the queue so I can start my critical section
Unlock (for Process i):
/* tell everyone we are finished */
flags[i] = -1; // I'm not in the queue anymore
As noted before, this is slightly different than the presentation of the 2-process version as given above. However, we can reframe that presentation in this framework easily with only some slight modification. Note that in the 2-process case, the queue only has two potential positions, the head (position 1) and the tail (position 0) of which only position 0 is explicitly claimed.
flag[0]=0; // I am at the tail of the queue
turn=0; // and I am the most recent process to join the queue
while (flag[1]==0 // while you are in the queue
&& turn==0) // and I joined the queue later than you did
{ } // I will wait
//Critical Section
flag[0]=-1; // I am no longer in the queue