We are the Dev Teams of
  • brands
  • ebay_main
  • ebay
  • mobile
<
>
BLOG

A Concurrent Monday

by Sergiusz Urbaniak
in Tutorials

We live in a concurrent world and especially as developers we are constantly faced with concurrency issues. As a frontend developer you are faced with concurrent UI events, asynchronous backend calls and background computation. As a backend developer you are faced with multiple concurrent incoming requests which have to be orchestrated and forced to work concurrently with external systems like databases. Things get even more complicated if all of these things run truly parallel. As we are all aware, it is hard to understand how concurrent execution is achieved. Ideally, we'd like to have a simple graphical model which one can draw on a blank paper and use as the basis for discussion.

Therefore I would like to share a technique with you for using petri nets which helped me to understand how concurrent execution is achieved using a simple mathematical model which has almost been forgotten but in my opinion is still very useful.

Petri Nets

So what is a petri net anyways? Let's be a little academic here. According to Peterson [1] a petri net is composed of a set of places and transitions and their corresponding input and output functions. It is being expressed as a graph containing vertices and connecting arcs. A vertex can either be a place or a transition. A place is being represented as a circle, a transition as a simple square. An arc connects places and transitions but never places and places or transitions and transitions (so that the graph is bipartite). Furthermore arcs are directed. Finally multiple arcs between vertices are allowed:

What makes petri nets suitable for examining concurrent systems are its dynamic properties. That's where tokens come into play. Tokens reside inside places (but never inside transitions) and travel to other places through transitions. If a place containing a token is connected through a transition to another place it can receive this very token. A transition without any incoming arcs can emit as many tokens as it likes. A transition without any outgoing arcs can "swallow" tokens. The state of the whole petri net therefore can change and the state changes can be animated:

Now imagine the token is the actual program pointer and the token travels such as in an IDE's debugger view as you step through the code. It represents the current state of our system. An animation of the travelling tokens represents its state changes. The following animation represents a possible model of a simple method call 'method1()' including a call to another method 'call1()', an if-statement calling either the method 'branch1()' or 'branch2()':

Modeling Threads

Synchronized

As you can see the petri net model is pretty simple. It is almost like an animated flowchart diagram. But how do threads fit into this picture? An image of our method 'method1()' is being called by two threads:

Now slowly the petri net becomes a little more expressive. Let's say we change the code and make 'method1()' synchronized as follows:

    synchronized void method1() {
        // body
    }

The 'synchronized' keyword implies an intrinsic lock (mutex) on the object instance where the method 'method1()' was declared. We can represent the state of the intrinsic lock by a place which initially has a token inside. If one thread enters the method it acquires the intrinsic lock thus pulling out the token from the intrinsic lock place. If the same thread leaves the method it releases the lock thus putting a token back intro the intrinsic lock place so other threads can acquire it:

Starvation

Let's model another synchronization primitive the using the notify()/wait() methods. As you know the notify/wait methods are being executed inside a synchronized block. So we have to draw the same intrinsic lock petri net structure as above but with a few additional places and transitions to model the notify/wait semantics.

    public static void main(String[] args) {
        final Object object = new Object();

        new Thread(new Runnable() {
            @Override
            public void run() {
                System.out.println(Thread.currentThread() + " notifying");

                synchronized (object) {
                    object.notify();
                }
            }
        }).start();

        new Thread(new Runnable() {
            @Override
            public void run() {
                System.out.println(Thread.currentThread() + " waiting");

                synchronized (object) {
                    try {
                        object.wait();
                    } catch (InterruptedException e) {
                        Thread.currentThread().interrupt();
                    }
                }

                System.out.println(Thread.currentThread() + " won");
            }
        }).start();
    }

Now let's execute the "happy" case where the wait()ing thread releases the intrinsic lock first and the notify()ing thread acquires the same intrinsic lock as the second one in order:

The standard output could look like this:

    Thread[Thread-0,5,main] waiting
    Thread[Thread-1,5,main] notifying
    Thread[Thread-0,5,main] won

Let's turn orders now. Let's assume that the notify()ing thread notify()s first:

The standard output could look like this:

    Thread[Thread-0,5,main] notifying
    Thread[Thread-1,5,main] waiting

Can you see how the wait()ing thread is staying at the lower left place in the net? This is a typical starvation situation. The wait()ing thread does not get notify()ied because the other thread already finished. If you execute the code above you might get lucky and the program finishes as in the first simulation. If you are unlucky you'll get a starvation situation as in the second simulation. On my machine I always get a starvation situation with the following thread dump stacktrace reflecting this fact:

    "Thread-1" prio=5 tid=0x00007fcf2b06f000 nid=0x6103 in Object.wait() [0x0000000195bbe000]
       java.lang.Thread.State: WAITING (on object monitor)
        at java.lang.Object.wait(Native Method)
        - waiting on <0x000000016237f710> (a java.lang.Object)
        at java.lang.Object.wait(Object.java:503)
        at foo.WaitStarvation$2.run(WaitStarvation.java:26)
        - locked <0x000000016237f710> (a java.lang.Object)
        at java.lang.Thread.run(Thread.java:744)

Deadlocks

You can simulate a deadlock using petri nets by copy/pasting the above intrinsic lock networks. Ever wondered how the following code could produce a deadlock?

    final Object lock1 = new Object();

    final Object lock2 = new Object();

    new Thread(new Runnable() {
        @Override
        public void run() {
            System.out.println(Thread.currentThread() + " trying lock1");

            synchronized (lock1) {
                synchronized (lock2) {
                    System.out.println(Thread.currentThread() + " acquired lock1, then lock2");
                }
            }

            System.out.println(Thread.currentThread() + " won");
        }
    }).start();

    new Thread(new Runnable() {
        @Override
        public void run() {
            System.out.println(Thread.currentThread() + " trying lock2");

            synchronized (lock2) {
                synchronized (lock1) {
                    System.out.println(Thread.currentThread() + " acquired lock2, then lock1");
                }
            }

            System.out.println(Thread.currentThread() + " won");
        }
    }).start();

First let's watch the happy case situation:

Now let's watch a situation where a deadlock can happen:

If a context switch happens from Thread 1 to Thread 2 right after the synchronized(lock1) block a deadlock can occur. The following thread dump stacktrace exposes this fact:

    "Thread-1":
            at foo.Deadlock$2.run(Deadlock.java:38)
            - waiting to lock <0x000000016e17f300> (a java.lang.Object)
            - locked <0x000000016e17f310> (a java.lang.Object)
            at java.lang.Thread.run(Thread.java:744)
    "Thread-0":
            at foo.Deadlock$1.run(Deadlock.java:23)
            - waiting to lock <0x000000016e17f310> (a java.lang.Object)
            - locked <0x000000016e17f300> (a java.lang.Object)
            at java.lang.Thread.run(Thread.java:744)

A Synchronized / NotifyAll Deadlock

I would like to show you a real live example when I used a petri net in order to understand the deadlock we found in Apache Lucene (see https://issues.apache.org/jira/browse/LUCENE-5002).

Take the following notifier class which is responsible for notifying all waiting threads. The same instance is being used by the waiting threads:

    class Notifier {

        public synchronized void doNotifyAll() {
            this.notifyAll();
        }

        public synchronized void doWait() {
            try {
                this.wait();
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
            }
        }
    }

In order to make the case a little more fun take the following class which acts as a proxy to the notifier:

    class Intrinsic {
        private final Notifier notifier;

        public Intrinsic(Notifier notifier) {
            this.notifier = notifier;
        }

        public final synchronized void lock1() {
            notifier.doWait();
        }

        public final synchronized void lock2() {
            notifier.doNotifyAll();
        }
    }

The above classes are stitched in two concurrently running threads in the main method:

        final Notifier notifier = new Notifier();
        final Intrinsic intrinsic = new Intrinsic(notifier);

        new Thread(new Runnable() {
            @Override
            public void run() {
                intrinsic.lock1();
            }
        }).start();

        new Thread(new Runnable() {
            @Override
            public void run() {
                intrinsic.lock2();
            }
        }).start();

Do you see the deadlock? The petri net is actually very simple, even simpler than the synchronized example above, so grab a coffee and watch the deadlock happen:

If you execute the above code you may see the following thread dump stacktrace:

    "Thread-1" prio=5 tid=0x00007fd93d09d000 nid=0x6203 waiting for monitor entry [0x000000019b763000]
       java.lang.Thread.State: BLOCKED (on object monitor)
        at foo.Intrinsic.lock2(Intrinsic.java:15)
        - waiting to lock <0x0000000167e85c90> (a foo.Intrinsic)
        at foo.Main$2.run(Main.java:19)
        at java.lang.Thread.run(Thread.java:744)

    "Thread-0" prio=5 tid=0x00007fd93d09c800 nid=0x6003 in Object.wait() [0x000000019b660000]
       java.lang.Thread.State: WAITING (on object monitor)
        at java.lang.Object.wait(Native Method)
        - waiting on <0x0000000167e82700> (a foo.Notifier)
        at java.lang.Object.wait(Object.java:503)
        at foo.Notifier.doWait(Notifier.java:11)
        - locked <0x0000000167e82700> (a foo.Notifier)
        at foo.Intrinsic.lock1(Intrinsic.java:11)
        - locked <0x0000000167e85c90> (a foo.Intrinsic)
        at foo.Main$1.run(Main.java:12)
        at java.lang.Thread.run(Thread.java:744)

The stacktrace reflects the blocking situation in the petri net. Thread 1 is stuck in the wait() method. It cannot proceed because it is not going to be notified. Thread 2 will never notifyAll() because Thread 1 already acquired the intrinsic lock.

Conclusion

Petri nets can make it clearer to understand a concrete deadlock situation. Due to their dynamic nature (you can animate the thing) they expose a deadlock situation and make it more visually obvious than just staring at different static blocks of code. Don't be tempted though to think they will solve all your concurrency issues. An important part of the Java thread model is missing in the presented model — that is the memory model and memory visibility. Furthermore graphical models also tend to quickly become bloated and hard to understand.

In systems software like Apache Lucene it might make sense to use low-level concurrency primitives. Here the presented petri nets can help to identify bugs for isolated use cases and report them upstream. But the traditional thread based model makes it difficult for developers to understand concurrent code especially in the context of an agile and fast-pacing environment, therefore there are attempts (with considerable success) to make programming parallel systems easier. Notable models on the horizon are CSP, actor based systems and reactive abstractions. We will cover these concurrency models in future articles.

In case you want to experiment and draw petri nets yourself, I recommend PIPE (Platform Independent Petri net Editor 2).

References:

[1] Peterson, James Lyle (1981). Petri Net Theory and the Modeling of Systems. Prentice Hall. ISBN 0-13-661983-5

threads, concurrency, petri, programming, java

?>