Deadlock에 대해 마지막으로 공부해 볼 내용은 바로 Deadlock Avoidance, 즉 교착상태 회피입니다. Deadlock Avoidance의 가장 핵심 아이디어는 어떤 자원을 요청할 때, 추가적인 정보를 제공하도록 요구하는 것입니다. 즉, 각각의 프로세스들이 어떤 자원을 어떤 순서로 사용할 것이라는 것을 이미 시스템이 알고 있다면, 미래에 Deadlock이 발생하지 않기 위해 어떤 프로세스가 대기를 해야 하는지 결정할 수 있을 것입니다. 이러한 방법으로 Deadlock의 발생 조건 4가지 중 적어도 하나 이상을 성립하지 않게 만들어줄 수 있습니다.
1. Safe State (안전 상태)
시스템이 안전하다는 말은 시스템이 어떤 순서로든 프로세스들이 원하는 모든 자원을 Deadlock 없이 차례대로 모두 할당해 줄 수 있다는 것을 의미합니다. 다시 말해, 시스템이 안전 순서 (Safe Sequence)를 찾을 수 있다면 그 시스템은 안전한 상태라고 말할 수 있습니다. 이는 현재 남아있는 자원과 또 앞으로 방출될 자원들을 이용해 시간에 따라 모든 프로세스들이 자신이 원하는 자원들을 모두 확보할 수 있다는 뜻입니다. 따라서 시스템이 안전하다면, Deadlock은 일어나지 않습니다.
반대로 Deadlock 상태에 빠진 시스템들은 불안전한 상태에 있습니다. 물론 모든 불안전한 시스템들이 Deadlock에 걸려있는 것은 아닙니다. 시스템이 불안전하다는 말은 "앞으로 Deadlock으로 가게 될 수도 있다."고 말할 수 있습니다. 시스템이 안전 상태에 머무르고 있다면, Deadlock을 완벽히 예방할 수 있지만, 일단 불안전 상태에 들어가게 되면, 프로세스는 Deadlock이 발생할 수도 있는 자원 할당을 막을 수 있는 방법은 없습니다.
안전이라는 개념을 이해했다면, 이제 시스템이 불안전한 영역으로 가지 않도록 하는 알고리즘을 생성할 수 있습니다. 최초의 시스템은 당연히 안전 상태에서 시작하므로, 그 후에 프로세스들의 자원 요청을 받아들일지 여부를 판단하는 과정에서 반드시 시스템이 안전한 상태를 유지하도록 하는 결정만을 하게 만들어 주면 됩니다.
물론 이러한 알고리즘들을 이용하면 자원이 남아 있더라도 상황에 따라 프로세스에게 할당을 못해주는 경우가 생길 수 있기 때문에 자원이 이용률은 하락할 수밖에 없습니다.
2. 자원 할당 그래프 알고리즘 (Resource-Allocation Graph Algorithm)
자원 할당 그래프 알고리즘은 각각의 자원 타입들이 하나의 인스턴스만을 가질 때 사용할 수 있습니다. 여기서 우리는 앞에서 배운 자원 할당 그래프에 예약 간선(claim edge)이라는 개념을 도입하여 사용할 수 있습니다. 이 예약 간선은 아래의 그림에서 점선으로 표시된 edge이며, 미래에 해당 프로세스가 가리키고 있는 자원을 요청할 것이라는 뜻입니다.
Claim edge를 그려봤는데 cycle이 탐지되지 않는다면, 해당 자원은 할당해줘도 시스템은 안전 상태에 머무를 수 있게 됩니다. 반대로 claim edge를 추가한 그래프가 cycle을 포함하고 있다면, 당장 해당 자원을 할당해 주는 것은 시스템을 불안전하게 만들 수 있습니다. 당연히 아래의 그림과 같은 상황이라면, P1은 R2를 할당받아서는 안됩니다.
3. 은행원 알고리즘 (Banker's Algorithm)
하지만 자원 할당 그래프 알고리즘은 각각의 자원이 여러 개 씩 존재한다면 (여러 개의 인스턴스를 가진다면) 사용할 수가 없게 됩니다. 앞의 글에서 자원 할당 그래프에 대해 공부할 때 사용했던 예시인 아래 그림에서는 R3와 R4가 둘 이상의 인스턴스를 가지기 때문에 (각각 2개, 3개) 자원 할당 그래프 알고리즘을 사용할 수 없습니다.
이러한 상황에서 사용할 수 있는 것이 바로 은행원 알고리즘입니다. 이 알고리즘에서는 새로운 프로세스가 시작할 때 자신이 가지고 있어야 할 자원의 최대 개수를 먼저 선언해주어야 합니다. 그러면 시스템은 이 요청을 들어주었을 때 시스템이 그대로 안전한 지를 판단하고, 안전하다면 해당 요청을 들어주게 됩니다. 물론 불안전하게 변하게 된다면, 프로세스는 다른 프로세스가 끝날 때까지 대기해야 합니다.
은행원 알고리즘을 사용하기 위해서는 몇 가지 자료구조를 사용해야 합니다. n은 프로세스의 수, m은 자원의 종류로 정의 하겠습니다.
Available: 각 종류 별로 사용 가능한 자원의 개수를 나타내는 벡터이며, 길이는 m이다. Available[j] = k라는 뜻은 현재 j라는 자원을 k개 사용할 수 있다는 뜻이다.
Max: 각 프로세스가 최대로 필요로 하는 자원의 개수를 나타내는 행렬. 크기는 n x m. Max[i,j] = k 라면, i라는 프로세스가 j라는 자원을 최대 j개까지 요청할 수 있다는 뜻이다.
Allocation: 각 프로세스들이 현재 사용하고 있는 자원의 개수를 나타내는 행렬. 크기는 n x m. Allocation[i, j] = k라면 현재 i라는 프로세스가 j라는 자원을 k개 사용하고 있다는 뜻이다.
Need: 각 프로세스가 사용할 수 있는 남은 자원의 개수. 크기는 n x m. Need[i,j] = k 라면 i라는 프로세스가 j라는 자원을 k개까지 더 요청할 수 있다는 뜻이다. Need[i,j] = Max[i,j] - Allocation[i,j].
1. 안정성 알고리즘 (Safety Algorithm)
현재 시스템이 안전한 지를 검사하는 알고리즘은 다음과 같습니다. 참고로 Work는 크기가 m, Finish는 크기가 n인 벡터입니다.
1. Work = Available로 초기화해주고, 모든 i에 대해 Finish[i] = false로 초기화해줍니다.
2. Finish[i] == false이고, Need[i] <= Work인 i를 찾습니다. 만약 찾을 수 없다면 4번째 단계로 넘어갑니다.
3. Work = Work + Allocation[i], Finish[i] = true를 해준 뒤, 2번째 단계로 돌아갑니다.
4. 모든 i에 대해 Finish[i]==true라면, 해당 시스템은 안전하다고 할 수 있습니다.
2. 자원 요청 알고리즘 (Resource-Request Algorithm)
다음으로는 자원 요청을 안전하게 승인해 줄 수 있는지에 대해 검사하는 알고리즘을 살펴보겠습니다. Request[i]는 i라는 프로세스의 요청 벡터입니다. 그래서 만약 Request[i][j] == k라면, i라는 프로세스가 j라는 자원을 k개 요청하고 있다는 뜻입니다. 프로세스 i가 자원을 요청하게 되면 다음과 같은 과정을 거칩니다.
1. 만일 Request[i] <= Need[i]라면, 즉, 프로세스의 요청이 시스템이 허용해 줄 수 있는 개수보다 적다면, 2번째 단계로 갑니다. 그렇지 않다면, 이미 시스템에 남아있는 개수보다 더 많은 요청이므로, 오류로 처리합니다.
2. 만일 Request[i] <= Available이면, 즉, 요청한 자원이 현재 남아있다면, 3단계로 갑니다. 그렇지 않다면, 현재 요청한 자원이 당장은 없으므로 프로세스는 대기해야 합니다.
3. 시스템이 자원을 할당해 줄 수 있으므로, 다음과 같이 상태를 변경해줍니다.
Available = Available - Request[i]
Allocation[i] = Allocation[i] + Request[i]
Need[i] = Need[i] - Request[i]
이렇게 변경한 상태가 안전하다면, 프로세스 i에게 요청받은 자원들을 할당해줍니다. 그렇지 않다면, 다시 원래의 상태로 되돌려줍니다.
이렇게 해서 Deadlock에 대해 모두 공부해보았습니다. 이제 다음 글에서부터는 메모리에 대한 공부로 넘어가보도록 하겠습니다. 읽어주셔서 감사합니다.
'전공공부 > 운영체제 (Operating System)' 카테고리의 다른 글
| [운영체제] Main Memory (2) - Paging (1) | 2021.01.04 |
|---|---|
| [운영체제] Main Memory (1) - Address Binding, Continuous Memory Allocation (0) | 2021.01.03 |
| [운영체제] Deadlock (2) - Deadlock Prevention (0) | 2021.01.01 |
| [운영체제] Deadlock (1) - Definition (2) | 2021.01.01 |
| [운영체제] Process Synchronization (3) - Mutex Lock, Semaphore (0) | 2020.12.29 |