교착 상태: 발생 조건과 해결 방법

교착 상태란

프로세스는 자원을 다음 순서로 사용한다.

1. 자원 요청: 필요한 자원을 요청하고, 다른 프로세스가 사용 중이면 대기(block) 한다.
2. 자원 사용: 요청한 자원을 획득하여 사용한다.
3. 자원 해제: 사용을 마친 자원을 되돌려준다.

교착 상태(Deadlock)는 여러 프로세스가 발생할 가능성이 없는 이벤트를 기다리며 Blocked 상태에 머무는 경우다. 둘 이상의 프로세스가 서로가 점유한 비공유 자원을 기다릴 때 발생하며, 한번 빠지면 작업이 정지되므로 외부의 간섭이 있어야 해결된다.

발생의 네 가지 조건

• 상호 배제: 한 번에 프로세스 하나만 사용할 수 있는 비공유 자원이 있어야 한다.
• 점유와 대기: 자원을 최소 하나 보유한 채, 다른 프로세스에 할당된 자원을 얻으려고 대기하는 프로세스가 있어야 한다.
• 비선점: 자원을 강제로 빼앗을 수 없고, 점유한 프로세스가 끝나야 해제된다.
• 순환(환형) 대기: 프로세스들이 서로의 자원을 원형으로 기다린다.

1. P1이 R2를 요청하여 할당받는다.
2. P2가 R1을 요청하여 할당받는다.
3. P1이 R1을 요청하지만 P2가 점유 중이므로 대기한다.
4. P2가 R2를 요청하지만 P1이 점유 중이므로 대기한다.

두 프로세스 모두 무한히 대기하므로 교착 상태다.

자원 할당 그래프

교착 상태는 그래프 G = (N, E)로 표현할 수 있다.

• 프로세스 P1이 자원 R1을 요청: P1 → R1
• 자원 R2를 프로세스 P2에 할당: R2 → P2

자원 할당 그래프에 사이클이 없으면 교착 상태가 아니다. 그러나 사이클이 있다면 교착 상태일 수도 있고 아닐 수도 있다. 사이클은 교착 상태의 필요조건이지 충분조건이 아니다.

해결 방법 1: 예방

네 가지 발생 조건 중 하나를 제거한다.

• 상호 배제 조건 제거: 모든 자원을 공유하게 만들면 동시성 문제가 발생하므로 불가능하다.
• 점유와 대기 조건 제거: 프로세스가 필요한 자원을 한꺼번에 요청하고, 모두 할당할 수 있을 때만 할당한다. 필요하지 않은 순간에도 자원을 쥐고 있어 자원 효율이 매우 낮고, 기아 상태가 발생할 수 있다.
• 비선점 조건 제거: 자원을 빼앗을 수 있게 하면 실행 중인 중요한 프로세스가 중단될 수 있다. 유사한 방법으로, 할당받을 수 없는 자원을 요청한 프로세스가 가진 자원을 모두 반납하고 처음부터 다시 시작하게 할 수도 있지만 자원 낭비가 심하다.
• 순환 대기 조건 제거: 모든 자원에 순서를 부여하고 오름차순으로만 요청하게 한다. 다른 여유 자원을 먼저 쓸 수 없어 자주 쓰이는 자원에 병목 현상이 생긴다.

조건 하나를 제거하면 교착 상태는 절대 발생하지 않지만, 장치 활용률과 시스템 처리량이 떨어지는 심각한 자원 낭비가 따른다. 결론적으로 예방은 비현실적이다.

해결 방법 2: 회피

발생 가능성을 미리 제거하는 예방과 달리, 교착 상태가 발생할 수 있음을 인정하고 발생하려 할 때 피해 가는 방법이다. 시스템 상태를 계속 감시하면서 교착 상태로 이어질 수 있는 자원 할당 요청을 보류해, 시스템을 항상 안전 상태(safe state)로 유지한다.

모든 프로세스가 일정 기간 안에 작업을 끝낼 수 있으면 안전 상태, 그렇지 않으면 불안전 상태다. 불안전 상태는 교착 상태가 발생할 가능성이 있다는 뜻이지 반드시 발생한다는 뜻은 아니다.

회피 방법은 두 가지다.

1. 프로세스 시작 거부: 자원 요청이 교착 상태를 일으킬 수 있다면 프로세스를 시작하지 않는다.
2. 자원 할당 거부: 요청한 자원을 할당했을 때 교착 상태가 발생할 수 있다면 할당하지 않는다. (예: 은행가 알고리즘)

은행가 알고리즘 (Banker’s algorithm)

• 다익스트라가 제안했으며, 자원 할당 여부를 결정하기 전에 할당 후의 상태를 시뮬레이션하여 안전한지 검사한다.
• 불안전해질 가능성이 있다고 판단하면 요청을 연기하거나 거부한다.
• 각 프로세스가 요청할 자원의 최대 수를 미리 알아야 한다.

자원 10개, 프로세스 3개인 예를 보자.

가용 자원은 2개이고, P1 → P3 → P2 순서로 실행을 끝낼 수 있다. 이런 안전 순서(safe sequence)가 하나 이상 존재하면 안전 상태다. 반대로 가용 자원으로 추가 요구량을 채울 수 있는 프로세스가 없으면 불안전 상태다.

회피의 한계

• 높은 오버헤드: 시스템을 항상 감시해야 한다.
• 낮은 자원 활용률: 안전 상태를 유지하려고 사용하지 않는 자원을 남겨 둔다.
• 프로세스 수와 자원 수가 고정되어 있다는 가정이 필요해 비현실적이다.

해결 방법 3: 탐지와 회복

교착 상태의 발생을 허용하되, 발생을 탐지한 뒤 회복시킨다. 탐지는 현재 상태만 고려하며, 교착 상태를 발견하면 회복 과정이 필요하다.

• 탐지 알고리즘을 언제 수행할지 결정하기 어렵다. 자주 실행하면 시스템 성능이 떨어지지만 교착 상태를 빨리 발견해 자원의 유휴 상태를 줄일 수 있고, 드물게 실행하면 그 반대가 된다.
• 필요한 정보를 유지하고 탐지 알고리즘을 실행하는 비용에 더해 회복 비용까지 부담해야 한다.

탐지: 그래프 소거

자원 할당 그래프에서 edge를 하나씩 지워 가며 판단한다. 어떤 프로세스의 요청 수가 남은 자원 수(자원의 총 수 − 할당된 수) 이하이면 그 프로세스는 unblocked 상태이므로 해당 edge를 지울 수 있다.

• Completely reduced: 모든 edge가 제거된다. 교착 상태가 없다.
• Irreducible: 지울 수 없는 edge가 남는다. 하나 이상의 프로세스가 교착 상태다.

회복

프로세스를 중단하는 방법은 두 가지다.

1. 교착 상태에 빠진 프로세스를 모두 중단: 자원 사용과 시간 면에서 비용이 높다.
2. 한 프로세스씩 중단: 매번 탐지 알고리즘을 호출해야 해서 부담이 크다.

따라서 다음을 기준으로 최소 비용으로 중단할 프로세스의 우선순위를 정한다.

• 프로세스가 수행된 시간과 종료까지 남은 시간
• 프로세스가 사용한 자원의 형태와 수
• 프로세스를 종료하는 데 필요한 자원 수

프로세스를 중단하는 대신 자원을 선점할 수도 있다. 이때는 교착 상태가 아닌 프로세스가 종료될 수 있고, 우선순위 기반으로 자원을 빼앗으므로 기아 상태가 발생할 수 있다.

각 방법마다 장단점이 있으므로 상황에 맞게 트레이드오프를 따져야 한다.

참고

• 운영체제: 그림으로 배우는 구조와 원리 (한빛아카데미)