운영체제 [Deadlock]

Deadlock (교착상태)

- 프로세스가 발생 가능성이 없는 이벤트를 기다리는 경우

 

Deadlock vs starvation

(자원/Event)  //  (CPU)
(가능성x)     //   (가능성o)

자원의 분류

 

선점 가능 여부에 따른 분류

preemptible resources
- 선점 당한 후, 돌아와도 문제가 발생하지 않는 자원
-processor, memory등

Non-preemptible resources
- 선점 당하면, 이후 진행에 문제가 발생하는 자원
- disk drive등

할당 단위에 따른 분류

Total allocation resources
- 자원 전체를 프로세스에게 할당
- processor, disk drive 등

partitioned allocation resources
-하나의 자원을 여러 조각으로 나누어, 여러 프로세스들에게 할당
- Memory 등

동시 사용 가능 여부에 따른 분류

Exclusive allocation resources
- 한순간에 하나만 사용 가능한 자원
- processor, memory, disk drive 등

Non Exclusive allocation resources
- program(sw), shared data 등

재사용 가능 여부에 따른 분류

SR(serially-reusable Resources)
- 시스템 내에 항상 존재하는 자원
- 사용이 끝나면, 다른 프로세스가 사용 가능
- Processor, Memory, disk drive, program 등

CR(consumable Resources)
- 한 프로세스가 사용 한 후에 사라지는 자원
- signal, message 등

Deadlock을 발생시킬 수 있는 자원의 형태

- Non-preemptible resources
- Exclusive allocation resources
- serially-reusable Resources

 

 

Deadlock model (교착상태 표현법)

Graph model

- Node 와 edge를 이용하여 그래프로 표현
- Graph를 그린 뒤, cycle이 생성되면 Deadlock

State Transition Model

- 프로세스와 자원의 상태의 모든 경우의 수를 나타낸 Model

Deadlock 발생 필요 조건

- Non-preemptible resources
- Exclusive use of resources
- Hold and wait (parital allocation)
- Circular wait