Deadlock
2022.07.19 - 2022.07.20 공부 내용
Thanks to Leegon Kim
Deadlock
시스템은 유한한 수의 자원을 가짐. 각 프로세스는 이 자원을 사용하기 전에는 요청하고, 사용 후에는 해제해야 함. 자원이 사용 불가능하다면 프로세스는 대기 상태가 됨.
Deadlock은 대기 상태의 프로세스가 다른 프로세스에 의해 점유된 자원 때문에 영원히 기다리는 상황.
Necessary Conditions
다음 네 가지 조건이 동시에 일어나야만 deadlock이 발생될 수 있음.
Mutual Exclusion
한 번에 한 프로세스만 사용 가능한 자원이 하나 이상 존재. 이 자원을 사용하려는 다른 프로세스는 해제될 때 까지 기다려야 함.
Hold and Wait
프로세스는 한 개 이상의 자원을 점유한 상태에서 다른 프로세스에 할당된 자원을 기다릴 수 있어야 함.
No Preemption
자원은 선점될 수 없음. 오직 자원을 점유한 프로세스만 해제 가능.
Circular Wait
{P0, P1, ... Pn}과 같은 프로세스 집합이 존재함. Pi는 Pi+1가 점유하는 자원을 대기하고, Pn은 P0이 점유하는 자원을 대기함.
Handle Deadlock
Deadlock 문제를 다음과 같은 세 가지 방법으로 다룰 수 있음.
- Deadlock이 일어나지 않게 예방 (Prevention) 혹은 회피 (Avoidance)
- Deadlock이 일어날 수 있게 하고 탐지 (Detection) 및 회복 (Recovery)
- Deadlock이 생기지 않는다고 가정하고 무시
Deadlock Prevention
Deadlock이 발생하기 위한 충분조건이 성립하지 않는다면, deadlock이 발생하지 않음. 따라서 네 가지 충분조건 중 하나가 성립하지 않게 만들면 됨.
Deadlock은 절대 일어나지 않지만 device utilization과 throughput을 낮춘다.
Mutual Exclusion
이 조건은 무조건 성립함. 어떤 자원들은 본질적으로 공유가 불가능한 성격을 가지고 있기 때문.
Hold and Wait
이 조건이 성립하지 않게 만드려면, 프로세스를 실행할 때 모든 자원을 한번에 요구하거나, 프로세스가 자원을 하나도 가지고 있지 않을 때만 요구할 수 있게 만드는 방법이 있음.
이렇게 되면 자원의 활용도가 낮아지고, 기아 현상이 발생 가능.
No Preemption
이 조건이 성립하지 않게 만드려면, 지금 자원을 바로 할당받을 수 없는 프로세스가 점유하는 자원들을 다 선점 가능하게 만들면 됨. 자원들을 다 돌려받은 후에 프로세스 재시작 가능.
Circular Wait
이 조건이 성립하지 않게 만드려면, 자원에 번호를 부여해 현재 가진 자원보다 큰 번호의 자원만 요청이 가능하게 만들면 됨.
Deadlock Avoidance
알고리즘을 통해 circular wait 조건이 일어나지 않게 일어나지 않게 조절하는 방법.
Safe State
프로세스 수열 Pi가 존재해서 해당 순서대로 프로세스에 자원을 주고 실행하면 모든 Pi를 끝내는게 가능한 경우.
해당 수열이 없다면 unsafe하다고 함. Deadlock은 unsafe state에서 일어나지만, 역은 성립하지 않음.
프로세스가 자원을 요청할 때, safe state에 머물 수 있는 경우에만 허용함으로 인해 deadlock을 회피 가능.
Resource Allocation Graph Algorithm
프로세스와 자원을 이용해 그래프를 만듦. 이 때 사이클이 없는 경우 safe state임.
사이클이 생기는 요청의 경우 이를 거절함으로써 deadlock 회피.
Banker's Algorithm
Resource allocation graph는 각 리소스 타입이 여러 인스턴스를 가질 때 해결 불가. 이를 해결하는 방법.
남아있는 자원(Available), 최대 자원 요구량(Max), 현재 자원 할당량(Allocated), 자원 필요량(Need)를 이용해 시스템이 안전 상태인지 확인 가능.
이를 이용해 자원의 요청이 들어왔을 때, 자원 할당 후 안전 상태인지 확인하는 방법으로 deadlock 회피 가능
Deadlock Detection
Banker's algorithm을 응용해 deadlock이 발생한 경우 탐지 가능. 매 자원 요청 마다 알고리즘을 실행하는 것은 큰 오버헤드. 일정 시간 혹은 CPU 사용률이 떨어졌을 때만 발동함.
Deadlock Recovery
Deadlock이 발생한 경우 이를 회복하는 방법.
Process termination
Deadlock이 발생한 프로세스를 종료시키는 법. 다음과 같은 방법이 있다.
- Deadlock이 발생한 모든 프로세스 종료: 확실하지만 비쌈
- Deadlock cycle이 없어질 때 까지 프로세스를 하나씩 종료: 프로세스 선택 필요
Resource Preemption
Deadlock이 해결될 때 까지 특정 자원을 다른 프로세스가 선점할 수 있게 하는 방법.
요약
Deadlock은 자원 요구의 충돌로 인해 발생하고, 컴퓨터 사용률을 떨어트림. 그러나 이를 예방 혹은 회피하는 것은 오버헤드가 큼. 발생하게 두고 탐지 및 회복하는 방법도 존재.
그러나 실제 대부분의 OS에서는 비용이 아주 큰 문제고 deadlock은 거의 발생하지 않으므로 무시함.
참고자료
- Operating System Concepts 9th Edition, Silberschatz, Galvin and Gagne ©2013
