You Can't Screw Java with Threads: Part III - Interaction

A brief overview of the features of the interaction of threads. Earlier, we discussed how threads are synchronized with each other. This time, we will dive into the problems that can arise when threads interact and talk about how they can be avoided. We also provide some useful links for a deeper study.

Introduction

So, we know that there are threads in Java, which can be read in the review " Java threads do not mess up: Part I - threads " and that threads can be synchronized with each other, which we dealt with in the review " Java threads do not Mess Up: Part II - Synchronization ". It's time to talk about how threads interact with each other. How do they share common resources? What problems can there be with this?

Deadlock

The most terrible problem is Deadlock. When two or more threads wait forever for each other, this is called Deadlock. Let's take an example from the Oracle site from the description of the concept of " 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 has bowed to me!%n",
                    this.name, bower.getName());
            bower.bowBack(this);
        }
        public synchronized void bowBack(Friend bower) {
            System.out.format("%s: %s has 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 here may not appear the first time, but if your program execution hangs, it's time to run it jvisualvm: If a plugin is installed in JVisualVM (via Tools -> Plugins), we can see where the deadlock happened:

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

Thread 1 is waiting for a lock from thread 0. Why is this happening? Thread-1starts execution and executes the method Friend#bow. It is marked with the keyword synchronized, that is, we pick up the monitor by this. We received a link to another Friend. Now, the thread Thread-1wants to execute a method on another Friend, thereby obtaining a lock on it as well. But if another thread (in this case Thread-0) managed to enter the method bow, then the lock is already busy and Thread-1waiting Thread-0, and vice versa. The lock is unresolvable, so it is Dead, that is, dead. Both a dead grip (which cannot be released), and a dead lock from which there is no way out. On the topic of deadlock, you can watch the video: " Deadlock - Concurrency #1 - Advanced Java ".

livelock

If there is Deadlock, is there Livelock? Yes, there is) Livelock means that the threads seem to live externally, but at the same time they cannot do anything, because the conditions under which they are trying to continue their work cannot be fulfilled. In fact, Livelock is similar to deadlock, but the threads do not "hang" on the system wait for the monitor, but do something forever. 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 it starts first Thead-1, then we will 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 can be seen from the example, both threads alternately try to capture both locks, but they fail. At the same time, they are not in deadlock, that is, visually everything is fine with them and they are doing their job. According to JVisualVM, we see sleep periods and a park period (this is when a thread tries to take a lock, it goes into the park state, as we discussed earlier, talking about thread synchronization ). On the topic of livelock, you can see an example: " Java - Thread Livelock ".

starvation

In addition to locks (deadlock and livelock), there is another problem when working with multithreading - Starvation, or "starvation". This phenomenon differs from blocking in that the threads are not blocked, but they simply do not have enough resources for everyone. Therefore, while some threads take over the entire execution time, others cannot be executed:

https://www.logicbig.com/

A super example can be seen here: " Java - Thread Starvation and Fairness ". This example shows how threads work during Starvation and how one small change from Thread.sleep to Thread.wait allows you to distribute the load evenly.

Race Condition

When working with multithreading, there is such a thing as a "race condition". This phenomenon consists in the fact that threads share some resource among themselves and the code is written in such a way that it does not provide for correct operation in this case. Let's 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 give an error the first time. And it might 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, while it was assigned, newValuesomething went wrong, and newValuethere were more. Some of the threads in the race condition managed to change valuebetween these two commands. As we can see, there is a race between threads. Now imagine how important it is not to make similar mistakes with monetary transactions... You can also see examples and diagrams here: " Code to simulate race condition in Java thread ".

Volatile

Speaking about the interaction of threads, it is worth noting the keyword volatile. 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;
    }
}

The most interesting thing is that he most likely will not work. The new thread will not see the change flag. To fix this, flagyou need to specify the keyword for the field volatile. How and why? All actions are performed by the processor. But the results of calculations need to be stored somewhere. To do this, there is a main memory and there is a hardware cache in the processor. These processor caches are a kind of small piece of memory for faster data access than main memory accesses. But everything has a minus: the data in the cache may not be up to date (as in the example above, when the flag value has not been updated). So, the keyword volatiletells the JVM that we don't want to cache our variable. This allows you to see the actual result in all threads. This is a very simplified formulation. On the topicvolatileA highly recommended reading is the translation of the " JSR 133 (Java Memory Model) FAQ ". For more details, I also advise you to familiarize yourself with the materials " Java Memory Model " and " Java Volatile Keyword ". In addition, it is important to remember that volatilethis is about visibility, and not about the atomicity of changes. If we take the code from "Race Condition", then we will see a hint in IntelliJ Idea: This check (Inspection) was added to IntelliJ Idea as part of issue IDEA-61117 , which is listed in the Release Notes back in 2010.

Atomicity

Atomic operations are operations that cannot be separated. For example, the operation of assigning a value to a variable is atomic. Unfortunately, increment is not an atomic operation, as the increment requires as many as three operations: get the old value, add one to it, save the value. Why is atomicity important? In the increment example, if a race condition occurs, at any time the share (i.e. the total value) can suddenly change. In addition, it is important that 64-bit structures are also not atomic, for example, longand double. You can read more here: " Ensure atomicity when reading and writing 64-bit values ​​". An example of problems with atomicity can be seen in the 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());
    }
}

A special class for working with atomic Integerwill always display 30000 for us, but valueit will change from time to time. There is a short overview on this subject " An Introduction to Atomic Variables in Java ". Atomics are based on the "Compare-and-Swap" algorithm. You can read more about it in the article on Habré " Comparison of Lock-free algorithms - CAS and FAA on the example of JDK 7 and 8 " or on Wikipedia in the article about " Comparison with the exchange ".

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

Happens Before

There is an interesting and mysterious thing - Happens Before. Talking about flows, you should also read about it. The Happens Before relation indicates the order in which actions between threads will be seen. There are many interpretations and interpretations. One of the most recent reports on this topic is this report: Probably better than this video does not tell anything about it. Therefore, I will just leave a link to the video. You can read " Java - Understanding Happens-before relationship ".

Results

In this review, we looked at the features of the interaction of threads. We discussed problems that may arise and ways to detect and eliminate them. List of additional materials on the topic:

• Once again about double-checked locking
• JSR 133 (Java Memory Model) FAQ (translation)
• Advanced Java - Concurrency (Yuri Tkach)
• Concurrency Concepts in Java by Douglas Hawkins (2017)

#Viacheslav