Deadlock
둘 이상의 프로세스가 서로 자원을 점유한 채 상대방의 자원을 기다리면서 무한히 대기하는 상태
다른 block된 프로세스만이 발생시킬 수 있는 이벤트를 기다리며 차단될 때, 해당 프로세스는 deadlock 상태
Reusable
사용 시 사라지지 않으나 한 번에 하나의 프로세스만 접근 가능한 자원
(프로세서, I/O 채널, 메인메모리, 보조기억장치, 세마포어와 같은 자료 구조)
Consumable
사용 시 사라지는 일시적인 자원
(인터럽트, 시그널, 메시지)
Reusable Resources Deadlock
프로세스들이 재사용 가능한 자원을 서로 점유하고 대기하며 발생하는 교착 상태
(ex. memory request)
Consumable Resources Deadlock
소모성 자원의 생성이 없을 때, 이를 기다리는 프로세스들이 무기한 대기하는 상태
Receive가 블로킹 상태일 경우 교착 상태가 발생한다
(상호 배제가 없으면 → 레이스 컨디션 발생 가능)
(상호 배제가 있고 + 나머지 3가지 조건 충족되면 → 데드락 발생 가능)
Deadlock은 다음 네 조건이 동시에 만족될 때 발생할 수 있다
Mutual exclusion (상호 배제)
한 번에 하나의 프로세스만 자원을 사용할 수 있다
Hold and wait (보유 대기)
최소 하나의 자원을 보유한 프로세스가, 다른 프로세스가 보유 중인 자원을 기다리고 있다
No preemption (비선점)
자원은 보유한 프로세스가 작업 완료 후 자발적으로 반납할 때만 회수될 수 있다
Circular wait (순환 대기)
P0는 P1이 보유한 자원을 기다리고, P1은 P2가 보유한 자원을 기다리며
Pn–1은 Pn이 보유한 자원을 기다리고, Pn은 다시 P0가 보유한 자원을 기다리는
순환적인 대기 상태가 존재한다
Mutual exclusion, Hold and wait, No preemption은 정책으로 만들어진 조건이고,
Circular wait는 정책 때문에 발행하는 상태이다
RAG(Resource Allocation Graph)
vertex는 두 가지 유형으로 구분:
T = {T1, T2, …, Tn}, 활성 스레드(또는 프로세스)들의 집합
R = {R1, R2, …, Rm}, 리소스들의 집합
요구 간선(Request edge)
Ti → Rj : 스레드 Ti가 자원 Rj를 요청
할당 간선(Assignment edge)
Rj → Ti: 자원 Rj가 스레드 Ti에게 할당되어 있음
데드락에 빠지지 않음
Add a request edge T3 → R2
Two cycle exist in this graph:
T1 → R1 → T2 → R3 → T3 → R2 → T1
T2 → R3 → T3 → R2 → T2
T1은 T2
T2는 T3
T3는 T1, T2를 기다리고 있다
이 경우 T2가 R1을 반납하고, T1이 해결되면 사이클이 풀리게 된다
=> 사이클이 있지만 데드락에 빠지지 않는다
사이클 X → 데드락 X
사이클 O → (싱글 인스턴스: 자원 유형당 인스턴스가 1개 뿐이라면) 무조건 데드락 O
사이클 O → (인스턴스 여러 개: 자원 유형당 인스턴스가 여러 개라면) 데드락에 빠질 수도, 안 빠질 수도 있다
(교착 상태 발생 가능성이 있음)
Deadlock Avoidance: 교착 상태 가능성이 있는 자원 요청을 사전에 차단함.
Deadlock Detection: 자원을 자유롭게 할당하되, 주기적으로 교착 상태를 탐지하고 복구함.
Deadlock prevention
데드락 발생 조건 네 가지 중 하나를 무효화하는 방법
Deadlock avoidance
자원 할당이 데드락을 유발할 가능성이 있다면, 해당 자원을 할당하지 않는 방법
Deadlock detection (교착 상태 탐지)
자원을 일단 할당하고, 주기적으로 데드락 발생 여부를 점검하고 복구 조치를 취하는 방법
Deadlock prevention
Mutual exclusion (상호 배제)
데이터 일관성과 무결성을 위해 OS가 반드시 지원해야 한다
쓰기 작업에 대해서는 배타적 접근만 허용하지만,
이 경우에도 두 개 이상의 프로세스가 쓰기 권한을 요구하면 교착 상태가 발생할 수 있다
Hold and wait를 무효화:
필요한 모든 자원을 할당 받을 수 있을 때 할당을 요청하는 방법
비효율성
모든 필요한 자원을 기다리느라 오랜 시간 대기할 수 있다
상당 기간 자원이 idle 상태로 남을 수 있다
(동적 환경에서 예측하기 어려움) 필요한 자원을 미리 모두 알기 어렵다
No Preemption을 무효화:
(1) 자원을 보유한 프로세스가 요청을 거부당하면, 보유하던 모든 자원을 해제하고 다시 요청해야 하는 방법
(2) 다른 프로세스가 보유한 자원을 선점하는 방법
(단, 두 프로세스가 동일한 우선순위를 가지지 않을 때만 데드락을 회피할 수 있다)
Circular Wait를 무효화:
리소드들의 순서를 정해줌으로써 예방할 수 있다
(리소스를 얻을 때, 순서대로만 얻을 수 있게 하는 방법)
비효율적(프로세스 속도를 저하, 자원 접근 제한)
동적으로 락을 획득할 수 있는 경우에는 데드락 예방이 보장되지 않는다
Deadlock avoidance
사전 정보 필요: 리소스 최대 개수
deadlock-avoidance algorithm은 자원 할당 상태를 동적으로 검사하여 circular-wait condition이 발생하지 않도록 보장
자원 할당 상태는 available(할당 가능), allocated(할당 됨), maximum demands(최대한으로 요구하는 양)으로 정의됨
Safe State
모든 프로세스가 데드락 없이 완료될 수 있는 자원 할당의 safe sequence가 존재하는 상태
스레드에 대해 (최대 요구량까지) 어떤 순서로 자원을 할당해도 교착 상태를 피할 수 있는 경우
각 Ti에 대해, Ti가 아직 요청할 수 있는 자원이
현재 사용 가능한 자원 + Ti보다 앞선 모든 Tj(j < i)가 보유한 자원으로 충족될 수 있다면
Ti가 필요한 자원을 즉시 얻지 못하더라도 Ti는 모든 Tj가 완료될 때까지 기다릴 수 있다
Tj가 완료되면 Ti는 필요한 자원을 얻어 실행하고, 할당된 자원을 반납하며 종료한다
Ti가 종료되면 Ti+1이 필요한 자원을 얻을 수 있으며, 이 과정이 계속 반복된다
safe state → 데드락 X
unsafe state → 데드락 가능성 있음 (반드시는 아니지만 빠질 수 있다)
회피(avoidance) → 시스템이 unsafe state에 진입하지 않도록 보장하는 것
싱글 인스턴스인 경우: RAG 사용
다중 인스턴스인 경우: Banker’s Algorithm 사용
claim edge
점선으로 표시한다
Ti → Rj: 스레드 Ti가 미래에 자원 Rj를 요청할 수 있음을 나타냄 (필요한 것을 전부 그어 놓는다)
안전성 검사는 cycle-detection algorithm으로 수행
사이클 X → 자원 할당 후 safe state 유지
사이클 O → 자원 할당 시 unsafe state가 됨 (이 경우, Ti는 요청이 충족될 때까지 기다려야 함)
뱅커 알고리즘
banker's algorithm은 다중 인스턴스 리소스 타입에 적용 가능하지만, RAG 방식보다 효율성이 떨어짐
할당 요청마다 연산
Banker's algorithm을 위한 자료구조
n = 스레드 수
m = 리소스 타입 수
Available
길이 m인 벡터. available[j] = k이면
리소스 타입 Rj의 사용 가능한 인스턴스가 k개임
Max
크기 n x m 행렬
Max[i, j] = k이면 스레드 Ti가 자원 유형 Rj를 최대 k개까지 요청할 수 있음
스레드가 Rj에 대하여 필요한 최대 자원의 수 (프로세스가 소비하는 최대 양)
Allocation
크기 n x m 행렬
Allocation[i, j] = k이면 Ti가 현재 자원 유형 Rj 인스턴스 k개를 할당받고 있음 (지금 할당 받은 양)
Need
크기 n x m 행렬
Need[i, j] = k이면 Ti가 작업을 완료하기 위해 자원 유형 Rj 인스턴스 k개를 추가로 필요로 함
Need[i, j] = Max[i, j] – Allocation[i, j]
Safety Algorithm
1. Work와 Finish를 각각 길이 m과 n인 벡터로 정의한다
초기화:
Work = Available
Finish[i] = false (for i = 0, 1, …, n-1)
2. 다음 두 조건을 모두 만족하는 i를 찾는다.
(아직 끝나지 않았으면서, Need만큼 필요한데, Work가 그 이상 있는 경우)
(a) Finish[i] = false
(b) Need[i] ≤ Work
만약 그런 i가 없으면 4단계로 간다
3. Work = Work + Allocation[i]
(해당 스레드 할당 했던 것을 work에 더해 주고, Finish를 true로 바꾸어 준다)
Finish[i] = true
2단계로 돌아간다
4. 모든 i에 대해 Finish[i] = true이면, 시스템은 safe state
전부 다 true: safe
하나라도 false: unsafe -> 할당 x
Resource-Request Algorithm for Process Pi
Request[i]는 스레드 Ti의 요청 벡터이다.
Requesti[j] = k이면 스레드 Ti가 자원 유형 Rj 인스턴스 k개를 요청한다는 의미
1. 만약 Request[i] ≤ Need[i]이면 2단계로 진행한다. (필요한 것보다 적게 요청하면, 2단계 진행)
그렇지 않으면, 스레드가 최대 요구량을 초과했으므로 오류를 발생시킨다.(필요한 것보다 많이 요청하면, 오류)
2. 만약 Request[i] ≤ Available이면 3단계로 진행한다. (가능한 것보다 적게 요청하면, 3단계 진행)
그렇지 않으면, 자원이 부족하므로 Ti는 기다려야 한다. (가능한 것보다 많이 요청하며, 대기)
=> 해당 스레드가, Request[i] < Need[i] && Request[i] < Available[i]이면...
3. 요청 자원을 Ti에게 할당하는 척 하면서 상태를 다음과 같이 변경한다:
Available = Available – Request[i]
Allocation[i] = Allocation[i] + Request[i]
Need[i] = Need[i] – Request[i]
safe하면 → 자원을 Ti에게 실제로 할당한다
unsafe하면 → Ti는 기다려야 하며, 이전 자원 할당 상태로 복구한다
Safe Test (available을 need와 비교하고, allocation을 더해 줌)
Ex1) T1 Request: (1,0,2)
Ex 2) T4 Request for (3,3,0)
- Request < Need 만족
- Request < Available 만족 x => 지금 할당x, 대기해야함
Ex 3) T0 Request for (0,2,0)
- Request < Need 만족
- Request < Available 만족 x => 지금 할당x, 대기해야함
- 그러나 safe 알고리즘 돌려보면, unsafe라고 나옴
데드락 회피의 단점
- 전체 용량 알아야 적용 가능하므로, 동적 환경에서 활용하기 어려움
- 연산량이 많음
Deadlock detection
교착 상태 발생 여부를 판단하기 위한 알고리즘
교착 상태에서 복구하기 위한 알고리즘
리소스 타입에 단일 인스턴스가 있는 경우: wait-for graph를 유지
- RAG의 변형이다
- 노드는 스레드(또는 프로세스)를 나타낸다
- Ti → Tj는 Ti가 Tj를 기다리고 있음을 의미한다
- 주기적으로 사이클 탐색 알고리즘을 실행한다
- 사이클이 존재하면 교착 상태가 발생한 것
리소스 타입에 다중 인스턴스가 있는 경우: deadlock detection algorithm
- wait-for graph 방식은 각 리소스 타입에 여러 인스턴스가 있는 경우에는 적용할 수 없다
- 이런 시스템에는 banker's algorithm과 유사한 deadlock detection algorithm이 적용 가능
- Available: 길이 m인 벡터로, 각 리소스 타입별 사용 가능한 인스턴스 수를 나타냄
- Allocation: 크기 n x m 행렬로, 각 프로세스에 현재 할당된 리소스 타입별 인스턴스 수를 정의
- Request: 크기 n x m 행렬로, 각 프로세스가 현재 요청하는 자원 수를 나타낸다.
- (Request[i][j] = k이면, 스레드 Ti가 자원 유형 Rj 인스턴스 k개를 추가로 요청하고 있음을 의미)
- (banker's algorithm과 다르게, max나 need는 없다)
Banker's algorithm
- Deadlock avoidance에서 사용된다
- max와 need가 있다
- available과 need를 비교하고, avilable과 allocation을 합산한다
Deadlock detectio algorithm
- Deadlock detection에서 사용된다
- max나 need가 없다
- available과 request를 비교하고, available과 allocation을 합산한다
Detection Algorithm
1. Work와 Finish를 각각 길이 m과 n인 벡터로 정의한다.
Initialize:
Work = Available
i = 1, 2, …, n에 대해, Allocation[i] ≠ 0 이면 Finish[i] = false,
그렇지 않으면 Finish[i] = true
(이미 자원을 가지고 있는 프로세스는 아직 완료되지 않았으므로 Finish[i] = false)
(아무 자원도 안 쓰고 있는 프로세스는 즉시 종료 가능하므로 Finish[i] = true)
2. 다음 조건을 모두 만족하는 i를 찾는다:
(a) Finish[i] == false
(b) Request[i] ≤ Work
(아직 안 끝난 애들 중에서, 가능한 것보다 적게 요청하는 경우)
만약 그런 i가 없으면 4단계로 간다
3. Work = Work + Allocation[i]
Finish[i] = true
2단계로 돌아간다
4. 모든 i에 대해 Finish[i] == true이면 시스템은 교착 상태가 아니다
만약 1 ≤ i ≤ n 중 일부 Finish[i] == false이면, 시스템은 교착 상태에 있다
또한 Finish[i] == false인 Ti가 교착 상태에 빠진 프로세스이다 (false인 애들은 전부 데드락 빠진 애들이다)
(available을 request와 비교하고 allocation을 더해준다)
Detection-Algorithm Usage
- 데드락이 자주 발생한다면 detection-algoritm도 자주 호출해야 한다
- 매 번 할당 요청 시마다 detection algorithm을 돌리면 너무 비효율적(overhead가 너무 큼)
- 데드락 발생 시 데드락 사이클에 포함된 스레드 수는 증가할 수 있다
- 정해진 간격마다 탐지 알고리즘을 호출하는 경우
예) 한 시간에 한 번 혹은 CPU 사용률이 40% 이하로 떨어질 때마다 호출한다.
- arbitrary한 시점에 detection algorithm을 호출하면
리소스 그래프는 많은 사이클을 포함할 수 있다, 이 경우 어떤 스레드가 데드락을 유발했는지 구분하기 어렵다
데드락으로부터 복구
탐지 알고리즘이 교착 상태를 발견하면,
(1) 데드락 발생을 운영자에게 알리고 처리하도록 하는 것
(2) 시스템이 자동으로 복구하도록 하는 것
- 하나는 circular wait를 끊기 위해, 데드락에 빠진 스레드 중 하나 이상의 스레드를 중단하는 것
- 다른 하나는 데드락에 빠진 스레드 중 일부에서 자원을 선점하는 것
프로세스 종료
데드락을 제거하기 위해 스레드를 중단할 때
(두 방법 모두 종료된 프로세스에 할당된 모든 자원을 시스템이 회수함)
1. 데드락에 빠진 모든 프로세스를 중단
2. 데드락이 해소될 때까지 한 번에 한 프로세스씩 중단
(중단할 프로세스의 선택은 시스템의 정책에 따라서 다르다)
자원 선점
데드락 제거하기 위해 자원 선점을 사용하는 경우,
데드락 순환이 끊어질 때까지 일부 자원을 차례로 선점하여 다른 프로세스에 할당한다
세 가지 이슈들이 다루어져야한다:
1. victim 선택 – 비용을 최소화하도록 victim을 선택하여야 한다
2. rollback – safe state로 되돌리고, 해당 state로부터 프로세스를 다시 시작, 최대한 가까운 safe state로 롤백한다
3. starvation – 동일한 프로세스가 계속 victim이 되지 않도록 victim이 되는 횟수 제한