在C#中实现同步算法

Question

在C#中实现同步算法

c#.netmultithreadingsynchronizationthread-safety

3

我将尝试在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");
            }
        }
    }
}

- DxCK

1

这可能是一个不错的实验，但对于真正的工作，您应该使用 Monitor 和 lock。 - H H

这不是作业，只是实验。 - DxCK

6个回答

6

你正在尝试实现Dekker's algorithm。不幸的是，他生活在更简单的时代，当硬件设计师和软件工程师仍在互相交流。 PC业务中供应商之间的激烈竞争，强调速度和内核，注定了Dekker先生的创新将会失败。我有点高兴，我必须回顾这个算法数十次，从未没有头疼过。

嗯，这有点元。查看维基百科文章中的“注意”部分，了解为什么该算法不再起作用。你有很多提供的替代方案可以使用。关键是，无论你找到的并发文献是否超过5年，都已经不再相关。

- Hans Passant

2

有趣的是，几个小时前，同样的问题在codeguru上提出...这是我的回复，改编自那里的回复，但重点是你需要为此代码添加内存栅栏才能正常工作。

你的代码存在问题，它依赖于系统的顺序一致性。x86系统不是顺序一致的，而是处理器一致的。

这非常微妙，因此让我们稍微简化一下你的代码:

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系统上进行内存栅栏。

- Mark oskin

他不是在写汇编语言，而是C#。恰好，.NET内存模型与x86内存模型在这方面匹配。对于其他处理器（例如IA-64），.NET运行时将插入所需的额外屏障等来模拟这些处理器上的.NET内存模型。您的ASM代码在单处理器（单核）的x86系统上是正确的 - 但他的C#代码在.NET内存模型中仍然不正确。编译器也可能重新排序指令。 - Daniel

2

嗯，不太清楚您想对锁标志进行什么操作，在多线程方面理解代码是至关重要的，但在缺乏lock / Monitor的情况下，我期望会看到很多Interlocked用于增量(.Increment) / 减量(.Decrement) / 测试(.CompareExchange)。仅仅因为它是volatile并不意味着两个线程在执行++/--时不会出现问题。

但老实说，除非您有充分的理由不这样做，否则我会直接使用lock。您希望保持简单 - "显然没有错误"，而不是"没有明显的错误"。

- Marc Gravell

他的“CriticalSection”在锁中受到保护 - 线程方法中的“while（_isLockedX）”循环实现了自旋锁。问题在于他的自旋锁实现存在一个错误（缺少内存屏障）。 - Daniel

好的，我已经给你的（更有见地的）答案点了赞，但我还是会留下这个回答，因为我认为它仍然提出了一些有效的观点，可能对“长尾”有用。 - Marc Gravell

2

我仍在努力解决这个问题，显然你通常应该使用锁……但我怀疑问题在于volatile可能并不意味着你认为的那样。

我想你认为它的意思是“当我写入这个变量时，立即使该写入可见；当我从这个变量读取时，读取一个绝对最新的值”。它并不完全意味着那个（尽管MSDN和我的线程教程都这么说；我需要在更好地掌握它之后更新它）。

我会看看能否弄清楚到底发生了什么，但看起来很奇怪。我想我理解你的代码试图做什么，而且我还没有成功地打破过它，即使是在简单地假设易失性的情况下……（而且我已经重现了这个问题，这总是有帮助的）

- Jon Skeet

0

为什么不直接使用lock呢？

lock (_anyInstantiatedObject)
{
    CriticalSection();
}

这样你就可以依赖操作系统来确保没有其他线程同时进入关键部分。

- vgru

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Daniel · Accepted Answer

问题在于写入操作后的读取可能会被重新排序（即使使用了“volatile”关键字）。您需要在四个“while (_isLockedX)”循环前调用Thread.MemoryBarrier（）。

请阅读http://www.albahari.com/threading/part4.aspx，了解有关内存屏障和volatile的说明。

对于任何真实项目，请优先考虑现有的锁实现，而不是尝试自己编写。