Ошибка метода параллельного дерева печати

Question

Классы:

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();
        }

Вопрос:

Что здесь не так? Почему узел в некоторых случаях равен нулю?И это происходит только тогда, когда есть много сгенерированных узлов.Например, если будет только 10 узлов, все в порядке.

Answer 1

Проблема в том, что у вас есть этот код:

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

Позволяет нескольким потокам добавлять элементы в список newRootNodes одновременно. Как отметил комментатор, List<T> не является потокобезопасным. Вероятно, происходит то, что Add одного потока прерывается вызовом другого потока к Add, что приводит к увеличению внутреннего индекса в списке. Это оставляет значение null в одном из элементов списка.

Затем, позже в цикле вы получите:

rootNodes = newRootNodes; 

, который помещает поврежденный список в список, который будет повторяться к тому времени.

Answer 2

У вас есть гонка данных здесь:

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

Добавление в список с несколькими потоками не является потокобезопасным и приведет к неопределенному поведению.

Сначала попробуйте запустить эту часть с простым foreach и посмотрите, исчезнет ли проблема. Выполнение двух вложенных операторов Parallel.ForEach определенно является странным выбором.

Answer 3

List<T> действительно не является потокобезопасным, поэтому rootNode.Nodes.Add(childNode); отбрасывает данные непредсказуемым образом.

Вместо использования List<> используйте ConcurrentBag<>, и все будет работать. Обратите внимание, что ConcurrentBag<T> является неупорядоченным , но это хорошо, потому что у вас нет никакого способа в любом случае предсказать порядок из потоков.