[운영체제] 교착 상태(Dead Lock ) 정리
🎯 교착 상태(Dead Lock) 이란 ?
둘 이상의 프로세스가 다른 프로세스가 점유하고 있는 자원을 서로 기다릴때 무한 대기에 빠지는 상황이 바로 교착상태 (Dead Lock) 이라고 합니다. 교착 상태는 기아 상태(Stravation) 와 비슷해보이지만 차이가 있습니다. 기아 상태는 잘못된 정책으로 인해 특정 프로세스의 작업이 자연되는 문제인 반면, 교착 상태는 여러 프로세스가 작업을 진행하다보니 발생하는 자연적인 현상입니다.
기아 상태(Stravation)란?
기아 상태는 프로세스가 필요한 자원을 계속해서 얻지 못하여 무한정 기다리게 되는 상황을 의미합니다. 이는 우선순위가 낮은 프로세스가 높은 우선순위의 프로세스들에 의해 자주 차단될때 발생합니다.
프로세스 1 은 자원 A 가 필요합니다. 자원 A 는 프로세스 2에 할당되어 있습니다.
프로세스 2 은 자원 B 가 필요합니다. 자원 B 는 프로세스 1에 할당되어 있습니다.
이처럼 어느 한 프로세스를 강제종료 하지 않으면 컴퓨터가 정지된 것 처럼 어떤 작업도 수행할 수 없습니다.
교착 상태가 발생하기 위해선 다음 4가지 조건을 모두 충족해야 발생합니다. 4가지 조건 중 한가지 조건이라도 충족하지 않으면 발생하지 않습니다.
✅ 교착 상태 발생 조건 4가지
(1) 상호 배체 (Mutal Exclusion) : 한 번에 한 개의 프로세스만이 공유 자원을 사용할 수 있습니다.
(2) 점유 대기 (Hold and Wait) : 프로세스가 할당된 자원을 가진 상태에서 다른 자원을 기다립니다.
(3) 비 선점 (No Preemption) : 프로세스가 작업을 마친 후 자원을 자발적으로 반환할 때 까지 기다립니다.
(4) 순환 대기 (Circular Wait) : 프로세스의 자원 점유 및 점유된 자원의 요구 관계가 원형을 이루며 대기하는 조건입니다.
각 프로세스는 순환적으로 다음 프로세스가 요구하는 자원을 가지고 있습니다.
🎯 교착 상태 해결 방법
교착 상태를 해결하는 방법은 예방 (Prevention), 회피(Avoidance), 탐지 및 회복 (Detection and Recovery), 무시(Ignorance) 등으로 나눌 수 있습니다. 각각의 방법에 대해 알아봅시다.
✅ 예방 (Prevention)
교착 상태를 유발하는 4가지 조건중 하나의 조건만을 무력화 한다면 교착 상태를 예방할 수 있습니다.
상호 배제를 없애는 방법 : 모든 자원을 프로세스들이 공유 하게 만든다. --> 이 방법은 현실적으로 불가능 합니다.
점유와 대기를 없애는 방법 : 모든 프로세스에 자원을 모두 할당하거나, 아예 할당하지 않는 방식으로 배분한다. --> 자원의 활용률이 낮아집니다.
비선점 조건 없애는 방법 : 선점이 가능한 자원에 한해 효과적이나 모든 자원이 선점 가능한건 아닙니다. ex) CPU
원형 대기 조건 없애는 방법 : 모든 자원에 번호를 붙이고 오름차순으로 자원을 할당하면 원형 대기는 발생하지 않습니다. 이는 현실적으로 예방할 수 있는 방법중 가장 가능성이 있으나, 이 역시 모든 자원에 번호를 부여하는 행위 자체가 효율적이지 못합니다.
정리해보면 교착 상태를 예방 하는 방법은 각각 부작용을 가지고 있음을 알 수 있습니다.
✅ 회피 (Avoidance)
교착 상태를 무분별한 자원 할당으로 인해 발생했다고 간주해, 교착 상태가 발생하지 않을 만큼 자원을 조심히 할당합니다. 배분할 수 있는 자원의 양을 고려하여 교착 상태가 발생하지 않을 만큼만 자원을 배분하는 방법이 교착 상태 회피 방법입니다.
이때 은행원 알고리즘이 사용됩니다.
은행원 알고리즘이란?
은행가 알고리즘(Banker's Algorithm)은 교착 상태를 회피하기 위한 기법 중 하나로, 운영 체제가 자원 할당을 관리할 때 시스템이 안전 상태(Safe State)에 있는지를 확인하여 교착 상태를 방지합니다. 이 알고리즘은 디지스트라(Edsger Dijkstra)에 의해 제안되었으며, "은행가(Banker)"라는 이름은 은행가가 고객에게 대출을 해줄 때 시스템의 안전성을 확인하는 것에 비유하여 붙여졌습니다.
프로세스가 자원을 요청할 때, 요청을 수락했을 때 시스템이 안전 상태인지 확인합니다. 안전 상태라면 자원을 할당하고, 그렇지 않다면 요청을 보류합니다.
안전 순서열 : 교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서
안전 상태 : 교착 상태 없이 모든 프로세스가 자원을 할당 받고 종료될 수 있는 상태 (안전 순서열이 있는 상태)
불안정 상태 : 교착 상태가 발생할 수도 있는 상태 (안전 순서열이 없는 상태)
교착 상태 회피는 항상 안전 상태를 유지하며 자원을 할당 하는 방식입니다.
✅ 탐지 및 회복 (Detection and Recovery)
교착 상태가 발생했음을 탐지하고, 이를 회복하는 방법입니다. 교착 상태를 회복하는 방식에는 두가지가 있습니다.
(1) 선점을 통한 회복
교착 상태가 해결될 때까지 한 프로세스씩 자원을 몰아주는 방식입니다.
(2) 프로세스 강제 종료를 통한 회복
교착 상태에 놓인 프로세스 모두를 강제 종료 하는 방식입니다. (작업 내용을 모두 잃을 수 있음)
교착 상태가 해결될 때까지 한 프로세스씩 강제 종료하는 방식입니다. (한 프로세스 종료 후 교착 상태가 해결됐는지 확인해야합니다. --> 오버헤드 발생)
✅ 무시 (Ignorance)
교착 상태(Dead Lock) 이 발생하지 않았다 생각하고 아무론 조치도 취하지 않는 방식입니다. 그 이유는 교착상태는 매우 드물하게 발생합니다. 교착 상태에 대한 조치 자체가 더 큰 오버 헤드를 발생시킬 수 있기에 시스템을 강제 종료하는 방식입니다.
(대부분의 운영체제가 채택하는 방식입니다.)