[운영체제-김덕수교수님] 교착상태(5/5) - Detection & Recovery

Deadlock Detection

‏‏‎ ‎

• Deadlock 방지를 위하 사전작업을 하지 않음
  • deadlock 발생 가능
• 주기적으로 deadlock 발생 확인
  • 시스템이 deadlock 상태인가?
  • 어떤 프로세스가 deadlock 상태인가?

• Resource allocation graph(RAG) 사용
  • Deadlock 검출을 위해 사용
  • Directed, bipartite Graph(바이파타이트)
    • 양분된 영역이 존재

그래프의 모습은 대략 이렇다.

전체 프로세스의 개수 - Np

전체 자원의 개수 - Nr

• Resource allocation graph(RAG)
  • Edge는 Np와 Nr 사이에만 존재
    • e = (Pi, Rj): 자원 요청
      • 간선의 방향이 나타나는데, P에서 R로 가면 요청
    • e = (Rj, Pi): 자원 할당
      • 간선의 방향이 나타나는데, R에서 P로 가면 할당

• 이게 조금 어렵게 느껴질 수 있는데, Rk 와 Tk 는 다른 것이다.
• 그림에서 보면 1 이라는 타입의 자원이 있는 것이고, R1 은 이 자원을 뜻하는 것이다. T1 은 그 R1에 속한 자원의 개수를 뜻한다. 여기선 2개다
• T2 의 개수는 그렇게 따지면 4개이다.
• |a,b| : 절대값을 뜻한다. 간선의 개수라고 생각하면 편하다.
• 여기까지 봐서 이해가 안갈 수 있는데 그림으로 설명하면 쉽다.

• 우리는 데드락이 발생했는지 아닌지 "감지"가 목표다.
• 간선을 하나씩 지우면서 모두 간선이 지워지면(할당된 자원이 모두 반납되면) 데드락이 없는 것이다.
• 위의 예제는 데드락이 없다. 왜 와이?
  • P1 에서 R2 로 자원 1개를 요청했다. 잉여 자원이 있으므로 할당가능
  • P1에서 R1로 자원 2개가 할당되었다.
  • P1에서 모든 자원을 할당받았으므로 작업이 수행되고 반납가능하다.
    • 간선을 모두 지울수 있다.
  • P2에서 R1 으로 자원을 요청하고 자원이 할당되었다.
  • P2에서 R2로 자원을 요청하고 자원이 할당되었다.
    • 간선을 모두 지울 수 있다.

---

Detection 방법

• Graph reduction
  • 주어진 RAG에서 간선을 하나씩 지워가는 방법
  • Completely reduced
    • 모든 간선이 제거됨
    • Deadlock 에 빠진 프로세스가 없음
  • irreducible
    • 지울 수 없는 간선이 존재
    • 하나 이상의 프로세스가 deadlock 상태
• Unblocked process
  • 필요한 자원을 모두 할당 받을 수 있는 프로세스

위의 공식을 만족하면 Unblocked process 이다.

J 는 상수, j 앞에 있는 이집트 문자같은 것(이산 수학 기호)은 "모든"을 뜻한다.

즉, 모든 j에 대해서 (괄호) 안의 공식을 만족하면 Unblocked process 이다.

|(Pi, Rj)|

• Pi 에서 Rj 로 가는 간선
• Pi 가 요청하는 모든 자원(Rj)에 대해

Tj - 시그마k|(Rj, Pk)|

• Rj 의 자원 수 전체 - | Rj -> Pk |
  • Rj 에서 P에 할당된 모든 자원(모든 간선)
• 전체 개수에서 이미 할당된 자원을 뺀다
• 앞으로 할당할 수 있는 남은 자원 수
• Pj 가 요청하는 자원의 수가 남은 자원수 이하면
• P 는 Unblocked state 이다.

필요한 자원을 모두 할당 받을 수 있는 프로세스를 Unblocked Process라고 한다.

‏‏‎ ‎

자 아직도 감지 방법을 들어가지 못했다. 여기까지 용어 정리가 끝났다

진짜 "감지" 방법

• Graph Reduction procedure
  • 1. unblocked process 에 연결된 모든 간선을 제거
  • 더 이상 unblocked process 가 없을 때까지 1을 반복

‏‏‎ ‎

• 최종 Graph 에서
  • 모든 edge가 제거됨(Completely reduced)
    • 현재 상태에서 deadlock 이 없음
  • 일부 edge가 남음(irreducible)
    • 현재 deadlock 존재
• 그림으로 보면 조금 낫다..(쪼금)

‏‏‎ ‎

상황 1

• (a)-(b)-(c) 순서로 보는 것이다.
• 먼저 a 를 보면 P1 은 Unblocked process 인가?
  • R2 에 요청한 자원 1, 할당받은 자원 1 - 위 공식 만족
  • R1에 요청한 자원 2, 할당받은 자원 2 - 위 공식 만족
• P1 은 Unblocked process 이므로 모든 간선을 지울 수 있다.
• P2 도 마찬가지로 지울 수 있다.

상황 2

• P3 을 보자
• unblocked 상태다. 간선을 지울 수 있다.
• P2 를 보자
  • |(R1, P2)| 간선을 지울 수 있다.
  • |(P2,R3)| 간선을 지울 수 있다.
• R2로 자원을 요청한느 간선은 2개이다.
• 그치만 남은 자원의 개수는 1개이다. (P1이 물고 있음)
• 위 공식을 만족하지 못한다.
• 즉 Blocked Process 이다.

‏‏‎ ‎

결론

• High overhead
  • 검사 주기에 영향을 받음
  • Node의 수가 많은 경우
• Low overhead deadlock detection methods
  • single-unit resources
  • single-unit request in expedient state

---

Deadlock Avoidance vs Detection

• Avoidance
  • 최악의 경우를 생각
    • 앞으로 일어날 일을 고려
  • Deadlock 이 발생하지 않음
• Deadlock detection
  • 최선의 경우를 생각
    • 현재 상태만 고려
  • Deadlock 발생 시 Recovery 과정 필요

‏‏‎ ‎

---

Deadlock Recovery

• 데드락을 검출한 후 해결하는 과정
• Deadlock recovery methods
  • process termination
    • Deadlock 상태에 있는 프로세스를 종료 시킴
    • 강제 종료된 프로세스는 이후 재시작 됨
  • resource preemption
    • deadlock 상태 해결 위해 선점할 자원 선택
    • 선정된 자원을 가지고 있는 프로세스에서 자원을 빼앗음
      • 자원을 빼앗긴 프로세스는 강제 종료됨
• Termination cost model
  • 종료 시킬 deadlock 상태의 프로세스 선택
  • termination cost
    • 우선순위
    • 종류
    • 총 수행시간
    • 남은 수행시간
    • 종료 비용
    • Etc
  • 어떤 코스트 모델을 사용하느냐에 따라 종료시킬 프로세스가 달라짐

‏‏‎ ‎

종료 프로세스를 고르는 방법엔 두가지가 있다.

• Lowest-termination cost process first
  • simple
  • low overhead
  • 불필요한 프로세스들이 종료 될 가능성이 높음
• minimum cost recovery
  • 최소 비용으로 deadlock 상태를 해소 할 수 있는 process 선택
    • 모든 경우의 수를 고려 해야함
  • Complex
  • High overhead
    • O(2k)

선점할 자원을 선택

• Resource preemption
  • deadlock 상태 해결을 위해 선점할 자원 선택
    • Preemption cost model 이 필요
    • Minimum cost recovery method 사용
      • O(r)
  • 해당 자원을 가지고 있는 프로세스를 종료 시킴
    • deadlock 상태가 아닌 프로세스가 종료 될 수도 있음
    • 해당 프로세스는 이후 재시작 됨

‏‏‎ ‎

종료된 프로세스는 어떻게 복구?

• Checkpoint-restart method
  • 프로세스의 수행 중 특정 지점(checkpoint)마다 context 를 저장
  • Rollback 을 위해 사용
    • 프로세스 강제 종료 후, 가장 최근의 checkpoint에서 재시작

‏‏‎ ‎

요약

• Deadlock 의 개념
• Deadlock model
• Deadlock 해결 방법들
  • 예방
  • 회피
  • 탐지와 복구

‏‏‎ ‎

‏‏‎ ‎

‏‏‎ ‎