Глава_3 (1085731), страница 4

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

Текст из файла (страница 4)

. . . . . . . .

С_n1 С_n2 С_n3 …. С_nм R_n1 R_n2 R_{n3 ……} R_nм

С трока n в данный момент Строка 2 нужна процессу 2

Предоставлена процессу n

Рис. 3.4. Четыре структуры данных, необходимые для алгоритма обнаружения тупиков

В любой момент времени некоторые из ресурсов могут оказаться занятыми и, соответственно, недоступны. Пусть А будет вектором доступных ресурсов, где Аi , равно количеству экземпляров ресурса i, доступных в текущий момент (то есть не использующихся). Если оба накопителя на магнитной ленте заняты, A₁) будет равно 0.

Теперь нам нужны два массива: С — матрица текущего распределения и R — матрица запросов, i-я строка в матрице С говорит о том, сколько представителей каждого класса ресурсов в данный момент использует процесс Р_i. Таким образом, С_ij — это количество экземпляров ресурса j, которое занимает процесс i. Аналогич­но, Rij — это количество экземпляров ресурса j, которые хочет получить процесс Рi. Эти четыре структуры показаны на рис. 3.4.

Для этих четырех структур данных существует важный инвариант. В принци­пе каждый ресурс или занят, или свободен. Это наблюдение означает, что

n

∑C_ij + A_j = E_j

i=1

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

Алгоритм обнаружения взаимоблокировок основан на сравнении векторов. Определим, что для двух векторов А и В отношение А < В означает, что каждый эле­мент вектора А меньше или равен соответствующему элементу вектора В. Мате­матически это запишется так: А<В тогда и только тогда, когда A_j < B_j для

1 ≤i ≤ т.

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

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

1. Ищем немаркированный процесс P_j , для которого i3-я строка матрицы R
   меньше вектора А или равна ему.

2. Если такой процесс найден, прибавляем i-ю строку матрицы С к вектору А,
   маркируем процесс и возвращаемся к шагу 1.

3. Если таких процессов не существует, работа алгоритма заканчивается.

Завершение алгоритма означает, что все немаркированные процессы, если та­кие есть, попали в тупик.

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

Для иллюстрации работы алгоритма обнаружения тупиков рассмотрим рис. 3.5. Здесь у нас есть три процесса и четыре класса ресурсов, которые мы произвольно назвали так: накопители на магнитной ленте, плоттеры, сканеры и устройство для чтения компакт-дисков. Процесс 1 использует один сканер. Процесс 2 занял два накопителя на магнитной ленте и устройство для чтения компакт-дисков. Про­цесс 3 занимает плоттер и два сканера. Каждый процесс нуждается в дополнитель­ном устройстве, как показывает матрица R..

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

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

А = (2 2 2 0).

С этого момента может выполняться процесс 2, по окончании возвращая свои ресурсы в систему. Мы получим:

А = (4 2 2 1).

Вектор существующих ресурсов Е= (4 2 3 1), где 4 –кол-во накопителей на магнитной ленте, 2-плоттеров, 3 – сканеров и 1- компакт-дисков. Соответственно вектор доступных ресурсов А= ( 2 1 0 0 ).

Теперь может работать оставшийся процесс. В этой системе не возникает взаи­моблокировки.

Матрица текущего распределения Матрица запросов

0 0 1 0 2 0 0 1

С= 2 0 0 1 R= 1 0 1 0

0 1 2 0 2 1 0 0

Рис. 3.5. Пример использования алгоритма обнаружения тупиков

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

Мы уже знаем, как обнаружить взаимоблокировки, и появляется вопрос: когда нужно искать их возникновение. Можно проверять систему каждый раз, когда за­прашивается очередной ресурс. Это, конечно, позволит обнаружить тупик макси­мально рано (насколько это возможно), но такая операция может оказаться доро­гой в смысле времени загрузки процессора. Альтернативный подход: проверять систему каждые k минут, или, может быть, только когда степень занятости про­цессора меньше некоторого граничного значения. Учет загрузки процессора име­ет смысл, потому что при достаточно большом количестве заблокированных про­цессов работоспособных процессов в системе останется немного, и процессор часто будет незанятым.

Выход из взаимоблокировки

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

личные способы ликвидации взаимоблокировок. Однако ни один из них не явля­ется особо заманчивым.

Восстановление при помощи принудительной выгрузки ресурса

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

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

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

Восстановление через откат

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

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

Восстановление путем уничтожения процессов

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

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

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

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

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

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

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

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

Характеристики

Список файлов книги