Why does Peterson lock fail in this test?

Question

I am experimenting with locks that do not require atomic instructions. Peterson's algorithm seemed the easiest place to start. However, with enough iterations, something goes wrong.

the code:

public class Program { private static volatile int _i = 0; public static void Main(string[] args) { for (int i = 0; i < 1000; i++) { RunTest(); } Console.Read(); } private static void RunTest() { _i = 0; var lockType = new PetersonLock(); var t1 = new Thread(() => Inc(0, lockType)); var t2 = new Thread(() => Inc(1, lockType)); t1.Start(); t2.Start(); t1.Join(); t2.Join(); Console.WriteLine(_i); } private static void Inc(int pid, ILock lockType) { try { for (int i = 0; i < 1000000; i++) { lockType.Request(pid); _i++; lockType.Release(pid); } } catch (Exception ex) { Console.WriteLine(ex); } } } public interface ILock { void Request(int pid); void Release(int pid); } public class NoLock : ILock { public void Request(int pid) { } public void Release(int pid) { } } public class StandardLock : ILock { private object _sync = new object(); public void Request(int pid) { Monitor.Enter(_sync); } public void Release(int pid) { Monitor.Exit(_sync); } } public class PetersonLock : ILock { private volatile bool[] _wantsCs = new bool[2]; private volatile int _turn; public void Request(int pid) { int j = pid == 1 ? 0 : 1; _wantsCs[pid] = true; _turn = j; while (_wantsCs[j] && _turn == j) { Thread.Sleep(0); } } public void Release(int pid) { _wantsCs[pid] = false; } } 

When I run this, I sequentially get <2,000,000. What happens?

Answer 1

The problem is the following two statements:

 _wantsCs[pid] = true; _turn = j; 

The .NET and C # memory models allow these two entries to be reordered.

To prevent them from reordering, add a memory barrier between them:

 _wantsCs[pid] = true; Thread.MemoryBarrier(); _turn = j; 

and you will get the expected result every time.

Note that this same problem is described on the Wikipedia page for the Peterson algorithm in the notes section (abbreviated here, read the article for full notes):

Notes
...
Most modern processors reorder memory access to improve execution efficiency (see Memory order for permitted reordering types). Such processors invariably provide some way to force sequencing in a memory access stream, usually using a memory instruction. The implementation of Peterson and its associated algorithms for processors that change the memory access order usually requires the use of such operations for proper operation, so that sequential operations are not performed in the wrong order.

(my emphasis)