chapter 13 교착 상태
13-1 교착 상태란
식사하는 철학자 문제
일어나지 않을 사건을 기다리며 진행이 멈춰 버리는 현상을 교착 상태 (deadlock)라고 합니다.
교착 상태의 해결을 위해 첫째, 교착 상태가 발생했을 때의 상황을 정확히 표현해 보고, 둘째, 교착 상태가 일어나는 근본적인 이유에 대해 알아야 합니다.
자원 할당 그래프
교착 상태는 자원 할당 그래프 (resource-allocation graph)를 통해 단순하게 표현할 수 있습니다.
- 첫째, 프로세스는 원으로, 자원의 종류는 사각형으로 표현합니다.
- 둘째, 사용할 수 있는 자원의 개수는 자원 사각형 내에 점으로 표현합니다.
- 셋째, 프로세스가 어떤 자원을 할당 받아 사용 중이라면 자원에서 프로세스를 향해 화살표를 표시합니다.
- 넷째, 프로세스가 어떤 자원을 기다리고 있다면 프로세스에서 자원으로 화살표를 표시합니다.
교착 상태 발생 조건
상호 배제, 점유와 대기, 비선점, 원형 대기가 모두 만족될 때 교착 상태가 발생할 가능성이 생긴다고 보면 됩니다.
상호 배제 (mutual exclusion)
한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없을 때
점유와 대기 (hold and wait)
어떤한 자원을 할당받은 상태에서 다른 자원을 할당받기를 기다린다면 교착 상태가 발생할 수 있습니다.
비선점 (nonpreemptive)
그 자원을 이용하는 프로세스의 작업이 끝나야만 비로소 이용할 수 있습니다. 즉, 어떤 프로세스도 다른 프로세스의 자원을 강제로 빼앗지 못했기 때문에 교착 상태가 발생했다고 볼 수 있습니다.
원형 대기 (circular wait)
자원 할당 그래프가 원의 형태로 그려지면 교착 상태가 발생할 수 있습니다.
13-2 교착 상태 해결 방법
교착 상태 예방
상호 배제 - 모든 자원을 공유 가능하게 만드는 방법이지만, 현실적으로 모두 없애기는 쉽지 않습니다.
점유와 대기 - 특정 프로세스에 자원을 모두 할당하거나, 아예 할당하지 않는 방식으로 배분합니다. 하지만, 자원의 활용률이 낮아집니다. 결국 많은 자원을 필요로 하는 프로세스가 무한정 기다리게 되는 기아 현상을 야기할 우려가 있습니다.
비선점 조건 - 선점하여 사용할 수 있는 일부 자원에 대해서는 효과적이지만, 범용성이 떨어지는 방안입니다.
원형 대기 - 모든 자원에 번호를 붙이고, 오름차순으로 자원을 할당하는 방법이지만, 간단한 작업은 아닙니다.
교착 상태 회피
교착 상태 회피는 교착 상태가 발생하지 않을 정도로만 조심 조심 자원을 할당하는 방식입니다.
교착 상태가 발생하지 않고 모든 프로세스가 정상적으로 자원을 할당받고 종료될 수 있는 상태를 안전 상태라고 부르고, 교착 상태가 발생할 수도 있는 상황을 불안전 상태라고 부릅니다.
안전 순서열은 교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서를 의미합니다.
교착 상태 검출 후 회복
교착 상태 발생을 인정하고 사후에 조치하는 방식입니다.
프로세스들이 자원을 요구할 때마다 그때그때 모두 할당하며, 교착 상태 발생 여부를 주기적으로 검사합니다.
선점을 통한 회복 - 해결될 때까지 다른 프로세스로부터 자원을 강제로 빼앗고 한 프로세스에 할당하는 방식
프로세스 강제 종료를 통한 회복 - 프로세스를 모두 강제 종료할 수도 있고, 교착 상태가 없어질 때까지 한 프로세스씩 강제 종료할 수도 있습니다.
Conference) 타조 알고리즘 - 드물게 발생하는 잠재적 문제를 무시로 대처하는 방식
