<개인공부>/[Operating System]

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

사용자 BlockDMask 2017. 11. 24. 18:56
반응형

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

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


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. 소스 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
//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!=4printf(" -> ");
        }
        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;
}
cs


3. 결과


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

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

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

반응형