并行树打印方法中的错误

本文关键字：错误 方法 打印 并行 | 更新日期: 2023-09-27 18:20:34

类：

public class Tree
{
    public Node RootNode { get; set; }
}
public class Node
{
    public int Key { get; set; }
    public object Value { get; set; }
    public Node ParentNode { get; set; }
    public List<Node> Nodes { get; set; }
}

方法：

此方法生成一个树。

private static int totalNodes = 0;
       static Tree GenerateTree()
       {
           Tree t = new Tree();
           t.RootNode = new Node();
           t.RootNode.Key = 0;
           t.RootNode.Nodes = new List<Node>();
           Console.WriteLine(t.RootNode.Key);
           List<Node> rootNodes = new List<Node>();
           rootNodes.Add(t.RootNode);
           while (totalNodes <= 100000)
           {
               List<Node> newRootNodes = new List<Node>();
               foreach (var rootNode in rootNodes)
               {
                   for (int j = 0; j < 3; j++)
                   {
                       totalNodes++;
                       Console.Write(string.Format(" {0}({1}) ", totalNodes, rootNode.Key));
                       Node childNode = new Node() {Key = totalNodes, Nodes = new List<Node>(), ParentNode = t.RootNode};
                       rootNode.Nodes.Add(childNode);
                       newRootNodes.Add(childNode);
                   }
                   Console.Write("     ");
               }
               Console.WriteLine();
               rootNodes = newRootNodes;
           }
           return t;
       }

这个方法应该打印一个树，但在某些情况下节点为空：

 static void PrintTreeParallel(Node rootNode)
       {
           List<Node> rootNodes = new List<Node>();
           List<Node> newRootNodes = new List<Node>();
           rootNodes.Add(rootNode);
           Console.WriteLine(rootNode.Key);
           while (rootNodes.Count > 0)
           {
               newRootNodes = new List<Node>();
               Parallel.ForEach(rootNodes, node =>
                                               {
                                                   if (node != null)
                                                   {
                                                       Console.Write(string.Format(" {0} ", node.Key));
                                                       if (node.Nodes != null)
                                                           Parallel.ForEach(node.Nodes,
                                                                            newRoot => { newRootNodes.Add(newRoot); });
                                                   }
                                                   else
                                                   {
                                                       //HOW CAN WE GET HERE?????
                                                       Debugger.Break();
                                                       Console.WriteLine(rootNodes.Count);
                                                   }
                                               });
               Console.WriteLine();
               rootNodes = newRootNodes;
           }
       }

执行：

 static void Main(string[] args)
        {
            var t = GenerateTree();
            Console.WriteLine("Tree generated");

            PrintTreeParallel(t.RootNode);
            Console.WriteLine("Tree printed paral");

            Console.ReadLine();
        }

问题：

这里怎么了为什么在某些情况下节点为null？只有当有大量生成的节点时，才会发生这种情况。例如，如果只有10个节点，则一切正常。

并行树打印方法中的错误

问题是您有以下代码：

Parallel.ForEach(node.Nodes, newRoot => { newRootNodes.Add(newRoot); });

这允许多个线程同时向newRootNodes列表中添加项目。正如一位评论者指出的，List<T>不是线程安全的。可能发生的情况是，一个线程的Add被另一个线程对Add的调用中断，这导致列表中的内部索引增加。这会在列表的某个项目中留下一个null值。

然后，在循环的后面，你有：

rootNodes = newRootNodes;

这将损坏的列表作为要在while之前迭代的列表。

这里有一场数据竞赛：

Parallel.ForEach(node.Nodes,
      newRoot => { newRootNodes.Add(newRoot); });

添加到具有多个线程的列表不是线程安全的，并且会导致不确定的行为。

首先试着用一个简单的foreach运行这个部分，看看问题是否消失了。运行两个嵌套的Parallel.ForEach语句无疑是一个奇怪的选择。

List<T>确实不是线程安全的，因此rootNode.Nodes.Add(childNode);正在以不可预测的方式丢弃数据。

不用List<>，用ConcurrentBag<>就可以了。请注意，ConcurrentBag<T>是无序的，但这很好，因为无论如何都无法从线程中预测顺序。

相关文章：