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

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

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

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

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

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

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

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

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

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

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

потребность[i] ≤ капитал, для всех i.

0 ≤ заем[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;

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

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

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

Если более глубоко анализировать эту проблему, то можно показать, что решение о выделении следующего запрашиваемого талера клиенту будет принято тогда, когда хотя бы для одного клиента выполниться условие ((Завершение_под_сомнением[i]) and (Треб[i]<=Св_Деньги)) и это говорит о безопасности ситуации и проверку можно приостановить.