Простейший алгоритм обхода тупика

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

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

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

Рисунок 10.4 - Граф выделения и закрепления ресурсов с дугами потребности

Если в системе имеется n процессов, то алгоритм проверки наличия цикла имеет сложность порядка .

Алгоритм банкира

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

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

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

Для реализации алгоритма банкира требуются некоторые структуры данных. Пусть:

­ п – количество процессов в системе,

­ т – количество типов ресурсов.

Тогда:

­ Available – вектор размерностью т, определяющий количество доступных экземпляров для каждого типа ресурсов. Если Available _j равно k, это означает, что доступно k экземпляров ресурса R _j.

­ Max – матрица размерностью п ´ т определяющая максимальные ресурсные потребности для каждого процесса. Если Max _ij равно k, это означает, что процессу Р_i  понадобится не более k экземпляров ресурса R_j.

­ Allocation – матрица размерностью п ´ т, определяющая текущее закрепление ресурсов. Если Allocation _i,j равно k, это означает, что процессу Р_i в настоящий момент выделено k экземпляров ресурса R_j.

­ Need – матрица размерностью п ´ т, определяющая оставшиеся невостребованные ресурсы для каждого процесса. Если Need _i,j  равно k, это означает, что процессу Р_i для завершения работы понадобится ещё k экземпляров ресурса R_j.

Need [i, j] = Max [i, j] - Allocation [i,j]

Будем считать, что для векторов Х и Y имеет место Х £ Y если Х_i £ Y_i для всех
i = 1,2, …, n.

Алгоритм банкира базируется на двух процедурах:

­ S - процедура (для определения состояния безопасности/опасности);

­ R - процедура (для выделения процессу запрашиваемых ресурсов или перевод его в ожидание).

С учетом введенных обозначений основные шаги S-процедуры могут быть представлены в виде:

Шаг 1. Определим векторы Work и Finish размерностью m и n соответственно.

Присвоим им следующие начальные значения:

Work: = Available, Finish [i]: = false для i = 1, 2, …, n

где false соответствует незавершенному процессу, true - завершенному процессу.

Шаг 2. Найдем i, такое, что одновременно Finish[i]:=false, Need_i £ Work,

где Need_i - строка матрицы Need, определяющая оставшиеся невостребованными ресурсы для процесса Р_i.

В том случае, если такое i не найдено, перейдём к шагу 4.

Шаг 3.

Work: = Work + Allocation_i

Finish [i] = true

Переходим к шагу 2.

Шаг 4. Если Finish [i] = true для всех i, то система находится в безопасном состоянии.

R - процедура

Пусть Reguest_i - вектор размерностью т, описывающий запрос на выделение ресурса процессом Р_i. Если Reguest_i [j] = k, это означает, что процессу Р_i необходимо k экземпляров ресурса R_j.

Шаг 1. Если Reguest_i £ Need_i, то перейти к шагу 2. В противном случае – ошибка: «Запрошено больше ресурсов, чем возможно для данного процесса».

Шаг 2. ЕслиReguest_i £ Available, то переходим к шагу 3. В противном случае процесс Р_i переводится в состояние ожидания.

Шаг 3. Предположив, что затребованные ресурсы выделены, получим новые состояния системы.

Available: = Available - Reguest_i,

Allocation_i: = Allocation_i + Reguest_i,

Need_i: = Need_i + Reguest_i

С помощью S - процедуры определяется безопасность/опасность в состоянии системы. Если новое состояние безопасно, то для процесса Р_i выделяются запрашиваемые ресурсы. Если новое состояние опасно, то Р_i переводится в состояние ожидания и сохраняется старое состояние системы.

Обнаружение тупиков

За счет различных дорогостоящих вычислений можно установить, существуют ли процессы, находящиеся в состоянии тупика. Чтобы выполнить эти вычисления, ОС должна вести список тех ресурсов, которые ждет каждый заблокированный процесс, и список тех процессов, которые держат каждый недоступный ресурс. Алгоритм распознавания замкнутых цепей (Deadlock detection) можно выполнять с любой нужной частотой. Например, часто – всякий раз, когда запрос на ресурс отклоняется, или редко – раз в час или, когда загруженность СРU падает ниже некоторой критической величины (например ниже 40%).

Пусть:

­ Available – вектор длины т, определяющий количество допустимых экземпляров для каждого типа ресурсов.

­ Allocation – матрица размерностью п ´ т,определяющая текущее закрепление ресурсов.

­ Reguest – матрица размерности п ´ т, определяющая текущие запросы для всех процессов.

Если Reguest_i [j] = k, это означает, что процесс Р_i запрашивает k экземпляров ресурса R_j. Как и прежде, будем считать, что векторы Allocation_i, Reguest эквивалентны строкам соответствующих матриц.

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

Шаг 1. Пусть Work и Finish – векторы размерностью п и т соответственно. Инициализируем:

Work: = Available

Для i = 1, 2, …, n если Allocation_i ¹ 0, то есть имеется какое-то отличное от нуля распределения ресурсов, тогда Finish[i]:=false, иначе Finish[i]:=true.

Шаг 2. Находим i такое, что одновременно Finish [i]: = false <процесс не завершён> и Reguest_i £ Work <запрос меньше, чем имеется в наличии>

В том случае, если искомое i не существует, перейдем к шагу 4.

Шаг 3.

Finish [i]: = true

Work: = Work + Allocation_i

Перейдем к шагу 1.

Шаг 4.

Если Finish [i]: = false для некоторых i Î [1, n ], тогда система находится в тупике, и в тупиковую ситуацию вовлечены все процессы Р_i, для которых имеет место Finish [i]: = false.

Восстановление после тупика

Как только тупик выявлен, должно быть выполнено восстановление (Recovery from leadlock).Это обязательно вызовет перезапуск одного или более процессов. Процессы, находящиеся в тупике, были заблокированы в некоторой точке. Их нужно вернуть в те условия, в которых они могут возобновить свое исполнение. Для большинства процессов перезапуск возможен только с самого начала, и даже в этом случае могут возникнуть некоторые трудности. Процесс может сделать снимок своего исполнения, то есть запомнить информацию о своем состоянии в некоторой контрольной точке. В этом случае при повторном запуске этого процесса не требуется повторять все вычисления, предшествовавшие перераспределению. Контрольные точки обычно вводятся не для того, чтобы помочь восстановлению после тупика, а для того, чтобы продолжить исполнение после возникновения ошибки, особенно при выполнении длинных работ в системах реального времени.

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

­ администратор/оператор информирует о тупиковой ситуации и вручную восстанавливает систему;

­ система восстанавливает автоматически

При автоматическом восстановлении возможно два подхода:

­ принудительно удаляются процессы находящиеся в тупике;

­ принудительно освобождаются ресурсы, закреплённые за одним или несколькими процессами, находящимися в тупике.

При принудительном удалении процессов используется один из двух сценариев:

а) удаляются все процессы, находящиеся в тупике,

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

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

При принудительном освобождении ресурсов необходимо решать три задачи:

а) Выбор процесса (Selection a victim). Иными словами, у какого процесса какие ресурсы должны быть отобраны.

б) Способ возврата процесса в исходное состояние (Rollback). Если ресурс принудительно отобран у процесса, что необходимо делать с этим процессом?

Наилучшее решение – вернуть процесс в такое состояние, когда возможно построение безопасной последовательности процессов. Однако часто процесс, у которого отобран ресурс, запускается заново

в) Предотвращение «наказания» одного и того процесса (Starvation). Чаще всего для того, чтобы не выбирался один и тот же процесс, в критерий выбора включают количество возвратов к исходному состоянию.

Контрольные вопросы

1. Каковы причины возникновения тупиковых ситуаций?

2. В чем сходство безопасной и беступиковой ситуаций? В чем их различия?

3. В какие моменты ОС должна проводить действия по обнаружению тупика?

4. Какие соображения могут влиять на выбор процесса-жертвы при ликвидации тупика?

5. Какие вам известны методы решения проблемы тупиков? В чем суть каждого из этих методов?

 

УПРАВЛЕНИЕ ПАМЯТЬЮ