Deadlocks
multi programming 환경에서 여러 thread가 한정된 resource를 사용하려고 서로 경쟁할 수 있다.
한 thread가 resource를 요청했을 때, 그 시각에 그 resource를 사용할 수 없는 상황이 발생할 수 있고, 그때는 thread가 대기 상태로 들어간다.
대기 중인 thread가 결코 다시는 그 상태를 변경시킬 수 없는 상황을 deadlock이라고 한다. 이 때에는 더이상 process가 진행되지 못하는 상태로 매우 치명적인 상태이다.
필요조건
deadlock은 한 시스템에 다음 네 가지 조건이 동시에 성립될 때 발생할 수 있다.
- 상호 배제(mutual exclusion): 최소한 하나의 resource가 비공유 모드로 점유되어야 한다. 비공유 모드에서는 한 번에 한 thread만이 그 resource를 사용할 수 있다. -> 한 번에 한 process만 사용할 수 있는 resource가 있어서 발생한다.
- Hold and wait: 어떤 process가 resource를 잡고 있는데 다른 resource를 또 요청하는 것.
- No preemption: 만약 resource를 요청, 언제든 그 resource를 뺐어 자신이 사용 가능한 process가 있다면 deadlock은 발생하지 않는다. 요청하는 resource를 언제든 막힘없이 가져오기 때문이다. no preemption의 경우 뺐어올 수 없으니 대기해야 하고 deadlock이 발생할 수 있다(그 resource를 잡고 있는 process가 release하지 않는다면)
- Circular wait: 순환대기. 대기하고 있는 thread의 집합 { T0, T1, ..., Tn }에서 T0는 T1이 점유한 resource를 대기하고 T1은 T2가 점유한 resource를 대기하고, ..., Tn-1d은 Tn이 점유한 resource를 대기하며 Tn은 T0가 점유한 resource를 대기한다.
Resource Allocation Graph
deadlock을 판별하기 위한 그래프. 시스템의 자원 할당 상황을 그래프로 나타낸다.
- P: process
- R: resource
- P -> R: Request Edge, process가 해당 resource를 요청
- R -> P: Assignment Edge, 해당 resource가 process에 할당되어 있음

deadlock이 발생하는 cycle.
만약 요청하는 resource가 여러개 있다면 cycle이 발생하더라도 deadlock이 발생하지 않을 수 있다.

cycle이 있어도 deadlock이 발생 X
P2가 R1을 가진 상태에서 release할 수 있다.
R1 하나는 P1에게 주면 되므로 P1이 수행이 끝나면서 R2 하나가 release되고 그것이 P3에 할당 가능하다.
Methods for Handling Deadlocks
- Deadlock prevention: 아에 deadlock에 접근 안 하도록. resource의 활용도가 떨어질 수 있다. deadlock 발생 조건 4가지를 부정하는 것을 통해 가능.(발생하지 않도록 미리 그 조건들을 피하게 코드를 짠다거나 수정) 제약 조건이 점점 붙게 되므로 resource활용도가 떨어지는 것
- Deadlock avoidance: resource 활용도를 좀 더 높일 수 있게된다. 조건 4가지를 부정하기는 하는데(실제로 부정은 3가지가 최대) 이것에 대해서는 banker's algorithm이 있다.
728x90
반응형
'운영체제' 카테고리의 다른 글
| 시스템 콜(System call) (0) | 2022.07.21 |
|---|---|
| 인터럽트(interrupt) (0) | 2022.07.21 |
| 쓰레드(Threads)와 multi process 차이, java에서 thread 그룹 (0) | 2022.07.15 |
| CPU Switch From Process to Process (0) | 2022.07.15 |