Взаимная блокировка | Обработка тупиковых ситуаций

Взаимная блокировка - ситуация, когда каждый из группы процессов ожидает событие, которое может вызвать только другой процесс из этой группы. Часто, такая ситуация наблюдается в парадоксах типа «Курица или яйцо». Также встречаются названия тупиковая ситуация, тупик, клинч. В англоязычной литературе эта ситуация называется англ. deadlock (произносится как Дедлок ).

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

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

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

Условия возникновения взаимной блокировки

Было показано, что для возникновения ситуации взаимной блокировки, необходимо выполнение следующих четырех условий одновременно:

1. Условие взаимного исключения ( англ. mutual exclusion ). Каждый ресурс в текущий момент или занят ровно одним процессом или свободный. То есть, ресурсы находятся в режиме эксклюзивного пользования.
2. Условие удержания и ожидания ( англ. hold and wait ). Процессы, в текущий момент удерживают полученные ранее ресурсы, могут делать запросы на получение новых ресурсов.
3. Условие отсутствия принудительного освобождения ресурсов ( англ. no preemption ). Невозможно заставить процесс освободить ранее полученные ресурсы.Процесс, обладающий ресурсами, должен сам их увольнять.
4. Условие циклического ожидания ( англ. circular wait ). Должно существовать кольцевая последовательность из двух или более процессов, каждый из которых ожидает увольнение ресурса, удерживаемого следующим членом последовательности. Иными словами, должно существовать множество процессов {P0, P1,... Pn}, так, что процесс P 0 ожидает освобождения ресур процесса P 1, P 1 ожидает P 2,..., P N - 1 ожидает P N, а P N ожидает освобождения ресурсов процессом P 0.

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

Моделирование тупиковых ситуаций

Пример графу выделения ресурсов. В этом примере все процессы получат доступ к необходимым ресурсам, следовательно, взаимная блокировка невозможна.

Ситуации взаимной блокировки возможно описать точнее с помощью специального средства - графу выделения ресурсов ( англ. system resource-allocation graph ). В этом ориентированном графе, множество вершин состоит из двух подмножеств - всех активных процессов в системе ( P = {P1, P2,..., Pn}) и существующих типов ресурсов ( R = {R1, R2,..., Rm} ).

Ребро от процесса P и к ресурсу P J обозначается как ; означает, что процесс P и подал запрос на одну единицу ресурса типа R J и ожидает этот ресурс (сокращенно, ребро запросу). Ребро от ресурса типа R J к процессу P и обозначается как ; означает, что единицу ресурса типа R J было предоставлено процесса P и (сокращенно, ребро выделения).

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

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

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

Если есть типы ресурсов с несколькими экземплярами, то из наличия цикла наличие тупика не следует. В этом случае наличие цикла является необходимым, но не достаточным условием для возникновения тупиков.

Сети Петри

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

Ловушкой называется такое множество позиций, для которой каждый переход, входом которого является одна из позиций множества на выходе имеет другую позицию множества. То есть, если в произвольной позиции ловушки есть фишка, то она всегда будет находиться в некотором с позиций ловушки.

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

Обработка тупиковых ситуаций

Обработку и обращение с ситуациями взаимной блокировки можно условно разделить на:

1. Пренебрежение проблемой вообще (т. н. "Страусиный алгоритм»).
2. Выявление и восстановление. Позволить произойти взаимному блокированию, выявить его, и выполнить некоторые действия.
3. Динамическое избежание взаимной блокировки путем правильного распределения ресурсов.
4. Предотвращение путем невыполнения одного из четырех условий возникновения взаимной блокировки.

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

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

Как было сказано выше, для возникновения ситуации взаимной блокировки необходимо одновременное выполнение четырех условий. Если один из них не выполняется, то ситуации взаимной блокировки возникать не будут. Здесь приведены описания подходов к каждой из условий.

Взаимное исключение

Условие взаимного исключения, или эксклюзивного пользования должна выполняться для неразделимых ресурсов. Например, принтер должен использоваться экслюзивно, одним процессом. Однако, некоторые раздельные ресурсы, такие, как доступ к файлам на чтение, могут раздаваться многим процессам.

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

Содержание и ожидания

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

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

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

Принудительное освобождение ресурсов

Для невыполнения условия отсутствия принудительного освобождения ресурсов, возможны следующие алгоритмы:

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

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

Циклическое ожидание

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

Пусть - множество типов ресурсов. Отождествит с каждым из них целое число, что позволит сравнивать ресурсы и устанавливать приоритеты (см. частично упорядоченное множество ).

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

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

Избежание

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

Инструменты

Известны такие инструменты для работы с клинчами в вычислительных системах:

witness

программа witness, работающий на операцинийних системах семейства BSD, получает информацию о полученных локи и проверяет на допустимость эти запросы.

SPIN

система для верификации моделей распределенных систем.