개요(Overview)
지난 포스팅에서는 교착상태의 기본적인 정의와 그 필요조건에 대해서 다루었습니다.
[운영체제] 교착 상태(Dead Lock)와 필요 조건
개요(Overview) 다중 프로그래밍 환경에서 여러 프로세스들은 제한된 수의 자원을 사용하려고 서로 경쟁할 수 있습니다.대기 중인 프로세스는 자 신이 필요로 하는 자원이 대기중인 또 다른 프
1-hee.tistory.com
이번 포스팅에서는 마지막에 소개했던 교착 상태를 해결하기 위한 다양한 관리 기법들 교착상태를 예방, 방지, 발견, 회복하는 방법에 대해 이어서 다루도록 하겠습니다.
1.6. 교착상태의 예방
교착 상태(Dead Lock)는 앞서 살펴본 네 가지 필요 조건에 의해 발생될 수 있습니다. 따라서, 이 조건 중 하나라도 일어나지 않도록 한다면 교착 상태의 발생을 막을 수 있습니다.
Havender는 4가지 필요 조건 중의 어느 하나라도 만족되지 않는다면 교착 상태는 일어날 수 없다고 했습니다. 이에 따라 아래와 같은 방법을 제시하여 교착상태의 필요조건을 만족하지 않을 수 있는 방법을 제안했습니다.
- 각 프로세스는 한 번에 자기에게 필요한 모든 자원을 요구해야 하며 이것이 모두 만족되지 않으면 작업을 진행할 수 없다. [대기조건의 방지]
- 만일 어떤 자원을 가진 프로세스가 더 이상 요구가 받아들여지지 않는다면 자신이 점유하던 자원을 반납하고 필요 시에 다시 그 자원이나 다른 자원을 요구해야 한다. [비중단 조건의 방지]
- 모든 프로세스는 각 자원 유형별로 할당에 대한 순서를 부여한다. 만약, 한 프로세스가 주어진 유형의 자원을 이미 할당 받았다면 그 프로세스는 순서에 따라 나중에 위치하는 유형의 자원만을 요구할 수 있다. [환형 대기 조건의 방지]
1.6.1. 대기조건의 방지
Havender는 프로세스가 필요로 하는 자원을 모두 일시에 요구하도록 하는 것을 제안했습니다.
시스템은 이에 대하여 전부 가능한 상태가 아니면 모두 불가하다는 응답을 전달해야 합니다.
만약 한 프로세스가 요구하는 자원들이 모두 사용 가능하다면 시스템은 그 자원 모두를 사용할 수 있도록 허가해주고 프로세스를 진행시킵니다. 반면에 프로세스가 원하는 자원이 모두 사용 가능한 것이 아니라면 프로세스는 모두 사용 가능해질 때까지 기다려야 합니다.
그리고 이때 프로세스는 그 어떤 자원도 가지고 있을 수 없으므로 교착상태의 필요 조건 중 ‘대기조건’을 막을 수 있습니다.
이와 같은 전략은 합리적인 것으로 보일 수 있지만, 자원의 심한 낭비를 초래할 수도 있습니다. 왜냐하면, 한 번에 10개의 테이프 드라이브를 요구하는 프로세스가 있다고 했을 때 이 프로세스는 실행 전 10개의 테이프 드라이브를 요구하고 이를 다 확보해야만 합니다.
만일 10개의 테이프 드라이브가 모두 실행 중에 필요한 것이라면 자원의 낭비는 없겠지만, 한 번에 하나의 테이프 드라이브만 쓰거나, 잘못 설계되어 하나도 사용되지 않는 다면 이는 굉장한 비효율성을 야기시킬 수 있습니다. 또한 이러한 대량의 컴퓨터 자원이 몇 시간동안 한가로이 쉬어야 하는, 즉 자원이 낭비될 수 있다는 단점이 있습니다.
시스템 설계자들이 이러한 상황에서 자원의 효율적 사용을 위해서 자주 사용하는 전략은 프로그램을 서로 독자적으로 수행될 수 있는 몇 가지 단계로 나누는 것입니다. 그러면 자원 할당이 전체 프로세스 단위가 아닌 단계별로 제어될 수 있습니다. 이 방법은 낭비를 줄일수는 있지만, 응용 시스템에서 설계와 실행 시에 더 많은 대가를 치러야 할 수 있습니다.
또 다른 방법으로는 각 프로세스가 자원을 하나도 갖지 않을 때에만 자원을 요구하도록 하는 방법입니다. 앞선 방법과의 차이점을 설명하기 위해 어떤 프로세스가 카드 판독기로부터 디스크 파일로 복사하고, 해당 파일을 분류한 뒤에 결과를 프린터로 출력하는 작업을 수행한다고 가정해보겠습니다.
처음 소개한 방법, 즉 모든 자원을 요구해야할 경우 프로세스는 카드 판독기, 디스크 파일, 프린터, 그리고 테이프 구동기를 요청합니다. 전체 작업에서 테이프 구동기는 가장 마지막에 쓰게 되지만 프로세스가 수행되는 동안에 그 프로세스에 의해 점유되게 됩니다.
반면에 두 번째로 소개한 방법에서는 프로세스가 처음에 카드 판독기와 디스크파일만을 요구하게 됩니다. 그리고 이 프로세스는 카드 판독기로부터 디스크파일로 데이터를 복사한 이후에 두 개의 자원을 해제하게 됩니다. 그 이후에 해당 프로세스는 디스크 파일과 프린터를 다시 요구하여 디스크 파일을 프린터로 복사한 후 두 자원을 돌려주게 됩니다. 그리고 모든 자원을 반납한 후에 다시 디스크 파일과 테이프 구동기를 요청하여 작업을 수행한 이후에 이 프로세스는 종료됩니다.
이러한 방법에는 두 개의 주요한 단점이 있습니다.
첫번째는 자원의 효율성이 너무 낮다는 것입니다. 왜냐하면 한 번에 많은 자원들이 쓰이지 않으면서 오랫동안 할당되어 있기 때문입니다. 다시 말해 위의 예시에서는 자료가 디스크에 그대로 남아있다는 것을 확신할 수 있다면 카드 판독기와 디스크를 해제하고 디스크와 프린터를 요구할 수 있습니다. 하지만, 이를 확신할 수 없다면 작업이 시작될 때 모든 자원을 요구해야만 합니다.
두번째는 기아 상태(Starvation)이 발생할 수 있다는 것입니다. 자주 사용되는 여러 자원들을 요구하는 프로세스의 경우 적어도 하나 이상이 다른 프로세스에게 할당되어 있을 때에는 무한히 기다려야 하는 경우가 발생할 수 있습니다.
1.6.2. 비중단 조건의 방지
Havender는 어떤 자원을 가진 프로세스가 더이상 자원에 대한 요구를 거절당했다면 그 프로세스는 자신이 가진 자원을 반납하고 필요시에 다시 요구하도록 하는 것을 제안했습니다.
이 방법을 구현한다면 교착상태의 필요 조건 중 비중단 조건을 효과적으로 방지할 수 있습니다.
이 방법에서는 어느 시점에서 어떤 자원을 사용하던 프로세스가 이 자원들을 일단 반환하면 그 시점까지 수행한 작업이 모두 무의미해질 수도 있습니다. 이러한 현상은 그 자체만으로 큰 문제가 되지 않을 수도 있지만, 우선 순위가 높거나 완료 시각이 정해진 프로세스가 제 시간에 작업을 마쳐야 하는 경우에는 치명적으로 작용할 수 있습니다.
또한 이 방법의 파생 효과로 생기는 문제 중 하나가 무기한 연기가 발생할 수도 있다는 것입니다. 프로세스가 동일한 자원을 요구했다가, 다시 반환하고 하는 일련의 과정을 무한히 반복하게 될 수도 있습니다. 이런 일이 자주 발생한다면 시스템은 이러한 프로세스가 다른 프로세스의 작업을 방해하지 않도록 제거해야 할 수도 있습니다. 그러나 이 경우 무기한으로 연기되는 프로세스가 무시하기 어려운 중요한 프로세스일수도 있기에, 이 경우에 프로세스는 상당한 컴퓨터 자원을 소비해서 성능이 저하될 우려가 있습니다.
1.6.3. 환형 대기 조건의 방지
마지막 방법으로는 시스템에서 환형 대기(circular wait)를 발생시키지 않도록 자원에 순서를 부여하는 방법이 있습니다. 즉, 각 자원에 서로 른 자연수 값을 두어 두 자원을 비교한 후 먼저 처리할 자원을 결정할 수 있습니다.
이를 수식으로 표현하자면, 자원의 집합을 R이라고 정의할 때, 컴퓨터 시스템에 존재하는 자원은 아래와 같은 수식으로 표현될 수 있습니다.
R = { r1, r2, … , rn }
이때 각 자원에 대하여 일대일 함수(F(x) = R → N)를 정의할 수 있는데, 이때 N은 자연수 집합을 의미합니다. 가령 어떤 시스템에 카드 판독기, 디스크 구동기, 테이프 구동기, 프린터 라는 주변장치가 있을 때 이 자원들에 대한 일대일 함수의 결과는 아래와 같을 수 있습니다.
F(카드 판독기) = 1
F(디스크 구동기) = 5
F(테이프 구동기) = 7
F(프린터) = 15
어떤 컴퓨터 시스템에서 위와 같이 자원이 관리되고 있다면, 각 프로세스는 이 자원들을 요청할 때 오름차순으로 요청하도록 강제할 수 있습니다. 즉, 만약 어떤 프로세스가 임의의 자원 ri를 요청한다면 새로운 자원 rj는 F(ri) > F(rj)를 만족할 때 요청할 수 있도록 할 수 있습니다.
위 사례에서는 만약 어떤 프로세스가 현재 디스크 구동기를 사용한 후에, 프린터를 요청하는 것은 가능하지만 카드 판독기는 요청할 수 없다는 것을 의미합니다.
그리고 이러한 조건을 만족시키지 못하는 경우 현재 점유했던 임의의 자원 ri를 반환하도록 하여, 환형 대기(circular wait) 조건이 일어날 수 없도록 방지할 수 있습니다.
이를 증명하기 위해 앞서 소개한 환형 대기 상태를 예시로 적용해보겠습니다.
위 그림에서 자원 1에 대하여 일대일 함수의 값이 1, 자원 2에 대하여 일대일 함수의 값이 2라고 했을 때, 프로세스 A는 자원 1을 소유하고 있었기 때문에 자원 2를 요청하면 F(자원1) > F(자원2)를 만족하므로 프로세스 A의 요청은 허용됩니다.
반면에, 프로세스 B는 자원 2를 소유하고 있었으므로 F(자원2) > F(자원1) 는 만족되지 않기 때문에 프로세스 B는 점유하던 자원 2를 반환하게 됩니다.
1.7. 교착 상태의 회피
만일 교착 상태가 일어날 필요 조건이 존재한다면, 자원을 할당할 때 주의를 기울여 교착 상태를 회피할 수도 있을 것입니다. 가장 널리 알려진 교착 상태의 회피 알고리즘으로는 다익스트라(Dijkstra)의 은행원 알고리즘(Banker's Algorithm)입니다. 은행원 알고리즘은 서로 다른 여러 종류의 자원 집합에 대해서도 쉽게 확장할 수 있다는 이점이 있습니다.
만약 운영체제에서 어떤 동일한 테이프 드라이브를 t개 만큼 할당해야 한다고 가정하겠습니다. 운영체제는 일정 수 a 개의 동등한 테이프 드라이버를 일정 수만큼의 사용자들 사이에서 공유합니다. 각 사용자는 사전에 자신의 작업이 시스템에서 실행하는 동안 필요로 하는 테이프 드라이브의 최대 개수를 제시해야 합니다.
이때, 운영체제는 테이프 드라이브에 대한 최대 요구량이 t를 초과하지 않을 경우 이를 받아들입니다. 한 사용자는 이러한 테이프 드라이브를 하나씩 할당 받거나 반납합니다.
때로는 새로운 드라이브를 얻기 위해 기다려야 할 수도 있지만, 운영체제는 한정된 시간만큼 이를 기다리도록 해줍니다. 현재 한 사용자에게 할당된 테이프 드라이브의 숫자는 그 사용자가 제시한 최대 필요량을 절대로 초과할 수 없습니다.
만일 운영체제가 사용자의 최대 필요량만큼 테이프 드라이브를 제공할 수 있다면, 사용자는 테이프 드라이브를 사용한 뒤 일정 시간 내에 반납할 것을 운영체제에 보증합니다. 만일 운영체제가 모든 사용자에게 각각의 프로세스 작업이 일정 기간 내에 끝낼 수 있도록 해줄 수 있다면 현재 시스템의 상태는 ‘안전(Safe)’하다고 합니다. 그렇지 않을 경우 ‘불안전(Unsafe)’하다고 합니다.
이제 운영체제로부터 테이프 드라이브를 사용할 n명의 사용자가 있다고 가정해보겠습니다.
그리고 임의의 사용자를 i 라고 할 때 각각의 사용자는 아래의 일반식으로 테이프 드라이브의 사용량을 표현할 수 있습니다.
l(i) = x
만약 사용자 5가 4개의 테이프 드라이브를 필요하다면, l(5) = 4 라고 정의할 수 있습니다.
또한, 이때 사용자 i가 필요로 하는 테이프 드라이브의 최대 사용량을 m(i)라고 하면,
사용자 5의 최대 사용량 m(5) = 4가 됩니다.
그리고 이때, 사용자가 필요로 하는 최대 테이프 드라이브의 양에서 현재 빌리고 있는 양을 뺀 값, 즉 사용자 i가 운영체제에게 추가적으로 요구할 수 있는 잔여 테이프 드라이브의 양을 c(i)라고 정의합니다.
이를 적용하면 사용자 7이 최대 6개의 테이프 드라이브를 필요로 하는데 현재 4대를 할당 받은 상황일 때 아래의 수식을 만족합니다.
c(7) = m(7) – l(7) → 2 = 6 – 4
이제 운영체제가 총 보유한 테이프 드라이브의 개수를 t개라고 할 때, 아직 할당할 수 있는 테이프 드라이브의 수를 a라고 한다면 a는 t에서 각 사용자의 대여량의 총합을 뺀 값입니다.
다익스트라의 은행원 알고리즘은 이러한 수식을 활용하여 할당한 결과가 시스템이 안전(Safe)한 상태일 때에만 테이프 드라이브를 사용자에게 할당하도록 합니다. 여기서 안전상태란 전체 자원의 배분 상태가 모든 사용자가 결국 작업을 마치고 자원을 반환할 수 있는 상태를 의미하고, 불안전(Unsafe)한 상태란 결국에는 교착상태가 발생할 여지가 있는 경우를 의미합니다.
은행원 알고리즘을 보다 쉽게 이해할 수 있도록 몇 가지 사례를 살펴보겠습니다.
은행원 알고리즘 사례 1
단, t = 12
| 현재 대여량(mi-ci) | 최대 대여량(mi) | |
| 사용자 1 | 1 | 4 |
| 사용자 2 | 4 | 6 |
| 사용자 3 | 5 | 8 |
| 잔여량(a) | a = 12 – ( 1 + 4 + 5) = 2 | |
위 사례에서 운영체제는 총 3명의 사용자를 관리합니다.
현재 남아있는 테이프 드라이브의 잔여량 a는 2일 때, 운영체제는 사용자 2에게 2개를 할당해줌으로써 사용자 2의 작업을 끝내고 6개를 돌려받을 수 있습니다.
그 다음으로는 상환된 테이프 드라이브 6개를 사용자 1 또는 사용자 3에게 할당하여 나머지 작업도 마치게 할 수 있습니다.
따라서 운영체제는 현재 상태가 안전(Safe)하다고 판정합니다.
은행원 알고리즘 사례 2
단, t = 12
| 현재 대여량(mi-ci) | 최대 대여량(mi) | |
| 사용자 1 | 8 | 10 |
| 사용자 2 | 2 | 5 |
| 사용자 3 | 1 | 3 |
| 잔여량(a) | a = 12 – ( 8 + 2 + 1) = 1 | |
위 사례에서는 테이프 드라이브의 잉여분이 단 1개이므로 그 누구도 잔여 테이프를 모두 할당 받았을 때 작업을 끝마칠 수 없습니다.
즉, 위 사례에서는 향후 교착상태가 발생할 가능성이 큽니다.
그러나 이러한 상황은 반드시 교착 상태가 일어날 것임을 의미하는 것이 아닙니다. 비록 잔여 사용량이 1개이더라도 현재 시점으로는 교착 상태가 일어난 것이 아니기 때문에 앞으로 어떤 일련의 사건이 발생하면 교착상태가 발생한다는 것 만을 보장하기 때문입니다.
따라서, 운영체제는 현재 상황을 분석했을 때 상태가 불안전(Unsafe)하다고 판정합니다.
은행원 알고리즘 사례 3
단, t = 12
| 현재 대여량(mi-ci) | 최대 대여량(mi) | |
| 사용자 1 | 1 | 4 |
| 사용자 2 | 4 | 6 |
| 사용자 3 | 5 | 8 |
| 잔여량(a) | a = 12 – ( 1 + 4 + 5) = 2 | |
위 사례는 처음의 사례로 든 안전(Safe)한 상태입니다.
만약 운영체제가 사례 3과 같이 안전한 상태라면,
반드시 현재 상태를 ‘안전(Safe)’하게 유지할 수 있다는 것을 보장할 수 있을까요?
예를 들어 현재 상황에서 아래와 같이 사용자 2가 아니라 사용자 3이 테이프 드라이브 1개를 추가로 요구했다고 가정해보겠습니다.
은행원 알고리즘 사례 4
단, t = 12
| 현재 대여량(mi-ci) | 최대 대여량(mi) | |
| 사용자 1 | 1 | 4 |
| 사용자 2 | 4 | 6 |
| 사용자 3 | 6 | 8 |
| 잔여량(a) | a = 12 – ( 1 + 4 + 6) = 1 | |
이번 사례는 분명 초기에는 상태가 안전(Safe)한 상태였지만,
사용자 2가 아니라 사용자 3이 운영체제에게 테이프 드라이브를 요청하고 운영체제가 이를 허용하면서 결과적으로 ‘불안전(Unsafe)’한 상태로 변하게 됩니다.
하지만 그렇다고 해서 [은행원 알고리즘 사례 4]가 반드시 교착상태에 빠지는 것은 아닙니다.
단지, 상태가 모든 사용자 프로세스가 정상적으로 끝날 수 있는 ‘안전(Safe)’한 상태에서 불안전한 상태로 변한 것일 뿐인 것입니다. 위 상황에서 운영체제가 각 프로세스가 안전하게 모든 작업을 끝마치게 하려면 최소한 2개의 자원이 추가적으로 필요합니다.
따라서, 은행원 알고리즘(Banker's Algorithm)은 만약 현재 테이프 드라이브의 사용량에 대한 누계가 [은행원 알고리즘 사례 3]과 같았을 때, 사용자 3이 추가 사용량을 요구할 경우 자원을 할당하기 전에 다른 사용자의 상황을 분석하여 ‘안전(Safe)’한지 판단합니다.
사례 1 또는 사례 3에서 사용자 3이 추가적으로 사용을 요구하게 된다면, 이 요청을 승낙할 경우 시스템은 ‘불안전(Unsafe)’한 상황이 되므로 이러한 요구를 거절하게 됩니다.
반면에, 사용자 2가 추가적으로 사용량을 요구하게 된다면, 이 요청을 승낙해도 시스템은 ‘안전(Safe)’한 상태를 유지할 수 있으므로 이 요구는 받아들여지게 됩니다.
이처럼 은행원 알고리즘은 교착상태의 회피를 위한 굉장히 합리적인 방법이라고 보이지만, 아래와 같은 약점이 존재합니다.
- 할당할 수 있는 자원이 일정량 존재할 것을 요구합니다. (실제 자원이 항상 사용가능한 상태임을 보장하기 어려운 점이 고려되지 못했습니다.)
- 사용자의 수가 항상 일정해야 한다는 것을 전제합니다. (실제 시스템에서 사용자의 수는 시간이 지남에 따라 가변적일 수 있습니다.)
- 이 알고리즘은 은행, 즉 운영체제가 모든 요구를 유한한 시간 내에 받아주도록 되어 있습니다. 하지만, 실제 시스템에서는 이보다 더 강력한 방안이 필요할 수 있습니다.
- 은행의 고객, 즉 운영체제는 각 프로세스에게 유한한 시간 내에 자원을 반환할 것을 요구하지만, 이러한 ‘약속’만으로는 강제성이 부족할 수 있습니다.
- 모든 사용자, 즉 모든 프로세스는 사용자가 미리 최대 필요량을 알려줄 것을 요구하고 있습니다. 이는 동적으로 자원의 할당량이 변할 수 있는 프로세스에서는 적용하기 어려워 궁극적으로 사용자 별 최대 필요량 판단이 어려울 수 있습니다.
1.8. 교착 상태의 발견
교착상태의 발견은 교착상태가 일어났는지를 실제로 결정하고 교착 상태에 관계된 프로세스와 자원을 규명하는 과정을 말합니다. 교착 상태의 발견은 앞선 포스팅에서 다루었던 교착상태의 필요조건을 모두 허용하는 시스템에서 널리 사용됩니다. 교착 상태의 발견에 사용되는 알고리즘들은 기본적으로 환형 대기의 존재 여부를 판단합니다.
교착 상태 발견 알고리즘은은 기본적으로 실행중(runtime) 추가 비용이 발생하게 됩니다. 만약 교착 상태가 자주 발생하게 된다면 이에 사용되는 알고리즘의 사용 빈도는 증가하게 될 것입니다.
어떤 프로세스가 교착상태일 때 그 프로세스에 할당된 자원은 이 상태가 해소될 때까지 사용되지 않게 됩니다. 더불어 이러한 프로세스 간의 그래프에서 환형 대기, 즉 사이클의 수는 점점 늘어날 수도 있습니다. 교착 상태는 어떤 프로세스가 즉시 수용될 수 없는 요청을 했을 경우 발생하므로, 이러한 요구는 결국에는 환형의 대기 사슬을 구성하게 됩니다.
극단적으로는 이러한 받아들여질 수 없는 요구가 있을 때마다 교착상태 발견 알고리즘(Deadlock Detection Algorithm)을 적용할 수도 있습니다. 하지만 이처럼 너무 잦은 알고리즘의 사용은 오히려 시스템 전체의 효율성을 저해할 수 있으므로, 보통 한 시간에 한 번 또는 CPU의 효율이 40% 이하로 떨어질 때마다 수행하는 것이 보편적입니다.
하지만, 이러한 알고리즘은 일반적인 상황에서 교착 상태에 놓인 프로세스들 사이에서 누가 그 원인이 되었는지 알아내는 것은 어렵습니다.
1.8.1. 자원 할당 그래프
교착상태를 쉽게 찾아내기 위한 방법으로 유향 그래프를 이용하여 자원의 할당 내역과 요구사항을 나타내는 기법, 즉 자원 할당 그래프를 사용하는 방법이 있습니다.
이러한 자원 할당 그래프는 아래와 같이 표현할 수 있습니다.
위 그림에서 사각형은 프로세스를 가리키고, 원은 동일한 자원의 집합을 나타내며, 큰 원 안에 그려진 작은 원은 해당 자원의 분류에 속하는 동일한 자원들을 의미합니다.
또는, 수학적 집합 표현을 응용하여 아래와 같이 자원 할당 그래프의 상황을 표현할 수 있습니다.
위와 같이 주어진 자원 할당 그래프에서 사이클을 형성하지 않는다면 이 시스템은 현재 교착상태(Dead Lock)이 발생하지 않았다는 것을 알 수 있습니다.
반면에 그래프에서 ①사이클이 확인되고, ②그 사이클 속의 자원이 하나만 존재한다면 이 사이클을 교착상태임을 나타내는 것입니다.
즉, 이 경우에 그래프 속에서 확인되는 사이클은 교착 상태라는 것을 의미하는 필요 충분 조건이 됩니다.
하지만, 각 자원이 여러 개 존재한다면 사이클이 존재한다고 해도 그래프 내의 사이클이 꼭 교착상태라는 것을 의미하는 것이 아닐 수 있습니다.
위 그림에서는 P1과 P3간에 사이클이 보이고 있지만, r1원 자원 그룹의 경우 전체 자원의 개수는 총 2개 이므로 p2가 작업을 마치게 되면 p1은 r1을 할당 받아서 교착상태는 해소될 수 있습니다. 또는 p4가 작업을 끝마치면 p3는 r2를 할당 받아서 교착상태가 해소될 수 있습니다.
1.8.2. 자원 할당 그래프의 소거
교착 상태의 발견은 교착 상태 발생 여부의 결정에 주안점을 둡니다. 교착 상태를 찾아내는 또 다른 방법은 그래프 소거법(reduction)으로 실행을 완료할 수 있는 프로세스와 교착상태에 빠진 프로세스를 결정하는 방법이 있습니다.
예를 들어 위와 같이 같은 자원 할당 그래프가 존재한다면, 이 그래프에서 사이클이 확인될 때 실제로 이 프로세스 사이에 교착상태가 발생했는지 판단하려면 아래와 같이 하나씩 소거하여 교착 상태의 발생 유무를 판정할 수 있습니다.
위 그림에서 각 프로세스의 자원 할당 그래프에서 어떤 관계를 먼저 소거하는지에 대한 부분은 교착 상태의 판단에 영향을 주지 않으므로, 위 상황은 사이클이 형성되었으나, 교착상태에 빠지지 않은 것이라고 판단할 수 있습니다.
1.9. 교착상태의 회복
앞선 사례와 같이 그래프를 통해 교착 상태가 ‘발견’ 된다면 시스템은 이러한 교착 상태로부터 회복할 방법을 마련해야 합니다. 이때, 사용할 수 있는 방법은 크게 두 가지 방법이 있습니다. 하나는 ① 환형 대기를 없애기 위하여 하나 또는 둘 이상의 프로세스를 중지시키는 방법, 다른 하나는 ② 교착 상태의 프로세스로부터 자원을 선점하는 것입니다.
먼저 ① 프로세스를 종료하는 방법은 다음과 같습니다.
1) 모든 교착상태 프로세스를 중지시킨다.
현재 수행중인 모든 프로세스를 중단시켜서 교착 사이클을 즉시 해소합니다. 이 방법은 가장 확실하게 교착 상태를 해소할 수 있지만, 수행중이던 프로세스의 계산 결과를 잃어버려 이를 복구하기 위한 추가적인 비용을 발생시킵니다.
2) 교착 상태 사이클이 제거될 때까지 하나씩 프로세스를 중단시킨다.
각 프로세스가 중지될 때마다 어떤 프로세스가 아직 교착상태인지 결정하기 위해 발견 알고리즘을 수행해야 하므로 추가적인 부담을 발생시킬 수 있습니다.
또한, 프로세스를 중단시키는 것은 쉬운 일이 아닙니다. 예컨대 파일을 작성중인 프로세스를 중단시킨다면 해당 파일은 부정확한 상태에 놓이게 됩니다. 또는 프린터를 조작하고 있었다면 시스템은 다음 작업을 출력하기 전에 프린터의 현재 상태를 정확하게 조정할 수 있어야 합니다.
이와 같이 부분 종료 방법을 적용하려면 교착상태 프로세스(deadlock proecess)가 주어졌을 때 교착상태를 제거하기 위해 어느 프로세스를 중단시킬지 결정해야 합니다. 이는 CPU의 스케줄링 문제와 비슷한 정책을 적용할 수 있습니다. 이러한 방법에서 가장 중요한 부분은 경제적인 비용입니다. 즉, 프로세스를 중단함으로 인해 발생할 수 있는 손실이나 비용이 가장 최소화가 되도록 프로세스를 중단시키는 것이 중요한 요인이 됩니다.
하지만, 이러한 ‘비용’ 은 중단할 프로세스를 선택하기 위한 하나의 기준이며 실제로 이 방법에서 중단시킬 프로세스를 선택할 때 고려해야 할 요소는 다음과 같습니다.
- 프로세스의 우선순위
- 프로세스의 수행 시간 ( 얼마나 오래 수행할 지, 종료 까지 얼마나 남았을 지)
- 프로세스가 어느 종류의 자원을 더 많이 사용하는지
- 프로세스가 작업을 끝내기 위하여 얼마나 더 많은 자원이 필요한 지
- 복귀(rollback)하는데 얼마나 많은 프로세스가 포함되어 있는 지
다음으로 ② 교착 상태의 프로세스로부터 자원을 선점하는 방식이 있습니다.
이 방법에서는 자원 선점을 통해 교착 상태를 이루는 사이클을 없앨 때까지 프로세스로부터 자원을 선점해 다른 프로세스에게 자원을 제공하는 것을 말합니다. 이러한 방식에는 다음과 같은 세가지 부분을 고려해야 합니다.
1) 희생자 선택
어떤 자원 어떤 프로세스를 선점할지 결정해야 합니다. 이대 프로세스를 종료하는 데 비용이 가장 적게 하기 위하여 우선순위에 대한 판단이 필요합니다.
운영체제로부터 어떤 프로세스 P와 Q가 특정 자원에 대한 선점을 주장하는 경우
다음과 같은 상황이 발생할 수 있습니다.
- P가 다루는 작업이 Q보다 우선순위가 높다. 이 경우에는 Q는 P의 작업이 먼저 마칠 수 있도록 자원을 먼저 선점하도록 양보해야 한다.
- P가 작업을 마치는 데 필요한 추가 자원의 수가 Q보다 적다면, Q는 P가 작업을 먼저 끝마칠 수 있도록 양보하는 것이 합리적이다.
- P와 Q가 작업을 수행함에 있어 P는 이후에 처리해야 할 추가 작업이 없고, Q는 자신과 관계된 작업이 여러 개 존재한다면 이때에는 P가 Q에게 자원을 양보하는 것이 합리적이다.
2) 복귀(rollback)
어떤 프로세스 A로부터 강제로 어떤 자원을 선점할 경우, 회수한 자원의 사용이 모두 끝 마쳤을 때 프로세스 A가 자신이 수행하던 작업을 정상적으로 이행할 수 있도록 복귀시켜줄 필요가 있습니다.
그렇다면 어떻게 해야 프로세스 A로부터 자원을 회수한 뒤, 다시 반환할 때 안정적으로 복귀시켜줄 수 있을까요?
이에 가장 단순한 방법으로는 절대 복귀(total rollback)가 있습니다. 이 방법은 프로세스가 진행중이던 작업을 다시 수행하도록 하는 것입니다. 즉 프로세스가 진행중이던 작업을 중단시키고 다른 프로세스로부터 자원이 반납되면 처음부터 작업을 수행하도록 하는 방법입니다.
또 다른 방법으로는 교착 상태의 해결에 필요한만큼만 복귀시키도록 하는 방법입니다. 이 방법은 시스템이 현재 진행중인 모든 프로세스에 대한 정보를 관리해야 하므로 추가적인 부담과 비용이 발생할 수 있지만, 체크포인트(Check point)라는 것을 통해 보다 효율적으로 관리할 수도 있습니다.
방법의 실행적인 측면에서는 절대 복귀가 확실할 수도 있지만, 이는 프로세스가 수행해야 할 작업의 처리라는 측면에서 보면 비효율적인 전략이 될 수 있으므로 체크포인트를 통해 최소한의 비용을 통해 복귀하는 방법이 합리적일 것입니다.
3) 기아상태(starvation)
기아상태란 특정 프로세스나 작업이 필요한 자원을 장기간 할당 받지 못해 실행되지 못하는 상태를 의미합니다.
교착상태를 해결하기 위해 특정 프로세스로부터 자원을 선점하는 행위는 스케줄링 전략에서 발생할 수 있는 기아 상태를 초래할 수도 있습니다.
따라서, 교착 상태에 사용되는 선점 전략은 보다 빠르고 짧은 시간 안에 결정하고 처리되어야 하며 복귀(rollback)시에 필요로 하는 비용을 가중치로 추가하여 보완할 수도 있습니다.
참고 자료
- 김완규, 고정국, 진광윤, 최신형, 하성권, 허덕행 | 핵심 운영 체제론 | 두양사
'CS BASIC > 운영체제(Operation System)' 카테고리의 다른 글
| [운영체제] 네트워크 위상(Topology)과 분산 시스템 (0) | 2025.01.07 |
|---|---|
| [운영체제] 네트워크 운영체제와 프리미티브 (0) | 2025.01.06 |
| [운영체제] 교착 상태(Dead Lock)와 필요 조건 (0) | 2024.12.30 |
| [운영체제] 세마포어(Semaphore) (1) | 2024.12.24 |
| [운영체제] 병행 프로세스와 Dekker 알고리즘 (0) | 2024.12.23 |
