Deadlock

• 교착 상태
• 2개 이상의 process/thread들이 더 이상 진행 불가 상태
  • resource를 잡으면서 동시에 다른 process에 의해서 잡혀진 resource를 대기하는 상황
  • 서로 다른 resource를 잡고 서로 잡은 resource를 요청

Resources

• 한 번에 하나의 process에 의해서만 사용 가능
• preemtion
  • preemtable
    • 뺏기 가능
    • 수행 중에 내려 놓더라도 문제 X
  • non-preemtable
    • 뺏기 불가
    • 뺏기면 side effect 有

Resource Allocation Graphs

• 유향 그래프
  • directed graph
• procedure = O
• Resource = ㅁ
  • instance는 resource 안의 점으로 표시
• Edge
  • Request edge
    • P → R
  • Assignment edge
    • R → P
• Cycle
  • 없으면
    • no deadlock
  • 있으면
    • instance 한 개씩
      • deadlock 有
    • instance 여러 개씩
      • deadlock 가능성 有

Dining Philosophers Problem

• 원탁에 포크 5개, 식사하는 철학자 5명
  • 밥을 때 포크 2개 필요
    • 포크는 왼쪽부터 집음

Deadlock Characterization

• Deadlock이 발생하는 조건
• mutual exclusion
  • 상호 배제
  • 자원 특성
    • OS 관리 힘듬
• No preemption
  • resource를 빼앗을 수 없음
  • 자원 특성에 가까움
    • 빼앗기기 이전 state로 복귀 힘듬