운영체제 강의 21

1. 교착상태(deadlock)

2. The Deadlock Problem

‣ Deadlock

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

‣ Resource(자원)

       ✓ 하드웨어, 소프트웨어 등을 포함하는 개념

       ✓ 예) 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

 

3. Deadlock 발생의 4가지 조건

‣ Mutual exclusion (상호 배제) : 매 순간 하나의 프로세스만이 자원을 사용할 수 있음

‣ No preemption (비선점) : 프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않음

‣ Hold and wait : 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있음

‣ Circular wait : 자원을 기다리는 프로세스간에 사이클이 형성되어야 함

 

4. Resource-Allocation Graph

P : Process                R : Resource

• 그래프에 cycle이 없으면 deadlock이 아니다

• 그래프에 cycle이 있으면

           ✓ if only one instance per resouce type, then deadlock

           ✓ if several instances per resource type, possibility of deadlock

 

5. Deadlock의 처리 방법

‣ Deadlock Prevention

       ✓ 자원 할당 시 Deadlock의 4가지 필요 조건 중 어느 하나가 만족되지 않도록 하는 것

‣ Deadlock Avoidance

       ✓ 자원 요청에 대한 부가적인 정보를 이용해서 deadlock의 가능성이 없는 경우에만 자원을 할당

       ✓ 시스템 state가 원래 state로 돌아올 수 있는 경우에만 자원 할당

‣ Deadlock Detection and recovery

       ✓ Deadlock 발생은 허용하되 그에 대한 detection 루틴을 두어 deadlock 발견시 recover

‣ Deadlock Ignorance

       ✓ Deadlock을 시스템이 책임지지 않음

       ✓ UNIX를 포함한 대부분의 OS가 채택