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

Тупики

Приведенный выше пример поможет проиллюстрировать еще одну проблему синхронизации - взаимные блокировки, называемые также дедлоками (deadlocks), клинчами (clinch) или тупиками. Если переставить местами операции P(e) и P(b) в программе "писателе", то при некотором стечении обстоятельств эти два процесса могут взаимно заблокировать друг друга. Действительно, пусть "писатель" первым войдет в критическую секцию и обнаружит отсутствие свободных буферов; он начнет ждать, когда "читатель" возьмет очередную запись из буфера, но "читатель" не сможет этого сделать, так как для этого необходимо войти в критическую секцию, вход в которую заблокирован процессом "писателем".

Рассмотрим еще один пример тупика. Пусть двум процессам, выполняющимся в режиме мультипрограммирования, для выполнения их работы нужно два ресурса, например, принтер и диск. На рисунке 7,а показаны фрагменты соответствующих программ. И пусть после того, как процесс А занял принтер (установил блокирующую переменную), он был прерван. Управление получил процесс В, который сначала занял диск, но при выполнении следующей команды был заблокирован, так как принтер оказался уже занят процессом А. Управление снова получил процесс А, который в соответствии со своей программой сделал попытку занять диск и был заблокирован: диск уже распределен процессу В. В таком положении процессы А и В могут находиться сколь угодно долго.

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

Рисунок 7 – (а) фрагменты программ А и В, разделяющих принтер и диск; (б) взаимная блокировка (клинч); (в) очередь к разделяемому диску; (г) независимое использование ресурсов

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

Проблема тупиков включает в себя следующие задачи:

· предотвращение тупиков,

· обход тупиков;

· распознавание тупиков,

· восстановление системы после тупиков.

“Алгоритм банкира” (предложил Дейкстра (Dijkstra)) напоминает процедуру принятия решения, может ли банк безопасно выдать заем.

Для реализации этого метода необходимо выполнить следующие правила:

1. Заранее объявлять все необходимые заданию ресурсы.

2. Перед назначением ресурса осуществлять проверку на возможность возникновения клинчей. Если эта возможность исключена, то ресурс можно назначить.

Рисунок 8 – Алгоритм Банкира

Каждому процессу поставлено в соответствие целое число i(1<=i<=N). Процессу i соответствует его максимальная потребность в устройствах МАКС[i], количество устройств, выделенных ему в данный момент (ВЫДЕЛУСТР[i]), полагающийся ему остаток (ОСТАТОК[i]) и признак (МОЖЕТ_НЕ_ОКОНЧИТЬСЯ[i]). Система заводит глобальную переменную ОБЩ, обозначающую общее число имеющихся в системе устройств. В начале работы неизвестно, может ли какой-либо процесс окончиться (МОЖЕТ_НЕ_ОКОНЧИТЬСЯ[i]=true для всех i). Каждый раз, когда какой-то ОСТАТОК может быть выделен из числа остающихся незанятыми устройств, предполагается, что соответствующий процесс работает, пока не окончится, а затем его устройства освобождаются. Если в конце концов все устройства освободятся, значит, все процессы могут окончиться и система находится в безопасном состоянии. Если состояние системы не безопасное, то она не удовлетворяет рассматриваемый запрос.

Begin

СВОБУСТР:=ОБЩУСТР;

For i:= 1 to N do

Begin

СВОБУСТР:= СВОБУСТР – ВЫДЕЛУСТР[i];

МОЖЕТ_НЕ_ОКОНЧИТЬСЯ[i]:=true;

ОСТАТОК[i]:= МАКС[i]-ВЫДЕЛУСТР[i];

End;

ПРИЗНАК:=true;

WHILE (ПРИЗНАК) DO

ПРИЗНАК:=false;

For i:=1 to N do

Begin

If МОЖЕТ_НЕ_ОКОНЧИТЬСЯ[i] and (ОСТАТОК[i] <= СВОБУСТР)

Then begin

МОЖЕТ_НЕ_ОКОНЧИТЬСЯ[i]:=false;

СВОБУСТР:= СВОБУСТР+ ВЫДЕЛУСТР[i];

ПРИЗНАК:=true

End;

End;

End;

End;

If СВОБУСТР= ОБЩУСТР then состояние системы БЕЗОПАСНОЕ

Else состояние системы НЕБЕЗОПАСНОЕ

Рассмотрим систему, в которой процессы конкурируют из-за лентопротяжных устройств. Если процессу предоставить все лентопротяжные устройства, которые ему нужны, он будет работать в течение лишь конечного отрезка времени. Каждый процесс, до того как он получит возможность запрашивать какие-либо лентопротяжные устройства, должен указать максимальное число этих устройств, которое ему может когда-либо понадобиться одновременно. Программа, распределяющая лентопротяжные устройства, должна удовлетворять запросы на эти устройства, пока это не может привести к тупику. То есть должна реализовываться такая последовательность выполнения процессов, при которой каждый процесс может окончиться. Пусть, например, система состоит из трех процессов и десяти лентопротяжных устройств. Каждому процессу соответствуют его максимальная потребность в лентопротяжных устройствах, количество их, выделенное процессу в данный момент, и количество, которое он еще имеет право потребовать. На рис. 9 (а) изображено типичное состояние системы. С точки зрения вероятности тупика худший случай из возможных — это если каждый процесс запросит все, что ему еще полагается. Если при таких обстоятельствах все процессы могут окончиться, то рассматриваемое состояние для системы безопасно. В частности, на рис. 1(а) изображено безопасное состояние. Теперь допустим, что процесс С запрашивает еще два лентопротяжных устройства. Если запрос процесса С будет удовлетворен и если все процессы запросят полагающиеся им остатки (рис. (б)), то система попа­дет в тупик. Поэтому удовлетворять запрос С опасно.

(а) Имя Максимальная

процесса потребность Выделено Остаток

А 4 2 2

В 6 3 3

С 8 2 6

(б) Имя Максимальная

процесса потребность Выделено Остаток

А 4 2 2

В 6 3 3

С 8 4 4

Рисунок 9 – Безопасное(а) и опасное(б) состояние системы

Недостатки Алгоритма Банкира

1. Алгоритм исходит из фиксированного количества ресурсов. Ресурсы выходят из строя, находятся на ремонте. Поэтому резерв практически может и не оказаться. Количество единиц ресурсов определяется при генерации.

2. Требуется более или менее ПОСТОЯННЫЕ числа одновременно работающих процессов (некоторого статического режима). Однако в современных системах их число постоянно меняется весьма динамически. Поэтому становится проблематично уследить за заявками и текущими потребностями.

3. При существующей системе распределения ресурсов возможны длительные периоды нахождения процессов в состоянии "приостановки".

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

Автоматическое обнаружение тупиков (алгоритм Медника)

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

Ниже, на примере, рассматривается один из алгоритмов обнаружения тупиков (алгоритмы Медника).

Пусть в какой-то период времени 3 процесса разделяют 5 устройств одного типа. Факты запроса устройств процессами представим в виде таблицы:

T	У1	У2	У3	У4	У5

Рисунок 10 – Запросы процессов на ресурсы

Произвольно нумеруем все ресурсы и процессы в системе. Создаем таблицы, в которых собиралась бы вся информация о назначении ресурсов процессами (РАСПРЕД) и о процессах, блокированных при попытке обращения к ресурсу (БЛК).

Заносим в эти таблицы соответствующую информацию при всяком назначении или освобождении ресурса согласно следующему алгоритму:

НАЧАЛО «МЕДНИК»

(*Процесс Рj запрашивает занятый ресурс Уi*)

(*ПОДГОТОВИТЬ*)

К = РАСПРЕД (i) (*К – номер процесса владеющего ресурсом Уi*)

ЦИКЛ-ПОКА БЛК (К) и J¹K

J = К

N = БЛК (К) (*N – номер ресурса, которого ожидает*)

К = РАСПРЕД (N) (* рассматриваемый процесс*)

ВСЕ-ЦИКЛ

ЕСЛИ

J = К

ТУПИК

ИНАЧЕ

БЛК (J) = i (*Перевести процесс Рi в состояние ожидания*)

ВСЕ-ЕСЛИ

КОНЕЦ «МЕДНИК»

Например, в первый момент времени заполняются строчки 1,3,4 таблицы РАСПРЕДЕЛ, а во второй – строчки 2,5.

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

В третий момент времени Р1 запрашивает У1, которое принадлежит процессу Р3 (К=РАСПРЕДЕЛ (1)=3). Так как J¹К, а также БЛК (3) = «» - тело цикла в алгоритме на рис. 3 не выполняется и БЛК (1) = 1.

В четвертый момент времени Р3 запрашивает У2. Получаем:

К = 2 J = 3 и БЛК (2) = «»

Поэтому: БЛК (3) = 2.

ТАБЛИЦА РАСПРЕДЕЛЕНИЯ РЕСУРСОВ /РАСПРЕД/

Номер ресурса	Номер процесса, которому распределен ресурс
	3 (1)
	2 (2)
	1 (1)
	2 (1)
	2 (2)

ТАБЛИЦА БЛОКИРОВАННЫХ ПРОЦЕССОВ /БЛК/

Номер процесса	Номер ресурса, которого ожидает данный процесс
	1 (3)
	2 (4)

Рисунок 11 - Таблицы распределения ресурсов и блокированных процессов

В пятый момент времени Р2 запрашивает У3, которым владеет процесс Рi (К = 1). В то же время процесс Р1 ожидает момента времени, когда освободится устройство У1, которым владеет процесс 3. В свою очередь процесс 3 ожидает освобождения устройства У2, которым владеет процесс Р2 (J = К). Таким образом, система попала в тупик в пятый момент времени.

Дата добавления: 2014-01-04