Добавлен: 29.10.2018
Просмотров: 48192
Скачиваний: 190
6.4. Обнаружение взаимоблокировок и восстановление работоспособности
501
процесс считается участвующим во взаимоблокировке. При работе этого алгоритма
предполагается наихудший из возможных сценариев развития событий: все процессы
удерживают все полученные ресурсы до тех пор, пока не закончат свою работу.
Теперь алгоритм обнаружения взаимного исключения можно изложить в следующей
последовательности:
1. Поиск непомеченного процесса, P
i
, для которого i-я строка матрицы R меньше или
равна A.
2. Если такой процесс найден, прибавление к A i-й строки матрицы C, установка
метки на процесс и возвращение к шагу 1.
3. Если такого процесса нет, алгоритм завершает работу.
По окончании работы алгоритма все непомеченные процессы, если таковые имеются,
считаются участвующими во взаимоблокировке.
На первом шаге алгоритм ищет процесс, который может доработать до конца. Такой
процесс характеризуется тем, что все его запросы на ресурсы могут быть удовлетво-
рены за счет текущих доступных ресурсов. Тогда выбранный процесс доработает до
конца, после чего вернет все удерживаемые им ресурсы в фонд доступных ресурсов.
Затем этот процесс помечается завершенным. Если в итоге окажется, что все про-
цессы могут доработать до конца, значит, ни один из них не участвует во взаимобло-
кировке. Если часть процессов никогда не сможет доработать до конца, значит, они
находятся в состоянии взаимоблокировки. Хотя алгоритм не является детермини-
рованным (поскольку он может запускать процессы в любом возможном порядке),
результат всегда одинаков.
Рассмотрим пример работы алгоритма обнаружения взаимоблокировок, показанный на
рис. 6.5. Здесь изображены три процесса и четыре класса ресурсов, которые мы произ-
вольно обозначили как накопители на магнитной ленте, плоттеры, сканер и привод Blu-
ray-дисков. Процесс 1 удерживает один сканер. Процесс 2 удерживает два ленточных
привода и один привод Blu-ray-дисков. Процесс 3 удерживает плоттер и два сканера.
Каждый процесс нуждается в дополнительных ресурсах, что отображено в матрице R.
Рис. 6.5. Пример, демонстрирующий работу алгоритма
обнаружения взаимоблокировок
502
Глава 6. Взаимоблокировка
Во время работы алгоритма обнаружения взаимоблокировок осуществляется поиск
процесса, чей запрос на ресурс может быть удовлетворен. Требования первого процесса
удовлетворить невозможно из-за отсутствия доступного привода Blu-ray-дисков. За-
прос второго процесса также нельзя удовлетворить, так как нет свободного сканера.
К счастью, можно удовлетворить запрос третьего процесса, поэтому третий процесс
запускается и в конечном итоге высвобождает все удерживавшиеся им ресурсы, в ре-
зультате чего получается:
A = (2 2 2 0)
Теперь может быть запущен процесс 2, высвобождающий удерживающиеся им ресурсы,
в результате чего получается:
A = (4 2 2 1)
и может быть запущен оставшийся процесс. При этом взаимоблокировки в системе
не возникает.
Рассмотрим незначительное изменение ситуации, показанной на рис. 6.5. Предпо-
ложим, что процесс 3 нуждается в приводе Blu-ray-дисков, а также в двух ленточных
накопителях и плоттере. Ни один из этих запросов не может быть удовлетворен, по-
этому вся система в конечном итоге войдет в состояние взаимоблокировки. Даже если
мы дадим процессу 3 два его ленточных накопителя и один плоттер, система войдет
в состояние взаимоблокировки при запросе привода Blu-ray-дисков.
Теперь, когда мы знаем, как можно обнаружить взаимоблокировку (по крайней мере,
при заранее известных статических запросах на выделение ресурсов), возникает вопрос,
когда именно нужно приступать к их поиску. Можно, конечно, проводить проверку при
выдаче каждого запроса на выделение ресурса. Тем самым будет обеспечено их обна-
ружение на самой ранней стадии, но это слишком обременительно для центрального
процессора. Есть альтернативная стратегия, предусматривающая проверку каждые
k минут или, может быть, только в том случае, когда степень загруженности процес-
сора снижается относительно какого-то порога. Оценка загруженности процессора
имеет определенный смысл, поскольку при участии во взаимоблокировке достаточного
количества процессов работоспособными останутся лишь несколько процессов и цен-
тральный процессор будет часто простаивать.
6.4.3. Выход из взаимоблокировки
Предположим, что наш алгоритм обнаружения взаимоблокировки успешно отработал
и обнаружил такую блокировку. Что же дальше? Нужны какие-то методы выхода из
нее, позволяющие системе восстановить работоспособность. В этом разделе будут
рассмотрены различные способы выхода из взаимоблокировки. Но ни один из них не
обладает какой-то исключительной привлекательностью.
Восстановление за счет приоритетного овладения ресурсом
Иногда можно временно отобрать ресурс у его текущего владельца и передать его дру-
гому процессу. В большинстве случаев для этого может понадобиться вмешательство
оператора, особенно в операционных системах пакетной обработки, запускаемых на
универсальных машинах.
6.4. Обнаружение взаимоблокировок и восстановление работоспособности
503
К примеру, чтобы отобрать лазерный принтер у владельца, оператор может сложить все
уже отпечатанные листы в стопку. Затем процесс может быть приостановлен (помечен
как неработоспособный). После этого принтер может быть выделен другому процессу.
Когда этот процесс завершит свою работу, стопка отпечатанных листов бумаги может
быть помещена обратно в приемный лоток принтера и работа исходного процесса
может быть возобновлена.
Возможность отобрать ресурс у процесса, позволить использовать его другому про-
цессу, а затем вернуть его без извещения процесса во многом зависит от природы этого
ресурса. Восстановление этим способом зачастую затруднено или вовсе невозможно.
Выбор процесса для приостановки обусловлен тем, какой именно процесс обладает
тем ресурсом, который у него можно легко отобрать.
Восстановление путем отката
Если разработчики системы и операторы вычислительной машины знают о том, что
есть вероятность возникновения взаимоблокировки, они могут организовать перио-
дическое создание процессами контрольных точек. Это означает, что состояние про-
цесса записывается в файл, что позволит осуществить его последующий перезапуск.
Контрольные точки содержат не только образ памяти, но и состояние ресурсов, то есть
информацию о том, какие ресурсы в данный момент выделены процессу. Для большей
эффективности новая контрольная точка должна записываться не поверх старой,
а в новый файл, чтобы во время выполнения процесса собралась целая последователь-
ность контрольных точек.
При обнаружении взаимоблокировки несложно определить, какие ресурсы нужны.
Чтобы выйти из взаимоблокировки, процесс, владеющий необходимым ресурсом, от-
катывается назад к точке, предшествующей получению данного ресурса, для чего он
запускается из одной из своих контрольных точек. Вся работа, выполненная после этой
контрольной точки, теряется (например, должна быть выброшена вся отпечатанная
после этой контрольной точки выходная информация, поскольку она будет отпеча-
тана снова). Фактически процесс возвращается к предшествующему моменту, когда
он еще не обладал тем ресурсом, который теперь выделен одному из участвующих во
взаимоблокировке процессов. Если перезапущенный процесс пытается опять получить
ресурс, ему приходится ждать, пока тот не станет доступен.
Восстановление путем уничтожения процессов
Самым грубым, но и самым простым способом прервать взаимоблокировку явля-
ется уничтожение одного или нескольких процессов. Можно уничтожить процесс,
находящийся в цикле взаимоблокировки. Если повезет, то другие процессы смогут
продолжить свою работу. Если это не поможет, то все можно повторить, пока цикл не
будет разорван.
В качестве альтернативы можно выбрать жертвой процесс, не находящийся в цикле,
чтобы он высвободил удерживаемые им ресурсы. При этом подходе уничтожаемый
процесс выбирается с особой тщательностью, потому что он должен удерживать ре-
сурсы, необходимые некоторым процессам в цикле. Например, один процесс может
удерживать принтер и требовать плоттер, а другой, наоборот, удерживать плоттер и за-
прашивать принтер. Оба они находятся в состоянии взаимоблокировки. Третий про-
504
Глава 6. Взаимоблокировка
цесс может удерживать другой такой же принтер и другой такой же плоттер и успешно
работать. Уничтожение третьего процесса приведет к высвобождению этих ресурсов
и разрушит взаимоблокировку первых двух процессов.
По возможности лучше убить процесс, который может быть безболезненно переза-
пущен с самого начала. К примеру, компиляция всегда может быть перезапущена,
поскольку все, что она делает, — это читает входной файл и создает объектный файл.
Если процесс компиляции будет уничтожен на полпути, то первый запуск не повлияет
на второй.
А вот процесс, обновляющий базу данных, не всегда можно будет безопасно запустить
во второй раз. Если процесс прибавляет единицу к какой-нибудь записи таблицы базы
данных, то его первоначальный запуск, уничтожение, а затем повторный запуск при-
ведут к неверному результату, поскольку к полю будет прибавлена двойка.
6.5. Уклонение от взаимоблокировок
При рассмотрении темы обнаружения взаимоблокировок мы предположили, что
когда процесс запрашивает ресурсы, он просит их все сразу (матрица R на рис. 6.4).
Но в большинстве систем ресурсы запрашиваются по одному. Система должна уметь
принимать решение, представляет выделение ресурса опасность или нет, и выделять его
только в том случае, если это безопасно. В связи с этим возникает вопрос: существует
ли алгоритм, который помог бы избежать взаимоблокировки, каждый раз делая пра-
вильный выбор? Ответом будет да, но при определенных условиях взаимоблокировки
можно избежать, но только если заранее будет доступна вполне определенная инфор-
мация. В этом разделе будут рассмотрены способы предупреждения взаимоблокировок
за счет тщательного распределения ресурсов.
6.5.1. Траектории ресурса
Основные алгоритмы уклонения от взаимоблокировок основаны на концепции без-
опасных состояний. Перед тем как дать описание алгоритмов, нужно сделать небольшое
отступление, чтобы рассмотреть концепцию безопасности в графическом, простом для
понимания виде. Хотя графический подход не переводится непосредственно в пригод-
ный к использованию алгоритм, он дает неплохое интуитивное понимание существа
вопроса.
На рис. 6.6 представлена модель для системы с двумя процессами и двумя ресурсами,
например принтером и плоттером. На горизонтальной оси отображены номера команд,
выполняемых процессом A. На вертикальной оси отображены номера команд, вы-
полняемых процессом B. В команде I
1
процесс A запрашивает принтер, в команде I
2
он
запрашивает плоттер. Принтер и плоттер высвобождаются командами I
3
и I
4
соответ-
ственно. Процессу B нужны плоттер с команды I
5
по команду I
7
и принтер с команды I
6
по команду I
8
.
Каждая точка на графике представляет совместное состояние двух процессов. Изна-
чально система находится в точке p, когда ни один процесс еще не выполнил ни одной
инструкции. Если планировщик запустит процесс A первым, мы попадем в точку q,
в которой процесс A выполнил какое-то количество команд, а процесс B еще ничего
не сделал. В точке q траектория становится вертикальной, показывая, что плани-
6.5. Уклонение от взаимоблокировок
505
Рис. 6.6. Траектории ресурсов двух процессов
ровщик решил запустить в работу процесс B. При наличии одного процессора все
отрезки траектории могут быть только вертикальными или горизонтальными, но не
диагональными. Кроме того, движение всегда происходит в северном или восточном
направлении (вверх и вправо) и никогда не происходит в южном или западном (вниз
и влево), поскольку процессы не могут работать, возвращаясь в прошлое.
Когда процесс A пересекает прямую I
1
на пути из r в s, он запрашивает, а затем полу-
чает в свое распоряжение принтер. Когда процесс B достигает точки t, он запрашивает
плоттер.
Особый интерес представляют заштрихованные области. Область со штриховкой из
верхнего левого угла в правый нижний представляет промежуток времени, когда оба
процесса удерживают принтер. Правило взаимного исключения делает попадание в эту
область невозможным. Аналогично этому область, имеющая другую штриховку, пред-
ставляет промежуток времени, когда оба процесса удерживают плоттер, и попадание
в эту область также невозможно.
Если система войдет в прямоугольник, ограниченный по бокам прямыми I
1
и I
2
, а сверху
и снизу прямыми I
5
и I
6
, то она в конце концов доберется до пересечения линий I
2
и I
6
и возникнет взаимоблокировка. В этот момент процесс A запрашивает плоттер, а процесс
B запрашивает принтер, но оба ресурса будут уже выделены. Получается, что небез-
опасным является весь прямоугольник и в него входить нельзя. В точке t единственным
безопасным действием будет работа процесса до тех пор, пока он не дойдет до команды I
4
.
После нее для того, чтобы добраться до точки u, подойдет любая траектория.
Важный для понимания момент заключается в том, что в точке t процесс B запра-
шивает ресурс. Система должна принять решение, предоставлять его или нет. Если
ресурс предоставляется, система попадает в небезопасную область и со временем
входит в состояние взаимоблокировки. Чтобы предупредить взаимоблокировку,
нужно приостановить процесс B до тех пор, пока процесс A не запросит и не высво-
бодит плоттер.