[운영체제] Banker's algorithm(은행원 알고리즘) 구현 - Deadlock

• 안녕하세요 BlockDMask 입니다.

• 2017/11/24 - [/[Operating System]] - [운영체제] Deadlock(교착상태)에 대해서

• 지난시간에 이어서 

• 이번시간에는 Deadlock(교착상태)를 회피하거나 탐지할 때 사용할 수 있는 은행원 알고리즘(Banker's algorithm)을 구현해보겠습니다.

• 문제는 공룡책 8th 7.10번 문제입니다.

**직접 구현한 것이라,, 많이 부족할 수 있습니다. 

보완이 필요한 부분은 댓글로 달아주시면 감사하겠습니다.

1. 구현할 내용

• 현재 시스템의 상태를 아래와 같이 정의 하겠습니다.
  프로세스가 안전한지(deadlock 이 발생하지 않는지) 확인할 수 있고
  프로세스가 어떤 순서로 자원을 할당 받는지 볼 수 있도록 구현하겠습니다.

	Allocation	Max	Available
	A B C D	A B C D	A B C D
P0	0 0 1 2	0 0 1 2	1 5 2 0
P1	1 0 0 0	1 7 5 0
P2	1 3 5 4	2 3 5 6
P3	0 6 3 2	0 6 5 2
P4	0 0 1 4	0 6 5 6

2. 소스 코드

//Banker's Algorithm
//은행원 알고리즘
 
#include<iostream>
#include<cstdio>
#define R_LEN 4
#define PROCESS_CNT 5
using namespace std;
 
//======================//
 
class process{
private:
    bool finish;    //process가 자원을 할당 받고 작업을 완료했는지
    int maxResource[R_LEN];   //process가 최대로 필요로 하는 자원의 개수
    int allocation[R_LEN];    //process가 현재 가지고 있는 자원들
    int need[R_LEN];  //process가 작업을 완료하기 위해 필요한 자원의 개수 (max-allocation)
public:
    process(int allocation[R_LEN], int maxResource[R_LEN]){
        finish = false;
        for(int i=0; i<R_LEN; i++){
            this->maxResource[i] = maxResource[i];
            this->allocation[i] = allocation[i];
            this->need[i] = this->maxResource[i] - this->allocation[i];
        }
    }
 
    bool isFinish() const{
        return finish;
    }
    void setFinish(bool finish){
        this->finish = finish;
    }
 
    bool isWork(int *available) const{ //work가 가능한지
        for(int i=0; i<R_LEN; i++){
            if(need[i] <= available[i]) continue;
            return false;
        }
        return true;
    }
 
    void giveAllocation(int *available){
        for(int i=0; i<R_LEN; i++){
            available[i] += allocation[i];
        }
    }
    void printAllocation() const{
        cout << "allocation : ";
        for(int i=0; i<R_LEN; i++){
            printf("%d ", allocation[i]);
        }
        printf("\n");
    }
    void printMaxResource() const{
        cout << "maxResource : ";
        for(int i=0; i<R_LEN; i++){
            printf("%d ", maxResource[i]);
        }
        printf("\n");
    }
    void printNeed() const{
        cout << "need : ";
        for(int i=0; i<R_LEN; i++){
            printf("%d ", need[i]);
        }
        printf("\n");
    }
    void printAll() const{
        printAllocation();
        printMaxResource();
        printNeed();
        printf("\n");
    }
};
 
//======================//
 
void printProcess(process *p[PROCESS_CNT]){
    for(int i=0; i<PROCESS_CNT; i++){
        printf("p[%d]\n", i);
        p[i]->printAll();
    }
}
void printAvailable(int *available){
    cout << "available : ";
    for(int i=0; i<R_LEN; i++){
        printf("%d ", available[i]);
    }
    printf("\n");
}
void printResult(bool result, int *sequence){
    printf("\nresult\n");
    if(result){
        for(int i=0; i<5; i++){
            printf("process[%d]", sequence[i]);
            if(i!=4) printf(" -> ");
        }
        printf("\n");
    }else{
        cout << "Fail" << endl;
    }
 
}
 
//======================//
//safety algorithm.
bool isSafe(process *p[PROCESS_CNT]){
    for(int i=0; i<PROCESS_CNT; i++){
        if(p[i]->isFinish()) continue;  //각각의 프로세스의 작업이 완료되었는지
        return false;
    }
 
    //모든 프로세스의 작업이 true이면
    return true;
}
 
//Banker's Algorithm
bool bankers(process *p[PROCESS_CNT], int *available, int *sequence){
    printProcess(p);
 
 
    for(int i=0; i<PROCESS_CNT; i++){
        for(int j=0; j<PROCESS_CNT; j++){
 
            if(!p[j]->isFinish() && p[j]->isWork(available)){//Finish[i] == false && need<= work
                p[j]->setFinish(true);
                p[j]->giveAllocation(available);
 
                printAvailable(available);  //available 출력
                sequence[i] = j;
                break;
            }
        }
    }
    return isSafe(p);
}
 
//======================//
 
int main(void){
    int sequence[PROCESS_CNT]={0};  //프로세스 수행 순서 저장을 위한 배열
 
    //초기 setting //
 
    int available[R_LEN] = {1,5,2,0}; //resource available.
    int allocation[PROCESS_CNT][R_LEN] = {{0,0,1,2}, {1,0,0,0}, {1,3,5,4}, {0,6,3,2},{0,0,1,4}};
    int maxResource[PROCESS_CNT][R_LEN] = {{0,0,1,2}, {1,7,5,0}, {2,3,5,6}, {0,6,5,2}, {0,6,5,6}};
    /*
    int available[R_LEN] = {3,3,2}; //resource available.
    int allocation[PROCESS_CNT][R_LEN] = {{0,1,0}, {2,0,0}, {3,0,2}, {0,0,0},{0,0,2}};
    int maxResource[PROCESS_CNT][R_LEN] = {{7,5,3}, {3,2,2}, {9,0,2}, {2,2,2}, {4,3,3}};
    */
    process *p[PROCESS_CNT];
    for(int i=0; i<PROCESS_CNT; i++){
        p[i] = new process(allocation[i], maxResource[i]);
    };
    //============//
    bool result = bankers(p, available, sequence);
    printResult(result, sequence);
    //============//
    for(int i=0; i<PROCESS_CNT; i++){
        delete p[i];
    }
    return 0;
}

3. 결과

4. 은행원 알고리즘에 대해

• 은행원 알고리즘은 deadlock을 탐지 혹은 회피 할때 사용한다고 했지만, 실제 돌아가는 프로그램에 적용하기 어렵다고 생각이 됩니다. 이유는 은행원 알고리즘은 해당 프로세스가 시작할 때 프로세스가 가지고 있어야할 자원의 최대 개수를 미리 알아야 하기 때문입니다. 실제 프로그램이 실행될때 어느정도의 자원을 요청할지 확신할 수 없으므로, 은행원 알고리즘을 사용하기 조금 힘들어 보입니다.

**문제 출처 : Operating System Concepts 8th Edition (공룡책 연습문제 7.10)