Chapter7 교착상태(Deadlock Resolution)

Chapter7 교착상태(Deadlock Resolution)

1. Deadlock의 개념

• 프로세스나 시스템이 발생 가능성이 없는 이벤트를 기다리는 상태

• 

  
  
  • blocked/asleep state : 프로세스가 특정 이벤트나 자원을 기다리는 상태

 

1.1 Deadlock vs Starvation

• Deadlock : 자원이나 이벤트를 기다리는 상태 → but 가능성이 zero
• Starvation : CPU를 기다리는 상태 → 운이 없어서 순서가 계속 뒤로 밀림

 

1.2 자원의 분류

• 선점 가능 여부에 따른 분류
  • Preemptible resources : 선점 당한 후 ,돌아와도 문제가 발생하지 않음(뺏길 수 있음)
    • ex) processor, memory
  • Non-preemptible resources : 선점 당하면, 이후 진행에 문제가 발생(뺏기지 않음)
    • ex) disk drive
• 할당 단위에 따른 분류
  • Total allocation resources : 자원 전체를 프로세스에 할당
    • ex) processor, disk drive
  • Partitioned allocationresources : 자원을 여러 조각으로 나누어, 여러 프로세스들에게 할당
    • ex) memory
• 동시 사용 가능 여부에 따른 분류
  • Exclusive allocation resources : 한 순간에 한 프로세스만 사용 가능한 자원
    • ex) processor, disk drivce, memory → 쪼개는 것은 가능하지만 쪼갠 범위내에서 한 프로세스만 사용가능
  • Shared allocation resources : 여러 프로세스가 동시에 사용 가능한 자원
    • ex) Program(SW), shared data
• 재사용 가능 여부에 따른 분류
  • SR(Serially-reusable Resources) : 사용이 끝나면 다른 프로세스가 사용 가능
  • CR(Consumable Resources) : 한 프로세스가 사용한 후에 사라지는 자원
    • ex) signal, message

 

1.3 교착 상태를 발생시킬 수 있는 요소

• 자원의 특성
  • Exclusive use of resources
  • Non-preemptible resources
• 프로세스의 특성
  • Hold and Wait(Partial allocation) : 자원을 하나 hold한 채로 다른 자원 요청
  • Circular wait : 자원과 프로세스간의 관계가 서로 원형을 이루는 상태

2. 표현볍

2.1 Graph Model

• 그래프 모형으로 표현한 모델
• Node : 프로세스 노드(P1, P2), 자원 노드(R1, R2)
• Edge
  • Rj → Pi : 자원 Rj이 프로세스 Pi에 할당 됨
  • Pi → Rj : 프로세스 Pi가 자원 Rj을 요청(대기 중)

• 

 

2.2 State Transition Model

• 상태 변화를 표현한 모델
• 가정
  • 2개의 프로세스와 같은 타입의 자원 2개가 존재
  • 프로세스는 한번에 자원 하나만 요청/반납 가능
  • 프로세스는 총 5개의 상태만을 가짐

    • 

• 

  
  
  • S33 상태는 교착상태가 발생하는 상태

3. 해결법

3.1 Deadlock prevention methods(교착상태 예방)

• Deadlock을 발생시킬 수 있는 요소 중 하나 제거
  1. Exclusive use of resources 제거
     • 현실적으로 불가능
  2. Non-preemptible reosources 제거
     • 현실적으로 불가능
  3. Hold and wait 조건 제거
     • 자원의 낭비, 무한 대기 현상 발생 가능
  4. Circular wait 조건 제거
     • 자원들에게 순서를 부여하여 프로세스가 순서의 증가 방향으로만 자원 요청 가능하게 함
     • 자원의 낭비
• 절대 Deadlock이 발생하지 않음
• 자원 낭비가 발생해 비현실적이다.

3.2 Deadlock avoidance methods(교착상태 회피)

• 시스템의 상태를 계속 감시하여 deadlock 상태가 될 가능성이 있는 자원 할당 요청시 요청을 보류 함
• → 시스템을 항상 safe state로 유지
• Safe state
  • 모든 프로세스가 정상적으로 종료 가능한 상태 → Safe sequence(Deadlock 상태가 되 지 않는 것을 보장)가 존재
  ↔ Unsafe state : Deadlock 상태가 될 가능성이 있음, 반드시 발생x
• 가정
  • 프로세스 수가 고정
  • 자원의 종류와 수가 고정
  • 프로세스가 요구하는 자원 및 최대 수량을 알고 있음
  → 비현실적
• 특징
  • Deadlock의 발생을 막을 수 있음
  • 항상 시스템을 감시하고 있어야 함 → high overhead
  • 자원 효율이 떨어짐
  • 비현실적임

 

3.2.1 Dijkstra's banker's algorithm

• 가정
  • 한 종류의 자원이 여러 개
  • 시스템을 항상 safe state로 유지

• 

• 

 

3.2.2 Habermann's algorithm

• Dijkstra's banker's algorithm을 확장한 개념
• 여러 종류의 자원 고려
• 시스템을 항상 safe statefh 유지

3.3 Deadlock detection and deadlock recovery methods(교착상태 탐지 및 복구)

3.3.1 Deadlock Detection

• Resource Allocation Graph (RAG)
  • Deadlock 검출을 위해 사용
  • Directed, bipartite graph

    • 

  • G = (N, E)
    • N = {Np, Nr}

      • 

    • E(Edge) : Np와 Nr사이만 존재
      • e = (Pi, Rj) : 자원 요청
      • e = (Rj, Pi) : 자원 할당

        • 

  • Rk : k type의 자원
  • tk : Rk의 단위 자원 수
  • |(a, b)| : (a, b) edge의 수

    • 

  • ex)

    

• Graph reduction
  • 주어진 RAG에서 edge를 하나씩 지워가는 방법
    1. Unblocked process에 연결 된 모든 edge를 제거
       • unblocked process : 필요한 자원을 모두 할당 다을 수 있는 프로세스
         • 프로세스가 요청 한 자원 수 <= 남은 자원의 수
    2. 더 이상 unblocked process가 없을 때까지 1을 반복
  • 모든 edge가 제거되면 Deadlock에 빠진 프로세스가 없음

    • 

  • 지울 수 없는 edge가 존재하면 하나 이상의 프로세스가 deadlock 상태

    • 

  • High overhead → 검사 주기에 영향을 받음
• 현재 상태만을 고려 함 → avoidnace와 달리 최선의 경우를 생각 함
  • Deadlock이 발생 시에 Recovery 과정이 필요

 

3.3.2 Deadlock Recovery

• Process termination
  • Deadlock 상태의 프로세스를 종료 시킴
• Resource preemption
  • Deadlock 상태 해결을 위해 선점할 자원 선택 → 선정 된 자원을 가진 프로세스에서 자원을 빼았음(프로세스를 강제 종료시킴)
• Checkpoint-restart method
  • 프로세스의 수행 중 특정 지점 마다 context를 저장(checkpoint)
  • Rollback을 위해 사용