Better together: Java and the Thread class. Part III — Interaction

A brief overview of the particulars of how threads interact. Previously, we looked at how threads are synchronized with one another. This time we will dive into the problems that may arise as threads interact, and we'll talk about how to avoid them. We will also provide some useful links for more in-depth study.

Introduction

So, we know that Java has threads. You can read about that in the review entitled Better together: Java and the Thread class. Part I — Threads of execution. And we explored the fact that threads can synchronize with one another in the review entitled Better together: Java and the Thread class. Part II — Synchronization. It's time to talk about how threads interact with one another. How do they share shared resources? What problems might arise here?

Deadlock

The scariest problem of all is deadlock. Deadlock is when two or more threads are eternally waiting for the other. We'll take an example from the Oracle webpage that describes deadlock:

public class Deadlock {
    static class Friend {
        private final String name;
        public Friend(String name) {
            this.name = name;
        }
        public String getName() {
            return this.name;
        }
        public synchronized void bow(Friend bower) {
            System.out.format("%s: %s bowed to me!%n",
                    this.name, bower.getName());
            bower.bowBack(this);
        }
        public synchronized void bowBack(Friend bower) {
            System.out.format("%s: %s bowed back to me!%n",
                    this.name, bower.getName());
        }
    }

    public static void main(String[] args) {
        final Friend alphonse = new Friend("Alphonse");
        final Friend gaston = new Friend("Gaston");
        new Thread(() -> alphonse.bow(gaston)).start();
        new Thread(() -> gaston.bow(alphonse)).start();
    }
}

Deadlock may not occur here the first time, but if your program does hang, then it's time to run jvisualvm: With a JVisualVM plugin installed (via Tools -> Plugins), we can see where the deadlock occurred:

"Thread-1" - Thread t@12
   java.lang.Thread.State: BLOCKED
	at Deadlock$Friend.bowBack(Deadlock.java:16)
	- waiting to lock <33a78231> (a Deadlock$Friend) owned by "Thread-0" t@11

Thread 1 is waiting for the lock from thread 0. Why does that happen? Thread-1 starts running and executes the Friend#bow method. It is marked with the synchronized keyword, which means we are acquiring the monitor for this (the current object). The method's input was a reference to the other Friend object. Now, Thread-1 wants to execute the method on the other Friend, and must acquire its lock to do so. But if the other thread (in this case Thread-0) managed to enter the bow() method, then the lock has already been acquired and Thread-1 waits for Thread-0, and vice versa. This is impasse is unsolvable, and we call it deadlock. Like a death grip that cannot be released, deadlock is mutual blocking that cannot be broken. For another explanation of deadlock, you can watch this video: Deadlock and Livelock Explained.

Livelock

If there's deadlock, is there also livelock? Yes, there is :) Livelock happens when threads outwardly seem to be alive, but they are unable to do anything, because the condition(s) required for them to continue their work cannot be fulfilled. Basically, livelock is similar to deadlock, but the threads don't "hang" waiting for a monitor. Instead, they are forever doing something. For example:

import java.util.concurrent.TimeUnit;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

public class App {
    public static final String ANSI_BLUE = "\u001B[34m";
    public static final String ANSI_PURPLE = "\u001B[35m";

    public static void log(String text) {
        String name = Thread.currentThread().getName(); // Like "Thread-1" or "Thread-0"
        String color = ANSI_BLUE;
        int val = Integer.valueOf(name.substring(name.lastIndexOf("-") + 1)) + 1;
        if (val != 0) {
            color = ANSI_PURPLE;
        }
        System.out.println(color + name + ": " + text + color);
        try {
            System.out.println(color + name + ": wait for " + val + " sec" + color);
            Thread.currentThread().sleep(val * 1000);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }

    public static void main(String[] args) {
        Lock first = new ReentrantLock();
        Lock second = new ReentrantLock();

        Runnable locker = () -> {
            boolean firstLocked = false;
            boolean secondLocked = false;
            try {
                while (!firstLocked || !secondLocked) {
                    firstLocked = first.tryLock(100, TimeUnit.MILLISECONDS);
                    log("First Locked: " + firstLocked);
                    secondLocked = second.tryLock(100, TimeUnit.MILLISECONDS);
                    log("Second Locked: " + secondLocked);
                }
                first.unlock();
                second.unlock();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        };

        new Thread(locker).start();
        new Thread(locker).start();
    }
}

The success of this code depends on the order in which the Java thread scheduler starts the threads. If Thead-1 starts first, then we get livelock:

Thread-1: First Locked: true
Thread-1: wait for 2 sec
Thread-0: First Locked: false
Thread-0: wait for 1 sec
Thread-0: Second Locked: true
Thread-0: wait for 1 sec
Thread-1: Second Locked: false
Thread-1: wait for 2 sec
Thread-0: First Locked: false
Thread-0: wait for 1 sec
...

As you can see from the example, both threads try to acquire both locks in turn, but they fail. But, they are not in deadlock. Outwardly, everything is fine and they are doing their job. According to JVisualVM, we see periods of sleep and a period of park (this is when a thread tries to acquire a lock — it enters the park state, as we discussed earlier when we talked about thread synchronization). You can see an example of livelock here: Java - Thread Livelock.

Starvation

In addition to deadlock and livelock, there is another problem that can happen during multithreading: starvation. This phenomenon differs from the previous forms of blocking in that the threads are not blocked — they simply don't have sufficient resources. As a result, while some threads take all the execution time, others are unable to run:

https://www.logicbig.com/

You can see a super example here: Java - Thread Starvation and Fairness. This example shows what happens with threads during starvation and how one small change from Thread.sleep() to Thread.wait() lets you distribute the load evenly.

Race conditions

In multithreading, there is such a thing as a "race condition". This phenomenon happens when threads share a resource, but the code is written in a way that it doesn't ensure correct sharing. Take a look at an example:

public class App {
    public static int value = 0;

    public static void main(String[] args) {
        Runnable task = () -> {
            for (int i = 0; i < 10000; i++) {
                int oldValue = value;
                int newValue = ++value;
                if (oldValue + 1 != newValue) {
                    throw new IllegalStateException(oldValue + " + 1 = " + newValue);
                }
            }
        };
        new Thread(task).start();
        new Thread(task).start();
        new Thread(task).start();
    }
}

This code may not generate an error the first time. When it does, it may look like this:

Exception in thread "Thread-1" java.lang.IllegalStateException: 7899 + 1 = 7901
	at App.lambda$main$0(App.java:13)
	at java.lang.Thread.run(Thread.java:745)

As you can see, something went wrong while newValue was being assigned a value. newValue is too big. Because of the race condition, one of the threads managed to change the variable's value between the two statements. It turns out that there is a race between the threads. Now think of how important it is to not make similar mistakes with monetary transactions... Examples and diagrams can also be seen here: Code to simulate race condition in Java thread.

Volatile

Speaking about the interaction of threads, the volatile keyword is worth mentioning. Let's look at a simple example:

public class App {
    public static boolean flag = false;

    public static void main(String[] args) throws InterruptedException {
        Runnable whileFlagFalse = () -> {
            while(!flag) {
            }
            System.out.println("Flag is now TRUE");
        };

        new Thread(whileFlagFalse).start();
        Thread.sleep(1000);
        flag = true;
    }
}

Most interestingly, this is highly likely to not work. The new thread won't see the change in the flag field. To fix this for the flag field, we need to use the volatile keyword. How and why? The processor performs all the actions. But the results of calculations must be stored somewhere. For this, there is main memory and there is the processor's cache. A processor's caches are like a small chunk of memory used to access data more quickly than when accessing main memory. But everything has a downside: the data in the cache may not be up-to-date (as in the example above, when the value of the flag field was not updated). So, the volatile keyword tells the JVM that we don't want to cache our variable. This allows the up-to-date result to be seen on all threads. This is a highly simplified explanation. As for the volatile keyword, I highly recommend that you read this article. For more information, I also advise you to read Java Memory Model and Java Volatile Keyword. Additionally, it is important to remember that volatile is about the visibility, and not about the atomicity of changes. Looking at the code in the "Race conditions" section, we will see a tooltip in IntelliJ IDEA: This inspection was added to IntelliJ IDEA as part of issue IDEA-61117, which was listed in the Release Notes back in 2010.

Atomicity

Atomic operations are operations that cannot be divided. For example, the operation of assigning a value to a variable must be atomic. Unfortunately, the increment operation is not atomic, because increment requires as many as three CPU operations: get the old value, add one to it, then save the value. Why is atomicity important? With the increment operation, if there is a race condition, then the shared resource (i.e. the shared value) may suddenly change at any time. Additionally, operations involving 64-bit structures, for example long and double, are not atomic. More details can be read here: Ensure atomicity when reading and writing 64-bit values. Problems related to atomicity can be seen in this example:

public class App {
    public static int value = 0;
    public static AtomicInteger atomic = new AtomicInteger(0);

    public static void main(String[] args) throws InterruptedException {
        Runnable task = () -> {
            for (int i = 0; i < 10000; i++) {
                value++;
                atomic.incrementAndGet();
            }
        };
        for (int i = 0; i < 3; i++) {
            new Thread(task).start();
        }
        Thread.sleep(300);
        System.out.println(value);
        System.out.println(atomic.get());
    }
}

The special AtomicInteger class will always give us 30,000, but the value will change from time to time. There is a short overview of this topic: Introduction to Atomic Variables in Java. The "compare-and-swap" algorithm lies at the heart of atomic classes. You can read more about it here in Comparison of lock-free algorithms - CAS and FAA on the example of JDK 7 and 8 or in the Compare-and-swap article on Wikipedia.

http://jeremymanson.blogspot.com/2008/11/what-volatile-means-in-java.html

Happens-before

There is an interesting and mysterious concept called "happens before". As part of your study of threads, you should read about it. The happens-before relationship shows the order in which actions between threads will be seen. There are many interpretations and commentaries. Here's one of the most recent presentations on this subject: Java "Happens-Before" Relationships.

Summary

In this review, we've explored some of the specifics of how threads interact. We discussed problems that may arise, as well as ways to identify and eliminate them. List of additional materials on the topic:

• Double-checked locking
• JSR 133 (Java Memory Model) FAQ
• IQ 35: How to prevent a deadlock?
• Concurrency Concepts in Java by Douglas Hawkins (2017)

Better together: Java and the Thread class. Part I — Threads of execution Better together: Java and the Thread class. Part II — Synchronization Better together: Java and the Thread class. Part IV — Callable, Future, and friends Better together: Java and the Thread class. Part V — Executor, ThreadPool, Fork/Join Better together: Java and the Thread class. Part VI — Fire away!