Livelock or a Deadlock?

Question

I'm preparing for Java SE 7 Programmer II exam. In one of the mock exams there was an exercise to name from what threading problem does the code suffer. This is the code:

public class Test {

    public static void main(String[] args) {
        final Counter obj1 = new Counter("obj1");
        final Counter obj2 = new Counter("obj2");

        new Thread(new Runnable() {
            @Override
            public void run() {
                Thread.currentThread().setName("first");
                obj1.display(obj2);
            }
        }).start();

        new Thread(new Runnable() {
            @Override
            public void run() {
                Thread.currentThread().setName("second");
                obj2.display(obj1);
            }
        }).start();
    }
}

class Counter extends Thread {
    int i = 10;
    String name;

    public Counter(String name) {
        this.name = name;
    }

    public synchronized void display(Counter obj) {
        try {
            Thread.sleep(5);
            obj.increment(this);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }

    public synchronized void increment(Counter obj) {
        System.out.println(++i);
    }
}

They say it is a livelock. I cannot see it. Please can someone explain it in more detail.

Answer 1

I wouldn't qualify this as livelock based on Wikipedia's definition

A livelock is similar to a deadlock, except that the states of the processes involved in the livelock constantly change with regard to one another, none progressing.

Though it does fit the definition of deadlock

In an operating system, a deadlock is a situation which occurs when a process or thread enters a waiting state because a resource requested is being held by another waiting process, which in turn is waiting for another resource. If a process is unable to change its state indefinitely because the resources requested by it are being used by another waiting process, then the system is said to be in a deadlock.

Your first thread has the lock for obj1, the second has the lock of obj2, they then requests the other's lock and block.

Answer 2

Here's how each thread works:

1. Obtain a lock on one object - happens in the run method of the thread because Counter.display is synchronized.
2. Call it's display method.
3. Obtain a lock on the other object - preparing to call the increment method of the other object because the increment method is synchronized.
4. Call the other increment and ask it to increment its own object - strange, but does not contribute to the deadlock.

Apart from the issue of not setting i volatile because it could be accessed in a multi-threaded fashion there are a number of lock-related problems here but the main one is:

The lock held in step 1 is not released before the lock is requested by stage 3. To me that is a potential deadlock because both threads will lock if they both pass stage 1 before the other hits 3. However, as it is possible for the two threads to actually work fine so long as they never hit that then it may be possible to interpret this as a livelock as the two threads can happily run together for some time before they eventually deadly embrace.

So I would call this potential deadlock and let the pedants decide what to call it.

Answer 3

After checking the thread states, I`m now sure that it is a deadlock!

I stored the threads in locals t1 and t2 in order to call the getState() method.

The System.out.println(t*.getState()) called right after starting the threads, prints: TIMED_WAITING.

The same in the display method AFTER the Thread.sleep(5), prints: RUNNABLE

And now the key part:

Calling System.out.println(t*.getState()) (for both threads t1 and t2) in main again but this time after a sleep(5000) will print BLOCKED.

Blocked means: waiting for acquiring lock, and that means it is a DEADLOCK!

Answer 4

Ran above program and got the thread dump
for first thread

"first@573" prio=5 tid=0xb nid=NA waiting for monitor entry
  java.lang.Thread.State: BLOCKED
     blocks second@575
     waiting for second@575 to release lock on <0x245> (a dp.Counter)
      at dp.Counter.increment(LiveLock.java:44)
      at dp.Counter.display(LiveLock.java:37)
      - locked <0x246> (a dp.Counter)
      at dp.LiveLock.lambda$main$0(LiveLock.java:15)
      at dp.LiveLock$$Lambda$1.16460856.run(Unknown Source:-1)
      at java.lang.Thread.run(Thread.java:745)

and for second thread

"second@575" prio=5 tid=0xc nid=NA waiting for monitor entry
  java.lang.Thread.State: BLOCKED
     blocks first@573
     waiting for first@573 to release lock on <0x246> (a dp.Counter)
      at dp.Counter.increment(LiveLock.java:44)
      at dp.Counter.display(LiveLock.java:37)
      - locked <0x245> (a dp.Counter)
      at dp.LiveLock.lambda$main$1(LiveLock.java:20)
      at dp.LiveLock$$Lambda$2.23661220.run(Unknown Source:-1)
      at java.lang.Thread.run(Thread.java:745)

looks like deadlock situation.