CS/운영체제
#9 교착 상태(Deadlock)
Scala0114
2022. 1. 3. 11:36
1. 교착 상태(Deadlock)란?
- Blocked/Asleep 상태
- 특정 이벤트나 자원의 사용을 위한 대기상태
- 특정 이벤트나 자원의 사용을 위한 대기상태
- Deadlock 상태
- 멀티프로세스 시스템에서 프로세스들이 서로 다른 프로세스의 작업이 끝나고 이벤트가
발생하거나 공유 자원에 대한 lock이 풀리는 것을 대기하느라 아무도 작업을 시작하지 못하고
대기상태만을 유지하는 상태 - 즉, Blocked/Asleep 상태에 들어간 프로세스가 기다리는 것이 발생할 가능성이 없는
이벤트거나 절대 얻을 수 없는 자원일 경우 Deadlock 상태에 빠진다.
- 멀티프로세스 시스템에서 프로세스들이 서로 다른 프로세스의 작업이 끝나고 이벤트가
- 절대 발생할 수 없는 이벤트나 절대 얻을 수 없는 자원을 기다리는 상태라는 점에서
단순히 우선순위에서 밀려나서 자원(CPU)의 할당이 미뤄지고있을 뿐인 기아(starvation)
현상과는 구분된다.
2. 자원의 분류
- 선점 가능여부에 따른 분류
- 선점 가능한 자원(Preemptive Resources)
- 선점당한 뒤 돌아와도 문제가 발생하지 않는 자원
- 프로세서(CPU), 메모리 등
- 선점 불가능한 자원(Non-Preemptive Resources)
- 선점당할 경우 이후 진행에 문제가 발생하는 자원
- 디스크 드라이브 등
- 선점 가능한 자원(Preemptive Resources)
- 할당 단위
- 전체 할당 자원(Total Allocation Resources)
- 할당될 때 자원 전체가 통채로 할당되어야하는 자원
- 프로세서, 디스크 드라이브 등
- 부분 할당 자원(Paritioned Allocation Resources)
- 할당될 때 여러 조각으로 나누어 할당될 수 있는 자원
- 메모리 등
- 전체 할당 자원(Total Allocation Resources)
- 동시 사용 가능 여부
- 배타적 할당 자원(Exclusive Allocation Resources)
- 한번에 하나의 프로세스만 사용 가능한 자원
- 프로세서, 디스크 드라이브, 메모리
- 여기서 말하는 메모리는 메모리의 동일 영역을 의미한다.
- 공유 할당 자원(Shared Allocation Resources)
- 여러 프로세스가 동시에 사용할 수 있는 자원
- 공유데이터 등
- 배타적 할당 자원(Exclusive Allocation Resources)
- 재사용 가능 여부
- SR(Serially-Reusable Resources)
- 시스템 내에 항상 존재하는 자원
- 사용이 끝나면 반환되어 다른 프로세스에게 할당될 수 있음
- 프로세서, 메모리, 디스크 드라이브 등
- CR(Consumable Resources)
- 하나의 프로세스에 의해 사용되면 사라지는 자원
- 시그널, 메세지 등
- SR(Serially-Reusable Resources)
- Deadlock을 발생시킬 수 있는 자원의 종류
- Non-preemptive Resources
- 선점이 불가능한 자원은 사용중인 프로세스가 반환하기 전까지
다른 프로세스가 사용할 수 없기에 교착 상태를 발생시킬 수 있다.
- 선점이 불가능한 자원은 사용중인 프로세스가 반환하기 전까지
- Exclusive Allocation Resources
- 배타적 할당 자원은 동시에 하나의 프로세스만 사용 가능하기에
교착상태를 발생시킬 수 있다.
- 배타적 할당 자원은 동시에 하나의 프로세스만 사용 가능하기에
- Non-preemptive Resources
3. Deadlock 발생의 예시

- 예를들어 프로세스 A와 B가 모두 실행을 위해 자원 R1과 R2를 필요로 할 때, A와 B가 각각 R1, R2를
나누어가지 가진 상태라면 서로 상대가 나머지 한쪽 자원을 release 하기만 기다리고 실행되지 않아
Deadlock 상태에 빠지게된다. 프로세스가 n개일 때도 마찬가지의 상황이 발생할 수 있다.
4. Deadlock 발생의 조건
- Exclusive use of Resources & Non-Preemptive Resources
=> 프로세스가 요구하는 자원이 배타적 할당 자원 / 선점 불가능한 자원일 경우 - Hold & Wait
=> 프로세스들이 하나의 자원을 hold 한 채로 다른 자원을 요청하는 상태 - Circular Wait
=> Hold & Wait 상태에 있는 프로세스들의 관계가 순환을 이루는 경우 - 위 네 가지 조건을 모두 만족할 경우 Deadlock이 발생한다.
5. Deadlock 의 방지(Prevention)
- 애초에 데드락이 발생할 수 없도록 하는 방법
- Deadlock 발생의 조건 네가지중 하나를 제거
- Exclusive use of Resources 조건 제거
- 모든 자원을 동시에 사용할 수 있도록 공유
- 현실적으로 불가능
- Non-Preemptive Resources 조건 제거
- 모든 자원을 선점 가능하도록 함
- 현실적으로 불가능
- Hold & Wait 조건 제거
- 필요한 자원을 한번에 할당받도록 함(Total Allocation)
- 자원의 낭비가 발생 => 이미 사용이 끝난 자원도 작업이 끝날 때까지 반납하지 않음
- 특정 프로세스들의 대기시간이 과하게 길어질 수 있다는 문제가 발생
- Circular Wait 조건 제거
- 자원들에게 순서를 부여하여 자원의 순서에 따라서만 요청 가능하도록 함
- 위 예시의 경우 자원은 R1, R2, R3, R4 순으로 요청해야하며 P1은 R1, R2, R4를 필요로하고
P2는 R1, R4를 필요로한다. 그런데 P1이 R1을 먼저 할당받았기에 P2는 R1을 할당받지 못하고
R4를 할당받으려면 R1을 먼저 할당받아야하기 때문에 P1이 R1을 반납할 때 까지 대기해야한다.
이렇게 하면 순환대기 형태가 되는 것을 막을 수 있다. - 그러나 Total Allocation과 마찬가지로 자원이 필요없을 때도 점유하고있는 자원낭비가 발생할 수 있다.
- 자원들에게 순서를 부여하여 자원의 순서에 따라서만 요청 가능하도록 함
6. Deadlock 회피(Avoidance)
- 시스템의 상태를 계속해서 감시하고 시스템이 deadlock 상태에 빠질 가능성이 있다면
자원의 할당을 보류하는 방식 - 시스템을 항상 safe state로 유지하는 것으로 Deadlock이 일어나지 않도록 한다.
- Safe State
- 모든 프로세스가 정상적으로 종료 가능한 상태
- Safe Sequence 가 존재한다
=> Deadlock 상태가 되지않고 모든 프로세스를 정상적으로 실행, 종료할 수 있는 방법이 존재한다
- Unsafe State
- Deadlock 상태가 되지 않는다는 것을 보장할 수 없는 상태
- 반드시 Deadlock에 빠지는 것은 아니지만 그럴 가능성이 있다.
- Deadlock 회피의 가정
- 프로세스의 수가 고정
- 자원의 종류와 수가 고정
- 프로세스가 요구하는 자원 및 최대수량을 미리 알고있음
- 프로세스는 자원을 사용한 후 반드시 반납
- 현실적이지 못한 조건을 가정하기에 그리 실용적이진 못함
- Dijkstra의 은행원 알고리즘(Banker's Algorithm)
- Deadlock 회피를 위한 가장 간단한 기법
- 한 종류의 자원이 여러개일 경우를 가정
- 각 프로세스의 요청 자원 최대수량(max_claim), 현재 할당받은 수량(current_allocated)을 알고있으면
앞으로 추가로 필요해질 수 있는 최대 수량을 알 수 있다.(additional_need = max_claim - current_allocated) - 모든 프로세스는 추가로 필요한 자원을 받고나면 작업을 완료하고 즉각 할당받은 자원을 반납한다
=> (current_allocated + additional_need) - 만약 남아있는 자원을 적절한 순서로 분배하여 모두에게 필요한 자원을 할당할 수 있는 방법(순서)이
단 하나라도 존재한다면 현재 상태는 safe state라고 할 수 있다. - 은행원 알고리즘에서는 자원할당 요청이 들어왔을 때 자원을 할당해주기 전에 미리 테이블 상에서
max_claim, current_allocated, additional_need 값에 자원을 할당한 후의 상태를 반영하여 그 상태에서
safe sequence가 존재하는지 확인해보고 만약 존재한다면 자원을 할당해주며 존재하지 않는다면
자원의 할당을 보류한다.
- Deadlock 회피를 위한 가장 간단한 기법
- Habermann의 알고리즘
- Dijkstra의 은행원 알고리즘을 확장
- 은행원 알고리즘과 달리 여러 종류의 자원이 존재할 경우를 상정
- 은행원 알고리즘과 마찬가지로 항상 safe state를 유지
- 마찬가지로 각 프로세스의 max_calim, current_allocated, additional_need 값을 가진다.
=> 다만 은행원 알고리즘에서와 달리 n개의 자원에 대해 위 세가지 값을 각각 가지고있다. - 방식 또한 은행원 알고리즘과 마찬가지로 자원을 할당했을때의 상태를 시뮬레이트하여
safe state임이 확인되면 자원을 할당해준다.
- Dijkstra의 은행원 알고리즘을 확장
- 문제점
- 위에서도 말했듯이 프로세스의 수, 자원의 수가 고정이며 필요한 최대 자원 수를
미리 알고있다는 전제조건이 비현실적이기에 실용적이지 못함 - 시스템을 항상 감시해야하기 때문에 오버헤드가 심함
- safe state 유지를 위해 할당할 수 있음에도 할당되지 않는 자원이 존재하게된다.(자원낭비)
- 위에서도 말했듯이 프로세스의 수, 자원의 수가 고정이며 필요한 최대 자원 수를
7. Deadlock 탐지 및 복구(Detection & Recovery)
- 위에서 알아봤듯이 Deadlock의 발생을 원천적으로 차단하거나 회피하기 위한 방법은
현실적으로 구현이 어렵거나 효율성이 떨어짐 - Deadlock이 발생할 것을 전제로 하고 주기적으로 이를 탐지해내고 복구하는 방식을 고안
- Resource Allocation Graph(RAG) 사용
- 자원이 어느 프로세스에 할당되어있는지 나타내는 유향 그래프
- 노드를 자원(Resource) 과 프로세스(Process)의 두 그룹으로 나누어 자원에서
프로세스로(할당), 프로세스에서 자원으로(요청) 가는 두 가지 경우의 간선만이 존재
- 자원이 어느 프로세스에 할당되어있는지 나타내는 유향 그래프
- Graph Reduction
- 모든 자원을 할당받아 실행될 수 있는 프로세스에 연결된 간선을 모두 지워나간다.
- 주어진 RAG에서 간선을 하나씩 지워나갔을 때 모든 간선을 지울 수 없다면
하나 이상의 프로세스가 Deadlock 상태에 빠졌다고 생각할 수 있다. - 검사 주기가 짧을수록, 노드가 수가 많을수록 높은 오버헤드를 보인다.
- 모든 자원을 할당받아 실행될 수 있는 프로세스에 연결된 간선을 모두 지워나간다.
- Process Termination
- Deadlock 복구 기법중 하나
- Deadlock 상태인 프로세스중 일부를 종료시키는 것으로 Deadlock 상태에서 회복
- Termination Cost Model
- Deadlock 상태인 프로세스중 어느 프로세스를 종료시킬지 선택하기 위한 기준
- 프로세스의 종류, 우선순위, 총 실행시간, 남은 실행시간, 종료 비용 등을 고려
- Lowest Termination Cost First
- 종료 비용이 가장 적은 프로세스를 먼저 종료시키는 방식
- 단순하고 오버헤드가 적지만 데드락의 해결에 큰 도움이 되지않는 프로세스가 종료될 수 있음
- Minimum cost recovery
- 데드락을 해결할 수 있는 모든 경우중 비용이 최소가되는 경우를 찾아 종료
- 최선의 선택을 할 수 있지만 모든 경우의 수를 고려하기 위한 절차가 복잡함
- 높은 오버헤드
- Deadlock 복구 기법중 하나
- Resource Preemption
- 또다른 Deadlock 복구 기법
- Deadlock 상태를 해결하기 위해 선접할 자원을 선택
- 해당 자원을 가진 프로세스를 종료시키는 것으로 자원을 회수
=> Deadlock 상태가 아닌 프로세스가 종료될 가능성이 있음 - Process Termination 때와 마찬가지로 자원의 선점에 드는 비용을 책정하기 위한 모델 사용
- 또다른 Deadlock 복구 기법
- Checkpoint-Restart Method
- Deadlock 복구를 위해 종료된 프로세스의 재실행 시 처음부터 다시시작하는 비효율적인
상황을 방지하기 위해 일정 주기로 진행 내용을 저장하여 종료된 프로세스가 가장 최근의
checkpoint에서 재시작되도록 하는 기법
- Deadlock 복구를 위해 종료된 프로세스의 재실행 시 처음부터 다시시작하는 비효율적인