교착 상태 - (2) 해결 방법

교착 상태 해결 방법

크게 4가지가 있다.

해결 방법	설명
교착 상태 예방	교착 상태를 유발하는 네 가지 조건을 무력화하는 방식이다.
교착 상태 회피	교착 상태를 유발할 가능성이 있다고 판단되면 자원 할당을 중단하고 지켜보는 방식이다.
교착 상태 검출과 회복	제약을 가하지 않고 자원 할당 그래프를 모니터링하는 방식이다. 교착 상태가 발생하면 회복 단계가 진행된다.

교착 상태 예방

상호 배제 예방

시스템 내의 모든 자원을 공유할 수 있게 만들어 상호 배타적인 자원을 없애는 방식이다. 그러나 상호 배제를 적용하여 보호해야 하는 자원이 있어서 불가능하다.

비선점 예방

모든 자원을 빼앗을 수 있도록 만드는 방법이다. 그러나 임계구역 보호를 위해 잠금을 사용하는 경우 자원을 빼앗는 것이 불가능하며, 임계구역의 상호 배제를 보장할 수 없어서 사실상 불가능하다. 또한 어떤 기준으로 빼앗을지, 빼앗은 시간 중 얼마나 사용할지 결정하기가 어려우며, 아사 현상의 가능성이 있다.

아사 현상을 에이징으로 해결한다 하더라도, 우선순위가 낮은 프로세스가 몇 번의 양보 끝에 무조건 실행하기 때문에, 해당 프로세스의 자원이 비선점이 될 수가 있다. 따라서 비선점 조건도 무력화하기 어렵다.

점유와 대기 예방

프로세스가 자원을 하나라도 할당받으면 다른 자원을 기다리지 못하게 하는 방법이다. 즉, all or nothing 방식이다. 결국 프로세스는 자신이 사용하려는 모든 자원을 한번에 점유하여 실행하거나, 전부 반납하여 대기해야 한다. 자원에 대한 제약을 없애는 위의 2가지 방식과는 달리, 이 방식은 프로세스의 자원 사용 방식을 변화시키는 방식이다.

그러나 다음과 같은 단점이 있다.

a. 프로세스가 사용할 모든 자원을 자세히 알기 어렵다.

• 필요한 모든 자원을 확보하여 실행하더라도 추가로 필요한 자원이 생기면 이를 확보하기 어렵다.

b. 자원의 활용성이 떨어진다.

• 프로세스가 앞으로 사용할 자원까지 미리 선점하기 때문에 해당 자원을 사용하는 프로세스가 실행되지 못한다.

c. 많은 자원을 사용하는 프로세스가 불리하다.

• 모든 자원을 확보하기 어려워 아사 현상이 발생할 수 있다.

d. 실제로 구현하면 거의 모든 프로세스가 일괄 작업 방식으로 처리되어 시스템 효율이 떨어진다.

원형 대기 예방

점유와 대기를 하는 프로세스들이 원형을 이루지 못하도록 하는 방법이다. 해당 프로세스들이 한 줄로 늘어선다면 결국 맨 끝의 프로세스부터 실행될 것이다.

혹은 모든 자원을 한 방향으로만 사용하도록 설정하는 방법도 있다. 각 자원에 숫자를 부여하고 숫자가 커지는 순서, 작아지는 순서 중 한가지로만 자원을 할당받도록 하는 것이다.

아래 그림을 살펴보자. P1의 경우 1번을 할당받은 다음 2번을 할당받기 때문에 실행이 가능하지만, P2의 경우 2번을 할당받은 상태라 1번을 할당받을 수 없어 강제로 종료된다. 결국 P1이 2번도 할당받아 실행이 가능해진다.

교착 상태 회피

교착 상태가 발생하는 자원 할당량을 파악하여, 해당 수준 이하로만 자원을 할당하는 방법이다. 교착 상태가 발생하는 범위에 있으면 프로세스를 대기시킨다. 교착 상태 예방과는 달리 프로세스의 작업 방식을 제약하지 않고, 자원의 수를 조절하는 것이기 때문에 좀 더 유연하다.

교착 상태 회피는 자원의 총수와 현재 할당된 자원의 수를 기준으로 시스템을 안정 상태(safe state)와 불안정 상태(unsafe state)로 나누고, 안정 상태를 유지하도록 자원을 할당한다. 자원의 총수에 비해 할당된 자원 수가 클수록 불안정 상태가 커진다. 교착 상태는 불안정 상태의 일부분으로, 안정 상태에서 멀어질수록 교착 상태가 발생할 가능성이 높아진다.

은행원 알고리즘(banker's algorithm)

알고리즘 설명에 앞서 다음 변수들을 정의하자.

변수	설명
전체 자원(Total)	시스템 내 전체 자원 수
가용 자원(Available)	시스템 내 현재 사용 가능한 자원 수 (전체 자원 - 모든 프로세스의 할당 자원)
최대 자원(Max)	각 프로세스가 선언한 최대 자원 수
할당 자원(Allocation)	각 프로세스에 현재 할당된 자원 수
기대 자원(Expect)	각 프로세스가 앞으로 사용할 자원 수 (최대 자원 - 할당 자원)

자원을 할당하는 기준은 다음과 같다.

a. 각 프로세스를 살펴보면서 프로세스 하나라도 (해당 프로세스의 기대 자원) < (가용 자원) 일 경우, 해당 프로세스에 자원을 할당한다. 이 조건을 만족한다는 것은 가용한 자원을 사용하여 끝낼 수 있는 프로세스가 하나라도 존재한다는 의미이므로 안정 상태이다.

b. 모든 프로세스에 대하여 (프로세스의 기대 자원) > (가용 자원)인 경우 자원을 할당하지 않는다. 가용 자원을 사용하여 작업을 마칠 수 있는 프로세스가 없으므로 불안정 상태이다.

이러한 기준에 의한 안정 상태와 불안정 상태의 예시는 다음과 같다.

문제점

a. 프로세스가 자신이 사용할 모든 자원을 미리 선언해야 한다.

• 쉽지 않으며, 선언한다 하더라도 정확하지 않으면 교착 상태 회피에서도 교착 상태가 발생할 수 있다.

b. 시스템의 전체 자원 수가 고정적이어야 한다.

• 일시적인 고장이나 새로운 자원 추가가 빈번하므로 시스템 자원 수는 유동적이다.

c. 자원이 낭비된다.

• 프로세스에 따라 최대 자원을 사용하지 않고 작업을 마치는 경우가 존재하며, 실제로 교착 상태가 발생하지 않는데도 발생할 것으로 예상하여 자원 할당에 제약을 준다.

교착 상태 검출

운영체제가 교착 상태 발생 여부를 계속 주시하여, 교착 상태가 발견되면 회복 단계로 넘어가는 방식이다. 교착 상태에 대한 해결 방법 중 가장 현실적인 방법이다. 크게 타임아웃을 이용하는 방법과 자원 할당 그래프를 이용하는 방법으로 나뉜다.

타임아웃 이용

일정 시간 동안 작업이 진행되지 않은 프로세스를 교착 상태가 발생한 것으로 간주하여 종료하는 방법이다. PC를 사용할 때 응답이 없는 프로그램을 종료하는 것이 대표적인 예이다. 특별한 알고리즘 없이 쉽게 구현이 가능하지만 다음과 같은 단점이 있다.

a. 엉뚱한 프로세스가 강제 종료될 수 있다.

• 모든 프로세스가 교착 상태 때문에 멈춘 것이 아니기 때문이다.

b. 모든 시스템에 적용할 수 없다.

• 한 OS 내에서 동작하는 프로세스 들의 경우 OS가 상태를 감시하기 때문에 타임아웃 적용이 가능하지만, 분산 데이터베이스 같이 여러 시스템으로 구성되어 있는 경우 이 방법을 적용하기 어렵다.

위와 같은 단점에도 불구하고 이 방법은 대부분의 OS와 DB에서 사용한다. 자주 발생하지 않는 교착 상태를 위해 자원 할당 그래프를 유지하는 것은 어렵기 때문이다.

데이터를 다루는 도중 타임아웃으로 프로세스가 종료되면 데이터의 일관성이 깨질 수 있다. 이를 해결하기 위해 체크포인트(check point)와 롤백(rollback)을 사용한다. 체크포인트를 설정하면 현재의 시스템 상태가 하드디스크에 저장되는데, 이 때 저장되는 데이터를 스냅샷(snapshot)이라 한다. 이후 작업을 하다 문제가 발생하면 과거의 체크포인트로 돌아가기 위해 스냅숏을 복원하는데, 이를 롤백이라 한다. 이 방법을 사용하는 예로 '특정 시점으로 복원'이 있다.

자원 할당 그래프 이용

자원을 요청하거나 할당할 때마다 OS가 자원 할당 그래프를 갱신하여 사이클의 존재 여부로 교착 상태를 판단하는 방법이다. 프로세스의 작업 방식을 제한하지 않으면서 교착 상태를 정확하게 파악하는 것이 장점이지만, 그래프를 유지, 갱신, 검사하는 작업으로 인한 오버헤드가 발생하는 단점이 있다. 또한 다중 자원을 사용하는 경우 사이클이 있다고 해서 모두 교착 상태라고 판단할 수 없기 때문에 다른 방식이 필요하다.

교착 상태 회복

검출 이후에 실행되는 작업으로, 교착 상태를 유발한 프로세스를 강제 종료한다. 아래와 같은 두가지 방법으로 강제 종료한다.

a. 교착 상태를 일으킨 모든 프로세스를 동시에 종료

• 종료된 모든 프로세스들이 동시에 작업을 시작하면 다시 교착 상태가 발생할 수 있기 때문에, 다시 실행할 때 일정한 기준에 따라 순차적으로 실행해야 한다.

b. 교착 상태를 일으킨 프로세스 중 하나를 골라 순서대로 종료

• 프로세스를 하나씩 종료하면서 나머지 프로세스의 상태를 파악하는 방법이다. 종료할 때 기준은 우선순위, 작업 시간, 자원 사용량 등이 있다.

회복 단계에서는 강제 종료 뿐만 아니라 강제 종료된 프로세스가 다시 실행되기 전 시스템을 복구해야 한다. 시스템 복구는 각 명령어가 실행될 때마다 체크포인트를 만드는 방법을 사용한다.

다중 자원과 교착 상태 검출

다중 자원을 사용하는 경우 사이클이 교착 상태를 보장하지 않는다. 따라서 교착 상태 검출을 위해 대기 그래프와 그래프 감소를 사용한다.

대기 그래프와 그래프 감소

대기 그래프(wait-for graph)는 자원 할당 그래프에서 프로세스들 간의 기다리는 관계만 나타낸 그래프이다. 그래프 감소(graph reduce)는 대기 그래프에서 기다리는 자원이 없는 프로세스, 즉 자신에게서 나가는 화살표가 없는 프로세스부터 연속적으로 지워가는 작업을 말한다. 그래프 감소를 완료한 후에도 사이클이 남아 있다면 교착 상태가 발생한 것이다.

예시로 다음과 같은 자원 할당 그래프를 살펴보자. 이 중에서는 다중 자원으로 R2가 있다.

대기 그래프로 바꾸면 다음과 같다.

이제 그래프 감소를 수행해보자. 우선 P2는 기다리는 자원이 없으므로 제거한다. 그러면 P1은 R2를 할당받기 때문에 기다리는 자원이 없다. 따라서 P1도 지운다. 그러면 사이클이 사라진다.

Reference

쉽게 배우는 운영체제