운영체제 - Deadlock

Deadlock

: 일련의 프로세스들이 서로가 가진 자원을 기다리며 block된 상태

Deadlock 발생 조건

(1) Mutual exclusion
: 매 순간 하나의 프로세스만이 자원을 사용할 수 있음
(2) No preemption
: 프로세스는 자원을 스스로 내어 놓을 뿐 강제로 빼앗기지 않음
(3) Hold and wait
: 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있음
(4) Circular wait
: 자원을 기다리는 프로세스간에 사이클이 형성되어야 함

Deadlock 처리 방법

(1) Prevention
: Deadlock의 4가지 필요 조건 중 어느 하나가 만족되지 않도록 함

• Mutual Exclusion
  • 공유해서는 안되는 자원의 경우 반드시 성립해야 함
• Hold and Wait
  • 프로세스 시작 시 모든 필요한 자원을 할당 or
  • 자원이 필요할 경우 보유 자원을 모두 놓고 요청
• No preemption
  • 자원을 빼앗을 수 있도록 함
  • State를 쉽게 저장할 수 있는 자원에서 주로 사용(CPU, memory)
• Circular Wait
  • 모든 자원에 할당 순서를 정함

(2) Avoidance
: 자원 요청에 대한 부가정보(ex. 자원별 최대 사용량)를 이용해서 자원 할당이 deadlock으로부터 안전한지를 조사해서 안전한 경우에만 할당

• Resource Allocation Graph Algorithm, Banker's Algorithm

(3) Detection and Recovery
: Deadlock 발생은 허용하되 그에 대한 detection 루틴을 두어 deadlock 발견시 recover

• Recovery
  • Process termination
    • Deadlock 상태의 프로세스들을 모두 중지
    • Deadlock 상태가 제거될 때까지 프로세스 하나씩 중지
  • Resource Preemption
    • 비용을 최소화할 victim을 선정
    • safe state로 rollback하여 process를 restart

(4) Ignorance
: Deadlock에 대해 아무런 조치도 취하지 않음

• Deadlock이 매우 드물게 발생하므로 deadlock에 대한 조치 자체가 더 큰 overhead일 수 있음
• 사람이 직접 process를 죽이는 방법 등으로 대처
• UNIX, Windows 등 현대의 대부분 운영체제들이 채택