교착 상태

왜 배우는가: 교착 상태는 다중 프로세스 시스템에서 자원 경합이 있을 때 시스템 전체가 멈추는 현상이라 운영체제, 데이터베이스, 클라우드 자원 관리 전반에 나타난다. 정보관리기술사 시험에서는 발생 조건, 예방·회피·탐지·회복 기법의 구분, 은행가 알고리즘의 자료구조를 묻는 문제로 반복 출제된다.

출제 이력: 제124회 3교시 4번, 제116회 1교시 4번

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

교착 상태(Deadlock)는 둘 이상의 프로세스가 서로 상대방이 점유한 자원을 기다리며 무한히 대기하는 상태이다. 답안 첫 줄에는 다음 문장을 쓴다.

둘 이상의 프로세스가 서로 상대가 점유한 자원을 기다리며 영원히 진행하지 못하는 상태

핵심 키워드는 다음과 같다.

• 교착 상태(Deadlock)
• 코프만 조건(Coffman Conditions)
• 안전 상태(Safe State)
• 불안전 상태(Unsafe State)
• 은행가 알고리즘(Banker's Algorithm)
• 교착 회피(Deadlock Avoidance)
• 안전 순서열(Safe Sequence)

2. 개념 풀이

쉽게 말하면 두 사람이 서로 상대의 물건을 받아야 자기 일을 끝낼 수 있는데, 둘 다 자기 물건을 내놓지 않고 버티는 상황이다. 컴퓨터에서 프로세스가 프린터와 디스크를 각각 쥐고 상대가 쥔 것을 기다리면 둘 다 멈춘다.

정식 정의는 다음과 같다. 여러 프로세스가 공유 자원을 점유한 채 다른 프로세스가 점유한 자원을 기다리고, 그 대기 관계가 순환을 이루어 어느 프로세스도 진행할 수 없는 상태이다. 1971년 E. G. 코프만(Coffman)은 교착 상태가 발생하려면 다음 네 조건이 동시에 성립해야 함을 보였다.

상호배제(Mutual Exclusion)는 자원을 한 번에 한 프로세스만 사용하는 조건이다. 점유와 대기(Hold and Wait)는 자원을 가진 채 다른 자원을 기다리는 조건이다. 비선점(No Preemption)은 사용 중인 자원을 강제로 빼앗을 수 없는 조건이다. 순환 대기(Circular Wait)는 프로세스들이 원형 사슬을 이루어 다음 프로세스가 가진 자원을 기다리는 조건이다.

이 네 조건 중 하나라도 깨지면 교착 상태는 발생하지 않는다. 다만 네 조건은 독립적이지 않다. 순환 대기는 점유와 대기, 비선점이 함께 있어야 성립한다는 점을 함께 알아 둔다.

은행가 알고리즘은 다익스트라(E. Dijkstra)가 제안한 교착 회피 기법이다. 은행이 고객의 대출을 보유 현금 범위 안에서만 승인하는 방식에서 이름이 유래했다. 자원을 할당하기 전에 할당 후에도 모든 프로세스가 완료될 수 있는지 검사하여, 안전 상태가 유지될 때만 할당한다.

안전 상태(Safe State)는 모든 프로세스가 차례로 완료될 수 있는 안전 순서열이 존재하는 상태이다. 불안전 상태(Unsafe State)는 그런 순서열이 없는 상태이며, 교착이 이미 발생했다는 뜻은 아니고 교착 가능성이 남아 있다는 뜻이다.

3. 등장 배경과 필요성

다중 프로그래밍과 시분할 시스템이 보편화되면서 여러 프로세스가 같은 자원을 경쟁하게 되었다. 자원 수는 한정되어 있고 프로세스는 자원을 나눠 쓰며 기다리는 일이 많아졌다. 이때 교착 상태가 발생하면 해당 프로세스뿐 아니라 시스템 자원이 함께 묶여 처리율이 급격히 떨어진다.

교착 상태를 다루는 방법은 크게 네 가지다. 예방(Prevention)은 네 조건 중 하나를 구조적으로 깨는 방법이다. 회피(Avoidance)는 자원 할당 시점마다 안전성을 검사하는 방법이다. 탐지(Detection)는 발생 여부를 주기적으로 검사하는 방법이다. 회복(Recovery)은 프로세스 종료나 자원 선점으로 해소하는 방법이다.