Release Notes

Starvation

Starvation refers to a situation where a thread is unable to make any progress (or progressing very slowly) despite being in runnable state. Some of the common causes of starvation are :

• Other 'greedy' threads with higher priority are hogging CPU and thread scheduler isn't picking this thread for service as it has low priority

• A thread is waiting indefinitely to enter a block of code guarded by a mutex (e.g a synchronized block) because another thread is holding the lock and is executing a piece of code which is quite time consuming.

• A number of threads were waiting on an object. Now all of them got notified. But because its a synchronized block (wait-notify code construct can be used only inside a synchronized context), the threads can only be serviced one-at-a-time and for some reason, this thread is placed low in the pecking order by thread scheduler

The following code snippet demonstrates starvation:

First lets define our task - a Runnable implementation. In this case, the while loop will run for 2^63 times before it overflows and breaks the loop - just to ensure that CPU will actually be busy executing the thread

class StarvationDemo implements Runnable {
    final long start = System.currentTimeMillis();

    @Override
    public void run() {
        long threadstart = System.currentTimeMillis();
        long i = 0;
        while(i > 0) {
            i++;
        }
        long end = System.currentTimeMillis();
        if (Thread.currentThread().getName().contains("100")) {
            System.out.println(Thread.currentThread().getName() + " done executing , time taken(ms) : "+ (end - start)+ " execution time (ms) : "+ (end - threadstart));
        }

    }
}

Now lets have 2 sets of threads - high priority (priority=9) and low priority (priority=1). We'll start 10 threads named T1-T100 (T1 - T99 are high priority threads and T100 is a low priority thread) at the same time. All of them are in runnable state but because of lower priority, thread T100 will be starved until other threads are done

public static void main(String[] args) {                
    Runnable r = new StarvationDemo();
    for (int i=1; i<=100; i++) {
        Thread t = new Thread(r, "T"+i);
        if (i == 100) {
            t.setPriority(1);
        }
        else {
            t.setPriority(9);
        }
        t.start();
    }
}

Lets look the output:

T100 done executing , time taken(ms) : 23 execution time (ms) : 0

So thread T100 actually took less than a ms to execute but was done only after 23 ms since start.
This is because for first 23 ms T100 was starving as CPU was busy servicing other higher priority threads

DeadLock

Deadlock refers to an irrecoverable situation where two threads are dependent mutually on each other and hence none of them can proceed. In other words, lets say we have two threads T1 and T2 and two locks A and B. Deadlock refers to a situation where :

• T1 is holding lock on A and is waiting to acquire lock on B

• T2 is holding lock on B and is waiting to acquire lock on A

Clearly in this situation neither T1 nor T2 can make any progress as they are stuck forever waiting for each other.

In general, in order for a deadlock to occur, you must meet all of the four conditions :

• mutual exclusion : only one thread can access the resource at the same time

• hold-and-wait : threads already holding a resource can request for additional resources without giving up their current resources

• no-preemption : one thread cannot forcibly remove resource held by another thread

• circular-wait : two or more threads form a circular chain where each thread is waiting on another resource in the chain

One of the commonest reasons behind deadlock is two or more threads trying to acquire same set of locks in different order. If you are trying to acquire multiple nested locks, try to ensure that the locks are always acquired in the same order consistently.

For example, the following code snippet illustrates the problem :

First lets create a class with two synchronized methods internally invoking each other. Note that invoking m1() will result in the same thread acquiring two different locks (one on current object, another on the object passed as argument to method m1.

class Dummy {
    synchronized void m1 (Dummy other) {
        System.out.println(Thread.currentThread().getName()+ " : Executing m1");
        try {
            TimeUnit.SECONDS.sleep(1);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        other.m2();
    }

    synchronized void m2() {
        System.out.println(Thread.currentThread().getName()+ " : Executing m2");
    }
}

Now lets define our task which will execute the method m1:

class DeadlockDemo implements Runnable {
    Dummy a;
    Dummy b;

    public DeadlockDemo(Dummy a, Dummy b) {
        this.a = a;
        this.b = b;
    }

    @Override
    public void run() {
        a.m1(b);
    }
}

In order to simulate threads acquiring locks in different order, we will create two instances of Dummy - a and b and start two threads - one invoking a.m1(b) and other invoking b.m1(a).

public static void main(String[] args) {
    Dummy a = new Dummy();
    Dummy b = new Dummy();

    Runnable r1 = new DeadlockDemo(a, b);
    Runnable r2 = new DeadlockDemo(b, a);
    new Thread(r1).start();
    new Thread(r2).start();
}

The first thread acquires lock on a (and is waiting to acquire a lock on b) whereas the second thread holds lock on b and is waiting to acquire lock on a. The 1 second sleep is there to ensure that we don't have a situation where first thread completes methods m1() and m2() even before second thread acquires the first lock.

If we run this code, this will result in a deadlock - there is no way for the system to recover from this on its own without any external intervention.

Thread-1 : Executing m1
Thread-0 : Executing m1

What if a running application has stopped responding (probably because of a deadlock) ? How do you identify which threads are in a deadlock and which part of the code were they running ?

The easiest way is to take a thread dump and analyze the dump file. There are a lot of UI based tools available to analyze thread dumps - VisualVM and JProfiler are among the most popular ones. Both Visual VM and JProfiler can connect to a JVM running locally or on a remote host and take a thread dump

For example, if we start Visual VM and connect it to our Java process, it will automatically detect a deadlock and allow us to create a thread dump file at the click of a button

If we generate a thread dump and inspect it, it clearly tells us where a thread is blocked

From the screenshot we can conclude :
+ Thread-1 was blocked while trying to invoke Dummy.m2()
+ Thread-0 was blocked while trying to invoke Dummy.m2()
+ Thread-0 is waiting for monitor entry 0x00000000d801570
+ Thread-1 is waiting for monitor entry 0x00000000d801560
+ Thread-0 is holding lock on 0x00000000d801560
+ Thread-1 is holding lock on 0x00000000d801570

This essentially conforms to the classic definition of a deadlock.

Note that there might be more than two participating threads in a deadlock. However, the mechanism for detection remains the same irrespective of number of participating threads

Livelock

Livelock refers to a situation where two or more threads are so busy relinquishing CPU for each other that overall there is hardly any progress going on. A thread often acts in response to the action of another thread. If the other thread's action is also a response to the action of this thread, then we may have a livelock.

Unlike deadlock, threads are not blocked when livelock occurs. They are simply too busy responding to each other to resume work.

The following code snippet simulates this.
We have a resource shared between threads. At any point only one thread can own the resource. We also have two worker threads. Each thread checks if the other thread is active or not and if not active, then relinquishes resource to the other thread causing a livelock

class Resource {
    volatile Worker owner;

    public Resource(Worker owner) {
        this.owner = owner;
    }

    public Worker getOwner() {return this.owner;}

    public synchronized void setOwner(Worker owner) {
        this.owner = owner;
    }
}

class Worker extends Thread {
    volatile boolean active;
    final Resource resource;
    volatile Worker other;

    public Worker (Resource resource) {
        this.resource = resource;
        this.active = true;
    }

    public void doWork(Resource resource, Worker other) {
        while (active) {
            if (resource.getOwner() != this) {
                try {
                    TimeUnit.SECONDS.sleep(1);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                continue;
            }

            if (other.active) {
                System.out.println(Thread.currentThread().getName() + " Handing over to other worker");
                resource.setOwner(other);
                try {
                    TimeUnit.SECONDS.sleep(1);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                continue;
            }

            System.out.println(Thread.currentThread().getName() + " working on resource");
            active = false;
            resource.setOwner(other);
        }
    }

    @Override
    public void run() {
        doWork(resource, other);
    }
}

public static void main(String[] args) {
    Resource resource = new Resource(null);
    Worker w1 = new Worker(resource);
    Worker w2 = new Worker(resource);
    w1.other = w2;
    w2.other = w1;
    resource.owner = w1;
    w1.start();
    w2.start();
}

Output :

Thread-0 Handing over to other worker
Thread-1 Handing over to other worker
Thread-0 Handing over to other worker
Thread-1 Handing over to other worker
Thread-0 Handing over to other worker
Thread-1 Handing over to other worker
Thread-0 Handing over to other worker
Thread-1 Handing over to other worker
Thread-0 Handing over to other worker
Thread-1 Handing over to other worker
Thread-0 Handing over to other worker
Thread-1 Handing over to other worker
Thread-0 Handing over to other worker

Visual VM clearly shows that none of the two threads are blocked - they are both runnable but are too busy passing the buck to each other

Memory Inconsistency

Memory inconsistency refers to a situation where two threads end up having different views of what is essentially the same data. This is because Java memory model allows each thread to read/write from its local cache in the absence of a happens-before relationship and no matter how much time elapsed between 2 operations in 2 separate threads, if there isn't a happens-before relationship, there are absolutely no guarantees as to what each thread will see in the memory. So, writes by one thread to a variable are not guaranteed to be visible to reads by another thread from the same variable unless there's a happens-before relationship. We'll explore happens-before relationship in greater details when we cover Java Memory Model.

For example, lets take a look at the code snippet here :

public class Test {

    private static boolean ready;

    private static class ReaderThread extends Thread {

        public void run() {
            while (!ready) {
                Thread.yield();
            }
        }

        public static void main(String[] args) {
            new ReaderThread().start();
            ready = true;
        }
    }
}

There is a possibility that the code above can result in an infinite loop.

The main thread is setting the ready flag to true. However, there is nothing to enforce a happens-before guarantee here and there might be a possibility that write to the ready variable by the main thread isn't visible to the Reader thread reading the flag and hence the reader thread continues to run forever.

Non Atomic Operation and Thread interleaving

Let's consider a simple counter implementation :

class Counter {
    static int count;
    public void increment() {
        count++;
    }
    public int get() {
        return count;
    }
}

Note that the increment() method implementation looks like a single step implementation but is actually a multi-step operation. The count++ operation internally involves the following steps :

• read the current value of count from memory

• increment the value by 1

• write the new value into memory.

Now let's assume that the current value of count is 4. Two threads A and B are simultaneously executing increment(). This is what might happen :
Thread A reads current value of count as 4
Thread B reads current value of count as 4
Thread A performs 4+1
Thread B performs 4+1
Thread A writes 5 to memory
Thread B writes 5 to memory

Clearly we have a problem with 'lost updates' here. The value of count was initially 4 and two calls to increment() method should have resulted in current value of count as 6.

The following code illustrates this problem. We have count = 0 at initial state. 100 threads invoke increment() method 100,000 times each. Ideally at the end of the whole operation the value of count should have been 1,000,000 but isnt so.

public class Test {
    public static void main(String[] args) {
        Counter counter = new Counter();
        Runnable r = new Runnable() {
            @Override
            public void run() {
                for (int i=0; i<100_000; i++) {
                    counter.increment();
                }
            }
        };
        for (int i=0; i<100; i++) {
            new Thread(r).start();
        }
        System.out.println(counter.get());
    }
}

Output:

531497

So we've lost nearly half of the updates. In later sections we'll explore ways to solve this problem.