C#实现同步算法

Question

我尝试用C#实现同步算法，但没有成功。

为什么下面的代码不是线程安全的？

using System;
using System.Threading;

namespace SoftwareLockTest
{
    class Program
    {
        private static volatile bool _isLocked1 = false;
        private static volatile bool _isLocked2 = false;
        private static volatile int _count = 0;

        static void Main(string[] args)
        {
            Thread thread2 = new Thread(Thread2Work);
            thread2.Start();

            Thread1Work();
        }

        public static void Thread1Work()
        {
            while (true)
            {
                _isLocked1 = true;

                while (_isLocked2)
                {
                    _isLocked1 = false;
                    while (_isLocked2) ;
                    _isLocked1 = true;
                }

                CriticalSection();
                _isLocked1 = false;
            }
        }

        public static void Thread2Work()
        {
            while (true)
            {
                _isLocked2 = true;

                while (_isLocked1)
                {
                    _isLocked2 = false;
                    while (_isLocked1) ;
                    _isLocked2 = true;
                }

                CriticalSection();
                _isLocked2 = false;
            }
        }

        private static void CriticalSection()
        {
            if (_count != 0)
            {
                Console.WriteLine("NOT THREAD SAFE 1");
                _count = 0;
            }

            _count++;

            if (_count != 1)
            {
                Console.WriteLine("NOT THREAD SAFE 2");
            }

            _count--;

            if (_count != 0)
            {
                Console.WriteLine("NOT THREAD SAFE 3");
            }
        }
    }
}

Answer 1

问题是先写后读可能会被重新排序（即使使用“易失性”）。您需要调用 Thread.MemoryBarrier();在四个“while (_isLockedX)”循环前面。

请阅读 http://www.albahari.com/threading/part4.aspx 了解内存屏障和易失性的解释。

对于任何实际项目，请优先选择现有的锁实现，而不是尝试创建自己的锁。

Answer 2

您正在尝试实施Dekker 算法。不幸的是，他生活在更简单的时代，当时硬件设计师和软件工程师仍在互相交谈。 PC 行业供应商之间的残酷竞争强调速度和核心，这给德克先生的独创性带来了厄运。有点高兴，我一定已经复习了这个算法几十次了，而且从来没有不头痛过。

嗯，这有点元。查看该维基百科文章中的“注释”，了解该算法不再起作用的原因。你有很多可行的替代方案。关键的一点是，您找到的任何有关并发性的文献超过 5 年的历史都不再相关了。

Answer 3

好吧，目前还不完全清楚您要尝试使用锁定标志做什么，并且理解代码对于线程来说是关键，但在没有锁定 / < code>Monitor，我希望看到很多用于增量 (.Increment) / 减量 (.Decrement) 的 Interlocked ) / 测试 (.CompareExchange)。仅仅因为它是易失性并不意味着两个线程在执行++/--时不会被绊倒。

但坦率地说，我只会使用锁，除非你有充分的理由不这样做。您希望保持简单 - “显然没有错误”，而不是“没有明显的错误”。

Answer 4

我仍在尝试解决这个问题，显然通常你确实应该使用锁......但我怀疑问题是易失性可能并不完全意味着什么你认为应该。

我希望您认为这意味着“当我写入此变量时，使写入立即可见；当我从此变量读取时，读取绝对最新的值”。 这并不完全是这个意思（尽管 MSDN 是这么说的）事实上，我自己的线程教程；当我更好地处理它时，我需要更新它）。

我会看看我是否能准确地弄清楚发生了什么，但它看起来确实很奇怪。我想我理解你的代码想要做什么，并且在对波动性做出“简单”假设时我还没有设法打破它......（并且我已经重现了这个问题，这总是有帮助的）

Answer 5

有趣的是，几个小时前在 codeguru 上出现了同样的查询...这是我的回复，改编自那里，但最重要的是你需要一个内存栅栏才能使该代码正常工作。

您的代码的问题在于它依赖于您的系统顺序一致。 x86 系统不是 SC。它们就是所谓的处理器一致性。

它非常微妙，所以让我们稍微简化一下您的代码：

thread1:

WRITE _isLocked1, 1
READ _isLocked2
(skip the while loop)
critical section
WRITE _isLocked1, 0

thread2:

WRITE _isLocked2, 1
READ _isLocked1
(skip the while loop)
critical section
WRITE _isLocked2, 0

处理器一致性仅表示线程 1 按照执行顺序观察线程 2 完成的写入（因此先写入 1，然后写入 0）。相反，线程 2 对线程 1 写入的观察。令您困扰的是处理器一致性几乎没有说明线程 1 的写入如何与线程 2 的写入交错，除了保持依赖操作的因果关系（这对您的示例并不重要）。

AMD 文档第 2 卷第 7.2 节提供了一组很好的示例，可以帮助您了解它并引用 Dekker 算法以及为什么它在 x86 系统上需要内存栅栏。

Answer 6

为什么不简单地使用lock？

lock (_anyInstantiatedObject)
{
    CriticalSection();
}

这样，您就可以依靠操作系统来确保没有其他线程同时进入临界区。