[11] 운영체제 - Deadlock-3

안녕하세요. 중간고사라서 포스팅이 상당히 미루어졌는데요...!!

6주차 수업에서는 5주차 복습과 간단히 Deadlock detection algorithm과 복구 방법에 대해서 배웠습니다.

그리하여 다행히 포스팅이 미뤄져도 6주차와 7주차를 포스팅하는 데는 크게 문제가 없을 것 같습니다!

그리고 6주차는 상당히 짧은 포스팅이 될 것 같은데요! 이 짧은 글을 이해하시려면 반드시 저번 주차 포스팅을

한번 보고 오시는 게 상당한 도움이 되실 것입니다. 그럼 바로 시작하겠습니다.

저번 포스팅에서는 Deadlock Avoidance, Prevention에 대해 알아보았는데요!

위의 방법들은 Deadlock을 안 일어나게끔 하는 방법들이라면 지금부터 알아볼 Deadlock detection은 Deadlock이 발생 한 이후에 

Deadlock을 감지하여 그 후에 Deadlock에 빠진 상태에서 복구하는 방법입니다. 즉 Deadlock이 일어난 후에 해결하는 방법이지요.

그럼 복구방법을 알아보기 전에 현재 Deadlock이 발생했는지를 알아보는 Deadlock detection algorithm을 알아보도록 하겠습니다.

Deadlock detection algorithm

이 알고리즘은 이전에 다뤘던 Banker's Algorithm과 크게 다르지 않습니다. 

먼저  자원의 인스턴스가 하나일 때 사용하는 Wait-for-Graph에 대해서 알아보도록 하겠습니다.

Wait-for-Graph

Resource-Allocation Graph에서는 자원에 대해 소유하고 있는 상황도 표현하였다면 Wait-for Graph에서는 단순히

프로세스가 다른 프로세스가 끝나고 자원을 반납하는 것을 기다리는 상황만을 표현해줍니다.

Wait-for Graph에서도 사이클이 존재한다면 현재 Deadlock에 빠졌다는 것을 의미합니다.

즉 전자는 자원이 할당되기 전 Deadlock 상태를 파악하고 자원 할당을 막는 반면

후자는 자원을 할당해주고 Deadlock이 빠졌는지를 판단합니다.

두 번째로 자원의 인스턴스가 다수일 때는 Banker's Algorithm과 매우 흡사한 방법을 사용합니다.

바로 알고리즘을 살펴보도록 하겠습니다.

Banker's Algorithm 과의 차이점은 모든 자료구조는 같지만 Need 대신 Request를 사용한다는 점입니다.

Need와 Request의 차이점은 Need는 현재 상태에서 요청은 하지 않아도 궁극적으로 작업을 끝내기 위해 필요한 자원의 양이고 Request는 당장 현재 상태에서 특정 자원을 요청한 상황을 말합니다.

그리고 알고리즘에서도 몇몇 차이점을 찾아볼 수 있는데요. 

1단계를 살펴보면 Allocation != 0 then Finish[i] =false; Otherwise Finish[i] = true;라는 부분을 찾아보실 수 있으실 텐데요.

Allocation이 0이라는 것은 현재 이 프로세스에 할당된 자원이 없다는 뜻이고 이것은 Deadlock이 발생하기 위한 조건 중 Hold & Wait를 위배하므로 이 프로세스는 Deadlock을 유발하지 않는 프로세스라는 뜻입니다.

그러므로 Finish[i] = true로 만들어주어 검사를 하지 않게 됩니다. 

Allocation이 0이 아니라면 현재 자원을 소유하고 있다는 뜻이고, 자원을 요청을 할 수도 있기 때문에 Hold & Wait 상황의 여지가 있기에 Finish[i] = false로 하여 2단계에서 검사를 진행하게 됩니다.

2, 3단계는 Banker's Algorithm과 같으며 4단계를 살펴보면 할당해줄 것을 모두 할당해주고 Finish[i] = false인 프로세스가 존재한다면 그 프로세스는 Deadlock에 빠져있는 프로세스이므로 이러한 방법으로 Deadlock에 빠져있는 프로세스를 찾아냅니다.

예를 들어보겠습니다.

이 예제에서는 현재 상황에서  Available 값이 모두 0이지만 P(0)가 아무 자원도 요청하지 않기 때문에 작업을 끝내면 자원을 반납하고 반납한 자원으로 P(2)에게 할당하면서 Safe State Sequence를 만들어낼 수 있기 때문에

현재 이 상태는 Deadlock에 빠져있지 않은 상태입니다.

만일 다음과 같이 Request를 바꿔준다면 어떻게 될까요?

P(0)가 자원을 반납하더라도 P(2)의 현재 요청 자원이 바뀜으로 인해 현재 아무 프로세스에게도 자원을 할당해줄 수  없으므로 현재 P(1), P(2) ,P(3) ,P(4)는 Deadlock에 빠져있는 프로세스라고 판단할 수 있습니다.

그렇다면 이젠 Deadlock을 복구하는 방법을 알아보겠습니다.

복구하는 방법에는 다양한 방법이 있겠지만 비효율적이고 복잡하여 대부분의 시스템에서는 다음과 같은 방법을 사용합니다.

1. 현재 상태에서 모든 프로세스를 종료.

2. Deadlock에 빠져있는 프로세스들을 하나씩 종료해가며 Deadlock에서 탈출.

Deadlock detection은 지속해서 현재 상태를 검사하며 또한 프로세스를  종료 시킨 후 다시 시작해야 하는 등 많은 비용이 들기 때문에 비효율적이라 판단되어 현재 다수의 시스템에서는 사용되지 않고 있습니다.

이렇게 오늘의 포스팅까지  Deadlock 전반에 대해서 알아보았습니다.

Deadlock은 상당히 중요한 문제이고 치명적일 수 있으므로 반드시 숙지하시고

다른 서적과 글들을 통해 보다 확실히 공부해보시길 바라겠습니다.

그럼 다음 시간에는 운영체제의 메모리 관리에 대하여 공부해보도록 하겠습니다.

감사합니다!