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

[한 번에 끝내는 운영체제 목차!]

Deadlock Avoidance 교착상태 회피 

저번 시간에 교착상태 해결 방안 4종류를 알아봤어요 

교착상태 예방, 교착상태 회피, 교착상태 탐지, 교착상태 복구! 이렇게 4가지 방안이 있었습니다. 기억나나요?

 

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

이번 포스팅에서는 교착상태 회피 대표 기법인 은행원 알고리즘에 대해서 자세히 포스팅해보도록 하겠습니다.

 

은행원 알고리즘 쉽게 이해하기!

은행원 알고리즘(Banker algorithm)은 다이직스트라 알고리즘을 개발한 Edsger Dijkstra가 개발한 알고리즘이예요 (다이직스트라 알고리즘은 네비게이션에서 쓰일 정도로 엄청 유명한 알고리즘입니다)

 

교착상태에 빠질 가능성이 있는지 판단하기 위해 상태를 '안전상태(safe state)'와 '불안전상태(unsafe state)'로 나눴습니다. (= 안전상태 개념). 즉 은행원 알고리즘에서 운영체제는 안전상태를 유지할 수 있는 요구만을 수락하고 불안전 상태를 초래할 사용자의 요구는 나중에 만족될 수 있을 때까지 계속 거절합니다.

 

쉽게 예시를 들어볼게요! Example!)

자 100달러를 가지고 있는 은행이 있고 돈을 빌리려는 고객이 3명이 있습니다. 먼저 하나를 가정할게요. 고객은 필요한 돈이 다 있어야만 일을 해결할 수 있고 빌린 돈을 상환할 수 있습니다. 즉 30달러가 필요한다 20달러만 있으면 상황 해결이 안된다는거죠! 고객 1은 60달러, 고객2는 40달러, 고객3은 50달러가 필요해요. 

그래서 은행은 일단 고객1에게 20달러를 고객2와 고객3에게 30달러를 빌려줬어요. 그럼 20+30+30 = 80달러 100-80=20! 은행이 수중에 가지고 있는 돈은 20달러네요! 근데 아직 고객1은 40달러, 고객2는 10달러, 고객3은 20달러가 추가적으로 필요한 상황입니다.

 

자 어떤 방법이 있을까요? 

첫 번째 방법은 남은 20달러 중에 10달러를 고객 2에게 빌려주고 그 고객이 어려운 상황을 해결하고 돈을 갚을 때까지 기다리는 겁니다. 은행은 10달러밖에 남지 않지만, 고객2로부터 40달러를 돌려받아 50달러가 생기므로 고객1이나 고객3을 도울 수 있는거죠. 

두 번째 방법은 20달러를 고객3에게 빌려주고 그 고객이 해결할 때까지 기다릴 수 있겠죠?

하지만 고객1에게는 이 방법이 통하지 않아요. 나는 20달러밖에 없는데 고객1은 추가적으로 필요한 돈이 40달러이기 때문이죠. 그래서 이 고객의 방법은 첫 번째 방법이나 두 번째 방법으로 돈을 어떻게든 충당한 후에 해결해줄 수 있습니다.

 

아무튼 이렇게 모든 고객들에게 결국 돈을 빌려주고 은행이 다시 돈을 돌려받을 수 있는 상태를 안전상태라고 합니다.

고객2 - 고객1 - 고객3 

고객2 - 고객3 - 고객1 

고객3 - 고객1 - 고객2

고객3 - 고객2 - 고객1

이런 순서로 모든 고객의 상황을 해결해 줄 수 있고 이를 안전 순서열이 존재한다고 합니다.

 

반면!

근데 갑자기 고객1이 너무 상황이 긴박해서 최소 35달러는 당장 필요하다 해서 35달러를 빌려줬다고 해봅시다.

그러면 은행에 남는 돈이 5달러밖에 없네요? ㅠㅠ 이런 상황에서는 셋 다 아무도 해결해줄 수가 없어요. 은행이 충분한 돈이 없기에 파산하는거죠. 이런 상태를 불안전상태 또는 데드락 상태라고 합니다.

즉 은행원 알고리즘은 '최소한 고객 한명에게 대출해줄 금액은 항상 은행이 보유하고 있어야 한다'는 개념에서 나옵니다.

 

은행원 알고리즘의 안전상태 정리와 이를 수행하기 위해 필요한 것들

안전상태 (Safe State): 

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

안전순서열이 존재하지 않는 상태를 말합니다. 불안전상태는 교착상태이기 위한 필요조건입니다. 교착상태는 불안전상태에서만 발생합니다. Unsafe state라고 해서 무조건 교착상태가 발생하는 것은 아닙니다.

 

또 은행원 알고리즘이 제대로 수행되기 위해서는 3가지가 필요해요. 

1. 각 고객들이 얼마나 맥시멈으로 돈을 요구할지 [Max] 

-> How much of each resource each process could possibly request. 각 프로세스가 자원을 얼마나 요청할 수 있는지

2. 각 고객들이 현재 빌린 돈이 얼마인지 [Allocated]. 

-> How much of each resource each process is currently holding. 각 프로세스가 현재 보유하고 있는 자원은 얼마인지

3. 은행이 보유한 돈이 얼마인지, 빌려줄 수 있는 돈이 얼마인지 [Available]

-> How much of each resource the system has available. 시스템이 얼마나 자원을 보유하고 있는지.

 

프로세스 예시!

이를 숙지하고 이번에는 프로세스에 예시를 대입해보겠습니다.

프로세스 P0, P1, P2가 있고 운영체제는 12개의 자기 테이프 드라이브를 공유자원으로 가지고 있어요. 

프로세스 P0을 수행하는데 10개의 테이프 드라이브 사용이 필요하고, P1은 최대 4개정도, P2는 9개 정도까지 요구됩니다. 

자 어느 특정 t0이라는 시각에 P0이 5개의 테이프 드라이브를 사용하고 있고, P1과 P2는 두 개를 사용하고 있어요.

따라서 현재 운영체제에는 3개의 테이프가 사용가능한 자원으로 남아있는거죠! 

그럼 t0시점에 시스템은 안전상태인겁니다. 왜냐! <P1, P0, P2>가 safe sequence를 만족하니까요! (안전 순서열이 존재!)

 

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

시간이 흘러 t1시간에 P2프로세스가 자원 하나를 더 요청했어요. 그러면 P2는 3개를 가지고 있겠고 시스템에서 사용할 수 있는 테이프는 2개 되었네요.

자 P0은 5개가 필요하기 때문에 일단 불가능해요.

P1은 2개가 필요해서 어! 남은 2개를 다 주면 P1을 끝낼 수 있겠네 하겠지만 P1이 다 사용되고 반환되어도 총 남는 테이프는 4개 밖에 안돼서 P0나 P2를 해결해줄 수 없습니다 ㅠ(각각 5개, 6개가 필요하니까요) P2도 해결해줄 수 없으니 결국 t1시간에 시스템은 불완전상태가 되는거예요. 

 

If we had made P2 wait until either of the other processes had finished and released its resources, then we could have avoided the deadlock

즉 운영체제는 t1시간에 P2 프로세스가 자원 하나를 요청했을 때 빌려줘야할까요? 교착상태에 빠질 가능성이 있으니까 빌려주지 않겠죠! 만약 P2에게 자원을 하나 빌려주지 않고, P1이 먼저 끝나도록 했으면 교착상태에 걸리지 않고 해결할 수 있었을 거예요. 

The idea is imply to ensure that the system will always remain in a safe state.

시스템이 항상 안전상태를 유지할 수 있게 하는 것 이것이 바로 은행가 알고리즘입니다.

 

은행원 알고리즘의 단점

- 할당할 수 있는 자원의 수가 일정해야 합니다.

- 사용자 수가 일정해야 합니다.

- 항상 불안전 상태를 방지해야 하므로 자원 이용도가 낮습니다.

- 최대 자원 요구량을 미리 알아야 합니다.

- 프로세스들은 유한한 시간 안에 자원을 반납해야 합니다.

 

즉 은행원 알고리즘은 알고리즘이 엄청나게 복잡합니다. 즉 OS가 이거 하다가 아무것도 못하는 상황이 발생하면 안되잖아요. 또 은행원 알고리즘은 해당 프로세스가 시작할 때 프로세스가 가지고 있어야 할 자원의 최대 개수를 미리 알아야 하기 때문에 실제 돌아가는 프로그램에 적용하기도 상당히 어렵습니다. 오버헤드가 너무 커요. 그래서 현재 채택하고 있는 방식은 아닙니다.

 

개념 잡는데 도움이 되셨나요?! 도움이 됐다면 상부상조! 광고는 짱짱 동기부여가 된답니다. 앞으로 더 좋은 포스팅으로 찾아뵐게요 (꾸벅)

 

문제

정보처리기사 기출

교착상태와 은행원 알고리즘의 불안전상태에 대한 설명으로 옳은 것은?

1. 교착상태는 불안전상태에 속한다.

2. 불안전상태의 모든 시스템은 궁극적으로 교착상태에 빠지게 된다

3. 불안전상태는 교착상태에 속한다.

4. 교착상태와 불안전상태는 서로 무관하다.

 

답: 1