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



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

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

  1. Клиент делает заем для совершения сделки, которая будет завершена за конечный промежуток времени.
  2. Клиент должен заранее указать максимальную "потребность" во флоринах для этой сделки.
  3. Пока "заем" не превышает заранее установленную "потребность", клиент может увеличивать или уменьшать свой заем флорин за флорином.
  4. Клиент, который просит увеличить его текущий заем, обязуется принимать без недовольства следующий ответ: "Если бы я дал вам запрашиваемый флорин, вы еще не превысили бы свою установленную потребность, и поэтому вы имеете право на следующий флорин. Однако в настоящий момент мне, по некоторым причинам, неудобно его дать, но я обещаю вам флорин в должное время".
  5. Гарантия для клиента в том, что этот момент действительно наступит, основана на предусмотрительности банкира и на том факте, что остальные клиенты подчиняются тем же условиям, что и он сам: как только клиент получает флорин, он приступает к своей сделке с ненулевой скоростью, т. е. в конечный промежуток времени он или запросит новый флорин, или возвратит флорин, или закончит сделку, что означает возвращение всего займа (флорин за флорином).

Основными вопросами здесь являются:

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

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

Ответ на вопрос (а) прост: он может принять любого клиента, чья максимальная потребность не превышает капитал банкира.

Для ответа на вопрос (б) введем следующую терминологию.

Банкир имеет в своем распоряжении фиксированный "капитал"; каждый новый клиент устанавливает свою максимальную "потребность" и для любого клиента выполняется условие:

"потребность[i] < капитал" (для всех i).

Текущая обстановка для каждого клиента характеризуется его "заемом".


Каждый заем первоначально равен "0" и будет в любой момент удовлетворять соотношению:

"0 < заем[i] < потребность[i]" (для всех i).

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

"требование[i] = потребность[i] - заем[i]" (для всех i).

Наконец, "наличные" банкира составляют:

"наличные = капитал - сумма всех займов".

Очевидно, что должно выполняться условие:

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

Для того чтобы решить, выплачивать ли запрашиваемый флорин клиенту, банкир по существу оценивает положение, которое сложилось бы, если бы он произвел выплату. Если это положение "безопасно", он выплачивает флорин; если положение не "безопасно", он должен сказать: "Извиняюсь, но вы должны подождать".

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

Если клиенты пронумерованы от 1 до N, то стандартную программу проверки положения можно составить так:

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; свободные деньги := свободные деньги + заем[i]; goto L end

end;

if свободные деньги = капитал then безопасно := true

else безопасно := false

Приведенная стандартная программа проверяет любое положение. Улучшение алгоритма банкира было предложено Цваненбургом, который принял во внимание, что подлежат исследованию только те положения, которые возникают, когда при безопасном положении выдается флорин некоторому клиенту [i]. Как только при работе программы выполнится условие "завершение под сомнением[i] := false", можно прямо сделать вывод о безопасности нового положения, так как тогда, очевидно, эта планируемая выплата будет обратима. Это усовершенствование реализовано в программе следующего параграфа.




Содержание раздела