<aside> 📌 교착상태(deadlock), The Deadlock Problem, Deadlock 발생의 4가지 조건, Resource-Allocation Graph(자원할당그래프), Deadlock Prevention, Deadlock의 처리 방법, Deadlock Avoidance, Resource Allocation Graph algorithm, Banker's Algorithm, Example of Banker's Algorithm

</aside>

교착상태(deadlock)

• 프로세스가 상대방의 자원을 서로 요구하고 있지만 가진 자원은 내놓지 않는 상황

The Deadlock Problem

• Deadlock
  • 일련의 프로세스들이 서로가 가진 자원을 기다리며 block된 상태
• Resource (자원)
  • 하드웨어, 소프트웨어 등을 포함하는 개념
  • ex) 하드웨어 - I/O device, CPU cycle, memory space / 소프트웨어 - semaphore 등
  • 프로세스가 자원을 사용하는 절차
    • Request → Allocate → Use → Release
• Deadlock Example 1
  • 시스템에 2개의 tape drive가 있다
  • 프로세스 P1과 P2 각각이 하나의 tape drive를 보유한 채 다른 하나를 기다리고 있다
• Deadlock Example 2

  • Binary semaphores A and B

    

    • P(S) 연산: 공유 자원 획득
    • V(S) 연산: 공유 자원 반납

Deadlock 발생의 4가지 조건

• Mutual exclusion (상호 배제)
  • 매 순간 하나의 프로세스만이 자원을 사용할 수 있음
• No Preemption (비선점)
  • 프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않음
• Hold and wait (보유 대기)
  • 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있음
• Circular wait (순환 대기)
  • 자원을 기다리는 프로세스간에 사이클이 형성되어야 함
  • 프로세스 P0, P1, …, Pn 이 있을 때
    • P0은 P1이 가진 자원을 기다림
    • Pn-1은 Pn이 가진 자원을 기다림
    • Pn은 P0이 가진 자원을 기다림