교착상태 필요조건

지난번에는 교착상태의 정의까지 공부했습니다. 그렇다면 언제 교착상태가 발생하는지에 대해서 알아보겠습니다. 다음 4가지 조건이 모두 발생할 때 교착상태는 발생합니다.

• 상호 배제(mutual exclusion) : 한 프로세스가 사용하는 자원은 다른 프로세스와 공유할 수 없는 배타적인 자원이어야 합니다.
• 비선점(non-preemptive) : 한 프로세스가 사용 중인 자원은 중간에 다른 프로세스가 빼앗을 수 없는 비선점 자원이어야 합니다.
• 점유와 대기(hold and wait) : 프로세스가 어떤 자원을 할당 받은 상태에서 다른 자원을 기다리는 상태여야 합니다.
• 원형 대기(circular wait) : 점유와 대기를 하는 프로세스 간의 관계가 원을 이루어야 합니다.

위 4가지 조건 중 상호 배제와 비선점 조건은 자원이 어떤 특징을 가지고 있는지 나타냅니다. 사용하는 자원을 동시에 공유할 수 없고 중간에 빼앗을 수도 없다면 자원을 가진 프로세스가 자원을 내놓을 때까지 무작정 기다리는 교착상태가 발생합니다. 점유와 대기, 원형 대기 조건은 프로세스가 어떤 행위를 하고 있는지를 나타냅니다. 프로세스가 자원을 점유 및 대기하고 있는 상태에서 다른 프로세스를 방해하는 방향이 원을 이루면 서로 양보하지 않기 때문에 교착상태가 발생합니다.

그렇다면 이러한 교착상태는 어떤 방식으로 해결할 수 있을까요?

교착상태 해결 방법

교착상태를 해결하기 위해서 사람들은 크게 3가지 방법을 생각해냈습니다.

• 교착상태 예방 : 교착상태를 유발하는 네 가지 조건이 발생하지 않도록 무력화하는 방법이지만 이 방법은 실효성이 적습니다.
• 교착상태 회피 : 자원 할당량을 조절하여 교착 상태를 해결하는 방식입니다. 자원을 할당하다가 교착상태를 유발할 가능성이 있다고 판단되면 자원 할당을 중단하고 지켜보는 것 입니다. 그러나 자원을 얼마나 할당해야 교착상태가 발생하지 않는다는 보장이 없기 때문에 실효성이 적습니다.
• 교착상태 검출과 회복 : 교착상태 검출은 어떤 제약을 가하지 않고 자원 할당 그래프를 모니터링하면서 교착상태가 발생하는지 살펴보는 방법입니다. 만약 교착상태가 발생하면 교착상태 회복 단계가 진행이 됩니다. 가장 현실적인 교착상태 해결 방법입니다.

이제 각 방법에 대해 자세히 공부해보겠습니다.

교착상태 예방

위에서 교착상태 예방은 교착상태를 유발하는 네 가지 조건이 발생하지 않도록 하는 것이라고 했습니다.

상호배제 예방 : 시스템 내에 있는 상호 배타적인 모든 자원을 없애버리는 방법입니다. 시스템 내의 모든 자원을 공유할 수 있다면 교착상태는 발생하지 않습니다. 하지면 현실적으로 모든 자원을 공유할 수 없으며 상호배제를 적용하여 보호해야 하는 자원이 있습니다. 자원을 공유하게 되면 임계 구역이 보호받지 못하는 문제가 발생하기도 합니다.

비선점 예방 : 모든 자원을 빼앗을 수 있도록 만드는 방법입니다. 하지만 임계 구역을 보호하기 위해 잠금을 사용하면 자원을 빼앗지 못할 뿐더러 어떤 기준으로 자원을 빼앗을지, 빼앗은 시간 중 얼마나 사용할지 등을 결정하기 어렵고 이로 인해 우선 순위가 낮은 프로세스는 아사(starvation) 현상이 발생할 수 있습니다. 에이징을 사용해도 특정 조건 이상일 때 한 프로세스가 계속 자원을 사용할 수 있기 때문에 비선점 효과를 일으켜 교착상태를 일으킬 수 있습니다.

점유와 대기 예방 : 프로세스가 자원을 점유한 상태에서 다른 자원을 기다리지 못하게 하는 방법입니다. 전부 할당하거나 아예 할당하지 않는(all or nothing) 방식을 적용합니다. 프로세스는 시작 초기에 자신이 사용하려는 모든 자원을 한꺼번에 점유하거나 그렇지 못할 경우 자원을 모두 반납해야 합니다. 앞에서 살펴본 상호 배제 예방과 비선점 예방은 자원에 대한 제약을 풀어버리는 것인데 임계구역으로 보호 받는 자원에 대한 제약을 풀기는 어렵습니다. 점유와 대기 예방은 자원이 아닌 프로세스의 자원 사용 방식을 변화시켜 교착상태를 처리한다는 점에서 의미가 있습니다.
하지만 점유와 대기 예방은 프로세스가 자신이 사용하는 모든 자원은 자세히 알기 어렵다는 점과 자원의 활용성이 떨어진다는 점, 많은 자원을 사용하는 프로세스가 적은 자원을 사용하는 프로세스보다 자원 선점에 불리한 점, 결국 일괄 작업 방식으로 진행된다는 단점이 있습니다.

원형대기 예방 : 점유와 대기를 하는 프로세스들이 원형을 만들지 못하도록 막는 방법입니다. 자원을 한 방향으로만 사용하도록 설정함으로써 원형대기를 예방할 수 있습니다. 즉 모든 자원에 숫자를 부여하고 숫자가 큰 방향으로만 자원을 할당하는 것 입니다. 원형 테이블에서 식사하던 것을 일렬로 줄세워 식사하는 것과 같습니다. 숫자가 작은 자원을 잡은 상태에서 큰 숫자를 잡는 것은 허용하지만 숫자가 큰 자원을 잡은 상태에서 작은 숫자를 잡는 것은 허용하지 않습니다. 이렇게 하면 원형대기는 사라지지만 프로세스 작업진행의 유연성이 사라지고 큰 번호 자원을 사용한 후 작은 번호의 자원을 사용할 수 없기 때문에 자원에 번호를 부여하는데 매우 신중해야 한다는 단점이 있습니다.

교착상태 회피

교착상태 회피는 프로세스에 자원을 할당할 때 어느 수준 이상의 자원을 나누어 주면 교착상태가 발생하는지 파악해 그 수준 이하로 자원을 나누어 주는 방법입니다. 교착상태가 발생하지 않는 범위 내에서만 자원을 할당하고 교착상태가 발생하는 범위에 있으면 프로세스를 대기시킵니다. 교착상태 회피는 시스템의 운영방식에 변경을 가하지 않기 때문에 교착상태 예방보다 유연합니다. 교착상태 회피는 자원의 총 개수와 할당된 자원의 개수를 기준으로 시스템을 안정상태와 불안정상태로 나누고 시스템이 안정상태를 유지하도록 자원을 할당합니다. 아래의 그림과 같이 할당된 자원이 적으면 안정상태가 크고 할당된 자원이 커질수록 불안정상태도 커집니다. 교착상태도 불안정상태의 일부이며 불안정상태가 커질수록 교착상태의 발생가능성이 증가합니다. 이렇게 교착상태 회피는 안정상태를 유지할 수 있는 범위 내에서 자원을 할당함으로써 교착상태를 회피합니다.

교착상태 회피에는 다익스트라가 제안한 은행원 알고리즘 방식이 대표적으로 쓰입니다. 예를 들어 어떤 음식점에 우동 10인분과 스파게티 20인분을 만들 수 있는 재료가 준비되어 있다고 가정해봅시다. 은행원 알고리즘에서는 30명을 기준으로 예약을 받지 않고 10명 이내로 예약을 받습니다. 왜냐하면 10명이 넘어갔을 때 손님 모두가 우동을 시키는 경우 우동의 재료는 10인분 밖에 없기 때문에 우동의 재료가 소진되기 때문입니다. 이처럼 은행원 알고리즘은 최악의 경우를 기준으로 함으로써 문제상황을 철저히 회피하여 교착상태를 막습니다. 은행원 알고리즘은 다음과 같은 변수를 가집니다.

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

은행원 알고리즘에서는 각 프로세스의 기대자원과 비교하여 가용자원이 크거나 같으면 자원을 할당합니다. 가용자원이 기대자원보다 크다는 것은 그 자원을 사용해 작업을 종료할 프로세스가 있다는 의미이므로 안정상태입니다.
이러한 교착상태 회피에도 여러 문제점이 존재합니다. 먼저 프로세스가 자신이 사용할 모든 자원을 미리 선언해야 합니다. 또한 미리 선언한 자원이 정확하지 않으면 교착상태 회피에서도 교착상태가 발생할 수 있습니다. 안정상태나 불안정상태를 파악하려면 시스템 자원의 수가 고정적이어야 합니다. 그러나 일시적인 고장이나 새로운 자원이 추가되는 경우가 자주 발생해 매우 유동적이기 때문에 이를 알기 어렵습니다. 위의 음식점에서 음식은 총 30인분이 준비되어 있지만 은행원 알고리즘에 의하면 10명만 받기 때문에 20인분의 음식은 버려지게 됩니다. 즉 자원이 낭비됩니다.

교착상태 검출

교착상태 예방은 실제로 구현하기 어렵고 교착상태 회피는 구현할 수는 있지만 자원을 낭비하는 등의 여러가지 문제점이 있습니다. 이에 따라 교착상태 검출이라는 가장 현실적인 해결방법이 등장했습니다. 교착상태 검출은 운영체제가 프로세스의 작업을 관찰하면서 교착상태 발생여부를 계속 주시하는 방법입니다. 만약 교착상태가 발견되면 이를 해결하기 위해 교착상태 회복 단계를 밟습니다. 그렇다면 운영체제는 어떤 방식으로 교착상태 발생여부를 판단할 수 있을까요?

가장 간단한 방법이 타임아웃을 통한 방식입니다. 일정시간동안 작업이 진행되지 않는 프로세스를 교착상태가 발생한 것으로 처리하는 방법입니다. 쉽게 구현이 가능하지만 교착상태로 인한 타임아웃이 아닌데도 프로세스가 강제 종료가 될 수 있고 하나의 운영체제 내에서 동작하는 프로세스들은 그 상태를 운영체제가 감시하기 때문에 타임아웃 방법을 적용할 수 있지만 분산 DB와 같이 데이터가 여러 시스템에 나뉘어 있고 각 시스템이 네트워크로 연결되어 있는 경우에는 원격지에 있는 프로세스의 응답이 없는 것이 교착상태 때문인지 네트워크 때문인지와 같이 원인을 정확히 파악할 수 없습니다. 이러한 문제에도 불구하고 타임아웃은 대부분의 데이터베이스와 운영체제에서 많이 선호합니다. 왜 그럴까요?

데이터베이스는 일관성이 깨지면 안되기 때문에 교착상태 처리가 운영체제보다 복잡합니다. 데이터를 조작할 때는 반드시 잠금을 얻은 후 작업을 시작해야 하고 만약 여러 개의 잠금을 얻어 작업을 진행하다가 타임아웃으로 프로세스가 종료되면 일부 데이터에 문제가 발생할 수 있습니다. 이러한 문제를 해결하기 위해 DB에서는 체크포인트(check point)와 롤백(roll back)을 사용합니다.

체크포인트는 작업을 하다가 문제가 발생하면 저장된 상태로 되돌아오기 위한 표시이고 체크포인트를 설정하면 현재 시스템 상태가 하드디스크에 저장되는데 이러한 데이터를 스냅숏이라고 합니다. 롤백은 작업을 하다가 문제가 발생하여 과거의 체크포인트로 되돌아가는 것을 말합니다. 롤백이 일어나면 저장된 스냅숏을 복원하여 시스템을 체크포인트 시점으로 되돌립니다.

타임아웃이 아닌 또다른 방법으로는 자원할당 그래프를 이용하여 교착상태를 검출하는 방법이 있습니다. 운영체제는 자원을 요청하거나 할당할 때마다 자원할당 그래프를 갱신하는데 이때 사이클이 발생하면 교착상태가 검출된 것으로 판단합니다. 위의 (a)그래프의 경우 사이클이 존재하지 않지만 (b)그래프의 경우 사이클이 존재하므로 (b)그래프는 교착상태가 있는 자원할당 그래프입니다.

교착상태 회복

위의 방법을 통해 교착상태가 검출되었다면 어떻게 이를 해결할까요? 교착상태 회복단계에서는 교착상태를 일으킨 프로세스를 강제로 종료합니다. 이 때 두 가지 방식으로 종료를 할 수 있는데 첫 번째는 교착상태를 유발한 모든 프로세스를 동시에 종료하는 것이고 두 번째는 교착상태를 일으킨 프로세스 중 하나를 선택해 순서대로 종료하는 것입니다. 교착상태를 유발한 모든 프로세스를 종료하는 경우 종료된 프로세스들이 동시에 작업을 다시 시작하면 교착상태를 다시 일으킬 가능성이 큽니다. 따라서 다시 실행할 때는 순차적으로 실행해야 하며 실행 순서를 정하는 기준이 필요합니다. 교착상태를 일으킨 프로세스 중 하나를 선택해 순서대로 종료를 할 때에는 어떤 프로세스부터 종료할 것인지 기준이 필요합니다. 우선순위가 낮은 프로세스를 먼저 종료하거나 우선순위가 같은 경우 작업시간이 짧은 프로세스를 먼저 종료하거나 위의 두 조건이 같을 경우 자원을 많이 사용하는 프로세스를 먼저 종료하는 것과 같은 기준이 있을 수 있습니다.