[CS] DeadLock과 은행원 알고리즘

먼저 Dead Lock (교착 상태)이 무엇인지 알아보자.

 

Dead Lock 이란 두 개 이상의 프로세스가 서로 상대방의 작업이 끝나기만을 기다리면서 결과적으로 아무도 완료되지 못하는 상태를 의미한다. 교착 상태가 발생하려면 4가지 조건이 필요하다. 조건은 아래와 같다.

상호 배제 (Mutual Exclusion)

한 번에 한 개의 프로세스만이 공유 자원을 사용할 수 있어야 한다.

점유 대기 (Hold and Wait)

프로세스가 할당된 자원을 가진 상태에서 다른 자원을 기다려야 한다.

비선점 (No preemption)

프로세스에게 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없어야 한다.

환형 대기 (Circular Wait)

각 프로세스는 순환적으로 다음 프로세스가 요구하는 자원을 가지고 있어야 하며, 이러한 요구는 환형이 되어야 한다.

 

Dead Lock을 해결하는 방법으로는 위의 4가지 조건을 제거하는 방법이 있으나, 자원 사용의 효율성이 떨어지고 비용이 많이 든다. 따라서, Dead Lock을 회피하는 방법을 사용하고, 대표적인 알고리즘으로는 은행원 알고리즘이 존재한다.

은행원 알고리즘? 🏦

은행원 알고리즘이란 '최소한 고객 한 명에게 대출해줄 금액은 항상 은행이 보유하고 있어야 한다'라는 개념에서 나온다. 해당 알고리즘은 교착 상태에 빠질 가능성이 있는지 판단하기 위해 상태를 안전 상태와 불안전 상태로 나누고, 안전 상태를 유지할 수 있는 요구만을 수락하고, 불안전 상태를 초래할 수 있는 사용자의 요구는 만족될 수 있을 때까지 계속해서 거절하는 방법이다. 

 

은행원 알고리즘이 수행되기 위해서는 3가지 요소가 필요하다.

 

◎ Max : 각 프로세스가 자원을 최대로 얼마까지 요청할 수 있는지

◎ Allocated : 각 프로세스가 현재 보유하고 있는 자원이 얼마인지

◎ Available : 시스템이 자원을 얼마나 보유하고 있는지

 

안전 상태는 시스템이 교착 상태를 일으키지 않고, 각 프로세스가 요구한 양 만큼 자원을 할당해줄 수 있는 상태로, 안전 순서열이 존재하는 상태이다. 불안전 상태는 안전 순서 열이 존재하지 않는 상태, 즉 아무런 방법이 없는 상태이다. 교착 상태는 불안전 상태일 때만 발생하고, 불안전 상태라고 해서 무조건 교착 상태인 것은 아니다.

 

이렇게만 들으면 이해가 잘 가지 않으니 같이 예시를 보자.

시스템은 12개의 자원을 가지고 있고, 프로세스는 P1, P2, P3 3개가 존재한다. 

P1의 경우 10개의 자원이 필요하고, P2는 4개 P3는 9개의 자원이 각각 필요하다.

 

이러한 상황에서 0이라는 시각에 P1이 5개, P2가 2개, P3가 2개의 자원을 가져가고 시스템에는 3개의 자원이 남았다고 가정해보자. 이러한 상황에서 0이라는 시각에 시스템은 안전 상태이다.

 

1 시각에 Case 1과 같이 P2에게 2개의 자원을 할당하고 P2 작업이 끝난 이후 4개의 자원을 돌려받아 P1이나 P3의 작업을 완료할 수 있는 안전 순서 열이 존재하기 때문이다. (P2 -> P1 -> P3 or P2 -> P3 -> P1)

 

하지만, 시스템은 안전 상태에서 불안전 상태로 변할 수 있다.

 

예를 들어 안전 상태 였던 0 시각에서 시간이 흘러 1 시각에 Case 2 같은 상황이 벌어지면 어떻게 될까?

P3가 자원을 하나 더 요청하여, 하나의 자원을 할당하고 시스템이 가지고 있는 자원은 2가 된다. 이 상황에서는 안전 순서 열이 존재하지 않는다. P1을 완료하려면 5개의 자원이 더 필요하니 일단 불가능하고, P2는 2개의 자원이 더 필요하니 현재 자원을 다 빌려준다 하더라도, 돌아오는 자원은 4개뿐이니 P1과 P3 모두 해결할 수 없다. 결국 1 시각은 불안전 상태가 되는 것이다.

 

즉, 운영체제는 1이라는 시각에 P3이 자원을 하나 더 요청했을 때, 자원을 빌려줘야 할까? 🤔

만약 교착 상태에 빠질 가능성이 있으면 빌려주지 않고 P2를 먼저 끝내는 안전 순서열을 지켰다면 교착 상태에 빠지지 않고 해결할 수 있었을 것이다.

 

이렇게 시스템이 안전 상태를 유지할 수 있도록 하는 것이 은행원 알고리즘이다.