[OS] Deadlock (데드락)

 

<설명>

  - 사용자 A,B라는 2명과 연장 도구 '망치', '스패너' 총 2개 있다.두 사용자는 망치&스패너를 모두 써서 작업해야 한다.

    먼저 사용자 A는 망치를 사용하고, B는 스패너를 쓴다. 그러다 사용자 A는 스패너가 필요하기에 망치를 쥐고 기다린다.

    사용자 B도 자신의 작업을 마쳐 망치가 필요로 하지만 A를 배려하여 기다린다.

    ==> 사용자 A,B는 각자의 tool을 가진 채로 한 쪽이 먼저 주겠거니... 하며 영원히 기다린다(loop).

A two-process deadlock. Source: Harvard 2018

 

 

  - 다수의 process들 사이에서 resource가 공유되며 발생하는 문제

  - 공유된 resource 는 Files, Database Tables, Memory, Peripherals(마우스, 프린터 등 주변기기), Network 등이 있음

  - deadlock 은 Threads, Users, Transactions, PCs 등에서 나타난다.

 

Blocking calls can lead to communication deadlocks. Source: Anthony 2016, fig. 3.40

  ** [Starvation] : 한 process가 다른 process에게 priority가 밀려 resource를 계속 못 받는 상황도 있다 (자본주의)

  ** [Livelock] : process들이 일은 안 끝내고(초과근무), 계속해서 서로 resource를 주고 받거나(했던 일 또 하기) state 변화가 일어나는 경우가 있다. (야근 수당 횡령)

 

---

 

<문제 발생 실례>

1) [Database Application 에서 자주 발생]

    - A라는 table 접근에 반드시 필요한 서로 다른 B,C table의 각 transaction에서 lock이 발생

    ==> database가 distributed 되었다면 사태는 더 심각해진다!

 

1-1) [글쓴이 경험]

  - table A 와 B의 data를 중복 제거하며 합치고 싶었다.

  - query가 잘못되었는지 갑자기 작업중에 멈췄다. sql 프로그램은 꺼지지 않았으며 작업관리자에서의 process kill도 안 먹혔다.

  - PC를 껐다 키니 합치려 했던 table 2개 뿐 아니라 database가 날아갔다?!

  - log를 확인해보니 column에 문제가 있어 table끼리 transaction 하다가 lock이 걸렸던 것.

  - data 수십만개가 날아가서 마음이 몹시 아팠다.

 

2) [resource를 공유하는 Multithreaded Application 이나 Multiprocessing System 에서 발생]

  - 한 process 에선 파일을 읽고 그 파일을 출력하려 한다.

  - 다른 process에서 출력을 하다가 뜬금없이 첫번째 process가 읽고 있는 file에 access하려 한다.

  ==> 이제 두 process는 deadlock 되었다

 

---

 

<deadlock 필수 발생 조건>

1) Mutual Exclusion :

  - resource는 한번에 1개를 초과한 process에 할당 불가

2) Holt-and_Wait :

  - resource를 지닌 process가 다른 resource가 오길 기다림

3) No Pre-emption :

  - resource를 지닌 process는 강제 혹은 자발적으로 resource를 포기하지 않는다. (코인에 물린 사람 같다)

4) Circular Wait :

  - 각 process는 다른 process가 가진 resource를 기다린다. 이 조건은 Holt-and-Wait 조건의 확장판이다.

 

---

 

<비교 이미지>

Resource allocation graphs. Source: Adapted from Bell 2006, figs. 7.2-7.3

  ==> resource를 중간에 뺄 다른 경로가 있으면 deadlock이 없다.

  ==> 신용불량자(process)가 빚(resource)을 카드 돌려막기 하다가 터진다(deadlock)

 

---

 

<deadlock 대처 방안>

Techniques for handling system deadlocks. Source: Isloor and Marsland 1980, table 1

1) Prevention (예방)

2) Avoidance (회피)

  - algorithm을 통해 연속된 resource 요청이 deadlock을 발생시킬 것 같으면 반려함.

3) Detection (탐지)

  - 주기적으로 deadlock 체크. 자주 확인하면 성능 부하. 반대로 너무 확인 안하면 금방 못 찾음

4) Recovery (복구)

  - deadlock 발생 조건 중 하나를 파괴.

  - 여러 process 중 하나가 제거되는 victim selection 발생 가능.

  - process가 가진 resource를 강제 방출

 

5) deadlock 이 아주 가끔 발생한다면, 그냥 문제가 일어나게 두고 system을 reboot 함. (Window & Linux에서 이렇게 함)

 

** process가 resource 1개만 할당 받게 하지 말고 필요한 모든 걸 할당받게 하자

** resource들을 공유할 때 pipeline pattern 같은 high-level pattern 을 쓰자

** communication deadlock을 방지하려면 적어도 1개의 process가 non-blocking IO여야 한다. thread가 막혀도 보낸다!

 

---

 

<출처 1> https://devopedia.org/deadlock

<출처 2> https://www.geeksforgeeks.org/introduction-of-deadlock-in-operating-system/

<출처 3> https://www.cs.uic.edu/~jbell/CourseNotes/OperatingSystems/7_Deadlocks.html