1. Deadlock (교착 상태)
데드락이란 일련의 프로세스들이 서로가 가진 자원을 기다리면서 잠들어있는 상태를 말합니다. 위의 그림에서 자동차는 프로세스, 도로는 자원으로 생각하면 이해가 쉬운데요. 자동차(프로세스)들이 각각의 도로(자원)를 점유한 상태에서 다른 자동차(프로세스)들이 사용하고 있는 도로(자원)를 사용하기 위해 대기하고 있지만, 진행이 더 이상 되질 않는 상태를 말합니다.
다시 말해, 두 개 이상의 프로세스가 자원을 점유한 상태에서, 다른 프로세스가 점유하고 있는 자원을 요구하여 서로의 작업이 끝나기만을 기다리며 영원히 끝나지 않는 상황입니다.
프로세스가 자원을 사용하는 절차는 크게 4단계로 자원 요청 -> 자원 획득-> 자원 사용 -> 자원 반납의 단계를 거칩니다. 데드락을 각각의 단계에서 구분해 어떻게 데드락을 막을 수 있을지에 대해서 살펴보겠습니다. 그 이전에 데드락이 발생하는 조건 4가지를 알아야 합니다.
2. Deadlock 발생의 4가지 조건
데드락이 발생하려면 아래의 4가지 조건을 모두 만족해야 합니다.
(1) Mutual exclusion (상호 배제)
매 순간 하나의 프로세스만이 자원을 사용할 수 있는 것입니다. 만약 하나의 자원에 여러 프로세스가 같이 쓸 수 있다면 데드락에 걸릴 수 없습니다.
(2) No preemption (비선점)
프로세스가 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않는 것입니다. 데드락은 가진 자원을 빼앗기지 않으면서 추가적인 자원을 요청하기 때문에 생기는 상황입니다. 만약 자원을 빼앗을 수 있다면 데드락은 발생하지 않습니다.
(3) Hold and Wait (점유 대기)
자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있는 것을 말합니다.
(4) Circular wait (순환 대기)
자원을 기다리는 프로세스 간에 사이클이 형성되는 것을 말합니다. 프로세스의 자원 점유와 점유된 자원의 요구 관계가 원형을 이루며 대기하는 것을 말합니다.
3. 자원 할당 그래프
데드락이 발생되었는지를 알아보기 위해 보통 자원 할당 그래프를 그려서 확인하게 됩니다.
그림에서 T 동그라미는 프로세스를 나타내고, R 사각형은 자원을 나타냅니다. 사각형 안의 작은 점들은 자원의 수를 의미합니다. 그리고 프로세스와 자원 사이에는 화살표가 있습니다. 화살표가 자원에서 프로세스로 향하는 화살표는 이 자원이 프로세스에 속해있다는 것을 알려주고, 프로세스에서 자원으로 향하는 화살표는 프로세스가 이 자원을 요청했다는 것을 의미합니다. 요청만 하고 아직 얻지는 못한 상태입니다.
그럼 이 그림에서 데드락인지 아닌지를 어떻게 확인할 수 있을까요?
우선 그래프에서 알 수 있는 방법은 그래프 안에서 사이클이 없다면 데드락이 아닙니다.
위 그래프를 보시면 R2 -> T2-> R3 -> T3-> R2로 사이클이 형성된 것이 보입니다. 이런 사이클은 데드락이 발생할 가능성이 있습니다.
만약 자원당 인스턴스가 하나밖에 없다면 사이클은 곧 데드락을 의미합니다. 위 그래프에서는 데드락이 발생합니다.
위 그래프에서는 사이클이 보이긴 합니다. 하지만 자원의 개수가 2개씩 할당되어 있기 때문에 데드락은 아닙니다.
4. Deadlock 처리 방법
데드락을 처리하는 방법으로 네 가지 방법을 살펴보겠습니다.
- Prevention (예방) : 자원 할당 시 Deadlock의 4가지 필요조건 중 하나가 만족되지 않도록 하는 것
- Avoidance (회피) : 자원 요청에 대한 부가적인 정보를 이용해 deadlock의 가능성이 없는 경우에만 자원 할당
- Detection and Recovery (탐지 및 회복) : 데드락 발생은 허용하지만, 그에 대한 detection 루틴을 두어 데드락 발견 시 회복
- Ignorance (무시) : 데드락을 시스템이 책임지지 않음.
위의 두 가지 방법은 데드락이 생기지 않게 미연에 방지하는 방법이고, 아래의 두 가지 방법은 데드락이 생기도록 놔두는 것입니다.
특히 Ignorance는 방법이라기 보단 데드락에 대해 아무것도 하지 않는 것인데 현대의 운영체제들은 대부분 Ignorance을 택하고 있습니다. 데드락이 생기든 말든 관여하지 않고, 프로세스를 돌리다 이상이 생기면 사용자가 프로세스를 종료한다던지 하는 방법으로 해결을 하는 것입니다.
왜냐하면 데드락은 빈번히 발생하는 이벤트가 아니기 때문에 그런 것을 미연에 방지하고자 오버헤드를 들이는 것이 현대적인 시스템에서는 비효율적이기 때문입니다.
위 네 가지 방법을 구체적으로 살펴보겠습니다.
(1) Deadlock Prevention
Prevention은 가장 강력한 데드락 방지 방법입니다. 데드락 Prevention은 데드락이 발생하는 4가지 조건 중에 어느 하나를 원천적으로 차단하여 데드락에 들어가지 못하게 하는 방법입니다.
Mutual Exclusion
데드락의 네 가지 발생 조건 중 Mutual Exclusion (상호 배제)는 개발자가 막을 수 있는 조건이 아닙니다. 만약 자원을 한 번에 여러 프로세스가 쓸 수 있다면 애초에 데드락이 성립하지 않습니다.
Hold and Wait
Hold and Wait은 내가 이미 가진 자원은 보유하고 있으면서 다른 자원을 요청했기 때문에 생기는 것입니다. 그래서 이 조건을 없애려면 자원을 기다려야 되는 상황에서는 자원을 보유하고 있지 않으면 됩니다. 이것을 두 가지로 생각해 볼 수 있습니다.
우선 첫 번째는 프로세스가 실행될 때, 중간에 추가로 필요한 자원이 없을 때 자원을 모두 할당받게 합니다. 처음부터 전부 hold 하고 시작하기 때문에 wait 할 일이 없어서 Deadlock이 생기지 않습니다. 그런 다음 작업을 끝나고 프로세스가 종료될 때 자원을 반납합니다. 하지만 이 방법은 매 시점마다 필요로 하는 자원이 다른데도 불구하고 모든 자원을 보유하고 있기에 자원에 대한 비효율성이 큽니다.
두 번째는 자원이 필요할 때 할당받는 방법입니다. 만약 어떤 자원을 Hold 하고 있는데 다른 자원을 기다려야 하는 상황이 된다면 이미 Hold 한 자원도 다 반환을 하고 기다립니다.
즉 필요한 자원을 전부 다 얻거나, 얻지 못하게 합니다.
No preemtion
No Preemption은 다른 프로세스가 가진 자원을 빼앗아올 수 없기 때문에 데드락이 생기는 이유였습니다. 그래서 자원을 preemtion 하게 한다면 데드락에 걸리지 않게 됩니다.
이전 CPU 관련 포스팅에서, CPU 같은 자원은 Preemtive 스케줄링을 주로 사용한다고 언급했습니다. 이 스케줄링에서 타이머 인터럽트를 통해 CPU는 Preemption을 했습니다. 이런 자원은 데드락에 걸리지 않습니다.
그래서 CPU와 메모리와 같은 자원은 자원을 언제든 뺏아올 수 있는데, 이는 현재 자원 상태를 저장할 수 있는 자원이기 때문입니다. 그래서 빼앗겼다가 다시 돌려받아도 그다음 지점부터 실행하는 것이 가능합니다.
이러한 자원들은 Preemption을 통해 데드락을 막을 수 있습니다. 하지만 그런 자원들이 아니라면 이 방법을 사용하기가 어렵습니다.
Circular Wait
Circular wait은 모든 자원 유형에서 할당 순서를 정해서, 정해진 순서로만 자원을 할당하는 방법이 있습니다. 원천적으로 데드락을 막을 수는 있지만 자원에 대한 이용률이 낮아지고, starvation 문제가 생겨 전체 시스템이 나빠지는 문제가 발생할 수 있습니다. 매우 적게 발생하는 데드락을 막기 위해 제약 조건을 많이 걸어놓는다면 비효율성이 큽니다.
(2) Deadlock Avoidance
프로세스가 시작될 때 이 프로세스가 쓸 자원의 최대량을 미리 알고 있다고 가정하고 데드락을 피하는 방법입니다. 모든 작업에서 사용할 자원의 양을 알고 있기 때문에, 어떤 프로세스가 자원을 요청했을 때 그 자원을 주게 되면 생길 데드락 발생 가능성을 판단합니다. 가능성이 있다고 판단되면 자원이 있는데도 자원을 내어주지 않습니다.
시스템이 safe 영역에 있다면 데드락의 가능성이 없는 것이고, unsafe 영역에 있다면 데드락의 가능성이 있는 것입니다. 데드락 avoidance는 데드락이 unsafe state에 있는 것을 보장합니다.
데드락 avoidance는 두 가지 알고리즘이 있습니다. 자원의 인스턴스가 한 개씩밖에 없을 경우에는 자원 할당 그래프를 보고 알 수 있고, 자원의 인스턴스가 여러 개라면 banker's 알고리즘을 통해 알 수 있습니다.
1. Resource Allocation Graph algorithm (자원 할당 그래프 알고리즘)
이전의 자원 할당 그래프에서 점선 화살표가 추가된 것입니다. 점선 화살표는 항상 프로세스로부터 자원으로 가는 방향만 있고, 평생에 한 번은 해당 자원을 사용할 일이 있다는 것입니다. 프로세스가 해당 자원을 요청하게 되면 실선으로 바뀌게 됩니다.
왼쪽 그림은 프로세스 1이 1번 자원을 가지고 있고, 프로세스 2는 1번 자원을 요청한 상태입니다. 이때 2번 자원은 아무도 갖고 있지 않기 때문에 요청한 프로세스에게 줄 수 있습니다.
하지만 오른쪽 그림은 점선을 포함해 사이클이 만들어져 데드락의 가능성이 있습니다. 데드락의 가능성이 있는 자원 요청에 대해서는 애초부터 받아들여지지 않고 피하기 때문에 프로세스 2가 2번 자원을 요청하면 자원을 주지 않습니다. 프로세스 1번이 2번 자원을 요청하는 경우는 데드락의 가능성이 없어 자원 할당이 가능합니다.
즉 데드락의 발생 가능성이 있는 요청에 대해서는 자원 요청을 받아들이지 않고, 피하는 방법입니다.
2. Banker's Algorithm
자원 당 인스턴스가 여러 개 있는 경우에는 Banker's 알고리즘을 통해 데드락을 막습니다. Banker's 알고리즘은 프로세스들이 자원을 요청하면 그 요청을 받아들일 것인지, 아니면 받아들이지 않을 것인지만 결정합니다.
Banker's 알고리즘은 프로세스들이 최대 요청을 할 것이라고 가정한 후, 그 최대 요청이 현재 가용 자원을 통해 충족하는지를 확인합니다. 충족이 되면 어떤 요청이든 요청을 받아들이고, 충족이 되지 않으면 받아들이지 않습니다.
현재 가용자원(Available)과 각 프로세스들이 작업을 완료하기 위해 필요한 자원(Need)을 비교하여 당장 작업을 마칠 수 있는 프로세스부터 자원을 할당해, 그 프로세스가 작업을 완료하고 반환하는 자원을 다른 프로세스에게 할당합니다. 아래의 그림을 통해 살펴보겠습니다.
위 그림에서는 5개의 프로세스, 3 종류의 자원이 있고 자원은 종류 별로 각각 10개(A), 5개(B), 7개(C)가 있습니다. 프로세스 0은 B 자원을 1개, 프로세스 1은 A자원을 2개.. 이런 식으로 자원을 가지고 있는 상황입니다. Max는 프로세스가 시작할 때 정해놓는 최대 사용 자원입니다. Need는 최대 요청 가능한 양에서 현재 할당된 양을 뺀 값으로, 추가 요청할 수 있는 양입니다.
그래서 Need가 available보다 적은 지를 판단합니다.
댱장 작업을 마칠 수 있는 프로세스 P1에 자원이 할당되어 있습니다. 이후 작업이 끝난 프로세스 P1는 자원을 반납하고 이와 같은 방식으로 프로세스 1 -> 3 -> 4 -> 0 -> 2 순으로 작업이 진행됩니다.
(3) Deadlock Detection and recovery (교착 상태 탐지 및 복구)
데드락 발생은 허용하지만, 그에 대한 detection 루틴을 두어 데드락 발견 시 회복하는 방법입니다. 위의 데드락 회피와 마찬가지로 자원이 하나일 때는 자원 할당 그래프로, 여러 개일 때는 banker's 알고리즘과 유사한 방법을 활용합니다.
1. 자원당 인스턴스가 하나일 때 데드락을 검사하는 법 : 자원 할당 그래프
자원할당 그래프에서 사이클은 곧 데드락을 의미합니다. 우측의 자원이 그려지지 않은 그래프는 wait for graph라고 하는데, 자원할당 그래프를 변형해 프로세스만으로 노드가 구성한 것입니다. Wait-for-Graph 알고리즘을 통해 사이클이 존재하는지 여부를 주기적으로 조사합니다. 여기서 사이클을 찾는 오버헤드는 O(n^2)입니다.(노드가 n개면 화살표의 최대 개수는 n - 1 이므로 n^2-n의 시간 복잡도가 도출)
2. 자원당 인스턴스가 여러 개일 때 데드락 검사하는 법
데드락 감지는 어떤 프로세스가 자원을 최대로 얼마나 요청할지 미리 알 필요가 없고 프로세스가 자원을 요청하면 자원을 할당합니다. 대신 현재 요청한 자원이 없는 프로세스들이 갖고 있는 자원들은 반납한다고 가정합니다.
위 그림에서는 5개의 프로세스, 3 종류의 자원이 있고 자원은 종류 별로 각각 7개(A), 2개(B), 6개(C)가 있습니다. 데드락 회피에서의 그림과 같이, 프로세스 0은 B 자원을 1개, 프로세스 1은 A자원을 2개.. 이런 식으로 자원을 가지고 있습니다. 프로세스 0과 프로세스 2는 요청한 자원이 없기 때문에, 낙관적으로 보면 프로세스 0과 프로세스 2는 자원을 반납할 것이라고 가정합니다. 그럼 가용 자원은 A는 3개, B는 1개, C는 3개가 됩니다. 이 반납한 자원을 다른 프로세스에게 줄 수 있습니다. 이런 식으로 자원들을 처리 가능한 프로세스들에게 자원을 주고받는 과정을 체크합니다.
위 방법들로 데드락을 감지하다가 데드락이 발견되면 Recovery를 실행해야 합니다. Recovery는 크게 두 가지 방법이 있습니다.
하나는 데드락에 연루된 프로세스들을 모두 종료시키거나, 데드락이 없어질 때까지 데드락과 연루된 프로세스들을 하나씩 종료시키는 방법입니다.
두 번째는 데드락에 연루된 프로세스들의 자원을 빼앗는 방법입니다. 어느 프로세스에게 자원을 빼앗을지 정한 다음, 그 프로세스 자원을 빼앗아 데드락을 없앱니다. Safe state로 되돌려 재시작하면 데드락이 없어질 수는 있지만, 똑같은 패턴이 반복되어 데드락이 생길 가능성이 있습니다. 어떤 프로세스에게서 자원을 빼앗았는데 다른 프로세스가 갖기 전 데드락을 유발한 프로세스가 또 해당 자원을 요청해 가져가면 데드락이 생길 수 있는 것입니다. 그래서 자원을 빼앗은 다음에는 패턴을 조금씩 바꿔서 실행하는 것이 데드락이 생길 가능성이 적습니다.
(4) Deadlock Ignorance
방법이라기보다는 말 그대로 무시하는 것입니다. 데드락이 일어나지 않는다고 가정해 아무런 조치를 취하지 않는 것입니다. 데드락은 드물게 발생하기 때문에 데드락에 대한 조치가 더 큰 오버헤드일 수 있습니다. 데드락을 감시하는 것도, 데드락이 발생하지 않게 조치를 하는 것도 자원을 비효율적으로 쓰는 것입니다.
만약 데드락이 발생한다면 시스템이 비정상적으로 작동하는 것을 사람이 인지하고 직접 프로세스를 죽이는 방법으로 해결합니다. UNIX, Windows 등 대부분의 범용 OS가 이 방식을 채택합니다.
참고자료
[KOCW 이화여대 반효경 교수님 - Deadlock]
https://core.ewha.ac.kr/publicview/C0101020140411151510275738?vmode=f
반효경 [운영체제] 16. Deadlock 1
설명이 없습니다.
core.ewha.ac.kr
[ Operating System Concepts - Abraham Silberschatz ]
https://www.yes24.com/Product/Goods/89496122
운영체제 - 예스24
운영체제
www.yes24.com
