OS_09_Deadlock

1. System Model

1) The Deadlock Problem

• deadlock이란 서로 다른 프로세스들이 각각의 자원을 가지고 있고, 다른 프로세스가 가지고 있는 자원을 기다리며 block 상태인 것이다.
• Example
  • system has 2 tape drives
  • P1 and P2는 각각 tape drive를 소유 하고 있으며 각자의 것을 필요로한다.
• Example
  • Semaphores A and B, initialized to 1

wait(A);
wait(B);

wait(B);
wait(A);

2) Resource-Allocation Graph

• vertices V의 집합과 edges E의 집합
• V는 두개의 형식으로 나누어 진다.
  • P = {P1, P2, …, Pn}, 시스템에 있는 모든 프로세스들의 집합이다.
  • R = {R1, R2, …, Rm}, 시스템에 있는 모든 resouce types들의 집합이다.
• Request edge
  • Directed edge P1 → Rj
• Assignment edge
  • Directed edge Rj → Pi
• Process

• Resource Type with 4 instances

• Pi requests instance of Rj

• Pi is holding an instacne of Rj (즉 critical section에 이미 진입.)

a) Example of Resource-Allocation Graph

2. Deadlock Characterization

1) Necessary Conditions for Deadlock

• Deadlock이 발생하면 4가지 조건을 모두 충족한다. (필요조건)
  • Mutual exclusion : 한 번에 한 개의 process만이 resource를 사용할 수 있다.
  • Hold and wait : 최소한 하나의 resource를 가지고 있는 process가 다른 process가 가지고 있는 추가 자원을 얻기 위해 기다리고 있다.
  • No preemption : 자원은 preempted될 수 없다. 즉 resource는 보유하고 있는 process가 자발적으로 작업을 완료하고 나서 해제할 수 있다. 다른 말로 다른 프로세스가 강제로 뺏을 수 없음을 뜻한다.
  • Circular wait : {P0, P1, P2,… Pn}으로 이루어진 waiting process집합이 존재하는데, P0은 P1이 보유한 자원을 기다리고 있고, P1은 P2가 보유한 자원을 기다리고 있는 상황이고, … , P(n-1)은 Pn이 보유한 자원, Pn은 P0이 보유한 자원을 기다리고 있다.
    • 즉, 이렇게 서로가 서로를 기다리는 circular wait상태가 이루어져야 한다.

a) Resource Allocation Graph With A Deadlock

가장 우선적으로 보아야 할 것은 cycle(circular wait)가 존재하는가

b) Resource Allocation Graph With a Cycle, But No Deadlock

cycle은 존재함

• cycle은 존재하지만, 언젠가 P2가 R1을 모두 사용하고 반납 할 것이다. 이때, P1에게 제공이 가능 하기에 cycle이 없어지므로 deadlock이 아님.

2) Basic Facts

• 만약 graph가 cycle이 없다면 → no deadlock
• 만약 graph가 cycle을 가지고 있다면
  • 만약 resource type당 하나의 instance만 가지고 있다면 → deadlock
  • 만약 resource type당 여러개의 instance를 가지고 있다면 → deadlock의 가능성이 있다.

3. Methods for Handling Deadlocks

1) Methods for Handling Deadlocks

• system이 deadlock에 들어가지 않도록 사전에 방지하는 방법이다. → 가능성을 원천 봉쇄
  • Deadlock prevention
• System이 deadlock에 들어가도록 허용하지만 recover한다.
  • Deadlock avoidance → 시스템이 deadlock이 발생하지 않도록 운영
  • Deadlock detection and recovery → deadlock 발생 하면 recovery함.
• Deadlock을 무시한다.
  • 대부분의 운영 체제에서는 해당 방법을 사용하며, deadlock을 처리하는 기능을 포함하지 않는다.
  • deadlock이 시스템에서 발생하지 않는다고 가정하고 무시를 해버림.
  • 위에 3가지의 기법들은 성능 저하를 야기하기에 선택하지 않음.

2) Deadlock Prevention

• 4가지의 deadlock의 충분 조건 중 하나라도 성립하지 않으면 deadlock이 불가능하다.
• Mutual Exclusion → sharable resource에서는 필요하지 않지만, nonsharable resource에서는 반드시 지켜야한다.
  • Nonsharable resource : printer, … → 한 번에 한번의 프로세스가 접근 할 수 있다.
  • Sharable resource : read-only files → 여러개의 프로세스가 동시에 접근된다.
  • 일반적으로 mutual exclusion condition을 무시하여 deadlock을 prevent할 수 없다.
    • 몇몇의 자원은 본질적으로 nonsharable하기 때문이다.
• Hold and Wait → process가 resource를 요청 할 때, 다른 resource를 가지지않도록 보장하여야한다.
  • 프로세스가 실행을 하기 전에 모든 자원을 요청하고 할당 받거나, 프로세스가 자원을 요청할 수 있는 시점을 보유하지 않을 때로 제한한다.
  • 하지만, Low resource utilization → starvation possible
• No Preemption - Resource의 고유적인 성질이다.
  • resource를 가지고 있는 process가 추가로 자원을 요청 했지만 즉시 할당받을 수 없는 경우, 현재 가지고 있는 모든 자원들을 해제한다.
  • Preempted resource들은 해당 process가 기다리고 있는 자원에 추가한다.
  • process는 새로운 것을 받는 것 뿐아니라 이전에 가지고 있던 것들도 다시 할당 받아야 restart한다.
• Circular Wait
  • 모든 resource type에 대해서 순서를 부과하고, 각 프로세스가 열거된 순서대로 자원을 요청한다.
  • 프로그램 개발이 가능하지만 현실적으로는 불가능하다.
• 즉, 현실적으로 programming으로 4가지 deadlock 성질 중 한개를 제거하는 것은 불가능하다.

3) Deadlock Avoidance

• system이 미리 필요한 추가적인 정보를 가져야한다.
  • Resources currently available
  • Resources currently allocated each process
  • Future requests and releases of each process
• 가장 간단한 모델은 process가 각 유형의 resource에 대해서 필요한 최대의 수를 선언하는 것이다.
  • resource의 최대 수는 각 프로세스의 requested가 된다.
• deadlock-avoidance algorithm은 자원 할당 상태를 동적으로 검사하여 circular-wait condition이 발생하지 않음을 보장한다.

4) Safe State

• A state is safe
  • system이 deadlock을 피하면서 resource를 process를 할당 할 수 있는 경우 safe라고 한다.
  • safe sequence of process가 존재하는 경우
• A sequence of processes <P1, P2, …, Pn> is safe
  • 각 프로세스 Pi에 대해서 현재 사용 가능한 자원과 Pj(j < i)가 소유한 자원으로 Pi가 요청한 자원을 충족시킬 수 있어야한다.
  • Pi가 필요로 하는 자원이 즉시 사용 가능하지 않는다면, Pi는 Pj가 모두 완료될 때까지 대기할 수 있어야한다.
  • Pj가 완료된 후 Pi는 필요한 자원을 얻고 실행하며, 할당된 자원하고 종료할 수 있어야한다.
  • Pi가 종료되면, P(i+1)은 필요한 자원을 얻을 수 있고 이와 같은 과정을 반복한다.

a) Example

• 12개의 magnetic tape drivers(resource)와 3개의 process

	Maximum Needs	Current Assignment (t0)
P0	10	5
P1	4	2
P2	9	2

• safe sequence <P1, P0 ,P2>가 존재한다.
  • 3개의 free tape driver가 존재한다.
  • P1은 즉시 필요한 tape driver를 할당 받을 수 있다. (2+2)
    • 이후 P1은 4개의 tape driver를 반납한다.(5 free tape drivers)
  • P0은 모든 resource를 할당 받는다. (5+5)
    • 이후에 P0는 10개의 tape driver를 반납한다. (10 free tape drivers)
  • P2은 필요한 resource를 할당 받는다. (2+7)

5) Basic Facts

• 만약 system이 safe state에 있다면 → no deadlock
• 만약 system이 unsafe state에 있다면 → deadlock의 가능성이 있음.

즉 ststem은 항상 safe state에서만 운영한다.

6) Deadlock Detection and Recovery

• 만약 system이 deadlock-prevention이나 deadlock-avoidance alogorithm을 사용하지 않는다면?
• 시스템은 반드시 이와 같은 기능을 제공해야한다.
  • 시스템의 상태를 검사하며 deadlock이 발생한 경우를 판단할 수 있는 detection algorithm을 제공해야한다.
  • Recovery scheme

7) Single Instance of Each Resource Type

• Wait-for graph
  • node들이 process이다.
  • Pi → Pj if Pi is waiting for Pj
  • resource allocation graph에서 이 graph를 추출 할 수 있음
    • resource type노드를 제거하고 인접 노드를 제거함으로써
• graph에서 cycle이 존재하는지 확인하는 algorithm을 사용할 수 있음.

a) wait-for graph

b) Several Instances of a Resource Type

• Available : m개의 원소로 구성된 벡터로, 각 reource type에서 이용 가능한 자원의 수를 나타낸다.
• Allocation : n x m 행렬로, 각 프로세스가 현재 각 type의 resource를 얼마나 할당 받았는지를 나타낸다.
• Request : n x m 행렬로, 각 프로세스의 현재 요청 상태를 나타낸다.
  • 만약 Request[ij] = k, reource type Rj에 대해서 Pi process가 k 개의 자원을 더 요청하고 있는 것이다.

Basic Idea

check if the system has circular wait

check if there is a safe sequence (safe한 상태인가?)

c) Detection Algorithm

1. Work와 Finish가 각각 길이 m,n인 벡터라고 하고 각자의 초기화는

   1. Work = Available
   2. i = 1,2,…,n에 대해서 Allocationi ≠ 0이라면 Finish[i] = false, Allocationi == 0 이라면 Finish[i] = true로 설정한다.

2. 두 조건을 만족하는 index i를 찾는다.

   1. Finish[i] == false
   2. Requesti ≤ Work
   3. 만약 이런 i가 없다면, 4번 step으로 간다.

3. Work = Work + Allocationi

   Finish[i] = true

   go to step 2

4. If Finish[i] == false, for some i, 1 ≤ i ≤ n, 그러면 system은 deadlock 상태이다.

   1. Finish[i] == false라면 Pi가 deadlock 상태인 것이다.

d) Dectection-Algorithm Usage

• 해당 알고리즘을 얼마나 자주, 언제 사용할 것인지 대해서:
  • Deadlock이 얼마나 자주 발생할 가능성이 있는가?
  • 얼마나 많은 process가 deadlock이 발생하면 영향을 받는가?
• algorithm을 언제 수행해야하는가?
  • reource 할당 요청이 즉시 승인 될 수 없을 때마다
    • 즉, critical section request마다, 하지만 overhead가 너무 크다.
    • semaphore나 mutex만으로도 충분히 큰데, 더 무거운 detection algorithm을 돌리는 것은 overhead가 크다.
  • 일정한 주기로 실행
    • 1시간에 한번씩(주기적으로) → 하지만 1시간동안 deadlock을 방치하는 것이므로 좋지 않다, 그렇다고 시간을 작게 가져간다면 overhead가 크다.
      
    • CPU utilization이 40percent 밑으로 떨어질 때 → CPU utilization과 deadlock은 상관관계는 있지만 인과관계가 없기에 좋은 방법이 아니다.
      

4. Recovery from Deadlock

1) Recovery from Deadlock: Process Termination

• 모든 deadlock 상태인 process를 중단시킨다.
• deadlock cycle이 없어질 때 까지 하나의 process를 계속해서 중단시킨다.
  • 그렇다면 어떤 process를 선택해야 하는가?
    • 프로세스의 우선순위
    • 얼마나 프로세스가 연산을 해왔고, 완료까지 얼마나 남았는가?
    • 프로세스가 사용한 resoruces
    • 완료하기 위해 process가 필요한 resources
    • 중지해야 할 프로세스의 수
    • 프로세스가 interative 하게 작업하는지 batch하게 작업하는지에 따라
• 하지만 이런 방법은 프로그래머의 의도를 무시하기에 좋지 않다.

2) Recovery from Deadlock: Resource Preemption

• Selecting a victim - 최소 비용
• Rollback - safe state로 돌아가고, process를 그 상태에서 다시 시작한다.
• Starvation - 동일한 프로세스가 계속해서 victim으로 선택할 경우 생길 수 있다. rollback 을 포함시킨다.

5. 결론

• 3가지의 방법의 모든 비용이 높기에 OS에서는 무시하는 방향으로 설계한다.
• 즉 deadlock은 프로그래머의 역량이다.