은행원 알고리즘
더 많은 작업
은행원 알고리즘(Banker's Algorithm, 은행가 알고리즘)은 프로세스가 자원을 요청할 때마다 그 요청을 들어준 뒤에도 시스템이 안전 상태로 남는지 미리 검사해, 안전할 때만 자원을 할당함으로써 교착상태를 회피하는 알고리즘이다.
에츠허르 데이크스트라(Edsger W. Dijkstra)가 1965년 제안했다. 은행이 모든 고객의 대출 한도 요구를 동시에 들어줄 만큼 현금을 갖고 있지 않아도, 고객들이 차례로 대출을 받아 갚을 수 있는 순서가 있으면 파산하지 않는다는 데서 이름이 왔다. 은행은 운영체제, 현금은 자원, 고객은 프로세스, 대출 한도는 프로세스가 선언한 최대 요구량에 해당한다.
교착상태 대처 방법 가운데 회피(avoidance)에 속한다. 예방처럼 교착상태의 네 가지 필요조건 중 하나를 원천적으로 막지는 않지만, 할당할 때마다 위험한 상태로 들어가는 것을 피한다.
- 안전 상태(safe state) : 모든 프로세스가 최대 요구량까지 자원을 받아 끝낼 수 있는 실행 순서(안전 순서열, safe sequence)가 하나 이상 있는 상태
- 불안전 상태(unsafe state) : 그런 순서가 없는 상태. 불안전 상태가 곧 교착상태는 아니지만, 교착상태로 갈 가능성이 있다
- 교착상태는 불안전 상태의 부분집합이다. 은행원 알고리즘은 시스템을 항상 안전 상태에 머물게 해서 교착상태를 피한다
- 프로세스 수(n)와 자원 종류 수(m)가 고정되어 있다.
- 각 프로세스는 실행 전에 자원별 최대 요구량을 미리 선언한다.
- 자원을 다 받은 프로세스는 유한한 시간 안에 작업을 끝내고 자원을 모두 반납한다.
n은 프로세스 수, m은 자원 종류 수이다.
| 자료구조 | 크기 | 의미 |
|---|---|---|
| Available | 1×m | 자원 종류별로 지금 남아 있는(할당 가능한) 수 |
| Max | n×m | 프로세스별로 각 자원을 최대 몇 개까지 요구할 수 있는지 |
| Allocation | n×m | 프로세스별로 각 자원을 현재 몇 개 할당받았는지 |
| Need | n×m | 앞으로 더 필요한 수. Need = Max − Allocation |
- Work = Available, 모든 프로세스 i에 대해 Finish[i] = false로 둔다.
- Finish[i] = false이고 Need[i] ≤ Work인 프로세스 i를 찾는다. 없으면 4로 간다.
- 그 프로세스가 끝까지 실행되어 자원을 반납한다고 보고 Work = Work + Allocation[i], Finish[i] = true로 한 뒤 2로 돌아간다.
- 모든 i에 대해 Finish[i] = true이면 안전 상태이고, 3에서 고른 순서가 안전 순서열이다. 아니면 불안전 상태이다.
시간 복잡도는 O(m × n²)이다.
프로세스 i가 Request[i]만큼 자원을 요청하면:
- Request[i] ≤ Need[i]인지 확인한다. 아니면 선언한 최대치를 넘었으므로 오류다.
- Request[i] ≤ Available인지 확인한다. 아니면 자원이 모자라므로 프로세스 i는 기다린다.
- 요청을 들어줬다고 가정하고 상태를 바꿔 본다.
- Available = Available − Request[i]
- Allocation[i] = Allocation[i] + Request[i]
- Need[i] = Need[i] − Request[i]
- 바뀐 상태로 안전성 검사를 한다. 안전하면 실제로 할당하고, 불안전하면 원래 상태로 되돌린 뒤 프로세스 i를 기다리게 한다.
프로세스 5개(P0~P4), 자원 3종(A, B, C)이고 전체 자원은 A=10, B=5, C=7이다.
| 프로세스 | Allocation (A B C) | Max (A B C) | Need (A B C) |
|---|---|---|---|
| P0 | 0 1 0 | 7 5 3 | 7 4 3 |
| P1 | 2 0 0 | 3 2 2 | 1 2 2 |
| P2 | 3 0 2 | 9 0 2 | 6 0 0 |
| P3 | 2 1 1 | 2 2 2 | 0 1 1 |
| P4 | 0 0 2 | 4 3 3 | 4 3 1 |
Available = (3 3 2)
안전성 검사:
| 순서 | 선택 | Need ≤ Work 확인 | 반납 후 Work |
|---|---|---|---|
| 1 | P1 | (1 2 2) ≤ (3 3 2) | (5 3 2) |
| 2 | P3 | (0 1 1) ≤ (5 3 2) | (7 4 3) |
| 3 | P4 | (4 3 1) ≤ (7 4 3) | (7 4 5) |
| 4 | P2 | (6 0 0) ≤ (7 4 5) | (10 4 7) |
| 5 | P0 | (7 4 3) ≤ (10 4 7) | (10 5 7) |
모든 프로세스가 끝나므로 안전 상태이고 <P1, P3, P4, P2, P0>이 안전 순서열이다.
이 상태에서 P1이 (1 0 2)를 요청하면, (1 0 2) ≤ Need(1 2 2)이고 (1 0 2) ≤ Available(3 3 2)이다. 할당했다고 가정하면 Available = (2 3 0), P1의 Allocation = (3 0 2), Need = (0 2 0)이 된다. 다시 검사하면 <P1, P3, P4, P0, P2> 순서로 모두 끝낼 수 있으므로 요청을 허용한다.
| 장점 | 한계 |
|---|---|
| 교착상태 예방보다 자원 이용률이 높다. 필요조건을 깨는 제약 없이 위험한 할당만 피한다 | 프로세스가 최대 요구량을 미리 알아야 하는데 실제로는 알기 어렵다 |
| 교착상태가 아예 생기지 않으므로 탐지·회복 비용이 없다 | 프로세스와 자원 수가 고정되어야 한다. 실행 중 프로세스가 생기고 사라지는 범용 운영체제에 맞지 않는다 |
| 이론적으로 정확하다 | 요청마다 O(m × n²) 검사를 해서 오버헤드가 크다 |
| 안전 상태 유지를 위해 남는 자원이 있어도 요청을 거절할 수 있다(보수적) | |
| 프로세스가 유한 시간 안에 자원을 반납한다는 가정이 필요하다 |
이런 한계 때문에 범용 운영체제는 은행원 알고리즘을 거의 쓰지 않고, 자원 수와 요구량이 정해진 임베디드·실시간 시스템이나 데이터베이스 자원 관리에서 개념을 활용한다.
| 방법 | 원리 | 예 |
|---|---|---|
| 예방(prevention) | 네 가지 필요조건(상호 배제, 점유와 대기, 비선점, 환형 대기) 중 하나를 원천 차단 | 자원을 한꺼번에 요청, 자원에 순서 번호를 붙여 오름차순으로만 요청 |
| 회피(avoidance) | 할당 전에 안전 상태 유지 여부를 검사 | 은행원 알고리즘, 자원 할당 그래프 알고리즘(자원 종류당 1개일 때) |
| 탐지·회복(detection, recovery) | 교착상태를 허용하고 주기적으로 찾아 해소 | 대기 그래프의 순환 탐지 후 프로세스 종료나 자원 선점 |
| 무시 | 드물게 일어난다고 보고 대처하지 않음 | 대부분의 범용 운영체제(타조 알고리즘) |
- E. W. Dijkstra, 「Cooperating Sequential Processes」, EWD123, 1965.
- A. Silberschatz, P. B. Galvin, G. Gagne, 『Operating System Concepts』, Wiley.