데드락이란?

프로세스들이 서로 가진 자원을 기다리며 block된 상태

이전에 설명했지만, 데드락을 더 깊게 파헤쳐보자.

데드락의 발생조건

아주 당연한 조건들이다.

• 매 순간 하나의 프로세스만이 자원 사용 가능(프로세스 동기화 문제 해결법)
• 비선점형. 자원을 빼앗기는 것이 아닌, 자의적으로 내놓는다. 빼앗긴다면 데드락이 발생할 일이 없다.
• 자원을 가진 프로세스가 다른 자원을 기다리면서 보유자원을 놓지 않음.(자원이 두개 이상이구나)
• 자원을 기다리는 프로세스 간에 사이클이 형성됨. 꼬리물기로 서로의 자원을 탐닉함!

---

자원 할당 그래프

데드락이 일어날 수 있는지 알아보는 그래프다.

• 동글뱅이(P1, P2...)는 프로세스
• 사각형은 자원
• 사각형 안의 동글뱅이는 자원의 갯수
• 화살표는 요청이다.(프로세스가 가리키는건 자원 요청, 자원이 가리키는건 프로세스에 자원 탑재됨)

데드락의 조건은 이렇다.

1. 그래프에 사이클이 없으면, deadlock이 아니다.
2. 사이클이 있다면.
   2-1. 자원 타입마다 하나의 인스턴스가 있다면(자원 안의 동글뱅이 개수), deadlock
   2-2. 여러개의 인스턴스가 자원 타입마다 있다면, 가능성이 있다

=> 그래프니까, dfs나 bfs로 탐색해서 사이클 판별을 하면 되겠구만!

데드락을 막아보자!

데드락의 처리방법엔 총 4가지가 있다. 절반은 아예 발생하지 않게 전처리를 하는 것이고, 두가지는 발생하고 나서 후처리를 하는 것이다.

전처리 2가지.

1. deadlock prevention : 데드락의 필요조건 4가지 중 하나가 만족되지 않게 한다.

• 상호배제(mutual exclusion)
• 점유대기(hold and wait)
• 비선점(nopreemption)
• 순환 대기(cicular wait)
  

2. deadlock avoidance의 가능성이 없는 경우에만 할당 or 시스템 상태가 원래 상태로 돌아올수 있는경우에만 할당
   

deadlock avoidance는 2가지 방식으로 구현이 가능하다.

1. 자원당 하나의 인스턴스를 가지면, 위에서 설명한 자원 할당 그래프로.

2. 자원당 여러개의 인스턴스를 가지면, banker's Algorithm을 사용. 은행씨가 만든 알고리즘을 쓴다.
   
   

후처리(?)2가지

1. deadlock발생은 허용. 대신 deadlock을 탐색하는 루틴을 둬서 발견시 복구.
   

banker's알고리즘과 비슷한 방법으로 테이블을 짜서 계산한다.

데드락 복구방법은 두가지로 나뉜다.
1. 프로세스 하나 or 전부 죽이기
2. 희생양 찾아서 자원 뺏기. 동일한 프로세스가 희생양이 되면, Starvation문제가 생긴다. 따라서 자원을 뺏는 방식을 매번 다르게 해야함.

2. 무시

현대의 대부분의 OS는 후처리의 2개중 무시를 채택한다.

왜 그런거지..?!
=> 데드락이 발생하면, 사람이 알아 해결해라.
wow!

---

느낀점

데드락에 대해 심도깊게 배웠다. 데드락이 정확히 왜 생기는지(4가지 충족요건), 생겼을때의 해결방안은 무엇이 있는지(전처리 2개, 후처리1, 무시1). 또한 알고리즘과 자료구조에서 배운 그래프의 사이클을 탐색하는 방법도 연관되어있다. 역시 컴퓨터 과학 안의 과목들은 유기적으로 연결되어있구나 싶다