Dijkstra의 Bankers 알고리즘

Question

누군가 은행가 알고리즘을 사용하여 다음 문제를 해결하기위한 단계적 접근 방식을 제공 할 수 있습니까? "안전 상태"가 존재하는지 어떻게 결정합니까? 프로세스가 "완료로 실행"할 수있는 것은 무엇을 의미합니까?

이 예에는 동일한 리소스의 4 가지 프로세스와 10 개의 인스턴스가 있습니다.

          Resources Allocated | Resources Needed
Process A                   1                  6
Process B                   1                  5
Process C                   2                  4
Process D                   4                  7

Answer 1

당 위키 백과,

모든 프로세스가 실행 (종료)이 완료 될 수있는 경우 상태 (위의 예에서와 같이)는 안전한 것으로 간주됩니다. 시스템은 프로세스가 언제 종료 될 것인지 또는 그때까지 요청한 리소스 수를 알 수 없으므로 시스템은 모든 프로세스가 결국 명시된 최대 리소스를 획득하고 곧 종료하려고 시도한다고 가정합니다. 시스템은 각 프로세스가 얼마나 오래 실행되는지 (적어도 교착 상태 회피 관점에서 나오지 않음) 대부분의 경우 합리적인 가정입니다. 또한 프로세스가 최대 리소스를 얻지 않고 종료되면 시스템에서만 더 쉽게 만듭니다.

필요한 각 유형의 리소스 수를 사용하여 자체와 시스템간에 프로세스가 완료 될 수 있습니다. 프로세스에 주어진 리소스의 8 단위가 필요한 경우 5 개 단위를 할당 한 경우 할당 할 수있는 3 개 이상의 단위가 더 있으면 완료 될 수 있습니다.

예를 들어, 시스템은 단일 리소스를 관리하고 있으며 10 개의 장치를 사용할 수 있습니다. 런닝 프로세스는 이미 8 (1+1+2+4) 장치를 할당 했으므로 2 개의 단위가 남아 있습니다. 프로세스를 완료 해야하는 금액은 이미 할당 된 내용이 최대 최대이므로 처음에는 A가 더 필요합니다 (6-1), B는 4 개 더 필요합니다 (5-1), C는 2 개 더 필요합니다 (4- 2), D는 3 더 필요합니다 (7-4). 사용 가능한 2 개가 있으므로 프로세스 C를 완료 할 수 있으므로 2 개의 유닛을 확보 할 수 있습니다 (4 개는 사용 가능). 이 시점에서 B 또는 D를 실행할 수 있습니다 (D가 가정). D가 완료되면 8 개의 유닛이 제공되며 A 또는 B를 실행할 수 있습니다 (A). A가 완료되면 9 개의 유닛이 사용 가능한 다음 B를 실행할 수 있으므로 추가 작업을 위해 10 개의 유닛이 모두 남게됩니다. 모든 프로세스를 실행할 수있는 프로세스 순서를 선택할 수 있으므로 상태는 '안전'으로 간주됩니다.

Answer 2

  Resources Allocated | Resources Needed    claim
  Process A      1                  6            5
  Process B      1                  5            4
  Process C      2                  4            2
  Process D      4                  7            3

할당 된 총 리소스는 8이므로 2 개의 리소스가 아직 할당되지 않으므로 프로세스 C에 할당됩니다. C 및 프로세스 C를 마감 한 후 프로세스 B에 제공 될 수있는 4 개의 리소스를 완화 한 후 프로세스 B를 완료 한 후 프로세스 B를 배정하는 5 개의 리소스가 처리됩니다. 마무리 후 N 프로세스 A는 2 개의 리소스를 처리하기 위해 2 개의 리소스를 할당합니다.