컴퓨터 시스템의 다중 프로그래밍 환경에서는 여러 프로세스들이 한정된 자원을 사용하기 위해 경쟁하고 있으며, 한 프로세스가 자원을 요청했을 때 해당 자원이 사용이 불가능한 상태라면 교착상태가 발생 하게 됩니다. 즉, 요청한 자원을 다른 프로세스가 점유하고 있고, 점유하고 있는 프로세스도 다른 자원에 대해 대기 상태에 있기 때문에 두 프로세스가 대기 상태에서 벗어날 수 없는 상황을 교착상태(deadlock) 라고 합니다.
본 강의에서는 운영체제 수준에서 교착상태를 예방하거나 다룰 수 있는 방법들을 논의 합니다.
시스템 모델
교착 상태에 대해 이야기 하기 전에 시스템에 대한 이야기를 잠깐 하고 넘어갑시다. 시스템은 경쟁하는 프로세스들 사이에 분배되어야 할 유한한 자원들로 구성 이되며, 여러 프로세스들을 해당 자원을 점유하기 위해 서로 경쟁 구도에 놓여있습니다. 메모리 공간, CPU 주기, 파일, 입출력 장치 등이 이러한 자원 유형이 예입니다. 프로세스가 자원을 사용하기 위해서는 반드시 사용하기 전에 요청 을 해야 하고 사용 후에는 반드시 방출해야 합니다. 즉, 정상적은 작동 모드에서 프로세스는 다음 순서로만 자원을 사용할 수 있습니다.
1. 요청
프로세스는 자원을 요청하고, 즉시 허용되지 않는 경우 자원을 얻을 때까지 대기상태에 놓이게 됩니다.
2. 사용
프로세스는 자원에 대해 작업을 수행합니다.
3. 방출
프로세스가 자원을 다 사용하였다면 방출합니다.
이렇게 경쟁 구도에 놓인 프로세스들은 자원을 요청하는 시점에 해당 자원이 다른 프로세스에 의해 점유되어 있으면 대기상태에 놓이게 되고 각 프로세스와 자원들이 서로 꼬리를 물며 자원을 대기하게 되는 경우 이를 교착상태 에 놓여있다고 합니다. 즉, 한 프로세스 집합 내 모든 프로세스가 그 집합 내 다른 프로세스에 의해서만 발생될 수 있는 사건을 기다린다면, 그 프로세스 집합은 교착상태 에 있는 것입니다.
다중 스레드 프로그램은 공유 자원을 위해 경쟁하는 다수의 스레드가 있을 수 있기 때문에 교착상태의 좋은 예 가 됩니다.
교착 상태의 특징
시스템 내에서 프로세스와 자원이 어떤 관계를 가지는 지 또, 교착 상태가 어떤 상황에서 발생하는 지를 알아보았으므로 이제 교착 상태 가 가지는 특징에 대해 알아봅시다.
교착 상태에서 프로세스들은 결코 실행을 끝낼 수 없으며, 시스템 자원이 묶여 있어서 다른 작업을 시작하는 것도 불가능 하며, 이런 교착 상태는 다음의 필요 조건 을 만족합니다.
- 상호배제(mutual exclusion)
최소한 하나의 자원을 점유한 채, 현재 다른 프로세스에 의해 점유된 자원을 추가로 얻기 위해 대기하고 있어야만 한다. - 점유하며 대기(hold-and-height)
프로세스는 최소한 하나의 점유한 채, 현재 다른 프로세스에 의해 점유된 자원을 추가로 얻기 위해 디기하고 있어야 한다. - 비선점(no-preemption)
자원들을 선점할 수 없어야 한다. 즉, 자원이 강제적으로 방출될 수 없고, 점유하고 있는 프로세스가 태스크를 종료한 후 프로세스에 의해 자발적으로만 방출될 수 있다. - 순환대기(circular-wait)
각 프로세스가 꼬리를 물며 자원을 점유하고 있어야 한다.
교착 상태가 발생하려면 위의 4가지 조건이 반드시 성립되어야 합니다.
하지만, 위와 같은 필수 조건들로는 어떤 시스템이 교착상태에 빠질 수 있는지를 간결하게 알 수 없는데, 이를 위해 우리는 자원과 프로세스의 관계를 그래프로 표현을 한 자원 할당 그래프 를 통해 시스템의 교착상태 유무를 파악할 수 있습니다. 자원 할당 그래프란 시스템 내 모든 활성 프로세스의 집합인 P 와 모든 자원의 집합인 R로 정점의 집합 V를 구성합니다. 이 그래프에서 P 로 부터 R 로 뻣어나가는 간선은 특정 프로세스가 해당 자원을 요청하고 기다리는 것을 표시하며 자원 R 에서 P로 뻣어나가는 간선 R->P 는 할당 간선 으로 해당 자원이 해당 프로세스에 할당되어있음을 나타냅니다.
이러한 자원 할당 그래프의 정의로 부터 그래프가 사이클을 포함하지 않은 경우 시스템 내 어느 프로세스도 교착상태가 아니라는 것을 보일 수 있습니다. 역으로, 반대의 경우에는 해당 시스템이 교착 상태 를 가질 가능성이 있다고 판단합니다. 여기서 왜 확실히 교착상태가 존재하는 것이 아닌 교착 상태가 될 가능성이 있다라는 표현을 하는 것일까요? 그것은 바로 자원이 하나의 인스턴스가 아니라 여러개의 인스턴스를 가질 수 도 있기 때문입니다. 만약 자원이 여러개의 인스턴스를 가질 수 있어서 여러 프로세스에게 자원을 제공한다면 교착상태가 일어나지 않게 됩니다.
교착 상태 처리 방법
이제 특정 시스템이 교착 상태에 빠질 우려가 있는지를 판단하는 방법 까지를 알아보았으니, 교착상태를 처리 하는 방법 에 대해 알아봅시다.
먼저, 교착상태 처리에는 3가지의 방법이 존재합니다.
첫째 방법 은 교착상태를 예방하거나 회피 하는 프로토콜을 사용하는 것 이며,
두번째 방법 은 시스템이 교착상태가 되도록 허용한 다음에 이를 회복 시키는 방법입니다.
마지막으로 세번째 방법 은 시스템의 교착상태를 무시하고 발생하지 않는 것처럼 꾸미는 방법입니다.
세번째 방법의 경우 터무니 없이 들리지만, 현대의 운영체제들이 대부분 사용하는 방식이며 이 경우 교착상태를 처리하는 것은 응용 개발자의 몫입니다.
위와 같은 여러가지 방법들을 통해 교착 상태가 발생하지 않게 할 수 있지만, 대부분의 경우는 이러한 해결 방법들은 큰 비용을 필요로 합니다. 가령 일년에 한두번 교착상태가 일어난다던가 혹은 특수한 경우 교착상태가 없으면서도 실행이 동결된 상태가 있을 수 있는데, 이를 피하는 것 보다는 수작업으로 한번 복구하는 것이 훨씬 효과적인 방법인 것과 같은 원리입니다. 때문에, 시스템은 교착상태가 아닌상황을 위해 수작업 복구 방법 을 반드시 가지고 있어야 하며 간단하게 이 방법을 교착상태 회복을 위해 사용 할 수도 있습니다.
교착 상태의 예방
교착 상태 처리방법 가운데 교착상태를 예방하는 법부터 배워봅시다.
시스템이 교착상태에 빠지지 않도록 하기 위해서는 앞에서 얘기한 교착 상태의 필요조건 들 중 적어도 하나가 성립하지 않도록 보장하는 방법입니다.
그렇다면 각 필요조건마다의 조건을 하나씩 따져 보며 해당 필요조건이 발생하지 않는 방안에 대해 고민해 봅시다.
상호배제
교착상태의 첫번째 필요조건인 상호배제 가 일어나는 경우는 공유가 불가능한 자원 에 의해서 입니다. 만약 여러 프로세스가 읽기 전용의 파일을 열면 프로세스들은 그 파일에 대한 동시 접근을 보장받고 이 경우 상호배제 가 깨어지게 되어 교착상태를 예방할 수 있습니다. 하지만, 어떤 자원들은 근본적으로 공유가 불가능 하기 때문에 이러한 상호배제가 반드시 일어나야 하기 때문에 교착 상태를 예방하지 못하는 경우가 발생할 수 있습니다.
점유하며 대기
두번째 필요조건인 점유하며 대기 를 방지할 조건에는 무엇이 있을까요?
점유하며 대기 조건이 발생하지 않도록 하려면 프로세스가 자원을 요청할 때 다른 자원들을 점유하지 않고 있다는 것을 반드시 보장 해야 합니다. 즉, 자기 자신이 아무런 자원도 점유하지 않고 있을 때에만 다른 자원을 요청 할 수 있도록 하면, 대기 상태에 빠지더라도 자신은 아무런 자원도 점유하지 않고 있기 때문에 대기 하더라도 점유하며 대기는 발생하지 않게 됩니다.
이 경우 사용할 수 있는 프로토콜은 프로세스가 실행되기 전에 자신이 필요한 모든 자원을 요청하여 할당받도록 하는 것입니다. 이렇게 되면 프로세스가 정도에 다른 자원을 요청하여 할당받을 때까지 대기하는 일이 없고 모든 자원을 가지고 프로세스를 시작하기 때문에 대기하는 일이 발생하지 않습니다. 하지만 이 경우 큰 단점이 발생하는데 바로 많은 자원들이 할당 된 후 오랫동안 사용되지 않기 때문에 자원의 이용률이 낮아 지는 것 입니다. 가령 어떤 명령이 디스크 접근과 인쇄를 같이 하는 것이라면 프로세스가 디스크 접근을 수행하는 동안에도 이 프로세스는 프린터의 자원을 점유하게 되어 그 시간동안 프린터가 이용되지 못하는 상황이 발생하게 됩니다. 또 기아 상태가 가능하다 는 단점이 있을 수 있습니다. 필요한 자원 중 최소 하나가 계속 다른 프로세스에게 할당되어 있으면 이 프로세스는 무한정 대기해야 할 가능성이 생기게 됩니다.
또 다른 프로토콜은 프로세스가 자원을 전혀 점유하지 않을 때만 자원을 요청할 수 있도록 하는 것 입니다. 이 경우 자원을 대기할 때 절대 자원을 점유하지 않게 되므로 점유하며 대기가 일어나지 않습니다. 하지만, 이 경우에도 치명적인 단점이 존재하는 가령 DVD 드라이브에서 디스크로 자료를 복사한 다음 디스크에서 파일을 정렬하고 이를 인쇄하는 경우를 생각해 봅시다 이 경우 프로세스는 드라이브와 디스크를 점유한 뒤에 인쇄를 하기 위해서 디스크와 드라이브를 모두 방출하고 다시 디스크의 자원을 할당받는 비효율적인 동작이 나타나게 되어 자원의 이용률이 낮아지게 됩니다.
비선점
세 번째 필요조건인 비선점 이 발생하지 않도록 해봅시다. 비선점 이란 이미 할당된 자원이 선점되지 않아야 한다는 것 입니다. 이를 위해서는 자신이 점유하고 있는 자원을 강제로 방출시켜 다른 프로세스가 선점하게 함으로써 교착상태를 끈어버리는 다음과 같은 프로토콜 을 생각해 볼 수 있습니다. 만일 어떤 자원을 점유하고 있는 프로세스가 즉시 할당할 수 없는 다른 자원을 요청하면 현재 그 프로세스가 점유하고 있는 모든 자원이 방출되어 필요로 하는 다른 프로세스에게 선점됩니다. 또 해당 프로세스는 자신이 요청하고 있는 새로운 자원은 물론 현재 강제로 방출한 옛 자원들을 다시 획득할 수 있을 때에만 다시 시작될 것입니다.
순환 대기
교착 상태가 일어나기 위한 마지막 조건인 순환대기 를 없애기 위해서는 모든 자원 유형들에게 전체적인 순서를 부여 하여 각 프로세스가 열거된 순서대로 오름차순으로 자원을 요청하도록 강제하는 것입니다. 이를 통해 모든 자원들은 먼저 할당되는 순서가 정해져 있기 때문에 교착상태가 일어날 수 없습니다.
교착 상태 회피
이처럼 교착 상태 예방 알고리즘은 요청 방법을 제약하여 교착 상태를 예방합니다. 그러나 이런 방식으로 교착 상태를 예방할 때 가능한 부작용은 바로 장치의 이용률이 저하 되고 시스템 이용률이 감소 된다는 것입니다.
이처럼 교착 상태를 처리하는 다른 방법 중 하나는 교착상태 회피 입니다. 교착상태 회피는 각 프로세스의 요청과 방출에 대한 순서를 파악하고 있다면 우리는 각 요청에 대해서 가능한 미래의 교착상태를 피하기 위해 프로세스가 대기해야하는 지를 결정할 수 있다는 점에 착안하여 나온 방안입니다. 즉, 어떤 프로세스가 요청을 할 때 미래에 대한 분석을 통해 나의 요청을 늦추는 방법으로 교착상태를 피할 수 있습니다. 이렇게 교착상태를 피하기 위한 알고리즘을 위해서는 각 프로세스가 요청할 각 유형의 자원의 최대 개수를 파악하는 것입니다.
안전 상태
안전 상태란 이러한 교착 상태 알고리즘을 설계함에 있어 각 유효 자원의 최대 개수까지 어떤 순서로 요청을 하더라도 교착상태를 야기하지 않고 모두 할당을 잘 해줄 수 있음 을 뜻합니다. 회피 알고리즘은 시스템이 정해진 최대 자원 내에서 시스템이 항상 안전 상태에 있도록 한합니다. 이를 위해 프로세스들이 자원을 요청하면 그 요청을 받아주던지 혹은 교착상태를 피하기 위해서 대기 시킬지를 결정하며, 오직 시스템이 안정상태로 유지될 수 있는 경우에만 즉시 요청을 들어줍니다.
자원 할당 그래프 알고리즘
앞에서 우리는 교착 상태 회피를 위해 정의한 자원 할당 그래프 를 살펴 보았습니다. 우리는 교착 상태 회피를 위해서 예약 간선 을 도입하겠습니다. 예약 간선이란 현재는 아니지만 추후 자원을 요청하게 될 것을 의미 합니다. 즉, 추후 시스템에서 교착상태가 일어날 가능성이 생기는 것이지요. 이러한 예약 간선 은 요청이 발생되면 요청 간선 으로 전환되고 자원이 할당되면 할당 간선 으로 전환됩니다.
은행원 알고리즘(Banker’s Algorithm)
교착 상태 탐지(deadlock detection)
교착 상태로 부터의 회복
탐지 알고리즘에 의해 시스템에 교착 상태 가 발생이 되면 이를 회복하는 여러가지의 방법이 있지만 크게 두가지로 나누어 집니다. 첫번째는 한 개 이상의 프로세스를 중지 시키는 것이고, 둘째는 하나 이상의 프로세스들로부터 자원을 선점하는 것입니다.
프로세스 종료
먼저 교착 상태를 해결하기 위해 존재하는 프로세스 하나를 임의로 종료하여 교착 상태를 해결하는 방법에 대해 알아봅시다.
프로세스를 종료함에 있어 우리는 두가지의 방법 을 사용할 수 있습니다.
첫째는, 교착 상태 프로세스를 모두 중지 하는 것 입니다. 이 방법은 상당히 큰 비용 이 들어가는데, 이유는 단순합니다. 교착상태에 가기까지 프로세스들이 이제껏 많은 작업을 진행했을 것이며, 이를 통해 결과가 폐기된다면 다시 계산을 시작해야 하기 때문입니다.
둘째는, 교착 상태가 제거될 때까지 한 프로세스씩 중지 하는 방법이 있습니다. 이 방법은 각 프로세스가 중지될 때마다 아직도 교착 상태에 있는지 매번 살펴봐야 하기 때문에 상당한 오버헤드를 유발합니다.
자원 선점
자원 선점을 통해 교착상태를 제거하기 위해서는 교착 상태가 깨어질 때까지 프로세스로부터 자원을 계속적으로 선점해 다른 프로세스에게 주어야 합니다.
이런 자원 선점 에 있어서 다음을 사항들을 꼭 고려하여야 합니다.
1. 희생자 선택(selection of a victim)
자원 선점에 앞서 어떤 자원과 어느 프로세스가 선점될 것인가 를 고민해야 합니다. 이 때 비용을 최소화 하기 위해 교착 상태 프로세스가 점유하고 있는 자원의 수, 그리고 교착상태 프로세스가 지금까지 실행하는 데 소요한 시간 등과 같은 변인들을 고려하여 희생자를 선택해야 합니다.
2. 롤백(rollback)
만약 특정 프로세스을 자원을 강제로 방출하고 선점시켰다면, 그 프로세스를 어떻게 처리 할 것인가에 대한 고민이 필요하다. 보통 가장 안전한 방법은 프로세스를 중지시키고 재시작하는 것 즉, 롤백하는 것이다.
3. 기아 상태(starvation)
자원 선점을 통해 기아상태가 발생하지 않을까를 고려해 보아야 한다. 계속해서 특정 프로세스의 자원을 강제 방출시켜 선점을 시켜주게 되면 그 프로세스는 계속해서 희생자로 선택될 확률이 높고 이경우 그 프로세스는 영원히 실행이 완료되지 못하는 기아상태에 빠질 수 있기 때문에 이를 심사숙고 해야 한다. 즉, 프로세스가 한정된 시간에만 희생자로 선정된다는 것을 반드시 보장 해야 한다.
Comments