[OS] Deadlock

Deadlock이란

Deadlock은 교착상태. 즉 process나 thread가 발생 가능성이 없는 이벤트를 기다리는 상태로써, 원하는 자원 혹은 특정 이벤트를 하염없이 기다리는 것을 말한다.

Deadlock과 Starvation은 계속 일을 못하는 상태로 비슷한 듯 보이지만,

구분	Deadlock	Starvation
기다리는 자원	자원/이벤트	CPU(processor)
발생 가능성	없음	있음 (우선순위에서 밀려서 계속 웨이팅)
존재하는 곳	asleep state에서 발생	ready state에서 발생

• blocked/asleep state란, 프로세스가 특정 이벤트 혹은 필요한 자원을 기다리는 상태이다.
• ready state란, CPU(processor)를 기다리는 상태이다.

아래 그림으로 Deadlock을 쉽게 표현할 수 있을 것 같다.
ex. 프론트 개발자는 충전기를 가져오고, 백엔드 개발자는 노트북을 가져온 상황을 가정해 작업을 해야 한다면, 각자 작업을 해야 하기에 자원을 놓아줄 생각이 없는데 상대의 자원을 대기하고 있기에 Deadlock 상태에 빠지게 된다.

Deadlock 발생 조건

아래 4가지 조건이 모두 성립해야 Deadlock이 발생한다.
1,2번째는 자원의 특성이고 3,4번째는 프로세스의 특성이다.

1. Exclusive use of resources
한순간에 한 프로세스만 사용할 수 있는 자원이다.
2. Non-preemptible resources
선점당하면, 이후 다른 프로세스가 자원을 가지고 진행하는데 문제가 발생하기에 해당 프로세스의 작업이 끝날 때까지 반납하지 않는 자원이다.
3. Hold and wait (Partial allocation)
자원을 하나 hold한 후 다른 자원을 요청하는 것이다. 반대로 자원이 하나도 없거나, 요청할 자원이 없다면 Deadlock의 원인이 되지 않을 것이다.
4. Circular wait
위 그림과 같이 점유와 대기 형태로 순환 사이클에 갇혀 빠져나갈 수 없는 상태가 되는 것이다.

Deadlock 해결 방법

1. Deadlock prevention methods (교착상태 예방)

4개의 deadlock 발생 조건 중 하나를 제거하여 Deadlock이 절대 발생하지 않도록 하는 것이다. 결론부터 말하자면, Deadlock이 절대 발생하지 않을 방법이나 심각한 자원 낭비가 발생하고, 비현실적이다.

1) 혼자 쓰는 자원이 아닌 모든 자원을 공유하도록 허용한다. 이는 현실적으로 불가능하다.

2) 모든 자원에 대해 선점을 허용한다. 누구든지 자원을 뺏어갈 수 있다는 것인데 현실적으로 불가능하다.
해서 유사하게 구현한다면, 프로세스가 할당받을 수 없는 자원(다른 프로세스에 할당된 자원)을 요청한다면, 기존에 가지고 있던 자원을 모두 반납하고 작업을 취소하는 방식이다. 이 또한 문제가 되는 것은 다시 작업을 하려 할 때 처음부터 다시 시작해야 하기에 심각한 자원 낭비로 이어져 비현실적이다.

3) 자원을 하나 hold 한 후 다른 자원을 요청하지 않고, 필요한 자원을 한 번에 모두 할당받는 것이다. 이는 자원의 낭비와 무한 대기 현상이 발생할 수 있다.

4) 자원들에게 순서를 부여한다. 프로세스는 자원의 순서대로 자원 요청이 가능하다. 이렇게 한다면 단방향으로 요청하기에 순환 사이클에 갇힐 일이 없다. 하지만 뒤 순서의 자원은 사용 가능한데 앞 순서의 자원을 할당받지 못하는 상황이라면, 자원의 낭비가 발생할 수 있다.

2. Deadlock avoidance method (교착상태 회피)

시스템의 상태를 계속 감시하다가 deadlock 상태가 될 가능성이 있는 자원 할당 요청은 보류한다. 어떻게 가능하냐 하면, 시스템을 항상 safe state로 유지하는 것이다.

• safe state란, 모든 프로세스가 정상적으로 종료할 수 있는 상태인데 safe sequence가 존재하느냐로 판단할 수 있다. safe sequence는 deadlock 상태가 되지 않을 수 있음을 보장하는 상태이다.

  이 방법은 아래의 가정하에 수행되기에, 비현실적이다.

  • 프로세스의 수 고정
  • 자원의 종류와 수 고정
  • 프로세스가 요구하는 자원 및 최대 수량을 알고 있다
  • 프로세스는 자원 사용 후 반드시 반납한다

또한, 항상 시스템을 감시하고 있어야하기에 높은 Overhead가 발생하고, safe sate 유지를 위해 사용되지 않은 자원이 존재해서 효율적이지 않은 방법이기도 하다.

다만, 이런 과정을 거쳐 현재 현실적인 방법이 나오게 되는 논리적 흐름을 공부하기 위해 정리해보았다.

3. Deadlock detection and deadlock recovery methods (교착상태 탐지 및 복구)

deadlock을 피하지 않고, 주기적으로 deadlock이 발생했는지를 확인하여 복구한다.

1) 확인 및 검출하는 방법으로 Resource Allocation Graph(RAG)를 사용한다.

아래 자원할당 그래프(RAG)에서 edge를 하나씩 지워가는 방법을 통해 알 수 있다. 어떤 edge를 지울 것인가.
Unblocked process된 edge 곧 필요한 자원을 모두 할당받을 수 있는 프로세스의 edge를 제거하는 것이다.

• Completely reduced
  모든 edge가 제거된다면 deadlock에 빠진 프로세스는 없는 것이다.

• Irreducible
  지울 수 없는 edge가 존재한다면, 하나 이상의 프로세스가 deadlock 상태이다.

2) 검출 후 해결하는 방법으로는 2가지 방법이 있다.

• Process termination
  deadlock 상태에 있는 프로세스 중 일부를 종료시킨다. Termination cost model을 기준으로 먼저 종료 시킬 deadlock 상태의 프로세스를 선택한다. 그로 인해 강제 종료된 프로세스는 이후에 재시작된다.

• Resource preemption
  deadlock 상태 해결을 위해 Preemption cost model을 기준으로 선점할 자원을 선택한다. 해당 자원을 가지고 있는 프로세스를 종료시켜 자원을 빼앗는다. 하여 deadlock 상태가 아닌 프로세스가 종료될 수 있다는 단점이 있으며, 해당 프로세스는 이후에 재시작된다.

• Tip. 진행 중 강제 종료된 프로세스를 효율적으로 재시작하기 위해서는 Checkpoint-restart method를 활용한다.
  Checkpoint-restart method는 프로세스 수행 중 특정 지점(checkpoint)마다 context를 저장하여 강제 종료 후, 가장 최근의 checkpoint에서 재시작(rollback)하는 것이다.