Что такое livelock java
Разбор основных концепций параллелизма
Завтра у нас плавненько стартует практически юбилейный поток курс «Разработчик Java» — уже шестой по счёту начиная с апреля прошлого года. А это значит, что мы снова подобрали, перевели интереснейший материал, которым делимся с вами.
Эта памятка поможет Java-разработчикам, работающим с многопоточными программами, понять основные концепции параллелизма и способы их применения. Вы ознакомьтесь с ключевыми аспектами языка Java со ссылками на стандартную библиотеку.
С момента своего создания Java поддерживает ключевые концепции параллелизма, такие как потоки и блокировки. Эта памятка поможет Java-разработчикам, работающим с многопоточными программами, понять основные концепции параллелизма и способы их применения.
| Концепция | Описание |
|---|---|
| Атомарная операция — это операция, которая выполняется полностью или не выполняется совсем, частичное выполнение невозможно. | |
| Visibility (видимость) | Условия, при которых один поток видит изменения, сделанные другим потоком |
Таблица 1: Концепции параллелизма
Состояние гонки (Race condition)
Гонка данных (Data race)
Гонка данных возникает, когда два или более потока пытаются получить доступ к одной и той же не финальной переменной без синхронизации. Отсутствие синхронизации может привести к внесению изменений, которые не будут видны другим потокам, из-за этого возможно чтение устаревших данных, что, в свою очередь, приводит к бесконечным циклам, поврежденным структурам данных или неточным вычислениям. Этот код может привести к бесконечному циклу, потому что считывающий поток может так и не заметить изменения, внесенные перезаписывающими потоками:
Модель памяти Java: отношение happens-before
Модель памяти Java определяется с точки зрения таких действий, как чтение/запись полей и синхронизация в мониторе. Действия упорядочены с помощью отношения happens-before (выполняется прежде), которое может быть использовано для объяснения того, когда поток видит результат действий другого потока, и что представляет собой правильно синхронизированная программа.
ОТНОШЕНИЯ HAPPENS-BEFORE ИМЕЮТ СЛЕДУЮЩИЕ СВОЙСТВА:
Изображение 1: Пример happens-before
Стандартные функции синхронизации
Ключевое слово synchronized
Ключевое слово synchronized используется для предотвращения одновременного выполнения разными потоками одного и того же блока кода. Оно гарантирует, что, если вы получили блокировку (войдя в синхронизированный блок), данные, на которые наложена эта блокировка, обрабатываются в эксклюзивном режиме, поэтому операция может считаться атомарной. Кроме того, оно гарантирует, что другие потоки увидят результат операции после того, как получат такую же блокировку.
Ключевое слово synchronized можно также раскрыть на уровне методов.
| ССЫЛКА, ИСПОЛЬЗУЕМАЯ КАК МОНИТОР | |
|---|---|
| static | ссылка на объект Class |
| non-static | this-ссылка |
Таблица 2: Мониторы, которые используются, когда весь метод синхронизирован
Блокировка реентерабельна (reentrant), поэтому, если поток уже содержит блокировку, он может успешно получить ее снова.
Уровень соперничества влияет на способ захвата монитора:
| Описание | |
|---|---|
| init | Только что создан, пока никем не был захвачен. |
| biased | Борьбы нет, и код, защищенный блокировкой, выполняется только одним потоком. Самый дешевый для захвата. |
| thin | Монитор захватывается несколькими потоками без борьбы. Для блокировки используется сравнительно дешевый CAS. |
| fat | Возникает борьба. JVM запрашивает мьютексы ОС и позволяет планировщику ОС обрабатывать парковки потоков и пробуждения. |
Таблица 3: Состояния мониторов
volatile решает проблему видимости и делает изменение значения атомарным, потому что здесь есть отношение happens-before: запись в volatile-переменную происходит до любого последующего считывания volatile-переменной. Таким образом, оно гарантирует, что при последующем считывании поля будет видно значение, которое было задано самой последней записью.
Используя классы AtomicXXX, можно реализовать атомарную операцию check-then-act :
Публикация объекта делает его ссылку доступной за пределами текущей области (например, возврат ссылки из геттера). Обеспечение безопасной публикации объекта (только когда он полностью создан) может потребовать синхронизации. Безопасность публикации может быть достигнута с использованием:
Убедитесь, что this-ссылка не испарилась во время создания.
Одним из самых замечательных свойств неизменяемых объектов является потокобезопасность, поэтому синхронизация для них не нужна. Требования к неизменному объекту:
Класс java.lang.Thread используется для представления приложения или потока JVM. Код всегда выполняется в контексте некоторого класса Thread (чтобы получить текущий поток вы можете использовать Thread#currentThread()).
| Описание | |
|---|---|
| NEW | Не запускался. |
| Запущен и работает. | |
| BLOCKED | Ожидание на мониторе — он пытается получить блокировку и войти в критическую секцию. |
| WAITING | Ожидание выполнения определенного действия другим потоком (notify/notifyAll, LockSupport#unpark). |
| То же, что и WAITING, но с таймаутом. | |
| TERMINATED | Остановлен |
Таблица 4: Состояния потоков
| Описание | |
|---|---|
| start | Запускает экземпляр класса Thread и выполняет метод run(). |
| join | Блокирует до окончания потока. |
| interrupt | Прерывает поток. Если поток заблокирован в методе, который отвечает на прерывания, в другом потоке будет брошен InterruptedException, в противном случае будет установлен статус прерывания. |
| stop, suspend, resume, destroy | Все эти методы устарели. Они выполняют опасные операции в зависимости от состояния рассматриваемого потока. Вместо них используйте Thread#interrupt() или флаг volatile, чтобы указать потоку, что он должен делать |
Таблица 5: Thread coordination methods Методы координации потоков
Как обрабатывать InterruptedException?
Пример потенциального дэдлока:
Взаимная блокировка происходит, если в одно и то же время:
JVM способен обнаруживать взаимные блокировки мониторов и выводить информацию о них в дампах потоков.
Livelock и потоковое голодание
Livelock возникает, когда потоки тратят все свое время на переговоры о доступе к ресурсу или обнаруживают и избегают тупиковой ситуации так, что поток фактически не продвигается вперед. Голодание возникает, когда потоки сохраняют блокировку в течение длительных периодов, так что некоторые потоки «голодают» без прогресса.
Основным интерфейсом для пулов потоков является ExecutorService.java.util.concurrent также предоставляет статическую фабрику Executors, которая содержит фабричные методы для создания пула потоков с наиболее распространенными конфигурациями.
| Метод | Описание |
|---|---|
| newSingleThreadExecutor | Возвращает ExecutorService только с одним потоком. |
| newFixedThreadPool | Возвращает ExecutorService с фиксированным количеством потоков. |
| newCachedThreadPool | Возвращает ExecutorService с пулом потоков различного размера. |
| Возвращает ScheduledExecutorService с одним потоком. | |
| newScheduledThreadPool | Возвращает ScheduledExecutorService с основным набором потоков. |
| newWorkStealingPool | Возвращает крадущий задачи ExecutorService. |
Таблица 6: Методы статической фабрики
| Реализация | Описание |
|---|---|
| ThreadPoolExecutor | Реализация по умолчанию с изменяющим размер пулом потока, одной рабочей очереди и настраиваемой политикой для отклоненных задач (через RejectedExecutionHandler) и создания потоков (через ThreadFactory). |
| Расширение ThreadPoolExecutor, которое обеспечивает возможность планирования периодических задач. | |
| ForkJoinPool | Крадущий задачи пул: все потоки в пуле пытаются найти и запустить либо поставленные задачи, либо задачи, созданные другими активными задачами. |
Таблица 7: Реализации пула потоков
| Описание | |
|---|---|
| Runnable | Представляет задачу без возвращаемого значения. |
| Callable | Представляет вычисление с возвращаемым значением. Он также выбрасывает исходный Exeption, поэтому не требуется обертка для проверенного исключения. |
Таблица 8: Функциональные интерфейсы задач
Future — это абстракция для асинхронного вычисления. Она представляет результат вычисления, который может быть доступен в какой-либо момент: либо вычисленное значение, либо исключение. Большинство методов ExecutorService используют Future как возвращаемый тип. Он предоставляет методы для изучения текущего состояния future или блокирует до тех пор, пока не будет доступен результат.
Пакет java.util.concurrent.locks также содержит интерфейс ReadWriteLock (и реализацию ReentrantReadWriteLock), который определяется парой блокировок для чтения и записи, обычно позволяя считывать одновременно нескольким читателям, но допуская только одного писателя.
CompletableFuture является абстракцией для произведения асинхронных вычислений. В отличие от простого Future, где единственная возможность получить результат — блокировать, рекомендуется регистрировать обратные вызовы для создания конвейера задач, которые должны выполняться, когда доступен результат или исключение. Либо во время создания (через CompletableFuture#supplyAsync/runAsync ), либо во время добавления обратных вызовов (методы семейства *async ) может быть указан исполнитель, где должно выполняться вычисление (если он не указан стандартным глобальным ForkJoinPool#commonPool ).
Учтите, что если CompletableFuture уже завершен, обратные вызовы, зарегистрированные с помощью не *async методов, будут выполняться в вызывающем потоке.
| Реализация | Описание |
|---|---|
| Предоставляет семантику копирования при записи, где каждая модификация структуры данных приводит к новой внутренней копии данных (поэтому запись очень дорогая, тогда как чтение дешевое). Итераторы в структуре данных всегда видят снепшот данных с момента создания итератора. |
Таблица 9: Списки в java.util.concurrent
| Описание |
|---|
| Обычно выступает в качестве сегментированной хэш-таблицы. Операции чтения, как правило, не блокируют и отражают результаты последней завершенной записи. Запись первого узла в пустой ящик выполняется просто CAS-ом (сравнить и установить), тогда как другим операциям записи требуются блокировки (первый узел сегмента используется как блокировка). |
| Обеспечивает параллельный доступ наряду функциональностью сортированного Map, подобной TreeMap. Границы производительности такие же как у TreeMap, хотя несколько потоков обычно могут читать и записывать из ассоциативного массива без конфликтов, если они не изменяют одну и ту же часть отображения. |
Таблица 10: Ассоциативные массивы в java.util.concurrent
| Описание |
|---|
| Подобно CopyOnWriteArrayList, он использует семантику copy-on-write для реализации интерфейса Set. |
| Подобно ConcurrentSkipListMap, но реализует интерфейс Set. |
Таблица 11: Множества в java.util.concurrent
Другим подходом к созданию параллельного множества является обертка параллельного Map:
Взаимоблокировка потоков Java и Livelock
Узнайте, как распознать и избежать взаимоблокировки и оживления в многопоточных Java-приложениях.
1. Обзор
Хотя многопоточность помогает повысить производительность приложения, она также сопряжена с некоторыми проблемами. В этом уроке мы рассмотрим две такие проблемы, deadlock и livelock, с помощью примеров Java.
2. Тупик
2.1. Что Такое Тупик?
Классическая проблема обедающих философов прекрасно демонстрирует проблемы синхронизации в многопоточной среде и часто используется в качестве примера тупика.
2.2. Пример Тупиковой Ситуации
Во-первых, давайте рассмотрим простой пример Java, чтобы понять тупик.
Теперь давайте напишем класс Deadlock Example :
Давайте теперь запустим этот пример взаимоблокировки и заметим результат:
2.3. Как избежать Тупика
Взаимоблокировка – это распространенная проблема параллелизма в Java. Поэтому мы должны разработать Java-приложение, чтобы избежать любых потенциальных тупиковых условий.
3. Живой замок
3.1. Что Такое Lifelock
Livelock-это еще одна проблема параллелизма, похожая на тупик. В livelock два или более потока продолжают передавать состояния друг другу вместо бесконечного ожидания, как мы видели в примере с тупиком. Следовательно, потоки не могут выполнять свои соответствующие задачи.
Отличным примером livelock является система обмена сообщениями, в которой при возникновении исключения потребитель сообщения откатывает транзакцию и помещает сообщение обратно в начало очереди. Затем одно и то же сообщение повторно считывается из очереди, только чтобы вызвать другое исключение и быть помещенным обратно в очередь. Потребитель никогда не получит никакого другого сообщения из очереди.
3.2. Пример Livelock
Обе нити нуждаются в двух блокировках, чтобы завершить свою работу. Каждый поток получает свою первую блокировку, но обнаруживает, что вторая блокировка недоступна. Таким образом, чтобы позволить другому потоку завершить работу первым, каждый поток освобождает свою первую блокировку и пытается снова получить обе блокировки.
Давайте продемонстрируем livelock с помощью примера Livelock класса:
Теперь давайте рассмотрим этот пример:
Как мы видим в журналах, оба потока неоднократно получают и освобождают блокировки. Из-за этого ни один из потоков не может завершить операцию.
3.3. Избегание живого потока
Чтобы избежать оживления, нам нужно изучить состояние, которое вызывает оживление, а затем придумать соответствующее решение.
Например, если у нас есть два потока, которые постоянно получают и освобождают блокировки, что приводит к оживлению, мы можем спроектировать код так, чтобы потоки повторяли попытки получения блокировок через случайные интервалы. Это даст потокам справедливый шанс приобрести нужные им замки.
Другой способ решить проблему живучести в примере с системой обмена сообщениями, который мы обсуждали ранее, – поместить неудачные сообщения в отдельную очередь для дальнейшей обработки вместо того, чтобы снова помещать их в ту же очередь.
4. Заключение
В этом уроке мы обсудили тупик и живую блокировку. Кроме того, мы рассмотрели примеры Java, чтобы продемонстрировать каждую из этих проблем, и кратко коснулись того, как мы можем их избежать.
19) Livelock
Что такое Livelock?
Из этого руководства по операционной системе вы узнаете:
Примеры Livelock
Самым простым примером Livelock могут быть два человека, которые встречаются лицом к лицу в коридоре, и оба они отодвигаются в сторону, чтобы пропустить другого. Они заканчивают тем, что двигались из стороны в сторону, не делая никакого прогресса, поскольку они двигаются тем же самым способом в то время. Здесь они никогда не пересекаются.
На приведенном выше изображении видно, что каждому из двух указанных процессов нужны два ресурса, и они используют примитивный входной регистр опроса, чтобы попытаться получить необходимые им блокировки. Если попытка не удалась, метод работает снова.
Предполагая, что процесс A запускается первым и получает ресурс данных X, а затем процесс B запускается и получает ресурс Y, независимо от того, какой процесс запускается первым, ни один из них не продвигается дальше.
Однако ни один из двух процессов не заблокирован. Они многократно расходуют ресурсы ЦП без какого-либо прогресса, но также останавливают любой блок обработки.
Следовательно, эта ситуация не является тупиковой, потому что нет ни одного заблокированного процесса, но мы сталкиваемся с ситуацией, эквивалентной взаимоблокировке, то есть LIVELOCK.
Что приводит к Livelock?
Livelock происходит, когда общее число разрешенных процессов в конкретной системе должно быть определено общим количеством записей в таблице процессов. Таким образом, слоты таблицы процессов следует называть конечными ресурсами.
Что такое тупик?
Взаимная блокировка — это ситуация, которая возникает в ОС, когда какой-либо процесс переходит в состояние ожидания, поскольку другой ожидающий процесс удерживает требуемый ресурс. Взаимная блокировка является распространенной проблемой в многопроцессорной обработке, когда несколько процессов совместно используют определенный тип взаимоисключающего ресурса, известного как программная блокировка или программное обеспечение.
Пример тупика
Что такое голод?
Голод — это ситуация, когда все процессы с низким приоритетом блокируются, а процессы с высоким приоритетом продолжаются. В любой системе запросы на ресурсы с высоким / низким приоритетом продолжают происходить динамически. Таким образом, требуется определенная политика, чтобы решить, кому и когда получить поддержку.
Используя некоторые алгоритмы, некоторые процессы могут не получить желаемое обслуживание, даже если они не заблокированы. Истощение происходит, когда некоторые потоки делают общие ресурсы недоступными в течение длительного периода времени.
Пример голодания:
Например, объект предлагает синхронизированный метод, который может занять много времени для возврата. Если один поток часто использует этот метод, другие потоки, которым также требуется частый синхронизированный доступ к одному и тому же объекту, часто блокируются.
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 очень неэффективный код, но голодания может также применяться к процессору, памяти, файловым дескрипторам, соединениям с бд, к любому ресурсу, который должен использоваться совместно.
Если у вас есть параллельный процесс, который настолько жаден, что препятствует эффективно работать другим параллельным процессам, то у вас большая проблема.