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

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

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

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

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

Талер_Сем, Талер_Пер,

Номер_Клиента[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 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;

Требование[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. С каждым клиентом связывается переменная Номер_Талера, значение которой после очередной выдачи талера клиенту определяет номер только что выделенного талера. В свою очередь с каждым талером связана переменная Номер_Клиента , значение которой указывает клиента, которому выдан этот талер. Имеются семафоры Клиент_Сем, и Талер_Сем. Фактически возврат талера заканчивается после того, как тот действительно присоединится к наличному капиталу банкира: об этом талер будет сообщать клиенту с помощью общего семафора клиента "Возвращенные_талеры". Значение булевой процедуры "Попытка_выдать_талер_клиенту" говорит о том, удовлетворен ли задержанный запрос на талер. В программе для талера используется тот факт, что возврат талера может теперь привести к удовлетворению единственного задержанного запроса на талер (если банкир распоряжается услугами более чем одного вида, то последнее свойство уже не будет выполняться).

Вычислительные структуры

Машины, управляемые контроллерами

Системы типа ОКОД

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

В зависимости от структуры управляющего устройства, такие машины подразделяются на системы с одним потоком команд и данных (ОКОД), системы с параллельными операциями, система с одним потоком команд и множественными потоками данных (ОКМД), системы с арифметическим конвейером.

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