프로세스는 실행을 위해 여러 자원을 필요로 합니다. 운영체제는 프로세스가 요구하는 자원을 적절히 분배해줍니다.
데드락(DeadLock)은 두 개 이상의 프로세스나 스레드가 서로 자원을 얻지 못해서 다음 처리를 하지 못하는 상태입니다. 즉, 무한히 다음 자원을 기다리게 되는 상태를 의미합니다.
데드락 발생 조건
- Mutual Exclusion (상호 배제)
자원은 한 번에 한 프로세스만 사용 가능 - Hola and Wait (점유 대기)
최소한 하나의 자원을 점유하면서 다른 프로세스에 할당되어 사용하고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 존재 - No Preemption (비선점)
다른 프로세스의 할당된 자원은 사용이 끝날 때까지 빼앗기 불가능 - Circular Wait (순환 대기)
프로세스의 집합에서 순환 형태로 자원을 대기
데드락 처리
데드락 예방
데드락 발생 조건 네 가지 중 최소 한 가지를 만족시키지 않도록 하는 것입니다.
1. Mutual Exclusion (상호 배제)
자원을 공유 가능하게 만들어야 합니다. 하지만 현실적으로 거의 불가능합니다.
2. Hola and Wait (점유 대기)
프로세스 실행에 필요한 모든 자원을 한꺼번에 요구하고 허용할 때까지 작업을 보류해서 나중에 다른 자원을 점유하기 위한 대기 조건을 성립하지 않게 합니다. 하지만 자원의 활용률을 저하시키고 기아(Starvation) 현상이 발생하는 단점이 있습니다.
3. No Preemption (비선점)
선점이 가능하게 합니다. 대부분의 자원에게는 불가능합니다.
4. Circular Wait (순환 대기)
모든 자원에 번호를 부여하여 순서대로 자원을 요청합니다. 하지만 자원의 활용률을 저하시키는 단점이 있습니다.
데드락 예방 방법들은 불가능하거나 단점을 가지고 있습니다.
데드락 회피
시스템의 프로세스들이 요청하는 모든 자원을 데드락을 발생시키지 않으면서도 차례로 모두에게 할당해줄 수 있다면 안정 상태(Safe State)에 있다고 합니다.
다음과 같이 특정한 순서로 프로세스들에게 자원을 할당, 실행 및 종료 등의 작업을 할 때 데드락이 발생하지 않는 순서를 안전 순서(Safe Sequence)라고 합니다.
불안정 상태는 안정 상태가 아닌 상황입니다. 데드락 발생 가능성이 있다는 의미입니다. 데드락은 불안정 상태의 부분집합이라고 할 수 있습니다.
회피 알고리즘은 자원을 할당한 후에도 시스템이 항상 안정 상태에 있을 수 있도록 할당을 허용하는 것이 기본입니다.
은행원 알고리즘
다익스트라가 제안한 기법으로 어떤 자원의 할당을 허용하는지에 관한 여부를 결정하기 전에 미리 결정된 모드 자원들의 최대 가능한 할당량을 가지고 시뮬레이션해서 Safe State가 될 수 있는지 여부를 검사합니다. 대기중인 다른 프로세스들의 활동에 대한 데드락 가능성을 미리 검사하는 것입니다.
예시를 들어보도록 하겠습니다. 총 12개의 자원이 있다고 가정합니다.
| Max | Allocation | Need | |
|---|---|---|---|
| P0 | 10 | 5 | 5 |
| P1 | 4 | 2 | 2 |
| P2 | 9 | 2 | 7 |
P0 ~ P2는 프로세스, Max는 각 프로세스마다 최대 자원 요청량, Allocation은 현재 프로세스에 할당중인 자원의 양, Need는 남은 필요한 자원 양(Max - Allocation)입니다.
현재 할당된 자원의 합은 5+2+2 = 9개입니다. 현재 사용 가능한 자원은 12-9 = 3개입니다.
P1 -> P0 -> P2 순서면 Safe Sequence를 만족합니다.
- P1은 2개를 추가로 할당받기를 기다로기 있습니다. 2개를 할당해서 P1의 실행이 끝나면 기존 할당 자원+추가 할당 자원 4개를 반납합니다. 사용 가능 자원이 5개가 됩니다.
- P0는 5개를 추가로 할당받기를 기다리고 있습니다. 5개를 할당해서 P0의 실행이 끝나면 기존 할당 자원+추가 할당 자원 10개를 반납합니다. 사용 가능 자원이 10개가 됩니다.
- 마지막으로 P2에게 7개를 할당해주면 P2도 실행이 끝나게 됩니다.
다음과 같이 자원 할당량을 사전에 파악해서 데드락을 회피할 수 있습니다.
P2의 Allocation이 1개 늘어난다면 처음 사용 가능한 자원이 2개였을 것입니다. 이 상황에 P1의 실행을 끝낸다고 쳐도 결국 사용 가능한 자원이 4개뿐이므로 P0나 P2의 Need를 해결할 수가 없습니다.
은행원 알고리즘의 경우, 미리 최대 자원 요구량을 파악해야 하고 할당할 수 있는 자원 수가 일정해야 하는 등 제약조건이 많고 자원 이용도 하락 등 단점이 존재합니다.
데드락 탐지 및 회복
데드락이 발생한 후에 데드락을 탐지하고 회복하는 알고리즘을사용합니다.
데드락 탐지
- 은행원 알고리즘과 비슷한 방식으로 현재 시스템의 자원 할당 상태를 보고 파악합니다.
- 자원 할당 그래프를 통해 탐지하는 방식도 있습니다.
데드락 회복
- 메모리의 상태를 주기적으로 메모리에 저장해놓고 데드락이 발생하면 이전 상태로 되돌리는 방법이 있습니다.
- 일부 프로세스를 강제로 종료하거나 자원을 강제로 선점하여 프로세스에 할당해주는 방법도 있습니다.
데드락 자체가 매우 드문 현상이기 때문에 자유롭게 자원을 사용하다가 데드락이 발생하면 정상적인 상태로 복구하는 것이 좋을 수도 있습니다.
하지만 복구가 제대로 되지 않을 수도 있고 탐지를 위해 추가적인 오버헤드가 발생합니다.
데드락 무시
데드락 발생 조건을 모두 만족하더라도 데드락이 무조건 발생하는 것은 아닙니다. 데드락 자체가 굉장히 드문 현상이기 때문에 데드락에 대해 대응하는 것이 비효율적인 환경도 존재합니다. 그런 환경에서는 데드락에 대해 아무 조치도 하지 않기도 합니다.
대부분의 운영체제에서도 데드락을 무시한다고 합니다.
