-
[문제해설] 은행가 알고리즘(Banker's Algorithm)은 교착상태의 해결 방법 중 어떤 기법에 해당하는가?전자계산기조직응용기사/필기 기출문제 해설 2021. 12. 1. 06:44반응형
전자계산기조직응용기사 필기 기출문제 해설(4과목 운영체제-교착상태) - 2017년3회
은행가 알고리즘(Banker's Algorithm)은 교착상태의 해결 방법 중 어떤 기법에 해당하는가?
① Avoidance ② Detection
③ Prevention ④ Recovery
- 문제 해설 -
다음은 20세기 초에 미국 캔자스 주 의회에서 통과된 법률입니다.“When two trains approach each other at a crossing, both shall come to a full stop and neither shall start up again until the other has gone.”
"두 개의 열차가 교차로에서 서로 접근하면 둘 다 완전히 정지해야 하며 다른 하나가 갈 때까지 둘 다 다시 출발하지 못한다."
교차로에서의 끔찍한 사고 발생을 방지하기 위한 법이지만, 위와 같은 법이라면, 교차로에서 두 열차가 마주치면, 두 열차는 영원히 멈추게 됩니다. 두 열차 모두 같은 법이 적용되니 서로 마주한 열차가 먼저 지나가기를 기다리게 되기 때문입니다.
운영체제가 프로세스를 관리하는 중 발생하는 교착상태(deadlocks)는 이와 같습니다. 교착상태란 프로세스 집합 내의 모든 프로세스가 그 집합의 다른 프로세스에 의해서만 일어날 수 있는 이벤트를 기다리는 상황입니다.
컴퓨터가 교착상태에 빠지면, CPU는 영원한 대기상태로 빠지게 됩니다. 다운이 된 것이죠.(물론, 시스템이 다운되는 현상은 다른 이유도 있습니다.) 교착상태가 되려는 4가지 조건은 "1. 상호 배제(mutual exclusion), 2. 점유하며 대기(hold-and-wait), 3. 비선점(no preemption), 4. 순환 대기(circular wait)"입니다. 이 네 가지 조건이 동시에 성립되어야 합니다.
이러한 교착상태를 처리하는 방법 4가지 유형은 다음과 같습니다.
교착상태 예방
(Deadlock Prevention)- 교착상태 필요조건 중 적어도 하나가 성립하지 않도록 보장하는 일련의 방법
- 장치의 이용률이 저하되고 시스템 처리율(thoughput)이 감소함교착상태 회피
(Deadlock Avoidance)- 스레드가 평생 요구하고 사용할 자원에 대한 부가적인 정보를 미리 제공할 것을 요구한다. 교착상태 탐지
(Deadlock Detection)- 교착상태에 있는 프로세스를 발견하는 방법 교착상태로부터 회복
(Recovery from Deadlock)- 교착상태로부터 회복한다.
- 교착 상태 프로세스를 모두 중지하거나 하나씩 중지
- 자원을 회수(희생자 선택, 후퇴(roolback), 기아 상태(starvation)를 고려위의 4가지 유형은 본문제에서의 보기들입니다.
그럼 문제에서 묻는 은행가 알고리즘(Banker's Algorithm)에 대해 간략하게 알아보겠습니다.
은행가 알고리즘의 명칭은 은행에서 고객들에게 원활한 서비스를 제공할 수 있도록 업무를 처리하는 절차와 비슷하다고 해서 붙여진 이름입니다. 은행가 알고리즘의 간단한 예를 들어보겠습니다.
보유하고 있는 자본이 총 1000원인 은행에 3명의 고객이 대출을 하기 위해 찾아왔습니다.
첫 번째 고객은 900원, 두번째 고객은 200원, 세번째 고객은 300원을 대출하기를 원합니다.
만약, 은행에서 선착순으로 돈을 빌려줄 경우, 첫 번째 고객에게 900원을 빌려주게 됩니다. 그럼 은행의 남은 돈은 100원뿐이라 나머지 고객들은 첫번째 고객이 돈을 갚을때까지 기다려야 합니다. 그런데 900원을 빌려간 첫번째 고객이 그만 망해버려 돈을 갚을 수가 없게 되면, 은행은 나머지 고객에게 돈을 빌려주지도 못하고, 망하게 됩니다.
은행이 모든 고객에게 서비스를 제공해주며, 망하지 않으려면, 우선 대출을 신청한 고객들에 대해 조사를 해야 합니다.
고객들의 상황을 조사해보니 위와 같습니다. 첫 번째 고객은 부채가 1100원이라서 900원을 빌려줘도 현재 상황을 해결하지 못하고 돈을 갚지 못할 확률이 높습니다. 두 번째 고객은 본인이 원하는 200원만큼의 부채를 가지고 있으며, 이것을 해결하면 바로 300원으로 갚을 수 있습니다. 3번째 고객은 부채가 400원인데 급한 300원을 대출받기를 원하고 있으며 본인 부채를 모두 해결하면 바로 갚을 수 있는 상황입니다.
고객의 상황을 파악한 은행은 우선 두 번째 고객에게 200원을, 세 번째 고객에겐 300원이 아니라 400원을 대출해줍니다. 그럼 두번째 고객은 금방 이자를 합친 300원을 갚고, 세번째 고객도 500원을 갚을 수 있게 됩니다. 그럼 은행의 총자산은 1200원이 됩니다. 그리고 첫 번째 고객에게 900원이 아닌 1100원을 빌려주어 본인의 채무를 해결하고 1300원으로 상환하면 은행의 총자산은 1400원이 됩니다.
이처럼 선착순이 아니라, 고객의 상황을 파악한 후 적절한 순서로 대출을 하게 되면, 모든 고객들에게 서비스를 제공하면서 은행은 자산을 불릴 수가 있습니다. 실제 우리가 은행에 가서 대출을 받을 때도 이와 비슷하게 신용도 등을 조회한 후 대출을 받습니다.
이처럼 은행은 망하지 않게 안전상태(Safe State)를 유지하기 위해 서비스 제공하는 순서를 적절히 정해야 합니다. 이는 은행이 망하는 상황을 피하기 위함입니다. 즉 은행원 알고리즘은 회피(Avoidance) 기법이므로 문제의 정답은 1번입니다.
https://youtube.com/playlist?list=PLboXycXmAIDuukQ2A6EvMZI-x1IMy3Xc-
반응형'전자계산기조직응용기사 > 필기 기출문제 해설' 카테고리의 다른 글