如果易失性不是一个好主意，则锁定的 C# 替代方法

Question

很抱歉，我知道这个话题已经被搞死了（我已经读过了，我已经读了这个，这个和其他一些），但我有一个问题，我不知道如何"正确"地做。

目前，我的多线程数独策略代码如下：

public class MultithreadedStrategy : ISudokuSolverStrategy
{
    private Sudoku Sudoku;
    private List<Thread> ThreadList = new List<Thread>();
    private Object solvedLocker = new Object();
    private bool _solved;
    public bool Solved // This is slow!
    {
        get
        {
            lock (solvedLocker)
            {
                return _solved;
            }
        }
        set
        {
            lock (solvedLocker)
            {
                _solved = value;
            }
        }
    }
    private int threads;
    private ConcurrentQueue<Node> queue = new ConcurrentQueue<Node>();
    public MultithreadedStrategy(int t)
    {
        threads = t;
        Solved = false;
    }
    public Sudoku Solve(Sudoku sudoku)
    {
        // It seems concevable to me that there may not be
        // a starting point where there is only one option.
        // Therefore we may need to search multiple trees.
        Console.WriteLine("WARNING: This may require a large amount of memory.");
        Sudoku = sudoku;
        //Throw nodes on queue
        int firstPos = Sudoku.FindZero();
        foreach (int i in Sudoku.AvailableNumbers(firstPos))
        {
            Sudoku.Values[firstPos] = i;
            queue.Enqueue(new Node(firstPos, i, false, Sudoku));
        }
        //Setup threads
        for (int i = 0; i < threads; i++)
        {
            ThreadList.Add(new Thread(new ThreadStart(ProcessQueue)));
            ThreadList[i].Name = String.Format("Thread {0}", i + 1);
        }
        //Set them running
        foreach (Thread t in ThreadList)
            t.Start();
        //Wait until solution found (conditional timeout?)
        foreach (Thread t in ThreadList)
            t.Join();
        //Return Sudoku
        return Sudoku;
    }
    public void ProcessQueue()
    {
        Console.WriteLine("{0} running...",Thread.CurrentThread.Name);
        Node currentNode;
        while (!Solved) // ACCESSING Solved IS SLOW FIX ME!
        {
            if (queue.TryDequeue(out currentNode))
            {
                currentNode.GenerateChildrenAndRecordSudoku();
                foreach (Node child in currentNode.Children)
                {
                    queue.Enqueue(child);
                }
                // Only 1 thread will have the solution (no?)
                // so no need to be careful about locking
                if (currentNode.CurrentSudoku.Complete())
                {
                    Sudoku = currentNode.CurrentSudoku;
                    Solved = true;
                }
            }
        }
    }
}

（是的，我已经完成了有递归和无递归的DFS，并使用BFS，这就是上述策略所修改的）

我想知道是否允许我将private bool _solved;更改为private volatile solved;并去掉访问器。我认为这可能是一件坏事，因为我的ProcessQueue()方法改变了_solved的状态。我是对的吗？我知道布尔是原子的，但我不希望编译器优化打乱我的读/写语句的顺序（尤其是因为写只发生一次）。

基本上，lock语句为该策略的运行时间增加了几十秒。如果没有锁，它的运行速度会快得多（尽管与DFS相比相对较慢，因为currentNode.GenerateChildrenAndRecordSudoku() 中的内存分配

Answer 1

在进入替代方案之前：通过访问布尔值volatile，在这里使用低锁解决方案可能是安全的。这种情况是理想的，因为您不太可能有复杂的观察排序要求。（"volatile"并不保证观察到多个volatile操作具有来自多个线程的一致顺序，只是读写具有获取和释放语义。）

然而，低锁定解决方案让我非常紧张，除非我确定有必要，否则我不会使用。

我要做的第一件事就是找出为什么锁上有这么多争论。一个未被控制的锁应该需要20-80纳秒；只有当锁被争用时，性能才会显著降低。为什么锁的争夺如此激烈？解决这个问题，你的性能问题就会消失。

如果不能减少争用，我可能会做的第二件事是使用读写器锁。如果我正确理解你的场景，你会有很多读者，只有一个作者，这对于读者-作者锁来说是理想的。

抛开波动性问题不谈：正如其他人所指出的，线程逻辑中存在一些基本错误，比如在布尔值上旋转。这东西很难做好。您可以考虑在这里使用任务并行库作为比滚动自己的线程逻辑更高级的抽象。TPL非常适合于必须在多个线程上完成大量工作的问题。（请注意，TPL并没有神奇地使非线程安全的代码成为线程安全的。但它确实提供了更高级别的抽象，因此您处理的是任务而不是线程。让TPL为您调度线程吧。）

最后：数独求解器需要几十秒的时间，这一想法向我表明，坦率地说，这个求解器不是很好。在理论上最糟糕的情况下，数独问题是一个很难快速解决的问题，无论你向它抛出多少线程。但对于"报纸"质量的数独，你应该能够编写一个在几分之一秒内运行的求解器。如果您可以在几百毫秒内完成整个工作，那么就没有必要将工作分配给多个线程。

如果你感兴趣，我有一个C#程序，可以在这里快速找到数独问题的解决方案：

http://blogs.msdn.com/b/ericlippert/archive/tags/graph+着色/

Answer 2

因此，首先，修复while循环，只连接线程。。。

    //Set them running
    foreach (Thread t in ThreadList)
        t.Start();
    //Wait until solution found (conditional timeout?)
    foreach (Thread t in ThreadList)
        t.Join(/* timeout optional here */);

然后是什么时候关闭线程的问题。我的建议是在类上引入一个等待句柄，然后在工作线程中循环。。。

ManualResetEvent mreStop = new ManualResetEvent(false);
//...
while(!mreStop.WaitOne(0))
{
    //...

现在只需修改Solved属性，就可以向所有线程发出应该退出的信号。。。

public bool Solved
{
    get
    {
        return _solved;
    }
}
// As Eric suggests, this should be a private method, not a property set.
private void SetCompleted()
{
    _solved = value;
    mreStop.Set();
}

这种方法的好处是，如果线程未能在超时时间内退出，您可以向mreStop发出信号，让其停止工作程序，而无需将_solved设置为true。

Answer 3

volatile IS用于防止对单个变量的读/写进行缓存和重新排序等优化。在这种情况下使用它正是它的设计目的。我看不出你关心什么。

lock是一个缓慢但有效的替代方案，因为它隐含地引入了内存围栏，但在您的情况下，您使用lock只是为了内存围栏的副作用，这不是一个好主意。