Лекция: Возврат ресурса
Если ресурс недоступен, когда он требуется, то запрашивающий его процесс вынужден ждать. В некоторых операционных системах при неудачном обращении к ресурсу процесс автоматически блокируется и возобновляется только после того, как ресурс становится доступным. В других системах запрос ресурса, получивший отказ, возвращает код ошибки, тогда вызывающий процесс может подождать немного и повторить попытку заново.
Процесс, чье обращение к ресурсу оказалось неудачным, обычно дальше попадает в короткий цикл: запрос ресурса, затем режим ожидания, потом очередная попытка. Хотя этот процесс не блокирован, он во всех смыслах ведет себя как заблокированный, поскольку не может выполнить никакой полезной работы. В дальнейшем мы будем предполагать, что когда процессу отказывается в предоставлении ресурса, он переходит в режим ожидания.
Истинная природа запросов ресурсов сильно зависит от системы. В некоторых системах существует системный вызов request, позволяющий процессам запрашивать ресурсы явно. В других случаях единственный вид ресурсов, известных операционной системе, – это специальные файлы, которые в каждый данный момент времени могут открыть только один процесс. Они открываются с помощью обычного вызова open. Если файл уже используется, вызывающая программа блокируется до тех пор, пока текущий владелец файла не закроет его.
Рис. 88
Для того чтобы произошла взаимоблокировка, должны выполниться все эти четыре условия. Если хоть одно из них отсутствует, тупиковая ситуация невозможна. Следует отметить, что каждое условие относится к стратегии определения того, что в системе позволяется, а что – нет.
Рассмотрим еще один пример тупика (циклическое ожидание). Пусть двум процессам, выполняющимся в режиме мультипрограммирования, для выполнения их работы нужно два ресурса, например, принтер и диск. И пусть после того, как процесс А занял принтер (установил блокирующую переменную), он был прерван. Управление получил процесс В, который сначала занял диск, но при выполнении следующей команды был заблокирован, так как принтер оказался уже занятым процессом А. Управление снова получил процесс А, который в соответствии со своей программой сделал попытку занять диск и был заблокирован: диск уже распределен процессу В. В таком положении процессы А и В могут находиться сколь угодно долго.
В зависимости от соотношения скоростей процессов, они могут либо совершенно независимо использовать разделяемые ресурсы, либо образовывать очереди к разделяемым ресурсам, либо взаимно блокировать друг друга. Тупики могут быть предотвращены на стадии написания программ, то есть программы должны быть написаны таким образом, чтобы тупик не мог возникнуть ни при каком соотношении взаимных скоростей процессов.
Начнем с самого простого варианта: в системе существует только один ресурс каждого типа. Подобная система могла бы иметь один сканер, одно устройство для записи компакт-дисков, один плоттер и один накопитель на магнитной ленте, то есть не более чем по одному представителю каждого класса. Другими словами, мы исключаем из рассмотрения системы с двумя одновременно подключенными принтерами.
Рис. 89
Для такой системы можно сконструировать граф ресурсов вида, продемонстрированного на рис. 89. Если этот граф содержит один или больше циклов, значит, произошла взаимоблокировка, и блокирован любой процесс, являющийся частью цикла. Если в графе нет циклов, система не попала в тупик. В качестве примера более сложной системы, чем те, которые мы рассматривали до сих пор, обсудим систему с семью процессами, обозначенными буквами от A до G, и шестью ресурсами, обозначенными буквами от R до W. Состояние системы, то есть то, какой процесс владеет каким ресурсом и какой ресурс запрашивается процессом в данный момент, соответствует следующему списку:
Процесс A занимает ресурс R и хочет получить ресурс S.
1. Процесс B ничего не использует, но хочет получить ресурс T.
2. Процесс C ничего не использует, но хочет получить ресурс S.
3. Процесс D занимает ресурс U и хочет получить ресурсы S и T.
4. Процесс E занимает ресурс T и хочет получить ресурс V.
5. Процесс F занимает ресурс Wn хочет получить ресурс S.
6. Процесс C занимает ресурс V хочет получить ресурс U.
Вопрос: заблокирована ли эта система и если да, то какие процессы в этом участвуют?
Чтобы ответить на этот вопрос, мы можем составить граф ресурсов. Этот граф содержит один цикл, который виден при визуальном обследовании. Изучая его, можно заметить, что процессы D, E, G заблокированы. Процессы A, C и F не попали в тупик, потому что любому из них можно предоставить ресурс 5, после чего процесс, получивший ресурс, закончит свою работу и вернет ресурс. Затем два других процесса по очереди могут получить ресурс и также успешно выполнить свою работу.
Несмотря на то, что в простом графе относительно легко зрительно различить взаимоблокировку процессов, для использования такой схемы в настоящей системе нам необходим формальный алгоритм, выявляющий тупики. Известно множество алгоритмов, обнаруживающих циклы в направленных графах. Ниже мы рассмотрим простой алгоритм, который изучает граф и завершается или когда находит цикл, или когда показывает, что циклов в этом графе не существует. Он использует одну структуру данных – список узлов L. Во время работы алгоритма на ребрах графа будет ставиться метка, говорящая о том, что их уже проверили, это делается во избежание повторной проверки.
Алгоритм работает, осуществляя пять перечисленных ниже шагов.
Для каждого узла N в графе выполняются следующие пять шагов, где N является начальным узлом.
Задаем начальные условия: L – пустой список, все ребра не маркированы. 3. Текущий узел добавляем в конец списка L и проверяем количество появлений узла в списке. Если узел присутствует в двух местах, граф содержит цикл (записанный в список L), и работа алгоритма завершается.
Для заданного узла смотрим, выходит ли из него хотя бы одно немаркированное ребро. Если да, то переходим к шагу 5, если нет, то переходим к шагу 6.
Случайным образом выбираем любое немаркированное исходящее ребро и отмечаем его. Затем по нему переходим к новому текущему узлу и возвращаемся к шагу 3.
Теперь мы зашли в тупик. Удаляем последний узел из списка и возвращаемся к предыдущему узлу, то есть тому, который был текущим перед тупиковым узлом. Обозначаем его текущим узлом и возвращаемся к шагу 3. Если это первоначальный узел, граф не содержит циклов, и алгоритм завершается.
Этот алгоритм по очереди берет каждый узел в качестве корня того, что, как он надеется, окажется деревом, и выполняет в дереве поиск в глубину. Если в процессе обхода алгоритм возвращается к уже встречавшемуся узлу, то он нашел цикл. Если алгоритм обходит все ребра из какого-нибудь заданного узла, то он возвращается к предыдущему узлу. Если он возвращается к корню и не может идти дальше, то подграф текущего узла не содержит циклов. Если данное свойство сохраняется для всех узлов, значит, полный граф не содержит циклов, а система не заблокирована.
Чтобы увидеть, как работает описанный алгоритм на практике, воспользуемся графом на рис. 89 (слева). Порядок обработки узлов произвольный, поэтому будем исследовать их слева направо и сверху вниз. Тогда алгоритм начнет поиск с узла R, затем последовательно с узлов A, B, C, S, D, T,E,Fa т. д. Если мы натолкнемся на цикл, алгоритм остановится.
Мы начинаем с узла R и инициализируем L как пустой список. Затем добавляем узел R в список, переходим к единственно возможному узлу A, и его также добавляем к списку L, получая L = [R, A]. Из узла A следуем к узлу S, получая L = [R, A, S]. Узел S не имеет исходящих ребер, следовательно, это тупик, который заставляет нас вернуться к узлу A. Так как у узла A тоже нет немаркированных исходящих ребер, мы возвращаемся к узлу R, завершая, таким образом, его исследование.
Теперь снова начнем поиск, стартуя с узла A и предварительно вернув список L в исходное состояние. Эта часть алгоритма тоже быстро остановится, поэтому выполним процесс заново, начиная с узла B. Из узла B алгоритм будет следовать исходящим ребрам до тех пор, пока не достигнет узла D; в это время список будет таким: L = [В, Т, Е, V, G, U, D]. Теперь мы должны сделать (случайный) выбор. Если выбрать узел S, мы попадаем в тупик и возвращаемся к узлу D. Во второй раз выбираем узел T и получаем измененный список L = [В, Т, Е, V, G, U, D, T]; в этот момент мы обнаруживаем цикл и останавливаем алгоритм.
Этот алгоритм далек от оптимального. Тем не менее он демонстрирует существование алгоритма для обнаружения взаимоблокировок.
Рис. 90
В некоторых случаях, когда тупиковая ситуация образована многими процессами, использующими много ресурсов, распознавание тупика является нетривиальной задачей. Существуют формальные, программно-реализованные методы распознавания тупиков, основанные на ведении таблиц распределения ресурсов и таблиц запросов к занятым ресурсам. Анализ этих таблиц позволяет обнаружить взаимные блокировки.
Когда в системе существует несколько экземпляров некоторых из ресурсов, для обнаружения взаимоблокировок необходим другой метод. Сейчас мы расскажем об основанном на матрицах алгоритме, обнаруживающем тупики среди n процессов, от P1, до Рn. Пусть m – это число классов ресурсов, причем в системе Е1 ресурсов класса 1, Е2 ресурсов класса 2 и, в общем, Ei, ресурсов класса i (где 1 <= i <= m). E – это вектор существующих ресурсов. Он передает общее количество имеющихся в наличии экземпляров каждого ресурса. Например, если класс 1 представляет собой накопители на магнитных лентах, то Е1 = 2 означает, что в системе есть два магнитофона. В любой момент времени некоторые из ресурсов могут оказаться занятыми и, соответственно, недоступны. Пусть A будет вектором доступных ресурсов, где Ai равно количеству экземпляров ресурса i, доступных в текущий момент (то есть не использующихся). Если оба накопителя на магнитной ленте заняты, Ai будет равно 0.
Теперь нам нужны два массива: C – матрица текущего распределения и R – матрица запросов, i-я строка в матрице C говорит о том, сколько представителей каждого класса ресурсов в данный момент использует процесс Рi. Таким образом, Cij – это количество экземпляров ресурса j', которое занимает процесс i. Аналогично, Rij – это количество экземпляров ресурса j, которые хочет получить процесс Рi.
Для этих четырех структур данных существует важный инвариант. В принципе каждый ресурс или занят, или свободен. Это наблюдение означает, что если сложить все экземпляры ресурса j, предоставленные процессам и доступные в данный момент, то в результате мы получим существующее в системе количество экземпляров этого класса ресурсов.
Алгоритм обнаружения взаимоблокировок основан на сравнении векторов. Определим, что для двух векторов A и B отношение A <= B означает, что каждый элемент вектора A меньше или равен соответствующему элементу вектора B. Математически это запишется так: A <= B тогда и только тогда, когда Ai, <= Bi для 1 < i < m.
Пусть в исходном положении все процессы не маркированы. По мере продвижения алгоритма на процессы будет ставиться отметка, служащая признаком того, что они могут закончить свою работу и, следовательно, не находятся в тупике. После завершения алгоритма известно, что любой немаркированный процесс находится в тупиковой ситуации.
Завершение алгоритма означает, что все немаркированные процессы, если такие есть, попали в тупик.
Если же тупиковая ситуация возникла, то не обязательно снимать с выполнения все заблокированные процессы. Можно снять только часть из них, при этом освобождаются ресурсы, ожидаемые остальными процессами, можно вернуть некоторые процессы в область свопинга, можно совершить «откат» некоторых процессов до так называемой контрольной точки, в которой запоминается вся информация, необходимая для восстановления выполнения программы с данного места. Контрольные точки расставляются в программе в местах, после которых возможно возникновение тупика.
Рис. 91