교착 상태

왜 배우는가: 교착 상태는 다중 프로그래밍 환경에서 자원 경쟁이 빚는 대표적 동기화 문제로, 시스템 중단과 서비스 장애의 원인이 된다. 운영체제, 데이터베이스, 분산 시스템 전반에서 반복해서 다뤄지므로 시험에서도 개념 정의와 필요조건, 해결 방법을 함께 묻는 형태로 자주 출제된다.

출제 이력: 제134회 2교시 5번, 제132회 4교시 4번

1. 한 줄 정의와 핵심 키워드

교착 상태는 둘 이상의 프로세스가 서로 상대가 점유한 자원을 기다리며 무한 대기에 빠져 외부 개입 없이는 진행할 수 없는 상태이다.

핵심 키워드

• 교착 상태(Deadlock)
• 상호 배제(Mutual Exclusion)
• 점유와 대기(Hold and Wait)
• 비선점(No Preemption)
• 순환 대기(Circular Wait)
• 자원 할당 그래프(Resource Allocation Graph)
• 기아 상태(Starvation)

2. 개념 풀이

쉬운 말로 풀면, 두 사람이 서로 상대 손에 든 것을 달라고 하면서 자기 것은 놓지 않고 기다리는 상황이다. 둘 다 기다리기만 하니 어느 쪽도 일을 끝내지 못한다.

정식 정의는 다음과 같다. 교착 상태란 둘 이상의 프로세스(또는 스레드)가 각자 점유한 자원을 유지한 채 다른 프로세스가 점유한 자원을 기다려, 아무도 실행을 완료할 수 없는 상태를 말한다. 이 상태는 자원 할당 관계를 그래프로 그렸을 때 순환 고리가 생기는 것으로 표현할 수 있다.

교착 상태는 자원 경쟁의 결과이지 프로세스 하나의 오류가 아니다. 자원을 공유하는 구조가 있어야 발생하므로, 공유 자원이 없는 프로세스 집합에서는 교착이 생기지 않는다. 이 점은 상호 배제 조건과 바로 연결된다.

자원 할당 그래프에서 프로세스 Pi에서 자원 Rj로 향하는 간선 Pi→Rj는 Pi가 Rj를 요청하여 대기 중임을, Rj→Pi는 Rj가 Pi에 할당되어 있음을 뜻한다. 이 그래프에서 순환이 있으면 교착 상태 가능성이 있고, 자원 인스턴스가 하나뿐인 경우에는 순환이 곧 교착 상태다.

교착 상태와 기아 상태(Starvation)는 구별해야 한다. 교착은 관련 프로세스 모두가 영원히 멈추는 것이고, 기아는 특정 프로세스만 자원을 계속 할당받지 못하는 것이다. 기아는 우선순위 정책 때문에도 생길 수 있어 교착과 원인이 다르다.

3. 등장 배경과 필요성

멀티프로그래밍과 멀티스레딩이 보편화되면서 여러 프로세스가 프린터, 파일, 메모리, 데이터베이스 레코드 같은 한정된 자원을 동시에 요구하게 되었다. 자원을 독점해야 하는 경우가 늘어나자 자원 획득 순서가 엇갈려 순환 대기가 생기는 상황이 실제로 발생하기 시작했다.

교착 상태가 문제가 되는 이유는 발생 시 해당 프로세스가 자원을 반환하지 않으므로 시스템이 스스로 풀리지 않는다는 점이다. 그 결과 CPU는 놀고 있는데 작업은 진행되지 않는 처리량 저하가 나타나고, 서비스 응답이 멈추는 가용성 문제로 이어진다.

이 때문에 운영체제는 교착을 막거나, 피하거나, 발견해서 풀어주는 체계가 필요하게 되었다. 교착 상태 이론은 이 세 가지 대응의 기준이 되는 필요조건과 해결 방법을 제공한다.