25. Восстановление при взаимной блокировке. Исключение условий появления взаимоблокировок. (Лекция 6)

Восстановление при взаимной блокировке. Условия работы алгоритмов:

- необходимо знать максимальные требования процессов к ресурсам;

- процессы не должны завершаться в состоянии захвата ресуров;

- кол-во ресурсов фиксированное.

Недостаток – кол-во процессов и ресурсов сильно изменяется.

Восстановление: 1. Прекратить выполнение всех заблокированных процессов (Уничтожение всех заблокированных процессов – грубый, но распространенный метод).

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

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

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

Исключение условий появления взаимоблокировок.

1. Условие взаимного исключения (mutual exclusion ). Каждый ресурс в текущий момент или занят ровно одним процессом или свободный. То есть, ресурсы находятся в режиме эксклюзивного пользования. Подкачка данных на диск (виртуальная память, печать). Различные типы доступа к ресурсу – чтение и запись. Условие взаимного исключения, или эксклюзивного пользования должна выполняться для неразделимых ресурсов. Например, принтер должен использоваться экслюзивно, одним процессом. Однако, некоторые раздельные ресурсы, такие, как доступ к файлам на чтение, могут раздаваться многим процессам.

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

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

3. Условие отсутствия принудительного освобождения ресурсов (no preemption ). Невозможно заставить процесс освободить ранее полученные ресурсы. Процесс, обладающий ресурсами, должен сам их увольнять. Подходит для выгружаемых ресурсов. В случаях, когда процесс запрашивает доступ к ресурсу, который не может быть сразу предоставлено, он освобождает остальных занятых ресурсов, и передает их в очередь на запрос. Работу процесса будет возобновлено после получения доступа ко всем ресурсам в очереди (старые и новые ресурсы).

4. Условие циклического ожидания (circular wait ). Должно существовать кольцевая последовательность из двух или более процессов, каждый из которых ожидает увольнение ресурса, удерживаемого следующим членом последовательности. Иными словами, должно существовать множество процессов {P0, P1,... Pn}, так, что процесс P0 ожидает освобождения ресурс процесса P1, P1 ожидает P2,..., PN - 1 ожидает PN, а PN ожидает освобождения ресурсов процессом P0. Ресурсы нумеруются, процесс не может захватить ресурс с номером меньшим, чем он уже захватил. Варианты – для каждого типа своя нумерация и свой алгоритм.

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

Двухфазное блокирование: Первая фаза - попытка заблокировать все записи за один раз. Вторая фаза – захват и освобождение ресурсов. Если фаза 1 не удалась – ожидание. Недостаток – не годится для систем реального времени.