[운영체제] Deadlock Handling #2(deadlock avoidance)

오늘은 deadlock을 다루는 방법 중 deadlock avoidance에 대해 알아보겠습니다.

deadlock avoidance는 circular wait이 발생하지 않는 알고리즘을 찾는 방법입니다.즉, 어떤 프로세스부터 자원 사용을 완료해야 deadlock이 발생하지 않는지를 찾는 것입니다.

 

네모는 자원, 동그라미는 프로세스, 검은 점은 자원에 있는 instance입니다.

검은 점과 연결된 프로세스는 그 자원을 이용하고 있다는 의미이고, 네모 바깥을 화살표로 가르키고 있는 프로세스는 그 자원을 요청하고 있다는 의미입니다.

 

여기서 P3, P2, P1 순서로 실행한다면 circular wait이 발생하지 않습니다.

이런 상태를 Safe State라고 하고, P3->P2->P1을 Safe Sequence라고 합니다.

Safe State가 존재한다면 deadlock은 발생하지 않습니다.

하지만 Unsafe State라고 deadlock이 무조건 발생한다는 것이 아니라 deadlock이 발생할 가능성이 있다는 의미입니다.

 

처음에 deadlock avoidance는 circular wait이 발생하지 않는 알고리즘을 찾는 방법이라고 했었습니다.

그 중 하나인 Banker's Algorithm에 대해 알아보겠습니다.

 

Banker's Algorithm에서 사용하는 자료구조입니다.

Available(=Work) : 사용 가능한 자원 수

Max: 프로세스가 요청한 자원 수

Allocation: 프로세스에게 이미 할당된 자원 수

Need: 프로세스에게 할당된 자원 이외에 더 필요한 자원 수

(Need = Max - Allocation)

 

Banker's Algorithm을 이용한 예제 문제를 하나 풀어보겠습니다.

프로세스는 P0, P1, P2, P3, P4이고 자원은 a, b, c입니다.

a의 총 instance 수는 10개이고,  b는 5개, c는 7개입니다.

위에서 언급했듯이 Need = Max - Allocation 입니다.

a, b, c가 프로세스에 총 할당된 개수가 각각 7, 2, 5 이므로 처음에 이용가능한 자원은 10-7, 5-2, 7-5로 각각 3, 3, 2입니다.

따라서 맨 처음 Available은 3, 3, 2 로 되어있습니다. 

Available이 Need 보다 크거나 같아야 프로세스가 필요한 자원을 모두 사용하고, 프로세스는 작업을 마칠 수 있습니다.

따라서 Available >= Need 인 프로세스를 먼저 실행하면서 모든 프로세스가 작업을 마칠 수 있게 되면 Safe State가 되는 것입니다.

 

Available >= Need 인 프로세스를 먼저 실행한 후에 그 프로세스가 종료되면서 이미 갖고 있던 자원은 더 이상 사용하지 않게 되면서 다른 프로세스들이 그 자원을 이용할 수 있게됩니다.

따라서 작업을 종료한 프로세스에 할당된 자원(Allocation에 있는 자원의 수)을 다른 프로세스들이 이용할 수 있게 Available에 더해주어야 합니다.

 

 

Deadlock이 발생하지 않고 모든 프로세스가 작업을 완료할 수 있게 되었기 때문에 Safe State가 되었습니다.

Safe Sequence는 P1->P3->P4->P0->P2입니다.