1. 実験目的
(1) 銀行家アルゴリズムの動作原理を理解する。
(2) プロセスの安全性を確認する方法と、リソース割り当ての方法を習得する。
2. 実験内容と基本要件
銀行家アルゴリズムを模擬するプログラムを実装し、正しさを検証する例を示す。
検証例では、安全な割り当てと安全でない割り当ての両方を含めること。
3. 銀行家アルゴリズムと安全性検査アルゴリズムの原理
銀行家アルゴリズム
銀行家アルゴリズムはデッドロックを回避するための手法である。実装においては、各新規プロセスがシステムに入る際に、実行过程中に要する可能性のある各リソース種の最大ユニット数を宣言する必要がある。この数はシステムが保持するリソース総量を超えてはならない。プロセスがリクエストを送信すると、システムは以下の2点を自動的に判定する：
- リクエスト量がプロセスの最大必要量を超えないか
- リクエスト量が現在のシステム利用可能なリソース量を超えないか
両条件を満たした場合、システムがリソースを仮割り当てし、安全性検査アルゴリズムを実行する。
安全性検査アルゴリズム
安全性検査アルゴリズムは、リソース割り当て後のシステムが安全であるかを判定するために用いられる。以下の手順で動作する：
- システム仮割り当て後、実行可能なプロセスを现有プロセスのリストから探索する
- 実行可能なプロセスを見つけ次第実行し、完了後に占有リソースを回収する
- 次の実行可能プロセスを探索する
- プロセスの必要量がシステムの分配可能量を超える場合、そのプロセスは実行できない
全プロセスが全て実行可能である場合、安全な実行序列が生成され、システムリソースの割り当ては成功である。 全プロセスが実行できない場合、安全な序列が見つからないため、 해당割り当て请求는 거부된다。
4. プログラム実装
// 銀行家アルゴリズムのシミュレーション実装
// 安全な割り当てと安全でない割り当ての例を含む
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define PROC_MAX 300
#define RES_MAX 300
int processCount, resourceTypeCount;
int resourceFree[RES_MAX];
int maxDemand[PROC_MAX][RES_MAX];
int allocated[PROC_MAX][RES_MAX];
int requirement[PROC_MAX][RES_MAX];
int requestVec[RES_MAX];
int targetProcess;
int completed[PROC_MAX];
int workVec[RES_MAX];
int safeSequence[PROC_MAX];
int seqIndex;
bool withinDeclared(int procId) {
for (int i = 0; i < resourceTypeCount; i++) {
if (requestVec[i] > requirement[procId][i]) {
return false;
}
}
return true;
}
bool withinAvailable(int procId) {
for (int i = 0; i < resourceTypeCount; i++) {
if (requestVec[i] > resourceFree[i]) {
return false;
}
}
return true;
}
void applyAllocation(int procId) {
for (int i = 0; i < resourceTypeCount; i++) {
resourceFree[i] -= requestVec[i];
}
for (int i = 0; i < resourceTypeCount; i++) {
allocated[procId][i] += requestVec[i];
}
for (int i = 0; i < resourceTypeCount; i++) {
requirement[procId][i] -= requestVec[i];
}
}
void rollbackAllocation(int procId) {
for (int i = 0; i < resourceTypeCount; i++) {
resourceFree[i] += requestVec[i];
}
for (int i = 0; i < resourceTypeCount; i++) {
allocated[procId][i] -= requestVec[i];
}
for (int i = 0; i < resourceTypeCount; i++) {
requirement[procId][i] += requestVec[i];
}
}
void displayState() {
printf("========== プロセスおよびリソース状態 ==========\n");
printf("\t%12s%16s%10s\n", "最大要求", "割り当て", "必要量");
printf("プロセス\t");
for (int header = 0; header < 3; header++) {
printf(" ");
for (int i = 0; i < resourceTypeCount; i++) {
printf("%2c", 'A' + i);
}
}
printf("\n");
for (int i = 0; i < processCount; i++) {
printf(" %d ", i);
printf(" ");
for (int j = 0; j < resourceTypeCount; j++) {
printf("%2d", maxDemand[i][j]);
}
printf(" ");
for (int j = 0; j < resourceTypeCount; j++) {
printf("%2d", allocated[i][j]);
}
printf(" ");
for (int j = 0; j < resourceTypeCount; j++) {
printf("%2d", requirement[i][j]);
}
printf("\n");
}
printf("システム利用可能リソース: ");
for (int i = 0; i < resourceTypeCount; i++) {
printf("%3d", resourceFree[i]);
}
printf("\n=============================================\n");
}
bool checkSafety() {
memset(completed, 0, sizeof(completed));
memcpy(workVec, resourceFree, sizeof(int) * (resourceTypeCount + 1));
seqIndex = 0;
for (int iteration = 0; iteration < processCount; iteration++) {
if (completed[iteration]) continue;
int j;
for (j = 0; j < resourceTypeCount; j++) {
if (requirement[iteration][j] > workVec[j]) {
break;
}
}
if (j == resourceTypeCount) {
for (j = 0; j < resourceTypeCount; j++) {
workVec[j] += allocated[iteration][j];
}
completed[iteration] = 1;
safeSequence[seqIndex++] = iteration;
iteration = -1;
}
}
for (int i = 0; i < processCount; i++) {
if (!completed[i]) {
return false;
}
}
return true;
}
void processRequest() {
if (!checkSafety()) {
printf("初期データ不安全\n");
return;
}
while (1) {
printf("\nプロセスIDと要求リソース量を入力してください:\n");
scanf("%d", &targetProcess);
for (int i = 0; i < resourceTypeCount; i++) {
scanf("%d", &requestVec[i]);
}
if (withinDeclared(targetProcess)) {
if (!withinAvailable(targetProcess)) {
printf("リソース不足、プロセスは待機する必要があります\n");
} else {
applyAllocation(targetProcess);
if (checkSafety()) {
printf("安全序列が存在します: ");
for (int i = 0; i < seqIndex; i++) {
if (i) printf("->");
printf("%d", safeSequence[i]);
}
printf("\n割り当て成功！\n");
displayState();
} else {
rollbackAllocation(targetProcess);
printf("不安全、割り当てを拒否！\n");
}
}
} else {
printf("エラー、要求量が宣言された最大値を超えています\n");
}
}
}
int main() {
printf("プロセス数とリソース数を入力してください:\n");
scanf("%d %d", &processCount, &resourceTypeCount);
for (int i = 0; i < processCount; i++) {
for (int j = 0; j < resourceTypeCount; j++) {
scanf("%d", &maxDemand[i][j]);
}
for (int j = 0; j < resourceTypeCount; j++) {
scanf("%d", &allocated[i][j]);
}
for (int j = 0; j < resourceTypeCount; j++) {
requirement[i][j] = maxDemand[i][j] - allocated[i][j];
}
}
printf("システム利用可能リソースを入力してください:\n");
for (int i = 0; i < resourceTypeCount; i++) {
scanf("%d", &resourceFree[i]);
}
displayState();
processRequest();
return 0;
}
5. 実験結果と考察
入力データ:
プロセス数: 5、リソース種: 3
プロセス0: Max=(7,5,3) Allocation=(0,1,0) → Need=(7,4,3)
プロセス1: Max=(3,2,2) Allocation=(2,0,0) → Need=(1,2,2)
プロセス2: Max=(9,0,2) Allocation=(3,0,2) → Need=(6,0,0)
プロセス3: Max=(2,2,2) Allocation=(2,1,1) → Need=(0,1,1)
プロセス4: Max=(4,3,3) Allocation=(0,0,2) → Need=(4,3,1)
システム利用可能リソース: (3,3,2)
ケース1: プロセス1が(1,0,2)を要求
結果: 安全序列 1->3->0->2->4
割り当て成功、利用可能リソースは(2,3,0)となる
ケース2: プロセス4が(3,3,0)を要求
結果: リソース不足、拒否
ケース3: プロセス0が(2,3,0)を要求
結果: 安全序列が存在しないため不安全、割り当てを拒否
6. 結論
銀行家アルゴリズムは動的にデッドロックを回避する手法である。各リソース割り当てに対して安全性検査アルゴリズムを施行し、安全序列が存在すれば割り当てを許可し、存在しなければ割り当てを取り消す。これによりシステムは常に安全な状態を維持できる。