[운영체제] Ch7. Deadlock

Deadlock (교착상태)

: 일련의 프로세스들이 서로가 가진 자원을 기다리며 block된 상태
각자 자원을 가지고 있으면서, 상대방의 자원을 더 요청하는.. 더 이상 진행이 되지 않는 상황. (어느 누구도 양보하지 않으면 진행이 안됨.)

Resource (자원)

• 하드웨어, 소프트웨어 등을 포함하는 개념 (ex. I/O device, CPU cycle, memory space, semaphore 등)
• 프로세스가 자원을 사용하는 절차 (4단계)
  • Request(요청), Allocate(획득), Use(사용), Realease(반납)

Deadlock Example

1) 하드웨어 - I/O device의 경우, 시스템에 2개의 tape drive가 있다.

프로세스 p(1)과 p(2) 각각 하나의 tape drive를 보유한 채, 다른 하나를 기다리고 있다.

2) 소프트웨어 - binary semaphore A and B

p(0)이 A를 획득하고 CPU 뺏김, p(1)이 B를 가진 상황에서 A를 가지려하는데, A는 p(0)이 갖고 있음.. CPU가 어느 쪽에 가더라도 진행이 안 됨.

Deadlock 발생의 4가지 조건

: deadlock은 왜 발생하는가?

• Mutual exclusion (상호배제) : 매 순간 하나의 프로세스만이 자원을 사용할 수 있음.
• No preemption (비선점) : 프로세스는 자원을 스스로 내어놓을 뿐, 강제로 빼앗기지 않음.
• Hold and wait (보유대기) : 자원을 가진 프로세스가 다른 자원을 기다릴 때, 보유 자원을 놓지 않고 계속 가지고 있음.
• circular wait (순환대기) : 자원을 기다리는 프로세스간에 사이클이 형성되어야 함. p(0)은 p(1)이 가진 자원을 기다림. p(1)은 p(2)가 가진 자원을 기다림. p(n)은 p(0)이 가진 자원을 기다림.

Resource-Allocation Graph (자원할당 그래프)

: deadlock이 발생했는지 알아보기 위해 사용.

• vertex

: 동그라미는 프로세스, 네모는 자원. 네모 안의 점은 자원의 수.

• edge

: 자원 -> 프로세스 (이 프로세스가 해당 자원을 가지고 있다.)

프로세스 -> 자원 (이 프로세스가 해당 자원을 요청. 아직 획득하진 못함)

• 그래프에 cycle이 없으면 deadlock이 아니다
• 그래프에 cycle이 있으면
  • 자원당 instance(개수)가 하나 밖에 없으면, deadlock
  • 자원당 instance가 여러개면, deadlock일 수도 아닐 수도

두 그림 모두 cycle이 존재,

첫 번째 그림은 R(2) 자원을 p(1),p(2)가 갖고 있으면서, p(3)가 요청하는 상황이기에 deadlock.

두 번째 그림은 p(4)가 R(2)를 반납하거나, p(2)가 R(1)을 반납할 수 있기에 deadlock 아님.

Deadlock의 처리 방법

• 미연에 방지하는 방법

  • 1) Deadlock Prevention : 자원 할당 시, Deadlock의 4가지 필요 조건 중 어느 하나가 만족되지 않도록 하는 것.

  • 2) Deadlock Avoidance : 자원 요청에 대한 부가적인 정보를 이용해서, deadlock의 가능성이 없는 경우에만 자원을 할당.

    시스템 state가 원래 state로 돌아올 수 있는 경우에만 자원 할당.

• deadlock이 생기게 놔둠

  • 3) Deadlock Detection and recovery : deadlock 발생은 허용하되, 그에 대한 detection 루틴을 두어 deadlock 발견 시 recover

  • 4) Deadlock Ignorance (현대 OS 에서 채택: deadlock이 자주 발생하지 않기 때문에, 미연에 방지하는데 드는 overhead가 더 크다.)

    : deadlock을 시스템이 책임지지 않음. UNIX를 포함한 대부분의 OS가 채택.

1) Deadlock Prevention

• Mutual Exclusion : 막을 수 없음. 공유해서는 안되는 자원의 경우, 반드시 성립해야 함.
• Hold and Wait : 프로세스가 자원을 요청할 때는 다른 어떤 자원도 가지고 있지 않아야 한다.
  • 방법 1) 프로세스 시작 시, 모든 필요한 자원을 할당받게 하는 방법. (중간에 추가로 필요한 자원이 없을 것. 비효율적..)
  • 방법 2) 자원이 필요할 경우, 보유 자원을 모두 놓고 다시 요청. (자진 반납)
• No Preemption
  • 프로세스가 어떤 자원을 기다려야 하는 경우, 이미 보유한 자원이 선점됨
  • 모든 필요한 자원을 얻을 수 있을 때, 그 프로세스는 다시 시작됨
  • state를 쉽게 save하고, restore할 수 있는 자원에서 주로 사용(CPU, 메모리)
• Circular Wait
  • 자원들이 꼬리에 꼬리를 물 때 사용 (cycle이 생기지 않도록)
  • 모든 자원 유형에 할당 순서를 정하여, 정해진 순서대로만 자원 할당
  • 예를 들어, 순서가 3인 자원R(i)를 보유 중인 프로세스가 순서가 1인 자원 R(j)를 할당받기 위해서는, 우선 R(i)를 release해야 함!

=> 문제점 : utilization(자원 이용률) 저하, throughput(전체 시스템 성능) 감소, starvation 문제

2) Deadlock Avoidance

: 자원 요청에 대한 부가정보를 이용해서, 자원 할당이 deadlock으로부터 안전한지를 동적으로 조사, 안전한 경우에만 할당. (deadlock이 발생할 수 있는 요청은 거부.)

가장 단순하고 일반적인 모델은 프로세스들이 필요로 하는 각 자원별 최대 사용량을 미리 선언하도록 하는 방법.

• safe state : 시스템 내의 프로세스들에 대한 safe sequence가 존재하는 상태
• safe sequence
  • 프로세스의 sequence <P(1),P(2), ... , P(n)>이 safe하려면 P(i) (1 <= i <= n)의 자원요청이 "가용자원 + 모든 P(j) (j < i)의 보유자원"에 의해 충족되어야 함.
  • 조건을 만족하면 다음 방법으로 모든 프로세스의 수행을 보장
    • P(i)의 자원요청이 즉시 충족될 수 없으면, 모든 P(j) (j < i)가 종료될 때까지 기다린다
    • P(i-1)이 종료되면 P(i)의 자원요청을 만족시켜 수행한다

• 시스템이 safe state에 있으면 => no deadlock
• 시스템이 unsafe state에 있으면 => possibility of deadlock

• deadlock avoidance을 다시 정리하자면,
  • 시스템이 unsafe state에 들어가지 않는 것을 보장
  • 2가지 경우의 avoidance 알고리즘
    • 1) 자원당 instance가 한 개일 때 => resource allocation graph 알고리즘 사용
    • 2) 자원당 instacne가 여러 개일 때 => banker's 알고리즘 사용

• 1) 자원당 instance가 한 개일 때 => resource allocation graph 알고리즘 사용

• claim edge (p(i) -> R(j))

  • 프로세스 p(i)가 자원 R(j)를 미래에 요청할 수 있음 (점선)
  • 프로세스가 해당 자원 요청 시, request edge(실선)로 바뀜
  • R(j)가 release되면, assignment edge는 다시 claim edge로 바뀜

• requese edge의 assignment edge 변경 시 (점선 포함) cycle이 생기지 않는 경우에만 요청 자원을 할당.

• cycle 생성 여부 조사시, 프로세스의 수가 n일 때, O(n^2) 시간이 걸림.

  
  

• 2) 자원당 instace가 여러 개일 때 => Banker's 알고리즘 사용

  example of Banker's Algorithm

  : Need(각 프로세스의 자원 요청)를 받아들일지 아닐지를 결정!! 항상 최악의 상황을 가정하며, 굉장히 보수적임. 프로세스들이 본인의 최대 요청을 할 것이라 가정하고, 가용 자원(Available)에서 줄 수 있는지를 본다. 가용자원으로 충족되면 처리되고, 추가 요청이 가용자원으로 충족되지 않을 시에는 처리되지 않음.

• 각 프로세스는 최대로 사용하는 자원의 수를 미리 알 수 있음(Max), 하지만 어느 시점에 필요할지는 알 수 없다.

• 평생에 요청할 수 있는 최대 자원의 수는 Need (Max - Allocation)

• sequence <P(1)-P(3)-P(4)-P(2)-P(0)>가 존재하므로 시스템은 safe state.

• deadlock이 생기지 않지만, 자원이 있는데도 주지 않으므로 비효율적.

  
  

3) Deadlock Detection and Recovery

• deadlock detection
  • resource type당 single instance인 경우
    • 자원할당 그래프에서의 cycle이 곧 deadlock을 의미
  • resource type당 multiple instance인 경우
    • banker's 알고리즘과 유사한 방법 활용

• wait-for graph 알고리즘

• resource type당 single instance인 경우

• wait-for graph

  • 자원할당 그래프의 변형
  • 프로세스만으로 node 구성
  • P(j)가 가지고 있는 자원을 P(k)가 기다리는 경우 P(k) -> P(j)

• 알고리즘

  • wait-for graph에 사이클이 존재하는지를 주기적으로 조사
  • cycle을 찾는데 걸리는 시간 : O(n^2)

• resource type당 multiple instance인 경우

  : 보수적이지 않고, 낙관적으로 생각함 (자원을 반납할거라 생각)

=> No deadlock : sequence <P(0)-P(2)-P(3)-P(1)-P(4)> will work!

먼저 가용자원(Available)으로 커버할 수 있는지 본다.

다음으로 요청자원이 없는 프로세스를 보고, 내어놓을 수 있는 자원을 살펴본다.

그 자원을 가용자원으로 합쳐놓고, 요청자원을 만족하는 프로세스를 진행시킨다.

문제 없이 끝까지 갈 수 있다면, No deadlock!!

만약, deadlock이 발견되면 recovery를 해야한다.

• Recovery
  • Process termination : deadlock에 연루된 프로세스들을 사살
    • 1) 연루된 모든 프로세스들을 사살
    • 2) 하나씩 죽이면서 deadlock이 해결되는지 살펴봄 (deadlock이 없어질 때까지 반복)
  • Resource Preemption : deadlock에 연루된 프로세스들로부터 자원을 뺏음
    • 비용을 최소화할 victim 선정 (자원을 빼앗을 희생양 선정)
    • safe state로 rollback하여 프로세스를 재시작
    • starvation 문제 (p1한테서 a자원을 뺏었는데 다른 p가 a자원을 요청하기도 전에 p1이 a자원을 또 요청..)
      • 동일한 프로세스가 계속해서 victim으로 선정되는 경우
      • cost factor에 rollback 횟수도 같이 고려 (꼭 비용만 최소화하는게 아니라~)

4) Deadlock Ignorance

: deadlock이 일어나지 않는다고 생각하고, 아무런 조치도 취하지 않음

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