OS는 deadlock을 해결하기 위해 크게 3가지 방법을 사용하는데 이는 예방, 회피, 검출 후 회복 이다.
애초에 deadlock이 일어나지 않도록 deadlock의 발생 조건에 부합하지 않도록 자원을 분배하여 예방할 수 있고, deadlock이 발생하지 않도록 조금씩 할당하다가 deadlock의 위험이 있다면 할당하지 않는 방식으로 회피할 수 있으며 자원을 제약없이 할당하다가 deadlock이 검출되면 deadlock을 회복하는 방법을 취할 수도 있다.
deadlock 예방
deadlock을 예방하는 방법은 deadlock의 조건 4가지 중 하나를 충족하지 못하게 하면 된다.
-
자원의 상호 배제를 없애는 경우
모든 자원을 공유 가능하게 만든다.
다만 이 방식대로라면 이론적으로는 deadlock을 없애지만 현실적으로는 모든 자원의 상호배제를 없앨 수는 없으므로 이 방식은 현실적이지 못하다. -
점유와 대기를 없애는 경우
식사하는 철학자 문제의 식기를 기다리지 못하게 금지하는 경우와 같다.
식기를 둘 다 들거나 아예 못들게 하는 경우라고 할 수 있는데, OS가 점유와 대기를 없애면 특정 process에 자원을 모두 할당하거나, 아예 할당하지 않는 방식으로 배분한다.
이 방식도 이론적으로는 deadlock을 해결하지만 큰 단점이 있는데, 우선 자원 활용률이 낮아진다는 점이다.
점유와 대기를 금지하면 한 process에 필요한 자원을 몰아주고, 그 다음 다른 process에 필요한 자원을 몰아줘야 한다. 이는 당장 자원이 필요해도 기다릴 수 밖에 없는 process와 사용되지 않으면서 오래 할당되는 자원을 다수 양산하기 때문에 자원의 활용률이 낮아진다고 할 수 있다.
그리고 많은 자원을 사용하는 process는 자원을 적게 사용하는 process에 비해 동시에 자원을 사용할 타이밍을 확보하기가 어렵고, 결국 자원을 필요로 하는 process가 무한정 기다리게 되는 starvation이 일어날 확률이 높다. -
비선점 조건을 없애는 경우
비선점 조건을 없애면 자원을 이용 중인 process로부터 해당 자원을 빼앗는 것이 가능해지는데, 이론상 deadlock을 없앨 수는 있고 일부 자원에 대해서는 효과적이다.
예를 들면 CPU는 process들이 선점할 수 있는 자원 중 하나인데 한 process가 CPU를 이용하다가 일정 시간이 지나면 아직 작업이 모두 끝나지 않았다고 해도 다른 process가 CPU를 할당받아 사용할 수 있기 때문이다.
하지만 모든 자원을 이렇게 선점할 수는 없다.
예를 들면 프린터 같은 경우는 이용 중 다른 process가 자원을 빼앗을 수 없다.
이렇게 비선점 조건을 없애 모든 자원을 빼앗을 수 있도록 하여 deadlock을 예방하는 방법은 다소 범용성이 떨어진다고 할 수 있다. -
원형 대기 조건을 없애는 경우
원형 대기를 없애는 방법은 간단하다.
모든 자원에 번호를 붙이고, 오름차순으로 자원을 할당하면 발생하지 않는다.
즉 1~5번까지 번호를 붙이고 5번은 1번에 접근할 수 없게 한다면 원형 대기가 발생하지 않는다.
비교적 현식적이고 실용적인 방식이지만, 각 자원에 어떤 번호를 붙이는 지에 따라 특정 자원의 활용률이 떨어진다는 단점이 있다.
이렇게 각 deadlock의 조건을 원천적으로 제거해 deadlock을 예방하는 방식은 deadlock이 발생하지 않음을 보장하지만 여러 부작용이 따르기도 한다.
deadlock 회피
deadlock 회피는 deadlock이 발생하지 않도록 조금씩 자원을 할당하는 방식이다.
모든 process들에 할당할 수 있는 자원이 충분한 상황에서 process들이 한두 개의 적은 자원만을 요구한다면 deadlock은 발생하지 않으나 자원이 한정된 상황에서 모든 process들이 한 번에 많은 자원을 요구하면 deadlock이 발생할 위험이 증가한다.
deadlock을 회피하는 방법을 설명할때 사용하는 언어가 3가지 있는데, 아래와 같다.
- safe state : 모든 process가 정상적으로 자원을 할당받고 종료할 수 있는 상태
- unsafe state : deadlock이 발생할 수 있는 상태
- safe sequence : 모든 process에 deadlock 없이 안전하게 자원을 할당할 수 있는 순서
deadlock을 회피하기 위해서는 시스템의 상태가 safe state에서 safe state로 움직이는 경우에만 자원을 할당할 수 있도록 하면 되고, unsafe state인 경우 자원을 할당하지 않도록 하면 된다.
즉, deadlock의 회피는 항시 safe state를 유지하는 방식이다.
deadlock 검출 후 회복
deadlock 예방과 회피는 deadlock 발생을 막기 위한 노력이라면 deadlock 검출 후 회복은 deadlock 발생을 인정하고 사후조치하는 방식이다.
검출 후 회복 방식에서 OS는 process가 자원을 요구할 때마다 그때그때 할당하며, deadlock 발생 여부를 주기적으로 검사한다.
그리고 deadlock이 검출되면 그때 아래와 같은 방식으로 회복한다.
-
선점을 통한 회복
deadlock이 해결될 때까지 한 process씩 자원을 몰아주는 방식.
deadlock이 해결될 때까지 다른 process로 부터 자원을 강제로 빼앗아 하나의 process에게 할당하는 방식이다. -
process 강제 종료를 통한 회복
가장 단순하면서 확실한 방식.
OS는 deadlock에 놓은 모든 process를 강제 종료할 수도 있고, deadlock이 없어질 때까지 한 process 씩 강제 종료할 수도 있다.
전자는 가장 확실하지만 그만큼 많은 process들을 잃을 수 있고 후자는 작업 내역을 잃는 process를 줄이지만 deadlock이 없어졌는지 확인하는 과정에서 overhead가 발생한다.
마지막으로 deadlock을 완전히 무시하는 타조 알고리즘이라는 방식도 있다.
