[OS] 교착상태 회피방법: 은행원 알고리즘(Banker's Algorithm)

 프로세스가 필요한 자원을 얻지 못해 무한정 대기하는 상황을 교착상태라고 합니다. 이러한 교착상태가 생기지 않도록 회피하는 방법인 '은행원 알고리즘'에 대해 알아봅니다.

 

[ Contents ]

 

 

1. 은행원 알고리즘

 은행에서 돈을 빌려주듯이, 운영체제가 자원을 할당할 때 요구한 양만큼 차례차례 빌려주는 알고리즘

 

 은행원 알고리즘은 교착상태가 되지 않도록 회피하는 자원 할당 방식입니다.

 교착상태는 대체로 Hold and Wait 상태로부터 기인합니다. 따라서 프로세스의 요구 자원을 모두 챙겨주고 이를 반환시키는 걸 목표로 합니다.

 은행으로 비유하자면, 전액 빌려줄 수 있는 대출부터 차근차근 해주는 프로세스입니다. 만약 일부만 대출해줄 경우, 잔금을 받아낼 때까지 갚지 않을 테니까요.

 

2023.07.31 - [CS] - [OS] 교착상태(Dead Lock)의 정의와 발생조건 4가지: 상호배제, 점유와 대기, 비선점, 환형대기

[OS] 교착상태(Dead Lock)의 정의와 발생조건 4가지: 상호배제, 점유와 대기, 비선점, 환형대기

 

 

 

2. 안전상태와 불안전상태

1) 안전 상태 (Safe state)

각 프로세스가 요구한 만큼 차례차례 필요한 자원을 할당할 수 있는 상태

 

 안전 상태는 아무렇게나 자원을 할당해도 교착상태가 되지 않는 상태는 아닙니다.

 적은 자원이 필요한 프로세스부터 차례차례 할당하면 교착상태를 회피할 수 있는 상태를 말합니다. 이를 '안전 순서열'이라고 하며, 안전 순서열대로 자원을 할당하고 회수하면 교착상태가 발생하지 않습니다.

 

 

2) 불안전 상태 (Unsafe state)

각 프로세스가 요구한 자원만큼 할당할 수 없는 상태

 

 이미 상당한 자원이 프로세스에 할당된 상태로, 남은 자원으로 프로세스가 요구하는 자원을 충당할 수 없는 경우를 뜻합니다. 다만 불안전 상태가 곧 '교착 상태'를 의미하진 않습니다.

 이미 할당된 프로세스로부터 자원을 회수해서 불안전 상태를 해소할 수 있으며, 다시 안전 상태로 돌아갈 수 있습니다. 만약 자원을 회수할 수 없다면 불안전 상태는 교착 상태로 굳어지게 됩니다. (불안전 상태는 교착 상태의 필요조건)

 

반응형

 

3. 은행원 알고리즘의 한계

1. 항상 불안전 상태를 회피해야 하므로 자원 활용도가 낮음
2. 최대 자원 요구량을 미리 알고 있어야 함
3. 자원과 프로세스, 사용자 수가 일정해야 함

 

 은행원 알고리즘은 '교착 상태'를 회피할 수 있는 방법이지만, 운영 관리가 어렵고 자원 효율성도 낮기 때문에 실무에서 사용하진 않습니다. 프로세스의 최대 자원 요구량을 계산하고, 프로세스의 최대 요구량을 충족시킬 수 있는 자원을 비축해둬야 하기 때문입니다.