Стратегии предотвращения тупиков

 

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

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

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

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

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

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

 

 

Алгоритм банкира

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

Рассмотрим систему, в которой процессы конкурируют из-за устройств вывода информации. Каждый процесс, до того как он получит возможность запрашивать доступ к устройству вывода, должен указать максимальное число устройств, которое ему может понадобиться одновременно. Алгоритм должен обеспечивать реализацию такой последовательности выполнения процессов, при которой не возникает тупиков, т.е. каждый процесс может быть завершен.

Пусть система состоит из трех процессов, которые пронумерованы I=1..N, где N=3 и десяти устройств вывода, КОЛ=10.

Каждому процессу соответствует:

· максимальная потребность в устройствах, МАКС[I], где I номер процесса;

· количество устройств, выделенных процессу в данный момент ВЫД[I];

· оставшееся количество, которое процесс может еще потребовать ОСТ[I].

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

 

 

Таблица 1

 

Номер процесса, I Максимальная потребность, МАКС[I] Выделено ВЫД[I] Остаток ОСТ[I]

 

 

Таблица 2

 

Номер процесса, I Максимальная потребность, МАКС[I] Выделено ВЫД[I] Остаток ОСТ[I]

 

 

Алгоритм, предложенный Дейкстрой - алгоритм банкира как раз и предназначен для выяснения ведет ли удовлетворение некоторого запроса к опасному состоянию. Заметим, что новое состояние безопасно тогда и только тогда, когда каждый процесс все же может завершиться (обозначим это таким образом: МОЖЕТ_НЕ_ЗАВЕРШИТЬСЯ[I]=false для каждого I-го процесса).

 

const КОЛ=10;N=3{общее количество устройств вывода и процессов,

соответственно}

var I : 1..N;{текущий номер процесса}

МАКС, ВЫД, ОСТ : array [1..N] of integer;{ соответственно,

максимальное, выделенное, оставшееся количество устройств, определенное каждому процессу в текущий момент времени, }

СВОБ : 1..N;{общее количество свободных устройств в текущий

момент времени}

ПРИЗ : boolean;

МОЖЕТ_НЕ_ЗАВЕРШИТЬСЯ : array [1..N] of boolean;

. . .

{здесь мы не рассматриваем процесс заполнения массивов МАКС и ВЫД в каждый момент времени, согласно данным, например таб. 1,2}

Begin

СВОБ:=КОЛ;

for I:=1 to N do

Begin

СВОБ:= СВОБ-ВЫД[I];

МОЖЕТ_НЕ_ЗАВЕРШИТЬСЯ[I]:=true;{в начале работы неизвестно может ли завершиться каждый процесс, поэтому начальное значение этого признака устанавливаем true }

ОСТ[I]:=МАКС[I] - ВЫД[I]{расчет оставшихся устройств для каждого процесса}

End;

ПРИЗ:=true;{признак завершения цикла проверок}

While (ПРИЗ) do

Begin

ПРИЗ:=false;

for I:=1 to N do

Begin

if (МОЖЕТ_НЕ_ЗАВЕРШИТЬСЯ[I]) and (ОСТ[I]<=CВОБ) then

Begin

МОЖЕТ_НЕ_ЗАВЕРШИТЬСЯ[I]:=false;

СВОБ:=СВОБ+ВЫД[I];

ПРИЗ:=true

End

End

End

End;

Каждый раз, когда какой-то остаток, ОСТ[I], может быть выделен процессу из числа свободных устройств, предполагается, что соответствующий процесс работает до завершения, а затем его устройства освобождаются. Если, в конце концов, все устройства освободятся, значит все процессы могут завершиться и система находится в безопасном состоянии.

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

- исходит из фиксированного числа распределяемых ресурсов, а на практике оно не всегда бывает фиксировано;

- требует, чтобы число пользователей оставалось постоянным, что не является реалистичным для мультипрограммных систем;

- требует, чтобы процессы гарантированно “платили долги”, т.е. возвращали выделенные им ресурсы в течение некоторого конечного времени, что также затруднительно в реальных условиях;



- требует, чтобы пользователи заранее указывали свои максимальные потребности в ресурсах, что усложняется по мере того, как распределение ресурсов становится все более динамичным, а системы более “дружественны” по отношению к пользователю (зачастую пользователь вообще не имеет представления о том, какие ресурсы ему потребуются).

<== предыдущая лекция | следующая лекция ==>
Тупики. Необходимые условия возникновения тупиков. | Обнаружение тупиков. Графы распределения ресурсов


Дата добавления: 2017-11-04; просмотров: 14; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию, введите в поисковое поле ключевые слова и изучайте нужную вам информацию.

Поделитесь с друзьями:

Если вам понравился данный ресурс вы можете рассказать о нем друзьям. Сделать это можно через соц. кнопки выше.
helpiks.org - Хелпикс.Орг - 2014-2017 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.012 сек.