Racing

Racing performs the tie-break in the entry protocol with no additional code in the exit protocol.

Two kinds of races:

• read
• write

Read Race

plus(): ensures that

• When T0 and T1 both want to enter the critical section, they can use the values in R[0] and R[1] to determine priority based on their differences.
• If R[0] and R[1] have different values, one thread has priority, and the other must wait A mechanism for toggling between the states of T(0) and T(1) to prevent simultaneously entry into the critical section.

Write Race

Peterson’s other 2-thread solution for mutual exclusion. Peterson’s algorithm uses a third chalk board (like Dekker’s algorithm), but differently to deal with simultaneous arrivals and fairness.

After a person indicates intent on their own chalk board, they race with the other person to put their name on the third chalk board. The person who wins the race breaks the tie and goes into the critical section, which handles livelock problems (rule 4).

Fairness (rule 5) is provided by ensuring a person cannot win two races in a row.

Third chalk board only used for simultaneous arrivals. Otherwise, a person is free to enter multiple times in a row.

Almost identical to the declare intent program

Except for the entry protocol.

• If both threads arrive simultaneously, they both indicate their intent to enter and they both race to put the address of their me variable in Last.
• For this race to work, assignment must occur atomically, so one of the values is overwritten (rather than scrambling the bits during simultaneous assignment).
• Loser’s value is in variable Last, because it wrote over the winner’s value!!
• Now each thread enters the busy loop, checking first if the other thread even wants to go in, if yes, who won the race.
• If Last is &me, that means I lost the race and I have to wait. NO LIVELOCK!

Peterson's algorithm is RW-unsafe

because it relies on atomic assignment (write-write) to decide the winner of the race in the entry protocol.

That is, the hardware treats assignment like a critical section and provides mutual exclusion around it rather than scrambling the bits on simultaneous assignment.