3

很抱歉，我知道这个话题已经死了（我已经读过我已经读过这个和这个以及更多）但是我有一个问题，我不确定如何“正确”地做。

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

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;为 aprivate volatile solved;并摆脱访问器。我认为这可能是一件坏事，因为我的ProcessQueue()方法改变了_solved我是否正确的状态？我知道布尔值是原子的，但我不希望编译器优化弄乱我的读/写语句的顺序（尤其是因为写只发生一次）。

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

4

3 回答 3

11

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

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

我要做的第一件事是找出为什么锁有这么多争用。一个非竞争的锁需要 20-80 纳秒；如果锁被争用，你应该只获得显着的性能下降。为什么锁的竞争如此激烈？解决这个问题，你的性能问题就会消失。

如果不能减少争用，我可能会做的第二件事是使用读写锁。如果我正确理解您的情况，您将有很多读者，只有一个作家，这是读写器锁的理想选择。

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

最后：数独求解器应该花费数十秒的想法向我表明，坦率地说，求解器不是很好。数独问题在理论上最坏的情况下是一个很难快速解决的问题，无论你投入多少线程。但是对于“报纸”质量的数独，您应该能够编写一个在几分之一秒内运行的求解器。如果您可以在几百毫秒内完成整个工作，则无需将工作分配给多个线程。

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

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

于 2012-01-05T21:29:28.500 回答
3

所以第一件事，修复你的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。

于 2012-01-05T21:23:39.280 回答
1

volatileIS 用于防止优化，例如单个变量的读/写缓存和重新排序。在这种情况下使用它正是它的设计目的。我不明白你的担忧是什么。

lock是一个缓慢但有效的替代方案，因为它隐式地引入了内存栅栏，但在您的情况下，您使用 a lockjust for the memory栅栏的副作用，这并不是一个好主意。

于 2012-01-05T21:05:19.517 回答