운영체제 - 교착 상태(Deadlock)
What is Deadlock? How to resolve Deadlock?
교착 상태(Deadlock)란?
교착 상태란 둘 이상의 프로세스가 자원을 점유한 상태에서 서로 다른 프로세스에서 점유하고 있는 자원을 요구하며, 서로가 작업을 끝나기만을 기다리며, 무한 대기 상태에 빠진 상황을 말한다. 예를들어, P1은 P2가 들고 있는 자원의 락이 풀리기를 기다리고 있고 P2는 P1이 들고 있는 자원의 락이 풀리기를 기다리고 있는 상황이다.
교착 상태 발생조건
아래 4가지 조건을 모두 만족하는 경우 교착 상태가 발생할 가능성이 있다.
- 상호 배제(Mutual Exclusion): 한 번에 한 프로세스만 공유 자원을 사용할 수 있다.
- 점유 대기(Hold and Wait): 자원을 최소한 하나 가진상태에서 다른 자원을 기다린다.
- 비선점(Non-Preemption): 한 프로세스가 다른 프로세스의 자원 접근 권한을 강제로 취소할 수 없다.
- 순환 대기(Circular Wait): 두 개 이상의 프로세스가 자원 접근을 기다리는데, 관계에 사이클이 존재한다.
교착 상태 해결법
교착 상태 해결법은 크게 3가지로 나눌 수 있다.
- 데드락 발생하지 않도록 예방(Prevention)하기
- 데드락이 발생할 수 있지만 적절히 회피(Avoidance)하기
- 데드락이 발생하면 탐지(Detection)하여, 데드락에서 회복(Recovery)하기
교착 상태 예방(Prevention)하기
교착 상태가 발생하지 않도록 사전에 예방하는 방법으로 교착상태 발생조건 4가지 조건중 하나를 예방(부정)함으로 써 교착상태를 예방하는 방법입니다.
- 상호 배제 부정: 한 번에 여러 프로세스 공유 자원을 사용할 수 있다.
- 점유 대기 부정: 프로세스가 실행되기 전 필요한 모든 자원을 할당하여 프로세스 대기를 없애거나, 자원이 점유되지 않은 상태에서만 자원 요청을 받도록 한다.
- 비선점 부정: 다른 프로세스에게 자원 접근을 강제로 취소하게 한다.
- 순환 대기 부정: 사이클이 존재하지 않게 일정한 방향으로 자원을 요구할 수 있게 한다.
하지만 이렇게 각 조건을 하나씩 부정하여 예방하게 되면 시스템의 처리량이나 자원의 효율성을 떨어뜨릴 수 있다.
교착 상태 회피(Avoidance)하기
교착상태가 발생할 수 있는 가능성이 있는 불완전 상태(Unsafe Sate)에서는 자원 할당을 하지 않고 안전한 상태(Safe State)에서만 자원 요청을 허락하는 방법
안정 상태(Safe State): 프로세스들이 요청하는 모든 자원을 데드락이 일어나지 않게 할당할 수 있는 상황, 안전 순서(Safe Sequence)가 있는 경우
안전 순서(Safe Sequence): 교착상태를 일으키지 않고 자원을 할당하는 순서
불안정 상태(Unsafe State): 안정 상태가 아닌 상황으로, 교착상태 발생할 가능성이 있는 상황
회피 알고리즘으로 가장 유명한 은행원 알고리즘을 알아보자
은행원 알고리즘
다익스트라가 제안한 방법으로, 자원을 할당하기 전에 모든 자원의 최대 할당량을 이용해 시뮬레이션하여 안정 상태(Safe State)인지 여부를 검사하여 교착 상태 가능성을 미리 알아보는 것이다.
예를 들어 처음에 시스템이 총 15개의 자원을 가지고 있다고 가정해보자.
| 최대 자원 요청량 | 할당 중인 자원량 | 남은 필요한 자원량 | |
|---|---|---|---|
| P0 | 11 | 7 | 4 |
| P1 | 6 | 3 | 3 |
| P2 | 10 | 2 | 8 |
현재 할당 중인 자원량은 7+3+3 으로 12개이다. 그러면 이제 사용 가능한 자원량은 15 - 12 = 3이 된다. 여기서 어떤 순서로 할당하냐에 따라 Safe Sequence인지 아닌지 결정된다.
- 먼저 P1에 사용 가능한 자원 3개를 할당 (사용 가능한 자원: 3 - 3 = 0)
- P1의 작업이 끝나면 할당된 자원 6개 반납 (사용 가능한 자원: 0 + 6 = 6)
- P0에 사용 가능한 자원을 4개 할당 (사용 가능한 자원: 6 - 4 = 2)
- P0의 작업이 끝나고 할당된 자원 11개 반납 (사용 가능한 자원: 2 + 11 = 13)
- P2에 사용 가능한 자원 8개 할당 (사용 가능한 자원: 13 - 8 = 5)
- p2 작업이 끝나고 나면 할당된 자원 10개 반납 (사용 가능한 자원: 5 + 10 = 15)
위 순서 처럼 P1 -> P0 -> P2 순서로 할당하게 되면 Safe Sequence를 만족하게 된다.
그러나 은행원 알고리즘 같은 경우 미리 자원의 최대 요청량을 알아야 되고, 할당할 수 있는 자원수가 일정해야 되는 등 제약조건이 많아 실제로 복잡한 환경에서 사용하기 어렵다.
교착 상태 탐지(Detection), 회복(Recovery)하기
교착 상태 탐지 알고리즘이나 자원 할당 그래프를 통해 교착 상태가 발생했는지 탐지하고, 교착 상태가 탐지되었다면 회복 기법을 통해 복구합니다.
회복(Recovery) 기법
- 프로세스 종료: 교착 상태에 있는 프로세스를 종료하는 방법으로 모든 프로세스를 종료 시키는 방법과, 하나씩 종료해가는 방법이 있다.
- 자원 선점: 프로세스에 할당된 자원을 선점해서, 교착 상태가 해결될 때까지 그 자원을 다른 프로세스에 할당해 주는 방법
*틀린 부분이 있으면 언제든지 말씀해 주시면 공부해서 수정하겠습니다.
