[운영체제/Operating System] 교착 상태 (Deadlock)

"KOCW - 반효경 교수님의 운영체제" 를 듣고 정리한 내용입니다.

Deadlocks

교착상태 (Deadlock)

• Deadlock
  • 일련의 프로세스들이 서로가 가진 자원을 기다리며 block된 상태
• Resource
  • 하드웨어, 소프트웨어 등을 포함하는 개념
  • ex) I/O device, CPU cycle, memory space, semaphore 등
  • 프로세스가 자원을 사용하는 절차
    • Request → Allocate → Use → Release
• Example
  1. 시스템에 2개의 tape drive가 있는데 프로세스 A와 B가 각각 하나의 tape drive를 보유한 채 다른 하나를 기다리는 경우
  2. Binary semaphores A and B
     • 프로세스 0이 A를 획득한 상황에서 CPU가 프로세스 1에게 할당되고, 프로세스 1이 B를 획득하여 서로의 A, B를 기다리는 경우

Deadlock 발생의 4가지 조건

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

위의 4가지 조건 중 하나라도 만족하지 않으면 deadlock이 발생하지 않는다.

Deadlock의 처리 방법

• Deadlock이 생기지 않도록 방지하는 방법
  • Deadlock Prevention
  • Deadlock Avoidance
• Deadlock이 생기도록 일단 놔두는 방법
  • Deadlock Detection and Recovery
  • Deadlock Ignorance

Deadlock Prevention

deadlock이 발생하는 네 가지 조건 중 하나를 원천적으로 차단하여 deadlock 발생을 미연에 방지하는 것이다.

• Mutual Exclusion
  • 막을 수 있는 조건 X
• Hold and Wait
  • 방법 1 : 프로세스 시작 시 모든 필요한 자원을 할당받게 하는 것
    • 자원의 비효율성
  • 방법 2 : 자원이 필요한 경우 보유 자원을 모두 놓고 다시 요청
• No Preemption
  • 모든 필요한 자원을 얻을 수 있을 때
  • state를 쉽게 save하고 restore 할 수 있는 자원에서 주로 사용 (CPU, memory)
• Circular Wait
  • 모든 자원 유형에 할당 순서를 정하여 정해진 순서대로만 자원 할당

deadlock을 막을 수는 있지만 자원에 대한 이용률 (utilization)은 떨어지고, throughput 감소 및 starvation 문제가 있다.

Deadlock Avoidance

자원 요청에 대한 부가적인 정보를 이용해서 deadlock 가능성이 없는 경우에만 자원을 할당해준다. 프로세스가 시작될 때 그 프로세스가 최대로 사용할 자원을 미리 알려준다. 따라서 자원을 요청 시 deadlock 가능성이 있으면 자원이 충분해도 할당해주지 않는다.

1. Single instance per resource types
   • Resource Allocation Graph Algorithm 사용

(사진 출처 - KOCW 운영체제 강의)

2. Multiple instances per resource types
   • Banker's Algorithm
     • 각 프로세스의 최대 요청 자원 수를 충족하는 시퀀스가 존재하므로 safe state (절대 deadlock이 생기지 않음)
     • 하지만 자원이 남아 돌아도 최대 요청이 가용 자원 수보다 적으면 주지 않기 때문에 비효율적

(사진 출처 - KOCW 운영체제 강의)

Deadlock Detection and Recovery

deadlock 발생은 그대로 놔두지만 그에 대한 detection routine을 두어 deadlock 발견 시 recovery 한다.

• Deadlock Detection
  1. Single instance per resource types
     • Resource Allocation Graph에서의 cycle이 곧 deadlock을 의미
  2. Multiple instances per resource types
     • Banker's Algorithm과 유사한 방법 활용
• Wait-for graph 알고리즘
  • Single instance per resource types인 경우
  • 자원 할당 그래프에서 프로세스만으로 node 구성
  • Algorithm
    • 사이클이 존재하는지 주기적으로 조사
    • 시간복잡도 : O(n)
• Recovery
  • Process termination
    1. deadlock에 연루된 프로세스들을 모두 죽임
    2. deadlock에 연루된 프로세스들을 하나씩 죽임 (deadlock이 없어질 때까지)
  • Resource preemption
    • deadlock에 연루된 프로세스들로부터 자원을 뺏는 방법
    • victim (희생양 프로세스)를 하나 선정해서 자원을 강제로 뺏음 → safe state로 rollback하여 프로세스 재시작
    • 동일한 프로세스가 계속 victim으로 선정되면 starvation 문제 발생 → rollback 횟수 같이 고려

Deadlock Ignorance

현재 대부분의 운영체제에서 채택한 방법으로 deadlock이 발생하지 않는다 생각하고 아무런 조치도 취하지 않는 것이다. deadlock은 매우 드물게 발생하기 때문에 조치를 취하는 것이 오히려 더 큰 오버헤드일 수 있기 때문이다.

만약 시스템에 deadlock이 발생한 경우 시스템이 느려지거나 프로세스가 멈춘 것을 사용자가 느낄 수 있으므로 일부 프로세스를 직접 죽이는 등의 방법으로 대처한다.

---

참고

• KOCW - 운영체제