교착 상태와 해결 방법에 대한 이론

🚀교착상태란?

식사하는 철학자 문제가 있다.

철학자들은 두 포크를 모두 들어야 식사를 할 수 있다. 식사를 할 수 있는 순서는 왼쪽 포크가 사용가능하면 왼쪽 포크를 들고, 오른쪽 포크가 사용가능하면 오른쪽 포크를 든다. 그리고 모두 포크를 들었다면 식사를 하고 식사를 마쳤다면 오른쪽 포크부터 내려놓는다. 이 과정을 계속 반복하면 된다.

 

결론부터 말하면 모든 철학자가 왼쪽 포크를 드는 순간, 모든 철학자는 오른쪽 포크를 들 수 없기 때문에 아무도 식사를 하지 못하는 상황이 발생한다. 이것이 교착상태이다.

식사하는 철학자

 

 

컴퓨터 공학에서 교착상태는 다음과 같이 설명할 수 있다.

프로세스 P1이 자원 R2를 할당받아 사용하고 있고, 프로세스 P2는 자원 R1을 할당받아 사용하고 있다.

그런데 P1은 자원 R1의 사용이 끝나기를 기다리고, P2는 자원 R2의 사용이 끝나기를 기다리고 있는 상황이다.

이 경우에는 각 프로세스들이 다른 프로세스가 점유한 자원이 끝나기를 기다리기만 하다가 결국 실행하지 못하게 된다.

Dead Lock

 

위의 그림과 같이 교착 상태는 자원 할당 그래프를 통해 표현할 수 있다.

그림처럼 순환 구조의 그래프는 교착 상태가 발생할 수 있음을 알 수 있다.

---

🤔교착 상태 발생 조건

교착 상태는 왜 발생하고 어떻게 해결해야하는지가 중요 포인트이다.

그렇다면 어떤 조건에서 교착상태가 발생하는 것일까?

바로 상호 배제, 점유와 대기, 비선점, 원형 대기이다. 이 조건 중 하나라도 만족하지 않으면 교착 상태는 발생하지 않지만, 모두 만족하면 교착 상태가 발생할 가능성이 생긴다.

상호 배제

교착 상태가 발생한 근본적인 원인은 해당 자원을 하나의 프로세스만 사용 가능했기 때문이다.

한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없을 때, 상호 배제의 상황에서 교착 상태가 발생할 수 있다.

점유와 대기

식사하는 철학자 문제에서 왼쪽 포크를 들고 다른 철학자의 포크를 기다렸다.

이처럼 어떤 자원을 할당받은 상태에서 다른 자원을 할당받기를 기다린다면 교착상태가 발생할 수 있다.

비선점

비선점 자원은 그 자원을 이용하는 프로세스의 작업이 끝나야만 비로소 이용할 수 있다.

즉, 어떤 프로세스도 다른 프로세스의 자원을 강제로 빼앗지 못했기 때문에 교착상태가 발생했다고 볼 수 있다.

원형 대기

자원 할당 그래프가 원의 형태로 순환적인 구조를 가지고 있다면 교착 상태가 발생할 수 있다.

주의할 점은 원의 형태를 띈다고 해서 반드시 교착 상태가 발생하는 것은 아니다.

---

🎯교착 상태 해결 방법

교착 상태를 해결하기 위해서는 교착 상태를 예방할 수 있고, 교착 상태를 회피할 수 있다. 아니면 교착 상태를 검출하고 회복하는 방법을 취할 수 있다.

교착 상태 예방

교착 상태를 예방하는 것은 위에서 언급한 교착 상태의 발생 조건 중, 어느 하나라도 만족시키지 않게 할당하는 것이다.

상호 배제를 부정하기 위해서 여러 개의 프로세스가 동시에 공유 자원을 사용할 수 있게끔 한다.

점유 대기를 부정하기 위해서 프로세스가 실행되기 전에 필요한 모든 자원을 할당하여 대기를 없애거나, 
자원이 점유되지 않은 상태에서만 자원 요청을 받도록 한다.

비선점 부정을 위해 모든 자원에 대한 선점을 허용한다.

순환 대기를 부정하기 위해 모든 자원에 번호를 붙이고, 오름차순으로 자원을 할당한다.

 

하지만 발생 조건을 방지해서 교착 상태를 해결하는 방법은 시스템 처리량이나 자원 사용의 효율성을 떨어뜨릴 수 있다.

교착 상태 회피

교착 상태가 발생할 가능성이 있는 자원 할당을 하지 않고 안전한 상태에서만 자원 요청을 허용하는 방법이다.

여기서 안전 상태(safe state)는 교착 상태가 발생하지 않고 모든 프로세스가 정상적으로 자원을 할당받고 종료될 수 있는 상태를 의미한다. 그와 반대로 교착 상태가 발생할 수도 있는 상황을 불안전 상태(unsafe state)라고 한다.

그리고 교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서를 안전 순서열(safe sequence)이라고 한다.

즉, 안전 순서열이 존재하는 상태는 안전 상태이고 그 반대는 불안전 상태이다.

교착 상태 검출 후 회복

검출 후 회복 방식에서는 프로세스들이 자원을 요청할 때마다 OS는 바로바로 할당을 한다. 그리고 교착 상태 여부를 주기적으로 검사하고 교착 상태가 검출되면 선점을 통해 회복하거나 프로세스를 강제 종료해서 회복한다. 아니면 아예 무시해버리는 방법도 있다.

 

선점을 통해 회복한다는 의미는 교착 상태가 해결될 때까지 다른 프로세스로부터 자원을 강제로 빼앗고 한 프로세스에 할당한다는 것이다.

 

프로세스를 강제 종료하는 방식에는 교착 상태에 빠진 모든 프로세스를 강제 종료할 수도 있고, 하나의 프로세스씩 종료하면서 교착 상태가 해결되는지 확인하는 방법이 있다.