Взаимная блокировка в вычислительных системах

Введение

Состояние, в котором участники блокируют друг друга

Концепция компьютерных наук

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

Управление тупиком

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

Игнорируем тупик

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

Обнаружение

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

Профилактика

Предотвращение взаимных блокировок достигается путем исключения одного из четырех условий Коффмана. Устранение условия взаимного исключения означает, что ни один процесс не будет иметь исключительного доступа к ресурсу. Это невозможно для ресурсов, которые нельзя буферизировать. Однако даже для буферизируемых ресурсов взаимная блокировка все еще может возникнуть. Алгоритмы, избегающие взаимного исключения, называются неблокирующими алгоритмами синхронизации. Условия удержания и ожидания или удержания ресурсов можно устранить, потребовав от процессов запрашивать все необходимые ресурсы перед началом работы (или перед выполнением определенного набора операций). Эти априорные знания часто трудно получить, и в любом случае это неэффективное использование ресурсов. Другой подход заключается в том, чтобы требовать от процессов запрашивать ресурсы только при их отсутствии; сначала они должны освободить все свои текущие ресурсы, прежде чем запрашивать все необходимые ресурсы с нуля. Это также часто непрактично, поскольку ресурсы могут быть выделены и оставаться неиспользованными в течение длительного времени. Кроме того, процесс, запрашивающий популярный ресурс, может ждать неопределенно долго, поскольку такой ресурс всегда может быть выделен другому процессу, что приведет к голоданию ресурсов. (Эти алгоритмы, такие как сериализация токенов, известны как алгоритмы "все или ничего"). Условие отсутствия вытеснения также может быть трудно или невозможно избежать, поскольку процесс должен иметь возможность удерживать ресурс в течение определенного периода времени, иначе результат обработки может быть непоследовательным или возникнет треш. Однако невозможность обеспечить вытеснение может помешать работе алгоритма приоритетов. Вытеснение "заблокированного" ресурса обычно подразумевает откат, которого следует избегать из-за высокой стоимости накладных расходов. Алгоритмы, допускающие вытеснение, включают алгоритмы без блокировок и без ожидания, а также оптимистический контроль параллелизма. Если процесс, удерживающий некоторые ресурсы, запрашивает другие ресурсы, которые не могут быть немедленно выделены, это условие можно устранить, освободив все ресурсы, в настоящее время удерживаемые этим процессом. Последнее условие – это условие циклической зависимости. Подходы, избегающие циклической зависимости, включают отключение прерываний в критических секциях и использование иерархии для определения частичного порядка ресурсов. Если очевидной иерархии не существует, даже адрес памяти ресурсов может использоваться для определения порядка, и ресурсы запрашиваются в порядке возрастания перечисления.

Deadlock prevention works by preventing one of the four Coffman conditions from occurring. Removing the mutual exclusion condition means that no process will have exclusive access to a resource. This proves impossible for resources that cannot be spooled. But even with spooled resources, the deadlock could still occur. Algorithms that avoid mutual exclusion are called non blocking synchronization algorithms. The hold and wait or resource holding conditions may be removed by requiring processes to request all the resources they will need before starting up (or before embarking upon a particular set of operations). This advance knowledge is frequently difficult to satisfy and, in any case, is an inefficient use of resources. Another way is to require processes to request resources only when it has none; First, they must release all their currently held resources before requesting all the resources they will need from scratch. This too is often impractical. It is so because resources may be allocated and remain unused for long periods. Also, a process requiring a popular resource may have to wait indefinitely, as such a resource may always be allocated to some process, resulting in resource starvation. (These algorithms, such as serializing tokens, are known as the all or none algorithms.) The no preemption condition may also be difficult or impossible to avoid as a process has to be able to have a resource for a certain amount of time, or the processing outcome may be inconsistent or thrashing may occur. However, the inability to enforce preemption may interfere with a priority algorithm. Preemption of a "locked out" resource generally implies a rollback, and is to be avoided since it is very costly in overhead. Algorithms that allow preemption include lock free and wait free algorithms and optimistic concurrency control. If a process holding some resources and requests for some another resource(s) that cannot be immediately allocated to it, the condition may be removed by releasing all the currently being held resources of that process. The final condition is the circular wait condition. Approaches that avoid circular waits include disabling interrupts during critical sections and using a hierarchy to determine a partial ordering of resources. If no obvious hierarchy exists, even the memory address of resources has been used to determine ordering and resources are requested in the increasing order of the enumeration.

Ливолок

Живой замок аналогичен тупику, за исключением того, что состояния процессов, участвующих в живом замке, постоянно меняются по отношению друг к другу, при этом ни один из них не продвигается вперед. Термин был введен Эдвардом А. Эшкрофтом в 1975 году в работе, посвященной исследованию систем бронирования авиабилетов. Живой замок является частным случаем нехватки ресурсов; общее определение лишь указывает на то, что конкретный процесс не прогрессирует. Живой замок представляет собой риск при использовании некоторых алгоритмов обнаружения и восстановления после тупика. Если действия предпринимают более одного процесса, алгоритм обнаружения тупика может запускаться многократно. Этого можно избежать, обеспечив, чтобы действия предпринимал только один процесс (выбранный произвольно или по приоритету).

Распределенный тупик

Распределенные взаимоблокировки могут возникать в распределенных системах при использовании распределенных транзакций или управления параллельным доступом. Распределенные взаимоблокировки можно обнаружить либо путем построения глобального графа ожидания на основе локальных графов ожидания в детекторах взаимоблокировок, либо с помощью распределенного алгоритма, например, алгоритма "обхода ребер" (edge chasing). Фантомные взаимоблокировки – это взаимоблокировки, которые ложно обнаруживаются в распределенной системе из-за внутренних задержек системы, но фактически не существуют. Например, если процесс освобождает ресурс R1 и отправляет запрос на ресурс R2, а первое сообщение теряется или задерживается, координатор (детектор взаимоблокировок) может ошибочно сделать вывод о наличии взаимоблокировки (если запрос на R2 при владении R1 привел бы к взаимоблокировке).