이 글은 KOCW에 공개되어있는 '반효경 교수님'의 운영체제 강의 및 강의 교재 Operation System Concepts(a.k.a 공룡책🦕)의 내용을 기반으로 작성했습니다.
이번 챕터에서는 Deadlock에 관해 정리해보겠습니다
오류가 있다면 댓글로 정정 부탁드립니다
Deadlock
교착상태
- 일련의 프로세스들이 서로가 가진 자원을 기다리며 block 된 상태
- 그래서 아무것도 이루어지지 않고, 오버헤드가 발생하게 된다
다음과 같은 상황에서 발생할 수 있다
1) 하드웨어 자원을 기다리며 데드락에 걸린 상황
- 하나의 tape driver를 읽고 다른 tape drive에 복사하고 싶은 상황
- 시스템에 두개의 tape drive 가 있다
- 프로세스 P1, P2가 각각 하나의 tape drive를 보유한 채 다른 하나를 기다리고 있다
2) 소프트웨어 자원을 기다리며 데드락이 걸리는 경우도 있다
- 세마포어, 공유 데이터와 같은 자원을 기다리며 데드락이 걸릴 수도 있다
Deadlock 발생의 4가지 조건
- Mutual Exclusion(상호 배타적)
- 하나의 프로세스가 자원을 독점적으로 사용한다(여러 개가 동시 사용 불가)
- No preemption
- 프로세스가 자원을 가지고 있을 때, 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않음
- Hold and wait
- 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있음
- Circular wait
- 자원을 기다리는 프로세스간에 사이클이 형성되어야 함
- 프로세스 P0, P1, ... , Pn이 있을 때 Pn-1은 Pn의 자원을 기다리고 Pn은 P0의 자원을 기다려야 한다
| 자원 할당 그래프 (Resource- Allocation Graph)
- 원 : 프로세스, 사각형 : 자원
- 자원 -> 프로세스 : 자원이 프로세스에 속해있다
- 프로세스 -> 자원 : 프로세스가 자원을 요청했으나 아직 획득하지 못했다
- 자원 할당 그래프에서 cycle이 발생하지 않으면 deadlock이 아니다
- cycle이 발생하고 자원이 하나씩 밖에 없다면 deadlock이인 것이다
- cycle이 발생하고 자원이 여러개 있는 상황이라면 deadlock일 수도 있고 아닐 수도 있다
Deadlock의 처리 방법
| Deadlock Prevention(데드락 예방)
- 자원 할당 시 Deadlock의 4가지 필요 조건 중 어느 하나가 만족되지 않도록 하는 것
- Utilization 저하, throughput 감소, starvation 문제 등 자원의 비효율성이 생긴다
1) Mutual Exclusion - 이미 Mutual Exclusion은 막을 수 있는 조건이 아님
2) Hold and Wait - 이미 가진 자원을 보유하며 다른 자원을 기다리기 때문에 생김
- 방법 1 : 프로세스를 시작할 때 모든 필요한 자원을 할당 받게 하는 방법 -> 하지만 자원에 대한 비효율성이 생긴다
- 방법 2 : 필요할 때 보유 자원을 모두 놓고 다시 요청
3) No Preemption
-
자원을 빼앗아올 수 없기 때문에 생김
-
모든 필요한 자원을 얻을 수 있을 때 그 프로세스는 다시 시작된다
-
State를 쉽게 save하고 restore할 수 있는 자원에서 주로 사용(CPU, memory) -> 그래야 자원을 빼앗을 수 있다
-
CPU는 항상 preemption을 할 수 있다(이런 자원은 데드락이 잘 생기지 않는다)
4) Circular Wait
- 필요한 자원들이 꼬리에 꼬리를 물면서 cycle이 형성된 경우를 말한다
- 자원에 순서를 매기고, 낮은 번호를 획득한 경우에만 높은 번호를 획득할 수 있도록 한다
| Deadlock Avoidance(데드락 예방)
- 자원을 할당 했을 때 데드락이 발생할 가능성이 있다면 자원을 배분해주지 않는 것
- 가장 단순하고 일반적인 모델은 프로세스들이 필요로 하는 각 자원별 최대 사용량을 미리 선언하도록 하는 방법
1) safe state
- 시스템 내의 프로세스들에 대한 safe sequence 가 존재하는 상태
2) safe sequence
- 프로세스의 sequence(P1, P2, ....Pn) 가 safe 하려면 Pi의 자원 요청이 "가용자원 + 모든 Pj(j < i)의 보유자원" 에 의해 충족되어야 함
- Pi의 자원요청이 충족될 수 없으면 Pi 모든 Pj(i 이전의 프로세스)가 종료될 때까지 대기
- Pi-1이 종료 -> Pi의 자원 요청 수행
일단 safe state에 있다면 dead lock이 되지 않지만, unsafe state에 있이면 deadlock의 가능성이 있다
그리고 deadlock avoidance는 unsafe state에 들어가는 것을 방지한다
| Resource Allocaltion Graph algorithm
instance 가 하나라면 자원 할당 그래프를 이용해 avoidance를 한다
- 점선(claim edge) : 프로세스 P가 자원(R)에 미래에 요청할 수 있음을 나타낸다
- 실선(request edge) : 프로세스가 해당 자원을 요청할 시 실선으로 바뀐다
- resource가 release 되면 다시 점선(claim edge)로 바뀐다
- cycle이 생기지 않는 경우에만 요청 자원을 할당한다(실선으로 변함)
- cycle 생성 여부 조사 시 프로세스의 수가 n일 때 O(n^2)의 시간이 걸린다
| Banker's Algorithm
instance가 여러개라면 Banker's Algorithm 을 이용해 avoidance를 한다
자원 요청 시 safe 상태를 유지할 경우에만 할당하도록 한다
가정
- 모든 프로세스는 자원의 최대 사용량을 미리 명시한다
- 프로세스가 요청 자원을 모두 할당받은 경우 유한 시간 안에 이들 자원을 다시 반납한다
방법
- 총 요청 자원의 수가 가용 자원의 수보다 적은 프로세스를 선택(그런 프로세스가 없으면 unsafe) 해서 자원을 할당
- 할당받은 프로세스가 종료되면 모든 자원을 반납하고, 모든 프로세스가 종료될 때까지 이러한 과정을 반복한다
- 뱅커스 알고리즘은 보수적이기 때문에 최대 요청을 할 것을 가정하고 자원을 분배하지만, 최대로 사용한다는 것이 언제 저 자원을 사용하는지를 알려주는 것은 아니다
예시
- Need : 추가로 요청할 수 있는 양
- Need와 Available(가용 자원)을 비교하여 만족이 가능하면 그냥 준다
- 위 예시에서는 sequence P1->P3->P4->P2->P0 가 존재하므로 시스템은 safe state
| Deadlock Detection and recovery(데드락 탐지)
- Deadlock 발생은 허용하되 그에 대한 detection 루틴을 두어 deadlock 발견시 recover
| Detaction
Wait-for graph 알고리즘
Resource type 당 single instance 인 경우 사용
- 자원 할당 그래프의 변형으로, 프로세스만으로 node를 구성한다
- Pi가 가지고 있는 자원을 Pk가 기다리는 경우 Pk -> Pi
- wait-for graph에 사이클이 존재하는지 주기적으로 조사
- 그래프와 표 방식으로 표현할 수 있으며, 표 형식이 더 정확하다
예시
1) 표
- Request : 현재 실제로 요청한 자원량
- sequence P0 -> P2 -> P3 -> P1 ->P4 가 존재한다
2) 그래프(wait-for graph)
- 자원의 최대 사용량을 미리 알릴 필요가 없기 때문에 그래프에 점선이 없음
- process가 n개일 때 O(n^2)의 오버헤드가 든다
- process가 n개 있을 때 화살표를 따라가게 되고, n개당 최대 n-1의 화살표를 가진다
- n(n-1)
| Recover
1) Process Terminate
데드락과 연관된 프로세스를 죽이는 방법
- 데드락에 연루된 프로세스를 한번에 죽이는 것
- 데드락에 연루된 프로세스를 하나씩 죽이는 것(데드락이 없어질 때까지)
2) Resource Preemption
데드락 이후 자원을 들고오는 방법
- 비용을 최소화 하는 victim을 선정
- safe state로 rollback해서 process를 재시작하게 된다
- 데드락을 없앴는데 같은 victim을 계속 선정하면 같은 패턴으로 데드락이 생길 수 있다
- 비용만 최소화하면 starvation이 발생할 수 있기 때문에 cost factor에 rollback 횟수도 같이 고려하게 된다
| Deadlock Ignorance(데드락 무시)
- Deadlock 을 시스템이 책임지지 않음
- 데드락은 빈번히 발생하지 않기 때문에 미연에 방지하기 위해 오버헤드를 많이 발생시키는 것은 매우 불합리
- UNIX를 포함한 대부분의 OS가 채택
- 운영체제가 관여를 안하면 사람이 프로세스를 죽이는 방법을 선택
