死锁和资源排序

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。具有相同索引但顺序相反的节点对象，这可能导致死锁。

同样，在synchronized块中，调用另一个buildSF方法，它在第三个Graph.Node上同步;第三张图。Node的索引不能比两个Graph都低。线程已经锁定的节点对象，因此也可能导致死锁