如果volatile不是一个好主意,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;改为a private volatile solved;并摆脱存取者.我认为这可能是一件坏事,因为我的ProcessQueue()方法改变了我的状态_solved是正确的吗？我知道布尔是原子的,但我不希望编译器优化搞乱我的读/写语句的顺序(特别是因为写只发生一次).

基本上,lock语句会为此策略的运行时间增加数十秒.如果没有锁,它的运行速度会快很多(尽管由于内存分配而与DFS相比相对较慢)currentNode.GenerateChildrenAndRecordSudoku()

Answer 1

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

然而,低锁解决方案让我非常紧张,除非我确定我需要,否则我不会使用它.

我要做的第一件事是找出为什么在锁上存在这么多争用.无争用锁应该需要20-80纳秒; 如果锁争用,你应该只会显着降低性能.为什么锁如此严重争议？解决这个问题,你的性能问题就会消失.

如果无法减少争用,我可能会做的第二件事是使用读写器锁.如果我正确理解你的场景,你将拥有许多读者和只有一个编写器,这是读写器锁定的理想选择.

抛开波动性问题:正如其他人所指出的那样,线程逻辑中存在基本错误,例如在布尔上旋转.这个东西很难做对.您可以考虑将此处的任务并行库用作更高级别的抽象,而不是滚动您自己的线程逻辑.TPL非常适合必须在多个线程上进行大量工作的问题.(注意,TPL并没有神奇地使非线程安全的代码线程安全.但它确实提供了更高级别的抽象,因此您正在处理Tasks而不是Threads.让TPL为您安排线程.)

最后:一个数独求解器应该花费几十秒的想法向我表明,解算器坦白地说并不是很好.在理论上最糟糕的情况下,数独问题是一个难以解决的问题,无论你抛出多少线程.但对于"报纸"质量的sudokus,你应该能够编写一个在几分之一秒内运行的解算器.如果你可以在几百毫秒内完成所有工作,就没有必要将工作分配给多个线程.

如果您有兴趣,我有一个C#程序可以快速找到解决数独​​问题的方法:

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