다익스트라의 은행원 알고리즘은 교착상태가 발생하지 않도록 하기 위한 알고리즘이다. 이 알고리즘은 은행에서 고객에게 대출을 바로 해 줄 것인지 나중에 해 줄 것인지를 은행의 잔고 상태에 따라 결정하듯, 특정 시스템이 자원 할당을 신중하게 조절해 교착 상태를 회피하는 방법이다.
교착상태를 아예 제거한다는 것은 상호배제를 부정하는 것이므로 다중프로그래밍에서 적합한 해결책이 될 수 없다. 따라서 교착상태가 우려되는 불안정상태에서는 자원을 추가 할당하지 않고, 교착상태 걱정이 없는 안정상태일 경우에만 프로세스에 자원을 추가 할당해줌으로써 교착상태를 회피한다.
| 은행 | 운영체제 |
|---|---|
| 은행보유금액 | 컴퓨터시스템의 총 자원수 |
| 은행원 | 운영체제 |
| 고객 | 프로세스 |
| 대출금액 | 프로세스가 현재 사용하고 있는 자원수 |
| 대출한도 | 프로세스가 완료될 때까지 필요한 자원수 |
| 불안정상태 | 교착상태가 될 수 있는 상태 |
| 안정상태 | 교착상태의 우려가 없는 상태 |
| 은행부도 | 교착상태 |
은행 보유금이 10억이고 고객 A, B, C, D 4명에게 총 7억이 대출된 상태이다. 은행의 잔고는 3억이다.
| 고객 | 대출금액 | 대출한도 |
|---|---|---|
| A | 3 억 | 10 억 |
| B | 1 억 | 4 억 |
| C | 2 억 | 5 억 |
| D | 1 억 | 7 억 |
- 잔고 3억을 모두 대출해줘도 A는 여전히 4억을 더 대출받아야 한다
- 이 경우, 다른 고객들은 대출을 받을 수도 없고 A도 대출받은 금액을 상환할 수 없다
- 즉, 교착상태에 빠질 가능성이 있는 불안정상태가 되므로 은행은 고객 A에게는 대출을 해주지 않아야 한다
- B나 C는 잔고 3억을 대출해주면 대출한도를 충족한다
- B나 C는 대출한도가 충족되는 즉시 가지고 있던 자금을 모두 상환하므로 A, D 고객에게도 대출한도만큼 대출을 해줄 수 있게 된다
- 즉, 교착상태에 빠질 가능성이 없는 안정상태이므로 B 또는 C에게 대출을 해주어야 한다