📌deadlock detection

• 데드락을 막지 않음
• 주기적으로 데드락 발생을 확인
• Resource allocation graph(RAG)

📖RAG

• 데드락 검출을 위해 사용
• directed, bipartite graph

📖graph reduction

• 주어진 RAG에서 edge를 하나씩 지워가는 방법
• completely reduced : 모든 edge가 지워진 상태, deadlock이 없다는 의미
• irreducible : 지울수 없는 edge가 남아있는 상태, deadlock이 있다는 의미

edge 지우는 방법

• unblocked process : 필요한 자원을 모두 받을 수 있는 프로세스

1. unblocked process가 가지고 있는 edge를 모두 지운다.
2. unblocked process가 없을 때까지 반복

📌deadlock avoidance vs detection

• deadlock avoidance

  • 최악의 경우를 대비해 미리 데드락을 막는 방법
  • 데드락이 발생하지 않는다

• deadlock detection

  • 최선의 경우를 생각
  • 데드락 발생시 recovery가 필요

📌deadlock recovery

• 데드락이 발생했을 때, 데드락을 해결하는 방법

📖deadlock termination

• 데드락이 발생한 프로세스를 종료시키는 방법
• 강제 종료된 프로세스는 이후 재시작

termination cost model

• 데드락이 발생했을 때, 종료시킬 프로세스를 선택하는 방법
• 고려 요소
  • 종류
  • 총 수행시간
  • 남은 수행시간
  • 종료비용

📖resource preemption

• 데드락 상태 해결 위해 선점할 자원을 선택
• 선정 된 자원을 가지고 있는 프로세스를 종료시키고 자원을 빼앗음

preemption cost model

• 선점할 자원을 선택하는 방법

📖checkpoint-restart method

• 데드락 recovery에서 프로세스는 항상 종료된다
• 프로세스의 수행 중 특정 지점마다 context를 저장
• rollback : 데드락이 발생했을 때, 저장된 context로 되돌림