[OS] 데드락

반효경 교수님 운영체제 강의와 도서를 정리한 내용입니다.

데드락이란

일련의 프로세스들이 서로가 가진 자원을 기다리며 block 된 상태
이때의 자원은 IO 디바이스, CPU, 메모리, 세마포어 등이 될 수 있다.

데드락의 4가지 조건

데드락은 4가지 조건을 만족해야 성립된다.

• mutual exclusion (상호 배제) : 매 순간 하나의 프로세스만이 자원을 사용할 수 있다.
• no preemption (비선점) : 프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않는다. 생각해보면 선점이 가능하다면 그대로 빼앗아 쓰면 되기 때문에 데드락이 생기지 않는다.
• hold and wait (보유 대기) : 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있는다.
• circular wait (순환 대기) : 자원을 기다리는 프로세스 간에 사이클이 형성되어야 한다.

  데드락 해결 방법

1. Deadlock Prevention : 데드락의 4가지 필요 조건 중 어느 하나가 만족되지 않도록 하는 것
2. Deadlock Avoidance : 자원 요청에 대한 부가적인 정보를 이용해서 deadlock의 가능성이 없는 경우에만 자원을 할당.
3. Deadlock Detection and Recovery : deadlock 발생은 허용하되 그에 대한 detection 루틴을 두어 deadlock 발견시 recover
4. Deadlock Ignorance : deadlock 을 시스템이 책임지지 않는다. 대부분의 운영체제가 이 방법을 택한다. 데드락을 탐지하고 회피하는데 쓰이는 비용이 낭비라고 판단했기 때문이다.

   1. Deadlock Prevention

   데드락의 4가지 필요 조건 중 어느 하나가 만족되지 않도록 하는 것이다. 4가지 조건을 하나씩 만족하지 않을 방법을 살펴보자.

• mutual exclusion (상호 배제) : 매 순간 하나의 프로세스만이 자원을 사용할 수 있다.
  -> 동기화를 위해 하나의 프로세스만이 자원을 사용해야 하는 경우 이 제약을 풀어버리면 안되기 때문에 이 조건을 깰 방법은 없다.
• no preemption (비선점) : 프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않는다. 생각해보면 선점이 가능하다면 그대로 빼앗아 쓰면 되기 때문에 데드락이 생기지 않는다.
  -> 특정한 조건 하에 선점이 되도록 한다. 그 조건은 바로 프로세스가 필요한 자원을 다 보유하지 않은 경우이다. 프로세스가 어떤 자원을 기다리는 경우 다른 프로세스에 의해 선점 당할 수 있으며 선점 당한 프로세스는 자원을 모두 얻고나서야 다시 실행된다. (선점 당했다가 다시 돌아왔을 때 정상 작동을 해야하기 때문에 state 를 쉽게 저장하고 복원할 수 있는 CPU 와 메모리에서 쓴다.)
• hold and wait (보유 대기) : 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있는다.
  -> 프로세스가 자원을 요청할 때 다른 어떠한 자원도 가지고 있지 않아야한다. 그렇게 하기 위한 방법은 프로세스 시작시 모든 필요한 자원을 미리 할당받게 하는 방법과 자원이 필요할 경우 보유 자원을 모두 놓아버리고 다시 요청하는 방법이 있다.
• circular wait (순환 대기) : 자원을 기다리는 프로세스 간에 사이클이 형성되어야 한다.
  -> 모든 자원 유형에 할당 순서를 정하여 정해진 순서대로만 자원을 할당한다.

이러한 방법은 결국엔 자원을 활용하기 때문에 효율성과 처리량을 감소시킨다. 그리고 비선점 조건의 경우 선점 당하게 하면 영원히 실행이 안되는 프로세스가 생길 수 있다. 순환 대기 또한 비슷한 맥락이다. 이는 starvation 문제로도 이어짐을 알 수 있다.

2. Deadlock Avoidance

자원 요청에 대한 부가적인 정보를 이용해서 deadlock의 가능성이 없는 경우에만 자원을 할당한다. 즉 deadlock 없이 실행될 수 있는 safe sequence 가 있으면 safe state 라고 부르며 이 경우에만 자원을 할당하는 것이다. unsafe state 이면 deadlock 이 일어날 확률이 존재한다.

safe state 임을 확인하는 방법에는 single instance per resource type 이면 Resource Allocation Graph Algorithm, multiple instances per resource type 이면 Banker's Algorithm 를 사용한다.

Resource Allocation Graph Algorithm

점선은 Assignment Edge 라고 불리며 해당 자원 요청을 함 을 뜻하고 실선은 Request Edge 로 미래에 요청할 수 있음 을 뜻한다. 만약 자원 요청을 통해 실선이 점선으로 바꼈고 이때 cycle 이 생기지 않는다면 요청 자원을 할당한다.
이때의 문제점은 cycle 생성 여부를 확인하는데 자원을 써야한다는 것이고 이때의 시간복잡도는 O(n^2) 이다.

Banker's Algorithm

가정 1 : 필요한 자원을 모두 얻은 후에는 (max 를 가진 이후에는) 해당 프로세스는 자원을 다시 반납한다.
가정 2 : 자원이 요청할 때는 항상 최댓값을 요청한다고 가정하며 이를 처리할 수 있는 경우 자원을 할당한다.


예를 들어 프로세스 1 이 (1,0,2) 를 요청했지만 우리는 항상 safe 하게 최댓값을 요청한다고 생각한다. 그렇게 되면 사실상 (1,2,2) 를 요청한 경우를 생각해야 한다. 이 경우 남은 자원으로 충분히 할당 가능하기 때문에 okay. 그리고 프로세스 1은 유한 시간 후에 자기가 갖고 있는 모든 자원을 반납하게 된다.

이러한 식으로 생각하면 safe sequence 1, 3, 4, 2, 0 이 존재하며 이 경우 자원을 할당한다.

3. Deadlock Detection and Recovery

deadlock 발생은 허용하되 그에 대한 detection 루틴을 두어 deadlock 발견시 recover 한다. deadlock은 Resource Allocation Graph Algorithm 과 Banker's Algorithm 으로 탐지 가능하다. 이때 데드락이 발견되면 Recovery 방법은 다음과 같다.

• Process termination : 데드락된 프로세스를 다 중지시키거나 하나씩 데드락이 없어질 때까지 종료시켜본다.
• Resource Preemption : safe state 로 롤백을 하여 다시 프로세스를 시작한다. 이때의 롤백은 최소 비용으로 할 수 있도록 하는 프로세스를 선택하여 한다. 하지만 이또한 동일한 프로세스를 롤백 시키면 starvation 문제가 생길 수 있기 때문에 돌아가면서 되도록 우선순위를 정하여 한다.