[운영체제] 08. Deadlocks

What is Deadlock?

• 세마포어 사용 예제
  • 두 개의 세마포어 S와 Q가 있고, 초기값은 1입니다. 

 

Deadlock : 한 집합의 차단된 프로세스들이 각자 하나의 자원을 잡고 있으며, 동시에 다른 프로세스가 가지고 있는 자원을 얻기 위해 기다리고 있는 상태.

 

---

Deadlock Characterization(데드락 특성)

• 시스템 모델링 (System modeling)
  • 프로세스: P1, P2, ..., Pn.
  • 자원 유형(resource types): R1, R2, ..., Rm
    • CPU 사이클, 메모리 공간, I/O 장치, 파일 등.
  • 각 자원 유형 Ri는 Wi 인스턴스를 가짐.
  • 각 프로세스는 다음과 같이 자원을 이용합니다:
    • 요청 (request)
    • 사용 (use)
    • 해제 (release)

• Deadlock은 네 가지 조건이 동시에 성립할 때 발생할 수 있습니다. (Deadlock can arise, 무조건 발생하는 것이 아님)
  • 상호 배제 (Mutual exclusion)
    • 한 번에 하나의 프로세스만 자원을 사용할 수 있음.
  • 점유 및 대기 (Hold and wait)
    • 적어도 하나의 자원을 보유하고 있는 프로세스가 다른 프로세스가 보유하고 있는 추가 자원을 획득하기 위해 대기하고 있다.
  • 비선점 (No preemption)
    • 자원은 이를 보유한 프로세스에 의해 자발적으로만 해제될 수 있음.
  • 순환 대기 (Circular wait)
    • P0, P1, ..., Pn의 대기 프로세스 집합이 존재하며, P0는 P1이 보유한 자원을 기다리고, P1은 P2가 보유한 자원을 기다리며, ... , Pn-1은 Pn이 보유한 자원을 기다리고, Pn은 P0가 보유한 자원을 기다림.

• 자원 할당 그래프 (Resource allocation graph)
  • V는 두 가지 유형으로 나뉩니다:
    • P = {P1, P2, ..., Pn}, 시스템의 모든 프로세스 집합.
    • R = {R1, R2, ..., Rm}, 시스템의 모든 자원 유형 집합.
  • E도 두 가지 유형으로 나뉩니다:
    • Pi → Rj : 요청 (request)
    • Rj → Pi : 할당 (assignment)
• 예제 (Examples)
  • Pi가 Rj의 인스턴스를 요청함.
    • 화살표 방향 : 프로세스에서 리소스로
  • Pi가 Rj의 인스턴스를 보유함.
    • 화살표 방향 : 리소스에서 프로세스로

 

• 자원 할당 그래프를 통한 Deadlock 예제 
  • (a) Deadlock 없음 (No deadlock)
  • (b) Deadlock 발생 (Deadlock)
  • (c) Deadlock 없음 (No deadlock)
  • 그래프에 사이클이 없으면 Deadlock 없음.
  • 그래프에 사이클이 있으면,
    • 자원 유형 당 인스턴스가 하나만 있으면 Deadlock 발생.
    • 자원 유형 당 인스턴스가 여러 개 있으면 Deadlock 발생 가능성.
    • (글 맨위에서 말했듯이 resource(R)에는 여러 개의 인스턴스(W)가 있을 수 있음 )

---

Methods for Handling Deadlocks

Deadlock 처리 방법

• 예방 (Prevention)
  • 시스템이 Deadlock 상태에 진입하지 않도록 합니다.
  • 네 가지 조건 중 적어도 하나가 성립되지 않도록 보장합니다.
• 회피 (Avoidance)
  • 시스템이 Deadlock 상태에 진입하지 않도록 합니다.
  • 각 프로세스가 자원을 어떻게 사용할 것인지에 대한 사전 정보를 필요로 합니다.
• 탐지 및 복구 (Detection and recovery)
  • 시스템이 Deadlock 상태에 진입하도록 허용한 다음 이를 복구합니다.

---

Deadlock Prevention

Deadlock 예방

• 네 가지 조건 중 적어도 하나가 성립되지 않도록 보장합니다.
  • 상호 배제 (Mutual Exclusion)
    • 상호 배제를 부정하는 것은 불가능합니다.
  • 점유 및 대기 (Hold and Wait)
    • 프로세스가 실행을 시작하기 전에 모든 자원을 요청하고 할당받도록 요구합니다.
  • 비선점 (No Preemption)
    • 자원을 보유한 프로세스가 다른 자원을 요청하고 해당 자원이 즉시 할당될 수 없는 경우, 현재 보유 중인 모든 자원을 해제합니다.
    • 프로세스는 요청한 새로운 자원과 이전 자원을 모두 다시 획득할 수 있을 때만 재시작됩니다.
  • 순환 대기 (Circular Wait)
    • 모든 자원 유형에 총 순서를 부여하고, 각 프로세스가 증가하는 순서로 자원을 요청하도록 합니다.

---

Deadlock Avoidance

Deadlock 회피

• Deadlock 회피 알고리즘 (Deadlock avoidance algorithm)
  • 프로세스가 사용 가능한 자원을 요청할 때, 시스템은 "즉시 할당이 시스템을 안전한 상태로 유지하는지" 결정해야 합니다.
    • 시스템이 각 프로세스에 자원을 할당하고 Deadlock을 피할 수 있는 순서가 있다면 상태는 안전합니다.
  • 시스템이 추가적인 사전 정보를 가지고 있어야 합니다.
• 시스템이 안전 상태(safe state)에 있으면 Deadlock이 없습니다.
• 시스템이 비안전 상태(unsafe state)에 있으면 Deadlock이 발생할 가능성이 있습니다.

 

• 자원 할당 그래프 (Resource allocation graph)
  • 예약 간선 (Claim edge) Pi → Rj:
    • Pj가 Rj를 요청할 수 있음을 나타냅니다. 점선으로 표시됩니다.
    • (프로세스가 새로 요구하는 자원)
  • 예약 간선이 요청 간선(request edge)으로 변환됩니다:
    • 프로세스가 자원을 요청할 때.
  • 요청 간선이 할당 간선(assignment edge)으로 변환됩니다:
    • 자원이 프로세스에 할당될 때.
  • 할당 간선이 예약 간선으로 재변환됩니다:
    • 프로세스가 자원을 해제할 때.
• 참고 [Note]
  • 여러 인스턴스의 자원 유형이 있는 경우 은행원 알고리즘(banker's algorithm)을 사용합니다.

Claim edge Pi -> Rj

• 프로세스 Pi가 자원 Rj를 미래에 요청할 수 있음을 뜻함 (점선으로 표시)
• 프로세스가 해당 자원 요청 시 request edge로 바뀜 (실선)
• Rj 가 realse 되면 assignment edge는 다시 claim edge로 바뀐다

Unsafe state(비안전 상태) 예시

 

R2에 대한 P2의 request를 grant 하면 사이클이 형성되어 데드락의 발생 가능성이 생기는 것

 

Deadlock Detection & Recovery

Deadlock 탐지 및 복구

• Allow system to enter deadlock state.
  • 시스템이 deadlock에 들어가도록 허용합니다.
• Detection algorithm.
  • 탐지 알고리즘
    • 주기적으로 알고리즘을 호출하여 그래프에서 사이클을 검색합니다.
      • 사이클이 존재하면 deadlock이 발생한 것입니다.
    • [참고] 자원 유형의 인스턴스가 여러 개인 경우 더 복잡한 알고리즘을 사용합니다.
• Recovery scheme.
  • 복구 계획
    • 프로세스 종료
      • 모든 deadlock 상태의 프로세스를 중단합니다.
      • deadlock 사이클이 제거될 때까지 한 번에 하나의 프로세스를 중단합니다. (피해의 최소화)
    • 자원 선점
      • 프로세스로부터 일부 자원을 선점하고, 이러한 자원을 다른 프로세스에 할당하여 deadlock 사이클이 깨질 때까지 진행합니다.