OS_Deadlock(2): Solution(Detection and Recovery)

교착상태에 대한 해결책은 당연히도 여러가지가 있다.

그 중, Deadlock Detection and Recovery에 대한 내용을 다뤄보려고 한다.

 

영어로 되어있는 전공책을 기반으로 내용 정리를 하는 것이기 때문에, 정리하다보면 한국어 단어 - 영어 단어 사이에서 왔다갔다 하게 되는데... 넓은 마음으로 양해 부탁드린다. (교착상태, 데드락, deadlock 제멋대로 왔다갔다 하면서 쓰는 것을 깨닫고 추가한 문장)

Deadlock Detection and Recovery

기본적으로 deadlock을 '탐지(detect)'하려면 deadlock이 발생해야한다.

즉, 일단 교착상태가 발생하도록 둔다. 그리고 발생했음을 탐지하면 바로 recovery 를 수행한다.

Detection

앞선 게시글 Deadlock(1):Problem(eth6n.tistory.com/7)의 그림에서 네모 안에 있던 '점'을 기억하시는지. 이 '점'이 인스턴스를 의미한다.
다시말해서, 특정 유형의 자원이 한 가지인 경우(자원 유형 당 인스턴스가 하나인 경우)와, 특정 유형의 자원이 여럿인 경우(자원 유형 당 인스턴스가 여럿인 경우)로 경우를 나누어 생각한다.

1. 자원 유형 당 인스턴스가 하나인 경우
   : 앞선 Deadlock(1):Problem 게시글에서 언급했던 그래프의 사이클 존재 유무를 통해 데드락을 탐지한다. 
   어떤 탐색 알고리즘을 사용하느냐에 따라 조금씩 달라질 수 있지만, 전공서적에 예시로 등장한 depth first search를 사용할 경우 그래프를 구성하는 vertex의 개수를 n이라고 했을 때, 데드락 탐지의 시간복잡도는 O(n^2) 라고 한다.
   #이산수학_그래프_사이클
   #알고리즘_시간복잡도
    
2. 자원 유형 당 인스턴스가 여럿인 경우
   : 아주 쵸큼 복잡해진다. 이건 책에 나온 예제를 보면서 정리해보는게 좋을 것 같다.
   일반화된 알고리즘은 다음과 같다. #공룡책 그대로 가져왔다.
   
   DEADLOCK DETECTION 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, if Allocation is not zero, then Finish[i] = false; Otherwise, Finish[i] = true
   Step 2. Find an index i such that both
       (a) Finish[i] == false
       (b) Request[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] == false for some i, then the system is in a deadlocked state. Moreover, if Finish[i] == false, then process Pi is deadlocked process.
   
   난 이걸 읽으면서 이해하려고 노력하다가 결국 유튜브를 찾아보고 한 인도 선생님의 설명을 듣고서야 이해했다.
   알고리즘 그대로 수행하면서 문제를 해설해보겠다. 다음은 예제이다. 데드락 여부를 판별해야 된다.

2.1-1) 우선, Allocation이 전부 0인 경우를 찾는다. 이 경우에 해당하는 프로세스에서는 데드락을 확인할 필요가 없다. 할당받은 자원도, 요청하는 자원도 없는, 종료된 프로세스이기 때문. 아쉽게도 그런 행운은 따라주지 않았다.

2.1-2) 이 시점에서 Work 에 해당하는 벡터(배열이라고 생각하면 된다.)에 Available 벡터를 불러온다. (Work = Available)
이때, Request 벡터가 이 벡터와 동일한 프로세스를 확인한다. P0 당첨. P0를 수행한다.

 

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

* 'Work' 랑 'Available'이랑 의미하는 바가 같다고 받아들이면 이해하기 쉽다. 당장 프로세스 수행에 필요한 자원이 'Work'이고, 해당 작업이 끝나면 자원을 돌려받아 그게 곧 'Available'의 의미를 갖게 되는 것.

2.1-3) Work에 해당하는 P0를 수행하는데 필요한 모든 자원을 돌려받았다. 이제 Work는 (0,1,0) 이다. 이때 Request에서 수행 할 수 있는 프로세스를 찾는다. P2 당첨. P2를 수행한다.

 

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

2.1-4) P2에 할당되어있던 자원을 돌려받았다. 이제 Work는 (3,1,3) 이다. 이때 Request에서 수행 할 수 있는 프로세스를 찾는다. P3 당첨. 사실 다른 프로세스도 가능하지만 i는 순차적으로 조건을 확인하기에 P3로 간다. P3을 수행한다.

 

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

 

2.1-5) P3에 할당되어있던 자원을 돌려받았다. 이제 Work는 (5,2,4) 이다. 이때 Request에서 수행 할 수 있는 프로세스를 찾는다. P4 당첨. 사실 다른 프로세스도 가능하지만 i는 순차적으로 조건을 확인하기에 P4로 간다. P4를 수행한다.

 

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

 

2.1-6) P4에 할당되어있던 자원을 돌려받았다. 이제 Work는 (5,2,6) 이다. 이때 Request에서 수행 할 수 있는 프로세스를 찾는다. P1 당첨. P1을 수행한다.

 

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

Work = (7, 2, 6)으로 모든 자원이 반환되었고, <P0, P2, P3, P4, P1> 순으로 아주 깔끔하게 모든 프로세스가 수행되었다.

데드락이 없는 것으로 판별되었다.

이제 여기서 문제를 변형한다. 

갑자기 P2의 Request가 (0,0,1)로 바뀌었다. 위에서 진행한 알고리즘대로 똑같이 진행해본다.

2.2-1) 우선, Allocation이 전부 0인 경우를 찾는다. 이 경우에 해당하는 프로세스에서는 데드락을 확인할 필요가 없다. 할당받은 자원도, 요청하는 자원도 없는, 종료된 프로세스이기 때문. 아쉽게도 그런 행운은 따라주지 않았다.

2.2-2) 이 시점에서 Work 에 해당하는 벡터(배열이라고 생각하면 된다.)를 Available 벡터와 같다고 간주한다.
이때, Request 벡터가 이 벡터와 동일한 프로세스를 확인한다. P0 당첨. P0를 수행한다.

 

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

2.2-3) P0에 할당되어있던 자원을 돌려받았다. 이제 Work는 (0,1,0) 이다. 이때 수행 할 수 있는 프로세스를 찾는다... 없다!

이런 경우, 프로세스 P1,P2,P3,P4에 대하여 데드락이 발생했다고 볼 수 있다.

 

여기까지가 Deadlock Detection이다. 데드락 발생을 확인했으면, 그것을 복구해야된다는 흐름으로 이어진다.

Recovery

'프로세스 종료 후 재실행' 이 대표적이고, 간단한 복구 방법이다.

단, 프로세스 종료를 데드락 발생 시점에서 전부 종료할지, 혹은 '정해진 순서'(프로세스 우선순위 등)에 따라서 필요한 프로세스만 종료할지 등의 차이가 존재할 뿐이다. 

이때, Starvation(특정 프로세스만 계속 우선순위에서 밀려서 종료되는 경우)가 발생할 수 있다. 이건 process scheduling에서 관리하는 것과 똑같이 종료 회수를 유한하게 제한해두는 등의 방법으로 해결 할 수 있겠다.

 

*오개념 지적 대환영*

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

 

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