Таблица 3.3. Методы предотвращения тупиков

Условие Метод

Взаимное исключение Организовывать подкачку данных

Удержание и ожидание Запрашивать все ресурсы на начальной стадии

Нет принудительной выгрузки ресурса Отобрать ресурсы

Циклическое ожидание Пронумеровать ресурсы и упорядочить

3.3.6. Избежание взаимоблокировок

Рассматривая обнаружение взаимоблокировок, мы неявно предполагали, что когда процесс запрашивает ресурсы, он требует их все сразу (матрица R на рис. 3.6). Однако в большинстве систем ресурсы запрашиваются поочередно, по одному. Система должна уметь решать, является ли предоставление ресурса безопасным или нет, и удовлетворять процесс только в первом случае. Таким образом, неизбежен новый вопрос: существует ли алгоритм, который никогда не повлечет ситуации взаимоблокировки, все время делающий правильный выбор? Ответом является условное да - мы можем избежать тупиков, но только если заранее будет доступна определенная информация. В следующем подразделе мы изучим способы уклонения от взаимоблокировок с помощью аккуратного предоставления ресурсов.

Алгоритм банкира для одного вида ресурсов

Алгоритм планирования, позволяющий избегать взаимоблокировок, был разработан Дейкстрой (Dijkstra, [27]) и носит название алгоритма банкира. Модель основана на примере банкира в маленьком городке, имеющего дело с группой клиентов, которым он выдал ряд кредитов. Алгоритм проверяет, ведет ли выполнение каждого запроса к небезопасному состоянию. Если да, запрос отклоняется. Если удовлетворение запроса ничем не грозит, ресурс предоставляется процессу. На рис. 3.8, а мы видим четырех клиентов, каждый из которых получил определенное количество единиц кредита (например, 1 единица равна 1 К долларов). Банкир знает, что не всем клиентам понадобится вся сумма немедленно, поэтому он зарезервировал только 10 единиц, а не все 22, которые требуются клиентам. (Чтобы провести аналогию с компьютерной системой, считаем, что клиенты - это процессы, единицами, скажем, являются накопители на магнитной ленте, а банкир - это операционная система.)

Клиенты вращаются в соответствующем бизнесе, время от времени прося у банка ссуды (то есть запрашивая ресурсы). В некоторый момент возникает ситуация, показанная на рис. 3.8, б. Список покупателей, фиксирующий, кому одолжены ресурсы, а также максимальный доступный кредит, называется состоянием системы.

Состояние системы считается безопасным, если существует последовательность состояний, когда все просители берут максимальный заем, до исчерпания кредита. Рассмотренное состояние безопасно, поскольку остались две единицы, и банкир может задержать все обращения, кроме запросов клиента или процесса Марвин, таким образом, позволяя процессу Марвин завершиться и вернуть все четыре отданных ему ресурса. Имея на руках четыре единицы, банкир может от-

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

Свободно: 10 а

Свободно: 2 б

Свободно: 1 в

Рис. 3.8. Три состояния распределения ресурсов: а - безопасное; б - безопасное;

в - небезопасное

Рассмотрим, что могло бы произойти, если бы в ситуации на рис. 3.8, б был удовлетворен запрос еще одной единицы для клиента Сьюзан. Мы попали бы в состояние рис. 3.8, в, не являющееся безопасным. Если бы все клиенты вдруг запросили максимальные ссуды, то банкир не сумел бы их обеспечить, и мы попали бы в тупик. Небезопасное состояние не обязано приводить к взаимоблокировке, так как клиентам не обязательно потребуется весь доступный кредит, но банкиру не следует рассчитывать на такую ситуацию.

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

Траектории ресурсов

Предыдущий алгоритм был описан в терминах одного класса ресурсов (то есть в нашем распоряжении только принтеры или только ленточные накопители, но не то и другое вместе). На рис. 3.9 представлена модель для системы с двумя процессами и двумя ресурсами, например принтером и плоттером. Горизонтальная ось отображает номера команд, выполняемых процессом А. По вертикальной оси отложены номера команд, выполняемых процессом В. В команде Ii процесс А запрашивает принтер, в команде I2 ему требуется плоттер. Принтер и плоттер освобождаются командами I3 и I4 соответственно. Процессу В необходим плоттер с команды i5 по команду I7 и принтер с команды Ie по команду Ig.

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

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

Когда процесс А пересекает линию Ii на отрезке от точки г до точки s, он запрашивает и получает принтер. Когда процесс В достигает точки t, он запрашивает плоттер.

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

Принтер

Плоттер

U (Завершены оба процесса)

Плоттер

Принтер

Рис. 3.9. Две траектории ресурсов процессов

Если система войдет в прямоугольник, офаниченный линиями Ii и I2 по сторонам и линиями I5 и 1б сверху и снизу, она в конце концов доберется до пересечения линий I2 и 1б. В этот момент процесс А запросит плоттер, а процесс В пофебует принтер, но оба ресурса будут к тому времени заняты. Получается, что тупиковым является целый прямоугольник и в него нельзя входить. В точке t единственно безопасный вариант состоит в том, чтобы оставить процесс А работать до тех пор, пока он не достигнет команды I4. После нее любая траектория дойдет до точки и.

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