OS_Deadlock(3): Solution(Prevention and Avoidance -Banker's Algorithm)

Deadlock Prevention and Avoidance - 교착상태 예방 및 회피

교착상태에 대한 여러 해결책 중 예방 및 회피에 대해 정리해 보겠다.

그 중 대표적인 교착상태 회피 기법으로 Banker's Algorithm이 있다.

Prevention, 예방

간단하다. 이전에 정리해둔 Deadlock 발생조건 네 가지를 동시에 만족하지 않도록 (따라서 Deadlock이 발생하지 않도록) 하는 것이다.

• Mutual Exclusion (상호 배제)
  : 공유 가능한 자원에 한해서는 상호 배제가 필요없다 (가령, Read-only files). 한편, 공유가 불가능한 자원 (e.g. printers)들은 상호 배제시킨다.
• Hold and Wait (점유 대기)
  : 프로세스 실행을 위해 자원을 요청할 때, 다른 자원을 점유하고 있지 않도록 한다. 이는 자원을 점유하기 위한 syscall(시스템 호출)을 프로세스가 실행을 위한 syscall 이전에 발생시킴으로서 구현할 수 있다. 효율이 좋지 않다는 단점이 있다.
• No Preemption (비선점)
  : 프로세스 실행을 위해 자원을 요청했을 때, 요청한 자원을 당장 할당 받을 수 없다면, 점유중인 모든 자원을 반환한다. 강제로 자원을 반환할 수 없다는 조건을 부정하는 것. 
  흠... Preempt를 사전에 검색하면 '선점'이라고 나오는데, 이게 누가 무엇을 선점하는건지 생각할 필요 없이, Preempt 라는 개념을 그냥 '강제 반환' 으로 받아들이면 훨씬 직관적이다. 
• Circular Wait (순환 대기)
  : 자원마다 '순서'를 부여한다('순서'로 이해할 수도 있고, '우선순위'로 이해할 수도 있을 것 같다. 즉, impose order/priority for all resource types). 따라서 필요한 자원의 요청을 수행할 때에도 어떤 자원유형인지에 따라 요청할 순서가 존재하게 된다.

Avoidance, 회피 : Banker's Algorithm

시스템이 항상 safe state에 있도록 보장하여 교착상태를 회피하는 대표적인 기법인 Banker's Algorithm에 초점을 맞추어 정리해보려고 한다. 그 유명한 컴퓨터과학자 다익스트라께서 고안해내신 알고리즘이다. 

 

SAFETY ALGORITHM  (Banker's Algorithm)

Step 1. Let Work and Finish be vectors of length m and n, respectively.
Initialize:
    (a) Work = Available
    (b) For i = 1, 2, ... n, Finish[i] = false;
Step 2. Find an index i such that both
    (a) Finish[i] == false
    (b) Need[i] is less then or equal to Work
    
    if no such i exists, go to step 4

Step 3. Work = Work + Allocation[i]
    Finish[i] = true
    go to step 2
Step 4. If Finish[i] == true for all i, then the system is in a safe state

 

시간복잡도: O(m(n^2))

Deadlock Detection and Recovery 알고리즘에서 못보던(?), 사실은 똑같지만, 데이터구조가 생겼다 : 바로 Max와 Need

Max 는 프로세스가 특정 자원유형에 대해 요청할 수 있는 자원의 최대치이다.

Need 는 프로세스가 수행하는데에 필요한 자원이다.

#Deadlock Detection and Recovery: eth6n.tistory.com/8

 

이제 예제를 풀어보면서 개념을 확실히 잡아보자.

Operating System Concepts, A. Silberschatz, P.Galvin, G.Gagne, 8.6.3.3 

1) 가장 먼저 해야될 것은, Need를 계산하는 것이다. Need = Max - Allocation , 즉 Need는 요청할 수 있는 최대치에서 현재 할당받은 만큼을 뺀 만큼이다. 따라서 계산을 하면:

2) 그리고 다음으로, Work 에 Available 을 불러온다 (Work = Available). 이제 Work는 (3,3,2)이다. 이제 우리가 할 일은 프로세스 별로 Need와 Work를 비교하는 것.

 

3) T0 부터 순차적으로 Need를 확인했을 때, 수행 가능한 프로세스를 찾는다 (Need less then or equal to Work). T1 당첨. T1을 수행한다. 

 

Work = Work + Allocation(T1)로 업데이트된다.

 

4) T1 수행종료된 후, Work는 (5,3,2) 이다. 다시 순차적으로 수행가능한 프로세스를 찾는다. T3 당첨. T3 을 수행한다.

 

Work = Work + Allocation(T3)로 업데이트된다.

 

5) T3 수행종료된 후, Work는 (7,4,3) 이다. 다시 순차적으로 수행가능한 프로세스를 찾는다. T4 당첨. T4 를 수행한다.

 

Work = Work + Allocation(T4)로 업데이트된다.

 

6) T4 수행종료된 후, Work는 (7,4,5) 이다. 다시 순차적으로 수행가능한 프로세스를 찾는다. T0 당첨. T0 를 수행한다.

 

Work = Work + Allocation(T0)로 업데이트된다.

 

7) T0 수행종료된 후, Work는 (7,5,5) 이다. 다시 순차적으로 수행가능한 프로세스를 찾는다. T2 당첨. T2 를 수행한다.

 

Work = Work + Allocation(T2)로 업데이트된다.

 

Work = (10, 5, 7)로 모든 자원이 반환되었고, <P1, P3, P4, P0, P2> 순으로 safe state에서 교착상태 없이 시스템이 실행됨을 알 수 있다.

모르는 척 무시하기

사실 교착상태 해결법에 마지막으로 소개되고 있는 방법은 시스템 레벨에서는 무시하는 방법이다.

진짜 최고의 방법일지도(?)

다시말해, 시스템 차원에서 해결하려고 할 필요 없이 유저 레벨의 Application 개발자들이 알아서 문제가 발생하지 않게 코드를 짜라고 하는 것이다. 대부분의 운영체제가 이 방법을 택한다고 한다(!) e.g. UNIX, Windows 등

 

나도 공부 안하고 모르는 척 무시하고싶다...

 

*오개념 지적 대환영*

#키워드 : (게시글이 있는 경우) 링크를 참고하시거나, 검색하면서 읽어주세요.이해에 꼭 필요한 개념입니다.

 

해당 게시글은 Operating Systems: Three Easy Pieces(#혜성책), Operating System Concepts (#공룡책), 그리고 이 도서를 기반으로 한 학부 수업 자료를 참고하여 작성하였습니다.