5. 교착상태(Deadlock)

 

교착 상태

 

일련의 프로세스들이 각자가 가진 자원은 점유하고 상대방의 자원을 기다리면서 각 프로세스가 아무 작업도 수행할 수 없는 상태를 말한다. 여기서의 자원은 하드웨어 및 소프트웨어를 포함하는데 가령, I/O 장치, CPU cycle, 메모리 공간과 같은 것이다. 

 

교착상태의 상황

교착상태 발생의 4가지 조건

 

- 상호 배제 : 매 순간 하나의 프로세스만이 자원을 사용할 수 있어야 한다.
- 비선점 : 프로세스는 자원을 스스로 내어놓지만 강제로 빼앗기지는 않아야 한다.
- 점유와 대기 : 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유하고 있는 자원은 놓지 않고 계속 갖고 있다.
- 원형 대기 : 자원을 기다리는 프로세스 간 사이클이 형성되어야 한다.

 

교착상태 처리 방법

- 교착상태 예방(Prevention)

 

자원할당 시 데드락의 4가지 필요 조건 중 하나가 만족되지 않도록 하는 것이다.

1. 상호 배제 예방 : 공유해서 안되는 자원의 경우에는 상호 배제가 반드시 성립해야 하는 문제가 있다.

2. 점유와 대기 예방 : 자원을 요청할 때 다른 어떤 자원도 갖고 있지 않아야 한다. 프로세스 시작 시 모든 필요한 자원을 할당받게 하거나 자원이 필요할 경우 점유 자원을 모두 놓고 다시 요청한다.

3. 비선점 예방 : 프로세스가 어떤 자원을 기다려야 하는 경우 이미 보유한 자원이 선점된다. 상태를 쉽게 저장하고 복원할 수 있는 자원에서 주로 사용된다.

4. 원형 예방 : 모든 자원 종류에 할당 순서를 정하여 정해진 순서대로만 자원을 할당한다.

교착상태를 예방하는 방법은 처리량을 감소시키지만 이용성이 저하되고 기아 현상 문제가 발생할 수도 있다.

 

- 교착상태 회피(Avoidance)

 

자원 요청에 대한 부가적인 정보를 이용해 데드락의 가능성이 없는 경우에만 자원을 할당한다. 프로세스들이 필요로 하는 각 자원별 최대 사용량을 미리 선언하도록 하는 방법이 있다. 이는 시스템이 불안정 상태에 들어가지 않는 것을 보장해준다.

 

자원 종류 당 인스턴스 하나인 경우, 자원할당 그래프를 통해 사이클이 발생하지 않을 때 자원을 할당해준다.

 

 

 

자원 종류 당 인스턴스가 여러 개인 경우, 자원 테이블을 통해 프로세스들이 자원 요청시 할당할 것인지 말 것인지 결정하는 뱅커스 알고리즘을 사용한다.

 

추가 자원 요청이 필요한 프로세스와 가용 자원을 비교하여 가용 자원으로 추가 요청의 자원을 받을 수 있을 때에만 할당해준다. 프로세스들이 최악의 경우로 자원 요청을 한다고 가정 하에 최대 사용량을 보고 할당을 해야한다.

 

- 교착상태 발견과 회복(Detection and Recovery)

 

데드락 발생은 허용하되 이에 대한 감지 루틴을 두어 데드락 발견시 회복하는 방법이다. 자원 종류별로 자원 인스턴스가 하나일 때와 여러 개일 때를 나눠 자원 할당 그래프 또는 뱅커스 알고리즘을 통해 데드락을 처리한다.

 

자원할당 그래프 사이클 발생

자원의 최대 사용량을 고려하는 게 아니므로 교착상태 회피와 달리 기존 자원이 할당된 프로세스가 실제로 추가 요청하는 자원이 없는 경우 자원을 내어놓는다고 가정하고 추가 요청을 하는 다른 프로세스들에게 가용 자원을 보고 자원을 할당받게 된다.

회복하는 방법으로는 데드락과 연관된 프로세스들을 모두 종료시키거나 데드락 사이클이 사라질 때까지 프로세스 하나씩 종료시키는 방법이있고, 데드락이 발생했을 때 연관 프로세스 중 하나를 골라 자원을 뺏어 데드락을 없애는 방법이 있다. 하지만 이 경우 어떤 프로세스의 자원을 뺏을지에 대한 비용과 rollback 횟수도 고려를 해야한다.

 

- 교착상태 무시(Ignorance)

 

대부분의 범용 운영체제(UNIX, Windows)에서 사용하는 방식으로 데드락을 시스템이 책임지지 않게한다. 교착상태가 발생하지 않는다고 가정하고 아무런 조치도 취하지 않는 것이다.

 

데드락 자체가 매우 드문 현상이므로 이에 대한 조치 자체가 비효율적일 수 있으며, 데드락이 발생했더라도 시스템이 비정상적으로 동작하는 걸 사용자가 인지 후 직접 프로세스를 강제 종료하는 등의 방법으로 해결한다.