교착상태 4가지 필요조건과 해결 방법, 은행원 알고리즘으로 안전 순서 찾는 과정 (정보처리기사)

둘 이상의 프로세스가 서로 상대가 가진 자원을 기다리며 영원히 멈추는 상태를 교착상태라고 한다. 정보처리기사에서는 발생 조건 네 가지와 해결 방법 분류를 묻는 문제가 많고, 실기에서는 은행원 알고리즘으로 안전 상태를 판단하는 계산이 나오기도 한다. 조건과 해결책을 짝지어 외우면 쉽다.

교착상태는 네 가지 조건이 동시에 성립할 때 생긴다

필요조건	의미	깨뜨리는 방법(예방)
상호배제	자원을 한 번에 한 프로세스만 사용	공유 가능한 자원으로 바꾼다(항상 가능하진 않다)
점유와 대기	자원을 쥔 채 다른 자원을 기다림	필요한 자원을 한꺼번에 요청한다
비선점	이미 할당된 자원을 강제로 뺏지 못함	대기 중인 프로세스의 자원을 회수한다
환형 대기	프로세스가 원형으로 서로의 자원을 기다림	자원에 번호를 매겨 순서대로만 요청한다

그림에서 P1은 R1을 쥔 채 R2를, P2는 R2를 쥔 채 R1을 요청한다. 자원이 각각 1개이면 이 순환이 곧 교착상태이다. 자원이 여러 개이면 순환이 있어도 교착이 아닐 수 있다는 점은 서술형에서 감점되기 쉬운 부분이다.

해결 방법은 예방, 회피, 탐지와 복구, 무시로 나뉜다

예방은 네 조건 중 하나를 구조적으로 깨는 방식이고 자원 활용률이 낮아지는 단점이 있다. 회피는 자원 요청이 올 때마다 시스템이 안전한지 판단하는 방식이며 대표가 은행원 알고리즘이다. 탐지와 복구는 교착을 허용한 뒤 자원 할당 그래프로 찾아 프로세스를 종료하거나 자원을 선점한다. 무시는 교착이 드물다고 보고 개입하지 않는 방식으로 많은 범용 운영체제가 쓴다.

예시: 은행원 알고리즘으로 안전 순서를 찾으면 P1, P3, P0, P2, P4가 나온다

자원 종류 3개, 현재 사용 가능량(Available)이 3 3 2라고 하자. 필요량(Need)은 최대 요구(Max)에서 현재 할당(Allocation)을 뺀 값이다.

프로세스	Allocation	Max	Need(Max-Allocation)
P0	0 1 0	7 5 3	7 4 3
P1	2 0 0	3 2 2	1 2 2
P2	3 0 2	9 0 2	6 0 0
P3	2 1 1	2 2 2	0 1 1
P4	0 0 2	4 3 3	4 3 1

Need가 Available 이하인 프로세스를 하나씩 끝내며 자원을 반납시키면 된다. P1(1 2 2)이 먼저 끝나 Available이 5 3 2가 되고, P3(0 1 1)이 끝나 7 4 3, P0(7 4 3)이 끝나 7 5 3, P2(6 0 0)가 끝나 10 5 5, 마지막으로 P4(4 3 1)가 끝난다. 모두 끝낼 수 있는 순서가 하나라도 있으므로 안전 상태이다. 안전 순서는 여러 개일 수 있고 이 글의 순서는 그중 하나이다. 이 상태에서 P1이 1 0 2를 요청하면 가정해서 할당해 봐도 안전 순서가 남아 허용되고, P4가 3 3 0을 요청하면 허용했을 때 안전 순서가 없어 거절된다. 이 판정은 파이썬으로 검산했다.

답안에는 조건, 해결 분류, 회피의 원리를 한 흐름으로 쓴다

서술형은 정의 → 네 필요조건 → 해결 방법 네 가지 → 은행원 알고리즘의 안전 상태 개념 순으로 쓴다. 실무에서는 데이터베이스의 잠금 순서를 통일하거나 타임아웃으로 대기를 끊는 방식으로 교착을 줄인다. 안전 상태가 아니라고 해서 반드시 교착이 일어나는 것은 아니고, 교착 가능성이 있는 상태일 뿐이다.

실전 팁으로, 은행원 알고리즘 계산은 Need를 먼저 만들고 Available로 끝낼 수 있는 프로세스를 하나씩 지워 가는 순서로 풀면 된다. 끝낸 프로세스의 Allocation을 Available에 더하는 단계를 빠뜨리지 않는다. 문제가 안전 순서를 묻는 경우 답이 여러 개일 수 있으므로 조건에 맞는 순서를 하나 제시하면 된다.

시험 직전 한 줄 요약

교착상태는 상호배제·점유와 대기·비선점·환형 대기가 모두 성립할 때 생기며, 은행원 알고리즘은 요청을 들어줘도 모든 프로세스를 끝낼 수 있는 순서가 남을 때만 허용한다.

이 글은 학습용 정리이며 실제 시험 문항과 다를 수 있다. 출제 기준은 큐넷·KISA·한국데이터산업진흥원 등 공식 공지를 확인하라. 그림은 설명용 예시 데이터로 그린 개념도이며 실측 데이터가 아니다.