銀行家のアルゴリズムはデッドロックの問題を避ける
28243 ワード
銀行家アルゴリズム(Banker’s Algorithm)はデッドロック(Deadlock)を避ける有名なアルゴリズムで、1965年にエズグ・ディジェストラがT.H.Eシステムのために設計したデッドロックの発生を避けるアルゴリズムである.銀行ローンシステムの分配戦略に基づいて、システムの安全運行を判断し、保証します.
背景知識
銀行では、顧客がローンを申請する数は限られており、各顧客は初めてローンを申請する際に、このプロジェクトを完了するために必要な最大資金量を宣言し、すべてのローンの要求を満たす場合、顧客は直ちに返済しなければならない.銀行家は、顧客が申請したローンの数が自分が持っている最大値を超えない場合、できるだけ顧客のニーズを満たすべきだ.このような説明では、銀行家はオペレーティングシステムのようなもので、資金は資源であり、顧客は資源を申請するプロセスに相当します.
銀行家アルゴリズムは最も代表的なデッドロックを避けるアルゴリズムである.デッドロック回避方法では、プロセスがリソースを動的に申請することができますが、システムはリソースの割り当てを行う前に、今回の割り当てリソースのセキュリティを計算する必要があります.割り当てがシステムを不安全な状態にしない場合は、割り当て、そうでない場合は待機します.銀行家アルゴリズムを実現するために、システムはいくつかのデータ構造を設定しなければならない.
銀行家のアルゴリズムを説明するには、オペレーティングシステムのセキュリティ状態と非セキュリティ状態を先に説明する必要があります.
セキュリティシーケンスとは、プロセスシーケンス{P 1,...,Pn}がセキュリティであることを意味し、すなわち、各プロセスPi(1≦i≦n)に対して、その後必要とされるリソース量は、システムの現在の残りのリソース量とすべてのプロセスPj(jあんぜんじょうたいシステム内のすべてのプロセスからなるセキュリティシーケンスP 1,...,Pnが存在する場合、システムはセキュリティ状態にある.安全状態はデッドロックが発生していないに違いない.
安全でない状態にはセキュリティシーケンスは存在しません.不安全な状態が必ずしもデッドロックを引き起こすとは限らない.
データ構造利用可能リソースベクトルAvailable:m個の要素を含む配列であり、各要素は利用可能なリソースの数を表す.Available[j]=Kの場合、システムに既存のRjクラスリソースK個があることを示す. 最大需要行列Max:これはn×システム内のnプロセスの各プロセスのmクラスリソースに対する最大の需要を定義するmのマトリクス.Max[i,j]=Kの場合、プロセスiがRjクラスリソースを必要とする最大数はKであることを示す. 分配行列Allocation:これもn×mのマトリクスは、システム内の各クラスのリソースが現在各プロセスに割り当てられているリソースの数を定義します.Allocation[i,j]=Kの場合、プロセスiが現在Rjクラスリソースに割り当てられている数がKであることを示す. デマンド行列Need:これもn×mのマトリクスは、各プロセスに必要な各種リソース数を表すために使用される.Need[i,j]=Kの場合、プロセスiはRjクラスリソースK個を必要とし、そのタスクを完了することができる. Need[i,j]=Max[i,j]-Allocation[i,j]
アルゴリズムの原理
オペレーティングシステムは銀行家と見なすことができ、オペレーティングシステムが管理する資源は銀行家が管理する資金に相当し、プロセスがオペレーティングシステムに資源の分配を要求するのはユーザーが銀行家に融資することに相当する.資金の安全を保証するために、銀行家は以下のように規定している.顧客の資金に対する最大需要量が銀行家の既存の資金を超えない場合、顧客を受け入れることができる. 顧客は分割ローンができますが、ローンの総数は最大需要量を超えてはいけません. 銀行家の既存の資金が顧客のまだ必要な貸付額を満たすことができない場合、顧客に対する貸付は支払いを延期することができるが、いつも顧客に限られた時間で貸付を得ることができる. お客様が必要なすべての資金を得た後、必ず限られた時間ですべての資金を返還することができます.
オペレーティングシステムは銀行家が制定したルールに従ってプロセスにリソースを割り当て、プロセスが初めてリソースを申請した場合、そのプロセスのリソースに対する最大需要量をテストし、システムの現存するリソースがその最大需要量を満たすことができる場合は、現在の申請量でリソースを割り当て、そうでなければ割り当てを遅らせる.プロセスが実行中にリソースを申請し続ける場合は、プロセスが今回申請したリソースの数がリソースの残りの総量を超えているかどうかをテストします.超過するとリソースの割り当てが拒否され、満足できる場合は現在の購買依頼量でリソースが割り当てられます.そうしないと、割り当ても延期されます.
コード実装
背景知識
銀行では、顧客がローンを申請する数は限られており、各顧客は初めてローンを申請する際に、このプロジェクトを完了するために必要な最大資金量を宣言し、すべてのローンの要求を満たす場合、顧客は直ちに返済しなければならない.銀行家は、顧客が申請したローンの数が自分が持っている最大値を超えない場合、できるだけ顧客のニーズを満たすべきだ.このような説明では、銀行家はオペレーティングシステムのようなもので、資金は資源であり、顧客は資源を申請するプロセスに相当します.
銀行家アルゴリズムは最も代表的なデッドロックを避けるアルゴリズムである.デッドロック回避方法では、プロセスがリソースを動的に申請することができますが、システムはリソースの割り当てを行う前に、今回の割り当てリソースのセキュリティを計算する必要があります.割り当てがシステムを不安全な状態にしない場合は、割り当て、そうでない場合は待機します.銀行家アルゴリズムを実現するために、システムはいくつかのデータ構造を設定しなければならない.
銀行家のアルゴリズムを説明するには、オペレーティングシステムのセキュリティ状態と非セキュリティ状態を先に説明する必要があります.
セキュリティシーケンスとは、プロセスシーケンス{P 1,...,Pn}がセキュリティであることを意味し、すなわち、各プロセスPi(1≦i≦n)に対して、その後必要とされるリソース量は、システムの現在の残りのリソース量とすべてのプロセスPj(j
安全でない状態
データ構造
アルゴリズムの原理
オペレーティングシステムは銀行家と見なすことができ、オペレーティングシステムが管理する資源は銀行家が管理する資金に相当し、プロセスがオペレーティングシステムに資源の分配を要求するのはユーザーが銀行家に融資することに相当する.資金の安全を保証するために、銀行家は以下のように規定している.
オペレーティングシステムは銀行家が制定したルールに従ってプロセスにリソースを割り当て、プロセスが初めてリソースを申請した場合、そのプロセスのリソースに対する最大需要量をテストし、システムの現存するリソースがその最大需要量を満たすことができる場合は、現在の申請量でリソースを割り当て、そうでなければ割り当てを遅らせる.プロセスが実行中にリソースを申請し続ける場合は、プロセスが今回申請したリソースの数がリソースの残りの総量を超えているかどうかをテストします.超過するとリソースの割り当てが拒否され、満足できる場合は現在の購買依頼量でリソースが割り当てられます.そうしないと、割り当ても延期されます.
コード実装
//#include <stdafx.h>
#include <stdio.h>
#include "string.h"
#include "stdlib.h"
#pragma warning(disable:4996)
#define MAX_PROCESS 10 //
#define MAX_RESOURCE_KIND 10 //
#define MAX_RESOURCE_NUM 20 //
int resource; //
int process; //
int safe_list[MAX_PROCESS]; //
struct AVAILABLE { //
int resource_number; //
int work; //
}Resource[MAX_RESOURCE_KIND], R_backup[MAX_RESOURCE_KIND];
struct PROC { //
int max[MAX_RESOURCE_KIND]; //
int allocation[MAX_RESOURCE_KIND]; //
int need[MAX_RESOURCE_KIND]; //
bool finish; //
}Process[MAX_PROCESS], P_backup[MAX_PROCESS];
void zero();
void show_me();
void init();
void init_allocation();
void update();
void backup();
void re_backup();
bool allocation();
bool one_allocation(int a, int b, int c);
bool release();
bool one_release(int a, int b, int c);
int is_safe();
void test();
int banker();
void menu();
void zero() {//
for (int i = 0; i<MAX_RESOURCE_KIND; i++) {
Resource[i].resource_number = 0;
}
for (int i = 0; i<MAX_RESOURCE_KIND; i++) {
for (int j = 0; j< MAX_RESOURCE_KIND; j++) {
Process[i].max[j] = 0;
Process[i].allocation[j] = 0;
Process[i].need[j] = 0;
}
}
}
void show_me() {//
printf("
Available ");
for (int i = 0; i < resource; i++) {
printf("%d ", Resource[i].resource_number);
}
printf("
");
printf("
Max ");
for (int i = 0; i < MAX_RESOURCE_KIND * 2 - 7; i++) printf(" ");
printf("Allocation ");
for (int i = 0; i < MAX_RESOURCE_KIND * 2 - 14; i++) printf(" ");
printf("Need ");
for (int i = 0; i < MAX_RESOURCE_KIND * 2 - 8; i++) printf(" ");
for (int i = 0; i<process; i++) {
printf("
");
for (int j = 0; j<resource; j++) printf("%d ", Process[i].max[j]);
for (int i = 0; i < MAX_RESOURCE_KIND * 2 - resource * 2; i++) printf(" ");
for (int j = 0; j<resource; j++) printf("%d ", Process[i].allocation[j]);
for (int i = 0; i < MAX_RESOURCE_KIND * 2 - resource * 2; i++) printf(" ");
for (int j = 0; j<resource; j++) printf("%d ", Process[i].need[j]);
}
printf("
");
}
void init() {//
int n;
printf("
");
scanf("%d", &n);
resource = n;
for (int i = 0; i<resource; i++) {
printf("
%d ", i + 1);
scanf("%d", &n);
Resource[i].resource_number = n;
}
printf("
");
scanf("%d", &n);
process = n;
for (int i = 0; i<process; i++) {
int a, flag;
flag = 0;
printf("
%d ", i + 1);// max
for (int j = 0; j<resource; j++) {
scanf("%d", &a);
Process[i].max[j] = a;
if (a>Resource[j].resource_number) flag = 1;
}
if (flag == 1) {
i--;
printf("
");
}
getchar();
}
}
void init_allocation() {//
for (int i = 0; i<process; i++) {
int a, flag;
flag = 0;
printf("
%d ", i + 1);
for (int j = 0; j<resource; j++) {
scanf("%d", &a);
Process[i].allocation[j] = a;
if (a>Resource[j].resource_number) flag = 1;
}
if (flag == 1) {
i--;
printf("
");
}
}
update();
}
void update() {// need allocation
for (int i = 0; i<process; i++) {
for (int j = 0; j<resource; j++) {
Process[i].need[j] = Process[i].max[j] - Process[i].allocation[j];
Resource[j].resource_number -= Process[i].allocation[j];
}
}
}
bool allocation()
{
backup();
printf("
");
int pro_num;
scanf("%d", &pro_num);
int aff[MAX_RESOURCE_KIND];
for (int i = 0; i < resource; i++)
{
scanf("%d", &aff[i]);
}
for (int i = 0; i < resource; i++)
{
if (one_allocation(pro_num - 1, i, aff[i]) == false)
{//
re_backup();
return false;
}
}
return true;
}
bool one_allocation(int a, int b, int c) {//
if (c>Process[a].need[b])
{
printf(" ，
");
return false;
}
else if (c>Resource[b].resource_number)
{
printf(" ，
");
return false;
}
Resource[b].resource_number -= c;
Process[a].need[b] -= c;
Process[a].allocation[b] += c;
return true;
}
void backup() { //
for (int i = 0; i < process; i++) {
P_backup[i] = Process[i];
}
for (int i = 0; i < resource; i++) {
R_backup[i] = Resource[i];
}
}
void re_backup() { //
for (int i = 0; i < process; i++) {
Process[i] = P_backup[i];
}
for (int i = 0; i < resource; i++) {
Resource[i] = R_backup[i];
}
}
bool release() { //
backup();
printf("
");
int pro_num;
scanf("%d", &pro_num);
int aff[MAX_RESOURCE_KIND];
for (int i = 0; i < resource; i++) {
scanf("%d", &aff[i]);
}
for (int i = 0; i < resource; i++) {
if (one_release(pro_num, i, aff[i]) == false) {
re_backup();
return false;
}
}
return true;
}
bool one_release(int a, int b, int c) {//
if (c>Process[a].allocation[b]) {
printf(" ，
");
return false;
}
Resource[b].resource_number += c;
Process[a].need[b] += c;
Process[a].allocation[b] -= c;
return true;
}
int is_safe()
{ //
for (int i = 0; i < resource; i++)
{
Resource[i].work = Resource[i].resource_number;// ， work
}
for (int i = 0; i < process; i++)
{
Process[i].finish = false;
safe_list[i] = 0;
}
test();
bool flag = true;
for (int i = 0; i < process; i++)
{
if (Process[i].finish == false)
{
flag = false;
break;
}
}
if (flag == true)
{
printf("
");
printf("
");
for (int i = 0; i < process; i++) {
printf("%d ", safe_list[i]);
}
return 1;
}
else {
printf("
");
return -1;
}
}
void test() { //
for (int i = 0; i < process; i++)
{
bool flag = true;
if (Process[i].finish == false)
{
for (int j = 0; j < resource; j++)
{
if (Process[i].need[j] > Resource[j].work)
{
flag = false;
break;
}
}
if (flag == true)
{
for (int j = 0; j < resource; j++)
{
Resource[j].work += Process[i].allocation[j];
Process[i].finish = true;
}
for (int k = 0; k < process; k++)
{
if (safe_list[k] == 0)
{
safe_list[k] = i + 1;
break;
}
}
test(); //
}
}
}
}
int banker() {//
backup(); //
//allocation();
if (allocation() == false) return -1;
bool flag;
flag = is_safe();
if (flag == true)
{
char k[10];
printf("
（y/n） ");
scanf("%s", &k);
if (_stricmp(k, "y") == 0) return 1;
else
{
re_backup();
return -1;
}
}
else {
re_backup();
return -1;
}
}
void menu() { //
printf("
");
printf("
(init)
(show)
(safe)
(request)
(release)
(quit)
(clear)
");
char code[20];
while (1) {
printf("
");
scanf("%s", code);
if (_stricmp(code, "init") == 0) { //
zero();
init();
init_allocation();
}
else if (_stricmp(code, "show") == 0) { //
show_me();
}
else if (_stricmp(code, "safe") == 0) { //
is_safe();
}
else if (_stricmp(code, "request") == 0) { //
printf("
（y/n）
");
scanf("%s", code);
if (_stricmp(code, "y") == 0) banker();
else allocation();
}
else if (_stricmp(code, "release") == 0) { //
release();
}
else if (_stricmp(code, "quit") == 0) { //
return;
}
else if (_stricmp(code, "clear") == 0) { //
system("cls");
printf("
");
printf("
(init)
(show)
(safe)
(request)
(release)
(quit)
(clear)
");
}
else printf(" ，
");
}
}
int main(int argc, char* argv[])
{
/* zero(); init(); init_allocation(); show_me(); is_safe();*/
menu();
getchar();
return 0;
}