Lock and Synchronize

Silberschatz: Operating System Concepts 8th Edition.
page 233. Hard-ware based.

All the models have one little trick in common: claim the lock before entering the critical section.

In real life, I can think of a bath-room-shortage scenario for the testAndSet() algorithm:

1. Several people are waiting for the same bathroom which takes one person only at a time. When the flag at the door is up, the bathroom is occupied and no one can enter it. 
2. So everyone keeps looking at the flag every a couple of seconds, and every time one looks at the flag, he puts the flag up, whether the flag was up or down.
3. Then one thinks about whether the flag was up or down before he flagged it up. If it was down, congratulations, it is your turn to enter. Otherwise, keep doing 2.
4. When one finishes, get out and put the flag down.

This claim-first, use-later guarantees when one enters the bathroom for "critical session", no one was in! Of course, there is an assumption: the observe and the flag up operations are successive and atomic. Namely, the flag observe operation is immediately followed by the flag up operation, and in between no other operations are allowed. Since the two operations are simple and fast, the assumption condition can be satisfied easily.

What would happen if enter-first then flag-up? Because entering the room could be slow, between the two operations, someone else may see the flag is down and enter the room!

As for the Swap() method, there is a little modification:

1. Everyone has a flag pointing up.
2. Every a couple of seconds, one switches his own flag with the door flag.
3. He observes his flag in hand: if up, keep doing 2; if down, enter the room. 
4. When one leaves the room, get out first and then put the flag down.

Well, if someone is unlucky, he might have to wait forever! Therefore the two algorithms above are not waiting-bounded.

The improvement is like a DMV, first come first server, using a first in first out queue: Everyone has a number. Everyone checks the room flag still. When someone leaves the room, however, only the one with the next number is granted to enter.  If the granted person is not ready (such as already took off because of long waiting, evolved in a conversation or abducted by aliens), then the next number is called.

/******************END******************/