Konkurso-zagadko-ankieta - konkurencja

Jest sobie program http://4programmers.net/Pastebin/1854 , który odpala dwa wątki oraz przeprowadza synchronizacje b. prostym algorytmem bez używania jawnych locków. CriticalSectionFunc zlicza ile watkow dostalo sie do sekcji krytycznej. Jezeli algorytm jest poprawny to tylko jeden watek bedzie w sekcji krytycznej.
Niestety po odpaleniu programu na konsoli pokazuje się tekst:

ok [21250172], err [63], err % [0.000296]

Co oznacza, że algorytm 63 razy wpuścił do sekcji krytycznej dwa wątki jednocześnie.
Pytanie konkursowe: co jest nie tak i jak to poprawić?
Założenia: program ma działać na x86 lub x64 i ma **NIE **używać gotowych metod synchronzacji (typu CRITICAL_SECTION, semaforów, mutexów etc.). Testowane na VS2010 i na MinGW ale niewykluczone, że (nie)działa także na innych kompilatorach.

flags[num] = true;
turn = 1 - num;
MemoryBarrier();
while (flags[1 - num] && turn == 1 - num);

Aczkolwiek nie jestem stuprocentowo pewien czy MemoryBarrier() stoi w optymalnym miejscu (wydaje mi się, że w zależności od wątku powinien być w innym miejscu). Co do MinGW, musisz sobie znaleźć odpowiednik, bo to compiler intrinsic.
Problemem jest to, że dzisiejsze procesory w celach optymalizacji mogą sobie poprzenosić kolejność odczytów i zapisów do pamięci jak tam sobie chcą. Żeby temu zapobiec istnieją memory barriers. Jest o tym sporo w necie.

Aczkolwiek nie jestem stuprocentowo pewien czy MemoryBarrier() stoi w optymalnym miejscu (wydaje mi się, że w zależności od wątku powinien być w innym miejscu). Co do MinGW, musisz sobie znaleźć odpowiednik, bo to compiler intrinsic.

MemoryBarrier to po prostu instrukcja xchg. Może być też inna instrukcja z prefiksem lock

Problemem jest to, że dzisiejsze procesory w celach optymalizacji mogą sobie poprzenosić kolejność odczytów i zapisów do pamięci jak tam sobie chcą. Żeby temu zapobiec istnieją memory barriers. Jest o tym sporo w necie.

Raczej materiałów nie jest dużo, ale dla x86 i x64 jest kawałek dokumentacji, który opisuje w jakim przypadku procesor może zrobić reordering http://www.multicoreinfo.com/research/papers/2008/damp08-intel64.pdf . W tym kawałku kodu jest zapis a potem odczyt do innego adresu, co może zostać inaczej uszeregowane i powoduje wejście 2 wątków do sekcji krytycznej. Tak więc MemoryBarrier musi stać w tym miejscu dla obu wątków.
Na innych prockach niz intelowa powinny być jeszcze inne barriery.

A tak w ogóle to gratuluje, wygrałeś konkurs ;)