은행원 알고리즘

컴퓨터언어/운영체제

bbanpro 2020. 7. 8. 18:54

728x90

👍 은행원 알고리즘이란?

짧게 복습하면,

다중프로그래밍에서 여러 프로세스가 한정된 자원을 오류 없이 사용하도록 순서를 부여한 것이 상호배제였고,

상호배제라는 것 때문에 특정 상황에서 대기중인 프로세스가 무한정 기다리게 되는 불상사가 생긴 것이 교착상태였다.

그리고 교착상태를 아예 제거한다는 것은 앞선 상호배제부터 부정한다는 말이기 때문에 다중프로그래밍으로서 모순이 있어 좋지 않은 방법이었고,

교착상태를 인정하되 똘똘한 운영체제가 알아서 회피해가자는 것이 "교착상태 회피"였다.

그리고 교착상태 회피의 알고리즘이 바로 "은행원 알고리즘"이다.

은행원 알고리즘은 은행에서 대출해주는 직원에서 착안한 것이다.

대출하고자 하는 고객 = 프로세스

고객의 대출한도 = 프로세스가 실행에 있어 필요로 하는 자원의 총량

고객이 실제 대출한 금액 = 프로세스가 현재 사용하고 있는 자원의 양

은행의 총 보유금액 = 운영체제가 가지고 있는 총 자원의 수

은행의 현 보유액 = 운영체제가 분배해주고 남은 자원의 수

은행의 목적은 다음과 같다.

각 고객에게 대출한도만큼 모두 대출해 주어라!
(= 각 프로세스가 필요로 하는 자원을 모두 할당하라)

그리고 가정은 다음과 같다.

이 가상은행은 컴퓨터와 같아서 대출한도만큼 모두 대출해주면, 고객은 그 즉시 모두 상환한다.
다시 말해, 은행원 알고리즘은 각 프로세스는 필요로 하는 자원을 다 할당받으면, 그 즉시 다른 프로세스를 위해 모두 반환한다.

예를 들어 어떤 은행의 총 보유금액이 10억이며, 다음과 같이 4명에게 대출을 해주고 3억이 남아 있다고 가정하자.

현재 은행 잔고가 3억이므로 은행원은 머리를 잘 굴려야 한다.

은행원의 목표는 단 하나다.

남은 잔고를 가지고 어느 고객에게 돈을 빌려주어야 대출한도를 딱 맞추기 쉬울까

만약 A에게 또 빌려준다고 하면, A는 남은 금액이 10억을 채우기까지 무려 7억이나 남았는데, 현재 은행 잔고는 3억밖에 안되기 때문에 너무 불안정해진다. A에게 빌려주고 나면 나머지 고객에게 대출을 해줄 수 없기 때문이다.

그래서 은행원은 A에게는 잠시 기다리라고 희망고문을 한 뒤, 상대적으로 대출한도에 근접할 수 있는 고객이 올 때까지 기다린다.

그 후보로는 B 또는 C가 될 수 있다.

B와 C는 모두 남은 대출금액이 현재 잔고와 딱 맞기 때문에, 고객이 아무리 적게 대출한다고 해도 A와 D 보다는 대출한도를 금방 달성하기 쉬우며, 이는 A와 D가 대출금액을 모두 상환하고 exit함을 의미한다.

그러면 은행은 잔고가 6억이 되므로, 이어서 D에게 대출해주고 마지막으로 A에게 대출해주면 모든 대출업무는 완료된다.

이를 컴퓨터로 바꾸면 다음과 같다.

👊 은행원 알고리즘의 특징

728x90