운영체제 시리즈 9. Deadlock
교착상태라고 부르기도 하며, 일련의 프로세스들이 서로 가진 자원을 요청하며 block된 상태를 의미한다. CPU를 사용하기 위한 자원을 확보해야 하는데, 자신이 확보한 일부 자원은 내어놓지 않고 서로 상대의 자원을 요구하는 상황이라 누구도 사용하지 못하고 계속 대기하는 상태를 뜻한다. 욕심쟁이 단체라 양보도 안하고 그렇다고 그 누구도 사용할 수 없는 느낌이다. 여기서 뜻하는 자원은 하드웨어, 소프트웨어 등을 포함하는 개념이다. IO device, CPU cycle, 메모리공간, semaphore 등을 의미한다.
Deadlock의 발생조건 4가지
- mutual exclusion (상호배제, 상호배타) : 매 순간 하나의 프로세스만 자원 사용 가능하다.
- no preemption (비선점) : 프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗지 않는다.
- hold and wait (보유대기) : 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있다.
- circular wait (순환대기) : 자원을 기다리는 프로세스 간에 사이클이 형성된다.
자원할당 그래프 (Resource-Allocation Graph)
R : 자원, P : 프로세스를 의미, 회색점 : 자원의 갯수를 의미
R -> P : 프로세스가 자원을 가지고 있다.
P -> R : 프로세스가 자원을 요청한다.
1. 사이클이 발생하지 않는다면, 데드락이 아니다.
2. 사이클이 발생한다면,
-1. 만약 자원 타입에 1개만 존재한다면(only one instance per resource type), 데드락이다.
-2 .만약 자원 타입에 여러개 존재한다면(several instances per resource type), 데드락이 될 수 있는 가능성이 있다.
그림의 예시는 2-2의 경우에 해당된다.
Deadlock의 처리방법
- Deadlock prevention : 미연에 방지하는 방법으로 가장 강력하며 4가지 필요조건 중 어느것도 만족하지 않도록 한다.
- Deadlock avoidance : 미연에 방지하는 방법으로 자원요청에 부가정보를 사용하여 deadlock의 가능성이 없는 경우에만 자원을 할당한다.
- Deadlock detection and recovery : 데드락이 감지되면 조치한다.
- Deadlock ignorance : 대부분의 OS가 채택하는 방식이다. deadlock이 자주 발생하지 않는데 처리하는데 오버헤드가 더 크기 때문이다. deadlock이 발생하면 무시하고 그 상황을 종료시켜버린다.
Deadlock Prevention
- mutual exclusion : 이 조건을 충족시키지 않는 방법은 존재하지 않는 듯 하다. 앞에서 동기화를 위해서 상호배타적으로 자원에 접근하기 때문에 그런 듯 하다.
- no preemption : 자원을 빼앗아 올 수 있게 한다. state를 쉽게 save 하고 restore 할 수 있는 자원에서 주로 사용한다.
- hold and wait : 프로세스가 자원을 요청할 때 다른 어떤 자원도 가지고 있지 않아야 한다. 1. 시작시 모든 필요한 자원을 할당받게 하거나, 2. 자원이 필요한 경우 보유자원을 모두 놓고 다시 요청한다.
- circular wait : 모든 자원은 정해진 순서대로만 자원을 할당한다.
이런 방식을 사용하면 사용률과 처리량이 감소되고 비효율적이며 starvation 문제가 발생할 수 있다.
Deadlock Avoidance
자신이 평생 쓸 자원을 미리 선언하고 데드락을 피할 방법을 찾는 방식이다. 자원할당 그래프에서 사이클이 발생하기 전상태까지만 자원을 할당한다. 사이클이 생기는 상황을 만들지 않는다. 자원의 instance가 1개일 때는 자원할당 그래프로 점선(요청가능성)까지 포함하여 사이클이 발생하지 않는지 확인한다. 자원의 instance가 여러개일 때는 아래와 같이 banker's algorithm을 사용한다.
[ Banker's algorithm ]
| snapshot at time T0 | Allocation | Max | Available | Need(Max-Allocation) |
| A B C | A B C | A B C | A B C | |
| P0 | 0 1 0 | 7 5 3 | 3 3 2 | 7 4 3 |
| P1 | 2 0 0 | 3 2 2 | 1 2 2 | |
| P2 | 3 0 2 | 9 0 2 | 6 0 0 | |
| P3 | 2 1 1 | 2 2 2 | 0 1 1 | |
| P4 | 0 0 2 | 4 3 3 | 4 3 1 |
현재 남은 가용에서 자원요청이 들어왔을 때 필요한 자원의 최대갯수(need)를 보고 가용자원(available) 이하인 경우에만 할당해 준다. 위의 예시에서는 현재 P1, P2만 자원을 요청했을 때 자원을 받을 수 있다. 다른 프로세스들은 누군가 자원을 반납하여 available이 자신의 need보다 같거나 커져야 자원을 받을 수 있는 자격이 생긴다. P0가 A자원을 1개만 요청한 경우에도 위와 같은 상황에서는 거절당하게 되는 것이다.
자원이 남아도 혹시 모르는 상황 때문에 안 주는 상당히 보수적인 알고리즘이다.
Deadlock detection and recovery
deadlock avoidance와 유사한 방식을 사용한다. 다만 다른점이 있다면 deadlock avoidance는 미래의 자원요청 가능성(점선)까지 생각하여 작동한다면 여기서는 현재의 요청만 생각하여 deadlock의 가능성을 판단한다.
[ Detection ]
자원당 인스턴스가 1개인 경우, 자원할당 그래프를 wait-for 그래프로 변환한다. 단순히 프로세스간의 관계만 간략하게 나타내는 것이고 여기서 사이클이 발생한다면 deadlock이 발생하는 것으로 본다.
자원당 인스턴스가 여러개인 경우,
| snapshot at time T0 | Allocation | Request | Available |
| A B C | A B C | A B C | |
| P0 | 0 1 0 | 7 5 3 | 0 0 0 |
| P1 | 2 0 0 | 3 2 2 | |
| P2 | 3 0 3 | 9 0 2 | |
| P3 | 2 1 1 | 2 2 2 | |
| P4 | 0 0 2 | 4 3 3 |
여기서는 P0, P2, P3, P1, P4 의 순서로 진행하면 (사용하고나면 자원을 반납하기 때문에 available이 늘어남) 데드락이 발생하지 않는다. 요청하는 가용자원과 반납상황을 확인하면서 시퀀스를 따라갈 수 있는지를 확인하는 방식이다.
[ Recovery ]
데드락이 발생했을 때 대처하는 2가지 방식이 있다.
- Process termination : 데드락에 연루된 모든 프로세스를 죽인다.
- Resource preemption : 데드락에 연루된 프로세스를 하나씩 죽이면서 데드락이 없어지는지 확인한다. (데드락이 없어지는 단계의 프로세스까지만 죽인다.)
Deadlock ignorance
데드락이 발생하지 않는다고 생각하고 아무런 조치를 취하지 않는다. 데드락은 매우 드물게 발생하므로 조치 자체가 더 큰 오버헤드일 수 있기 때문이다. 데드락이 발생하면 시스템이 비정상적 작동을 한다고 느끼고 그 시스템을 죽인다. 대부분의 OS가 채택하여 사용하고 있다.
정리
자신의 자원을 가지고 남의 것을 탐내면서 그 누구도 자원을 사용하지 못하는 상태를 deadlock이라고 한다. deadlock 상황을 발생하지 않게 방지하는 방식, deadlock이 발생했을 때 대처하는 방식등 deadlock 상태와 관련된 메커니즘을 정리해 보았다.
운영체제 시리즈는 반효경 교수님의 운영체제 강의 와 "운영체제와 정보기술의 원리"라는 책을 바탕으로 정리한 내용입니다.