Применение алгоритма банкира

Каждому талеру можно поставить в соответствие жесткий диск или какое-либо устройство. Тогда заем талера будет означать разрешение на использование одного из дисков.

begin

integer array Заем, Требование, Клиент_Сем,

Клиент_Пер, Номер_Талера,

Возвращенные_Талеры[1..N];

integer array Талер_Сем, Талер_Пер, Номер_Клиента[1..M];

integer Взаимн_искл, наличные, k;

boolean procedure Попытка_выдать_талер_клиенту (integer j);

begin

if (Клиент_Пер[j]=1) then begin

integer i, Своб_Деньги;

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

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

Требование[j]:=Требование[j]-1;

Заем[j]:=Заем[j]+1;

for i:=1 step 1 until N do

Завершен_под_сомн[j]:=true;

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

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

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

if (i<>j) then begin

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

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

goto L0;

end;

else begin

i:=0;

L1: i:=i+1;

if (Талер_Пер[i] = 0) then goto L1;

Номер_Талера[j]:=i;

Номер_Клиента[i]:=j;

Клиент_Пер[j]:=0;

Талер_Пер[i]:=0;

Наличные:=Наличные-1;

Попытка_Выдать_Талер_Клиенту:=true;

V (Клиент_Сем[j]);

V (Талер_Сем[j]);

goto L2;

end;

end;

end;

Требование[j]:=Требование[j]+1;

Заем[j]:=Заем[j]-1;

end;

Попытка_Выдать_Талер_Клиенту:=false;

L2: end; /* процедуры */

Взаимн_искл:=1; Наличные :=M;

for k:=1 step 1 until N do begin

Заем[k]:=0;

Клиент_Сем[k]:=0;

Клиент_Пер[k]:=0;

Требование[k]:=Потребность[k];

Возвращенные_Талеры[k]:=Потребность[k];

end;

for k:=1 step 1 until M do begin

Талер_Сем[k]:=0;

Талер_Перем[k]:=1;

end;

parbegin

Клиент 1: begin ... end;

…

Клиент i: begin ...

P(Возвращенные_Талеры[i]);

P(Взаимн_искл);

Клиент_Пер[i] := 1;

Попытка_выдать_талер_клиенту(i);

V(Взаимн_искл);

P(Клиент_Сем[i]);

…

end;

Талер 1: begin ... end;

…

Талер m: begin integer h;

…

начало: P(Талер_Сем[m]);

P(Взаимн_искл);

Требование[Номер_Клиента[m]] := Требование[Номер_Клиента[m]] - 1;

Талер_Перем[m] := 1;

наличные := наличные + 1;

V(Возвращенные_Талеры[Номер_Клиента[m]]);

for h:=1 step 1 until N do begin

if (Попытка_выдать_талер_клиенту(h))

then goto выход;

end;

выход:V(Взаимн_искл);

goto начало

…

end;

parend;

end;

Сущность: есть клиент и есть талер. Каждый клиент имеет переменную со­стояния Клиент_Пер. Если Клиент_Пер = 1 – это означает: “хочу получить заем”. Иначе Клиент_Пер = 0. Каждый талер имеет переменную состояния Талер_Пер. Если Талер_Пер = 1 – это означает: “нахожусь среди свободного капитала”. Кли­енты пронумерованы от 1 до N, а талеры от 1 до M. С каждым клиентом связыва­ется переменная Номер_Талера, значение которой после очередной выдачи та­лера клиенту определяет номер только что выделенного талера. В свою очередь с каждым талером связана переменная Номер_Клиента , значение которой указы­вает клиента, которому выдан этот талер. Имеются семафоры Клиент_Сем, и Та­лер_Сем. Фактически возврат талера заканчивается после того, как тот действи­тельно присоединится к наличному капиталу банкира: об этом талер будет сооб­щать клиенту с помощью общего семафора клиента "Возвращенные_талеры". Значение булевой процедуры "Попытка_выдать_талер_клиенту" говорит о том, удовлетворен ли задержанный запрос на талер. В программе для талера исполь­зуется тот факт, что возврат талера может теперь привести к удовлетворению единственного задержанного запроса на талер (если банкир распоряжается услу­гами более чем одного вида, то последнее свойство уже не будет выполняться).