Что такое livelock?

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

Как возникает livelock?

Типичный сценарий — два потока пытаются захватить два ресурса (A и B), но используют алгоритм избежания deadlock: если ресурс занят, они освобождают уже захваченный и повторяют попытку позже. Если оба потока синхронизируют свои действия, они могут одновременно захватывать и освобождать ресурсы, никогда не получая оба сразу.

Пример на Python

import threading
import time

resource_a = threading.Lock()
resource_b = threading.Lock()

def worker1():
    while True:
        if resource_a.acquire(blocking=False):
            print("Worker1 захватил A")
            time.sleep(0.1)  # Имитация работы
            if resource_b.acquire(blocking=False):
                print("Worker1 захватил B → работа завершена")
                resource_b.release()
                resource_a.release()
                break
            else:
                print("Worker1 не может захватить B, освобождает A")
                resource_a.release()
                time.sleep(0.1)  # Пауза перед повторной попыткой

def worker2():
    while True:
        if resource_b.acquire(blocking=False):
            print("Worker2 захватил B")
            time.sleep(0.1)
            if resource_a.acquire(blocking=False):
                print("Worker2 захватил A → работа завершена")
                resource_a.release()
                resource_b.release()
                break
            else:
                print("Worker2 не может захватить A, освобождает B")
                resource_b.release()
                time.sleep(0.1)

thread1 = threading.Thread(target=worker1)
thread2 = threading.Thread(target=worker2)
thread1.start()
thread2.start()
thread1.join()
thread2.join()

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

Где встречается и как избежать?

• Сетевые протоколы: например, два узла одновременно отправляют пакеты, сталкиваются, отступают и снова отправляют в один момент.
• Координация распределённых систем: процессы пытаются достичь консенсуса, но постоянно меняют свои решения.
• Способы избежания: использовать случайные задержки перед повторными попытками, приоритеты потоков или более сложные алгоритмы (например, с обратным отсчётом).

Вывод: Livelock — коварная проблема, потому что система кажется рабочей, но фактически простаивает. Важно проектировать алгоритмы синхронизации так, чтобы потоки не попадали в циклические зависимости, и добавлять механизмы обнаружения (например, ограничение числа попыток).