deadlock 해결 조건

• deadlock prevention methods
• deadlock avoidance method
• deadlock detection and deadlock recovery methods

Deadlock avoidance method(교착상태 회피)

• 시스템의 상태를 계속 감시
• 시스템이 deadlock 상태가 될 가능성이 있는 자원 할당 요청 보류
• 시스템을 항상 safe state로 유지!

safe state

• 모든 프로세스가 정상적 종료 가능한 상태
• safe sequence가 존재(safe sequence가 존재하면 safe state임.)
  • Deadlock 상태가 되지 않을 수 있음을 보장

unsafe state

• Deadlock 상태가 될 가능성이 있음
• 반드시 발생한다는 의미는 아님

가정

• 프로세스의 수가 고정됨
• 자원의 종류와 수가 고정됨
• 프로세스가 요구하는 자원 및 최대 수량을 알고 있음
• 프로세스는 자원을 사용 후 반드시 반납한다.
  -> 비현실적(not practical)

Dijkstra's algorithm

• Banker's algorithm

Harbermanss's algorithm

Dijkstra's banker's algorithm

• Deadlock avoidance를 위한 간단한 이론적 기법
• 가정
  • 한 종류(resource type)의 자원이 여러 개(unit)
  • 시스템을 항상 safe state로 유지

safe state 예시

• 자원 종류 1개(R), 자원 10개, 프로세스 3개
  

unsafe state 예시

bankers algorithm 해보기

• 기존 흐름: 자원 요청이 들어오면, 요청받은 자원을 줬을 때 safe state가 유지 되는지 미리 simulation돌려보고 된다면 자원을 할당해줌, 안되면 Reject

accept

reject

Harbermanss's algorithm

Deadlock avoidance 정리

• Deadlock의 발생 막을 수있음
• High overhead
  • 항상 시스템 감시해야 함
• Low resource utilization
  • safe state 유지를 위해 사용 되지 않는 자원이 존재
• Not practical
  • 가정
    • 프로세스 수, 자원 수가 고정
    • 필요한 최대 자원 수를 알고 있음

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

Deadlock Detection

• Deadlock 방지를 위한 사전 작업을 하지 않음(발생하면 그때 가서 해결하자!)
  • Deadlock 발생 가능함!
• 주기적으로 deadlock 발생 확인
  • 시스템이 deadlock 상태인가?
  • 어떤 프로세스가 deadlock 상태인가?
• resource Allocation Graph(RAG) 사용

Resource Allocation Graph(RAG)

• Deadlock 검출을 위해 사용
• Directed, bipartite Graph
  • bi 두개, partite나누다 -> 두개로 나누다.
  • Process(사진상 U)와 Resource(사진상 V)두 개로 나눔
    
    
• G = (N, E)
  • G는 그래프, N은 노드, E는 edge
• N = {Np, Nr}
  • 노드는 프로세스 노드와 리소스 노드의 집합이다!
  • {}는 집합을 의미
  • Np는 프로세스 노드
  • Nr은 리소스 노드

• e 는 edge
• P -> R 이면 자원 요청
• R -> P 이면 자원 할당
  
  

Graph reduction

Deadlock Recovery

• deadlock을 검출한 후 해결하는 과정

Deadlock recovery methods

• process termination
  • deadlock 상태에 있는 프로세스를 종료시킴
  • 강제 종료된 프로세스는 이후 재시작 됨
• Resource preemption
  • deadlock 상태 해결 위해 선점할 자원 선택
  • 선정된 자원을 가지고 있는 프로세스에서 자원을 빼앗음
    • 자원을 빼앗긴 프로세스는 강제종료 됨.

process termination

• deadlock 상태인 프로세스 중 일부 종료
• 누구를 종료시킬지 선택해야 함(termination cost model)

termination cost model

• 종료 시킬 deadlock 상태의 프로세스 선택

• termination cost

  • 우선순위 / Process priority
  • 종류 / Process type
  • 총 수행 시간 / Accumulated execution time of the process
  • 남은 수행 시간 / Remaining time of the process
  • 종료 비용 / Accounting cost
  • Etc.

• 1) Lowest-termination cost process first

  • Simple
  • Low overhead
  • 불필요한 프로세스들이 종료될 가능성이 높음

• 2) Minimum cost recovery

  • 최소 비용으로 deadlock 상태를 해소할 수 있는 process 선택
    • 모든 경우의 수를 고려해야 함
  • Complex
  • High overhead
    • O(2k승) -> k개의 프로세스가 있으면 경우의 수가 2의 k승

Resource preemption

• Deadlock 상태 해결을 위해 선점할 자원 선택
• 해당 자원을 가지고 있는 프로세스를 종료시킴
  • Deadlock 상태가 아닌 프로세스가 종료될 수도 있음
  • 해당 프로세스는 이후 재시작 됨

선점할 자원 선택

• Preemption cost model이 필요(선점 기준)
• Minimum cost recovery method 사용
  • O(r)

Checkpoint-restart method

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