교착 상태 (정보관리기술사)

교착 상태란

교착 상태는 둘 이상의 프로세스가 서로 상대가 점유한 자원을 기다리며 멈춘 상태다.

컴퓨터에서는 프로세스가 프린터와 디스크를 각각 쥐고 상대가 쥔 것을 기다리면 둘 다 멈춘다.

코프만의 네 가지 조건

1971년 코프만은 교착 상태가 발생하려면 다음 네 조건이 동시에 성립해야 함을 보였다.

상호배제, 점유와 대기, 비선점, 순환 대기가 그 네 조건이다. 자원을 한 번에 한 프로세스만 쓰면 상호배제다.

다만 네 조건은 독립적이지 않다. 순환 대기는 점유와 대기, 비선점이 함께 있어야 성립한다.

은행가 알고리즘의 자료구조

은행가 알고리즘은 시스템 전체의 자원 상태를 여섯 가지 자료구조로 기록한다.

Need 는 계산으로 얻는 값이다. 최대 요구량에서 현재 할당량을 뺀 잔여 요구량이다.

Need[i][j] 는 프로세스 Pi 가 자원 Rj 를 앞으로 더 요청할 수 있는 개수다.

안전 상태 판정 예제

예제로 확인해 보자. 총 자원은 12개이고 프로세스는 P0, P1, P2 세 개다.

할당된 자원은 5+2+2=9개이므로 가용 자원은 12−9=3개다.

Need 가 Work 이하인 P1 부터 실행할 수 있다. 종료 후 Work 는 5가 된다.

이어서 P0 의 Need 5 가 Work 5 이하이므로 실행되고, Work 는 10이 된다.

P2 의 Need 7 도 Work 10 이하라 실행된다. 모든 프로세스가 완료되므로 이 상태는 안전 상태다.

교착 상태 처리 기법

교착 상태를 다루는 방법은 예방, 회피, 발견과 회복으로 나뉜다.

예방은 조건을 원천 차단하므로 교착이 생기지 않지만 자원 활용이 떨어진다.

은행가 알고리즘은 자원 요청 때마다 안전 상태를 검사하는 회피 기법이다. 안전 상태가 유지될 때만 할당한다.

정답은 회피다. 은행가 알고리즘은 할당 전에 안전 상태 여부를 검사하는 방식이다.

한계와 실무 적용

은행가 알고리즘에는 다음과 같은 한계가 있다.

최대 요구량을 미리 신고해야 하고, 프로세스 수와 자원 종류 수가 일정해야 한다.

요청마다 안전성 검사를 하므로 오버헤드가 생기고, 동적 환경에는 적용이 어렵다.

그래서 실무에서는 순환 대기를 막는 설계와 락 획득 순서 규칙을 더 많이 쓴다.