교착상태와 기아상태

개요

교착상태는 시스템 관점에서 자원의 요구가 서로 뒤엉킨 상태를 말한다. 한 프로세스 집합 안에서 프로세스들이 서로 발생시켜야 할 사건(event)을 상대방에게 미룬 채 기다리고 있는 상태이며, 둘 이상의 작업이 보류 상태에 놓인 채 중요한 자원을 확보하려고 기다릴 때 나타난다. 제한된 자원의 이용률을 높이고 시스템 효율을 끌어올리기 위해 사용하는 병행처리 기술과 자원 공유가 낳는 부작용인 셈이다.

초기 일괄처리시스템

초기 일괄처리시스템에서는 사용자가 작업제어카드에 작업을 완료하는 데 필요한 자원을 미리 명시했기 때문에 교착상태가 자주 발생하지 않았다. 운영체제는 요청한 자원이 준비 큐로 이동하기 전에 사용 가능 여부를 확인한 뒤 할당했고, 자원이 확보되지 않으면 작업 자체가 준비 큐로 이동하지 못했으므로 교착상태가 생기지 않았다.

대화식 시스템

반면 대화식 시스템은 동적으로 자원을 공유해 이용률을 높이는 과정에서 오히려 교착상태가 발생한다.

DVD 드라이브와 프린터가 각각 하나씩 있다고 하자.

• Process P: DVD 드라이브를 점유한 채 프린터를 요청한다.
• Process Q: 프린터를 점유한 채 DVD 드라이브를 요청한다.

테이프 드라이브가 3개 있다고 하자.

• Process P, Q, R이 각각 테이프 드라이브 하나씩을 점유한다.

프로세스 자원 이용 순서

프로세스가 자원을 다루는 과정은 요청, 사용, 해제 세 단계로 이루어진다. 먼저 자원을 요청하는데, 요청이 즉시 받아들여지지 않으면 다른 프로세스가 이미 사용 중이라는 뜻이므로 할당받을 때까지 대기한다. 자원을 받으면 사용하고, 사용을 마치면 할당받았던 자원을 해제해 돌려준다.

교착상태 발생 사례

• 파일 요청: 한 파일로 작업이 실행되는 동안, 같은 파일에 대한 다른 작업의 점유 요청이 받아들여지면 교착상태가 발생한다.
• 전용장치 할당: 두 사용자(P1, P2)가 각각 테이프 드라이브 1대씩 사용하며 한 테이프에서 다른 테이프로 복사하려 할 때 교착상태가 발생한다.
• 스풀링 시스템: 디스크에 할당된 스풀 공간의 출력이 끝나지 않은 상태에서 다른 작업이 남은 스풀 공간을 모두 차지하면 교착상태가 발생한다.
• 디스크 공유: 디스크는 대표적인 공유 자원이라, 사용에 대한 통제가 없으면 교착상태가 발생할 수 있다.
• 네트워크: 트래픽이 몰리거나 입출력 버퍼 공간이 부족한 네트워크 시스템이 메시지 흐름을 제어할 적절한 프로토콜을 갖추지 못하면 교착상태가 발생한다.

교착상태 발생 조건

교착상태는 상호배제, 점유와 대기, 비선점, 순환대기라는 네 조건이 동시에 만족될 때 발생한다.

강 건너기 교착상태로 이 네 조건을 직관적으로 이해할 수 있다. 여러 개의 돌로 된 징검다리가 놓인 강을 건넌다고 하자. 강을 건너는 사람을 프로세스(P), 징검다리의 돌을 자원(Data)이라 하면, 두 사람이 서로 다른 방향에서 동시에 출발해 강 중간에서 마주쳤을 때 이를 ‘교착상태가 발생했다’고 말할 수 있다. 돌을 딛는 것은 자원 할당, 발을 떼는 것은 자원 해제에 해당하므로 같은 돌을 동시에 딛으려 하면 교착상태가 생긴다. 각 사람은 돌 하나를 딛은 채 다음 돌을 요구하므로 점유와 대기 조건을 만족하고, 딛고 있는 돌을 강제로 치울 수 없으므로 비선점 조건을 만족하며, 왼쪽에서 오는 사람은 오른쪽 사람을, 오른쪽에서 오는 사람은 왼쪽 사람을 기다리므로 순환대기 조건까지 만족한다.

이 상황을 해결하는 방법은 세 가지다. 둘 중 한 사람이 되돌아가거나(복귀), 강을 건너기 전에 상대편 쪽을 미리 확인하고 출발하거나, 강의 한쪽 편에 우선권을 부여하는 것이다.

교착상태 해결 기법

교착상태에 대응하는 전략은 크게 세 가지다: 시스템이 애초에 교착상태에 빠지지 않도록 예방하는 것, 가능한 교착상태를 회피하는 것, 그리고 교착상태를 허용하되 다시 회복할 수 있게 하는 것(구현이 까다롭고 오버헤드도 크다).

예방 기법

예방 기법은 상호배제 문제를 우선 고려한다. 하벤더는 1986년, 상호배제를 제외한 나머지 세 조건을 막는 기본 방법을 제안했다. 첫째, 각 프로세스는 필요한 모든 자원을 한 번에 요청해야 하며 요청한 자원을 전부 받기 전까지는 작업을 진행할 수 없다. 둘째, 어떤 자원을 점유한 프로세스의 추가 요구가 더 이상 받아들여지지 않으면 점유한 자원을 모두 반납하고, 필요할 때 다시 요구해야 한다. 셋째, 모든 프로세스에 자원을 순서대로 할당해야 한다. 각 자원 유형에 할당 순서를 미리 부여하고, 그 순서에 따라서만 자원을 요구하게 한다.

상호배제 조건 방지

상호배제 조건은 자원을 공유할 수 없다는 전제에서 출발한다. 이 조건 자체를 거부하면 사실상 교착상태를 예방할 수 없다. 예를 들어 파일 쓰기는 배타적인 접근만 허용되어야 하기 때문이다.

점유와 대기 조건 방지

최대 자원 할당 방식은 프로세스가 작업을 수행하기 전에 필요한 모든 자원을 요청하고 확보하도록 한다. 보류 상태에서는 프로세스가 자원을 점유할 수 없으므로 대기 조건 자체가 성립하지 않는다.

비선점 조건 방지

할당 자원의 선점권을 제외하는 방식은, 어떤 자원을 가진 프로세스가 새로운 자원을 요청했을 때 기다려야 한다면 현재 가진 자원을 모두 해제하도록 한다. 프로세스가 작업을 다시 시작하려면 요청한 새 자원과 이전에 해제한 자원을 함께 확보해야 한다. 이 방식은 작업 상태를 쉽게 저장하고 복구할 수 있을 때, 혹은 상황이 자주 발생하지 않을 때만 효과적이다.

대안으로는, 프로세스가 자원을 요청할 때 사용 가능 여부를 먼저 검사하는 방법이 있다. 사용 가능하면 바로 할당하고, 그렇지 않다면 그 자원을 점유하고 있는 대기 프로세스가 있는지 검사한다. 대기 프로세스가 선점하고 있다면 자원을 해제해 요청 프로세스에 넘기고, 실행 중인 프로세스가 점유하고 있다면 요청 프로세스는 대기한다.

순환 대기 조건 방지

계층적 요구 기법은 모든 자원에 일련의 순서를 부여하고, 각 프로세스가 오름차순으로만 자원을 요청하도록 강제한다. 이렇게 하면 순환대기 자체가 성립할 수 없어 교착상태를 예방할 수 있다. 다만 정해진 순서와 다르게 자원을 요구해야 하는 작업이 있다면 자원 낭비로 이어질 수 있다. 자원 형태 집합을 R = {R1, R2, …, Rn}이라 하면, 각 자원 형태에 고유한 숫자를 부여해 순서를 정한다.

교착상태 회피 기법

프로세스의 시작을 거부하는 방법은, 어떤 프로세스의 요구가 교착상태를 일으킬 수 있다고 판단되면 그 프로세스의 시작 자체를 막는다. 현재 수행 중인 모든 프로세스의 최대 자원 요구량과 새 프로세스의 최대 요구량을 합쳤을 때 시스템이 이를 수용할 수 있어야만 새 프로세스를 받아들인다.

자원 할당을 거부하는 방법은, 요청한 자원을 할당했을 때 교착상태가 발생할 가능성이 있다면 그 자원을 아예 할당하지 않는다. 이를 흔히 은행가 알고리즘이라 부른다.

이런 회피 기법이 제대로 작동하려면 자원 요구 시점에 대한 추가 정보가 필요하다. 각 프로세스의 요청과 해제 순서를 정확히 파악하고 있어야 요청에 따라 대기시킬지 결정할 수 있고, 프로세스별로 필요한 정보의 양과 종류에 따라 다양한 회피 알고리즘을 적용할 수 있다. 프로세스가 요청할 자원의 최대치를 미리 알 수 있다면, 시스템이 교착상태에 빠지지 않는다는 것을 보장하는 알고리즘도 만들 수 있다.

이 알고리즘은 시스템이 순환대기 조건에 빠지지 않도록 자원 할당 상태를 계속 검사한다. 자원 할당 상태는 사용 가능한 자원의 수, 이미 할당된 자원의 수, 프로세스들의 최대 요구 수로 정의되며, 이 상태는 안정 상태와 불안정 상태로 나뉜다. 안정 상태는 각 프로세스에 최대치까지 자원을 할당할 수 있어 교착상태를 방지할 수 있는 상태다. 불안정 상태는 프로세스의 자원 할당·해제 순서가 안정 상태처럼 명확히 존재하지 않는 상태를 말한다. 교착상태는 언제나 불안정 상태이지만, 모든 불안정 상태가 곧 교착상태인 것은 아니다.

교착상태 탐지

쇼사니와 포크만은 교착상태를 탐지하기 위해 다음과 같은 자료구조를 제안했다.

• Available: 자원 형태마다 사용 가능한 수를 나타내는 길이 M의 벡터.
• Allocation: 각 프로세스에 현재 할당된 자원 형태별 수를 나타내는 n×m 행렬.
• Request: 각 프로세스의 현재 요청을 나타내는 n×m 행렬. Request(i, j)는 프로세스 pi가 자원 형태 rj를 k개 더 요청한다는 뜻이다.

교착상태 회복 기법

순환대기에서 벗어나려면 프로세스를 한 개 이상 중지시키거나, 교착상태에 놓인 프로세스들로부터 자원을 회수하는 방법을 쓴다. 프로세스를 중지하는 방식에는 두 가지가 있는데, 교착상태에 놓인 프로세스를 모두 한꺼번에 중지시키거나 한 프로세스씩 순차적으로 중지시키는 방법이다. 어느 쪽이든 시스템은 정지된 프로세스에 할당됐던 모든 자원의 해제를 요구한다.

부분 종료 방식에서는 어느 프로세스를 중지시킬지 결정해야 하는데, 이는 프로세서 스케줄링과 비슷한 정책 결정 문제다. 프로세스를 중지시키는 데 드는 비용을 최소화하는 방법을 찾는, 사실상 경제적인 문제이기도 하다.

자원 선점 방식은 프로세스의 자원을 강제로 선점해, 교착상태가 해결될 때까지 그 자원을 다른 프로세스에 할당해 사용한다. 이때는 어떤 자원을 선점할지 선택하는 문제, 자원을 되돌려주는 복귀 문제, 그리고 특정 프로세스가 자원을 계속 빼앗기며 작업을 끝내지 못하는 기아 문제를 함께 고려해야 한다.

기아상태

기아상태는 프로세스가 자신의 작업을 끝내 완료하지 못하는 상태로, 교착상태를 예방하려고 자원을 할당하는 과정에서 나타나는 부작용이다.

다익스트라의 식사하는 철학자 문제가 이를 잘 보여준다. 철학자 5명이 대부분의 시간을 생각하고 먹는 데 쓰며, 의자 5개로 둘러싸인 원형 테이블을 공유한다. 테이블 중앙에는 음식이 있고 포크 5개가 놓여 있다. 지역 풍습에 따라 철학자는 포크 2개로 식사해야 하므로, 5명이 동시에 식사할 수는 없고 최대 2명만 동시에 식사할 수 있다. 한 철학자가 생각 중일 때 다른 철학자는 간섭하지 않는다. 배고픈 철학자는 왼쪽과 오른쪽 포크를 들어야 식사를 시작할 수 있는데, 한 번에 포크 하나만 집을 수 있어 왼쪽 포크를 먼저 집고 오른쪽 포크를 나중에 집는다. 이웃 철학자가 이미 들고 있는 포크는 집을 수 없고, 두 포크를 모두 갖게 되면 식사를 시작하며, 식사를 마치면 포크 2개를 내려놓고 다시 생각에 잠긴다. 모든 철학자가 동시에 왼쪽 포크만 집으면, 다섯 명 모두 오른쪽 포크를 영원히 기다리는 교착상태에 빠진다.

이 문제는 포크를 세마포어로 표현해 해결할 수 있다. 철학자는 포크에 해당하는 세마포어에 P 연산을 수행한 뒤에야 포크를 집을 수 있고, 포크를 내려놓을 때는 그 세마포어에 V 연산을 수행한다.

교착상태를 막는 다른 해결 방안으로는 철학자 4명만 테이블에 동시에 앉게 하는 방법, 양쪽 포크를 모두 사용할 수 있을 때만 포크를 집도록 허용하는 방법(임계영역 활용), 그리고 비대칭 해결법으로 홀수 번째 철학자는 왼쪽 포크를 먼저, 짝수 번째 철학자는 오른쪽 포크를 먼저 집게 하는 방법이 있다.