Что такое взаимная блокировка (Deadlock)

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

Взаимная блокировка может возникнуть в системах, в которых ресурсы могут быть захвачены и освобождены, а процессы не могут быть прерваны в процессе выполнения. Основные условия, приводящие к возникновению взаимной блокировки, называются «четырьмя условиями Дейкстры»:

1. Взаимная блокировка (Mutual Exclusion): Каждый ресурс либо уже захвачен, либо доступ к нему возможен только одному процессу за раз.
2. Неотъемлемость (Hold and Wait): Процесс уже удерживает какой-то ресурс и ждет освобождения других.
3. Неделимость ресурсов (No Preemption): Ресурсы, уже захваченные процессом, не могут быть освобождены принудительно до их завершения.
4. Циклическое ожидание (Circular Wait): Существует цепь процессов, где каждый процесс ожидает ресурсы, контролируемые следующим в цепочке.

Взаимная блокировка может создать заметные проблемы для системы, так как блокированные процессы простаивают, занимая ресурсы и не позволяя другим процессам получить доступ к ним. Система может оказаться в состоянии, из которого она не может выйти без вмешательства оператора. Для избежания такой ситуации используются различные методы, такие как анализ и предотвращение чрезмерной использования ресурсов, использование алгоритмов выделения ресурсов и т.д.

Пример взаимной блокировки на языке Swift

Вот пример кода на Swift, демонстрирующий взаимную блокировку:

import Foundation

// Создаем два объекта блокировки
let lock1 = NSObject()
let lock2 = NSObject()

// Создаем два потока
let thread1 = Thread {
    objc_sync_enter(lock1)
    print("Thread 1 locked lock1")
    // Делаем небольшую задержку, чтобы дать потоку 2 возможность
    // заблокировать lock2
    sleep(1)
    
    objc_sync_enter(lock2)
    print("Thread 1 locked lock2")
    
    // Разблокируем lock2
    objc_sync_exit(lock2)
    print("Thread 1 unlocked lock2")
    
    // Разблокируем lock1
    objc_sync_exit(lock1)
    print("Thread 1 unlocked lock1")
}

let thread2 = Thread {
    objc_sync_enter(lock2)
    print("Thread 2 locked lock2")
    // Делаем небольшую задержку, чтобы дать потоку 1 возможность
    // заблокировать lock1
    sleep(1)
    
    objc_sync_enter(lock1)
    print("Thread 2 locked lock1")
    
    // Разблокируем lock1
    objc_sync_exit(lock1)
    print("Thread 2 unlocked lock1")
    
    // Разблокируем lock2
    objc_sync_exit(lock2)
    print("Thread 2 unlocked lock2")
}

// Запускаем потоки
thread1.start()
thread2.start()

// Ожидаем завершения потоков
thread1.join()
thread2.join()

print("End of program")

import Foundation

​

// Создаем два объекта блокировки

let lock1 = NSObject()

let lock2 = NSObject()

​

// Создаем два потока

let thread1 = Thread {

    objc_sync_enter(lock1)

    print("Thread 1 locked lock1")

    // Делаем небольшую задержку, чтобы дать потоку 2 возможность

    // заблокировать lock2

    sleep(1)

    objc_sync_enter(lock2)

    print("Thread 1 locked lock2")

    // Разблокируем lock2

    objc_sync_exit(lock2)

    print("Thread 1 unlocked lock2")

    // Разблокируем lock1

    objc_sync_exit(lock1)

    print("Thread 1 unlocked lock1")

}

​

let thread2 = Thread {

    objc_sync_enter(lock2)

    print("Thread 2 locked lock2")

    // Делаем небольшую задержку, чтобы дать потоку 1 возможность

    // заблокировать lock1

    sleep(1)

    objc_sync_enter(lock1)

    print("Thread 2 locked lock1")

    // Разблокируем lock1

    objc_sync_exit(lock1)

    print("Thread 2 unlocked lock1")

    // Разблокируем lock2

    objc_sync_exit(lock2)

    print("Thread 2 unlocked lock2")

}

​

// Запускаем потоки

thread1.start()

thread2.start()

​

// Ожидаем завершения потоков

thread1.join()

thread2.join()

​

print("End of program")

В этом примере потоки 1 и 2 пытаются захватить два объекта блокировки lock1 и lock2 соответственно, в разных последовательностях. Когда поток 1 блокирует lock1, а затем пытается захватить lock2, он блокируется, так как lock2 уже заблокирован потоком 2. Аналогично, поток 2 блокируется при попытке захвата lock1, который уже захвачен потоком 1. Оба потока ожидают освобождения ресурсов, создавая взаимную блокировку и приводя к замораживанию программы.

Как избежать взаимных блокировок

Избежать взаимных блокировок в системе можно с помощью различных подходов и стратегий. Вот несколько из них:

Использование строгой иерархии при захвате ресурсов: Программисты могут разрабатывать код таким образом, чтобы ресурсы всегда захватывались в одном и том же порядке. Этот подход исключает возможность циклической блокировки.

Использование отложенного захвата ресурсов: Если процесс не может немедленно захватить все необходимые ресурсы, он может освободить захваченные ресурсы и попробовать снова позже.

Установка ограничений на время ожидания: Если процесс не может получить доступ к ресурсу в течение определенного времени, он может освободить ресурсы и попытаться снова позже, либо выполнить альтернативные действия.

Использование алгоритмов выделения ресурсов: При выделении ресурсов система должна учитывать возможность возникновения блокировок и предпринимать меры для их предотвращения.

Использование мониторов и семафоров: Мониторы и семафоры предоставляют механизмы синхронизации доступа к ресурсам, что позволяет избежать конфликтов и взаимных блокировок.

Анализ кода и алгоритмов: При проектировании и разработке программного обеспечения важно внимательно анализировать код и алгоритмы на предмет возможности взаимных блокировок и предпринимать меры для их предотвращения.

Кроме того, существуют различные инструменты и методы анализа кода, которые могут помочь выявить потенциальные узкие места и проблемы с взаимными блокировками в программном обеспечении.