Deadlock
- 2개 이상의 프로세스나 스레드가 아무것도 하지 못하는 상태로 서로 영원히 대기하는 현상
- 프로세스들이 서로 상대방이 사용 주인 자원을 쓰기 위해 대기할 때 발생
하나의 사다리를 상상해 보자.
한 명은 사다리의 위쪽에서 내려오려고 하고 한 명은 사다리의 아래쪽에서 올라가려고 할 때, 서로가 상대방이 비켜줄 때까지 하염없이 기다리고 있는 상황을 deadlock이라고 할 수 있다.
-wiki
deadlock 발생 조건
deadlock이 발생하려면 4가지 조건이 모두 만족해야 한다.
mutual exclusion
- 해당 자원을 한 번에 하나의 프로세스만 이용 가능해야 한다.
hold and wait
- 한 프로세스가 어떠한 자원을 할당받은 상태에서 다른 자원을 할당받기를 기다려야 한다.
nonpreemptive
- 해당 자원을 이용하는 프로세스의 작업이 끝나야만 다른 프로세스가 이용할 수 있다.
circular wait
- resource-allocation graph(자원 할당 그래프)가 원의 형태(cycle)를 그리면 deadlock이 발생할 수도 있다.
resource-allocation graph
- deadlock을 표현하는 도구
- 프로세스는 원으로, 자원은 사각형으로 표현
- 하나의 자원 내에서 사용 가능한 자원 개수에 대해 사각형 내 점으로 표현
- 프로세스(p)가 자원(r) 할당 시 화살표 방향 r → p
- 프로세스(p)가 자원(r)을 기다리고 있을 시 화살표 방향 p → r
- cycle이 존재하지만 deadlock이 발생하지 않는 경우
- p4가 작업을 끝내고 r2 자원 하나를 반납하면 deadlock 발생하지 않음.
- cycle이 없으면 → deadlock 발생 x
- cycle이 있으면 → deadlock 발생 가능성 o
deadlock 해결 방법
- deadlock prevention (예방)
- deadlock avoidance (회피)
- deadlock detection (검출)
3가지 방법이 존재하는데, 모두 이름 그대로다.
예방하거나, deadlock을 피하거나, deadlock이 발생하면 조치하기.
deadlock prevention
deadlock이 발생하려면 반드시 4가지 조건을 충족해야 했음.
== 4가지 조건 중 하나라도 충족하지 않으면 deadlock은 발생하지 않는다.
하나의 조건이라도 만족시키지 않게 자원을 할당해 보자.
mutual exclusion
mutual exclusion은 계속 이야기했듯이, 자원을 한 번에 하나의 프로세스에게만 할당하는 것이다.
자원의 mutual exclusion을 없앤다는 것은 모든 자원을 공유 가능하게 한다는 것인데, 당연히 현실적으로 불가능하다.
본질적으로 공유 불가능한 자원이 존재하기 때문이다.
프린터를 여러 프로세스가 공유한다고 생각하면, 이상한 출력물이 나올 것이다.
hold and wait
hold and wait는 한 프로세스가 자원을 이미 할당받은 상태에서 다른 자원을 기다리는 것이다.
이를 없애면, os는 특정 프로세스에 자원을 모두 할당하거나 모두 할당하지 않는 방식으로 배분한다. 이론적으로 deadlock을 해결할 수 있다.
<단점>
- 자원 활용률이 낮아진다
- 한 프로세스에 자원을 모두 할당해야 함
- 당장 자원이 필요해도 기다려야 할 수밖에 없는 상황
- 많은 자원을 사용하는 프로세스가 불리
- 필요한 프로세스 중 최소 1개가 항상 다른 프로세스에게 할당되어 있어 starvation 야기
nonpreemptive
비선점 조건을 없애면, 현재 자원을 이용 중인 프로세스로부터 자원을 뺏어올 수 있다. CPU 같은 선점하여 사용할 수 있는 자원엔 효과적.
<단점>
- 한번에 하나의 프로세스만 이용 가능한 자원(ex. 프린터)는 비선점 조건을 없앨 수 없음
circular wait
모든 자원에 번호를 붙이고, 오름차순으로 자원을 할당하기.
<단점>
- 모든 자원에 번호를 붙이는 데 드는 오버헤드
- 번호에 따라 특정 자원의 활용률 감소
deadlock avoidance
deadlock 발생 가능성이 있을 시 자원을 할당하지 않아 deadlock을 피함
deadlock avoidance를 위한 개념들
- safe sequence: deadlock이 발생하지 않고 프로세스들에게 자원을 할당할 수 있는 순서
- safe state
- deadlock이 발생하지 않고 모든 프로세스가 자원을 할당받고 종료되는 상태
- safe sequence가 존재하는 상태
- unsafe state: deadlock이 발생할 수 있는 상태
ex. 총 자원이 12라고 가정해 보자.
| 프로세스 | 요구량 | 현재 사용량 |
|---|---|---|
| p1 | 10 | 5 |
| p2 | 4 | 2 |
| p3 | 9 | 2 |
총 자원: 12
할당한 자원(p1, p2, p3 현재 사용량의 합): 9
남은 자원: 3
p2가 필요한 자원 2개를 배분하면
| 프로세스 | 요구량 | 현재 사용량 |
|---|---|---|
| p1 | 10 | 5 |
| p2 | 4 | 4 |
| p3 | 9 | 2 |
총 자원: 12
할당한 자원(p1, p2, p3 현재 사용량의 합): 11
남은 자원: 1
p2는 요구량 전부를 받았고, 실행을 끝내면 자원을 반환
| 프로세스 | 요구량 | 현재 사용량 |
|---|---|---|
| p1 | 10 | 5 |
| p2 | 4 | |
| p3 | 9 | 2 |
총 자원: 12
할당한 자원(p1, p2, p3 현재 사용량의 합): 7
남은 자원: 5
p1에 남은 자원 5개를 배분
| 프로세스 | 요구량 | 현재 사용량 |
|---|---|---|
| p1 | 10 | 10 |
| p2 | 4 | |
| p3 | 9 | 2 |
총 자원: 12
할당한 자원(p1, p2, p3 현재 사용량의 합): 12
남은 자원: 0
p1이 실행을 끝내고 자원을 반환하면
| 프로세스 | 요구량 | 현재 사용량 |
|---|---|---|
| p1 | 10 | |
| p2 | 4 | |
| p3 | 9 | 2 |
총 자원: 12
할당한 자원(p1, p2, p3 현재 사용량의 합): 2
남은 자원: 10
p3에게 필요한 자원 할당하여 실행시킬 수 있음.
p2 → p1 → p3로 자원 배분 시 deadlock이 발생하지 않고 올바르게 작업을 종료할 수 있음.
→ safe sequence
나머지는 unsafe state.
deadlock detection
deadlock의 발생 가능성을 허용하고, deadlock 발생 시 recovery 실시.
process termination
- 모든 프로세스를 종료시키기
- 모든 deadlock 싸이클을 없앨 수 있음
- 많은 프로세스들이 작업 내용을 잃을 가능성
- deadlock이 없어질 때까지 한 프로세스를 종료하기
- deadlock이 없어졌는지 매번 확인하는 과정에서 오버헤드
preemptive
deadlock cycle이 없어질 때까지 프로세스들로부터 자원을 강제로 회수하는 방법
Reference
혼자 공부하는 운영체제
