[운영체제] 교착 상태(DeadLock)

프로세스 집합의 각 프로세스가 다른 프로세스에 의해 발생될 자원의 해제와 같은 이벤트를 무한히 기다리는 상황을 말한다.

이 상황에서는 모든 프로세스가 멈춰 서 있어 시스템의 개입 없이는 이 상태에서 벗어날 수 없다.

 

프로세스가 os 혹은 block에서 승인이 되면 use로 이동하고 use에서는 release로 이동한다.

이때 os에서 응답이 지연될 경우 block으로 이동한다.

여기서 특정 조건이 만족되어 무한히 프로세스가 block에 갇히게 되면 deadlock이 발생하게 된다.

교착 상태의 조건

1. 상호 배제(Mutual Exclusion)
   하나의 프로세스가 cs에 들어가 있으면 다른 프로세스가 cs가 비어있을 때 까지 계속 기다리고 있어야 함으로 만약 비워주지 않는다면 deadlock이 발생한다.
   
2. 점유와 대기(Hold and Wait)
   프로세스가 자원을 점유한 상태에서 추가 자원을 대기하는 경우이다.
   예를들어 만약 P1에서 a를 잡고 있고 P2에서 b를 잡고 있는 상황을 가정해볼 때 만약 P1에서 b가 필요할 경우 이미 P2에서 잡고 있으므로 접근할 수 없다.
   그리고 P2에서 a가 필요하다면 똑같이 P1에서 잡고 있으므로 P2에서도 접근할 수 없다.
   따라서 P1과 P2모두 작업을 끝내지 못하고 무한히 wait하게 된다.
   
   
3. 비선점(No Preemption)
   만약 프로세스P에서 자원 a를 계속 잡고 있는다면 다른 프로세스에서 a를 사용할 수 없고 해제될 때까지 계속 기다려야해서 deadlock을 발생시킨다.
   
4. 순환 대기(Circular Wait)
   프로세스P1이 프로세스P2를 필요로하고, 프로세스P2가 프로세스P1을 필요로 하면 프로세스 집합 각각이 순환적으로 다음 프로세스가 요구하는 자원을 보유하고 있어 무한히 순환하기 때문에 deadlock이 발생한다.

리소스(Resource)

Deadlock은 시스템 내에서 자원을 다루는 방식에 따라 발생할 수 있으며 자원이 Single Instance인지 Multi-instance인지에 따라 다르다.

 

 - Single instance

하나의 프로세스만 리소스에서 사용될 수 있다.

 

 - Multi-instance

많은 프로세스가 리소스를 동시에 사용할 수 있다.       

교착 상태 처리 방법

1. Deadlock Ignorance(Ostrich Algorithm)

운영 체제나 시스템이 교착 상태를 무시하고, 교착 상태가 발생할 경우에도 적극적으로 대응하지 않는다.

이 전략은 deadlock 발생의 비용 대비 deadlock을 처리하는 비용이 더 크거나, deadlock이 매우 드물게 발생하는 시스템에서 사용된다.

 

이 접근 방식은 deadlock 문제를 해결하지 않으며, deadlock이 발생하면 시스템의 안정성이나 성능에 심각한 영향을 미칠 수 있다.

또한, 사용자 불만이나 데이터 손실과 같은 문제를 야기할 수 있다.

 

이러한 방법은 개인용 컴퓨터에서 문제가 발생했을 때 사용할 수 있다.

일부 개인용 컴퓨터 운영 체제에서는 deadlock을 무시하고 문제가 발생하면 사용자가 시스템을 재시작하도록 한다.

deadlock이 드물게 발생하고, 대부분의 사용자가 재시작으로 문제를 해결할 수 있기 때문에 복잡한 deadlock 탐지 및 복구 메커니즘을 구현하는 것보다 경제적이다.

 

2. Deadlock Prevention

데드락이 발생하는 네 가지 필수 조건 중 최소 하나를 비활성화함으로써 데드락 발생 가능성을 차단하는 방법이다.

 

 - 상호 배제 비활성화

• Spooling
  자원을 spooling을 통해서 출력 장치나 다른 고속성을 요구하는 장치들에 대한 요청을 중앙화된 버퍼에 임시 저장한 뒤 순차적으로 처리하는 방식을 사용할 수 있다.
  예를 들어, 프린터와 같은 장치는 동시에 여러 요청을 받을 수 있도록 중앙화된 스풀링 시스템을 통해 관리될 수 있다.
• Daemon Process
  여러 프로세스가 동시에 요청할 수 있는 자원을 관리하는 Daemon Process를 사용하여 동시에 여러 요청을 받아들이고, 순차적으로 자원을 할당한다.

 - 점유와 대기 비활성화

모든 필요한 자원을 프로세스가 시작될 때 한꺼번에 할당받도록 일괄 할당을 사용하면 된다.

다만 이 방법은 프로세스가 실행되기 전에 모든 자원이 사용 가능해야 한다는 단점이 있다.

 

 - 비선점 비활성화

이미 할당된 자원을 다른 프로세스가 요청할 경우 해당 자원을 강제로 회수하여 다른 프로세스에 할당한다.

이는 자원을 선점하고 반환하는 메커니즘이 별도로 필요하다.

 

 - 순환 대기 비활성화

모든 자원에 고유한 숫자를 할당하고, 프로세스가 이 숫자의 순서대로 자원을 요청하도록 하여 순환 대기의 가능성을 없앨 수 있다.

 

Deadlock Prevention 기법은 deadlock 발생을 효과적으로 차단할 수 있지만, 자원 활용도와 시스템 처리량이 감소할 수 있는 단점이 있다.

 

3. Deadlock Avoidance

시스템이 데드락 가능성을 고려하여 자원 할당 결정을 내리는 방법으로 데드락 발생을 피하면서 자원을 할당하는 데 사용한다.

 

안전 상태(Safe State)

Deadlock Avoidance에서 안전 상태는 시스템이 데드락 없이 모든 프로세스가 요구한 자원을 얻고 실행을 완료할 수 있는 상태를 의미한다.

따라서 시스템이 데드락을 피하기 위해 항상 안전 상태를 유지해야 한다.

 

불안전 상태(Unsafe State)

불안전 상태는 데드락이 발생하지 않았지만 데드락으로 진입할 가능성이 있는 상태를 말한다.

불안전 상태에 있는 시스템은 데드락을 발생시키지 않을 수도 있지만 데드락 발생 위험이 있기 때문에 피해야 한다.

 

- 은행원 알고리즘(Banker's Algorithm)

Banker's Algorithm은 다중 인스턴스 자원을 다루는 시스템에서 데드락 회피를 위해 사용된다.

Banker's Algorithm에서 현재 사용 가능한 자원, 각 프로세스에 할당된 자원, 각 프로세스의 최대 요구 자원을 추적하여 각 프로세스의 최대 자원 요구량을 미리 알고 있다.

그렇기 때문에 프로세스가 자원을 요청할 때마다 요청을 수락하는 것이 안전 상태를 유지하는지를 판단할 수 있고, 요청이 안전 상태를 유지한다면 요청을 수락하고, 그렇지 않다면 프로세스를 대기 상태로 만든다.

 

4. Deadlock Detection and Recovery

데드락 탐지 및 복구는 데드락을 탐지하고 이미 발생한 데드락을 처리하는 방법이다.

데드락 탐지 (Deadlock Detection)

 

단일 인스턴스 리소스에서는 자원 할당 그래프를 이용해서 탐지가 가능하다

 - 리소스 할당 그래프(Resource Allocation Graph, RAG)

시스템의 프로세스와 리소스 간의 관계를 시각적으로 나타내는 도구로, 데드락 탐지에 널리 사용된다.

이 그래프는 프로세스, 리소스, 그리고 이들 간의 관계를 표현하는 꼭짓점과 간선으로 구성된다.

 

프로세스 꼭짓점 (Process Vertex)

꼭짓점의 한 종류로 원으로 표현되고, 내부에 프로세스 번호가 표시된다.

 

리소스 꼭짓점 (Resource Vertex)

리소스 꼭짓점은 사각형으로 표현된다.

CPU와 같은 싱글 인스턴스 리소스는 내부에 단일 점으로 표시되고, 레지스터와 같은 멀티 인스턴스 리소스는 리소스의 인스턴스 수만큼 점으로 표시된다.

 

요청 간선 (Request Edge)

프로세스에서 리소스로 향하는 간선으로 프로세스가 리소스를 요청할 때 표시된다.

 

할당 간선 (Assign Edge)

리소스에서 프로세스로 향하는 간선으로 리소스가 프로세스에게 할당될 때 표시된다.

 

단일 인스턴스 리소스에서 순환은 프로세스 집합 각각이 서로 다른 프로세스가 요구하는 리소스를 보유하고 있음을 나타내기 때문에 순환(Cycle)이 있으면 데드락이 발생했다고 판단할 수 있다.

 

다중 인스턴스 리소스에서는 순환을 이용해서 데드락을 판단할 수 없기 때문에 은행원 알고리즘을 이용해서 현재 할당 상태에서 안전 순서가 존재하는지를 검사한다.

여기서 안전 순서는 프로세스들이 자원을 요청하고 사용한 후에 해제하는 순서로 이 순서에 따르면 모든 프로세스는 데드락 없이 실행을 완료할 수 있다.

만약 안전 순서가 없다면 데드락이 발생했다고 판단할 수 있다.

 

데드락 복구 (Deadlock Recovery)

 

 - 리소스에서 복구 방법

Preemption

하나 이상의 프로세스로부터 자원을 강제로 회수합니다.

 

Rollback

데드락에 관련된 프로세스를 이전 안전 상태로 되돌립니다.

 

 - 프로세스에서 복구 방법

한 프로세스 종료

데드락을 해결할 수 있는 최소한의 프로세스를 종료한다.

 

모든 프로세스 종료(Kill All Processes)

만약 한 프로세스를 종료했음에도 데드락이 지속되면 관련된 모든 프로세스를 종료하고 시스템을 재시작한다.