Banker's Algorithm cf. Detection Algorithm

Deadlock Avoidance는 거의 뱅커스 알고리즘이 다라고 보면 된다. 이름에서도 알 수 있듯이, 리소스 할당을 돈을 빌려주고 갚은 은행의 업무에 비유하여 고안된 알고리즘이다.

 

간단하게 예를 들어, 은행에 돈이 1000만원 있다. 그리고 3명의 고객이 은행에서 돈을 빌린다. 은행은 고객이 원하는 돈을 다 빌려 주면 바로 반환 받을 수 있다. 하지만 돈을 다 빌려주기 전까지는 강제로 반환받지 못한다.

 

  - 고객1이 총 600만원을 빌리고자 한다.

  - 고객2이 총 800만원을 빌리고자 한다.

  - 고객3이 총 400만원을 빌리고자 한다.

 

지금 현재 상태는 safe하다. 1-2-3, 1-3-2, 2-3-1 등등 모든 경우가 다 가능하다. 한꺼번에 필요한 돈을 다 빌려주고 다시 받은 후 다음 고객에게 빌려주면 되기 때문이다. 하지만 돈을 한꺼번에 빌려주는 일은 잘 없다. 조금씩 빌려주다가 아래와 같은 상태가 되었다고 하자.

 

 - 고객1에게 300만원을 빌려주고 300만원을 더 빌려줘야 한다.

 - 고객2에게 400만원을 빌려주고 400만원을 더 빌려줘야 한다.

 - 고객3에게 100만원을 빌려주고 300만원을 더 빌려줘야 한다.

 

이와 같은 상태가 Deadlock이다. 빌려 줄 수 있는 돈(할당 가능한 리소스)는 200만원이 남았는데 고객(프로세스)들은 더 큰돈을 요구하고, 돈을 받기 전까지는 반환하지 않기 때문이다. 이런 unsafe한 상태를 방지 하는게 Banker's Algorithm이다. 어떻게?

 

 - 고객1에게 200만원을 빌려주고 400만원을 더 빌려줘야 한다.

 - 고객2에게 400만원을 빌려주고 400만원을 더 빌려줘야 한다.

 - 고객3에게 100만원을 빌려주고 300만원을 더 빌려줘야 한다.

 

현재 남은 돈은 300이다. 그리고 현 시점에서 고객1이 돈을 100만원 더 빌려 달라고 한다. 빌려 줘야 할까?? 현 상태로는 남은 돈 300만원을 고객3에게 빌려주면 빌려준 돈을 모두 받을 수 있기 때문에 safe하지만 고객1에게 100만원을 빌려주는 순간 은행은 파산한다. (unsafe)

 

이런것을 미리 계산하여 적절한 allocation이 이루어 지도록 하는게 핵심이다.

 

자료 구조는 아래와 같다.

• n은 프로세스의 수, m은 리소스 타입의 수를 의미한다.

• Available : 일차원 배열, 각 리소스 타입별로 남은 인스턴스 정보를 저장한다. available[j]는 리소스j의 남은 인스턴스를 의미한다.

• Max : 이차원 배열, 프로세스 i 가 j 타입의 리소스를 최대로 얼마나 요구 할 것인가를 max[i,j]로 나타낸다.

• Allocation : 이차원 배열, 프로세스 i 에 j 타입의 리소스가 얼마나 할당 되었는지를 allocation[i,j]로 나타낸다.

• Need : 이차원 배열, 프로레스 i가 필요로 하는 j 타입의 리소스가 얼마나 남았는가를 need[i,j]로 나타낸다.
  (Need = Max - Allocation)

Safe한 상태란? 요구하는 할당량을 충족하는 프로세스들의 시퀀스를 하나라도 만들어 낼 수 있다면 safe = true;

 

바로 예제를 보자

 

5 processes P0  through P4 
3 resource types : A (10 instances),  B (5instances), and C (7 instances)

 

현재 할당 상태 :

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

Available : 3 3 2

 

safe한지, unsafe한지 확인 하려면 safe한 시퀀스를 하나라도 만들어 보면 된다. 가장 편하게 하려면 Need가 가장 적게 남은 프로세스부터 리소스를 할당해 주고 반환받아 보면 된다.

 

현재 할당 상태 :

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

Available : 3 2 1 -> 5 4 3

 

현재 할당 상태 :

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

Available : 4 2 1 -> 7 4 3

 

더 해볼 필요가 없을것 같다. 이런식으로 하나씩 처리 해 가면서 가능한 시퀀스가 하나라도 있는가를 검증 해 보면 된다.

이 문제에서 주어진 상태에선 P3 - P1 - P4 - P2 - P0 시퀀스도 가능하고, P1 - P3 - P4 - P0 - P2 도 가능하고.. 아주 많은 시퀀스가 가능하기 때문에 까다로운 문제가 아니다.

리소스를 할당 할 때 마다 이런식으로 검증 알고리즘을 거쳐서 안전한지 체크를 하는것이 Deadlock Avoidance이다.

 

 

이와 비슷한 알고리즘으로 Detection 알고리즘이 있다. Banker's Algorithm이 아직 할당되지 않은 리소스를 가상으로 할당 해 가면서 검증을 하는 것이라면, Detection 알고리즘은 현재 상태만 보고 데드락인지 아닌지 확인하면 되기 때문에 Banker's Algorithm에 비해 훨씬 간소화된 알고리즘이다.

 

Request 들어온 리소스가 얼마만큼인데, 현재 가용한 Available이 그만큼이 안될 경우 Deadlock 상태인지만 검증하는 것이다. 이때부턴 뱅커스 알고리즘과 같다. 현재 Need를 충족시킬 수 있는 다른 알고리즘을 보고 반환 받을게 있다면 반환 받은 후 프로세스 시퀀스를 만들어 낼 수 있는지 확인한다.

만약에 Need를 충족시켜 줄 것도 없고 반환 받을 것도 없다면 Deadlock인 것이다.

 

Banker's Algorithm 이나 Detection Algorithm 모두 Deterministic Algorithm이지만 Banker's는 리소스를 할당 하기 전에 데드락 방지(avoidance)를 위한 것이고(Allocation을 할지 안할지 Determine) Detection은 뭔가 일이 발생 한 후 데드락인지 아닌지를 확인하는 알고리즘이다.