Что такое deadlock и livelock?

# Deadlock и Livelock: концепции, различия и примеры на Go

Deadlock (Взаимная блокировка)

Deadlock — это состояние в многопоточном программировании, когда два или более потока (горутины в Go) бесконечно ожидают друг друга, освобождения ресурсов, которые они захватили. Все участвующие потоки блокируются, и прогресс программы становится невозможным.

Условия возникновения deadlock (четыре условия Коффмана):

1. Взаимное исключение — ресурс может использоваться только одним потоком одновременно
2. Удержание и ожидание — поток удерживает ресурс и ждет получения другого ресурса
3. Отсутствие вытеснения — ресурс нельзя отобрать у потока, только добровольно освободить
4. Круговое ожидание — образуется циклическая цепочка потоков, где каждый ждет ресурс от следующего

Пример deadlock в Go:

package main

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

func main() {
    var mu1, mu2 sync.Mutex
    
    // Горутина 1: захватывает mu1, затем пытается захватить mu2
    go func() {
        mu1.Lock()
        fmt.Println("Горутина 1: захватила mu1")
        time.Sleep(100 * time.Millisecond)
        
        mu2.Lock() // Блокировка здесь
        fmt.Println("Горутина 1: захватила mu2")
        
        mu2.Unlock()
        mu1.Unlock()
    }()
    
    // Горутина 2: захватывает mu2, затем пытается захватить mu1
    go func() {
        mu2.Lock()
        fmt.Println("Горутина 2: захватила mu2")
        time.Sleep(100 * time.Millisecond)
        
        mu1.Lock() // Блокировка здесь
        fmt.Println("Горутина 2: захватила mu1")
        
        mu1.Unlock()
        mu2.Unlock()
    }()
    
    // Даем время для возникновения deadlock
    time.Sleep(2 * time.Second)
    fmt.Println("Программа завершена (это сообщение может не вывестись)")
}

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

Livelock (Активная блокировка)

Livelock — это состояние, когда потоки активно выполняются, но не продвигаются в решении задачи из-за постоянного реагирования на действия друг друга. Это похоже на вежливых людей в дверном проеме: каждый уступает дорогу другому, и в результате никто не проходит.

Характеристики livelock:

• Потоки не заблокированы, они выполняют работу
• Потоки постоянно меняют состояние в ответ на действия других потоков
• Общего прогресса не происходит, система "топчется на месте"

Пример livelock в Go:

package main

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

type Spoon struct {
    sync.Mutex
    owner string
}

func (s *Spoon) use() {
    fmt.Printf("%s использует ложку\n", s.owner)
}

func eat(person, spoonOwner string, spoon *Spoon, wg *sync.WaitGroup) {
    defer wg.Done()
    
    for i := 0; i < 3; i++ {
        // Пытаемся взять ложку
        spoon.Lock()
        
        // Если ложка принадлежит другому, вежливо отдаем
        if spoon.owner != person {
            fmt.Printf("%s: ой, это твоя ложка, %s, забирай\n", person, spoon.owner)
            spoon.owner = person
            spoon.Unlock()
            time.Sleep(100 * time.Millisecond) // Ждем немного
            continue // Пытаемся снова
        }
        
        // Используем ложку
        spoon.use()
        spoon.Unlock()
        
        time.Sleep(500 * time.Millisecond)
        return // Завершаем прием пищи
    }
    
    fmt.Printf("%s так и не поел!\n", person)
}

func main() {
    var wg sync.WaitGroup
    spoon := &Spoon{owner: "Алиса"}
    
    wg.Add(2)
    go eat("Алиса", "Боб", spoon, &wg)
    go eat("Боб", "Алиса", spoon, &wg)
    
    wg.Wait()
}

В этом примере Алиса и Боб постоянно передают ложку друг другу из вежливости, в результате никто не может поесть — это классический livelock.

Ключевые различия

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

Для deadlock:

1. Упорядоченная блокировка — всегда захватывать мьютексы в одинаковом порядке
2. Использование sync.RWMutex вместо sync.Mutex где это уместно
3. Использование select с таймаутами при работе с каналами
4. Инструменты анализа вроде go run -race для обнаружения гонок данных

// Правильный подход: упорядоченная блокировка
func safeTransfer(a, b *Account, amount int) {
    // Всегда блокируем аккаунт с меньшим ID первым
    first, second := a, b
    if a.id > b.id {
        first, second = b, a
    }
    
    first.mu.Lock()
    second.mu.Lock()
    
    // Выполняем операцию
    a.balance -= amount
    b.balance += amount
    
    second.mu.Unlock()
    first.mu.Unlock()
}

Для livelock:

1. Введение случайных задержек для打破 симметрии
2. Приоритеты потоков — определение, кто должен действовать первым
3. Ограничение числа попыток перед сменой стратегии
4. Использование backoff-алгоритмов (экспоненциальная отсрочка)

// Решение livelock с экспоненциальной отсрочкой
func worker(id int, resource *sync.Mutex, wg *sync.WaitGroup) {
    defer wg.Done()
    
    backoff := time.Millisecond
    maxBackoff := time.Second
    
    for attempt := 0; attempt < 5; attempt++ {
        if resource.TryLock() {
            // Критическая секция
            fmt.Printf("Worker %d получил ресурс\n", id)
            time.Sleep(50 * time.Millisecond)
            resource.Unlock()
            return
        }
        
        // Экспоненциальная отсрочка
        time.Sleep(backoff)
        backoff *= 2
        if backoff > maxBackoff {
            backoff = maxBackoff
        }
    }
    
    fmt.Printf("Worker %d не смог получить ресурс\n", id)
}

Заключение

Понимание deadlock и livelock критически важно для разработки надежных конкурентных приложений на Go. В то время как deadlock приводит к полной остановке выполнения, livelock создает иллюзию работы, фактически не продвигаясь к решению задачи. Обе проблемы требуют внимательного проектирования системы синхронизации, использования правильных примитивов (sync.Mutex, sync.RWMutex, каналы, select с таймаутами) и тщательного тестирования, особенно с включенным детектором гонок данных (-race флаг).