c# - 为什么彼得森的锁在这个测试中失败了？

Question

我正在试验不需要原子指令的锁。彼得森的算法似乎是最简单的起点。但是，经过足够多的迭代，就会出现问题。

代码:

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;
    }
}

当我运行这个时，我总是得到 < 2,000,000。怎么回事？

Answer 1

这里的问题是这两个语句:

_wantsCs[pid] = true;
_turn = j;

.NET 和 C# 的内存模型允许对这两个写入进行重新排序。

为了强制它们不被重新排序，在它们之间添加一个内存屏障:

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

你每次都会得到预期的输出。

请注意，Wikipedia page for Peterson's Algorithm 中描述了这个问题在注释部分(此处已缩短，请阅读文章以获取完整注释):

Notes
...
Most modern CPUs reorder memory accesses to improve execution efficiency (see memory ordering for types of reordering allowed). Such processors invariably give some way to force ordering in a stream of memory accesses, typically through a memory barrier instruction. Implementation of Peterson's and related algorithms on processors which reorder memory accesses generally requires use of such operations to work correctly to keep sequential operations from happening in an incorrect order.

(我的重点)