교착 상태(Deadlock) - 예방과 회피

아래의 글에서 교착 상태에 대한 전반적인 설명을 다루고 있습니다.

https://create-new-worlds.tistory.com/113

교착 상태(Deadlock)

 

* 교착 상태 예방

 

교착 상태가 발생하기 위한 필요조건 4가지 중 하나가 성립하지 못하게 함으로써 교착 상태의 발생을 예방할 수 있다.

 

- 상호 배제를 방지한다.

 

공유 가능한 자원들은 배타적인 접근을 요구하지 않으며 교착 상태에 관련될 수 없다. 한 예로 읽기 전용 파일이 공유 가능한 자원이다. 읽기 전용 파일을 열면 파일에 대한 동시 접근을 허용한다. 하지만 일반적으로 자원들은 공유가 불가능하다.

 

 

- 점유하며 대기를 방지한다.

 

점유하며 대기 조건이 발생하지 않도록 하려면 스레드가 자원을 요청할 때마다 다른 자원을 보유하지 않도록 보장해야 한다. 여러 가지 방식이 존재한다.

• 각 스레드가 실행을 시작하기 전에 모든 자원을 요청하고 할당한다. 단점은 자원 요청의 동적 특성으로 인해 대부분의 응용 프로그램에는 실용적이지 않는 점이다.
• 스레드가 자원을 전혀 가지고 있지 않을 때만 자원을 요청할 수 있도록 허용한다. 단점은 자원이 할당되었지만 장기간 사용되지 않을 수 있기 때문에 자원 이용률이 낮을 수 있고, 여러 자원이 필요한 스레드는 필요한 자원 중 적어도 하나는 항상 다른 스레드에 할당될 수 있고 이는 기아 현상으로 이어진다.

 

 

- 비선점을 방지한다.

 

방법1

• 만일 어떤 자원을 점유하고 있는 스레드가 즉시 할당할 수 없는 다른 자원을 요청하면 현재 점유하고 있는 모든 자원이 선점되게 한다.
• 선점된 자원들은 그 스레드가 기다리고 있는 자원들의 리스트에 추가된다.
• 자신이 요청하고 있는 새로운 자원과 이미 점유하고 있었지만 반납된 옛날 자원을 다시 획득할 수 있을 때만 다시 시작될 것이다.

 

방법1의 변형

• 한 스레드가 자원A를 요청하면 사용 가능한지 검사하고 사용 가능하다면 할당한다.
• 만약 사용 불가하다면 자원A를 할당받고 있는 어떤 다른 스레드의 상태를 확인한다.
• 어떤 다른 스레드에서 추가의 자원을 위해 대기 중이라면 대기 중인 스레드로부터 원하는 자원을 선점해 이들을 요청하는 스레드에 할당한다.
• 만약 자원을 이용할 수 없거나 다른 대기 스레드에 의해 점유되어 있지 않다면 요청 스레드는 반드시 대기해야한다.
• 스레드가 요청 중인 새로운 자원을 할당받고 또한 대기 중에 선점되었던 모든 자원을 회복할 때만 다시 시작할 수 있다.
• CPU 레지스터나 데이터베이스 트랜잭션과 같이 상태가 쉽게 저장, 복원될 수 있는 환경에 적합하다.

 

 

- 순환 대기를 방지한다.

 

위의 세가지 경우는 대부분 상황에서 일반적이지 않다. 순환 대기를 방지하는 방법은 실용적으로 사용될 수 있다.

 

방법1 // 자원 R = {R1, R2, ..., Rm}

모든 자원 유형에 전체적인 순서를 부여하여 각 프로세스가 열거된 순서대로 오름차순으로 자원을 요청하도록 요구하는 방식이다.

• 각 자원에 순서를 결정하기 위해 고유의 정수 번호를 부여해야한다.
• Function(R) -> N 와 같은 1대 1 함수를 정의한다. N은 자연수이다.
• 각 스레드는 오름차순으로만 자원을 요청할 수 있다.
• Function(R1) = 1, Function(R2) = 5일때 R1을 먼저 요청하고 다음에 R2를 요청해야한다.
• Ri의 인스턴스를 요청할때마다 Function(Ri) >= Function(Rj)인 모든 Rj를 반납하는 방법도 있다.
• 동일한 유형의 자원이 여러 개 필요할 경우 단 한번의 요청으로 모든 자원을 할당받아야 한다.

 

귀류법을 통해 증명할 수 있다. 순환 대기 조건에 연관된 스레드들을 {T0, T1, ..., Tn}이라고 부르고 Ti는 Ri를 기다리고 있고 그것은 Ti+1이 점유하고 있다고 가정해본다.

 

Ti+1은 Ri를 점유하고 있지만 Ri+1을 요청하고 있기 때문에 Function(Ri) < Function(Ri+1)이다. 만약 사이클이 발생한다면 다음을 만족해야한다. Function(R0) < Function(R1) < ... < Function(Rn) < Function(R0)

여기서 Function(R0) < Function(R0)의 모순이 발생하게 된다. 즉 사이클이 발생하지 않는다.

 

락이 동적으로 획득될 수 있다면 락 순서를 부여한다고 해서 교착 상태 예방을 보장하지 않는다. 

void function(mutex1, mutex2)
{
    lock(&mutex1);
    lock(&mutex2);
    
    // do something
    
    unlock(&mutex2);
    unlock(&mutex1);
}

// 다음과 호출이 각 스레드에서 일어난다면 교착 상태가 발생할 수 있다.

// 스레드1에서 호출
function(A, B);

// 스레드2에서 호출
function(B, A);

 

 

* 교착 상태 회피

 

교착 상태를 예방하는 방식의 문제점은 장치의 이용률이 저하되고 시스템 총처리율(throughput)이 감소한다는 것이다.

 

자원이 어떻게 요청될지에 대한 추가 정보를 요구하는 방식으로 교착 상태를 회피하는 방법이 존재한다. 스레드의 자원 요청과 반납에 대한 완전한 순서를 파악하고 있다면 각 요청에 대해 가능한 미래의 교착 상태를 피하기 위해 요청한 스레드의 대기 여부를 결정할 수 있다. 이러한 대기 여부를 결정하기 위해 현재 가용 자원, 현재 각 스레드에 할당된 자원, 각 스레드가 앞으로 요청하거나 반납할 자원을 고려해야한다.

 

이러한 알고리즘은 정보에 따라서 다양하게 존재할 수 있다. 가장 단순하고 유용한 알고리즘은 스레드가 자신이 필요로 하는 각 유형의 자원마다 최대 수를 선언하도록 요구하는 것이다. 각 스레드가 요청할 각 유형 자원의 최대 수 정보를 미리 파악할 수 있다면 시스템이 교착 상태에 들어가지 않을 것을 보장할 수 있다.

 

 

- 안전 상태

 

안전 상태라는 말은 시스템이 어떤 순서로든 스레드들이 요청하는 모든 자원을 교착 상태를 발생시키지 않고 차례로 모두 할당해 줄 수 있다는 것을 뜻한다. 기본 원칙은 시스템의 상태가 항상 안전 상태를 떠나지 않도록 고수하며 요청된 자원에 대해서 허가를 내주는 것이다. 자원을 요청하면 즉시 할당할지 대기할지 안전 상태를 고려하여 결정하여야 한다.

다음 예시는 안전 상태를 고려하지 않았을 때 교착 상태가 나타나는 과정을 보여주고 있다.

		최대 소요량	현재 사용량
thread0		10			5
thread1		4			2
thread2		9			3

// 할당하면 안전 상태가 지켜지지 못하는 상황이다.
thread2에 자원을 1개 할당한다. // 남은 자원 3개중 1개 사용

thread1에 자원을 2개를 할당하여 thread1을 끝낸다. // 남은 자원 2개중 2개 사용
thread1은 자원을 4개를 반납한다. // 남은 자원 4개
thread0와 thread2는 둘 다 5개의 자원을 필요로 하기 때문에 교착 상태에 빠진다. // 남은 자원 4개

 

 

- 자원 할당 그래프 알고리즘

 

동작 방식은 다음과 같다.

• 미래 자원을 예약 : P  --> R
• 자원을 요청 : P -> R
• 자원이 할당 : R -> P // 반납 시 P --> R로 변환
• P와 관련된 모든 간선들이 예약 간선일 때만 P --> R을 추가
• 모든 예약 간선을 표시 후 사이클이 존재하는 지 확인한다.

R2를 P2에게 할당하면 사이클이 생기기 때문에 P2에 할당할 수 없다.

 

 

- 은행원 알고리즘

 

은행원(banker's) 알고리즘이라고 불리는 이유는 은행에 고객들이 현금을 찾으러 와도 일정한 순서에 의해 모든 고객의 요청을 다 들어줄 수 있기 때문이다.

• 스레드가 시작할 때 스레드가 가지고 있어야 할 자원의 최대 개수를 자원 종류마다 미리 신고해야한다. 단 자원의 총 보유 수를 넘어가면 안된다.
• 스레드가 자원들을 요청하면 시스템은 이를 수락했을 때 안전 상태에 머무르게 되는 지 판단해야 한다. 안전 상태에 머르게 된다면 요청을 들어주고 그렇지 않다면 다른 스레드가 끝날 떄까지 기다리게 된다.
• 구현하기 위한 시스템이 자원을 할당하고 있는 상태를 나타내는 자료구조가 필요하다. 

 

자료구조는 다음과 같다. n은 스레드의 수, m은 자원의 종류의 수이다.

• Available : 각 종류별로 가용한 자원의 개수를 나타내는 벡터로 크기가 m이다. 만약 Available[j] = k라면 스레드 Rj를 k개 사용할 수 있다는 뜻이다.
• Max : 각 스레드가 최대로 필요로 하는 자원의 개수를 나타내는 행렬로 크기가 n * m 이다. Max[i][j] = k라면 Ti가 Rj를 최대 k개까지 요청할 수 있음을 뜻한다.
• Allocation : 각 스레드에 현재 할당된 자원의 개수를 나타내는 행렬로 크기가 n * m 이다. Allocation[i][j] = k라면 현재 스레드 Ti가 Rj를 k개 사용 중임을 뜻한다.
• Need : 각 스레드가 향후 요청할 수 있는 지원의 개수를 나타내는 행렬로 크기가 n * m이다. Need[i][j] = k라면 스레드 Ti가 향후 스레드 Ti가 Rj를 k개까지 더 요청할 수 있음을 뜻한다. Need[i][j] = Max[i][j] - Allocation[i][j] 관계가 있다.

 

@ 안전성 알고리즘

시스템이 안전한지 알아낼 수 있는 알고리즘은 다음과 같다.

 

1. Work와 Finish를 각각 길이가 m과 n인 벡터이고 Work = Available, i = [0, n - 1]에 대하여 Finish[i] = false로 초기화 한다.

 

2. 다음 조건을 만족하는 i 값을 찾는다. i 값이 없으면 4번으로 이동한다.

• Finish[i] == false
• Need[i] <= Work

3. 다음을 연산을 수행하고 2번으로 이동한다.

• Work = Work + Allocation[i];
• Finish[i] = true;

4. 모든 i 값에 대하여 Finish[i]가 true이면 시스템은 안전 상태에 있다.

 

간단한 원리는 확인하지 않는 스레드에 대해여 요청할 수 있는 최대의 자원의 수가 가용 자원보다 적다면 해당 스레드는 끝낼 수 있는 것이다. 끝냈다고 처리하여 현재 할당된 Allocation을 다시 가용 자원에 넣어주고 알고리즘을 다시 수행한다. 이 방식대로 진행하다보면 모든 스레드가 순차적으로 처리되는 것은 아니다.

 

 

@ 자원 요청 알고리즘

자원 요청을 안전하게 수행할 수 있는지 검사하는 알고리즘이다.

1. Request[i] <= Need[i]이면 2번으로 이동하고 만족하지 않으면 시스템에 있는 개수보다 더 많이 요청했기 때문에 오류로 처리한다.

 

2. Request[i] <= Available 이면 3번으로 이동하고 만족하지 않으면 요청한 자원이 당장 없기 때문에 Ti는 대기한다.

 

3. Ti에 자원을 할당해준 것처럼 시스템 상태를 바꿔보고 안전성을 검증해본다. 불안전하다면 롤백하고 Ti는 Request[i]가 만족하기까지 기다려야 한다.

• Available = Available - Request[i];
• Allocation[i] = Allocation[i] + Request[i];
• Need[i] = Need[i] - Request[i];