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

Замечания к программе:

1. Предполагается, что пользовательские процессы пронумерованы от 1 до N, и что страницы пронумерованы от 1 до M. С каждым процессом связана переменная «номер_страницы», значение которой после очередной выдачи страницы определяет номер только что выданной страницы. В свою очередь с каждой страницей связана переменная «номер_процесса», значение которой указывает процесс, которому была выдана.

2. Каждый пользовательский процесс имеет переменную состояния «процесс_пер» - переменная клиента; при этом процесс_пер=1 означает «Мне нужна страница» (иначе процесс_пер=0). Каждая страница имеет переменную состояния «страница_пер»; при этом страница_пер=1 означает, что она находится среди буферного пула свободных страниц. С каждым процессом и каждой страницей связаны двоичные семафоры «процесс_сем» и «страница_сем».

3. Предполагается, что каждая страница выдается и возвращается на основании указаний пользовательского процесса, но процесс не имеет возможности возвратить взятую страницу мгновенно. После того, как процесс заявляет, что страница ему больше не нужна, последняя не становится немедленно доступной для последующего использования. Фактически возврат страницы заканчивается после того, как та действительно присоединится к буферному пулу свободных страниц: об этом страница будет сообщать процессу с помощью общего семафора процесса «возвращенные_страницы». P-операция над этим семафором должна предостеречь пользовательский процесс от неумышленного превышения своей максимальной потребности. Перед каждым запросом страницы процесс выполнит P-операцию над семафором «возвращенные_страницы», а начальное значение переменной «возвращенные_страницы» полагается равным потребности.

Текст программы:

int заем[N], требование[N], процесс_сем[N],

процесс_пер[N], номер_страницы[N],

возвращенные_страницы[N], страница_сем[Ì],

страница_пер[Ì], номер_процесса[Ì];

int взаимоискл, V_буфера, к;

Boolean procedure попытка_выдать_страницу_процессу(j)

int j;

{ int i, свободные_страницы;

boolean int завершение_под_сомнением[N];

if процесс_пер[j] = 1

{ свободные_страницы = V_буфера -1;

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

заем[j] = заем[j]+1;

for (i=1; i<=N; i++)

завершение_под_сомнением[i] = true;

L0: for (i=1; i<=N; i++)

/* проверка на безопасность завершения */

{ if завершение_под_сомнением[i] and

требование[i] <= свободные деньги

{ if i # j

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

свободные деньги = свободные деньги+заем[i];

goto L0;}

else

{ i = 0;

L1: i = i+1;

if страница_пер[i] = 0 goto L1;

номер_страницы[j] = i;

номер_процесса[i] = j;

процесс_пер[j] = 0;

страница_пер[i] = 0;

V_буфера = V_буфера - 1;

попытка_выдать_страницу_процессу = true;

V(процесс_сем[j]);

V(страница_сем[i]; return;

}

}

}

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

заем[j] = заем[j]-1;

}

попытка_выдать_страницу_процессу = false;

}

/* конец процедуры *.

взаимоискл = 1; V_буфера = M;

for (k=1; k<=N; k++)

{ заем[k] = 0; процесс_сем[k] = 0; процесс_пер[k] = 0;

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

возвращенные_страницы[k] = потребность[k]; }

for (k=1; k<=M; k++)

{ страница_сем[k] = 0; страница_пер = 1; }

parbegin

процесс 1: { . . . . . . . . . }

процесс 2: { . . . . . . . . . }

. . . . . . . . .

процесс N: { . . . . . . . . . }

страница 1: { . . . . . . . . . }

страница 2: { . . . . . . . . . }

. . . . . . . . .

страница M: { . . . . . . . . . }

parend

}

У процесса «n» запрос новой страницы (часть программы процесса) описывается последовательностью операторов:

P(возвращенные_страницы[n]);

P(взаимоискл);

процесс_пер[n]=1;

попытка_выдать_страницу_процессу(n);

V(взаимоискл);

P(процесс_сем[n]);

После завершения последнего оператора значение переменной «номер страницы[n]» определяет только что выданную страницу; процесс может использовать его, но обязан возвратить его в надлежащее время ОС.

Структура программы для страницы:

Страница m:

{ int h;

L: P(страница_сем[m]); * (разблокирует процесс)

/* теперь номер_процесса[m] указывает процесс, которому

выдана страница. Страница обслуживает процесс до тех пор, пока она необходима.

Для возвращения в буферный пул страница поступает

след. образом: */

P(взаимоискл);

требование[номер_процесса[m]]=

требование[номер_процесса[m]]+1;

заем[номер_процесса[m]]=заем[номер_процесса[m]]-1;

страница_пер[m]=1;

V_буфера= V_буфера+1;

/* сообщение процессу *.

V(возвращенные_страницы[номер_процесса[m]]);

J: V(взаимоискл);

goto L;

}