운영체제 - 교착 상태(Deadlock)

교착상태(Deadlock)

---

둘 이상의 프로세스가 다른 프로세스가 점유하고 있는 자원을 서로 기다릴 때 무한 대기에 빠지는 상황이다.

간단하게 이해를 도울 수 있는 그림을 그려보았다.

치킨을 사먹기 위해 돈이 필요한데 서로 돈을 빌려달라고 요구하는 중이다.

결국에는 아무도 돈을 빌려주지 않고 상대방이 빌려줄 때까지 기다리는 상태로 남아있게 되고 최종적으로 영원히 치킨을 사 먹지 못하게 된다.

다시 설명을 해보자면 어떤 프로세스가 자원을 점유하고 있는 상태에서 다른 프로세스가 점유하고 있는 자원을 기다리게 되고(wait) 결국에는 작업을 끝마치지 못한 채 무한 대기에 빠져버리는 상황을 교착 상태라고 한다.

 

 

교착 상태 발생 조건

---

교착 상태가 발생하 조건은 크게 4가지로 분류된다. 

• 상호 배제(Mutual Exclusion)

상호 배제가 이루어 지면 임계 영역에 단 하나의 프로세스만 접근할 수 있기 때문에 다른 프로세스가 동시에 사용할 수 없으므로 이러한 자원을 사용하면 교착 상태가 발생한다.

• 점유 대기(Hold and Wait)

자원을 최소한 하나 보유하고, 다른 프로세스에 할당된 자원을 점유하기 위해 대기하는 프로세스가 존재하면 교착 상태가 발생할 수 있다.

• 비선점(No preemption)

이미 할당된 자원을 중간에 다른 프로세스가 강제로 빼앗을 수 없으므로 교착 상태가 발생한다.

• 순환 대기(Circular Wait)

대기 프로세스의 집합이 순환 형태로 자원을 대기하고 있는 경우이다. 즉, 프로세스가 특정 자원에 대해 점유와 대기를 하고 있는데 이러한 프로세스들이 원의 형태로 이루어져 있으면 교착 상태가 발생한다.

 

이러한 4가지 조건 중에서 단 하나의 조건이라도 충족하지 않으면 교착 상태는 발생하지 않는다.

 

교착 상태 처리 방법

---

교착 상태를 해결하는 방법은 크게 3가지로 분류할 수 있다.

• Prevention(예방)

먼저 Prevention(예방)은 교착 상태가 발생하는 4가지의 경우 중에서 하나라도 발생하지 않도록 예방하는 방법이다.

앞에서 살펴봤던 것처럼 교착 상태가 발생하는 4가지 조건 중 하나라도 발생하지 않는다면 교착 상태가 발생하지 않는다. 따라서 해당 조건 중에서 하나라도 예방하여 교착 상태가 발생하지 않도록 막는 방법이다.

• 상호 배제

한 번에 여러 프로세스가 공유 자원을 사용할 수 있게 한다. 

• 점유 대기

프로세스 실행에 필요한 모든 자원을 한꺼번에 요구하고 허용할 때까지 작업을 보류해서 나중에 또 다른 자원을 점유하기 위한 대기 조건을 성립하지 않도록 한다.

• 비선점

이미 다른 프로세스에게 할당된 자원이 선점권이 없다고 가정할 때 높은 우선순위의 프로세스가 해당 자원을 선점할 수 있도록 한다.

• 순환 대기

자원을 순환 형태로 대기하기 않도록 일정한 한 쪽 방향으로 자원을 요구할 수 있도록 한다.

위의 설명과 같이 예방하는 방법을 사용하면 교착 상태를 예방할 수 있지만 시스템의 처리량이나 효율성을 떨어트리는 단점이 발생할 수 있다.

 

• Avoidance(회피)

회피 알고리즘은 한정된 자원을 무분별하게 할당해서 교착 상태가 발생했다고 간주한다. 배분할 수 있는 자원의 양을 고려해서 교착 상태가 발생하지 않을 만큼만 자원을 배분하는 방식이다.

회피 방법에는 Safe sequence(안정 순서), Safe state(안정 상태) 라는 키워드가 있다.

프로세스들이 요청하는 모든 자원을 교착 상태가 발생하지 않으면서 차례로 모두에게 할당해줄 수 있다면 안정 상태에 있다고 한다.

특정한 순서로 프로세스들에게 자원을 할당, 실행 및 종료 등의 작업을 할 때 교착 상태가 발생하지 않는 순서를 찾을 수 있다면 안정 순서라고 부른다.

불안정 상태는 안정 상태가 아닌 상황을 말한다. 즉, 교착 상태가 발생할 가능성이 있는 상황이다.

회피 알고리즘은 자원을 할당한 후에도 시스템이 항상 안정 상태에 있을 수 있도록 할당을 허용하는 것이 특징이다.

교착 상태 회피를 구현하는 방법 중에서 대표적으로 은행원 알고리즘을 사용할 수 있다.

• 은행원 알고리즘(Banker Algorithm)

은행원 알고리즘은 대기 중인 다른 프로세스들의 활동에 대한 교착 상태 가능성을 미리 조사하는 것이다.

어떤 자원의 할당을 허용하는지에 관한 여부를 결정하기 전에 미리 결정된 모든 자원들의 최대 가능한 할당량을 가지고 시뮬레이션해서 안정 상태에 들 수 있는지 여부를 검사한다.

미리 최대 자원 요구량을 알아야 하고 할당할 수 있는 자원의 수가 일정해야 하는 등 사용하는데 있어 제약 조건이 많고 그에 따른 자원 이용도 하락하는 단점이 존재한다.

 

• Detection(탐지)

교착 상태 탐지는 현재 시스템에 교착 상태가 발생했는지 여부를 탐색하는 방법이다.

타임 아웃을 사용하거나 자원 할당 그래프를 사용하여 교착 상태 여부를 확인할 수 있다.

• 타임 아웃

타임 아웃을 사용하여 일정 시간 동안 작업이 진행되지 않는 프로세스를 교착 상태가 발생한 것으로 간주하여 처리하는 방법이다.

타임 아웃을 이용하는 방법을 가벼운 교착 상태 검출이라고도 하는데 유닉스나 윈도우와 같은 운영체제에서 사용하는 방법이다.

타임 아웃을 이용하면 교착 상태가 아닌 다른 이유로 인해 작업이 일정 시간 동안 진행되지 않을 수 있는데 이런 상황에서도 해당 프로세스를 강제 종료할 수 있는 단점이 있다.

• 자원 할당 그래프

자원 할당 그래프를 이용하면 시스템 내의 프로세스가 어떤 자원을 사용하거나 기다리고 있는지 알 수 있다.

이를 통해서 프로세스의 작업 방식을 제한하지 않으면서 교착 상태를 정확하게 파악할 수 있는 장점이 있지만 자원 할당 그래프를 유지하거나 갱신하는 추가 작업이 필요하므로 오버헤드가 발생하는 단점이 있다.

 

• Recovery(회복)

탐지 기법을 사용하여 교착 상태를 발견했다면 순환 대기에서 벗어나 교착 상태로부터 회복하기 위한 방법을 사용한다.

• 단순히 프로세스를 1개 이상 중단시키기

- 교착 상태에 빠진 모든 프로세스를 중단 시키는 방법

계속 연산 중이던 프로세스들도 모두 일시에 중단되어 부분 결과가 폐기될 수 있는 부작용이 발생한다.

- 프로세스를 하나씩 중단 시킬 때마다 탐지 알고리즘으로 교착 상태를 탐지하면서 회복시키는 방법

매번 탐지 알고리즘을 호출 및 수행해야 하므로 부담이 되는 작업일 수 있다.

• 자원 선점하기

프로세스에 할당된 자원을 선점해서 교착 상태를 해결할 때까지 그 자원을 다른 프로세스에 할당해 주는 방법