что такое livelock java

Java Thread Deadlock and Livelock

Last modified: July 2, 2021

Get started with Spring 5 and Spring Boot 2, through the Learn Spring course:

1. Overview

While multi-threading helps in improving an application’s performance, it also comes with some problems. In this tutorial, we’ll look into two such problems, deadlock and livelock, with the help of Java examples.

2. Deadlock

2.1. What Is Deadlock?

A deadlock occurs when two or more threads wait forever for a lock or resource held by another of the threads. Consequently, an application may stall or fail as the deadlocked threads cannot progress.

The classic dining philosophers problem nicely demonstrates the synchronization issues in a multi-threaded environment and is often used as an example of deadlock.

2.2. Deadlock Example

First, let’s take a look into a simple Java example to understand deadlock.

In this example, we’ll create two threads, T1 and T2. Thread T1 calls operation1, and thread T2 calls operations.

To complete their operations, thread T1 needs to acquire lock1 first and then lock2, whereas thread T2 needs to acquire lock2 first and then lock1. So, basically, both the threads are trying to acquire the locks in the opposite order.

Now, let’s write the DeadlockExample class:

Let’s now run this deadlock example and notice the output:

Once we run the program, we can see that the program results in a deadlock and never exits. The log shows that thread T1 is waiting for lock2, which is held by thread T2. Similarly, thread T2 is waiting for lock1, which is held by thread T1.

2.3. Avoiding Deadlock

Deadlock is a common concurrency problem in Java. Therefore, we should design a Java application to avoid any potential deadlock conditions.

To start with, we should avoid the need for acquiring multiple locks for a thread. However, if a thread does need multiple locks, we should make sure that each thread acquires the locks in the same order, to avoid any cyclic dependency in lock acquisition.

We can also use timed lock attempts, like the tryLock method in the Lock interface, to make sure that a thread does not block infinitely if it is unable to acquire a lock.

3. Livelock

3.1. What Is Livelock

Livelock is another concurrency problem and is similar to deadlock. In livelock, two or more threads keep on transferring states between one another instead of waiting infinitely as we saw in the deadlock example. Consequently, the threads are not able to perform their respective tasks.

A great example of livelock is a messaging system where, when an exception occurs, the message consumer rolls back the transaction and puts the message back to the head of the queue. Then the same message is repeatedly read from the queue, only to cause another exception and be put back on the queue. The consumer will never pick up any other message from the queue.

3.2. Livelock Example

Now, to demonstrate the livelock condition, we’ll take the same deadlock example we’ve discussed earlier. In this example also, thread T1 calls operation1 and thread T2 calls operation2. However, we’ll change the logic of these operations slightly.

Both threads need two locks to complete their work. Each thread acquires its first lock but finds that the second lock is not available. So, in order to let the other thread complete first, each thread releases its first lock and tries to acquire both the locks again.

Let’s demonstrate livelock with a LivelockExample class:

Now, let’s run this example:

As we can see in the logs, both the threads are repeatedly acquiring and releasing locks. Because of this, none of the threads are able to complete the operation.

3.3. Avoiding Livelock

To avoid a livelock, we need to look into the condition that is causing the livelock and then come up with a solution accordingly.

For example, if we have two threads that are repeatedly acquiring and releasing locks, resulting in livelock, we can design the code so that the threads retry acquiring the locks at random intervals. This will give the threads a fair chance to acquire the locks they need.

Another way to take care of the liveness problem in the messaging system example we’ve discussed earlier is to put failed messages in a separate queue for further processing instead of putting them back in the same queue again.

4. Conclusion

In this tutorial, we’ve discussed deadlock and livelock. Also, we’ve looked into Java examples to demonstrate each of these problems and briefly touched upon how we can avoid them.

As always, the complete code used in this example can be found over on GitHub.

Источник

19) Livelock

Что такое Livelock?

Из этого руководства по операционной системе вы узнаете:

Примеры Livelock

Самым простым примером Livelock могут быть два человека, которые встречаются лицом к лицу в коридоре, и оба они отодвигаются в сторону, чтобы пропустить другого. Они заканчивают тем, что двигались из стороны в сторону, не делая никакого прогресса, поскольку они двигаются тем же самым способом в то время. Здесь они никогда не пересекаются.

На приведенном выше изображении видно, что каждому из двух указанных процессов нужны два ресурса, и они используют примитивный входной регистр опроса, чтобы попытаться получить необходимые им блокировки. Если попытка не удалась, метод работает снова.

Предполагая, что процесс A запускается первым и получает ресурс данных X, а затем процесс B запускается и получает ресурс Y, независимо от того, какой процесс запускается первым, ни один из них не продвигается дальше.

Однако ни один из двух процессов не заблокирован. Они многократно расходуют ресурсы ЦП без какого-либо прогресса, но также останавливают любой блок обработки.

Следовательно, эта ситуация не является тупиковой, потому что нет ни одного заблокированного процесса, но мы сталкиваемся с ситуацией, эквивалентной взаимоблокировке, то есть LIVELOCK.

Что приводит к Livelock?

Livelock происходит, когда общее число разрешенных процессов в конкретной системе должно быть определено общим количеством записей в таблице процессов. Таким образом, слоты таблицы процессов следует называть конечными ресурсами.

Что такое тупик?

Взаимная блокировка — это ситуация, которая возникает в ОС, когда какой-либо процесс переходит в состояние ожидания, поскольку другой ожидающий процесс удерживает требуемый ресурс. Взаимная блокировка является распространенной проблемой в многопроцессорной обработке, когда несколько процессов совместно используют определенный тип взаимоисключающего ресурса, известного как программная блокировка или программное обеспечение.

Пример тупика

Что такое голод?

Голод — это ситуация, когда все процессы с низким приоритетом блокируются, а процессы с высоким приоритетом продолжаются. В любой системе запросы на ресурсы с высоким / низким приоритетом продолжают происходить динамически. Таким образом, требуется определенная политика, чтобы решить, кому и когда получить поддержку.

Используя некоторые алгоритмы, некоторые процессы могут не получить желаемое обслуживание, даже если они не заблокированы. Истощение происходит, когда некоторые потоки делают общие ресурсы недоступными в течение длительного периода времени.

Пример голодания:

Например, объект предлагает синхронизированный метод, который может занять много времени для возврата. Если один поток часто использует этот метод, другие потоки, которым также требуется частый синхронизированный доступ к одному и тому же объекту, часто блокируются.

Источник

Многопоточность в Java. Лекция 6: взаимные блокировки и дампы потоков

В пятой лекции краткого курса о многопоточности речь шла об атомарных переменных и многопоточных коллекциях. На этот раз наши коллеги рассказывают о дампах потоков, простых и скрытых дедлоках.

В некорректно спроектированной многопоточной программе может возникнуть ситуация, когда два потока блокируют друг друга. В этом случае их выполнение зависает, пока программу не остановят извне. Такая ситуация называется deadlock.

6.1 Дампы потоков

Помимо дедлоков, бывает, что поток очень долго ожидает какие-то ресурсы или остается постоянно активным, например, выполняя очень большой или бесконечный цикл. Для выявления таких ситуаций и других проблем, связанных с потоками, JVM предоставляет возможность сделать мгновенный снимок состояния потоков. Такой снимок называется thread dump. Он представляет собой текстовый документ, в котором перечислены все потоки, в том числе, потоки JVM. Для каждого потока отображается стандартный набор информации: имя, статус, приоритет, стек-трейс, демон ли поток или нет, а также адрес объекта блокировки, на которой находится поток. Часть такого thread dump приведена в листинге 1.

Листинг 1

«Java Thread» #11 prio=5 os_prio=0 tid=0x00007fb0a4356000 nid=0x1242 waiting for monitor entry [0x00007fb078701000] java.lang.Thread.State: BLOCKED (on object monitor)
at com.da.lect5.deadlock.TwoTasks.lambda$getTask1$0(TwoTasks.java:14)
— waiting to lock (a java.lang.String)
— locked (a java.lang.String)
at com.da.lect5.deadlock.TwoTasks$$Lambda$1/1078694789.run(Unknown
Source)
at java.lang.Thread.run(Thread.java:748)

«UNIX Thread» #12 prio=5 os_prio=0 tid=0x00007fb0a4357800 nid=0x1243 waiting for monitor entry [0x00007fb078600000] java.lang.Thread.State: BLOCKED (on object monitor)
at com.da.lect5.deadlock.TwoTasks.lambda$getTask2$1(TwoTasks.java:27)
— waiting to lock (a java.lang.String)
— locked (a java.lang.String)
at com.da.lect5.deadlock.TwoTasks$$Lambda$2/1747585824.run(Unknown
Source)
at java.lang.Thread.run(Thread.java:748)

«Monitor Ctrl-Break» #5 daemon prio=5 os_prio=0 tid=0x00007fb0a42b5800 nid=0x123b runnable [0x00007fb07901f000] java.lang.Thread.State: RUNNABLE
at java.net.SocketInputStream.socketRead0(Native Method)
at java.net.SocketInputStream.socketRead(SocketInputStream.java:116)
at java.net.SocketInputStream.read(SocketInputStream.java:171)
at java.net.SocketInputStream.read(SocketInputStream.java:141)
at sun.nio.cs.StreamDecoder.readBytes(StreamDecoder.java:284)
at sun.nio.cs.StreamDecoder.implRead(StreamDecoder.java:326)
at sun.nio.cs.StreamDecoder.read(StreamDecoder.java:178)
— locked (a java.io.InputStreamReader)
at java.io.InputStreamReader.read(InputStreamReader.java:184)
at java.io.BufferedReader.fill(BufferedReader.java:161)
at java.io.BufferedReader.readLine(BufferedReader.java:324)
— locked (a java.io.InputStreamReader)
at java.io.BufferedReader.readLine(BufferedReader.java:389)
at com.intellij.rt.execution.application.AppMainV2$1.run(AppMainV2.java:64)

Существует несколько способов снять thread dump:

В листинге 1 можно увидеть, что поток с именем Java Thread заблокирован на мониторе с адресом 0x0000000719bf5760. Важно правильно сопоставить адрес объекта с самим объектом, потому что по шестнадцатеричному значению сделать это невозможно. Для этого можно использовать код, приведенный в листинге 2.

Листинг 2:

Используя класс в листинге 2, можно понять, какой поток на какой блокировке находится. При использовании этого класса следует учесть, что адреса объектов могут меняться после работы сборщика мусора. При анализе потоков необходимо фильтровать потоки, которые создал пользователь, и те, которые запустила сама JVM. Поэтому удобно назначать имена потокам, как это было показано в лекции номер 2. Рекомендуется делать дампы потоков работающего приложения несколько раз, чтоб увидеть изменения состояния потоков. Если одно из ядер процессора загружено на 100 %, следует искать бесконечный цикл или цикл, который очень долго выполняется, обрабатывая большое количество данных. Если предельной загрузки процессора не наблюдается, но какая-то работа все же ожидает выполнения, значит, возник один из видов дедлока или потоки ждут освобождения определенного ресурса.

6.2 Простая взаимная блокировка

Простой дедлок возникает, когда из двух потоков первый захватил блокировку А и пытается захватить блокировку B, а второй захватил блокировку B и пытается захватить блокировку A. Пример такого дедлока приведен в листинге 3.

Листинг 3:

public class DeadLock <
public static void main(String[] args) <
TwoTasks tasks = new TwoTasks();
new Thread(tasks.getTask1(), «Java Thread»).start();
new Thread(tasks.getTask2(), «UNIX Thread»).start();
>
>

В листинге 1 создаются два потока: первый сначала захватывает блокировку на строке str1, а затем — на str2. Второй поток делает то же самое, только в другом порядке. Два потока пытаются захватить блокировки бесконечное количество раз. Рано или поздно наступит дедлок: когда первый поток захватил блокировку на строке “Java” и хочет захватить блокировку на строке “UNIX”. А второй поток уже захватил блокировку на строке “UNIX” и пытается захватить блокировку на строке “Java”. В результате программа в Листинге 1 будет находиться в состоянии взаимной блокировки вечно — т. е. до тех пор пока ее не остановят. Решение в сложившейся ситуации — использовать один и тот же порядок захвата и отпускания блокировок во всех критических секциях программы.

Не стоит использовать в качестве объектов блокировки строки. Это связано с тем, что JVM кэширует строки, объявленные при помощи литералов. Соответственно, строки с одинаковым содержанием будут ссылаться на один и тот же объект, хотя могут быть объявлены в разных частях программы.

6.3 Скрытый дедлок

В разделе 6.1 был рассмотрен случай взаимной блокировки, который виртуальная Java-машина смогла определить, что и было показано в thread dump. Однако могут возникать ситуации, когда Java-машина определить дедлок не может. Рассмотрим такую программу в листинге 4.

Листинг 4:

public class LockOrderingDeadlockSimulator <
public static void main(String[] args) <
CountDownLatch startSignal = new CountDownLatch(1);
CountDownLatch endSignal = new CountDownLatch(3);

TasksHolder tasks = new TasksHolder();
ExecutorService executor = Executors.newFixedThreadPool(3);

executor.execute(new WorkerThread1(tasks, startSignal, endSignal));
executor.execute(new WorkerThread2(tasks, startSignal, endSignal));
Runnable deadlockDetector =
new ThreadDeadlockDetector(tasks, startSignal, endSignal);
executor.execute(deadlockDetector);
executor.shutdown();

while (!executor.isTerminated()) <
try <
endSignal.await();
> catch (InterruptedException e) <
>
>

public class TasksHolder <
private final Object SHARED_OBJECT = new Object();
private final ReentrantReadWriteLock lock = new ReentrantReadWriteLock();
public void executeTask1() <
// 1. Attempt to acquire a ReentrantReadWriteLock READ lock
lock.readLock().lock();
// Wait 2 seconds to simulate some work.
try <
Thread.sleep(2000);
> catch (InterruptedException any) <
>
try <
// 2. Attempt to acquire a Flat lock.
synchronized (SHARED_OBJECT) <
>
> finally <
lock.readLock().unlock();
>
System.out.println(«executeTask1() :: Work Done!»);
>

public void executeTask2() <
// 1. Attempt to acquire a Flat lock
synchronized (SHARED_OBJECT) <
// Wait 2 seconds to simulate some work.
try <
Thread.sleep(2000);
> catch (InterruptedException any) <
>
// 2. Attempt to acquire a ReentrantReadWriteLock WRITE lock
lock.writeLock().lock();
try <
// Do nothing
> finally <
lock.writeLock().unlock();
>
>
System.out.println(«executeTask2() :: Work Done!»);
>
public ReentrantReadWriteLock getReentrantReadWriteLock() <
return lock;
>
>

public class WorkerThread1 implements Runnable <
private final CountDownLatch startSignal;
private final CountDownLatch endSignal;
private TasksHolder tasks;
public WorkerThread1(TasksHolder tasks, CountDownLatch startSignal,
CountDownLatch endSignal) <
this.tasks = tasks;
this.startSignal = startSignal;
this.endSignal = endSignal;
>
@Override
public void run() <
try <
startSignal.await();
// Execute task #1
tasks.executeTask1();
> catch (InterruptedException e) <
> finally <
endSignal.countDown();
>
>
>

public class WorkerThread2 implements Runnable <
private final CountDownLatch startSignal;
private final CountDownLatch endSignal;
private TasksHolder tasks;
public WorkerThread2(TasksHolder tasks, CountDownLatch startSignal,
CountDownLatch endSignal) <
this.tasks = tasks;
this.startSignal = startSignal;
this.endSignal = endSignal;
>
@Override
public void run() <
try <
startSignal.await();

// Execute task #2
tasks.executeTask2();
> catch (InterruptedException e) <
> finally <
endSignal.countDown();
>
>
>

public class CommonResource <
private Worker owner;
public CommonResource (Worker d) <
owner = d;
>
public Worker getOwner () <
return owner;
>
public synchronized void setOwner (Worker d) <
owner = d;
>
>

public class Worker <
private String name;
private boolean active;
private final Object LOCK = new Object();

public Worker (String name, boolean active) <
this.name = name;
this.active = active;
>

public String getName () <
return name;
>

public boolean isActive () <
return active;
>

Источник

Deadlocks, Livelocks и Starvation

Продолжаем серию статей о проблемах многопоточности, параллелизме, concurrency и других интересных штуках.

В 1965 году Эдсгер Дейкстра сформулировал задачу об обедающих философах. Задача была иллюстрацией проблем синхронизации при разработке параллельных алгоритмов и техник решения этих проблем.

В задачи были рассмотренный такие проблема, как deadlock, livelock, resource starvation.

Саму задачу и возможные решения можно посмотреть на wiki.

А мы рассмотрим проблемы синхронизации в контексте современных языков программирования.

Deadlock

Что такое deadlock и как избежать таких ошибок?

Deadlock или взаимная блокировка — это ошибка, которая происходит когда процессы имеют циклическую зависимость от пары синхронизированных объектов.

Deadlock — это программа, в которой все параллельные процессы ожидают друг друга. В этом состоянии программа никогда не восстановится без вмешательства извне.

Пример

fatal error: all goroutines are asleep — deadlock!

Отладка взаимных блокировок, как и других ошибок синхронизации, усложняется тем, что для их возникновения нужны специфические условия одновременного выполнения нескольких процессов. Если бы Процесс 1 успел захватить ресурс B до Процесса 2, то ошибка не произошла бы.

Но все не так плохо, оказывается, есть несколько условий, которые должны присутствовать для возникновения взаимных блокировок, и в 1971 году Эдгар Коффман перечислил эти условия в своей статье System Deadlocks. Условия теперь известны как условия Кофмана и являются основой для методов, которые помогают обнаруживать, предотвращать и исправлять взаимные блокировки.

Условия Коффмана

Указанные условия являются необходимыми. То есть, если хоть одно из них не выполняется, то взаимных блокировок никогда не возникнет. Достаточность не имеет места быть: если выполняются все четыре условия, блокировка может и не произойти, например, если в системе нет процессов, претендующих на одновременное использование одних и тех же ресурсов.

Диаграммы Холта (Holt).

Отслеживать возникновение взаимных блокировок удобно на диаграммах Холта (Holt). Диаграмма Холта представляет собой направленный граф, имеющий два типа узлов: процессы (показываются кружочками) и ресурсы (показываются квадратиками). Тот факт, что ресурс получен процессом и в данный момент занят этим процессом, указывается ребром (стрелкой) от ресурса к процессу. Ребро, направленное от процесса, к ресурсу, означает, что процесс в данный момент блокирован и находится в состоянии ожидания доступа к соответствующему ресурсу.

Критерий deadlock.

Livelock

Livelock— это программы, которые активно выполняют параллельные операции, но эти операции никак не влияют на продвижение состояния программы вперед.

Ситуация, в которой два или более процессов непрерывно изменяют свои состояния в ответ на изменения в других процессах без какой-либо полезной работы. Это похоже на deadlock, но разница в том, что процессы становятся “ вежливыми” и позволяют другим делать свою работу.

Выполнение алгоритмов поиска удаления взаимных блокировок может привести к livelock — взаимная блокировка образуется, сбрасывается, снова образуется, снова сбрасывается и так далее.

Жизненный пример такой ситуации:

Двое встречаются лицом к лицу. Каждый из них пытается посторониться, но они не расходятся, а несколько секунд сдвигаются в одну и ту же сторону.

Вы делаете телефонный звонок, но человек на другом конце тоже пытается вам позвонить. Вы оба повесите трубку и попробуйте снова через одно и то же время, что снова создаст такую же ситуацию. Это может продолжаться вечность.

Рассмотрим простой пример livelock, где муж и жена пытаются поужинать, но между ними только одна ложка. Каждый из супругов слишком вежлив, и передает ложку, если другой еще не ел.

Ложка у которой есть хозяин:

Процесс обеда. Ложка и партнер:

Обедаем пока не утолим голод( isHungry=false ).

Поесть этим милым людям не суждено. До третьего блока выполнение не дойдет.

На мой взгляд, обнаружить livelock труднее, чем deadlock, просто потому, что может показаться, что программа работает. Она может реагировать на сигналы, потреблять ресурсы и как то менять состояния, но выйти из цикла и завершить работу уже не в состоянии.

Livelock— это подмножество более широкого набора проблем, называемых Starvation.

Starvation

Starvation — это любая ситуация, когда параллельный процесс не может получить все ресурсы, необходимые для выполнения его работы.

При livelock все параллельные процессы одинаково “голодают”, и никакая работа не выполняется до конца.

В более широком смысле starvation обычно подразумевает наличие одного или нескольких параллельных процессов, которые несправедливо мешают одному или нескольким другим параллельным процессам выполнять работу настолько эффективно, насколько это возможно.

Пример

У нас будет два работника. Один жадный( greedyWorker ), другой вежливый( politeWorker ). Обоим дается одинаковое кол-во времени на их полезную работу — спать по 3 наносекунде.

greedyWorker жадно удерживает общий ресурс( sharedLock ) на протяжении всего цикла работы, тогда как politeWorker пытается блокировать его только тогда, когда это необходимо.

Результат их работы:

За одно и то же время, жадный работник получил почти вдвое больше возможностей выполнять свою работу и владеть общим ресурсом.

Конечно, lock\unlock медленные и в данном примере у politeWorker очень неэффективный код, но голодания может также применяться к процессору, памяти, файловым дескрипторам, соединениям с бд, к любому ресурсу, который должен использоваться совместно.

Если у вас есть параллельный процесс, который настолько жаден, что препятствует эффективно работать другим параллельным процессам, то у вас большая проблема.

Источник