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

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

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

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

На рис. З.б представлена модель для системы с двумя процессами и двумя ресур­сами, например принтером и плоттером. Горизонтальная ось отображает номе­ра команд, выполняемых процессом А. По вертикальной оси показаны номера

команд, выполняемых процессом В. В команде /, процесс А запрашивает принтер, в команде 1₂ ему требуется плоттер. Принтер и плоттер освобождаются командами /₃ и 7₄ соответственно. Процессу В необходим плоттер с команды /₅ по команду 1-, и принтер с команды 1₆ по команду /₈.

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

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

B ∙u Завершены оба процесса

Принтер

I₈

I₇

I₆

I₅ t

Плоттер

r s

A

p q I₁ I₂ I₃ I₄

Плоттер

Принтер

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

Особенно интересны прямоугольные области (I₁ I₅, I₄ I₈). Область (I₁ I₆, I₁ I₈- I₃ I₆, I₃ I₈) верх­него левого угла в правый нижний представляет промежуток времени, когда оба процесса занимают принтер. Правило взаимного исключения делает попадание в эту область невозможным. Вторая область (I₂ I₅, I₂ I₇- I₄ I₆, I₄ I₈) соответствует тому, что оба процесса используют плоттер, и это также невозможно.

Если система войдет в прямоугольник, ограниченный линиями I₁ и I₂ по сторо­нам и линиями /₅ и /₆ сверху и снизу, она в конце концов доберется до пересечения линий 1₂ и /₆, попадет в тупик. В этот момент процесс А запросит плоттер, а процесс В потребует принтер, но оба ресурса будут к тому времени заняты. Получается, что небезопасным является целый прямоугольник, и в него нельзя входить. В точке t

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

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

Безопасные и небезопасные состояния

Алгоритмы предотвращения взаимоблокировок, которые мы будем изучать дальше, используют информацию рис. 3.4. В любой момент времени существует текущее состояние, составленное из величин Е, А, Си R. Говорят, что состояние безопас­но, если оно не находится в тупике и существует некоторый порядок планирова­ния, при котором каждый процесс может работать до завершения, даже если все процессы вдруг захотят немедленно получить свое максимальное количество ре­сурсов. Проще всего проиллюстрировать эту идею на примере с одним ресурсом. На рис.3.7.а у нас есть состояние, в котором процесс А занимает 3 экземпляра ре­сурса, но ему в итоге могут потребоваться 9 экземпляров. Процесс В в настоящий момент занял 2 экземпляра, но позже ему могут понадобиться всего 4. Процесс С владеет двумя, но может потребовать еще 5 штук. В системе есть всего 10 экземп­ляров данного ресурса, 7 из них уже распределены, три пока свободны.

А 3 9 А 3 9 А 3 9 А 3 9 А 3 9

В 2 4 В 4 4 В 0 - В 0 - В 0 -

С 2 7 С 2 7 С 2 7 С 7 7 С 0 -

Свободно 3 Свободно 1 Свободно 5 Свободно 0 Свободно 7

а б в г д

Рис. 3.7. Демонстрация того, что состояние а безопасно

Состояние на рис. 3.7.а безопасно, потому что существует такая последователь­ность предоставления ресурсов, которая позволяет завершиться всем процессам. А именно, планировщик может просто запустить в работу только процесс В на то время, пока он запросит и получит два дополнительных экземпляра ресурса, что приведет к состоянию, изображенному на рис. 3.7, б. Когда процесс В закончится, мы получим состояние рис. 3.7, в. Затем планировщик может запустить процесс С, что со временем приведет нас к ситуации рис. 3.7, г. По завершении процесса С мы получим рис. 3.7, д. Теперь процесс Л наконец может занять необходимые ему шесть экземпляров ресурса и также успешно завершиться. Таким образом, состоя­ние на рис. 3.7, а является безопасным, потому что система может избежать тупи­ка с помощью аккуратного планирования процессов.

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

А 3 9 А 4 9 А 4 9 А 4 9

В 2 4 В 2 4 В 4 4 В 4 4

С 2 7 С 2 7 С 2 7 С 2 7

Свободно 3 Свободно 2 Свободно 0 Свободно 4

а б в г

Рис. 3.8. Демонстрация того, что состояние б небезопасно

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

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

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

Алгоритм планирования, позволяющий избегать взаимоблокировок, был разра­ботан Дейкстрой (Dijkstra, [96]) и носит название алгоритма банкира. Он пред­ставляет собой расширение алгоритма обнаружения тупиков, о котором было рас­сказано в разделе «Обнаружение взаимоблокировки при наличии одного ресурса каждого типа» данной главы. Модель алгоритма основана на примере банкира в маленьком городке, имеющего дело с группой клиентов, которым он выдал ряд кредитов. Алгоритм проверяет, ведет ли выполнение каждого запроса к небез-

опасному состоянию. Если да, то запрос отклоняется. Если удовлетворение запроса к ресурсу приводит к безопасному состоянию, ресурс предоставляется процессу. На рис. 3.9, а мы видим четырех клиентов: Л, Б, С и D, каждый из которых полу­чил определенное количество единиц кредита (например, 1 единица равна 1 К дол­ларов). Банкир знает, что не всем клиентам понадобится их максимальный кредит немедленно, поэтому он зарезервировал только 10 единиц, а не все 22, которые требуются клиентам. (Чтобы провести аналогию с компьютерной системой, счи­таем, что клиенты — это процессы, единицами, скажем, являются накопители на магнитной ленте, а банкир — это операционная система.)

А 3 9 А 4 9 А 4 9

В 2 4 В 2 4 В 4 4

С 2 7 С 2 7 С 2 7

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

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