Question

Would peterson's algorithm work if regular flag registers are used instead of atomic flag registers

Answer 1

Peterson's Algorithm

Now that we understand sequential consistency, let's get back to mutual exclusion. Herlihy and Shavit calls Peterson's algorithm "the most succinct and elegant two-thread mutual exclusion algorithm." Well, this better be good. The original paper is here.

T1 T2 flag1 = true flag2 = true victim = 1 victim = 2 while (flag2 && while (flag1 && victim == 1) {} victim == 2) {} // critical section // critical section flag1 = false flag2 = false

Each thread begins by setting its flag to true. It then sets the victim variable to its thread id, and waits until either the other thread's flag is false or victim is set by the other thread.

To see informally why this ensures mutual exclusion, consider the case where T1 enters the critical section. Then the loop condition must have been false, which means either flag2 was false or victim was set to 2. If flag2 was false, then T2 was not even trying to enter the critical section. If victim was set to 2, then T2 was trying to enter the critical section, but T1 won the race.