7
$\begingroup$

The intuitive informal description of two process Peterson's algorithm for process 0 can be given as follows:

flag[0]=true;                   //I am ready to enter my critical region
turn=1;                         //but you may take your turn to enter your critical section

while(flag[1]==true && turn==1) //if you are ready to enter your critical section
                                //and if its your turn,
{ }                             //I will wait         

//Critical Section

flag[0]=false;                  //I am no more ready to enter my critical section

Peterson's algorithm for n processes is given as follows:

Each process runs the following pseudo code:

lock(pid);
<critical section>;
unlock(pid);

where lock() and unlock() functions are defined as below..

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;

Now I want to understand the n process Peterson's algorithm in same intuitive way, but I am unable to bring such informal explanation for it. To be precise I want to know the following:

  1. In 2 process Peterson's algorithm, flag[i]=true means "process i is ready to enter its critical section". What does it mean in n process algorithm when flag[i]=true

  2. In 2 process Peterson's algorithm, turn=1 means "its process 1's turn to enter its critical section". What does it mean in n process algorithm when turn[i]=x

  3. How can we intuitively / informally describe the line:

     "wait until (for all k != i, flags[k]<count) or (turn[count] != i)"
    
$\endgroup$
2
  • $\begingroup$ Copying material from others without attributing the source constitutes plagiarism. We don't like that. Please check out our guidelines on referencing material written by others and update your post accordingly. Thank you! $\endgroup$
    – D.W.
    Jul 22, 2016 at 4:39
  • $\begingroup$ Have you checked the description on Wikipedia? en.wikipedia.org/wiki/Peterson%27s_algorithm $\endgroup$ Jul 22, 2016 at 9:16

2 Answers 2

2
+50
$\begingroup$

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
$\endgroup$
10
  • $\begingroup$ It looks like this answer is misleading in some fundamental way. "flags[i] = count // I think I'm in position "count" in the queue." This explanation implicitly tell us there is a queue and each position of the queue can have at most one process, which is false. The word "estimate" is also very leading. There is no estimation per say. The code executed by each process is completely fixed, although its effect may not be certain for shared-writable variables. $\endgroup$
    – John L.
    Oct 24, 2018 at 23:08
  • $\begingroup$ @anir123 If this answer is a personal understanding, it does not matter much. However, it is unlikely to be up to the expectation of a better explanation of higher standard such as university textbook or even a good paper. (Of course, this is just my subjective judgement.) $\endgroup$
    – John L.
    Oct 24, 2018 at 23:13
  • $\begingroup$ "flag[0]=0; // I am at the tail of the queue" That comment is plainly wrong a you can see the other process will say the same, which is a contradiction. This assignment should be interpreted as I am interested in critical section. It is not about the queue at all. $\endgroup$
    – John L.
    Oct 24, 2018 at 23:18
  • $\begingroup$ The code snippet at the end is for process 0. For process 1, that line would read "flag[1] = 0". $\endgroup$
    – mhum
    Oct 24, 2018 at 23:26
  • $\begingroup$ Also, my intent was for the imaginary "queue" to be merely a thought exercise to interpret how the processes are behaving. Due to concurrency, there is not an actual queue and there are not actual positions to occupy. I don't think this is significantly different than the "waiting room" analogy presented in the Wikipedia write-up. $\endgroup$
    – mhum
    Oct 24, 2018 at 23:34
1
$\begingroup$

I'm late to the party but I suppose I can offer my intuition on this. I think of it as a race between threads. The race consists the number of laps = #threads-1. The idea is after each lap, 1 thread is left behind, so at the end of the race, only 1 thread is guaranteed to come out on top.

From the perspective of each thread, it looks like below (the comments).

For lock:

lock(for Process i): 
    for (count = 0; count < (NUMPROCS-1); count++):    // For each lap/iteration:
        flags[i] = count;                              // Update where I'm at right now.
        turn[count] = i;                               // Ring the bell to get my turn.
        wait until (for all k != i, flags[k] < count)  // If I'm the furthest in the race (highest iteration),
                or (turn[count] != i);                 // or I'm not the last to ring the bell in my current lap,
                                                       // then I can proceed to the next lap, else I'll just wait

For unlock:

unlock(for Process i):
    // I'm done with the race. Let the next guy be on top.              
    flags[i] = -1;
    // Imma do sth else now, but I might come back later tho.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.