🔒 Deadlock

일련의 프로세스들이 서로가 가진 자원(Resource)를 기다리며 block된 상태

Resource(자원)

• 하드웨어, 소프트웨어 등을 포함하는 개념
  ex) I/O device, CPU cycle, memory space, semaphore
• 프로세스가 자원을 사용하는 절차
  Request, Allocate, Use, Release

Deadlock 발생 조건 4가지

• Mutual exclusion (상호 배제)
  매 순간 하나의 프로세스만이 자원을 사용할 수 있다. 사용 중인 자원을 다른 프로세스가 사용하기 위해서는 해당 자원이 해제될 때까지 기다려야 한다.
• No preemption (비선점)
  이미 할당된 자원을 강제로 빼앗을 수 없다.
• Hold and wait (점유 대기)
  자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있다.
• Circular wait (순환 대기)
  자원을 기다리는 프로세스간에 사이클이 형성되어야 한다. 대기 프로세스의 집합이 순환 형태로 자을 대기하고 있어야 한다.
  

Deadlock의 처리 방법

1. Deadlock Prevention
   자원 할당 시 Deadlock의 4가지 필요 조건 중 어느 하나가 만족되지 않도록 하는 것이다. (active하게 막는다.)
2. Deadlock Avoidance
   자원 요청에 대한 부가적인 정보를 이용해서 deadlock의 가능성이 없는 경우에만 자원을 할당한다.
   시스템 state가 원래 state로 돌아올 수 있는 경우에만 자원을 할당한다.
3. Deadlock Detection and recovery
   Deadlock 발생은 허용하되 그에 대한 detection 루틴을 두어 deadlock 발견 시 recover
4. Deadlock Ignorance
   이것은 OS의 처리 방법
   Deadlock을 시스템이 책임지지 않는 방법이다. UNIX를 포함한 대부분의 OS가 채택했다.

하나씩 살펴보도록 하자.

Deadlock Prevention

Deadlock 발생 조건 4가지 중 하나라도 발생하지 않게 하는 방법인데, 각각의 조건을 부정해서 Deadlock 발생 가능성을 차단한다.

• Mutual Exclusion 부정
  한 번에 여러 프로세스가 공유 자원을 사용할 수 있게 한다.
  (BUT, 추후 동기화 관련 문제 발생 가능성 O)
• No Preemption 부정
  • 이미 다른 프로세스에서 할당된 자원이 선점권이 없다고 가정할 때, 높은 우선순위의 프로세스가 해당 자원을 선점할 수 있도록 한다.
  • 모든 필요한 자원을 얻을 수 있을 때, 그 프로세스는 다시 시작된다.
  • State를 쉽게 save하고 restore 할 수 있는 자원에서 주로 사용한다. (CPU, memory)
• Hold and Wait 부정
  • 프로세스 실행에 필요한 모든 자원을 한꺼번에 요구하고 허용할 때까지 작업을 보류해서, 나중에 또 다른 자원을 점유하기 위한 대기 조건을 성립하지 않도록 한다.
  • 방법 1) 프로세스 시작 시 모든 필요한 자원을 할당받게 하는 방법
  • 방법 2) 자원이 필요할 경우 보유 자원을 모두 놓고 다시 요청
• Circuit Wait 부정
  • 자원을 순환 형태로 대기하지 않도록 일정한 한쪽 방향으로만 자원을 요구할 수 있도록 한다.
  • 모든 자원 유형에 할당 순서를 정하여 정해진 순서대로만 자원을 할당한다.
  • ex) 순서가 3인 자원 Ri를 보유 중인 프로세스가 순서가 1인 자원 Rj을 할당받기 위해서는 우선 Ri를 release 해야 한다.

이러한 조건을 방지해서 Deadlock을 예방하는 방법
👉 Utilization 저하, throughout 감소, starvation 문제가 발생한다.

2번째로 살펴볼 Avoidance 방법은 조금 덜 제한적인 방법으로 위의 단점을 일부 해결할 수 있다.

Deadlock Avoidance

핵심 키워드 Safe state, Safe sequence

• 자원 요청에 대한 부가적인 정보를 이용해서 deadlock으로부터 안전(safe)한지를 동적으로 조사해서 안전한 경우(deadlock의 가능성 없는 경우)에만 할당한다.
• 가장 단순하고 일반적인 모델은 프로세스들이 필요로 하는 각 자원별 최대 사용량을 미리 선언하도록 하는 방법이다.
• 시스템 state가 원래 state로 돌아올 수 있는 경우에만 자원을 할당한다.

Safe state

시스템 내의 프로세스들에 대한 safe sequence가 존재하는 상태

Safe sequence

• 프로세스의 sequence <P1, P2, ... , Pn> 이 safe하려면 Pi (1 <= i <= n)의 자원 요청이 가용 자원 + 모든 Pj(j < i)의 보유 자원에 의해 충족되어야 한다.
• 조건을 만족하면 다음 방법으로 모든 프로세스의 수행을 보장한다.
  • Pi의 자원 요청이 즉시 충족될 수 없으면 모든 Pj(j < i)가 종료될 때까지 기다린다.
  • P(i-1)이 종료되면 Pi의 자원 요청을 만족시켜 수행한다.

시스템이 safe state에 있다 👉 no deadlock
시스템이 unsafe state에 있다 👉 possibility of deadlock
: 무조건 deadlock 상태가 아니다.

Deadlock Avoidance는 시스템이 unsafe state에 들어가지 않는 것을 보장한다.

2가지 경우의 Avoidance 알고리즘

1. Single instance per resource types
   Resource Allocation Graph algorithm 사용
2. Multiple instances per resource types
   Banker's Algorithm 사용

1️⃣ Resource Allocation Graph algorithm

Resource당 Single Instance 인 경우

• Claim edge Pi -> Ri
  • 프로세스 Pi가 자원 Rj를 미래에 요청할 수 있음을 뜻한다. (점선으로 표시)
  • 프로세스가 해당 자원 요청 시 request edge로 바뀐다.
  • Rj가 release 되면 assignment edge는 다시 claim edge로 바뀐다.
• request edge의 assignment edge 변경 시 (점선을 포함하여) cycle이 생기지 않는 경우에만 요청 자원을 할당한다.
• Cycle 생성 여부 조사 시 프로세스의 수가 n일 때 O(n^2) 시간이 걸린다.

2️⃣ Banker's Algorithm

Resource당 Multi instances 인 경우

가정

• 모든 프로세스는 자원의 최대 사용량을 미리 명시
• 프로세스가 요청 자원을 모두 할당받은 경우 유한 시간 안에 이들 자원을 다시 반납한다.

방법

• 기본 개념 : 자원 요청 시 safe 상태를 유지할 경우에만 할당한다.
• 총 요청 자원의 수가 가용 자원의 수보다 적은 프로세스를 선택한다.
  (그런 프로세스가 없으면 unsafe 상태)
• 그런 프로세스가 있다면 그 프로세스에게 자원을 할당한다.
• 할당받은 프로세스가 종료되면 모든 자원을 반납한다.
• 모든 프로세스가 종료될 때까지 이 과정을 반복한다.

Deadlock Detection and Recovery

Deadlock Detection

• Resource type당 single instance인 경우
  자원할당 그래프에서의 cycle이 곧 deadlock을 의미한다.
• Resource type당 multiple instance인 경우
  Banker's algorithm과 유사한 방법 활용

Wait-for graph 알고리즘

• Resource type 당 single instance인 경우
• Wait-for graph
  • 자원할당 그래프의 변형
  • 프로세스만으로 node 구성 (Resource를 제외한 프로세스간의 의존성을 본다.)
  • Pj가 가지고 있는 자원을 Pk가 기다리는 경우 Pk -> Pj
• Algorithm
  • Wait-for graph에 사이클이 존재하는지를 주기적으로 조사한다.
  • O(n^2)

Deadlock Recovery

Process termination

• Abort all deadlocked processes (모든 프로세스를 죽인다.)
• Abort one process at a time until the deadlock cycle is eliminated (한 번에 하나의 프로세스만 죽인다.)

Resource Preemption

• 비용을 최소화할 victim의 선정
• safe state로 rollback하여 process를 restart
• Starvation 문제
  • 동일한 프로세스가 계속해서 victim으로 선정되는 경우
  • cost factor에 rollback 횟수도 같이 고려

Deadlock Ignorance

Deadlock이 일어나지 않는다고 생각하고 아무런 조취도 취하지 않는 방법이다.

• Deadlock이 매우 드물게 발생하므로 deadlock에 대한 조치 자체가 더 큰 overhead일 수 있다.
• 만약 시스템에 deadlock이 발생한 경우, 시스템이 비정상적으로 작동하는 것을 사람이 느낀 후 직접 프로세스를 죽이는 방법으로 대처
• Unix, Windows 등 대부분의 범용 OS가 채택했다.