1.5 Synchronization, cpu scheduling  (Page 2/10)

Explain why this works.

But it is wrong! Why? (in case P1wants = P2wants = true then deadlock occurs)

Let's try again. The trouble was that setting want before the loop permitted us to get stuck. We had them in the wrong order!

Initially P1wants=P2wants=false

Code for P1 Code for P2

Loop forever { Loop forever {

while (P2wants) {} ENTRY while (P1wants) {}

P1wants = true ENTRY P2wants = true

critical-section critical-section

P1wants = false EXIT P2wants = false

non-critical-section } non-critical-section }

Explain why this works.

But it is wrong again! Why? (both processes may enter the CS)

So let's be polite and really take turns. None of this wanting stuff.

Initially turn=1

Code for P1 Code for P2

Loop forever { Loop forever {

while (turn = 2) {} while (turn = 1) {}

critical-section critical-section

turn = 2 turn = 1

non-critical-section } non-critical-section }

This one forces alternation, so is not general enough. Specifically, it does not satisfy condition three, which requires thatno process in its non-critical section can stop another process from entering its critical section. With alternation, if one process is in its non-criticalsection (NCS) then the other can enter the CS once but not again.

The first example violated rule 4 (the whole system blocked). The second example violated rule 1 (both in the critical section. Thethird example violated rule 3 (one process in the NCS stopped another from entering its CS).

In fact, it took years (way back when) to find a correct solution. Many earlier “solutions” were found and several werepublished, but all were wrong. The first correct solution was found by a mathematician named Dekker, who combined the ideas of turn and wants. The basicidea is that you take turns when there is contention, but when there is no contention, the requesting process can enter. It is very clever, but I amskipping it (I cover it when I teach distributed operating systems in V22.0480 or G22.2251). Subsequently, algorithms with better fairness properties werefound (e.g., no task has to wait for another task to enter the CS twice).

What follows is Peterson's solution, which also combines turn and wants to force alternation only when there is contention. WhenPeterson's solution was published, it was a surprise to see such a simple soluntion. In fact Peterson gave a solution for any number of processes. A proofthat the algorithm satisfies our properties (including a strong fairness condition) for any number of processes can be found in Operating Systems ReviewJan 1990, pp. 18-22.

Initially P1wants=P2wants=false and turn=1

Code for P1 Code for P2

Loop forever { Loop forever {

P1wants = true P2wants = true

turn = 2 turn = 1

while (P2wants and turn=2) {} while (P1wants and turn=1) {}

critical-section critical-section

P1wants = false P2wants = false

non-critical-section non-critical-section

}}

Hardware assist (test and set)

TAS(b), where b is a binary variable, ATOMICALLY sets b = true and returns the OLD value of b.

Of course it would be silly to return the new value of b since we know the new value is true.