[운영체제] 7. Deadlocks (1)

Deadlock(교착상태, 데드락)

일련의 프로세스들이 서로가 가진 자원을 기다리며 block 된 상태. 각 프로세스는 다른 프로세스가 가진 자원을 얻기 위해 무한정 기다리고 있어서 더 이상 진행할 수 없는 상태

Resource(자원)

• 하드웨어, 소프트웨어 자원 등을 포함하는 개념
• 예) I/O device , CPU cycle, memory space, semaphore 등
• 자원 사용 절차
  • request, allocate, use, release
    • 자원 요청 → 자원 획득 → 자원 사용 → 자원 반납
• Deadlock Example1
  • 시스템에 2개의 tape drive가 있다.
  • 프로세스 P1과 P2 각각이 하나의 tape drive를 보유한 채 다른 하나를 기다리고 있다.
    : 두 프로세스 모두 서로가 점유하고 있는 테이프 드라이브를 얻기 위해 무한정 기다는 상황 => 이러한 상태에서는 두 프로세스 모두 진행할 수 없으며, 시스템은 블록된 상태에 갇히게 된다!
• Deadlock Example 2
  • Binary semaphores A and B

CPU가 어느 누구한테 가더라도 둘중에 하나는 어느 누구도 획득안되기 때문에 Deadlock 발생

Deadlock 발생의 4가지 조건

• Mutual Exclusion(상호 배제)
  • 매 순간 하나의 프로세스만이 자원을 사용할 수 있음
  • 가지고 있는 동안에는 독점적으로 사용한다.
• No preemption(비선점)
  • 프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않음
  • 자원을 빼앗긴다면 데드락이 생기지 않음
  • 추가 자원을 요청할 때는 보유한 자원을 내어놓지 않으면 데드락이 발생
• Hold and wait(보유 대기)
  • 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있음
  • 내가 가진 자원 보유하면서 기다리는 상태
  • 내가 가진 자원 내어놓지 않아야지 데드락이 생김
• Circular wait (순환대기)
  • 자원을 기다리는 프로세스간에 사이클이 형성되어야 함
  • 프로세스 P0, P1, … , Pn이 있을 때
    • P0은 P1이 가진 자원을 기다림
    • P1은 P2가 가진 자원을 기다림
    • Pn-1은 Pn 이 가진 자원을 기다림
    • Pn은 P0이 가진 자원을 기다림
  • 원형으로 자원을 기다리는 순환 구조. 이러한 순환 구조로 인해 무한정 자원을 기다리는 상태가 되어 데드락이 발생