교착상태(Dead Lock) 알아보기
교착상태(Dead Lock)은 상호 배제에 의해 나타나는 문제점으로, 둘 이상의 프로세스들이 자원을 점유한 상태에서 서로 다른 프로세스가 점유하고 있는 자원을 요구하며 무한 대기하는 현상을 의미합니다.
교착상태 조건
교창상태가 일어나려면 다음과 같은 네 가지 조건을 모두 충족시켜야 합니다.
- 상호 배제 (Mutual exclusion)
- 자원은 한 번에 한 프로세스만이 사용할 수 있어야 한다.
- 점유 대기 (Hold and wait)
- 최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용하고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 있어야 한다.
- 비선점 (No preemption)
- 다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없어야 한다.
- 순환 대기 (Circular wait)
- 프로세스들이 순환 형식으로 서로를 기다리고 있어야 한다.
교착상태 표현 방법
자원 할당 그래프(Resource-Allocation Graphs)를 통해 시스템의 교착상태 유무를 파악할 수 있습니다.
자원 할당 그래프 요소
- 리소스 집합 {R1, R2,..., RN} : 그래프에서 정사각형 노드로 나타냅니다. 리소스 노드 내부의 점은 할당할 수 있는 인스턴트 수를 나타냅니다.
- 프로세스 집합 {P1, P2,..., PN} : 원형 노드로 프로세스를 나타냅니다.
- 요청 간선(Request Edges) : Pi → Rj로 향하는 간선입니다. Pi가 Rj를 요청했으며 현재 해당 리소스를 사용할 수 있을 때까지 기다리고 있음을 나타냅니다.
- 할당 간선(Assignment Edges) : Rj → Pi로 향하는 간선입니다. 리소스 Rj가 Pi에게 할당되었고 Pi가 리소스 Rj를 보유하고 있음을 나타냅니다.
그래프에 순환(cycle)이 있는 경우
다음과 같이 자원 할당 그래프에서 순환(cycle)이 나타나지 않으면 교착 상태가 아닙니다.
그래프에 순환(cycle)이 없는 경우
그래프에 순환이 있으면 교착상태 일 수 있습니다.
순환이 있다고 해서 무조건 교착 상태는 아닙니다.
다음과 같이 리소스 집합에 인스턴스가 둘 이상인 경우 교착 상태가 아닐 수 있습니다.
위 그림에서 P2 또는 P4가 자원을 사용한 뒤 해제한다면 P1 또는 P3은 자원을 할당받을 수 있게 되어 교착상태에서 벗어나게 됩니다.
