교착상태란?

교착상태(Deadlock)란?

두 개 이상의 작업이 서로 다른 작업이 끝나기 만을 기다리고 있기 때문에 결과적으로 아무것도 완료되지 못하는 상태를 가리킨다. 하나의 CPU를 가지고 여러 작업을 한번에 가능하게 하는 멀티프로세싱과 멀티쓰레딩을 사용하는 과정에서 발생하게 된다. 이러한 교착상태는 흔히 발생할 수 있는데 현재의 대부분의 운영체제들은 이를 해결할 수 있는 일반적인 방법이 아직 없기 때문에 제각기 다른 비표준 방식들로 교착상태에 대응하고 있다고 한다.

교착 상태가 일어나는 이유는?

1. Mutual Exclusion(상호배제)

자원에 대한 동시접근을 불가하게 만드는 알고리즘이다. 네덜란드 수학자 ‘데커’가 동시 프로그래밍에서 공유 불가능한 자원의 동시 사용을 피하기 위해 만든 것으로, 프로세스들이 필요로 하는 자원에 대해 임계구역(Critical Section)을 통한 배타적인 통제권을 요구한다. 임계구역을 통해 한 번에 한 프로세스만 사용할 수 있게 된다.

2. Hold and wait(점유대기)

점유하고 기다리는 방식으로 자원을 가지고 있는 상태에서 다른 프로세스가 사용하고 있는 자원을 반납하길 기다리는 상태를 말한다.

3. No preemption(비선점)

자원을 뺏어오지 못함을 말하며, 프로세스가 어떤 자원을 할당 받았을 경우, 자원을 스스로 반납하기 전까지 해당 자원을 사용하도록 허용하는 정책이다. 여기서 ‘선점’은 시간상의 선점을 뜻하는 것이 아니라 우선권을 가진다는 우선의 ‘선점’이다.

4. Circular wait(순환대기)

각 프로세스는 순환적으로 다음 프로세스가 요구하는 자원을 가지고 있다. 즉, 마지막 프로세스는 첫 번째 프로세스가 점유한 자원을 요구하게 된다는 것이다. 위 조건을 모두 만족해야 교착상태가 발생한다. 의미가 비슷한 이유는 4가지 조건이 완전히 독립적인 것이 아니기 때문이라고 한다.

교착 상태를 해결하기 위한 방법은?

예방, 회피, 회복, 탐지, 무시 등의 방법이 있다. 하나씩 살펴보자

1. 교착 상태의 예방

가. 상호배제 조건의 부정

 교착 상태는 두 개 이상의 프로세스가 공유 가능한 자원을 사용할 때 발생하는 것이므로 상호배제의 조건을 제거하면 여러 개의 프로세스가 공유 자원을 사용할 수 있도록 함

나. 점유대기 조건의 부정

 한 프로세스에 수행되기 전에 모든 자원을 할당시키고 나서 점유하지 않을 때에는 다른 프로세스가 자원을 요구하도록 하는 방법이다. 이는 자원을 과다하게 사용하게 되어 효율성 및 비용 측면에서 문제가 발생할 수 있고, 이 외에도 기아 상태, 무한대기 등의 문제점이 있다.

다. 비선점 조건의 부정

 자원을 점유하고 있는 프로세스가 다른 자원을 요구할 때 자원을 반납하고 요구한 자원을 사용하기 위해 기다리게 한다.

라. 순환대기 조건의 부정

 자원에 고유한 번호를 할당하고, 번호 순서대로 자원을 요구하도록 한다.

2. 교착 상태의 회피

가. Resource Allocation Graph Algorithm(자원 할당 그래프 알고리즘)

 프로세스와 자원의 요청 및 할당 관계를 표시하여 순환 대기 조건을 발견하기 위한 목적으로 사용되며 교착 상태가 1개 발생한 경우에 주로 사용된다.

나. Banker’s algorithm(은행원 알고리즘)

 은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는 데서 유래한 기법으로, 프로세스의 자원 요구시 시스템이 자원을 할당한 후의 안정상태를 검사하여 회피하는 기법이다. 안정 상태로 남아있게 된다면 자원을 할당하고, 그렇지 않다면 할당을 거부하는 방식이다. 이는 2개 이상의 교착상태를 해결할 수 있다.

3. 교착 상태의 회복

 교착상태가 발생한 프로세스를 종료하거나, 할당된 자원을 선점함으로써 교착상태를

회복하는 방법이다. 교착상태가 발생하는 것을 막는 것이 아닌 교착상태 발생 이후

처리방식이다.

가. 프로세스를 종료하는 방법

- 교착상태의 프로세스를 모두 중지시켜 해결하는 방법

- 교착 상태가 제거될 때까지 한 개의 프로세스씩 중지시켜 해결하는 방법

나. 할당된 자원을 선점하는 방법

- 교착 상태의 프로세스가 점유하고 있는 자원을 선점하여 다른 프로세스에 할당한 후 해당 프로세스를 일시 정지 시키는 방법

- 우선순위가 낮거나 수행된 횟수가 적은 프로세스 등을 위주로 프로세스의 자원을 선점하는 방법이 있다.

4. 교착 상태의 탐지

 자원 할당 그래프를 통해 자원을 요청할 때 탐지 알고리즘을 실행하는 방법이다. 이 또한 교착상태를 막는 것이 아닌 발생 후 처리를 위한 탐지법이다. 오버헤드가 발생하게 되므로 교착상태가 얼마나 자주 일어나는지 인지하고 그에 따라 적절히 수행해야 한다. 교착상태가 일어나는 시점은 어떠한 프로세스가 자원 요청 시 그것이 즉시 만족되지 못하는 시점이므로 극단적으로 프로세스의 요청이 즉시 만족되지 않을 때마다 탐지 알고리즘을 실행시키는 방법이 있다. 이는 교착상태에 연루된 프로세스들뿐만 아니라 교착상태를 야기한 프로세스 또한 알아낼 수 있다. 그러나 매 요청 지연마다 탐지 알고리즘을 실행하게 되면 오버헤드가 발생해서 효율성이

떨어진다.

5. 교착 상태의 무시

 교착 상태에 대응하는 방법으로 예방이나 회피 기법을 사용할 경우 오버헤드가 발생해 성능 면에서 큰 영향을 미칠 수 있게 된다. 또한 교착 상태 발생 확률이 비교적 낮은 경우 별다른 조취를 취하지 않는다. 안정성과 성능을 고려해서 교착상태 무시 여부를 결정해야 한다.