[OS] 교착 상태(Deadlock)

 

#1. 교착 상태(Deadlock)에 대해서

 

교착 상태(Deadlock)란 둘 이상의 프로세스가 각자가 가지고 있던 자원을 보유한 채로 외부적 조치가 없는 한 영원히 그 상태에서 기다리고 있는 상황을 말한다.

• 해당 프로세스들이 더 이상 실행되지 못하여 사용자들에게 응답해 주지 못함
• 보유된 자원들이 교착 상태에서 벗어나기 전까지는 전환 활용되지 못함

이것은 결과 시스템의 성능 저하로 나타난다.

---

자원이란?

선점 가능성에 따른 분류

• 선점 가능 자원(Preemptible) : 운영체제에 의해 사용 도중 뺏길 수 있음
• 선점 불가능 자원(Nonpreemptible) : 사용 도중 뺏을 수 없음

자원이 사용되는 방식에 따른 분류

• 공유 자원(Shareable) : 공유 가능한 자원, 시스템 프로그램, 유틸리티 프로그램
• 배타적 사용 자원(Exclusive Use) : CPU, 메모리, 테이프 , 버퍼, 키보드와 모니터...

자원의 속성에 따른 분류

• 순차적 재사용 가능(Serially Reusable) : 아무리 사용해도 없어지지 않고 영구히 존재(CPU, 메모리...)
• 소모성 자원(Consumable) : 일시적으로 생성되었다가 사용된 후 없어짐 (시그널, 메시지..)

---

프로세스는?

• 프로세스는 필요한 자원에 대한 요청(Request)과 사용이 끝난 자원의 반납을 할 수 있다.
• 요청된 자원이 사용 중이라면 반납될 때까지 대기 상태로 기다려야 한다.
• 대기 상태의 프로세스는 자력으로 그 상태를 벗어날 수 없다.
• 요청과 반납은 실행 중인 프로세스가 System call 함으로써 이루어진다.
• 반납된 자원으로 그 자원 때문에 대기 중인 프로세스를 깨우는 것도 운영체제이다.

---

교착 상태의 원인은?

교착 상태의 원인은 4가지가 있으며 만약 이 중 하나라도 부정할 수 있다면 교착 상태는 일어나지 않는다.

• 상호 배제 : 최소한 하나는 비공유 방식으로 점유되어야 한다. (한 번에 하나의 프로세스만 자원 사용)
• 점유와 대기 : 프로세스는 최소한 하나의 자원을 점유하고 있고, 다른 프로세스는 그것을 기다린다.
• 비선점 : 프로세스가 자원의 사용을 끝마치고 자발적으로 해제할 때까지는 그 자원을 얻을 수 없다.
• 순환 대기 : 프로세스들이 자원을 보유한 채로 서로 상대방의 자원을 요청

---

#2. 교착 상태의 해결

 

• 예방 기법 : 아예 발생하지 않도록 하는 방법
• 회피 기법 : 프로세스들이 교착상태를 피해가도록 하는 방법
• 탐지 기법 : 교착 상태가 발생되도록 놓아두었다가 조치하는 방법
• 복구 기법 : 탐지 기법으로 인해 교착 상태 발생 시 복구

---

예방 기법

교착 상태의 원인 중 하나를 제거하면서 해결

---

상호 배제	어떤 자원은 근본적으로 공유할 수 없기 때문에 상호배제 조건을 통해 예방하기는 어렵다.
점유와 대기	프로세스가 실행되기 전 필요한 모든 자원을 점유하도록 한다. 자원의 낭비가 심함
비선점	일부 자원을 가지고 실행했던 프로세스가 현재 할당이 불가능한 자원을 요청할 경우 자신이 보유하고 있던 자원을 반납하고 요구한 자원을 사용하기 위해 기다린다. 자원의 낭비가 심하고 무한 대기 가능성
순환 대기	자원의 번호를 부여하고 낮은 번호의 자원부터 할당을 받도록 한다.  자원의 낭비가 심하고 무한 대기 가능성

---

회피 기법

사전에 프로세스가 필요한 자원의 정보를 이용하여 교착상태가 발생하지 않도록 지연하거나 할당해주는 방법

---

안전 상태(Safe State)

안전 상태란 교착 상태가 발생할 수 없는 상태를 말하며, 불안전 상태라고 해서 그것이 곧 교착 상태임을 의미하는 것은 아니지만 불안전 상태는 교착 상태로 갈 가능성이 있으며 그럴 경우의 방지책이 없음을 뜻한다.

결국 회피 기법은 시스템의 상태가 안전 상태로만 가도록 지속적으로 제어해 나가는 것이다.

---

Dijkstra의 은행가 알고리즘

은행가 알고리즘이 제대로 작동하기 위한 가정 (현실적으로 지켜지기 힘듦, 이론적 접근의 방편)

1. 시스템 내의 프로세스 수가 고정되어 있어야 한다.
2. 자원의 수 역시 고정되어 있어야 한다.
3. 각 프로세스가 요구할 자원의 최대 개수가 알려져야 한다.
4. 각 프로세스는 할당받은 자원을 사용 후 반드시 반납하여야 한다.

프로세스	현재 보유량(Current Loan)	최대 요구량(Maximum need)
P1	1	4
P2	4	6
P3	5	8
여유량(Available)	2

• 이 상태는 안전하다.
• P2가 더 요구할 최대량이 2개이며 이것은 시스템이 현재 가지는 여유량을 넘지 않는다.
• P2가 성공적으로 종료가 되면 반납되는 자원은 6개이고 P1, P3 모두 할당 가능하다.

 

프로세스	현재 보유량(Current Loan)	최대 요구량(Maximum need)
P1	1	4
P2	4	6
P3	6	8
여유량(Available)	1

• 이 상태는 불안전하다.
• 현재 여유량인 1개의 자원으로는 어떤 프로세스도 향후 자신의 최대 요구량에 이르지 못하는 상태

---

탐지 기법

교착 상태의 발생을 막기 위한 사전 조치를 취하지 않는 경우 언젠가는 발생할 터이고 이것을 어떤 방법으로든 찾아내어 적절한 대응을 하겠다는 것이 탐지 기법이다.

• 어떤 프로세스가 어떤 자원을 가지고 있는가?
• 어떤 프로세스가 어떤 자원에 의해 대기 상태가 되어 있는가?

자원 할당 그래프(RAG)

 

• 노드들은 프로세스와 자원들을 표현, 에지(화살표)들은 프로세스와 자원들 간에 할당과 대기 상황
• 자원에 대한 할당과 반납, 대기는 해당 에지의 추가와 삭제로 RAG를 수정
• 이렇게 관리되어 온 RAG에 대한 그래프 제거법으로 교착 상태를 탐지
• 탐색 도중 싱크가 발견되면 교착 상태는 없다고 판단
• 모든 가능 경로를 탐색해도 싱크가 발견되지 않는다면 교착 상태

---

복구 기법

교착 상태로부터 벗어나기 위한 방법

---

프로세스의 종료

• 교착 상태에 포함된 모든 프로세스를 종료한다. 교착 상태는 바로 해결되지만 종료, 비용이 많이 소요된다.
• 순환 대기하는 프로세스 중 하나를 종료한다. 교착 상태가 제거될 때까지 하나 씩 종료

종료 비용의 최소화는 중요하다. 종료 비용은 여러 가지 잣대들로 산정되는데 프로세스의 우선순위나 종류, 실행된 시간의 크기, 남은 시간 등이 있다. 

---

자원의 선점에 의한 방식

필요한 자원을 가지고 있는 프로세스로부터 강제로 뺏어 교착 상태에 있는 프로세스들에게 줌으로써 해결. 이 방식 역시 선점 시의 최소 비용을 따져야 한다.

---

검사점 지정(Checkpointing) 과 재시작(Restart)

강제 종료 시의 낭비를 줄이기 위한 방법으로 프로세스들은 실행의 중간중간에 그 시점까지의 실행 결과를 보존하고 표시를 해 두는데 이를 검사점이라 한다. 강제로 종료될 때는 아예 처음으로 돌아가는 것이 아니라 가장 최근의 검사점부터 차례로 하나씩 되돌리는 것이다.

---

 

참고 자료

• OS? Oh Yes! , 김주균 지음