Exercise 10.9 Greg Hudson ------------- Assertion 10.5.3: In any reachable system state of PetersonNP: 1. If process i is a competitor at level k, if pc[i] = check-flag and if any process j != i in S[i] is a competitor at level k, then turn(k) != i. 2. If process i is a winner at level k and if any other process is a competitor at level k, then turn(k) != i. Assume that "i is a competitor at level k" means that i has finished set-flag[i] and set-turn[i] for level k, i.e. flag[i] = k and pc[i] is not set-flag or set-turn. We will also say that a process in the critical region (pc[i] = leave-try) is not a competitor at any level. Assume that "i is a winner at level k" means that level[i] > k, or that i is in the critical region of k = n - 1. First note that, by a very simple induction, at the end of each round flag[i] = level[i] except when pc[i] = set-turn[i]. We will prove this claim by induction. The base case is obvious, since no processor is a competitor or winner at any level initally. Now assume that both conditions are true at the beginning of a round. We will show that each transition guarantees that the conditions are true at the end of the round. try[i], set-flag[i], crit[i], exit[i], reset[i], and rem[i] are trivial. set-turn[i] sets turn(level[i]) to i and S[i] to {i}. So process i satisfies condition 1 since there are no j != i in S[i], and every other competitor at level[i] satisfies condition 1 since turn(level[i]) = i. By the induction hypothesis, condition 1 is true for all other levels. Condition 2 remains true by the induction hypothesis and the observation that although we're introducing a competitor at level[i], turn(level[i]) gets i so turn(level[i]) will not be the index of any winner at level[i]. check-flag(j)[i] has several cases (let k be level[i] at the beginning of the round): * If flag(j) >= k then S[i] := {} and both conditions are obviously satisfied by the induction hypothesis. * If flag(j) < k then S[i] := S[i] + {j}. Since j is not a competitor at k, condition 1 is still satisfid. Condition 2 is not affected. * If |S| = n after S[i] := S[i] + {j}, then pc[i] becomes set-flag or leave-try, so i is not a competitor at any level and condition 1 is satisfied by the induction hypothesis. Since i has become a winner at k, we must verify condition 2; by the induction hypothesis, since i was a competitor at level k at the beginning of the round, S includes all other processes except j, and j is not a competitor at k, if there are any competitors at k, turn(k) != i. So condition 2 is satisfied. check-turn[i] has several cases (let k be level[i] at the beginning the round): * If turn(k) = i then S[i] bcomes {i} and condition 1 is easily satisfied. Condition 2 is not affected, so is true by the induction hypothesis. * If turn(k) != i, then i becomes a winner at level k, and a non-competitor at any level (for the moment). Condition 1 is not affected, and since turn(k) != i, condition 2 is satisfied. So assertion 10.5.3 is true. Exercise 10.20 Greg Hudson -------------- Upper bound: Let's work backwards from the time when some process enters the critical region. We will discuss the three phases going back to the time when some process reaches M, and then show how long it takes for some process to reach M. Phase: A process k has reached M and no higher-numbered process has finished testing k's flag in the first loop. O(nl) time before process k reaches the critical region.. Phase: A process k has reached M, is the highest-numbered process to do so, and no higher-numbered process has finished testing k's flag in the second loop. O(nl) time to previous phase since any higher-numbered process will go to L within n steps, set its flag to 0, and leave its flag at 0 until all processes which have reached M enter and leave the critical region. Phase: A process k has reached M and is the highest-numbered process to do so. O(nl) time to previous phase since any higher-numbered process which has finished testing k's flag in the second loop must reach M or go back to L within O(nl) time, and once back at L their flags remain 0 until the processes which reached M enter and leave the critical region. O(n^2l) time before a process reaches M, as follows: suppose there are m processes in the trying region, and no other processes enter the trying region henceforth. Then within O(nl) time the least process will successfully test all the flags of processes lower than it, set its flag to 1, repeat the tests, and reach M. So if at least one process is in the trying region, within O(nl) time either some other process enters the trying region or some process reaches M. Since only n processes can enter the trying region (before some process enters the critical region), it takes O(n^2l) time before a process reaches M. So the total time is O(n^2l). Execution: As an example of how an execution might take O(n^2l) time before a process reaches M, consider the execution where process n enters the trying region, performs n-1 comparisons and sets its flag to 1. At this point, process n-1 enters the trying region and performs its n-2 comparisons in lock-step with process n's second set of comparisons. Now say process n-1 sets its flag to 1 just before process n tests process n-1's flag. Process n now has to go back to L and will be irrelevant until some process reaches the critical region (we will have it take steps at regular intervals for the rest of the execution, but it will never reach the second loop). Now process n-1 is ready to do the second loop; at this point we introduce process n-2 into the trying region and do the same thing as we did to process n, etc.. The end result of this execution is that each process j will run for theta(jl) time before process j-1 enters the trying region, but only process 1 manages to reach M. Therefore, the time taken is the sum of theta(jl) from j=1 to n, or theta(n^2l) time. Once process 1 reaches M, it will take O(nl) steps for some process to reach the critical region, so we have theta(n^2l) + O(nl) = theta(n^2l) time taken. Exercise 10.22 Greg Hudson -------------- Here's a three-process execution: processes 1 and 2 alternate through the critical region, each entering the trying region before the other leaves the critical region, so that we have a sequence: number(1) gets 1 process 1 enters the critical region number(2) gets 2 process 1 leaves the critical region process 2 enters the critical region number(1) gets 3 etc. At some point, either number(1) or number(2) will get b-1. Let's say that number(1) gets b-1 (if b is odd, reverse the order in which process 1 and 2 started alternating in the above sequence). At this point in our execution, we will have process 2 exit the critical region (so number(2) gets 0) and process 1 enter it. Now in our execution, process 2 and 3 will enter the trying region in lock step, and both choose 1 + number(1) = 1 + (b - 1) = 0 (mod b), and set choosing to 0. Then process 1 will exit the critical region. Now number(1,2,3) = choosing(1,2,3) = 0, and process 1 and 2 are in the for loop. Both of them will leave the for loop and enter the critical region. Exercise 10.31 Greg Hudson -------------- The algorithm does not satisfy progress. One case where it doesn't make progress is, for a two-process system: Process 1 sets x := 1 Process 2 sets x := 2 Process 1 tests y, finds it 0 Process 2 tests y, finds it 0 Process 1 sets y := 1 Process 2 sets y := 1 Process 1 tests x, finds it 2, goes to L Process 1 sets x := 1 Process 2 tests x, finds it 1, goes to L Now both process 1 and 2 are at L and y is 1, so neither of them can get past the second statement in the algorithm. So neither process can reach the critical region. So the algorithm does not satisfy the two claimed conditions.