은행원 알고리즘?

S-rim·2020년 7월 5일

교착상태 회피는 데드락이 빠질 가능성이 있는지 없는지 운영체제가 검사하고 빠질 가능성이 없을 경우에만 자원을 할당함으로써 문제 발생을 피하는 방법이다.

교착상태에 빠질 가능성이 있는지, 없는지를 판단하기 위해 상태를 ‘안전 상태’와 ‘불안전 상태’로 나눈다. 그리고 운영체제는 안전상태를 유지할 수 있는 요구만 수락해주고, 나머지 요구들은 안전상태를 만족할 때까지 계속 거절한다.

은행원 알고리즘 닉값을 할 수 있게, 은행으로 쉽게 예시를 들어보자.😁

여기 100원을 가지고 있는 은행이 있다. 그리고 그 은행에게 돈을 빌리려는 3명의 고객이 있다. 고객은 찔끔찔끔 빌려가서 쓸 수 있는게 아니라, 빌리려는 돈이 충족되어야 일을 해결할 수 있고, 다시 빌린 돈을 갚을 수 있다. 즉, 20원이 필요하면 20원이 있어야 해결하지, 10원만 있으면 일을 해결하지 못하고 다시 갚지도 못한다는 거다.

이 고객 세 명은 각 40원, 50원, 60원이 필요하다. 그래서 은행은 각 세 명에게 일단 25원씩 주기로 했다. 그럼 고객은 각각 15원, 25원, 35원이 더 필요하다. 근데 아까 말했듯이 고객은 빌리려던 돈이 충족되어야 다시 갚을 수 있고, 자신의 일을 해결할 수 있다고 했다. 지금 은행은 돈이 25원 남았다. 어떻게 해결할 수 있을까?

첫 번째로 15원 더 필요한 첫번째 고객에게 15원을 빌려주고 첫번째 고객이 일을 해결하고 갚을 때까지 기다렸다가 다른 고객에게 돈을 빌려주는 방법이 있다.

아니면 두 번째 고객에게 남은 25원을 빌려주고 두번째 고객이 일을 해결하고 갚을 때까지 기다리는 방법이 있다. 하지만 세번째 고객에게는 통하지 않는다. 은행은 25원이 남아있는데, 세번째 고객은 35원이 더 필요하기 때문이다. 돈을 빌려줄 수 있고, 다시 돈을 돌려 받을 수 있는 상태를 안전상태라고 한다.

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

이런 순서대로 모든 고객에게 돈을 빌려줄 수 있고 이를 안전 순서열이 존재한다고 한다.

근데, 만약에 60원이 필요한 고객3이 너무 급하다고 25원 말고 45원을 달라고 했다고 하자. 그럼 은행에 남는 돈은 5원 밖에 없다. 이 상황에서는 세 고객 중 아무도 해결해 줄 수 없다. 이 상태를 불안전 상태 또는 데드락 상태라고 한다.

은행원 알고리즘

은행원 알고리즘의 이름은 은행이 최소한 한 명에게 대출해줄 수 있는 금액을 항상 보유하고 있어야한다는 개념에서 나온 것이다.

그리고 은행원 알고리즘이 수행되기 위해서는 3가지가 필요하다.

각 고객들이 얼마나 최대로 돈을 요구할지 = 각 프로세스가 자원을 최대로 얼마까지 요청할 수 있는지

Allocated

각 고객들이 현재 빌린 돈이 얼마인지 = 각 프로세스가 현재 보유하고 있는 자원이 얼마인지

Available

은행이 보유하고, 빌려줄 수 있는 돈은 얼마인지 = 시스템이 자원을 얼마나 보유하고 있는지

이제 이 예시에서 더 자세한 용어들로 다시 보도록 하자.

안전상태는 시스템이 교착상태를 일으키지 않고, 각 프로세스가 요구한 양만큼 자원을 할당해줄 수 있는 상태로, 안전순서열이 존재하는 상태이다.

불안전 상태는 안전 순서열이 존재하지 않는 상태, 즉 아무런 방법이 없는 상태이다. 교착상태는 불안전 상태일 때만 발생한다. 불안전 상태라고 해서 무조건 교착 상태인 것은 아니다.

아까 그 은행과 고객 예시를 운영체제와 프로세스에 대입해 다시 한번 은행원 알고리즘을 머릿속에 확실히 기록해보자.

프로세스 P1, P2, P3이 있고, 운영체제는 12개의 자원을 가지고 있다.

P1은 10개의 자원이 필요하고, P2는 4개, P3은 9개까지 요구된다.
여기서 0이라는 시각에 P1이 5개의 자원을 가져가고, P2가 2개, P3이 2개를 가져갔다. 그럼 현재 운영체제는 3개의 자원이 남아있다. 그럼 이 0이라는 시각에는 시스템은 안전상태이다. 세 프로세스에 ‘P2에게 나머지 2개의 자원을 빌려주고 돌려받아 다른 프로세스에게 빌려주면 되는’ 안전순서열이 존재하기 때문이다.

하지만 시스템은 안전상태에서 불안전 상태로 변할 수 있다.

안전 상태였던 0시각에서 시간이 흘러 1시각이 되었다. 그 때 P3이 자원 하나를 더 요청했다. 운영체제에 3개의 자원이 남아있었으니 하나를 더 빌려줬다면 운영체제에는 이제 2개의 자원이 남는다.

그럼 이 상황에서는 안전 순서열이 존재하지 않는다.

P1은 5개의 자원이 더 필요하니 일단 불가능하다. P2에 2개가 더 필요해서 남은 2개의 자원을 다 빌려준다해도, 돌아오는 자원은 4개뿐이니 P3과 P1 어디에도 해결해줄 수가 없다. 결국 1이라는 시각은 불안전 상태가 되는 것이다.

즉 결론은, 운영체제는 1이라는 시각에 P3이 자원 하나를 더 요청했을 때 자원을 빌려줘야할까? 교착 상태에 빠질 가능성이 있으면 빌려주지 않는 것이 회피다. 그러므로 P3에게 자원 하나를 더 빌려주지 않고, P2를 먼저 끝내는 안전 순서열을 지켰다면 교착상태에 걸리지 않게 해결할 수 있었을 거다.

이렇게 시스템이 안전상태를 유지할 수 있게 하는 것이 은행원 알고리즘이다.