[OS/운영체제] Banker's Algorithm / 은행원 알고리즘

1. Banker's Algorithm이란?

• Deadlock을 회피하는 방법 중 한가지로 자원의 갯수가 2개 이상인 사이클에서 데드락을 회피할 때 사용하는 알고리즘이다.
• 알고리즘이 Banker's인 이유는 은행에서 100만원을 대출하려면 은행이 먼저 100만원을 가지고 있어야 대출해줄 수 있다. 만약 100만원이 없다면 은행은 돈을 빌려줄 수 없다. 이처럼 할당해 줄 수 있는 자원이 충분한지를 먼저 검사하고 교착상태에 빠질 가능성이 없으면 자원을 할당해주는 방식이다.

아래의 그림을 예시로 Banker's Algorithm을 살펴보자

2. 그림으로 살펴보는 Banker's Algorithm

아래 그림은 은행원 알고리즘을 이해하는데 가장 쉬운 그림이다. 차례대로 사용되는 용어를 알아보자면

A, B, C : 각 자원 // P1, P2, P3 : 각 프로세스

Allocation : 프로세스가 처음 실행됐을 때 할당받은 자원의 양을 나타낸다.

Max Need : 프로세스가 최대로 요청할 수 있는 범위를 나타낸다. 항상 Max Need만큼 요청하지 않을 수도 있다.

Current Available : 프로세스들이 자원을 요청했을 때 빌려줄 수 있는 자원의 수를 타나낸다.

Remaining Need : 프로세스가 이미 할당받은 자원을 제외하고 최대로 요청할 수 있는 자원의 갯수를 나타낸다. Max Need - Allocation 값이다. 

출처 : https://cstaleem.com/deadlock-avoidance

2-1. Banker's Algorithm의 자원 할당 방식

결론부터 말하자면 Banker's Algorithm은 자원을 요청하는 프로세스의 Remaining Need값이 Current Available을 초과할 경우자원을 할당해주지 않는다. 반대로 Remaining Need 값이 Current Available을 초과하지 않는 Safe State에만 자원을 할당해준다.

Available값은 할당해줄수 있는 최대 값을 나타내는데 만약 Remaining Need 값이 Current Available값보다 1이라도 넘치게 되면 절대 할당을 해주지 않는다. P1을 예시로 보면 P1의 Remainiing Need 값은 7 4 3이기 때문에 Current Abailable값을 훨씬 넘는다. 물론 P1이 Remaining Need값 전부를 항상 할당 요청하는 것은 아니다. 언제는 A자원만 1개를 요청할 때도 있고 언제는 ABC 전부 다 최대로 요청할 수도 있다. Current Available안에서 요청하더라도 P1의 요청은 잠재적으로 Current Available값을 초과한 자원을 요청할 수 있는 가능성이 있기 때문에 절대 할당해주지 않는다. 이처럼 Banker's 알고리즘은 굉장히 보수적이다.

2-2. 자원 할당과 Safe Sequence

P2를 예시로 보면 P2는 최대로 자원을 요청하더라도 Current Available값을 넘지 않는다. 그렇기 때문에 P2가 자원을 요청하면 할당해주게 된다. 이후 프로세스 P2가 실행을 완료하게 되면 가지고 있는 CPU자원을 모두 반납하기 때문에 Current Available값은 기존 P2에게 할당된 Allocation + 할당받은 P2의 Remaining Need값을 더한 A-4, B-5, C-4로 증가하게 된다.

P4 Remaining Need값은 현재 Current Available 4 5 4보다 낮기 때문에 또 P4가 자원을 요청하면 할당해줄 수 있으며 P4의 실행이 완료되게 되면 Current Available값은 6 6 5로 증가한다. 이처럼 할당 가능한 프로세스들 먼저 처리해주고 완료시키면 자원이 늘어나기 때문에 P2>P4>P5>P3>P1 순서로 실행하게 되면 모든 프로세스를 실행시킬 수 있다.
이와 같이 모든 프로세스가 데드락을 발생시키지 않으며 정상적으로 실행하고 종료할 수 있는 순서를 Safe Sequence라고 한다. Safe Sequence가 존재한다면 프로세스들은 Deadlock이 일어나지 않는 Safe State를 유지할 수 있다. 반대의 의미로 UnSafe State는 조금이라도 비정상적인 종료(Deadlock)가 발생할 수 있는 상황을 말한다. 하지만 UnSafe State라고 해서 무조건 Deadlock이 일어나는 것은 아니다

2-3. Banker's Algoritm의 특징

장점

1. 교착 상태가 발생하기 전에 예방할 수 있다

2. 교착 상태를 예방하기 때문에 시스템 성능 향상을 기대할 수 있다

단점

1. 프로세스의 자원 요청 순서를 변경하지 못할 경우 사용하지 못한다.

2. 프로세스가 얼만큼의 자원을 사용할 지 미리 파악하고 알고있어야 하며 중간에 자원 사용량이 늘어나는 상황은 허용하지 않는다.

3. 항상 Safe State를 유지해야 하기 때문에 자원 사용량이 낮아진다.

 

CS 지식을 공부하고 기록하는 개인 공부 블로그입니다.
내용 중 틀린 부분 피드백 혹은 궁금한 점이 있으면 댓글로 남겨주시면 참고 및 답변 달아드리겠습니다🧐