교착 상태 탐지와 Banker's Algorithm 기반 자원 관리

자원 경쟁이 멈춤으로 바뀌는 순간

운영체제에서는 여러 프로세스가 CPU, 메모리, I/O 장치처럼 제한된 자원을 함께 사용한다. 한 프로세스가 가진 자원을 다른 프로세스가 기다리고, 그 대기 관계가 다시 되돌아오면 누구도 다음 단계로 진행하지 못한다. 이것이 교착 상태(Deadlock)다.

교착 상태가 발생하면 외부 개입 없이는 대기가 끝나지 않고, 점유된 자원도 해제되지 않는다. 일부 작업이 멈출 수 있고, 범위가 넓으면 시스템 전체의 처리도 중단된다. 네 방향 교차로에 차량이 동시에 진입한 뒤 각 차량이 오른쪽 차량을 기다리는 상황이 같은 구조를 보여준다.

함께 성립할 때 교착 상태가 되는 조건

교착 상태는 다음 조건이 모두 동시에 성립할 때 발생한다.

상호 배제(Mutual Exclusion)

하나의 자원을 동시에 사용할 수 있는 프로세스는 하나뿐이다. 프린터나 테이프 드라이브처럼 공유할 수 없는 자원, 세마포어로 보호하는 임계 구역이 여기에 해당한다.

점유와 대기(Hold and Wait)

프로세스가 최소한 하나의 자원을 점유한 채 추가 자원을 요청하는 상태다. 기존 자원을 놓지 않은 채 부분 할당 상태를 유지하면서 다른 자원의 획득을 시도한다.

비선점(No Preemption)

이미 할당한 자원은 프로세스가 자발적으로 반납할 때까지 강제로 회수할 수 없다. CPU는 선점할 수 있지만 I/O 장치는 비선점 자원일 수 있다.

순환 대기(Circular Wait)

프로세스 집합에서 각 프로세스가 다음 프로세스가 점유한 자원을 기다리는 순환 의존 관계다. P0 → P1 → P2 → ... → Pn → P0처럼 연결되며, 대기 그래프에서는 사이클로 나타난다.

⤢✕

대기 관계에서 사이클 찾기

Wait-For Graph(대기 그래프)

Wait-For Graph는 자원 할당 그래프를 프로세스 중심으로 단순화해 교착 상태를 찾는 방식이다. 노드는 프로세스만 표현하며, Pi → Pj 간선은 Pi가 Pj가 점유한 자원을 기다린다는 뜻이다. 사이클이 있으면 교착 상태가 발생한 것으로 본다.

탐지는 현재 자원 할당 상태를 대기 그래프로 바꾼 뒤 깊이 우선 탐색(DFS)으로 사이클을 찾는 순서로 진행한다. 사이클을 발견하면 회복 절차로 이어진다.

⤢✕

시간 복잡도는 프로세스 수 n에 대해 O(n²)이며, 주기적으로 탐지할 때는 그 오버헤드를 고려해야 한다.

자원 할당 그래프(Resource Allocation Graph)

자원 할당 그래프는 교착 상태를 방향 그래프로 표현한다. 프로세스는 원형 노드, 자원은 사각형 노드로 나타내며, 자원에서 프로세스로 향하는 간선은 할당을, 프로세스에서 자원으로 향하는 간선은 요청을 뜻한다.

자원 인스턴스가 하나인 경우 사이클은 교착 상태를 의미한다. 자원 인스턴스가 여러 개인 경우에는 사이클이 필요조건이므로 추가 분석이 필요하다.

조건을 깨뜨려 발생 가능성을 없애는 방법

예방(Prevention)은 교착 상태의 필요조건 가운데 하나를 원천적으로 성립하지 않게 만드는 접근이다.

상호 배제를 줄이려면 읽기 전용 파일처럼 동시 읽기가 가능한 자원을 사용하거나, 프린터 출력을 디스크에 임시 저장하는 스풀링(Spooling)을 적용할 수 있다. 다만 프린터와 테이프처럼 본질적으로 배타적인 자원에는 적용할 수 없고, 임계 구역에도 상호 배제가 필요하다.

점유와 대기를 막는 방식은 필요한 자원을 한 번에 요청하게 하거나, 새 자원이 필요할 때 보유 자원을 모두 해제한 뒤 전체 자원 집합을 다시 요청하게 한다. 전자는 프로세스 시작 시 필요한 자원을 모두 확보해야 실행을 시작할 수 있다. 후자는 기존 자원을 놓은 뒤 필요한 자원 전체를 재요청한다. 둘 다 자원 활용률을 낮출 수 있고 기아 상태(Starvation)가 생길 수 있다.

비선점을 부정하려면 자원 요청이 실패했을 때 보유 자원을 모두 선점하거나, 우선순위에 따라 자원을 회수할 수 있어야 한다. 체크포인트와 롤백을 지원하는 방법도 있다. 상태를 저장하기 어려운 프린터 같은 자원에는 적용하기 어렵고 오버헤드도 증가한다.

순환 대기는 자원 타입에 고유 번호를 부여하고 프로세스가 증가하는 순서로만 자원을 요청하도록 제한해 차단한다. F(Ri) < F(Rj)일 때만 Ri를 보유한 상태에서 Rj를 요청할 수 있다. 구현이 간단하고 오버헤드가 낮지만, 자원 요청 순서가 제한되어 프로그래밍 복잡도가 커진다.

안전 상태를 확인하고 요청을 승인하는 방식

회피(Avoidance)는 자원을 할당할 때마다 시스템이 안전 상태를 유지하는지 확인한다. 안전 상태(Safe State)는 모든 프로세스가 정상적으로 끝날 수 있는 자원 할당 순서가 존재하는 상태다. 안전 순서 <P1, P2, ..., Pn>에서 각 Pi는 현재 가용 자원과 앞선 프로세스가 해제한 자원으로 완료할 수 있어야 한다.

Banker's Algorithm

Banker's Algorithm은 은행이 대출 가능 여부를 판단하는 것처럼, 자원 요청을 받아들인 뒤에도 안전 상태가 유지되는지 확인한다. 각 프로세스는 최대 자원 요구량을 미리 선언하고, 안전 상태가 보장되는 요청만 승인받는다.

알고리즘은 다음 자료 구조를 사용한다.

• Available[m]: m개 자원 타입의 가용 자원 벡터
• Max[n][m]: 각 프로세스의 최대 자원 요구량
• Allocation[n][m]: 현재 할당된 자원량
• Need[n][m]: 추가 필요 자원량 (Max - Allocation)

안전성 검사는 Work를 가용 자원으로 초기화하고, Finish가 false이면서 Need[i] ≤ Work인 프로세스를 찾는다. 해당 프로세스가 완료된다고 가정해 Allocation[i]를 Work에 더한다. 이 과정을 반복해 모든 프로세스를 완료할 수 있으면 안전 상태다.

⤢✕

프로세스 i가 Request[i]를 요청하면 먼저 Request[i] ≤ Need[i]인지 확인하고, 이어 Request[i] ≤ Available인지 확인한다. 조건을 만족하면 다음처럼 가정적 할당을 수행한다.

• Available -= Request[i]
• Allocation[i] += Request[i]
• Need[i] -= Request[i]

그 뒤 안전성 검사를 실행한다. 안전하면 요청을 승인하고, 불안전하면 상태를 복원한 후 대기시킨다.

안전 순서를 확인하는 예

프로세스는 P0, P1, P2, P3, P4이고, 자원 타입은 A, B, C이며, Available은 (3, 3, 2)라고 한다.

프로세스	Allocation(A,B,C)	Max(A,B,C)	Need(A,B,C)
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)

P1은 Need ≤ Available을 만족하므로 먼저 완료할 수 있고, 이후 Work는 (5,3,2)가 된다. 이어 P3을 완료하면 Work는 (7,4,3), P4를 완료하면 (7,4,5), P2를 완료하면 (10,4,7), 마지막으로 P0를 완료하면 (10,5,7)이 된다.

따라서 안전 순서 <P1, P3, P4, P2, P0>가 존재하며 시스템은 안전 상태다.

Banker's Algorithm은 예방 방식보다 자원 활용률을 높이면서 교착 상태를 완전히 방지할 수 있다. 반면 최대 자원 요구량을 미리 선언해야 하고, 계산 오버헤드는 O(n²×m)이다. 또한 프로세스 수와 자원 타입이 고정돼 있다고 가정한다.

이미 발생한 교착 상태에서 복구하기

교착 상태가 발생한 뒤에는 프로세스를 종료하거나 자원을 선점해 정상 상태로 되돌린다.

프로세스를 모두 종료하는 방식은 가장 단순하지만 비용이 크다. 선택적으로 종료할 때는 교착 상태가 풀릴 때까지 하나씩 종료하며, 우선순위, 실행 시간, 사용 자원량, 완료까지 필요한 자원, 종료 비용을 기준으로 대상을 고른다.

자원 선점은 희생자 선택(Victim selection), 이전 안전 상태로의 롤백(Rollback), 기아 방지 순으로 다룬다. 동일 프로세스가 반복해서 선점되지 않게 해야 하며, 이를 위해 체크포인트 저장, 롤백 비용, 자원 일관성을 함께 고려해야 한다.

시스템 성격에 따라 달라지는 대응 선택

전략	특징	오버헤드	자원 활용률	적용 사례
예방	조건 제거	높음	낮음	단순 시스템
회피	동적 검사	중간	중간	뱅킹 시스템
탐지+회복	발생 후 처리	낮음	높음	데이터베이스
무시	발생 가능성 낮음	없음	높음	Unix, Windows

선택에는 교착 상태 발생 빈도, 시스템 복잡도, 성능 요구사항, 복구 가능성이 영향을 준다.

데이터베이스 시스템에서는 Wait-For Graph를 주기적으로 검사하고 트랜잭션 타임아웃을 설정할 수 있다. 교착 상태가 확인되면 희생 트랜잭션을 롤백하거나 락 타임아웃을 자동으로 해제하는 방식으로 복구한다.

멀티스레드 프로그래밍에서는 락 획득 순서를 정해 순환 대기를 막고, 타임아웃 기반 락 획득을 사용한다. Try-lock 패턴과 데드락 프리 알고리즘도 회피 기법으로 사용할 수 있다.

⤢✕

교착 상태는 자원 경쟁 자체보다 자원 의존 관계가 순환한다는 점에서 문제가 된다. 데이터베이스나 임베디드 시스템에서는 여전히 중요한 설계 고려사항이며, 시스템 특성에 맞춰 예방, 회피, 탐지, 회복 전략을 조합해야 한다. Unix와 Windows처럼 발생 빈도가 낮다는 이유로 무시 전략을 쓰는 경우도 있다.