Livelock¶

Livelock (от англ. live — живой, активный и lock — блокировка, затор) — в информатике и параллельных вычислениях — состояние, при котором два или более параллельных процесса (потоков, задач) постоянно изменяют своё состояние в ответ на действия друг друга, но при этом ни один из них не может выполнить полезную работу и завершиться. В отличие от взаимоблокировки (deadlock), где процессы просто ожидают освобождения ресурсов и не выполняют никаких действий, при livelock процессы активны, но их активность бесполезна и не приводит к прогрессу.

¶Отличие от взаимоблокировки (deadlock)

Ключевое различие между livelock и deadlock заключается в поведении процессов. При deadlock процессы находятся в состоянии ожидания и не потребляют процессорное время (или потребляют его минимально, ожидая сигнала). При livelock процессы, напротив, активно выполняют код, но их действия сводятся к бесконечному циклу попыток согласования или освобождения ресурсов. С точки зрения внешнего наблюдателя, система может выглядеть работающей (процессы не «зависли»), но фактически она не выполняет никаких полезных вычислений.

Пример: два процесса, A и B, пытаются получить доступ к двум ресурсам, R1 и R2. Процесс A захватывает R1, процесс B захватывает R2. Затем A пытается захватить R2, но обнаруживает, что он занят, и освобождает R1, чтобы «уступить» B. B, в свою очередь, пытается захватить R1, видит, что он освобождён, но затем A снова захватывает R1, и цикл повторяется. Оба процесса постоянно освобождают и повторно захватывают ресурсы, не продвигаясь к выполнению своей основной задачи.

¶Причины возникновения

Livelock возникает в системах, где используется механизм «отката» (rollback) или «уступки» (backoff) при попытке захвата ресурсов. Типичные сценарии:

• Синхронизация с тайм-аутами и повторными попытками. Если несколько процессов одновременно обнаруживают конфликт и решают подождать случайное время перед повторной попыткой, но при этом алгоритм выбора времени ожидания неудачен (например, все процессы выбирают одинаковую задержку), они могут снова и снова входить в конфликт.
• Алгоритмы, основанные на «вежливом» поведении. Процессы, которые при обнаружении блокировки немедленно освобождают все свои ресурсы в надежде, что другой процесс сможет их захватить, могут создать ситуацию, когда ни один из них не может удержать ресурсы достаточно долго.
• Обработка исключений и прерываний. В некоторых реализациях, при возникновении исключения в критической секции, процесс может освободить ресурсы и попытаться перезапустить операцию, что при определённых условиях приводит к livelock.

¶Примеры в реальных системах

¶Сетевые протоколы

В компьютерных сетях livelock может возникать в протоколах, использующих механизмы обнаружения коллизий и повторной передачи (например, в ранних версиях Ethernet). Если два узла одновременно начинают передачу и обнаруживают коллизию, они оба ждут случайное время перед повторной попыткой. Если случайные задержки оказываются одинаковыми, коллизия повторяется, и процесс может продолжаться бесконечно. В современных протоколах (например, в алгоритме «экспоненциальной задержки» — exponential backoff) вероятность этого снижается, но не исключается полностью.

¶Операционные системы

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

¶Многопоточные приложения

В многопоточных программах, использующих блокировки (mutex, spinlock), livelock может возникнуть, если потоки используют «вежливый» алгоритм захвата: при неудачной попытке захвата ресурса поток освобождает все свои ресурсы и начинает сначала. Если все потоки действуют синхронно, они могут вечно «перебрасывать» ресурсы друг другу.

¶Способы обнаружения и предотвращения

¶Обнаружение

Livelock сложнее обнаружить, чем deadlock, поскольку процессы активны. Основные методы:

• Мониторинг загрузки процессора. Если система потребляет 100% процессорного времени, но не выполняет полезных задач, это может быть признаком livelock.
• Анализ логов. Если в логах фиксируется многократное повторение одних и тех же операций без прогресса, это указывает на возможный livelock.
• Использование специализированных инструментов. Профилировщики и отладчики могут отслеживать состояния потоков и выявлять повторяющиеся последовательности действий.

¶Предотвращение

Основные стратегии предотвращения livelock:

• Использование случайных задержек (randomized backoff). При повторной попытке захвата ресурса процесс должен ждать случайное время, чтобы снизить вероятность синхронного поведения.
• Иерархия ресурсов. Упорядочивание ресурсов и обязательный захват их в строгом порядке (как при предотвращении deadlock) также помогает избежать livelock.
• Приоритеты процессов. Назначение разным процессам разных приоритетов позволяет одному из них «выиграть» конкуренцию за ресурсы.
• Ограничение числа попыток. Если процесс не может захватить ресурс после определённого числа попыток, он должен перейти в состояние ошибки или выполнить альтернативный сценарий.
• Использование атомарных операций. В некоторых случаях livelock можно избежать, используя атомарные инструкции (например, compare-and-swap), которые позволяют выполнить захват и проверку за одну операцию.

¶Livelock в аппаратном обеспечении

В цифровой электронике livelock может возникать в схемах, использующих асинхронные интерфейсы или протоколы с рукопожатием (handshake). Например, два устройства могут бесконечно обмениваться сигналами готовности, ни одно из них не переходя к передаче данных. Для предотвращения таких ситуаций в проектировании аппаратуры применяются конечные автоматы с тайм-аутами и механизмами сброса.

¶Сравнение с другими видами блокировок

¶Интересные факты

• Термин «livelock» был введён в обиход в начале 1980-х годов в контексте распределённых систем и сетевых протоколов.
• В некоторых учебниках livelock рассматривается как частный случай «активной блокировки» (active deadlock).
• В реальной практике livelock встречается значительно реже, чем deadlock, но его последствия могут быть более серьёзными, так как он приводит к полной загрузке процессора и может быть ошибочно принят за нормальную работу системы.
• Алгоритм «экспоненциальной задержки», используемый в протоколах Ethernet и Wi-Fi, был разработан в том числе для предотвращения livelock.

¶Источники

• Таненбаум Э., Бос Х. «Современные операционные системы». 4-е издание. — СПб.: Питер, 2015.
• Херлихи М., Шавит Н. «Искусство многопроцессорного программирования». — М.: ДМК Пресс, 2012.
• Silberschatz A., Galvin P. B., Gagne G. «Operating System Concepts». 10th Edition. — Wiley, 2018.
• Coulouris G., Dollimore J., Kindberg T., Blair G. «Distributed Systems: Concepts and Design». 5th Edition. — Addison-Wesley, 2011.