Что такое Livelock (взаимная блокировка) в Go и чем он отличается от Deadlock?

Livelock (взаимная блокировка) — это состояние в конкурентной системе, при котором несколько горутин постоянно выполняют работу (их состояние меняется), но система в целом не достигает прогресса. Горутины не заблокированы, а находятся в бесконечном цикле "уступок" друг другу.

Отличие от Deadlock

Ключевое отличие — в состоянии участников:

• Deadlock (тупик): Горутины находятся в состоянии ожидания ресурса, который захвачен другой горутиной. Они "заморожены" и не выполняют никакой работы.
• Livelock (взаимная блокировка): Горутины активны и постоянно меняют свое состояние, реагируя на действия друг друга, но эта активность бесполезна и не ведет к результату.

Аналогия:

• Deadlock: Два человека встретились на узкой лестнице, каждый ждет, что другой сойдет с пути. Никто не двигается.
• Livelock: Два вежливых человека встретились в узком коридоре. Первый шагает вправо, чтобы пропустить. Второй одновременно шагает влево (в ту же сторону). Затем они оба пытаются исправить ситуацию, шагая в другую сторону, и снова блокируют друг друга. Они постоянно двигаются, но пройти не могут.

Пример Livelock

Рассмотрим двух "вежливых" горутин, которые пытаются захватить два мьютекса, но уступают, если не могут захватить оба сразу. Это может привести к livelock, если они будут уступать синхронно.

package main

import (
    "fmt"
    "sync"
    "time"
)

func main() {
    var wg sync.WaitGroup
    mu1 := &sync.Mutex{}
    mu2 := &sync.Mutex{}

    worker := func(id int, first, second *sync.Mutex) {
        defer wg.Done()
        for i := 0; i < 100; i++ { // Ограничим попытки, чтобы не зависнуть навсегда
            first.Lock()
            time.Sleep(10 * time.Millisecond) // Имитация работы

            // Пытаемся захватить второй мьютекс
            if second.TryLock() {
                fmt.Printf("Работник %d успешно выполнил работуn", id)
                second.Unlock()
                first.Unlock()
                return // Работа сделана, выходим
            }

            // Не удалось захватить второй, "вежливо" освобождаем первый
            first.Unlock()
            fmt.Printf("Работник %d уступил...n", id)
        }
    }

    wg.Add(2)
    // Запускаем работников, передавая мьютексы в разном порядке, 
    // чтобы создать условие для блокировки.
    go worker(1, mu1, mu2)
    go worker(2, mu2, mu1)
    wg.Wait()
    fmt.Println("Программа завершена")
}

Как избежать Livelock?

1. Фиксированный порядок захвата ресурсов: Если все горутины будут захватывать мьютексы в одном и том же порядке (например, всегда сначала mu1, потом mu2), livelock (и deadlock) не возникнет.
2. Случайная задержка (Randomized Backoff): Вместо того чтобы сразу пытаться снова, горутина может подождать случайный промежуток времени перед следующей попыткой. Это нарушит синхронность "уступок".