뱅커 알고리즘
Banker's algorithm뱅커 알고리즘(Banker algorithm)은, 때로는 검출 알고리즘(Detection algorithm)이라고 일컬어지기도 하는, Edsger Dijkstra가 개발한 자원 할당 및 교착 회피 알고리즘으로, 미리 결정된 모든 자원의 최대 가능량의 할당을 시뮬레이션하여 안전성을 시험한 다음, 다음에, 다음, 다음, 다음, 다음, 에 대한 가능한 교착 상태를 시험하기 위해 "s-상태" 검사를 실시한다.할당을 계속하도록 허용해야 하는지 여부를 결정하기 전에 다른 보류 중인 활동.
알고리즘은 THE 운영 체제의 설계 프로세스에서 개발되었으며 EWD108에서 원래 (네덜란드어로) 설명되었다.[1] 새로운 프로세스가 시스템에 진입할 때, 새로운 프로세스는 자신이 주장할 수 있는 각 리소스 유형의 최대 인스턴스 수를 선언해야 한다. 분명히, 그 수는 시스템의 총 리소스 수를 초과하지 않을 수 있다. 또한, 프로세스가 요청된 모든 자원을 얻었을 때, 한정된 시간 내에 그것들을 반환해야 한다.
자원.
뱅커의 알고리즘이 작동하려면 다음 세 가지를 알아야 한다.
- 각 프로세스에서 요청할 수 있는 리소스 수[]최대]
- 각 프로세스가 현재 보유하고 있는 리소스 수[개별 리소스 수할당됨]
- 시스템에서 현재 사용할 수 있는 각 리소스 수[사용 가능한 리소스 수]사용 가능]
자원은 요청된 자원의 양이 가용한 양보다 작거나 같은 경우에만 공정에 할당될 수 있다. 그렇지 않으면 공정이 자원을 사용할 수 있을 때까지 기다린다.
실제 시스템에서 추적되는 리소스 중 일부는 메모리, 세마포어, 인터페이스 액세스 등이다.
은행 알고리즘은 은행이 더 이상 모든 고객의 요구를 충족시킬 수 없는 방식으로 자금을 배분하지 않기 때문에, 은행이 자원이 고갈되지 않도록 하기 위해 이 알고리즘을 은행 시스템에서 사용할 수 있다는 사실에서 유래한다.[2] 은행은 은행 알고리즘을 사용하여 고객이 돈을 요청할 때 은행이 절대 안전한 상태를 벗어나지 않도록 보장한다. 고객의 요청이 은행으로 하여금 안전한 상태를 유지하도록 하지 않는다면, 현금은 할당될 것이고, 그렇지 않으면 고객은 다른 고객이 충분히 예치할 때까지 기다려야 한다.
은행원 알고리즘을 구현하기 위해 유지해야 할 기본 데이터 구조:
을(를) 시스템의 프로세스 개수로 하고 을(를) 리소스 유형의 개수로 설정하십시오. 그렇다면 다음과 같은 데이터 구조가 필요하다.
- 사용 가능: 길이 m의 벡터는 각 유형의 사용 가능한 자원의 수를 나타낸다. 사용 가능[j] = k인 경우 리소스 유형 R의j 인스턴스(instance)가 k개 있다.
- Max: × 행렬은 각 프로세스의 최대 수요를 정의한다. Max[i,j] = k인 경우 P는i 리소스 유형j R의 대부분의 k 인스턴스를 요청할 수 있다.
- 할당: × 행렬은 각 프로세스에 현재 할당된 각 유형의 리소스 수를 정의한다. 할당[i,j] = k이면 프로세스 P는i 현재 리소스 유형 R의j k 인스턴스(instance)가 할당된다.
- : n × 행렬은 각 프로세스의 남은 리소스 요구를 나타낸다. Need[i,j] = k인 경우i P는 작업을 완료하기 위해 리소스j 유형 R의 인스턴스(instance)를 더 많이 필요로 할 수 있다.
참고: 필요[i,j] = 최대[i,j] - 할당[i,j] n=m-a
예
총 시스템 리소스: A B C D 6 5 7 6
사용 가능한 시스템 리소스: A B C D 3 1 1 2
프로세스(현재 할당된 리소스): A B C D P1 1 2 2 1 P2 1 P2 1 0 3 3 3 P3 1 2 1 0
프로세스(최대 리소스): A B C D P1 3 2 2 P2 1 2 3 4 P3 1 3 5 0
니즈 = 최대 리소스 - 현재 할당된 리소스 프로세스(필요한 리소스): A B C D P1 2 1 0 1 P2 0 2 0 1 P3 0 1 4 0
안전 및 안전하지 않은 상태
상태(위의 예와 같이)는 모든 프로세스가 실행(종료)을 마칠 수 있다면 안전한 것으로 간주된다. 시스템은 프로세스가 언제 종료될 것인지 또는 그 때까지 요청된 자원의 수를 알 수 없기 때문에, 시스템은 모든 프로세스가 결국 명시된 최대 자원을 획득하려고 시도하고 그 후에 곧 종료될 것으로 가정한다. 시스템이 각 프로세스가 얼마나 오래 실행되는지(적어도 교착 회피적 관점에서 실행되지 않음)와 특별히 관련이 없기 때문에 대부분의 경우 이는 합리적인 가정이다. 또한 프로세스가 최대 자원을 획득하지 않고 종료되는 경우 시스템에서 프로세스가 더 쉬워질 뿐이다. 준비 대기열을 처리할 경우 안전 상태가 의사결정자로 간주된다.
그러한 가정을 감안하여 알고리즘은 각자가 최대 자원을 획득한 다음 종료(자원을 시스템으로 되돌리는)할 수 있는 프로세스에 의한 가상의 요청 집합을 찾으려고 시도함으로써 상태가 안전한지 여부를 결정한다. 그러한 세트가 존재하지 않는 모든 상태는 안전하지 않은 상태다.
각 공정이 최대 자원을 획득한 다음 종료할 수 있다는 것을 보여줌으로써 앞의 예에서 주어진 상태가 안전한 상태임을 보여줄 수 있다.
- P1은 2A, 1B, 1D의 자원이 더 필요하여 최대치를 달성한다.
- [사용 가능한 자원: <3 1 1 2> - <2 1 0 1> = <1 0 1>]
- 시스템에 현재 사용 가능한 1A, B, 1C 및 1D 리소스가 있음
- P1이 종료되어 시스템에 3A, 3B, 2C 및 2D 리소스를 반환함
- [사용 가능한 자원: <1 0 1> + <3 3 2> = <4 3 3 3 3 3 3>]
- 이제 시스템에는 4A, 3B, 3C 및 3D 리소스가 제공됨
- P2는 2 B와 1 D의 추가 자원을 획득한 후, 종료하고, 모든 자원을 반환한다.
- [사용 가능한 자원: <4 3 3 3> - <0 2 0 1> + <1 2 3 4> = <5 3 6 6>]
- 현재 시스템에는 5A, 3B, 6C, 6D 리소스가 있다.
- P3는 1 B와 4 C 자원을 획득하여 종료한다.
- [사용 가능한 자원: <5 3 6> - <0 1 4 0> + <1 3 5 0> = <6 5 7 6>]
- 이제 시스템에 모든 리소스가 있음: 6A, 5B, 7C 및 6D
- 모든 프로세스가 종료될 수 있었기 때문에 이 상태는 안전하다.
안전하지 않은 상태의 예를 들어 프로세스 2가 초기에 리소스 B의 1단위를 보유할 경우 어떻게 되는지 고려하십시오.
요청한다
시스템이 자원에 대한 요청을 받으면 은행원 알고리즘을 실행하여 요청을 허가해도 안전한지 판단한다. 알고리즘은 일단 안전과 안전하지 않은 상태의 구분이 이해되면 상당히 간단하다.
- 요청을 허용할 수 있는가?
- 그렇지 않으면 요청이 불가능하므로 거부하거나 대기자 명단에 올려야 한다.
- 요청이 부여되었다고 가정하십시오.
- 새 주는 안전한가?
- 그렇다면 요청을 허용하십시오.
- 그렇지 않은 경우 요청을 거부하거나 대기 목록에 넣으십시오.
시스템이 불가능하거나 안전하지 않은 요청을 거부하거나 연기하는지는 운영 체제에 특정한 결정이다.
예
이전 예제에서 시작된 것과 동일한 상태에서 시작하여 프로세스 1이 리소스 C의 2단위를 요청한다고 가정하십시오.
- 요청을 승인하는 데 사용할 수 있는 리소스 C가 충분하지 않음
- 요청이 거부됨
한편, 프로세스 3이 리소스 C의 1단위를 요청한다고 가정한다.
- 요청을 승인하기에 충분한 자원이 있다.
- 요청이 승인되었다고 가정하십시오.
- 이 시스템의 새로운 상태는 다음과 같다.
사용 가능한 시스템 리소스 A B C D 무료 3 1 0 2
프로세스(현재 할당된 리소스): A B C D P1 1 2 2 1 P2 1 P2 1 0 3 3 P3 1 2 0
프로세스(최대 리소스): A B C D P1 3 2 2 P2 1 2 3 4 P3 1 3 5 0
- 이 새 상태가 안전한지 확인
- P1은 2 A, 1 B, 1 D 자원을 획득하여 종료할 수 있다.
- 그 후, P2는 2 B, 1 D 자원을 획득하여 종료할 수 있다.
- 마지막으로, P3는 1 B와 3 C 자원을 획득하여 종료할 수 있다.
- 그러므로 이 새로운 상태는 안전하다.
- 새 주가 안전하므로 요청을 허용하십시오.
마지막 예: 시작 단계부터 프로세스 2가 리소스 B의 1단위를 요청한다고 가정해 보십시오.
- 자원이 충분하다.
- 요청이 승인된다고 가정할 경우, 새로운 상태는 다음과 같다.
사용 가능한 시스템 리소스: A B C D 자유 3 0 1 2
프로세스(현재 할당된 리소스): A B C D P1 1 2 2 5 1 P2 1 3 3 P3 1 2 1 0
프로세스(최대 리소스): A B C D P1 3 2 2 P2 1 2 3 4 P3 1 3 5 0
- 이 주(州)는 안전한가? P1, P2, P3이 더 많은 자원 B와 C를 요청한다고 가정한다.
- P1은 충분한 B 자원을 획득할 수 없다.
- P2는 충분한 B 자원을 획득할 수 없다.
- P3는 충분한 B 자원을 획득할 수 없다.
- 어떤 프로세스도 종료할 수 있는 충분한 자원을 획득할 수 없으므로 이 상태는 안전하지 않다.
- 상태가 안전하지 않으므로 요청을 거부하십시오.
수입하다 불결한 로서 np n_bea = 인트로(입력하다('프로세스 수? ')) n_bea = 인트로(입력하다('자원의 수? ')) 사용 가능한_message = [인트로(x) 을 위해 x 에 입력하다('클레임 벡터? ').갈라지다(' ')] current_properties = np.배열하다([[인트로(x) 을 위해 x 에 입력하다(f'현재 공정을 위해 할당됨 {i + 1}? ').갈라지다(' ')] 을 위해 i 에 범위(n_bea)]) max_demand = np.배열하다([[인트로(x) 을 위해 x 에 입력하다(f'프로세스로부터의 최대 수요 {i + 1}? ').갈라지다(' ')] 을 위해 i 에 범위(n_bea)]) total_available = 사용 가능한_message - np.합계를 내다(current_properties, 축을=0) 러닝의 = np.하나(n_bea) # 프로세스가 아직 실행되지 않았음을 나타내는 n_processes 1이 있는 배열 하는 동안에 np.count_nonzero(러닝의) > 0: at_time_one_message = 거짓의 을 위해 p 에 범위(n_bea): 만일 러닝의[p]: 만일 전부(i >= 0 을 위해 i 에 total_available - (max_demand[p] - current_properties[p])): at_time_one_message = 진실의 인쇄하다(f'{p} 달리고 있다') 러닝의[p] = 0 total_available += current_properties[p] 만일 아닌 at_time_one_message: 인쇄하다('안전하지 않다') 부숴뜨리다 # 출구 다른: 인쇄하다('안전하다')
제한 사항
다른 알고리즘과 마찬가지로 뱅커의 알고리즘도 구현 시 몇 가지 한계가 있다. 구체적으로, 그것은 한 프로세스가 얼마나 많은 자원을 요청할 수 있는지 알아야 한다. 대부분의 시스템에서는 이 정보를 사용할 수 없기 때문에 뱅커의 알고리즘을 구현할 수 없다. 또한 대부분의 시스템에서는 프로세스 수가 동적으로 변화하기 때문에 프로세스 수가 정적이라고 가정하는 것은 비현실적이다. 더욱이 프로세스가 최종적으로 모든 자원을 방출한다는 요구사항(프로세스 종료 시)은 알고리즘의 정확성에 충분하지만, 실제 시스템에는 충분하지 않다. 자원이 방출될 때까지 몇 시간(또는 며칠)을 기다리는 것은 일반적으로 허용되지 않는다.
참조
- ^ Dijkstra, Edsger W. Een algorithme ter voorkoming van de dodelijke omarming (EWD-108) (PDF). E.W. Dijkstra Archive. Center for American History, University of Texas at Austin. (transcription)(네덜란드어; 치명적인 포옹을 방지하기 위한 알고리즘)
- ^ Silberschatz, Galvin, & Gagne (2013). Operating System Concepts, 9th Edition. Wiley. p. 330. ISBN 978-1-118-06333-0.
{{cite book}}
: CS1 maint : 복수이름 : 작성자 목록(링크)
추가 읽기
- 실버스챗츠, 갈빈, 가그네의 「운영 체제 개념」(7판 259-261쪽)
- 실버스챗츠, 갈빈, 가그네의 「운영 체제 개념」(8판 298-300쪽)
- Dijkstra, Edsger W. The mathematics behind the Banker's Algorithm (EWD-623) (PDF). E.W. Dijkstra Archive. Center for American History, University of Texas at Austin. (번역) (1977년), Edsger W. Dijkstra, Selected Writes on Computing: A Personal Perspective, Springer-Verlag, 1982년) 308–312페이지로 출판되었다. ISBN 0-387-90652-5