이전 포스트 : 데드락 회피에서는 데드락 회피의 개념, 안전 상태와 그렇지 않은 상태의 개념을 알아보았다. 그리고 데드락 회피를 구현하기 위한 자원 할당 그래프 알고리즘(Resource-Allocation Graph Algorithm)과 은행원 알고리즘(Banker's Algorithm)의 이론적인 측면들 또한 살펴 보았다.
오늘 포스트에서는일정 금액이 있어야 사업을 마치고 상환을 할 수 있는 고객들에게 어떤 순서로 한정된 은행의 돈을 빌려 주고 돌려 받아야 모든 고객들의 요구를 만족 시킬 수 있는지 고민하는은행원 알고리즘의 실제 예제를 만들어 봄으로써 은행원 알고리즘에 대한 이해도를 높이도록 한다.
잠깐! 시작하기 전에
본격적으로 시작하기 전에 은행원 알고리즘에 대해 잠깐 되짚어 보자. 은행원 알고리즘은 아래와 같은 제약 사항과 자료구조, 알고리즘들을 필요로 한다. 아래 사항들에 대한 자세할 설명은 [여기]를 참고 하자.
- 은행원 알고리즘은 할당 할 수 있는 자원의 수가 일정해야 함.
- 시스템의 프로세스 갯수가 일정해야 함
- 불안전 상태 방지를 위해 자원 이용도가 낮음
- Available(가용자원), Max(프로세스 최대 요구 자원), Allocation(현재 프로세스에 할당 된 자원), Need(프로세스가 작업을 마치기 위해 추가 필요한 자원). 4가지 자료 구조가 필요함.
- 프로세스가 안전하게 자원을 요청하기 위한 자원 요청 알고리즘
- 프로세에게 자원을 할당 했을 때 안전 상태가 유지되는지 확인하기 위한 안전 상태 판단 알고리즘
가정
- 위에서 은행원 알고리즘은 프로세스의 개수가 일정해야 한다고 했다. 이 시스템에는 P0부터 P4까지 총 다섯개의 프로세스가 있다고 가정한다.
- 할당 할 수 있는 최대 자원의 개수도 정해져 있어야 한다고 했다. 이 시스템에서는 A, B, C 세가지 타입의 자원이, 자원A 10개, 자원B 5개, 자원C 7개가 있다고 가정한다.
- 특정 시점 T0 때 시스템의 자원 할당 테이블이 아래와 같다고 가정한다.
Allocation은 현재 시점에 각 프로세스에게 할당 되어 있는 자원.
Max는 각 프로스세들이 작업을 완료하기 위해 최종적으로 필요한 자원.
Need는 현시점에 각 프로세스들이 작업을 완료 하기 위해 추가적으로 필요한 자원.
Avaiable은 현재 시스템 상에서 가용한 자원을 나타낸다.
구현
은행원 알고리즘의 핵심은 :
- 현재 가용자원(Available)과 각 프로세스들이 작업을 완료하기 위해 필요한 자원(Need)을 비교하여
- 당장 작업을 마칠 수있는 프로세스 부터 자원을 할당하여
- 그 프로세스가 작업을 완료하고 반환하는 자원을 다른 프로세스에게 다시 할당
위와 같은 방식으로 모든 프로세스들이 필요한 자원을 할당 받을 수 있도록 하는 방식이다.
예를 들어 P0의 경우, 현재 각각의 자원 A:0, B:1, C:0 를 할당 받았고 작업을 완료하기 위해 A:7, B:4, C:3의 추가자원이 더 필요하다. 하지만 현재 시스템상에서 가용자원은 A:3, B:3, C:2 밖에 없으므로 P0은 당장 작업을 완료 할 수 없는 상태다.
P1의 경우는 A:1, B:2, C:2의 자원만 추가 된다면 작업을 마치고 Max(A:3, B:2, C:2)의 자원을 되돌려 줄 수 있다. 현재 시스템의 가용자원이 P1의 완료 조건을 만족하므로 P1의 작업이 완료 되고 가용자원은 다시 Available(A:5, B:3, C:2)가 된다.
왜 P1이 Max(A:3, B:2, C:2)의 자원을 돌려 줬는데 Available이 A:6, B:5, C:4가 아니냐고 묻는 사람이 있었다. P1의 작업을 완료하기 위해 할당 했던 A:1, B:2, C:2 의 자원이 있었다는 것을 잊지말자. 현재 가용 자원은, 이전 Available - Need + Max라고 생각하면 된다.
이와 같이 프로세스들을 순회하며 각 프로세스들의 필요 자원과 가용자원들을 비교하여 자원을 할당하는 것이 은행원 알고리즘이다. 간단하다.
아래는 위에서 이야기한 내용을 C++ 코드로 구현한 것이다. 코드를 살펴 보면 좀더 은행원 알고리즘에 대한 이해에 도움이 될것이다.
- Vector 클래스
은행원 알고리즘에 핵심적으로 관여하지는 않지만 모든 자원 타입을 순회하는 코드를 매번 만들긴 번거로우므로 이를 추상화한 클래스를 추가하도록 한다.
template <int COUNT>
class Vector
{
int resources[COUNT] = {};
public:
Vector() = default;
Vector(const int rhs[COUNT]);
Vector& operator = (int rhs[COUNT]);
bool operator <= (const Vector& rhs) const;
Vector& operator -= (const Vector& rhs);
Vector operator - (const Vector<COUNT>& rhs);
Vector operator + (const Vector<COUNT>& rhs);
int& operator[](int index);
};- Process 클래스
Process 클래스는 프로세스가 작업을 처리하기 위해 필요한 최대 자원(Max), 현재 할당되어 있는 자원(Allocation), 추가 필요 자원(Need)에 대한 정보를 가지고 있다.
class Process
{
public:
// 프로세스 상태
enum class State
{
Success,
Wait,
Error
};
State Request(const Vector<RESOURCE_TYPE_COUNT>& request)
{
// 만일 요청 자원이 필요 자원이 보다 작거나 같다면 2번 과정으로 이동
// 그렇지 않다면 프로세스 최대 필요 자원양 보다 많이 요청한 것이므로 에러를 발생 시킨다.
if (request <= this->need)
{
// 만일 요청 자원이 가용 자원이 보다 작거나 같다면(Requesti <= Available) 3번 과정으로 이동
// 그렇지 않다면 현재 가용 자원이 부족한 상태이므로 대기한다.
if (request <= Available)
{
Vector<RESOURCE_TYPE_COUNT> tmpAvailable = Available;
Vector<RESOURCE_TYPE_COUNT> tmpAllocation = allocation;
Vector<RESOURCE_TYPE_COUNT> tmpNeed = need;
// 아래와 같이 '자원 할당 상태'를 수정하여 시스템이 요청된 리소르를 할당한 척 하도록 한다.
Available = Available - request;
allocation = allocation + request;
need = need - request;
// 안전 상태 판단 알고리즘을 이용해 현재 상태가 '안전 상태'인 경우라면
// 시스템은 프로세스에게 자원을 할당해주고 트랜잭션을 완료 한다.
// 하지만 안전 상태가 아닌 경우 프로세스는 자원을 요청 할 수 있는 상태가 될때 까지 대기하며
// '자원 할당 상태'는 이전 상태로 복구 된다.
if (false == check_safe_state())
{
Available = tmpAvailable;
allocation = tmpAllocation;
need = tmpNeed;
return State::Wait;
}
return State::Success;
}
else
{
return State::Wait;
}
}
else
{
return State::Error;
}
}
Vector<RESOURCE_TYPE_COUNT> max; // 최대 요구 가능 자원
Vector<RESOURCE_TYPE_COUNT> allocation; // 현재 할당 자원
Vector<RESOURCE_TYPE_COUNT> need; // 추가 필요 자원
};- 안전 상태 체크
// Work[m], Finish[n]. 이렇게 두개의 1차원 배열이 있다.
Vector<RESOURCE_TYPE_COUNT> Work;
bool Finish[PROCESS_COUNT] = {};
bool check_safe_state()
{
// Step 1
// 알고리즘이 시작 되면 Work := Available로, Finish[i] := false 로 초기화 된다
Work = Available;
for (int i = 0; i < PROCESS_COUNT; i++)
{
Finish[i] = false;
}
// 안전 상태를 결정하기 위해 m x n2 만큼의 오퍼레이션이 필요 할 수 있다.
for (int i = 0; i < PROCESS_COUNT; i++)
{
for(int j=0; j< PROCESS_COUNT; j++)
{
Process& process = Processes[j];
// Step 2
// 각 프로세스가 아래의 두 조건에 해당하는지 검사한다.
// Finish[i] = false
// Needi <= Work
// 조건에 부합한다면 3번으로, 만일 조건에 부합하는 프로세스가 없다면 4번으로
bool found = false;
if (false == Finish[j] && process.need <= Work)
{
found = true;
}
// Step 3
// Work := Work + Allocation
// Finish[j] := true
// 2번 과정으로 이동
if (true == found)
{
Work = Work + process.allocation;
Finish[j] = true;
std::cout << "P" << j << " >> ";
}
}
}
// step 4
// 만일 모든 Finish[i]가 true면 현재 상태는 안전한 상태다.
for (int i = 0; i < PROCESS_COUNT; i++)
{
if (false == Finish[i])
{
return false; // not safe state
}
}
return true; //ok, safe state
}전체 코드
#include <iostream>
constexpr int PROCESS_COUNT = 5;
constexpr int RESOURCE_TYPE_COUNT = 3;
constexpr int TotalResource[RESOURCE_TYPE_COUNT] = {
10, 5, 7
};
constexpr int Max[PROCESS_COUNT][RESOURCE_TYPE_COUNT] = {
{7, 5, 3},
{3, 2, 2},
{9, 0, 2},
{2, 2, 2},
{4, 3, 3},
};
constexpr int Allocation[PROCESS_COUNT][RESOURCE_TYPE_COUNT] = {
{0, 1, 0},
{2, 0, 0},
{3, 0, 2},
{2, 1, 1},
{0, 0, 2},
};
template <int COUNT>
class Vector
{
int resources[COUNT] = {};
public:
Vector() = default;
Vector(const int rhs[COUNT])
{
for (int i = 0; i < COUNT; i++)
{
resources[i] = rhs[i];
}
}
Vector& operator = (int rhs[COUNT])
{
for (int i = 0; i < COUNT; i++)
{
resources[i] = rhs[i];
}
return *this;
}
bool operator <= (const Vector& rhs) const
{
for (int i = 0; i < COUNT; i++)
{
if (resources[i] > rhs.resources[i])
{
return false;
}
}
return true;
}
Vector& operator -= (const Vector& rhs)
{
for (int i = 0; i < COUNT; i++)
{
resources[i] -= rhs.resources[i];
}
return *this;
}
Vector operator - (const Vector<COUNT>& rhs)
{
Vector<COUNT> result;
for (int i = 0; i < COUNT; i++)
{
result.resources[i] = resources[i] - rhs.resources[i];
}
return result;
}
Vector operator + (const Vector<COUNT>& rhs)
{
Vector<COUNT> result;
for (int i = 0; i < COUNT; i++)
{
result.resources[i] = resources[i] + rhs.resources[i];
}
return result;
}
int& operator[](int index)
{
return resources[index];
}
};
Vector<RESOURCE_TYPE_COUNT> Available = TotalResource;
Vector<RESOURCE_TYPE_COUNT> Work;
bool Finish[PROCESS_COUNT] = {};
bool check_safe_state();
class Process
{
public:
enum class State
{
Success,
Wait,
Error
};
Process(const int max[RESOURCE_TYPE_COUNT], const int allocation[RESOURCE_TYPE_COUNT])
{
this->max = max;
this->allocation = allocation;
this->need = this->max - this->allocation;
for (int i = 0; i < RESOURCE_TYPE_COUNT; i++)
{
Available[i] = Available[i] - allocation[i];
}
}
State Request(std::initializer_list<int> li)
{
int request[RESOURCE_TYPE_COUNT];
std::copy(li.begin(), li.end(), request);
return Request(request);
}
State Request(const Vector<RESOURCE_TYPE_COUNT>& request)
{
if (request <= this->need)
{
if (request <= Available)
{
Vector<RESOURCE_TYPE_COUNT> tmpAvailable = Available;
Vector<RESOURCE_TYPE_COUNT> tmpAllocation = allocation;
Vector<RESOURCE_TYPE_COUNT> tmpNeed = need;
Available = Available - request;
allocation = allocation + request;
need = need - request;
if (false == check_safe_state())
{
Available = tmpAvailable;
allocation = tmpAllocation;
need = tmpNeed;
return State::Wait;
}
return State::Success;
}
else
{
return State::Wait;
}
}
else
{
return State::Error;
}
}
Vector<RESOURCE_TYPE_COUNT> max;
Vector<RESOURCE_TYPE_COUNT> allocation;
Vector<RESOURCE_TYPE_COUNT> need;
};
Process Processes[PROCESS_COUNT] = {
Process(Max[0], Allocation[0]),
Process(Max[1], Allocation[1]),
Process(Max[2], Allocation[2]),
Process(Max[3], Allocation[3]),
Process(Max[4], Allocation[4])
};
bool check_safe_state()
{
// Step 1
Work = Available;
for (int i = 0; i < PROCESS_COUNT; i++)
{
Finish[i] = false;
}
for (int i = 0; i < PROCESS_COUNT; i++)
{
for(int j=0; j< PROCESS_COUNT; j++)
{
Process& process = Processes[j];
// Step 2
bool found = false;
if (false == Finish[j] && process.need <= Work)
{
found = true;
}
// Step 3
if (true == found)
{
Work = Work + process.allocation;
Finish[j] = true;
std::cout << "P" << j << " >> ";
}
}
}
// step 4
for (int i = 0; i < PROCESS_COUNT; i++)
{
if (false == Finish[i])
{
return false; // not safe state
}
}
return true; //ok, safe state
}
int main()
{
Processes[1].Request({ 1, 0, 2 });
}결과
P1 >> P3 >> P4 >> P0 >> P2 >>
