Deadlocks
- CPU를 받지 못 하는 waiting process에 의해 발생할 수 있는 이벤트를 기다리는 것으로 영원히 일어나지 않는 상태
- Deadlock Prevention - 보수적, 자원 효율 ↓ (프로세스 시작 전 자원 확보)
- Deadlock Avoidance - deadlock에 접근, 자원 활용도 조금 더 높음
- Deadlock Detection - deadlock 발생 시 무시 → 어느 부분에서 발생했는지 알려줌, 어떤 경우에 발생하는지 알고 코드를 변경하는 것이 필요함 (다른 패턴으로 바꾸기)
- Recovery from Deadlock - deadlock 발생 시 어떻게 회복 시킬 것인지에 대한 것
- system calls, locking 등을 통해 발생할 수 있음
System Model
- 시스템이 리소스로 구성
- 리소스 유형 R1, R2, . ., Rm
- CPU 주기, 메모리 공간, I/O devices
- 각 리소스 유형 Ri에는 Wi 인스턴스가 있음
- 각 프로세스는 다음과 같이 리소스를 활용
- request - 자원 요청
- use - 자원을 할당 받아 사용 중
- release - 자원 사용이 끝나 필요 없음
Deadlock Characterization
4가지 조건이 동시에 유지되면 Deadlock 발생 가능
- Mutual exclusion: 한 번에 하나의 프로세스만 리소스를 사용 가능 (대부분의 자원이 공유 가능하지 않아 한 프로세스에 의해서만 실행됨)
- Hold and wait: 하나 이상의 리소스를 보유한 프로세스가 다른 프로세스에서 보유한 추가 리소스를 획득하기 위해 기다림
- No preemption: 빼앗을 수 없음, 리소스는 해당 프로세스가 작업을 완료한 후 리소스를 보유한 프로세스에 의해서만 자발적으로 해제될 수 있음 (해당 프로세스가 자발적으로 리소스를 내주지 않는 한 사용을 끝낼 때까지 기다림)
- Circular wait(순환 대기): 대기 프로세스 집합 {P0, P1, …, Pn}이 존재할 때, P0은 P1이 보유한 리소스를 대기하고, P1은 P2가 보유한 리소스를 대기하고, Pn–1은 Pn이 보유한 리소스를 대기하고, Pn은 P0이 보유한 리소스를 대기함
Deadlock은 system calls, locking 등을 통해 발생할 수 있음
Resource-Allocation Graph
- 정점 집합 V, 모서리 집합 E
- V는 두 가지 유형으로 분할
- P = {P1, P2, …, Pn}, 시스템의 모든 process로 구성된 집합
- R = {R1, R2, …, Rm}, 시스템의 모든 resource 유형으로 구성된 집합
- V는 두 가지 유형으로 분할
- request edge – 방향 에지 Pi → Rj (프로세스에서 리소스로)
- assignment edge – 방향 에지 Rj → Pi (리소스에서 프로세스로, 리소스가 프로세스에 의해 할당)
Example of a Resource Allocation Graph (Deadlock X)
- P3는 자원을 요청하지 않음, P3가 할당받은 리소스 R3를 수행한 후 release
- P2는 1에 의해 R3에 대한 요청이 받아들여질 수 있게 되어 리소스 R3를 할당받아 수행
- 리소스 R1은, P2가 수행하고 release한 후에 P1이 수행
Resource Allocation Graph With A Deadlock
- R과 P 사이에 cycle이 형성됨
- P3는 R2에 여분이 없어 wait하게 됨
- P2는 R3에 여분이 없어 wait하게 됨
- P2, P3로 인해 deadlock이 발생
- recovery 방법
- P2, R3 kill → 나중에 restart 시켜줘야 함
- 누구를 kill 시킬지 생각해야 함
Graph With A Cycle But No Deadlock
- cycle이 형성되어 있지만 deadlock이 발생하지 않는다!
- multiple instance의 경우 cycle이 발생하더라도 프로세스가 나눠서 가질 수 있는 경우에는 deadlock이 발생하지 않음
Basic Facts
- graph에 cycle이 없는 경우 → deadlock 없음
- graph에 cycle이 있는 경우
- 리소스 유형당 하나의 인스턴스만 있는 경우 : deadlock
- 리소스 유형당 여러 인스턴스가 있는 경우 : deadlock이 발생할 수 있음 (인스턴스의 개수보다 더 많은 프로세스가 요청한다면 deadlock이 발생가능 ex) P 3개, R 인스턴스 2개)
Methods for Handling Deadlocks
- Deadlock prevention
- Deadlock avoidence
- 시스템이 deadlock state에 들어가 복구하도록 허용
- 문제를 무시하고 시스템에서 Deadlock이 발생하지 않는 것처럼 가장함, UNIX를 비롯한 대부분의 운영 체제에서 사용 → 사용자가 deadlock이 발생하지 않도록 만들어줘야 함
Deadlock Prevention
Mutual Exclusion
- 리소스를 공유 가능하도록 만든다.
- consistency 문제가 발생해 mutual exclusion을 부정할 수 없음
Hold and Wait
- 프로세스가 리소스를 요청할 때, 다른 리소스를 보유하고 있지 않도록 보장
- 두 가지 방법으로 부정 가능
- 수행 전에 프로세스가 필요한 모든 리소스를 요청해 할당받아 수행
- 프로세스에 할당된 리소스가 없는 경우에만 프로세스가 리소스를 요청하도록 허용함
- 문제
- 낮은 리소스 활용률: 프로세스의 끝부분에 필요한 리소스를 미리 가지고 있을 경우 효율이 떨어짐
- starvation 가능성: 모든 리소스를 가져야만 시작할 수 있음
No Preemption
- 일부 리소스를 보유하고 있는 프로세스가 즉시 할당할 수 없는 다른 리소스를 요청하면 현재 보유 중인 모든 리소스를 내주고 나중에 다시 요청
- 선점된 리소스가 프로세스가 기다리는 리소스 목록에 추가됨
- 프로세스가 요청 중인 새 리소스뿐만 아니라 이전 리소스를 다시 찾을 수 있는 경우에만 프로세스가 다시 시작
- 중단했다가 중단된 시점부터 재시작할 수 있는 리소스의 경우 사용 가능
- Blocked Semaphore와 유사 - 프로세스 자신이 가지고 있는 CPU를 포기하고 block 상태로 갔다가 나중에 다시 요청함
Circular Wait
- 모든 리소스 유형의 총 순서를 지정하고 각 프로세스가 순서에 따라 리소스를 요청
- 순번이 증가하는 순서대로 리소스를 가질 수 있게 만들어 준다면 deadlock이 발생하지 않을 수 있음
Deadlock Example
/* thread one runs in this function */
void *do_work_one(void *param)
{
pthread_mutex_lock(&first_mutex); // 1
pthread_mutex_lock(&second_mutex); // 3
/** * Do some work */
pthread_mutex_unlock(&second_mutex);
pthread_mutex_unlock(&first_mutex);
pthread_exit(0);
}
/* thread two runs in this function */
void *do_work_two(void *param)
{
pthread_mutex_lock(&second_mutex); // 2
pthread_mutex_lock(&first_mutex); // 4
/** * Do some work */
pthread_mutex_unlock(&first_mutex);
pthread_mutex_unlock(&second_mutex);
pthread_exit(0);
}- CPU 사용 순서에 따라 deadlock이 발생할 수도, 발생하지 않을 수도 있음
- 주석에 해당하는 순서로 CPU가 할당된다면 deadlock 발생
Deadlock Example with Lock(자원) Ordering
void transaction(Account from, Account to, double amount)
{
mutex lock1, lock2;
lock1 = get_lock(from); // 순서 1
lock2 = get_lock(to); // 순서 2
acquire(lock1);
acquire(lock2);
withdraw(from, amount);
deposit(to, amount);
release(lock2);
release(lock1);
}- from, to를 static하게 정함(컴파일 시(런타임 이전))→ deadlock 방지 가능
- from, to에 해당하는 lock이 런타임 시에 동적으로 결정 → 순서 정하더라도 deadlock 발생 가능
- 트랜잭션 1과 2가 동시에 실행 → 트랜잭션 1은 A(from) 계좌에서 B(to) 계좌로 25달러를 송금하고 트랜잭션 2는 B(from) 계좌에서 A(to) 계좌로 50달러를 송금함 - Cycle이 형성됨
- lock의 순서를 결정하는 것은 수행시에 얼마든지 변경될 수 있음. 런타임 시 동적으로 할당되는 경우 순서를 정하더라도 deadlock 발생 가능
- account A가 from이고 account B가 to로 static하게 결정 → lock ordering으로 deadlock 방지 가능
Deadlock Avoidance
- 사용하기 위해 각 프로세스가 자신이 필요한 리소스의 최대 개수를 알려줘야 하는 문제점이 있음
- 가장 간단하고 가장 유용한 모델은 각 프로세스가 필요한 각 유형의 최대 리소스 수를 선언하는 것
- Deadlock-avoidance 알고리즘은 resource-allocation 상태를 동적으로 검사하여 순환 대기(circular-wait) 조건이 절대 존재할 수 없도록 함
- Resource-allocation 상태는 사용 가능한 리소스의 수, 할당된 리소스의 수와 프로세스의 최대 요구량에 따라 정의됨
Safe State
- 프로세스가 요청하는 리소스를 할당받을 수 있는 상태
- 프로세스가 사용 가능한 리소스를 요청할 때 시스템은 즉시 할당이 시스템을 safe state로 유지하는지 여부를 결정
- 시스템에 있는 모든 프로세스의 순서 <P1, P2, …, Pn>이 존재할 때, 각 Pi에 대해 Pi가 요청하는 리소스가 현재 사용 가능한 리소스 + Pj (j < i) 에 의해 hold된 리소스를 만족시킬 때 시스템은 safe state이다.
- available한 resource의 개수 ≥ 프로세스가 요청하는 리소스의 개수
- available한 resource의 개수 + 다른 프로세스가 수행하고 release하는 리소스 개수 (nR(Pj)) ≥ 프로세스가 요청하는 리소스 개수 (nR(Pi))
- Pi 리소스 요청을 즉시 사용할 수 없는 경우 Pi는 모든 Pj가 완료될 때까지 기다림
- Pj가 완료되면 Pi는 필요한 자원을 얻고, 실행하고, 할당된 자원을 반환하고, 종료함
- Pi가 종료되면 P(i+1)은 필요한 리소스를 얻을 수 있음
Basic Facts
- safe state - 프로세스가 요청하는 리소스들을 할당받을 수 있는 상태 (약간의 delay 가능) → deadlock 발생하지 않음
- unsafe state - 프로세스가 요청하는 리소스들을 할당받을 수 없는 상태 → deadlock 발생 가능
- deadlock - 모든 프로세스가 unsafe한 상태 (모든 프로세스가 움직일 수 없음)
- Avoidance → 시스템이 unsafe state로 빠지지 않도록 보장함
- unsafe ≠ deadlock
Avoidance Algorithms
- 리소스 한 개 (단일 인스턴스) - resource-allocation graph 사용
- 리소스 여러 개 (여러 인스턴스) - banker’s algorithm 사용
Resource-Allocation Graph Scheme
- Claim edge - Pi → Rj, 프로세스 Pi가 리소스 Rj를 예약, 점선으로 표시됨
- Request edge - Pi → Rj, 프로세스 Pi가 리소스 Rj를 요청
- Assignment edge - Pi ← Rj, 프로세스 Pi가 리소스 Rj를 할당받음
- 프로세스가 리소스를 요청 → claim edge가 request edge로 변환됨
- 리소스가 프로세스에 할당 → request edge가 assignment edge로 변환됨
- 프로세스에서 리소스를 해제 → assignment edge가 Claim edge로 다시 변환됨
- 시스템에서 리소스를 우선 순위로 할당해야 함
- 세 가지의 edge로 인해 cycle이 발생한다면 deadlock 발생 가능 → 요청을 받아들였기 때문에 발생(claim x)
- 요청을 받아들여서 R2가 P2에 할당됨 → Cycle 형성 → deadlock 발생 가능
- 요청을 받아들이면 안 됨!
- P1이 R2를 요청하면 deadlock이 발생함, P1이 R1을 먼저 release 해야 함
- Pi가 리소스 Rj를 요청한다고 가정
- request edge를 assignment edge로 변환해도 resource allocation graph에 cycle이 형성되지 않는 경우에만 요청을 허용 (할당을 해주는 것 x)
Banker’s Algorithm
- Multiple instances의 리소스에 사용
- 각 프로세스는 우선적으로 최대로 사용할 리소스의 개수를 표시해야 함 (미리 예약)
- 프로세스가 리소스를 요청했을 때 available 하지 않다면 대기해야 할 수 있음
- 프로세스가 자신이 요청한 리소스를 할당 받는다면 제한된 시간 내에 return하며 자신이 할당한 리소스를 release시킴
Data Structures for the Banker’s Algorithm
n개의 process와 m개의 resource
- Available: 길이 m의 벡터. available [j] = k인 경우, 리소스 Rj 인스턴스가 k개 사용 가능
- Available [j] = 전체 리소스 개수 - 할당 중인 리소스 개수
- Max: n x m 행렬. Max [i,j] = k인 경우, 프로세스 Pi는 리소스 Rj의 최대 k개 인스턴스를 요청(필요로 함)
- Allocation: n x m 행렬. Allocation [i,j] = k인 경우, Pi는 현재 리소스 Rj의 k개 인스턴스를 가지고 있음(할당 중)
- Need: n x m 행렬. Need[i,j] = k인 경우, Pi는 작업을 완료하기 위해 추가적으로 Rj 인스턴스 k개가 필요함
- Need [i,j] = Max [i,j] – Allocation [i,j]
Safety Algorithm
- 각각 Work와 Finish를 길이 m과 n의 벡터라고 함
- Work = Available
- Finish [i] = false for i = 0, 1, …, n- 1
- 다음을 모두 충족하는 i를 찾음
- (a) Finish [i] = false
- (b) Need i ≤ Work (available 개수)
- 이러한 i가 없으면 4단계로 이동
- Work = Work + Allocation i (수행이 끝나고 release하면 available은 가지고 있는 리소스 개수만큼 증가)
Finish[i] = true
2단계로 이동 - 모든 i에 대해 Finish [i] == true이면 시스템은 safe state → 초기 request를 받아도 됨
특정 프로세스의 Finish[i] = false → 끝내지 못하는 프로세스 존재 → deadlock 가능성
모든 프로세스에 대해 Finish[i] = false → deadlock
Avoidance Algorithm → 프로세스를 unsafe 상태로 들어가게 해서는 안 됨
Resource-Request Algorithm for Process Pi
Request i = 프로세스 Pi에 대한 request vector, Request i [j] = k인 경우 프로세스 Pi는 리소스 Rj의 k개 인스턴스 요청
- Request i ≤ Need i인 경우 2단계로 이동, 그렇지 않으면 프로세스가 최대 claim을 초과했으므로 error condition 제기(자신이 예약한 것보다 더 많은 리소스를 요청한 것임)
- Request i ≤ Available(현재 시스템에 가용한 리소스의 개수)인 경우 3단계로 이동 → 그렇지 않으면 리소스를 사용할 수 없기 때문에 Pi가 기다려야 함. Request i ≥ Available인 경우에도, 이전 프로세스가 resource를 release한다면 safe state가 될 수 있음 (delay 존재)
- 다음과 같이 상태를 수정하여 요청된 자원을 Pi에 할당하는 시뮬레이션
- Available = Available – Request i;
- Allocation i = Allocation i + Request i;
- Need i = Need i – Request i;
- safe → 리소스가 Pi에 할당됨
- unsafe → Pi가 기다려야 하며 이전 리소스 할당 상태가 복원됨
- 이 상태에서 위의 simulation algorithm(safety Algorithm) 수행 - 모든 프로세스가 safe 상태일 때만 이 request를 받아들임, 프로세스가 request를 할 때 unsafe 상태로 갈 것이냐 안 갈 것이냐를 판단
Example of Banker’s Algorithm
- 5 processes P0 through P4, 3 resource types: A (10 instances), B (5instances), and C (7 instances)
- Need = Max – Allocation
P0 현재 unsafe 상태는 x (safe 가능) → but, 당장은 시작할 수 없어 기다려야함
- P1 → (5, 3, 2) (+(2, 0, 0))
- P3 → (7, 4, 3) (+(2, 1, 1))
- P4 → (7, 4, 5) (+(0, 0, 2))
- P2 → (10, 4, 7) (+(3, 0, 2))
- P0 → (10, 5, 7) (+(0, 1, 0))
시퀀스 <P1, P3, P4, P2, P0>이 safety 기준을 충족하므로 시스템이 safe state
모든 프로세스가 안전하게 끝낼 수 있는 상태가 있으면 safe state (약간의 기다림은 있을 수 있음)
Example: P1 Request (1,0,2)
Request ≤ Available 확인 ( (1, 0, 2) ≤ (3, 3, 2) → true)
- P1 → (5, 3, 2) (+(3, 0, 2))
- P3 → (7, 4, 3) (+(2, 1, 1))
- P4 → (7, 4, 5) (+(0, 0, 2))
- P0 → (7, 5, 5) (+(0, 1, 0))
- P2 → (10, 5, 7) (+(3, 0, 2))
- safety algorithm을 실행하면 시퀀스 < P1, P3, P4, P0, P2>가 안전 요구 사항을 충족
- P4의 (3,3,0)에 대한 요청이 허용될 수 있을까?
- 받아들일 수 없다. 기다려야 함. unsafe 라고 말할 수는 없음 → 이 다음에 수행되는 프로세스들이 수행한 후 release한 다음에 P4가 끝낼 수 있는 sequence가 있을 수 있음
- P0의 (0,2,0)에 대한 요청이 허가될 수 있을까?
- available (2, 3, 0) - request (0, 2, 0) = (2, 1, 0)
- P0가 (0, 2, 0)만큼 요청하는 것을 받아들이면 P0 ~ P4 수행하지 못함
- 모든 프로세스가 deadlock에 빠질 수 있는 상태 유발 (아닐 수도 있음)
- 요청을 받아들일 경우 시스템은 unsafe한 상태가 되어 받아들이면 안 됨
Deadlock Detection
- 현재 상태가 deadlock에 빠졌는지 확인하는 알고리즘
- Allow system to enter deadlock state
- Detection algorithm
- Recovery scheme
Single Instance of Each Resource Type
- wait-for graph
- 프로세스만을 가지고 표시 (노드는 프로세스들임)
- Pi → Pj - Pi가 Pj를 기다림 (Pj가 할당받은 리소스를 기다림)
- 그래프에서 cycle을 찾는 알고리즘을 주기적으로 호출 → cycle이 있으면 deadlock 상태에 있는 것
- 그래프에서 cycle을 탐지하는 알고리즘은 n^2개의 연산을 필요로 함 (n은 그래프의 정점 수)
cycle 존재 → 끝낼 수 있는 방법이 없어 deadlock에 빠짐
Several Instances of a Resource Type
- Available : 길이 m의 벡터는 사용 가능한 리소스 수를 나타냄
- Allocation : n x m 행렬은 프로세스에 할당된 리소스 수를 정의함
- Request : n x m 행렬은 현재 요청을 나타냄. Request [i][j] = k인 경우 프로세스 Pi는 리소스 Rj의 인스턴스를 추가로 요청
Detection Algorithm
- Work와 Finish를 각각 길이 m과 n의 벡터라 함
- Work = Available
- For i = 1,2, …, n, Allocation i ≠ 0 → Finish[i] = false, 그렇지 않으면 Finish[i] = true
- 다음과 같은 인덱스 i를 찾음
- Finish[i] == false
- Request i ≤ Work
- 이러한 i가 없으면 4단계로 이동
- Work = Work + Allocation i
Finish[i] = true
2단계로 이동 - 1 ≤ i ≤ n에서 어떤 i가 Finish[i] == false인 경우 시스템은 deadlock state. 또한 Pi는 deadlocked
알고리즘을 사용하려면 시스템이 deadlock 상태에 있는지 여부를 감지하기 위해 O(m x n^2) 작업이 필요
Example of Detection Algorithm
5 processes P0 through P4; three resource types; A (7 instances), B (2 instances), and C (6 instances)
- P0 → (0, 1, 0) (+(0, 1, 0))
- P2 → (3, 1, 3) (+(3, 0, 3))
- P3 → (5, 2, 4) (+(2, 1, 1))
- P1 → (7, 2, 4) (+(2, 0, 0))
- P4 → (7, 2, 6) (+(0, 0, 2))
시퀀스 <P0, P2, P3, P1, P4>는 Finish[i] = 모든 i에 대해 true가 됨 → deadlock x
Example (Cont.)
P2 requests an additional instance of type C
- P0 → (0, 1, 0)
- 프로세스 P0이 보유한 리소스를 회수할 수 있지만 다른 프로세스를 수행할 리소스가 부족
- 이 상태에서 움직이지 않는다면 deadlock 상태에 빠지고, 프로세스 P1, P2, P3, P4는 deadlock 상태를 유발시키는 프로세스가 됨
Deadlock Avoidance - 요청을 받아들여서 unsafe state인지 예측해 받아들이지 않음
Deadlock Detection - 요청을 다 받아들이고 시스템이 멈췄을 때 이 상태가 deadlock 때문인지 판별
Detection-Algorithm Usage
- 호출 시기와 빈도는 다음에 따라 달라짐
- deadlock 상태가 얼마나 자주 발생하는가?
- deadlock 이전 상태로 rollback해야 하는 프로세스는 몇 개인가?
- 분리된 각 사이클당 하나
- detection-algorithm이 임의로 호출되면 리소스 그래프에 많은 cycle이 있을 수 있으므로 많은 deadlock 상태 프로세스 중 어떤 프로세스가 deadlock 상태를 발생시켰는지 알 수 없음
Recovery from Deadlock: 1. Process Termination
- deadlock 상태에 있는 모든 프로세스 중단
- deadlock 상태 cycle이 제거될 때까지 한 번에 하나의 프로세스 중단
- 어떤 순서로 중단할지 선택
- 우선순위 낮은 프로세스
- 프로세스가 수행된 시간 및 완료되는 데 걸리는 시간
- 프로세스가 사용한 리소스의 수
- 프로세스를 완료할 때까지 필요한 리소스의 수
- 종료해야 하는 프로세스 수
- 프로세스가 interactive인지, batch형인지?
Recovery from Deadlock: 2. Resource Preemption
- Selecting a victim(희생자 선택) – 비용 최소화
- rollback – 안전한 상태(리소스 갖기 이전 상태)로 돌아가서 해당 상태에 대한 프로세스를 다시 시작
- starvation – 비용 요인에 rollback 횟수를 포함하여 항상 동일한 프로세스를 희생자로 선택할 수 있음
참고 자료 : Operating System Concepts - 10th edition, Sliberscahatz, Galvin and Gagne
'CS > 운영체제' 카테고리의 다른 글
| 운영체제 ch 10. Virtual Memory (0) | 2023.06.09 |
|---|---|
| 운영체제 ch 9. Main Memory (0) | 2023.05.15 |
| 운영체제 ch 7. Synchronization Examples (0) | 2023.05.02 |
| 운영체제 ch 6. Synchronization Tools (0) | 2023.04.18 |
| 운영체제 ch 5. CPU Scheduling (0) | 2023.04.12 |
