#24 데드락 해결 by 은행원 알고리즘(Banker's algorithm)

https://en.wikipedia.org/wiki/Banker's_algorithm

● 교착상태 회피

- 교착상태 해결방법으로 교착상태 회피(deadlock avoidance)라는 방법이 있다.

- 이는 운영체제(OS)가 프로세스들에게 어느 정도의 자원을 할당해야 교착상태가 발생하는지 파악해서 교착상태가 발생하지 않는 수준의 자원을 할당하는 것이다.

출처 - 인프런, 그림으로 쉽게 배우는 운영체제

---

- 교착상태 회피는 전체 자원의 수와 할당된 자원의 수를 기준으로 안정상태(Safe state)와 불안정 상태(Unsafe state)를 나눈다.

- OS는 최대한 안정상태를 유지하기위해 자원 할당을 한다.

- 단, (불안정상태 = 교착상태)는 아니고 교착상태에 빠질 확률이 높다는 것을 의미한다.

---

● 은행원 알고리즘(Banker's algorithm)

- 교착상태 회피를 표현한 알고리즘이 바로 은행원 알고리즘(Banker's algorithm)이다.

ex)

출처 - 인프런, 그림으로 쉽게 배우는 운영체제

1. 은행에 돈이 1000만원 있다고 가정해보자

2. 사업가 A는 은행에서 500만원을 빌렸다.

3. 사업가 B는 은행에서 400만원을 빌렸다. 현재 은행에는 100만원이 남아있는 상태이다.

4. 시간이 지나 은행은 A에게 돈을 갚으라고 하는데 A는 지금은 갚을 수 없고 200만원만 더 빌려주면 그것으로 돈을 벌어 갚겠다고 말했다.

5. 은행은 현재 100만원 밖에 없기 때문에 B에게 빌려준 돈을 받아서 A에게 200만원을 빌려주려고 한다.

6. 이에 은행은 B에게 돈을 갚으라고 하는데 B 역시 지금은 갚을 수 없고 200만원만 더 빌려주면 그것으로 돈을 벌어 갚겠다고 말했다.

7. 결국 은행은 누구에게도 돈을 빌려주지도 못 하고 빌려준 돈을 받을 수도 없는 교착상태에 빠졌다.

 

- 은행은 이러한 상황을 피하기 위해 돈을 빌려줄 때 은행의 여윳돈과 사업가들에게 빌려준 돈들을 보고 대출 가능한 상황(= 안전상태)인지 확인하고 빌려주는데 이것을 은행원 알고리즘이라고 한다.

---

- OS에서 은행원 알고리즘을 구현하는 방법을 자세히 알아보자

 

1. 

- OS는 프로세스들에게 자원을 할당하기 전에 자신이 가지고 있는 전체 자원의 수를 알고 있어야한다.

- 이때 (OS가 가지고 있는 전체 자원의 수 = 시스템의 총 자원)이라고 하자

 

2. 

- 프로세스들은 각자 자신에게 필요한 자원의 최대 숫자를 OS에게 알려줘야 한다.

- 이때 (프로세스가 필요한 자원의 최대숫자 = 최대 요구 자원)이라고 하자

 

3. 안정상태

- 현재 (OS가 가지고 있는 전체 자원의 수 = 시스템의 총 자원)의 수는 14개이다.

- 프로세스 P1의 (최대 요구 자원 = 9개)이고 (현재 할당된 자원 = 5개)이다.

- 프로세스 P2의 (최대 요구 자원 = 6개)이고 (현재 할당된 자원 = 4개)이다.

- 프로세스 P3의 (최대 요구 자원 = 4개)이고 (현재 할당된 자원 = 3개)이다.

프로세스	최대 요구 자원	현재 할당된 자원
P1	9	5
P2	6	4
P3	4	3

- P1 ~ P3에게 할당된 자원은 총 12개이기에 현재 사용 가능한 (시스템의 총 자원 여유 = 2개)이다.

- 해당 여유 자원들을 가지고 프로세스들의 요청이 예상되는 자원을 제공할 수 있다.

 

3-1.

- 여기서 은행원 알고리즘은 각 프로세스가 현재 요구할 수 있는(= 요청이 예상되는) 자원을 구한다.

- 프로세스 P1의 (최대 요구 자원 = 9개)이고 (현재 할당된 자원 = 5개)이기에 (요청이 예상되는 자원 = 4개)이다.

- 프로세스 P2의 (최대 요구 자원 = 6개)이고 (현재 할당된 자원 = 4개)이기에 (요청이 예상되는 자원 = 2개)이다.

- 프로세스 P3의 (최대 요구 자원 = 4개)이고 (현재 할당된 자원 = 3개)이기에 (요청이 예상되는 자원 = 1개)이다.

- 이때 P1 ~ P3가 모두 추가 자원을 요청했다고 해보자

프로세스	최대 요구 자원	현재 할당된 자원	요청이 예상되는 자원
P1	9	5	4
P2	6	4	2
P3	4	3	1

- 만약 P1이 4개의 자원을 추가로 요청하면 현재 (여유 자원 = 2개)이기에 P1의 요청을 거부하고 P2의 요청을 받는다.

- P2는 2개를 요청했기 때문에 (여유 자원 = 2개)를 전부 P2에게 할당한다.

- P2는 할당된 자원을 가지고 작업을 마친 후 6개의 자원을 반납한다.

프로세스	최대 요구 자원	현재 할당된 자원	요청이 예상되는 자원
P1	9	5	4
P2	6	0	6
P3	4	3	1

- P2의 반납으로 (여유 자원 = 6개)가 됐기에 P1과 P3가 요청한 추가 자원을 모두 할당할 수 있는 상태가 되었다.

 

4. 불안정상태

프로세스	최대 요구 자원	현재 할당된 자원	요청이 예상되는 자원
P1	9	7	2
P2	6	4	2
P3	4	2	2

- 동일하게 현재 (OS가 가지고 있는 전체 자원의 수 = 시스템의 총 자원)의 수는 14개라고 했을 때

- P1 ~ P3에게 할당된 자원은 총 13개이기에 현재 사용 가능한 (시스템의 총 자원 여유 = 1개)이다.

- (여유 자원 = 1개)만으로는 P1 ~ P3의 추가 요구 자원(2개)을 모두 충족할 수가 없기에 불안정 상태가 된다.

- 단, 불안정 상태에 있더라도 모든 프로세스가 최대 자원을 요청하지 않는다면 교착상태에 빠지지 않지만 불안정 상태 자체에 빠지지 않도록 유지하는 것이 최선이라고 할 수 있다.

---

● 교착 상태 검출

- 은행원 알고리즘(Banker's algorithm)은 교착상태를 피하는 좋은 방법이지만 비용이 비싸고 비효율적이다.

- 그렇기에 OS 연구자들은 교착상태의 발생은 허용하되 교착상태가 발생했을 때 이를 해결하는 방식을 연구했다.

※ 주의 : 은행원 알고리즘은 교착상태를 회피하는 방법이지 해결하는 방법은 아니다.

- OS 연구자들은 어떻게 교착상태를 검출할 것인지를 고민했고(현재 상태가 교착상태인지 아닌지 확인 필요) 2가지 방식을 고안했다.

 

1. 가벼운 교착 상태 검출

- 타이머를 이용하는 방법으로 프로세스가 일정 시간동안 작업을 진행하지 않는다면 교착상태가 발생했다고 간주하여 교착상태를 해결한다.

- 여기서 교착상태를 해결하는 방법은 간단하다.

- 일정 시점마다 체크포인트를 만들어 작업을 저장하고 타임아웃으로 교착상태가 발생했다면 가장 마지막으로 저장했던 체크포인트로 롤백하는 것이다.

 

2. 무거운 교착 상태 검출

- 자원 할당 그래프를 이용하는 방법으로 OS에서 현재 프로세스가 어떤 자원을 사용하는지 지켜보고 교착상태가 발생했다면 이를 해결한다.

 

Q. 그래프를 이용해서 교착상태가 발생했는지 어떻게 알 수 있을까?

A. 아래 그림 보면서 설명

- 프로세스들은 각자 자원을 차지하고 있고 분홍색 화살표로 다른 자원을 요청하고 있는 상태이다.

- 왼쪽 그래프는 순환구조가 생기지 않기 때문에 교착상태가 없는 그래프이다.

- 오른쪽 그래프는 순환구조가 생기기 때문에 교착상태가 생긴 그래프이다.

- 교착상태를 검출했다면 교착상태를 일으킨 프로세스를 강제 종료 시킨후 다시 실행시킬 때 가장 마지막으로 저장했던 체크포인트로 롤백시킨다.

출처 - 인프런, 그림으로 쉽게 배우는 운영체제

- 장점 : 가벼운 교착 상태 검출에서 발생할 수 있는 억울하게 종료되는 프로세스가 발생하지 않는다.

- 단점 : OS가 지속적으로 자원 할당 그래프를 유지하고 검사해야 하기 때문에 오버헤드 발생

 

cf) 같이 읽으면 좋은 글

https://velog.io/@seorim0801/%EC%9D%80%ED%96%89%EC%9B%90-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

은행원 알고리즘?