You Can't Spoil Java with a Thread: Part III - Interaction

A brief overview of the features of thread interaction. Previously, we looked at how threads synchronize with each other. This time we'll dive into the problems that can arise when threads interact and talk about how they can be avoided. We will also provide some useful links for deeper study.

Introduction

So, we know that there are threads in Java, which you can read about in the review “ Thread Can’t Spoil Java: Part I - Threads ” and that threads can be synchronized with each other, which we dealt with in the review “ Thread Can’t Spoil Java ” Spoil: Part II - Synchronization ." It's time to talk about how threads interact with each other. How do they share common resources? What problems could there be with this?

Deadlock

The worst 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 website 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();
    }
}

The deadlock here may not appear the first time, but if your program execution is stuck, it’s time to run jvisualvm: If a plugin is installed in JVisualVM (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 &lt33a78231> (a Deadlock$Friend) owned by "Thread-0" t@11

Thread 1 is waiting for a lock from thread 0. Why does this happen? 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. At the entrance to the method, we received a link to another Friend. Now, the thread Thread-1wants to execute a method on another Friend, thereby obtaining a lock from him 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 blocking is unsolvable, so it is Dead, that is, dead. Both a death grip (which cannot be released) and a dead block from which one cannot escape. On the topic of deadlock, you can watch the video: " Deadlock - Concurrency #1 - Advanced Java ".

Livelock

If there is a Deadlock, then is there a Livelock? Yes, there is) Livelock is that threads seem to be alive outwardly, but at the same time they cannot do anything, because... the condition under which they are trying to continue their work cannot be met. In essence, Livelock is similar to deadlock, but the threads do not “hang” on the system waiting for the monitor, but are always 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 it starts first Thead-1, 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. Moreover, they are not in deadlock, that is, visually everything is fine with them and they are doing their job. According to JVisualVM, we see the sleep periods and the park period (this is when a thread tries to occupy a lock, it goes into the park state, as we discussed earlier when talking about thread synchronization ). On the topic of livelock, you can see an example: " Java - Thread Livelock ".

Starvation

In addition to blocking (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 all the execution time, others cannot be executed:

https://www.logicbig.com/

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

Race Condition

When working with multithreading, there is such a thing as a "race condition". This phenomenon lies in the fact that threads share a certain 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 generate 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 being assigned, newValuesomething went wrong and newValuethere were more. Some of the threads in the race state managed to change valuebetween these two teams. As we can see, a race between threads has appeared. Now imagine how important it is not to make similar mistakes with money transactions... Examples and diagrams can also be found here: “ Code to simulate race condition in Java thread ”.

Volatile

Speaking about the interaction of threads, it is worth especially 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 with a high degree of probability it will not work. The new thread will not see the change flag. To fix this, flagyou need to specify a keyword for the field volatile. How and why? All actions are performed by the processor. But the calculation results need to be stored somewhere. For this purpose, there is main memory and a hardware cache on the processor. These processor caches are like a small piece of memory for accessing data faster than accessing main memory. But everything also has a downside: the data in the cache may not be current (as in the example above, when the flag value was not 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 this topic, volatileit is highly recommended to read the translation of " JSR 133 (Java Memory Model) FAQ ". I also advise you to read more about 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", we will see a hint in IntelliJ Idea: This inspection (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 is atomic. Unfortunately, increment is not an atomic operation, because an increment requires as many as three operations: get the old value, add one to it, and save the value. Why is atomicity important? In the increment example, if a race condition occurs, at any time the shared resource (i.e., the shared value) may 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 following 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 show us 30000, but valueit will change from time to time. There is a short overview on this topic " An Introduction to Atomic Variables in Java ". Atomic is 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 using the example of JDK 7 and 8 " or on Wikipedia in the article about " Comparison with exchange ".

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

Happens Before

There is an interesting and mysterious thing - Happens Before. Speaking about flows, it’s also worth reading 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: It’s probably better that this video doesn’t tell anything about it. So I'll just leave a link to the video. You can read " Java - Understanding Happens-before relationships ".

Results

In this review, we looked at the features of thread interaction. 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