교착 상태

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

• 자원: 하드웨어, 소프트웨어 등을 포함하는 개념
• (ex) I/O device, CPU cycle, memory space, semaphore
  • [하드웨어 예시] 시스템에 2개의 tape drive가 있다. 프로세스 P1과 프로세스 P2는 하나의 tape drive를 나머지 tape drive에 복사하는 작업을 해야 한다. 그런데 프로세스 P1과 P2 각각이 하나의 tape drive를 보유한 채 다른 하나를 기다리고 있다.
  • [소프트웨어 예시] Binary Semaphores A & B

    P0-------------------P1
    P(A);----------------P(B);
    P(B);----------------P(A);
    프로세스0는 자원 A를 얻은 상태에서 CPU를 빼앗겼는데, 프로세스1은 자원 B를 얻음. 서로가 가진 자원을 얻지 못함

  • 프로세스가 자원을 사용하는 절차: Request, Allocate, Use, Release

교착 상태 발생의 4가지 조건

• Mutual exclusion (상호 배제)
  매 순간 하나의 프로세스만이 자원을 사용할 수 있음. 일단 자원을 얻으면 공유할 수 없고 독점적으로 사용.
• No preemption (비선점 - 빼앗기느냐에 focus)
  프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않음.
• Hold and wait (보유 및 대기 - 내놓느냐에 focus)
  자원을 가진 프로세스가 다른 자원을 기다릴 때 보유자원을 놓지 않고 계속 가지고 있음.
• Circular wait (순환 대기)
  자원을 기다리는 프로세스 간에 사이클이 형성되어야 함.
  프로세스 P0, P1, ..., Pn이 있을 때
  • P0는 P1이 가진 자원을 기다림
  • P1는 P2이 가진 자원을 기다림
  • Pn-1는 Pn이 가진 자원을 기다림
  • Pn는 P0이 가진 자원을 기다림

자원 할당 그래프

원: 프로세스
사각형: 자원
사각형 내부의 점: 자원의 인스턴스 (개수는 인스턴스의 개수)
request edge: 프로세스에서 자원 쪽으로 나가는 화살표
assignment edge: 자원에서 프로세스 쪽으로 나가는 화살표

• 그래프에 사이클이 없으면 deadlock이 아니다.
• 그래프에 사이클이 있으면
  • 사이클에 연루된 자원의 인스턴스가 각각 1개씩 밖에 없으면 deadlock (사이클이 곧 deadlock임을 의미)
  • 2개 이상이면 deadlock 발생 가능성 있음.
  • ex) 사이클에 연루된 자원 하나에 인스턴스가 2개 있고, 해당 인스턴스가 각각 이미 프로세스 2개에 점유되어 있고, 각각의 인스턴스는 각각의 사이클에 연루된 상태. 이 때 사이클에 연루된 제 3의 프로세스가 해당 자원을 요청하는 상태 -> deadlock
  • ex) 사이클에 연루된 자원 하나에 인스턴스가 2개 있고, 인스턴스 중 하나는 사이클에 연루되어 있고, 다른 하나는 사이클에 연루되어 있지 않은 상황 -> 사이클에 연루되어 있지 않은 인스턴스가 특정 프로세스에 의해 사용되다가 반납된다면 사이클이 있더라도 deadlock이 생기지 않음.

Deadlock의 처리 방법

(1) Deadlock이 생기지 않도록 미연에 방지하는 방법

• Deadlock Prevention
  • 자원 할당 시 Deadlock의 4가지 필요 조건 중 어느 하나가 만족되지 않도록 하는 것
• Deadlock Avoidance
  • 자원 요청에 대한 부가적인 정보를 이용해서 deadlock의 가능성이 없는 경우에만 자원을 할당

(2) Deadlock이 생기도록 일단 놔두는 방법 (Deadlock은 빈번히 발생하는 이벤트가 아니므로 미연에 방지하는 것의 overhead는 현대적인 시스템에서는 비효율적인 것으로 간주됨)

• Deadlock Detection and recovery
  • Deadlock 발생은 허용하되 그에 대한 detection 루틴을 두어 deadlock 발견 시 recover
• Deadlock ignorance
  • Deadlock을 시스템이 책임지지 않음
  • UNIX를 포함한 대부분의 OS가 채택

Deadlock prevention

4가지 조건 중 어느 하나를 원천적으로 차단하는 방법

Mutual Exclusion

• 사실상 무력화할 수 없음. (공유해서는 안되는 자원의 경우 반드시 성립해야 함.)

No Preemption

• preemtion: 자원을 빼앗아올 수 있게 하면 deadlock이 안 생긴다. state을 쉽게 save하고 restore할 수 있는 자원에서 주로 사용. (ex. 프로세스0과 프로세스1 간 자원X와 자원Y의 deadlock이 발생했을 때, 시스템이 프로세스1로부터 자원X를 선점하여 프로세스0에 할당하면 자원X, Y 둘 다 프로세스0이 사용 후 반납하면 된다. CPU는 프로세스1의 state을 save하고 restore할 수 있기 때문이다.).
• 다만 state을 save, restore하기가 어려우면 선점을 허용하는 방식은 사용하기가 어려움.
• 그리고 프로세스의 우선순위에 의한 preemption을 허용하면 우선순위가 낮은 프로세스의 starvation이 발생할 가능성이 있다.

Hold and Wait
프로세스가 자원을 요청할 때 다른 어떤 자원도 가지고 있지 않아야 한다. 즉, All or nothing 방식을 사용하면 된다.

• 방법1: 프로세스 시작 시 평생에 필요로 할 필요한 자원을 할당받게 하는 방법 -> 프로세스가 종료될 때까지 필요없는 자원도 전부 다 보유 하고 시작하므로 비효율성이 생김.
• 방법2: 자원이 필요할 경우 보유 자원을 모두 놓고 다시 요청

Circular wait

• 모든 자원 유형에 할당 순서를 정하여 정해진 순서대로만 자원 할당
• ex) 순서가 3인 자원을 보유 중인 프로세스가 순서가 1인 자원을 할당받기 위해서는 우선 자원을 release해야 한다. 이 때 순서가 1인 자원을 보유 중인 프로세스는 자원 3을 이용하고, 자원 1과 자원 3을 release하면 되므로 deadlock이 발생하지 않음.

다만, Deadlock prevention의 경우 자원 이용률이 낮아지고, 성능이 감소하고 starvation이 발생할 가능성이 있어서 상당히 비효율적임.

Deadlock Avoidance

• 자원 요청에 대한 부가 정보를 이용해서 자원 할당이 deadlock으로부터 안전한지를 동적으로 조사해서 안전한 경우에만 할당.

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

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

  • 시스템이 safe state에 있으면 no deadlock
  • 시스템이 unsafe state에 있으면 possibility of deadlock. "혹시 이 자원을 할당해주면 deadlock이 생길 가능성이 있을까?" -> 할당 X (보수적 접근)

자원 당 instance가 하나만 있으면 자원 할당 그래프 알고리즘 사용

• claim edge: 프로세스가 자원을 미래에 요청할 수 있음을 뜻함
• request edge: 프로세스가 해당 자원 요청 시 실선으로 바뀜
• assignment edge: 자원이 할당되면 화살표의 방향이 바뀜.
• 자원이 release되면 assignment edge는 해제되고 claim edge로 바뀐다.
• request edge의 assignment edge로의 변경 시 claim edge를 포함하여 cycle이 생기지 않는 경우에만 자원을 할당한다. 초기 그래프가 아래와 같다고 가정해보자.
  
  이 때 P1에 R2를 할당하면 사이클이 생기지 않지만,
  
  P2에 R2를 할당하면 점선을 포함하여 사이클이 생긴다. 즉, 현재 deadlock은 아니지만 (점선이므로 지금 당장 요구한 건 아님) unsafe한 상태이므로 자원을 할당하지 않는다.
  

자원 당 instance가 여러개면 은행원 알고리즘(banker's algorithm) 사용.

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

safe sequence: 프로세스의 sequence<P1, P2, ..., Pn>이 safe하려면 Pi(1 <= i<= n)의 자원 요청이 가용자원 + 모든 Pj (j < i)의 보유자원에 의해 충족이 되어야 함. 조건을 만족하면 다음 방법으로 모든 프로세스의 수행을 보장

• Pi의 자원 요청이 즉시 충족될 수 없으면 모든 Pj(j < i)가 끝날 때까지 기다린다.
• Pi-1이 종료되면 Pi의 자원 요청을 만족시켜 수행한다.

예시)
5개의 프로세스가 있음. (P0 ~ P4)
3가지 자원 종류가 있음. A(10), B(5), C(7)이고 괄호 안은 인스턴스 개수.

Snapshot at T0

프로세스1에 Need 만큼 할당하더라도, 이미 할당된 자원까지 모두 반환하면 가용자원에 A가 2만큼 쌓임. -> 이 때 가용자원이 5, 3, 2가 되고 프로세스 3의 Need를 수용할 수 있는 상태가 됨. -> ...

-> 각 프로세스의 최대 요청 자원을 충족할 수 있는 sequence<P1, P3, P4, P2, P0>가 존재하므로 시스템은 safe state(dead lock이 생기지 않음)임.

⭐️ P0는 available <= need인 프로세스이긴하지만, P0가 A 단 1개를 요청하는 경우에는 여전히 모든 프로세스에 자원을 할당할 수 있는 sequence가 존재하므로 safe state이 유지됨을 간주하고 할당 가능.
반면, P0가 B 2개를 요청하면 모든 프로세스에 자원을 할당할 수 있는 sequence가 존재하지 않으므로 unsafe state에 들어선다고 간주하고 자원 할당 거부됨.
(이 부분은 반효경 교수님과 공룡책의 설명이 다른데, 일단 공룡책의 설명대로 알고 있기로 결정하였다. 현강 수강생이었으면 질문을 드렸을 것 같다.)

프로세스 0가 Need만큼 요구할 때 가용자원만큼 할당하더라도 deadlock이 반드시 발생하는 것은 아니지만, 은행원 알고리즘은 최악을 가정하는 모델이므로 unsafe일 때 무조건 자원 할당을 거부하므로 비효율적이라고 할 수 있음.

Deadlock Detection and recovery

자원 당 인스턴스가 하나인 경우: 자원할당 그래프에서의 cycle이 곧 deadlock임을 의미.

Wait-for 알고리즘

• 자원 당 인스턴스가 하나인 경우 사용
• 자원 없이 프로세스만으로 node 구성
• Pi가 가지고 있는 자원을 Pk가 기다리는 경우 Pk -> Pi
• 자원의 최대 사용량을 미리 알 필요가 없다. (그래프에 점선이 없다.)
• 알고리즘
  • wait-for 그래프에 사이클이 존재하는지를 주기적으로 조사
  • O(N^2) (프로세스가 N개일 때 하나의 프로세스에서 나머지 node로 간선이 모두 나간다고 가정하면 하나의 프로세스 당 최대 N - 1개의 간선을 가짐.)

자원 당 인스턴스가 여러개인 경우: 은행원 알고리즘과 유사한 방법 활용 (but, 낙관적으로 적용)
예시)
5개의 프로세스가 있음. (P0 ~ P4)
3가지 자원 종류가 있음. A(7), B(2), C(6)이고 괄호 안은 인스턴스 개수.

Request는 Need와 다르다. 최대 요청 가능량이 아니라 현재 실제로 요청한 자원량을 나타낸다.

deadlock이 발생하지 않는다고 간주(낙관적). P0, P2가 모든 자원 사용 후 반납하면, P3, P1, P4의 요청한 자원량 할당 가능.

그런데 만약 P2가 C1개를 요청하는 상황이라면?

P0가 모든 자원 사용 후 반납하더라도 나머지 프로세스들의 요청을 충족할 수 없으므로 deadlock 발생. -> recovery 필요

• recovery
  • process termination
    (1) 모든 deadlock 걸린 프로세스 종료
    (2) deadlock 사이클이 제거될 때까지 한 번에 하나의 프로세스 종료
  • process preemption
    • 비용을 최소화할 victim 선정
    • deadlock에 연루된 victim으로부터 자원을 빼앗아서 deadlock을 없앰
    • safe state로 rollback하여 process 재시작

Deadlock ignorance

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