[OS] 프로세스 교착 상태에 대한 해결방안

프로세스 교착 상태에 대한 해결방안

교착 상태(Dead Lock)란?

 교착 상태란 두 개 이상의 작업이 대기 중일 때 아무런 작업도 실행하지 못하는 상태를 말한다. 예를 들어 문 앞에 닫으려는 자와 열려는 자가 동시에 있을 경우, 사다리에 내려오려는 자와 올라가려는 자가 동시에 있는 경우가 교착상태이다. 운영체제의 작업 처리 방식 중 다중 프로그래밍 환경에서 흔히 발생하는 문제이며, 이를 해결할 방법은 없으나 현재는 운영체제마다 각각의 방식대로 대응하고 있다.

교착 상태의 조건

 1971년에 E. G. 코프만 교수는 교착 상태 발생 조건을 네 가지로 정리했다.

1. 상호배제 : 한번에 하나의 프로세스가 하나의 자원을 점유할 수 있어야 한다.
2. 점유대기 : 프로세스가 자원을 점유한 상태에서 다른 프로세스에 할당되어 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 있어야 한다.
3. 비선점 : 다른 프로세스에 할당된 자원은 작업이 끝날 때까지 다른 프로세스가 강제로 점유할 수 없다.
4. 순환대기 : 각 프로세스는 연결고리처럼 순환적으로 다음 프로세스가 점유하고 있는 자원을 요구한다. 점유 대기 조건과 비선점 조건이 성립한 조건이다.

교착 상태는 위 네 가지의 조건이 동시에 성립할 때 발생한다. 만약 네 가지 조건 중 하나라도 성립하지 않도록 한다면 교착 상태가 발생하지 않는다.

교착 상태의 해결

 교착 상태를 대응하기 위한 방안은 예방, 회피, 복구, 무시, 탐지 등이 있다. 

교착 상태의 예방(Prevention), 제거

 교착 상태는 네 가지의 조건이 동시 성립할 때 발생한다. 교착 상태의 예방은 이 네 가지 조건 중 하나의 조건을 제거함으로 교착 상태를 대응한다.

1. 상호배제 조건의 제거
   상호배제란 두 개 이상의 프로세스가 공유 자원을 사용할 때 발생하는 것이므로 상호 배제 조건을 제거하면 교착 상태를 해결할 수 있다. 즉 여러 개의 프로세스가 공유 자원을 사용할 수 있도록 하는 것이다.
2. 점유대기 조건의 제거
   프로세스가 작업을 시작하기 전 모든 자원을 미리 할당 시켜 작업을 처리할 수 있도록 하는 방법이다. 일부 자원만 할당되면 실행할 수 있음에도 모든 자원을 할당 받을 때까지의 대기 시간이 존재.
   
3. 비선점 조건의 제거
   프로세스가 작업 중 현재 할당하지 않은 자원으로부터 요청이 있을 경우 작업 중인 자원을 내 놓고 요청된 자원을 점유한다. 프로세스의 비정상종료와 재시작 문제성, 최악의 경우 작업 했던 것들이 무효가 되어 낭비가 심하다.
   
4. 순환대기 조건의 제거
   순환이 한 방향으로만 존재하도록 하여 순환이 발생하지 않게끔 하는 방법이다. 

교착 상태의 예방은 자원 활용 효율성이 떨어지고 비용이 많다는 문제점이 있다.

교착 상태의 회피(Avoidance)

 교착 상태가 발생할 경우 알고리즘을 적용하여 교착 상태를 회피하는 방법이다. 교착 상태를 회피하는 대표적인 알고리즘은 은행가 알고리즘(Banker's Algorithm)이다. 은행가 알고리즘은 프로세스가 안전 상태를 유지하도록 제어하는 작업을 한다. 프로세스가 자원을 요청할 때 할당 했을 경우에 대한 안정성을 계산하여 안전 상태일 경우만 자원을 할당 시키는 것이다.

교착 상태의 복구(Recovery), 회복

 교착 상태가 발생하는 것을 방지하는 것이 아닌, 교착 상태 발생 이후에 대한 문제를 해결하는 방법이다. 교착 상태가 발생할 경우 문제를 일으킨 프로세스를 종료하거나, 할당된 자원을 해제함으로 유지 상태로 복구 시키는 것이다. 교착 상태의 복구는 두 가지의 방식이 있다..

-프로세스 종료 방식

1. 교착 상태의 프로세스를 모두 종료한다.
2. 안전 상태로 복구될 때까지 프로세스를 하나씩 종료한다.
   

 프로세스는 종료할 때 자원을 반납하는데, 이 때 해 왔던 작업이 무효화되는 단점이 있다. 이러한 손실을 최대한 줄이기 위해서는 종료 비용을 산정하여 종료 비용이 최소인 프로세스부터 종료한다.

-종료 비용 산정

 실행 시간이 짧은 것, 실행 완료 예정 시간이 많이 남은 것, 우선 순위가 낮은 것들은 종료 비용이 비교적 적다고 할 수 있다.

-자원 선점 방식

 교착 상태인 프로세스가 점유하고 있는 자원을 선점하여 다른 프로세스에게 할당하여 교착 상태를 해결하는 방법이다. 자원을 선점할 때 프로세스 종료 방식과 비슷하게 최소 비용을 산정하여 자원을 선점한다.

교착 상태의 탐지(Detection), 발견

 프로세스 동작 중 교착 상태가 발생했는지에 대한 여부를 감지해 발견하는 방법이다. 교착 상태 탐지 알고리즘이나 자원 할당 그래프를 통해 교착 상태를 확인한다. 

교착 상태의 무시(Ignore)

 교착 상태를 해결할 때 성능에 큰 영향을 미치게 되는데, 교착 상태 해결로 인한 성능 저하가 교착 상태 발생으로 인한 성능 저하보다 클 경우 교착 상태에 대한 처리를 무시한다.