Hard
Peterson's algorithm built from plain non-atomic variables
Peterson's algorithm is the textbook proof that two threads can achieve mutual exclusion using only plain reads and writes of shared flag[]/turn, with no atomic read-modify-write instruction required. Compiled and run as plain (non-atomic, non-volatile) C++ variables on a real modern multicore machine with a standard optimizing compiler, is mutual exclusion actually guaranteed?
main.cpp
bool flag[2] = {false, false};
int turn = 0;
void thread0() {
flag[0] = true;
turn = 1;
while (flag[1] && turn == 1) { /* spin */ }
// critical section
flag[0] = false;
}
void thread1() {
flag[1] = true;
turn = 0;
while (flag[0] && turn == 0) { /* spin */ }
// critical section
flag[1] = false;
}26 of 51 in Concurrency