[운영체제] The Banker's Algorithm

Deadlock Avoidance(교착상태 회피)

교착상태 회피는 교착상태에 빠질 가능성이 있는지 없는지를 운영체제가 검사하고 빠질 가능성이 없을 경우에만 자원을 할당하여 문제 발생을 피하는 방법이다. 우선 이를 판단하기 위해 상태를 안전 상태와 불안전 상태로 나누고, 운영체제는 안정상태를 유지할 수 있는 요구만 수락하고, 나머지 요구들은 안전상태를 만족할 때까지 계속 거절한다.

여기서 은행을 예로 들어보겠다. 100원을 가지고 있는 은행이 있고, 그 은행으로부터 돈을 빌리려는 3명의 고객이 있다. 고객은 필요한 돈이 있어야만 일을 해결할 수 있고, 빌린 돈을 상환할 수 있다. 이를 테면, 30원이 필요한 상황인데 수중에 20원만 있으면 일을 해결하지 못하고 돈을 다시 갚지도 못한다.

고객 1은 60원, 고객 2는 50원, 고객 3은 40원이 필요하다. 그래서 은행은 고객 1에게는 30원을, 고객 2에게는 30원을, 그리고 고객 3에게는 20원을 빌려주었다. 그리하여 은행은 총 80원을 빌려준 셈이고, 남아있는 돈은 20원이다. 하지만 여전히 고객 1은 30원이, 고객 2는 20원이, 고객 3은 20원이 더 필요하다. 이러한 상황에서 어떻게 모든 고객의 상황을 해결할 수 있을까? 우선 첫 번째로는 남은 20원을 고객 2에게 빌려주고 고객 2가 일을 다 해결할 때까지 기다린다. 두 번째로는 고객 3에게 20원을 빌려주고 고객 3이 일을 다 해결할 때까지 기다리는 방법이다.

 

고객 2 -> 고객 1 -> 고객 3

고객 2 -> 고객 3 -> 고객 1

고객 3 -> 고객 1 -> 고객 2

고객 3 -> 고객 2 -> 고객 1

이러한 순서로 모든 고객의 상황을 해결할 수 있고, 이를 안전 순서열이 존재한다고 한다.

 

그러나 갑자기 성질 급한 고객 1이 35원 빌려달라고 재촉해서 35원을 고객 1에게 빌려주면 아래와 같은 상황이 발생하게 된다.

그렇게 되면 은행에 남아있는 돈은 15원밖에 없는데, 이런 상황에서 모든 고객들을 다 해결할 수 없다. 은행의 돈이 충분하지 않기 때문이다. 따라서 이런 상황을 불안정 상태, 즉 Deadlock 상태라 한다.
결국 은행원 알고리즘은 '은행은 최소한 고객 한명에게 대출할 수 있는 금액을 보유해야 한다'의 개념에서 파생된다.

The Banker's Algorithm을 수행하기 위해 필요한 것들

안전 상태(Safe State): 시스템이 교착 상태를 일으키지 않으면서 각 프로세스가 요구한 최대 요구량만큼 필요한 자원을 할당해 줄 수 있는 상태. 안전순서열이 존재해야 한다.

불안전 상태(Unsafe State): 안전순서열이 존재하지 않는 상태. 불안전 상태는 교착상태이기 위한 필요조건. 불안전 상태라 해서 무조건 교착상태가 발생하는 것이 아니라, 교착상태는 불안전 상태에서만 발생한다는 것이다.

 

은행원 알고리즘이 제대로 수행되기 위한 3가지 조건

1. 각 고객들이 얼마나 최대한도의 금액을 요구할 수 있는가(Max) -> 각 프로세스가 자원을 얼마나 요청할 수 있나
2. 각 고객들이 현재 빌린 돈이 얼마나 있는가(Allocated) -> 각 프로세스가 현재 보유하고 있는 자원은 얼마인가
3. 은행이 보유한 돈이 얼마이며, 빌려줄 수 있는 돈이 얼마인가(Available) -> 시스템이 얼마나 자원을 보유하고 있는가

프로세스 예시

운영체제는 총 12개의 자원을 지니고 있고, 프로세스 P0, P1, P2가 있다고 가정해보자. 프로세스 P0을 수행하는데 자원 10개가 필요하고, P1은 4개가 필요, P2는 9개가 필요하다. t0이라는 특정 시점에 P0은 5개의 자원을 가져갔고, 나머지 P1과 P2는 자원을 2개씩 가져갔다. 그리하여 현재 운영체제에는 3개의 사용 가능한 자원이 남아 있다. 그렇다면 t0이라는 시간에 시스템은 안정 상태에 있다. 왜냐하면 'P1 -> P0 -> P2'라는 안전수열이 존재하기 때문이다.

그러나 시스템은 불안정 상태로 변할 수 있다. 예를 들어 시간이 흘러 어느덧 t0시각이 되었다. 이때 P2가 하나의 자원을 더 요청했는데, 이로 인해 운영체제에는 2개의 자원이 남아 있다. 이런 상황에서 안전 수열이 존재하지 않는다. 우선 P1은 5개를 더 필요로 하니 불가능하고, P1에 남은 2개의 자원을 빌려준다 해도 돌아오는 자원은 4개이므로 P0나 P2 어느 쪽도 해결할 수 없는 상황이 발생한다. 고로 이때 불안정 상태가 되는 것이다.

여기서 만약 P2에 자원을 빌려주지 않고 P1이 먼저 끝나도록 조치했으면 교착상태에 걸리지 않고 바로 해결할 수 있었을 것이다. 그리하여 시스템이 항상 안전상태를 유지할 수 있게 하는 것이 은행가 알고리즘이다.

The Banker's Algorithm 단점

1. 할당할 수 있는 자원의 수가 일정해야 한다
2. 사용자 수가 일정해야 한다.
3. 항상 불안전 상태를 방지해야 하므로 자원 이용도가 낮다.
4. 최대 자원 요구량을 미리 알아야 한다.
5. 프로세스들은 유한 시간 안에 자원을 반납해야 한다.

우선 알고리즘이 매우 복잡하며 해당 프로세스가 시작할 때 프로세스가 가지고 있어야 할 자원의 최대 개수를 숙지해야 한다. 따라서 실제 프로그램 작동 시 이를 적용하기도 상당히 어렵다. 그리고 오버헤드 역시 크므로 현재 체택하는 방식은 아니다.

 

참고 자료

https://jhnyang.tistory.com/102

[운영체제]교착상태 회피-은행원 알고리즘(Banker's Algorithm) 쉬운 예시, 안전상태, 불안전상태