Deadlock without cycle

if I draw a graph that symbolizes all possible calls to blocking functions (java synchronized methods) and I haven't got any cycle in this graph, can I be sure that deadlocks are imposible. Do petri-nets not work like that?

I am not looking for answers like this: Use some monster framework blahblah.

I want to handle my multithreading with synchronized methodes.

EDIT1: The pointed 开发者_如何学编程arrows symbolize if one class calls any synchronized method of another class EDIT2:klick @here the example, showing a cycle

No, that is not enough. Suppose you have to threads: A and B. A calls a method m1 of object o1, which calls method m1 of object o2. Thread B calls method m2 of object o2, which calls method m2 of object o1. Suppose all methods are synchronized. Now, there are concurrent executions of A and B which lead to dead-locks. Although, there is no cyclic call relation between methods.

Is that homework?

Even with your edit regarding class it is not enough, because you can close the cycle through a non synchronized method call.

No. Consider:

private static final Semaphore foo = new Semaphore(1);
private static final Semaphore bar = new Semaphore(1);

private static void one() throws InterruptedException {
    foo.acquire();
    bar.acquire();
    bar.release();
    foo.release();
}

private static void two() throws InterruptedException {
    bar.acquire();
    foo.acquire();
    foo.release();
    bar.release();
}

See http://pastebin.com/QfK5ZByj for a runnable example. It deadlocks pretty quickly for me.

Some methods might block without a synchronized key word. This applies to many methods in package java.util.concurrent for instance. You should also take into account the synchronized blocks inside methods.

If considering only synchronized methods, you can have deadlocks without cycle in methods calls, as the synchronized methods use the object instance as a monitor. For instance if you have two objects A and B, each one with synchronized methods 1() and 2(). If A.1() calls B.1() and B.2() calls A.2(), although there is no cycle in methods, if a thread calls B.2() at the same time an other calls A.1() then there is a deadlock risk.