Проблема тупиков

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

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

О процессах известно следующее:

1. Их требования к объему памяти не будут превышать определенного предела.

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

Имеющаяся память поделена на страницы фиксированного размера, эквивалентный с точки зрения программы.

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

Такая ситуация является тупиковой. Из этой ситуации невозможно выйти без уничтожения какого-либо из процессов.

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

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

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

1. Клиент делает заем для совершения сделки, которая будет завершена за определенный промежуток времени.

2. Клиент должен указать максимальное количество талеров для этой сделки.

3. Пока заем не превысит заранее установленную потребность, клиент может увеличивать или уменьшать свой заем.

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

5. Гарантия для клиента в том, что такой момент наступит, основана на предусмотрительности банкира и на том факте, что остальные клиенты работают по таким же правилам.

Основными вопросами при решении такой задачи являются:

1. При каких условиях банкир может заключить контракт с новым клиентом?

2. При каких условиях банкир может выплатить (следующий) запрашиваемый талер клиенту, не опасаясь попасть в тупик?

Ответ на первый вопрос достаточно прост: банкир может принять любого клиента на обслуживание, чья максимальная потребность не превышает капитал банкира. Ответ на второй вопрос достаточно сложный. Сначала нужно формализовать задачу.

потребность[i] =< капитал, для любого i.

0 =< заем[i] =< потребность[i], для любого i.

требование[i] = потребность[i] - заем[i], для любого i.

наличные = капитал - СУММА_по_i заем[i], для любого i.

0 =< наличные =< капитал.

Алгоритм разрешения ситуации на выдачу талера:

integer Св_Деньги; boolean Безопасно;

boolean array Завершение_под_сомнением [1..N];

Св_Деньги := наличные;

for i := 1 step 1 until N do Завершение_под_сомнением[i] := true;

L: for i :=1 step 1 until N do begin

if (Завершение_под_сомнением [i]) and

(Требован[i] =< Св_Деньги) then begin

Завершение_под_сомнением [i] := false;

Св_Деньги := Cв_Деньги + Заем[i];

goto L;

end;

end;

if Св_Деньги = капитал then Безопасно := true

else Безопасно := false;

Данное решение основано на проверке: могут ли все клиенты завершить сделку? Можно упростить условие: если хотя бы один клиент может завершить сделку.