今日は昨日のアルゴリズム、銀行家アルゴリズムを完成させました。これはオペレーティングシステムの授業を知っている人には理解できると思います。昨日はずっと復習に忙しく、今日もそうでしたが、午後には基本的なデバッグを終えました。デバッグ環境は GCC と TC です。今、コードを皆さんにお届けします。
銀行家アルゴリズムの説明：最初にアルゴリズムの巨匠エドスガー・ダイクストラ（Edsger Dijkstra）によって提案されました。銀行家アルゴリズムは、その名の通り、銀行システムの貸出管理に基づいています。つまり、銀行（システム）は N 人（プロセス）に一定の資金（リソース）を貸し出す（配分）必要があります。当然、信用問題は考慮しません <'_'>。一定の金額が発放された後、銀行のすべての貸出（リソースの配分）は、銀行（システム）の運用が安全である（デッドロックを防止する）ようにしなければなりません（こう理解してもいいでしょう）。したがって、銀行家は既存の資金を合理的に配分しなければなりません。基本的な要件は、銀行は一定の預金を保持しなければならず、一定の限度（臨界リソース）を下回ってはいけません。同時に、貸出を行わなければならず、そうしないと顧客が「餓死」する（プロセスの飢餓）ことになります。顧客は貸出を使用した後、この貸出を返還（解放）しなければなりません。もちろん、利息はありません。その後、銀行は再び顧客に配分し、顧客のすべての貸出要求を満たすまで続けます。
具体的にはhttp://baike.baidu.com/view/93075.htm を参照できます。
コードは以下の通りです：
/*
* 銀行家アルゴリズム
*code CG 2008 01 05
*/
#include"stdio.h"
#define FALSE 0
#define TRUE 1
#define W 10
#define R 20
int M ; /* 総プロセス数 */
int N ; /* リソースの種類 */
int ALL_RESOURCE [W];/* 各種リソースの数の合計 */
int MAX [W][R]; /*M 個のプロセスが N 種類のリソースに対する最大リソース要求量 */
int AVAILABLE [R]; /* システムで利用可能なリソース数 */
int ALLOCATION [W][R]; /*M 個のプロセスがすでに得た N 種類のリソースの量 */
int NEED [W][R]; /*M 個のプロセスがまだ必要とする N 種類のリソースの量 */
int REQUEST [R]; /* 要求されたリソースの数 */
/*
* 関数名：output
* 機能：リソース配分状況を出力する
*/
void output()
{
int i,j;
printf (" すべてのリソース");
for(j = 0 ; j < N ;j++)
printf("R%d:%dn", j , ALL_RESOURCE[j]);
printf("利用可能なリソース:n");
for(j = 0 ; j < N ; j++)
printf("R%d:%dn", j , AVAILABLE\[j\]);
printf("プロセスが必要とするリソース:n");
printf("| PID |");
for(j = 0 ; j < N ; j++)
printf(" R%d |", j);
printf("n");
for(i = 0 ; i < M ; i++)
for(i = 0 ; i < M ; i++)
{
printf("|%-5d|", i);
for(j = 0 ; j < N ; j++)
printf("%-4d|", NEED\[i\]\[j\]);
printf("n");
}
printf("プロセスに割り当てられたリソース:n");
printf("| PID |");
for(j = 0 ; j < N ; j++)
printf(" R%d |", j);
printf("n");
for(i = 0 ; i < M ; i++)
{
printf("|%-5d|", i);
for(j = 0 ; j < N ; j++)
printf("%-4d|", ALLOCATION\[i\]\[j\]);
printf("n");
}
}/*output*/
/*
* 関数名 ：modify
* 機能：利用可能なリソースとすでに取得したリソース、まだ必要なリソースの値を変更する
* パラメータ：int k 修正番号 K の P のデータ
*/
void modify(int k)
{
int j;
for (j = 0 ; j < N ; j++){/* データを修正する */
AVAILABLE [j] = AVAILABLE [j] - REQUEST [j];/* 利用可能なリソースを修正する */
ALLOCATION [k][j] = ALLOCATION [k][j] + REQUEST [j];/* 配分リソースを修正する */
NEED [k][j] = NEED [k][j] - REQUEST [j];/* リソース要求を修正する */
}
}
/*
* 関数名：undo
* 機能：利用可能なリソースとすでに取得したリソース、まだ必要なリソースの値を元に戻す
* パラメータ：int k 修正番号 K の P のデータ
*/
void undo(int k){
int j;
for (j = 0 ; j < N ; j++){/* データを修正する */
AVAILABLE [j] = AVAILABLE [j] + REQUEST [j]; /* 利用可能なデータを修正する */
ALLOCATION [k][j] = ALLOCATION [k][j] - REQUEST [j]; /* 配分されたリソースを修正する */
NEED [k][j] = NEED [k][j] + REQUEST [j];/* リソース要求を修正する */
}
}
/*
* 関数名：chkerr
* 機能：修正操作が安全かどうかをチェックする
*/
int chkerr(int s){
int WORK , FINISH[W];
int i , j;
for (i = 0 ; i < M ; i++)/*FINISH をクリアする */
FINISH[i] = FALSE;
for (j = 0 ; j < N ; j++){/* 一つずつチェックする */
WORK = AVAILABLE[j];
i = s;
do{
if (FINISH [i] == FALSE && NEED [i][j] <= WORK){/* 条件に合致するか？*/
WORK = WORK + ALLOCATION[i][j];
FINISH[i] = TRUE;
i = 0;
}
else
i++;
}while(i
for (i = 0 ; i < M ; i++)/* 一つでも満たさない場合は安全でない */
if(FINISH[i] == FALSE){
printf ("エラー：安全でない配分！n");
return 1;
}
}
printf ("OK : 配分は OKn");
return 0;
}
/*
* 関数名：bank
* 機能 ：銀行家アルゴリズムの実装
*/
void bank()
{
int i , j;
int flag = TRUE;
printf ("Ctrl+C で中断します..n");
while(TRUE){
i = -1;
while(i < 0 || i >= M)
{
printf ("配分するプロセスを入力 PID=");
scanf("%d", &i);
if(i < 0 || i >= M)
printf ("エラー：無効な入力！n");
}
printf ("リソースの必要数を入力 n");
for (j = 0 ; j < N ; j++)
{
printf("R%d=", j);
scanf("%d", &REQUEST[j]);
if (REQUEST [j] > NEED [i][j]){/* 要求されたリソース数が要求リソースを超える場合 */
printf ("エラー：無効な入力！n");
flag = FALSE;
}
else{
if (REQUEST [j]>AVAILABLE [j]){/* 要求されたリソース数が利用可能リソース数を超える場合 */
printf ("エラー：無効な入力！n");
flag = FALSE;
}
}/*else*/
}/*for*/
if(flag)
{
modify(i); /\*リソース数を修正する\*/
if(chkerr(i)){/\*安全か？\*/
undo(i); /\*リソース数を元に戻す\*/
output();/\*出力する\*/
}
else
output(); /\*出力する\*/
}
else
output();
}/\*while\*/
}/*bank*/
/* メイン関数 */
int main(){
int i , j , p;
printf ("プロセス数 M を入力してください =");/* プロセスの数 */
scanf("%d", &M);
printf ("リソースの種類 N を入力してください =");/* リソースの種類 */
scanf("%d", &N);
printf (" 各カテゴリーのすべてのリソースの数を入力");/* リソースの数 */
for(i = 0 ; i < N ; i++)
scanf("%d", &ALL_RESOURCE[i]);
printf (" 最大リソースプロセスの必要数を入力");/* 最大リソース要求 */
for (i = 0 ; i < M ; i++){
for (j = 0 ; j < N ; j++){
do{
scanf("%d", &MAX[i][j]);
if (MAX [i][j] > ALL_RESOURCE [j])/* 最大可用を超えるか？*/
printf ("n エラー：無効な入力！n");
}while (MAX[i][j] > ALL_RESOURCE[j]);
}
}/*for*/
printf("プロセスに割り当てられたリソースを入力:n");
for (i = 0 ; i < M ; i++){
for (j = 0 ; j < N ; j++){
do{
scanf("%d", &ALLOCATION\[i\]\[j\]);
if (ALLOCATION\[i\]\[j\] > MAX\[i\]\[j\])/\*最大要求を超えるか？\*/
printf("nエラー: 無効な入力！n");
}while (ALLOCATION\[i\]\[j\] > MAX\[i\]\[j\]);
}
}/\*for\*/
for(j = 0 ; j < N ; j++){
p = ALL\_RESOURCE\[j\];
for(i = 0 ; i < M ; i++){
p -= ALLOCATION\[i\]\[j\];/\*すでに配分されたリソースを減らす\*/
AVAILABLE\[j\] = p;
if(AVAILABLE\[j\]<0)
AVAILABLE\[j\] = 0;/\*データをクリアする\*/
}/\*for\*/
}/\*for\*/
for (i = 0 ; i < M ; i++)
for(j = 0 ; j < N ; j++)
NEED\[i\]\[j\] = MAX\[i\]\[j\] - ALLOCATION\[i\]\[j\];/\*まだ必要なリソースを求める\*/
output();
bank();/\*銀行家アルゴリズム\*/
return 0;
}/*main*/