[OS]CH7. Deadlock(교착상태)

 

본 글은 HPC Lab의 youtube 강의를 듣고 요약한 것입니다. 모든 이미지 출처 역시 HPC Lab의 pdf 수업자료입니다.

 

Deadlock 발생 필요조건 4가지

---

• Mutual exclusion of resources : 자원은 한 번에 한 프로세스만 사용 가능
• Non-preemption resources : 자원은 오로지 사용 중인 프로세스가 끝날 때만 반환 가능
• Hold and wait(Partial allocation) : 자원을 이미 hold하고 다른 자원 요청
• Circular wait : P0은 P1이 사용 중인 자원을 기다리고, P1은 P2가 사용 중인 자원을 기다리고...Pn은 P0이 사용 중인 자원을 기다리는 형태

1,2번은 자원의 특성이고 3,4번은 프로세스의 특성이다. 위의 조건 4개가 모두 성립하면 deadlock이 발생한다. 줄여서 'MCNH'이라 외우자!

 

Deadlock 해결방법

---

• Deadlock prevention
• Deadlock avoidance
• Deadlock detection & recovery

 

Deadlock prevention

---

• 4개의 deadlock 발생 조건 중 하나 제거
• deadlock이 절대 발생하지 않게 하는 방법
• 전반적으로 자원활용도가 떨어지는 비현실적 방법

1. Mutual exclusion 제거
   • 모든 자원을 공유가능하도록 하면 됨
   • BUT 현실적으로 불가능
2. Non-preemption 제거
   • 현실적으로 불가능
   • 유사한 방법으로는 프로세스가 할당받을 수 없는 자원 요청한 경우, 기존에 가지고 있던 자원을 모두 반납하고 작업 취소했다가 다시 시작하게 할 수 있음 -> 심각한 자원낭비(비현실적)
3. Hold and wait(Partial allocation) 제거
   • 필요 자원 한 번에 모두 할당(Total allocation)시키는 방법으로 해결
   • BUT 자원 낭비 발생(특정 자원은 사용이 끝났어도 계속 hold하고 있음) + Starvation 발생가능
4. Circular wait 제거
   • 자원에 순서를 부여해 증가하는 방향으로만 요청 가능하도록 설정
   • BUT 자원 낭비 발생(사용가능한 자원이 있어도 순서때문에 할당 못받는 상황)

• Deadlock prevention의 장단점
  • 장점
    • Deadlock 절대 발생 안함
  • 단점
    • 구현이 비현실적
    • 낮은 자원활용도

 

Deadlock avoidance

---

• 시스템을 감시하며 deadlock이 될 가능성이 있는 자원 할당 요청 보류
• 시스템을 항상 safe-state로 유지
  • safe-state : 모든 프로세스가 정상적 종료가 가능한 상태로 safe sequence가 존재
  • unsafe-state : deadlock이 될 가능성 존재(반드시 발생한단 의미는 X)
• Deadlock avoidance algorithm
  • Banker's algorithm
  • Habermann's algorithm(Banker's algorithm의 확장판, 여러 종류의 자원 고려)

자원할당 accept 예시

자원할당 reject 예시

Habermann's algorithm 예시

Habermann's algorithm accept 예시

Habermann's algorithm reject 예시

• Deadlock avoidance 장단점
  • 장점
    • Deadlock 발생 막을 수 있음
  • 단점
    • High overhead : 항상 시스템을 감시해야 함
    • 낮은 자원활용도 : safe state 유지 위해 사용되지 않는 자원 존재
    • 비현실적 : 애초에 프로세스 수, 자원 수 고정 + 필요한 최대 자원 수 알고 있다는 가정이 들어감

 

Deadlock detection & recovery

---

• Deadlock 방지를 위한 사전작업 하지 않음 -> deadlock 발생가능
• 대신, RAG(Resource Allocation Graph)로 주기적으로 deadlock 발생 여부 확인
• RAG(Resource Allocation Graph)
  • Deadlock 검출 위해 사용
  • directed, bipartite(자원-프로세스 간에만 edge 가질 수 있음) graph
  • P->R : 자원 요청 / R->P : 자원 할당

자원 요청, 할당 edge

RAG 예시

• Graph reduction
  1. unbloked process(필요한 자원을 모두 할당받을 수 있는 프로세스)에 연결된 모든 edge 제거
  2. 더 이상 unbloked process가 없을 때까지 1번 반복
  3. 최종 그래프에서 모든 edge가 제거되면 deadlock 없음, 일부 edge가 남으면 deadlock이 존재

deadlock 없는 예시

deadlock 발생 예시

• Deadlock recovery : deadlock 검출 후 해결하는 과정
• Recovery method
  1. Process termination
     • deadlock 상태에 있는 프로세스 종료시킴(최소비용이 드는 프로세스 선택해야 함)
     • 종료된 프로세스는 이후 재시작
  2. Resource preemption
     • deadlock 상태 해결 위해 선점할 자원 선택
     • 해당 자원을 갖고 있는 프로세스에서 자원 뺏어옴(선점)
     • 자원 뺏긴 프로세스는 강제종료 되고 이후 재시작
     • BUT) deadlock 상태가 아닌 프로세스가 종료될 수도 있음
• Checkpoint-restart method
  • 프로세스 수행 중 특정지점(checkpoint)마다 context 저장
  • Rollback을 위해 사용(프로세스 강제종료 후 가장 최근의 checkpoint에서 시작)