8 / 10 Locks & Mutual Exclusion

Whose Turn Is It

An engineer writes Peterson's algorithm from memory. Reasoning that turn records whose turn it is to enter, they set it to their own thread id:

int flag[2] = {0, 0};
int turn = 0;

void lock(int self) {
    flag[self] = 1;
    turn = self;                                   // differs from Peterson's
    while (flag[1 - self] == 1 && turn == 1 - self)
        ;                                          // spin
}

void unlock(int self) { flag[self] = 0; }

Assume a sequentially consistent machine (no store reordering). Which interleaving puts both threads in the critical section at the same time?

A

None on this machine. The bug only appears on hardware that reorders the store to flag after the store to turn.

B

T0 runs flag[0]=1; turn=0; and its spin test fails because flag[1] is still 0, so it enters. T1 then runs flag[1]=1; turn=1; and its test needs turn == 0, which is now false, so it enters too.

C

Both threads execute flag[self] = 1 before either executes its turn write, so both see flag[1-self] == 1 and both spin forever.

D

T0 enters and T1 spins forever, because unlock clears flag but never restores turn to the other thread.