java - 死锁和资源排序

Question

我在调试下面代码中的网格锁时遇到问题(旨在计算图形的生成森林，不一定是最小生成森林)。我在代码中很小心，总是首先获取具有较高索引的节点的锁，但是当我运行它时我仍然遇到死锁。我想知道我是否知道我的锁定策略哪里出了问题？我尝试使用 Eclipse 调试器进行调试，但似乎没有什么能真正说明是什么导致了它。

完整代码链接:https://github.com/lstrait2/parallel_SF?files=1

public class SFRunnable implements Runnable
    {
        private int start_idx;
        private int end_idx;
        private Graph.Node[] u_ancestors;
        private Graph.Node[] v_ancestors;
            private ArrayList<Graph.Edge> edges;
        private ConcurrentHashMap<Graph.Node,Graph.Node> newAncestors;


        public SFRunnable(
            int start, 
            int end, 
            ArrayList<Graph.Edge> edges, 
            Graph.Node[] u_ancestors, 
            Graph.Node[] v_ancestors, 
            ConcurrentHashMap<Graph.Node,Graph.Node> newAncestors
        ) {
            this.start_idx = start;
            this.end_idx = end;
            this.edges = edges;
            this.u_ancestors = u_ancestors;
            this.v_ancestors = v_ancestors;
            this.newAncestors = newAncestors;
        }
        @Override
        public void run()
        {
            for(int i = this.start_idx; i < this.end_idx; i++)
            {
                Graph.Edge e = this.edges.get(i);
                buildSF(i,this.u_ancestors,this.v_ancestors,this.newAncestors);
            }
        }

        private Graph.Node ancestorOf(
            final Graph.Node u, 
            ConcurrentHashMap<Graph.Node, Graph.Node> newAncestors
        ) {
            Graph.Node newAncestor;
            if(u.ancestor != u)
            {
                return u.ancestor;
            }
            else if( (newAncestor = newAncestors.get(u)) != null)
            {
                return newAncestor;
            }
            return u;
        }

        private void buildSF(
            int i, 
            Graph.Node[] u_ancestors, 
            Graph.Node[] v_ancestors, 
            ConcurrentHashMap<Graph.Node, Graph.Node> newAncestors
        ) {

            Graph.Edge e = this.edges.get(i);

            if(e.u.index < e.v.index)
            {
                synchronized(e.v)
                {
                    Graph.Node v_ancestor = e.v;
                    synchronized(e.u)
                    {
                        Graph.Node u_ancestor = e.u;
                        buildSF(e,i,u_ancestors,v_ancestors,newAncestors,u_ancestor,v_ancestor);
                    }
                }

            }
            else
            {
                synchronized(e.u)
                {
                    Graph.Node u_ancestor = e.u;
                    synchronized(e.v)
                    {
                        Graph.Node v_ancestor = e.v;
                        buildSF(e,i,u_ancestors,v_ancestors,newAncestors,u_ancestor,v_ancestor);
                    }
                }
            }
        }


        private void buildSF(
            Graph.Edge e, 
            int i, 
            Graph.Node[] u_ancestors, 
            Graph.Node[] v_ancestors, 
            ConcurrentHashMap<Graph.Node,Graph.Node> newAncestors, 
            Graph.Node u_ancestor, 
            Graph.Node v_ancestor
        ) {
            // locks acquired for u_ancestor and v_ancestor in previous call
            Graph.Node nextAncestor_u = ancestorOf(u_ancestor,newAncestors);
            Graph.Node nextAncestor_v = ancestorOf(v_ancestor,newAncestors);

            if(nextAncestor_u == u_ancestor && nextAncestor_v == v_ancestor)
            {
                if(u_ancestor == v_ancestor)
                    return;

                if(u_ancestor.index < v_ancestor.index)
                {
                    // swap nodes
                    Graph.Node temp = u_ancestor;
                    u_ancestor = v_ancestor;
                    v_ancestor = temp;
                }

                u_ancestors[i] = u_ancestor;
                v_ancestors[i] = v_ancestor;
                newAncestors.put(u_ancestor,v_ancestor);
            }
            else
            {

                if(nextAncestor_u == u_ancestor)
                {
                    synchronized(nextAncestor_v)
                    {
                        buildSF(e,i,u_ancestors,v_ancestors,newAncestors,u_ancestor,nextAncestor_v);
                    }
                }

                else if(nextAncestor_v == v_ancestor)
                {
                    synchronized(nextAncestor_u)
                    {
                        buildSF(e,i,u_ancestors,v_ancestors,newAncestors,nextAncestor_u,v_ancestor);
                    }
                }
                else if(nextAncestor_u.index < nextAncestor_v.index)
                {
                    synchronized(nextAncestor_v)
                    {
                        buildSF(e,i,u_ancestors,v_ancestors,newAncestors,u_ancestor,nextAncestor_v);
                    }
                }
                else
                {
                    synchronized(nextAncestor_u)
                    {
                        buildSF(e,i,u_ancestors,v_ancestors,newAncestors,nextAncestor_u,v_ancestor);
                    }

                }

            }
        }

这是图形代码:

import java.io.*;
import java.util.*;


public class Graph
{
    static class Node
    {
        final int index;
        Node ancestor;

        Node(int index)
        {
            this.index = index;
            ancestor = this;
        }


    }


    static class Edge
    {
        final Node u, v;
        boolean inSF = false;

        Edge(Node u, Node v)
        {
            this.u = u;
            this.v = v;
        }

    }



    ArrayList<Edge> edges;
    Node[] nodes;

    public Graph()
    {
        edges = new ArrayList<>();
        nodes = new Node[0];
    }

    static Graph readEdgeGraph(String file) throws IOException
    {
        BufferedReader reader = new BufferedReader(new FileReader(file));

        Graph g = new Graph();

        if(!"EdgeArray".equals(reader.readLine()))
            throw new IOException("invalid edge graph format");

        while(true)
        {
            String line;

            try
            {
                line = reader.readLine();
            }catch(EOFException e){ break;}


            if(line == null)
                break;

            String[] words = line.split("[ \t]+");
            if(words.length != 2)
                throw new IOException("invalid edge graph format");

            int u = Integer.parseInt(words[0]);
            int v = Integer.parseInt(words[1]);

            Node U = g.getVertex(u);
            Node V = g.getVertex(v);

            g.addEdge(U,V);
        }
        return g;
    }

    public Node getVertex(int n)
    {
        if(nodes.length < n)
            nodes = Arrays.copyOf(nodes, n+1+ n/2);

        if(nodes[n] == null)
            nodes[n] = new Node(n);

        return nodes[n];
    }

    public void addEdge(Node u, Node v)
    {
        Edge edge = new Edge(u,v);
        edges.add(edge);
    }


}

Answer 1

有可能在第一个 buildSF 方法中，e.u.index 可以等于 e.v.index。在这种情况下，两个线程可能会尝试以相反的顺序锁定具有相同索引的两个 Graph.Node 对象，这可能会导致死锁。

此外，在同步块(synchronized block)中，您调用另一个 buildSF 方法，该方法在第三个 Graph.Node 上同步；第三个 Graph.Node 的索引不能低于线程已经锁定的两个 Graph.Node 对象，因此这也可能导致死锁。