[운영체제 #11] Deadlocks

Deadlock

Deadlock Concept

 

앞서 10장에서 봤던 "Dining-Philosophers Problem"을 해결하는 과정에서 Deadlock이 발생할 수 있다 했는데, 다시 말하자면 여러 프로세스가 리소스를 받을 수 없는 상태에서 동시에 리소스를 무한히 대기하는 상태로 이로 인해 시스템이 정상 작동될 수 없는 상황이다.

 

헷갈릴 수 있는 다른 용어들은 다음과 같다.

• Livelock : Deadlock과 반대로 한 프로세스가 무한히 running상태에 빠져 CPU를 점유하며  프로그램 진도를 못나가는 상태
• Starvation : Deadlock과 유사하지만, Starvation은 일어날 수 있는 일을 대기하는 상태이다. 그냥 우선순위가 낮아 필요한 리소스를 장시간 얻지 못하는 상태이다.

Deadlock이 발생할 수 있는 필요충분조건은 4가지이며, 아래 4가지 조건이 동시에 충족되야 Deadlock이 걸릴 수 있다.

• Mutual exclusion : 리소스는 한 번에 한 프로세스만 사용해야만 하는 상황
• Hold and wait : 프로세스가 리소스를 가진 상태에서 다른 리소스를 기다리는 상황
• No preemption : 프로세스가 리소스를 뺏을 수 없는 상황
• Circular wait : 프로세스가 순환 형태로 리소스를 기다리는 상황, 일자형이면 X

---

Resource-Allocation Graph

Deadlock Graph

 

Vertice V는 2가지 타입이 있다.

• P : 프로세스, 원으로 표시
• R : 리소스, 사각형으로 표시

Edge E도 2가지 타입이 있다.

• Request Edge : P→R 간선, 프로세스가 리소스를 요구하는 상태
• Assignment Edge : R→P 간선, 리소스가 프로세스로 할당된 상태

이 Resource-Allocation Graph형태를 보고 Deadlock인지 아닌지 판단할 수 있다.

• 사이클이 존재하지 않을 때 : No Deadlock
• 사이클이 존재하고, 리소스 타입에 인스턴스가 여러개 있을 때 : Deadlock 가능성 존재
• 사이클이 존재하고, 리소스 타입에 오직 한 인스턴스만 존재할 때 : Deadlock

---

Methods for Handling Deadlocks

1. Deadlock Prevention

Deadlock 필요충분조건 중 최소 한가지를 발생하지 않도록 막는 방법

• Mutual exclusion : 모든 리소스가 공유될 수 있도록 설정, 사실상 불가능한 방법
• Hold and wait : 점유한 리소스가 없는 상태에서만 리소스 요청하게끔 설정, 자원 효율성▼
• No preemption : 다른 프로세스가 리소스를 요청하면 강제로 반납, 리소스 일관성▼
• Circular wait : 리소스마다 번호를 부여해서 순서대로 요청하도록 설정, 가장 현실적이지만 복잡성▲

2. Deadlock Avoidance

알고리즘 등으로 시스템이 safe한 상태를 유지하도록 보장하여 Deadlock을 아예 회피하는 방법. 그래서 시스템은 리소스의 최대 요구량을 미리 선언하고, 리소스 할당 상태를 검사해서 safe 상태를 유지시킨다. 대표적인 방법으로 은행가 알고리즘이 존재한다.

Prevention은 구현이 단순하고 발생 조건은 원천적으로 차단한다는 장점이 있지만 자원을 비효율적으로 사용할 수 있고 이는 성능 저하로도 연결될 수 있다. 반대로 Avoidance는 필요할 때만 리소스를동적으로 할당하는 방식으로 보다 효율적이고 유연한 리소스 사용이 가능하지만 구현이 복잡하다.