Лекция: Траектории ресурсов

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

На рис. 92 представлена модель для системы с двумя процессами и двумя ресурсами, например принтером и плоттером. Горизонтальная ось отображает номера команд, выполняемых процессом A. По вертикальной оси показаны номера команд, выполняемых процессом B. В команде 11, процесс A запрашивает принтер, в команде 12 ему требуется плоттер. Принтер и плоттер освобождаются командами 13 и 14 соответственно. Процессу B необходим плоттер с команды 15 по команду 17 и принтер с команды 16 по команду 18.

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

Когда процесс A пересекает линию 11, на отрезке от точки r до точки s, он запрашивает и получает принтер. Когда процесс B достигает точки t, он запрашивает плоттер.

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

Если система войдет в прямоугольник, ограниченный линиями 11 и 12 по сторонам и линиями I5 и I6 сверху и снизу, она в конце концов доберется до пересечения линий I1 и I6 и попадет в тупик. В этот момент процесс A запросит плоттер, а процесс B потребует принтер, но оба ресурса будут к тому времени заняты. Получается, что небезопасным является целый прямоугольник, и в него нельзя входить. В точке t единственно безопасный вариант состоит в том, чтобы оставить процесс A работать до тех пор, пока он не достигнет команды 14. После нее любая траектория дойдет до точки u.

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

На рис. 93 на первой части рисунка у нас есть состояние, в котором процесс A занимает 3 экземпляра ресурса, но ему в итоге могут потребоваться 9 экземпляров. Процесс B в настоящий момент занял 2 экземпляра, но позже ему могут понадобиться всего 4. Процесс C владеет двумя, но может потребовать еще 5 штук. В системе есть всего 10 экземпляров данного ресурса, 7 из них уже распределены, три пока свободны.

Состояние на первом рисунке первого ряда безопасно, потому что существует такая последовательность предоставления ресурсов, которая позволяет завершиться всем процессам. А именно, планировщик может просто запустить в работу только процесс B на то время, пока он запросит и получит два дополнительных экземпляра ресурса, что приведет к состоянию, изображенному на втором рисунке первого ряда. Когда процесс B закончится, мы получим состояние на рисунке 3 (первого ряда). Затем планировщик может запустить процесс C, что со временем приведет нас к ситуации, когда свободно 0. По завершении процесса C мы получим ситуацию, изображенную на последнем рисунке.

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

Рис. 93

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

В итоге процесс B успешно завершается, и мы получаем ситуации, изображенные на следующем рисунке. В этом месте мы застряли: в системе осталось только четыре свободных экземпляра ресурса, а каждому из активных процессов необходимо пять. И не существует последовательности действий, гарантирующей успешное завершение всех процессов. Следовательно, решение о предоставлении ресурса, которое передвинуло систему из положения на рисунке 1 к рисунку 2, привело ее из безопасного в небезопасное состояние. Если из ситуации на втором рисунке запустить процесс A или C, мы не выйдем из тупика. Теперь, оглядываясь назад, можно уверенно сказать, что нельзя было выполнять запрос процесса A.

Следует отметить, что небезопасное состояние само по себе не является тупиком. Начав с рисунка 2, система может проработать некоторое время. Фактически даже может успешно завершиться один процесс. Кроме того, возможна ситуация, что процесс A сможет освободить один ресурс до следующего своего запроса, позволяя успешно завершиться процессу C, а системе избежать взаимной блокировки. Таким образом, разница между безопасным и небезопасным состоянием заключается в следующем: в безопасном состоянии система может гарантировать, что все процессы закончат свою работу, а в небезопасном состоянии такой гарантии дать нельзя.

Рис. 94

Алгоритм планирования, позволяющий избегать взаимоблокировок, был разработан Дейкстрой и носит название алгоритма банкира. Он представляет собой расширение алгоритма обнаружения тупиков, о котором было рассказано в разделе «Обнаружение взаимоблокировки при наличии одного ресурса каждого типа» данной главы. Модель алгоритма основана на примере банкира в маленьком городке, имеющего дело с группой клиентов, которым он выдал ряд кредитов. Алгоритм проверяет, ведет ли выполнение каждого запроса к опасному состоянию. Если да, то запрос отклоняется. Если удовлетворение запроса к ресурсу приводит к безопасному состоянию, ресурс предоставляется процессу. На первом рисунке мы видим четырех клиентов: A, B, C и D, каждый из которых получил определенное количество единиц кредита (например, 1 единица равна 1 К долларов). Банкир знает, что не всем клиентам понадобится их максимальный кредит немедленно, поэтому он зарезервировал только 10 единиц, а не все 22, которые требуются клиентам. (Чтобы провести аналогию с компьютерной системой, считаем, что клиенты – это процессы, единицами, скажем, являются накопители на магнитной ленте, а банкир – это операционная система).

Клиенты вращаются в соответствующем бизнесе, время от времени прося у банка ссуды (то есть запрашивая ресурсы). В некоторый момент возникает ситуация, показанная на втором рисунке. Это состояние безопасно, потому что остались две единицы, и банкир может задержать все обращения, кроме запросов клиента или процесса C, таким образом, позволяя процессу C завершиться и вернуть все четыре отданных ему ресурса. Имея на руках четыре единицы, банкир может отдать их или клиенту D, или B, обеспечивая их необходимыми единицами, и т. д.

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

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

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

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

Рис. 95

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

· Ищем в матрице R строку, соответствующую процессу, чьи неудовлетворенные потребности ресурсов меньше или равны вектору A. Если такой строки не существует, то система в конце концов попадет в тупик, так как ни один процесс не может проработать до успешного завершения.

· Допускаем, что процесс, строку которого выбрали в пункте 1, запрашивает все необходимые ресурсы (гарантируется, что это возможно) и заканчивает работу. Отмечаем этот процесс как завершенный и прибавляем все его ресурсы к вектору A.

· Повторяем шаги 1 и 2 до тех пор, пока или все процессы будут помечены как завершенные – и состояние в этом случае является безопасным, или произойдет взаимоблокировка – тогда состояние небезопасно.

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

Рис. 96