데드락을 설명해보세요.
두 개 이상의 프로세스가 각자가 점유하고있는 자원을 얻기 위해 무한정 대기상태에 빠지는 상황을 의미합니다.
데드락의 발생 조건을 설명해보세요.
데드락은 반드시 4가지 조건이 성립해야 발생합니다.
첫번째로 공유자원을 한번에 하나의 프로세스만 접근할 수 있는 상호배제가 보장되어야합니다 (상호배제). 두번째로 이미 하나의 자원을 보유하는 동시에 다른 프로세스가 점유한 자원을 기다리는 프로세스가 존재해야합니다 (점유와 대기). 또한 하나의 프로세스에게 할당된 자원을 사용이 끝나기 전에 다른 프로세스가 빼앗을 수 없는 비선점이 제공되어야합니다 (비선점). 마지막으로 프로세스의 집합 즉, p0 .. pn의 프로세스가 존재할 때 p0 이 p1의 자원을 기다리고 p1가 p2의 자원을 기다리고 pn이 p0의 자원을 기다리는, 순환 대기의 구조가 필요합니다 (순환 대기).
데드락의 해결 방법을 자세히 설명해보세요.
데드락은 예방/회피/탐지/회복 기법이 존재합니다.
예방 기법은 앞서 언급한 4가지 조건을 완화시키는 것입니다. 자원의 상호배제 조건을 방지하거나, 모든 자원에 대한 선점을 허용하는 방법이 있습니다. 또한, 프로세스의 순서가 증가하는 방향으로만 자원을 요청할 수 있게 설정하는 등의 방법으로 순환 대기 구조를 무너뜨리는 방법이 있지만 위와 같은 방법들은 자원 낭비와 동기화 문제가 발생합니다.
회피 기법은 프로세스가 자원을 요구할 때, 시스템이 자원을 할당한 이후에도 Safe State로 남아있는가를 확인하여 데드락을 회피하는 방법이 있습니다. 프로세스들이 요청하는 모든 자원을 데드락을 발생시키지 않고 차례대로 모두에게 할당할 수 있다면 Safe State에 있다고 말합니다. 이처럼 프로세스들에게 자원을 할당하면서 데드락을 발생시키지 않는 자원 할당 순서를 찾을 수 있다면 이것을 Safe Sequence라고 합니다.
이러한 특징을 살린 알고리즘이 바로 은행원 알고리즘입니다.
Q. 은행원 알고리즘을 활용하여 Safe Sequence를 찾아내라. (주어진 초기 자원은 12개)
위의 상황에서 은행원 알고리즘을 활용하여 찾을 수 있는 Safe Squecnce는 P1 -> P0 -> P1입니다. 현재 할당중인 자원의 수는 5+2+2 = 9개이며 할당가능한 자원의 수는 3개입니다. 이중 2개를 P1에게 할당하면 남은 자원의 수는 1이 됩니다. 여기서 P1의 작업이 끝나면 P1에게 할당된 4개의 자원이 반납되며 할당 가능한 자원의 수는 5가 됩니다. 마찬가지로 P0에게 5개의 자원을 할당 가능하며 이후 P2에게 7개의 자원을 할당할 수 있습니다.
하지만 은행원 알고리즘의 경우 사전에 프로세스들의 요구 자원량을 알아야합니다. 또한, 요구하는 자원의 수가 일정해야하는 등 사용에 있어서 많은 제약조건들이 존재합니다.
은행원 알고리즘을 제외하고도 자원할당 그래프 알고리즘을 사용하는 방법이 있습니다. 자원 요구관계를 노드와 간선으로 표현하여 사이클이 생기지 않는 상황에서 자원을 할당할 수 있는 방법입니다.
마지막으로 데드락이 발생한 상황에서의 회복 기법이 존재합니다. 데드락 회복기법은 크게 두개로 나뉘는데, 프로세스 중단 방법과 자원 선점방법이 존재합니다.
우선, 데드락이 발생한 모든 프로세스를 중단시키는 방법이 존재합니다. 하지만 계속 연산중이던 프로세스들이 일시에 중단되어 도중의 결과값이 폐기되는 등의 부작용이 발생할 수 있습니다. 또한, 프로세스를 하나씩 중단시킬 때마다 탐지 알고리즘으로 데드락을 탐지하면서 회복시키는 방법이 존재합니다. 다만 매번 탐지 알고리즘을 호출해야하는 오버헤드의 부담이 있습니다. 자원 선점방법은 프로세스에 할당된 자원을 선점하여 데드락을 해결할 때까지 그 자원을 다른 프로세스에 할당하는 방법입니다.
