2022. 4. 23. 22:19ㆍMajor`/운영체제
각 프로세스들이 자원을 보유한 상태에서 "서로 다른 프로세스의 자원을 요구함"에 따라서 Reqeust한 프로세스들이 Block되는 현상을 "Deadlock이 발생했다"라고 한다
- 한마디로 본인 자원은 내놓지 않으면서 다른이의 자원만 요구해서 결국 block되는 경우이다
이러한 Deadlock은 어떤 프로세스의 희생이 있다면 결코 발생하지 않을 것이다
"Deadlock 프로세스 집합"은 다른 의미로 "자원을 Hold한 상태로 Block된 프로세스들의 집합"이라고 할 수 있다
## P0 ##
wait(A);
wait(B);
## P1 ##
wait(B);
wait(A);대표적인 Deadlock의 예이다
P0는 wait(A)를 통해서 자원 A를 갖게 되었고, P1은 wait(B)를 통해서 자원 B를 갖게 되었다
이 다음 P0는 wait(B)를 통해서 자원 B를 요구하고 있고, P1은 wait(A)를 통해서 자원 A를 요구하고 있다
이렇게 자원의 여부가 있다면 Deadlock은 일어날 일이 없다
하지만 자원 A, B의 instance가 하나씩 존재한다면??
이 상태로 자원이 없는데도 불구하고 wait()를 통해서 호출을 하니까 프로세스 A, B 둘다 block이 됨으로써 Deadlock이 발생하게 된다
프로세스가 자원을 요청하고 반납하는 절차
1. Request : 자원 요청
2. Allocate : 자원 할당
3. Use : 자원 사용
4. Release : 자원 반납
Deadlock 발생 4가지 조건
다음 4가지 조건을 "모두 만족"해야 Deadlock이 발생한다
1) Mutual Exclusion : 상호 배제
"매 순간 그 자원은 하나의 프로세스만 사용 가능하다"
이 조건은 당연히 만족되는 조건이다
왜냐하면 애초에 프로세스에게 자원을 할당할 때는 "Mutual Exclusive"하게 할당해줌으로써 Critical Section 문제가 발생되지 않게 해야한다
2) No Preemption : 비선점
"프로세스는 자원을 강제로 빼앗기지 않는다"
만약 선점 스케줄링의 경우 그냥 프로세스가 Request하면 다른 프로세스로부터 그 자원을 강제로 빼앗으면 되기 때문에 Deadlock이 발생하지 않는다
3) Hold & Wait : 보유 대기
"본인이 자원을 보유하고 있으면서 다른 자원을 대기하는 것"
4) Circular Wait : 순환 대기
"모든 프로세스가 자원을 요청할 때 꼬리를 무는 상황이 발생한 경우"
순환 대기의 경우 "점유 대기 & 비선점"을 만족해야 성립하므로 이 4가지 조건은 서로 완전 독립적이지는 않다
Resource-Allocation Graph
프로세스 A가 존재한다하고 A의 자원 요청 반납 절차를 그래프를 통해서 파악해보면
1) Request :: wait(K)
이렇게 "Process → Resource" 화살표를 통해서 Request를 표현해준다
당연히 자원이 없다면 이 상태로 Process A는 Block된다
2) Allocate
"Resource → Process" 화살표를 통해서 Allocate를 표현해준다
4) Release :: signal(K)
반납한다면 다시 초기상태로 돌아간다
자원 할당 그래프 ↔ Deadlock 관계
1) 그래프에 Cycle 존재 X
이 경우는 간단하다 :: Cycle이 없으면 Deadlock도 없다
Cycle이 없으므로 Deadlock도 없는 것을 파악할 수 있다
2) 그래프에 Cycle 존재 O
이 경우는 또 2가지로 나눌 수 있다
▶ 자원의 instance가 1개
instance가 1개라면 반드시 Deadlock이다
Cycle이 존재하고 {R1, R3}의 instance가 1개이므로 이 경우는 Deadlock이 발생한다
▶ 자원의 instance가 여러개
instance가 여러개라면 "Deadlock일 가능성"이 존재한다
이 사진도 보면 Cycle이 존재한다
그런데 instance가 여러개이므로 반드시 Dealock이 아닌 "Deadlock일 가능성"이 존재한다
결론적으로 말하면 이 사진에서는 Deadlock이 발생하지 않는다
왜냐하면 현재 Deadlock Cycle과 연관된 Process & Resource는 {P1, P3 - R1, R2}이다
P2, P4는 현재 Deadlock Cycle과 연관이 없고 만약 P2, P4 프로세스들의 R1, R2를 반납한다면???
>> P1이든 P3든 Request한 요청에 대해서 할당을 받을 수 있다
Deadlock 처리 방법
Deadlock을 처리하는 방법은 크게 3가지로 분류할 수 있다
1. 사전에 Deadlock 방지
Deadlock Prevention / Deadlock Avoidance
이 방법은 애초에 시스템에서 Deadlock이 발생하지 않도록 미리 차단하는 방식이다
물론 이러한 방법은 Deadlock에 대한 걱정을 할 필요는 없지만, Deadlock은 굉장히 드물게 발생하고 이렇게 드물게 발생하는 문제에 대해서 미리 제약조건을 많이 설정해놓으면 시스템 자원 사용에 있어서 효율성이 떨어지게 된다
2. Deadlock 감지하고 처리
Deadlock Detection & Recovery
이 방법은 일단 Deadlock은 발생한다. 그리고 발생한 Deadlock에 대해서 Recovery하는 방법이 존재한다
3. Deadlock 무시
Deadlock Ignorance
이 방법은 현대 OS에서 대부분 사용하는 방식이다.
시스템은 Deadlock에 관련된 모든 사항을 무시하고 오로지 Deadlock Handling을 user에게 맡기는 방식이다
방법 1) Deadlock Prevention
Deadlock 발생 4가지 조건(Mutual Exclusion / No Preemption / Hold & Wait / Circular Wait)중 "어느 하나가 만족되지 않게 설정"해줌으로써 Deadlock을 미연에 방지하는 방식
Mutual Exclusion 만족 X
결론적으로 말하자면 Mutual Exclusion을 만족 시키지 않고 프로세스들에게 자원을 할당해주는 방법은 "존재하지 않는다"
왜냐하면 애초에 프로세스 간에 동기화를 하기 위해서는 Critical Section에 여러 프로세스가 동시에 들어가지 않게 해주어야 하고 이말은 곧 각 프로세스에게 "자원 자체를 Mutual Exclusive하게 할당"해줘야 한다는 의미이다
따라서 Mutual Exclusion 조건을 만족 시키지 않을수는 없다
No Preemption 만족 X
Process A가 현재 {R1, R2, R3}자원을 보유한다고 하자
그리고 A는 새롭게 자원 R4를 요청한다고 하자
이 때 자원 R4가 즉시 할당될 수 있다면 그냥 즉시 할당받으면 된다
하지만 자원 R4가 즉시 할당될 수 없다면??
>> A는 본인이 보유한 자원{R1, R2, R3}를 전부 반납을 먼저 하고, R4 + {R1, R2, R3}를 전부 할당받을 수 있게 된다면 다시 시작된다. 한마디로 (요청한 자원 + 원래 자원)을 전부 할당받아야 재시작된다
- 만약 A가 {R1, R2, R3}를 반납했는데 다른 프로세스가 {R1, R2, R3}중 몇개를 선점해놓았다면 그 프로세스에게 할당 될 것이다
- 따라서 A는 R4만 필요한게 아니라 뺏긴 자원도 다시 받아야 시작이 될 수 있다
하지만 No Preemption을 만족 시키지 않기 위해서는 일단 "context switch가 간단하게 되는 자원(CPU / DB)"한테만 적용되는 사항이다
그리고 일반적으로 Mutex Lock이나 Semaphore같은 자원에는 적용될 수 없다
Hold & Wait 만족 X
Hold & Wait를 만족시키지 않으려면 "프로세스는 자원을 요청할 때 어떠한 자원도 보유해서는 안된다"가 보장되어야 한다
>> 아예 시작할 때 모든 자원을 전부 할당받자
이렇게 하면 이미 모든 자원을 가졌기 때문에 wait를 할 필요가 없다
하지만 이러한 방식은 2가지 문제점이 존재한다
1. 자원 이용률 ↓
프로세스는 각 시점마다 필요한 자원이 다르다. 따라서 이렇게 미리 모든 자원을 할당받게 되면 결국 안쓰는 자원이 반드시 존재할 것이고 이에 따라서 자원의 효율성이 감소하게 된다
예를 들어서 Mutex Lock과 같은 자원은 굉장히 짧은 시간만 필요한 경우가 있기 때문에 Mutex Lock이란 자원은 낭비가 될 것이다
2. Starvation
프로세스가 굉장히 인기가 많은 자원을 시작할때부터 할당받으려고 대기한다면 다른 우선순위 높은 프로세스들에 의해서 "영원히 대기"할 수도 있다
따라서 Starvation문제가 발생한다
Circular Wait 만족 X
"모든 자원 유형에 순서를 매겨서 반드시 정해진 순서대로 자원을 할당받도록 해주기"
먼저 Total Ordering과 Partial Ordering의 차이를 보게 되면
Total Ordering은 모든 원소간에 크고 작음을 판단할 수 있다
Partial Ordering은 일부의 원소들간에만 크고 작음을 판단할 수 있다
우리는 일단 모든 자원에 대해서 Total Ordering Generation Function :: F를 부여해준다
자원은 {Printer, Tape, Disk}가 있고 각각에 F를 부여한다면
F(Printer) = 5
F(Tape) = 10
F(Disk) = 20
여기서 Circular Wait를 만족 시키지 않으려면 반드시 Printer → Tape → Disk 순으로 할당을 받아야 한다는 것이다
예를 들어서 프로세스 A가 현재 Tape를 보유한 상태로 Printer를 요청한다면 F(Tape) > F(Printer)이므로 정해진 순서대로 자원을 할당받는 것이 아니다
따라서 프로세스 A가 Printer를 할당받으려면 먼저 Tape를 반납을 하고 Printer를 요청해야 한다
그리고 Printer를 할당받으면 다시 Tape를 요청해야 한다
다른 예를 들어보면 프로세스 B가 아무것도 보유하지 않은 상태로 Disk를 요청한다고 하자
이 때 F(Disk)는 F(Printer) & F(Tape)보다 순서가 나중에 있다
따라서 프로세스 B는 Printer → Tape를 먼저 순서대로 할당 받은 후에야 Disk를 할당받을 수 있다
Circular Wait를 발생시키지 않는 위의 방법을 "위의 방법을 이용해도 Circular Wait가 발생한다"라는 귀류법을 이용해서 증명
이러한 상태에서 Circular Wait가 만약 존재한다면 "Pn → R0"인 Request Edge가 존재할 것이다
근데 Pn은 Rn을 보유한 상태에서 R0를 요청하는 것이기 때문에 F(Rn) < F(R0)일 것이다
이것을 전체적 자원의 대소비교로 표현하면 아래와 같게 될 것이다
이러한 대소는 말이 안되기 때문에 "위의 방법을 이용해도 CIrcular Wait가 발생한다"라는 조건은 성립할 수 없다
※ Deadlock Prevention의 문제점
1. 자원에 대한 이용률이 낮아진다
2. 시스템의 처리율이 감소한다
3. Starvation 문제 발생 가능
>> 현재 시점에 생기지도 않은 데드락에 대해서 너무 많은 제약조건이 존재하기 때문에 이러한 문제점이 발생한다
방법 2) Deadlock Avoidance
이 경우 각 프로세스는 "자원 요청에 대한 추가 정보"를 시스템에 미리 제공함으로써 시스템에서 Deadlock을 미리 예방하는 방법이다
"자원 요청에 대한 추가 정보"는 아래와 같다
- 각 프로세스들이 "최대로 요청할 자원량" : MAX
- 현재 이용 가능 자원량 : Available
- 각 프로세스에게 현재 할당된 자원량 : Allocation
- 각 프로세스 별 추가 요청 가능량 : Need
- 이것은 "MAX - Allocation"을 통해서 계산 가능
Safe State
시스템이 Safe State에 있다면 Deadlock이 발생 X
시스템이 Unsafe State에 있다면 "Deadlock 발생 가능성"이 존재한다
>> "Deadlock Avoidance"는 시스템이 Unsafe State에 들어가지 않음을 보장해줌으로써 Deadlock을 미연에 방지한다
2가지 Deadlock Avoidance Algorithm
일단 Deadlock Avoidance는 각 프로세스별 자원 할당 상태를 동적으로 조사해서 절대로 Circular Wait 조건을 만족시키지 않도록 보장해준다
프로세스에게 자원이 할당될때마다 자원 할당 상태는 변하게 되는데, 이 때 변경된 자원 할당 상태가 Deadlock에 빠질 가능성이 존재한다면 할당 요청을 받아도 할당해주지 않는다
- 자원의 여분이 존재하더라도 "일단 자원 할당해주면 자원 할당 상태가 어떻게 될까"를 미리 계산해서 만약 Deadlock에 빠질 가능성이 있다면 자원 여분이 있어도 할당해주지 않는다
여기서 Deadlock에 빠질 가능성을 판단하는 것은 "Safe State"를 통해서 판단하고 Safe State는 "Safe Sequence"가 하나라도 존재하는지에 의해서 판단된다
Safe Sequence
{P0, P1, P2, ... Pn}이 존재할 경우 Safe Sequence의 경우의 수는 n!이다. 즉, 여러가지 Safe Sequence가 존재할 수 있다.
여기서 Safe Sequence가 하나라도 존재한다면 그 시점에서의 시스템은 Safe State에 있다고 볼 수 있다
## j < i 일 경우 ##
프로세스 i가 어떠한 자원을 요청한다고 가정하자
이 때, "현재 이용 가능 자원" + "{P0, P1, ... P(j)}가 요청한 자원"을 합한 것으로 P(i)가 요청한 자원을 할당해줄 수 있다면 일종의 Safe Sequence라고 볼 수 있다
현재는 할당 가능 자원이 없을지라도, 자원을 할당받은 프로세스는 언젠가는 자원을 반납하게 된다.
이렇게 미래의 요소를 고려해서 현재 프로세스의 자원 요청을 충족시킬 수 있다면 이것은 Circular Wait 조건을 성립하지 않는다고 볼 수 있다
>> 따라서 Deadlock 4가지 조건 중 하나인 Circular Wait 조건을 만족하지 않기 때문에 Deadlock은 발생하지 않는다
(1) 자원의 instance가 하나
Resource Allocation Graph Algorithm을 사용한다
원래 Resource Allocation Graph에는 실선 화살표(Request Edge / Assignment Edge)만 존재한다
하지만 여기서는 점선 화살표(Claim Edge)를 추가적으로 사용한다
"Claim Edge"란 "프로세스가 앞으로 요청할 자원이 무엇인지"를 표시한 화살표이다
현재 자원 A는 프로세스 A에게 할당된 상태이다
그리고 프로세스 B가 자원 A를 요청하고 있다
>> 여기서 프로세스 A가 자원 A를 반납한다면 프로세스 B는 자원 A를 할당받을 수 있을 것이다
프로세스 A, B둘다 언젠가는 자원 B를 요청할 거라는 것이 "점선 화살표(Claim Edge)"를 통해서 표현되고 있다
여기서 프로세스 B가 자원 B를 요청했다고 하자
이 때 자원 B는 아직 아무에게도 할당되지 않았으므로 프로세스 B에게 할당해줄 수 있을 것이다
하지만 시스템에서는 "자원 B를 프로세스 B에게 할당해줌으로써 Deadlock 발생 가능성이 생길까??"를 미리 파악해본다
>> Claim Edge → Request Edge로 변경된 것을 Request Edge → Assignment Edge로 임시 변경해봄으로써 Cycle이 생기나 판별해본다
Assignment Edge로 변경하자마자 바로 Cycle이 생겼다는 사실을 시스템이 파악을 해버렸다
따라서 자원 B는 여분이 있음에도 불구하고 프로세스 B의 자원 B 요청에 대해서 할당을 해주면 Cycle이 생기므로 시스템에서는 프로세스 B의 자원 B 요청에 대해서 거부를 하게 된다
▶ 하지만 프로세스 A가 자원 B를 요청해도 시스템에서 요청에 대한 거부를 할까??
이렇게 프로세스 A가 자원 B에 대해서 요청을 하게 되면 시스템은 위의 과정과 마찬가지로 Request Edge를 임의로 Assignment Edge로 변경함으로써 Cycle이 발생하는지 파악한다
프로세스 A에 대한 요청은 Cycle이 발생하지 않기 때문에 프로세스 A는 자원 B를 할당받을 수 있다
- Cycle 생성 여부를 조사할 때 프로세스의 수가 n이라면 전체적인 생성 여부 조사 시간 복잡도는 O(n2)이 걸린다
이렇게 instance가 하나인 경우에는 Resource Allocation Graph Algorithm으로 Deadlock Avoidance를 할 수 있다
하지만 instance가 여러개인 경우에는 다른 Algorithm으로 Deadlock Avoidance를 해줘야 한다
(2) 자원의 instance가 여러개
자원의 instance가 여러개일 경우 Banker's Algorithm을 사용해야 한다
Banker's Algorithm을 구현하려면 몇가지 자료구조가 필요하다
▶ Max
각 프로세스가 최대로 필요한 자원량
- 프로세스 시작할 때 미리 시스템에 알려주어야 하는 자료구조이다
▶ Allocation
현재 각 프로세스들에게 할당된 자원량
▶ Available
현재 시스템 상에서 각 자원 종류별 할당 가능한 양
▶ Need
각 프로세스가 향후에 요청할 수 있는 자원량
- 각 프로세스별로 "Max - Allocation"'으로 구한다
그리고 Banker's Algorithm에서 1) 자원 요청에 대해서 허용 가능한가 & 2) 요청에 대해서 할당해주면 시스템이 안전한가를 판별하는 알고리즘 2개가 존재한다
- 먼저 자원 요청 알고리즘을 검사하고 통과하면 안전성 알고리즘을 검사한다
1) 자원 요청 알고리즘 : Resource-Request Algorithm
2) 안전성 알고리즘 : Safety Algorithm
일반적으로 어느 프로세스도 요청을 하지 않은 상태에서 현재 시스템이 안전한지 확인하고 싶으면 그냥 2)만 수행해주면 된다
Banker's Algorithm Example 1) 시스템 Safe State 확인
Process : {P0, P1, P2, P3, P4}
Resource : {A=10, B=5, C=7}
현재 각 프로세스별 자원 할당 정보는 위의 표와 같다
여기서 현재 시스템이 Safe State인지 "안전성 알고리즘"을 통해서 검증해보자
Work = Available = (3, 3, 2)
boolean [] check = new boolean[process.length];| Allocation(i) | Need(i) | check[i] | Work | |
| P0 | (0, 1, 0) | (7, 4, 3) | false | (3, 3, 2) |
| P1 | (2, 0, 0) | (1, 2, 2) | false | |
| P2 | (3, 0, 2) | (6, 0, 0) | false | |
| P3 | (2, 1, 1) | (0, 1, 1) | false | |
| P4 | (0, 0, 2) | (4, 3, 1) | false |
Case 1)
Step 1의 두 조건을 만족하는 i 찾기
check[i] = false;
Need(i) ≤ Work
>> P(1)이 해당 조건에 맞는다
Step 2 수행
Work += Allocation(i)
check[i] = true
| Allocation(i) | Need(i) | check[i] | Work | |
| P0 | (0, 1, 0) | (7, 4, 3) | false | (3, 3, 2) ↓ (5, 3, 2) |
| P2 | (3, 0, 2) | (6, 0, 0) | false | |
| P3 | (2, 1, 1) | (0, 1, 1) | false | |
| P4 | (0, 0, 2) | (4, 3, 1) | false |
>> Step 1, 2를 계속 반복해서 Safe Sequence를 찾아준다
Case 2)
Step 1의 두 조건을 만족하는 i 찾기
>> P3
Step 2 수행
| Allocation(i) | Need(i) | check[i] | Work | |
| P0 | (0, 1, 0) | (7, 4, 3) | false | (5, 3, 2) ↓ (7, 4, 3) |
| P2 | (3, 0, 2) | (6, 0, 0) | false | |
| P4 | (0, 0, 2) | (4, 3, 1) | false |
Case 3)
Step 1의 두 조건을 만족하는 i 찾기
>> P0
Step 2 수행
| Allocation(i) | Need(i) | check[i] | Work | |
| (7, 4, 3) ↓ (7, 5, 3) |
||||
| P2 | (3, 0, 2) | (6, 0, 0) | false | |
| P4 | (0, 0, 2) | (4, 3, 1) | false |
Case 4)
Step 1의 두 조건을 만족하는 i 찾기
>> P2
Step 2 수행
| Allocation(i) | Need(i) | check[i] | Work | |
| (7, 5, 3) ↓ (10, 5, 5) |
||||
| P4 | (0, 0, 2) | (4, 3, 1) | false |
Case 5)
Step 1의 두 조건을 만족하는 i 찾기
>> P4
Step 2 수행
| Allocation(i) | Need(i) | check[i] | Work | |
| (10, 5, 5) ↓ (10, 5, 7) |
||||
Case 5)
Step 1의 두 조건을 만족하는 i 찾기
>> 이 조건에 만족하는 i가 없기 때문에 Step 3으로 넘어가기
Step 3 : 모든 i에 대해서 check[i] == true인지 확인
>> 참이다
따라서 여기서 Safe Sequence : <P1, P3, P0, P2, P4>를 찾아냄으로써 현재 시스템은 Safe State이다
Banker's Algorithm Example 2) 프로세스의 자원 요청
여기서 P1이 Resource(1, 0, 2)를 요청했다고 하자
이러면 일단 "자원 요청 알고리즘"을 돌려보고 통과하면 "안전성 알고리즘"을 돌려야 한다
1. 자원 요청 알고리즘
Step 1) 먼저 Request ≤ Need인지 확인
(1, 0, 2) ≤ (1, 2, 2)이므로 True
Step 2) Request ≤ Available인지 확인
(1, 0, 2) ≤ (3, 3, 2)이므로 True
>> 이제 "안전성 알고리즘"을 돌려야 한다
- 요청에 대한 안전성 알고리즘을 돌릴때는 "프로세스 요청량"을 임시로 Allocation에 적용하고 돌려야 한다
- 요청량에 따라서 P1의 Allocation & Available & Need가 변경되었다
2. 안전성 알고리즘
| Allocation(i) | Need(i) | check[i] | Work | |
| P0 | (0, 1, 0) | (7, 4, 3) | false | (2, 3, 0) |
| P1 | (3, 0, 2) | (0, 2, 0) | false | |
| P2 | (3, 0, 2) | (6, 0, 0) | false | |
| P3 | (2, 1, 1) | (0, 1, 1) | false | |
| P4 | (0, 0, 2) | (4, 3, 1) | false |
| Allocation(i) | Need(i) | check[i] | Work | |
| P0 | (0, 1, 0) | (7, 4, 3) | false | (2, 3, 0) ↓ (5, 3, 2) |
| P2 | (3, 0, 2) | (6, 0, 0) | false | |
| P3 | (2, 1, 1) | (0, 1, 1) | false | |
| P4 | (0, 0, 2) | (4, 3, 1) | false |
| Allocation(i) | Need(i) | check[i] | Work | |
| P0 | (0, 1, 0) | (7, 4, 3) | false | (5, 3, 2) ↓ (7, 4, 3) |
| P2 | (3, 0, 2) | (6, 0, 0) | false | |
| P4 | (0, 0, 2) | (4, 3, 1) | false |
| Allocation(i) | Need(i) | check[i] | Work | |
| (7, 4, 3) ↓ (7, 5, 3) |
||||
| P2 | (3, 0, 2) | (6, 0, 0) | false | |
| P4 | (0, 0, 2) | (4, 3, 1) | false |
| Allocation(i) | Need(i) | check[i] | Work | |
| (7, 5, 3) ↓ (10, 5, 5) |
||||
| P4 | (0, 0, 2) | (4, 3, 1) | false |
| Allocation(i) | Need(i) | check[i] | Work | |
| (10, 5, 5) ↓ (10, 5, 7) |
||||
>> Safe Sequence <P1, P3, P0, P2, P4>가 존재하므로 P1의 Request인 (1, 0, 2)를 그대로 할당해준다
Banker's Algorithm Example 3) 프로세스의 자원 요청
위의 상태에서 P4가 (3, 3, 0)을 요청했다고 하자
1. 자원 요청 알고리즘
Step 1) 먼저 Request ≤ Need인지 확인
(3, 3, 0) ≤ (4, 3, 1)이므로 True
Step 2) Request ≤ Available인지 확인
(3, 3, 0) ≤ (2, 3, 0)이므로 False
>> 따라서 P4의 자원 요청은 "자원 요청 알고리즘"에서 통과하지 못했기 때문에 P4는 (3, 3, 0)을 얻을때까지 대기하게 된다
Banker's Algorithm Example 4) 프로세스의 자원 요청
위의 상태에서 P0이 (0, 2, 0)을 요청했다고 하자
1. 자원 요청 알고리즘
Step 1) 먼저 Request ≤ Need인지 확인
(0, 2, 0) ≤ (7, 4, 3)이므로 True
Step 2) Request ≤ Available인지 확인
(0, 2, 0) ≤ (2, 3, 0)이므로 True
>> 이제 "안전성 알고리즘"을 돌려야 한다
- 요청에 대한 안전성 알고리즘을 돌릴때는 "프로세스 요청량"을 임시로 Allocation에 적용하고 돌려야 한다
2. 안전성 알고리즘
| Allocation(i) | Need(i) | check[i] | Work | |
| P0 | (0, 3, 0) | (7, 2, 3) | false | (2, 1, 0) |
| P1 | (3, 0, 2) | (0, 2, 0) | false | |
| P2 | (3, 0, 2) | (6, 0, 0) | false | |
| P3 | (2, 1, 1) | (0, 1, 1) | false | |
| P4 | (0, 0, 2) | (4, 3, 1) | false |
>> Need(i) ≤ Work를 만족시키는 어느 i도 존재하지 않기 때문에 "안전성 알고리즘의 Step 3)"로 이동한다
Step 3 : 모든 i에 대해서 check[i] == true인지 확인
>> 없다
따라서 P0의 Request(0, 2, 0)는 "안전성 알고리즘"을 통과하지 못했기 때문에 자원 할당 상태는 이전으로 돌아가게 되고 P0는 (0, 2, 0)을 할당받을 때까지 대기하게 된다
Banker's Algorithm Example 5) 연습문제 8.3
(a) 현재 시스템이 안전한지 먼저 확인 >> "안전성 알고리즘"
| Allocation(i) | Need(i) | check[i] | Work | |
| P0 | (0, 0, 1, 2) | (0, 0, 0, 0) | false | (1, 5, 2, 0) |
| P1 | (1, 0, 0, 0) | (0, 7, 5, 0) | false | |
| P2 | (1, 3, 5, 4) | (1, 0, 0, 2) | false | |
| P3 | (0, 6, 3, 2) | (0, 0, 2, 0) | false | |
| P4 | (0, 0, 1, 4) | (0, 6, 4, 2) | false |
| Allocation(i) | Need(i) | check[i] | Work | |
| (1, 5, 2, 0) ↓ (1, 5, 3, 2) |
||||
| P1 | (1, 0, 0, 0) | (0, 7, 5, 0) | false | |
| P2 | (1, 3, 5, 4) | (1, 0, 0, 2) | false | |
| P3 | (0, 6, 3, 2) | (0, 0, 2, 0) | false | |
| P4 | (0, 0, 1, 4) | (0, 6, 4, 2) | false |
| Allocation(i) | Need(i) | check[i] | Work | |
| (1, 5, 3, 2) ↓ (2, 8, 8, 6) |
||||
| P1 | (1, 0, 0, 0) | (0, 7, 5, 0) | false | |
| P3 | (0, 6, 3, 2) | (0, 0, 2, 0) | false | |
| P4 | (0, 0, 1, 4) | (0, 6, 4, 2) | false |
| Allocation(i) | Need(i) | check[i] | Work | |
| (2, 8, 8, 6) ↓ (3, 8, 8, 6) |
||||
| P3 | (0, 6, 3, 2) | (0, 0, 2, 0) | false | |
| P4 | (0, 0, 1, 4) | (0, 6, 4, 2) | false |
| Allocation(i) | Need(i) | check[i] | Work | |
| (3, 8, 8, 6) ↓ (3, 14, 11, 8) |
||||
| P4 | (0, 0, 1, 4) | (0, 6, 4, 2) | false |
| Allocation(i) | Need(i) | check[i] | Work | |
| (3, 14, 11, 8) ↓ (3, 14, 12, 12) |
||||
>> Safe Sequence <P0, P2, P1, P3, P4>가 존재하므로 현재 시스템은 Safe State이다
(b) P1이 (0, 4, 2, 0)을 요청했을 경우
1. "자원 요청 알고리즘"
Step 1) 먼저 Request ≤ Need인지 확인
(0, 4, 2, 0) ≤ (0, 7, 5, 0)이므로 True
Step 2) Request ≤ Available인지 확인
(0, 4, 2, 0) ≤ (1, 5, 2, 0)이므로 True
>> 이제 "안전성 알고리즘"을 돌려야 한다
- 요청에 대한 안전성 알고리즘을 돌릴때는 "프로세스 요청량"을 임시로 Allocation에 적용하고 돌려야 한다
2. 안전성 알고리즘
| Allocation(i) | Need(i) | check[i] | Work | |
| P0 | (0, 0, 1, 2) | (0, 0, 0, 0) | false | (1, 1, 0, 0) |
| P1 | (1, 4, 2, 0) | (0, 3, 3, 0) | false | |
| P2 | (1, 3, 5, 4) | (1, 0, 0, 2) | false | |
| P3 | (0, 6, 3, 2) | (0, 0, 2, 0) | false | |
| P4 | (0, 0, 1, 4) | (0, 6, 4, 2) | false |
| Allocation(i) | Need(i) | check[i] | Work | |
| (1, 1, 0, 0) ↓ (1, 1, 1, 2) |
||||
| P1 | (1, 4, 2, 0) | (0, 3, 3, 0) | false | |
| P2 | (1, 3, 5, 4) | (1, 0, 0, 2) | false | |
| P3 | (0, 6, 3, 2) | (0, 0, 2, 0) | false | |
| P4 | (0, 0, 1, 4) | (0, 6, 4, 2) | false |
| Allocation(i) | Need(i) | check[i] | Work | |
| (1, 1, 1, 2) ↓ (2, 4, 6, 6) |
||||
| P1 | (1, 4, 2, 0) | (0, 3, 3, 0) | false | |
| P3 | (0, 6, 3, 2) | (0, 0, 2, 0) | false | |
| P4 | (0, 0, 1, 4) | (0, 6, 4, 2) | false |
| Allocation(i) | Need(i) | check[i] | Work | |
| (2, 4, 6, 6) ↓ (3, 8, 8, 6) |
||||
| P3 | (0, 6, 3, 2) | (0, 0, 2, 0) | false | |
| P4 | (0, 0, 1, 4) | (0, 6, 4, 2) | false |
| Allocation(i) | Need(i) | check[i] | Work | |
| (3, 8, 8, 6) ↓ (3, 14, 11, 8) |
||||
| P4 | (0, 0, 1, 4) | (0, 6, 4, 2) | false |
| Allocation(i) | Need(i) | check[i] | Work | |
| (3, 14, 11, 8) ↓ (3, 14, 12, 12) |
||||
>> Safe Sequence <P0, P2, P1, P3, P4>가 존재하므로 P1의 Request(0, 4, 2, 0)을 그대로 할당해준다
방법 3) Deadlock Detection & Recovery
Deadlock Detection
▶ 자원당 instance가 하나인 경우
Resource-Allocation Graph를 사용해서 Deadlock Detection이 가능하다
- Cycle이 존재한다면 Deadlock도 존재
RA-G에는 Deadlock Avoidance에서처럼 각 자원별로 향후에 요청하는 "Claim Edge"가 존재하지 않는다
그리고 어차피 Deadlock Detection만 하기 때문에 Resource-Allocation Graph에는 "프로세스들 간의 연결"만 표시되면 된다
>> "프로세스 간의 연결"만 표시한 그래프를 "Wait-For Graph"라고 한다
instance가 1개인 경우 Deadlock Detection Algorithm의 Time-Complexity는 O(m × n)이다
▶ 자원당 instance가 여러개인 경우
Banker's Algorithm과 유사한 방법으로 Deadlock Detection이 가능하다
>> Banker's Algorithm의 "안전성 알고리즘"을 응용해서 Detection하면 된다
- Deadlock Detection & Recovery는 Deadlock Avoidance와는 다르게 프로세스가 시스템에게 미리 최대 자원 사용량을 알리지 않는다
- 따라서 Detection Algorithm에서는 MAX - Allocation에 따른 Need를 쓰는게 아니라 Need대신에 각 프로세스의 Request를 표에 적용해서 사용한다
instance가 여러개인 경우 Deadlock Detection Algorithm의 Time-Complexity는 O(m × n2)이다
| Allocation(i) | Request(i) | check[i] | Work | |
| P0 | (0, 1, 0) | (0, 0, 0) | false | (0, 0, 0) |
| P1 | (2, 0, 0) | (2, 0, 2) | false | |
| P2 | (3, 0, 3) | (0, 0, 0) | false | |
| P3 | (2, 1, 1) | (1, 0, 0) | false | |
| P4 | (0, 0, 2) | (0, 0, 2) | false |
Detection Algorithm의 결과 <P0, P2, P1, P3, P4>가 존재하므로 현재 시스템은 데드락 상태가 아니다
하지만 여기서 P2가 (0, 0, 1)을 Request했다고 하자
| Allocation(i) | Request(i) | check[i] | Work | |
| P0 | (0, 1, 0) | (0, 0, 0) | false | (0, 0, 0) |
| P1 | (2, 0, 0) | (2, 0, 2) | false | |
| P2 | (3, 0, 3) | (0, 0, 1) | false | |
| P3 | (2, 1, 1) | (1, 0, 0) | false | |
| P4 | (0, 0, 2) | (0, 0, 2) | false |
| Allocation(i) | Request(i) | check[i] | Work | |
| (0, 0, 0) ↓ (0, 1, 0) |
||||
| P1 | (2, 0, 0) | (2, 0, 2) | false | |
| P2 | (3, 0, 3) | (0, 0, 1) | false | |
| P3 | (2, 1, 1) | (1, 0, 0) | false | |
| P4 | (0, 0, 2) | (0, 0, 2) | false |
여기서 Detection Algorithm은 종료된다 :: Request(i) ≤ Work인 프로세스가 더이상 존재 X
따라서 check[i] == false인 {P1, P2, P3, P4}는 데드락과 연관된 프로세스이고 현재 시스템은 데드락 상태이다
Deadlock Detection을 하면 이제 Recovery를 해야 한다
Recovery 1) Process Termination (프로세스 죽이기)
(1) 데드락과 관련된 모든 프로세스들 죽이기
이 방법은 확실히 Deadlock Cycle을 깨뜨릴 수 있는 방법이지만, 비용이 굉장히 많이 발생한다
왜냐하면 Deadlock에 연루된 프로세스가 어떠한 연산을 굉장히 오래 수행한 경우, 그 연산에 대한 부분 결과들을 전부 flush해야 하고 나중에 다시 계산해야 하기 때문이다
(2) 데드락이 없어질때까지 데드락과 관련된 프로세스 하나씩 죽여보기
이 방법은 프로세스를 하나씩 죽일때마다 Deadlock Detection Algorithm을 호출해서 프로세스들이 아직도 Deadlock인지 파악해야 하기 때문에 매우 큰 오버헤드를 유발한다
따라서 Recovery 1)의 방법은 어느 프로세스를 죽일지 결정할 때 다음 요인들을 고려해야 한다
- 프로세스들간의 우선순위
- 지금까지 프로세스가 수행한 시간 & 남은 CPU Burst Time
- 프로세스가 사용한 자원의 유형과 수 (자원들을 선점할 때 쉽게 선점할 수 있는지 여부)
- 프로세스가 종료하기 위해 더 필요한 자원의 수
- 얼마나 많은 수의 프로세스가 종료되어야 하는지
Recovery 2) Resource Preemption (자원 빼앗기)
자원 선점을 통해서 Deadlock을 제거하려면, Deadlock이 깨질때까지 프로세스로부터 계속 자원을 선점해서 선점된 자원을 다른 프로세스에게 줘야 한다
따라서 데드락과 연관된 프로세스들 중에서 "비용상으로 가장 손해가 없을 만한 프로세스의 자원"을 빼앗아야 한다
자원을 빼앗는 경우 다음 3가지 사항을 고려해야 한다
(1) 자원 빼앗길 프로세스(희생자) 선택
위에서 말한것처럼, "비용상으로 가장 손해가 없을만한 프로세스의 자원"을 빼앗아야 한다
- Deadlock 프로세스들이 점유하고 있는 자원의 수
- Deadlock 프로세스들이 지금까지 실행하는 데 소요한 시간
- etc...
이러한 요소들을 고려해서 빼앗으면 된다
(2) Rollback
어느 한 프로세스로부터 자원을 빼앗게 된다면 그 프로세스는 더이상 정상적으로 실행할 수 없을 것이다
- 필요한 자원을 빼앗겼기 때문에
따라서 해당 프로세스를 Safe State로 Rollback시키고 그 상태부터 다시 시작해야 한다
여기서 프로세스의 Safe State가 무엇인지 결정하는 것은 쉽지 않다
▶ 단순한 해결안은 해당 프로세스의 실행 상태를 전부 Rollback하는 것이다
한마디로 해당 프로세스를 중지시키고 재시작한다
굳이 전부 Rollback시키지 않고 Deadlock을 깨뜨릴 정도로만 Rollback시키는게 더 효율적일 것이다
하지만 일정 부분만 Rollback시키려면 모든 프로세스의 상태에 대한 더 많은 정보가 필요하다
(3) Starvation
운이 나쁘게 하나의 프로세스한테만 계속 자원을 빼앗게 된다면??
그 프로세스는 영원히 필요한 자원이 없게 되어서 결국 Starvation 문제가 발생할 것이다
따라서 Cost Factor에 Rollback의 횟수 제한도 같이 고려를 해줘야 한다
방법 4) Deadlock Ignorance
이 방법은 Deadlock이 발생하든 발생하지 않든 시스템에서 Deadlock을 신경을 아예 쓰지 않음으로써 Deadlock에 관한 조치를 하지 않는 방법이다
현대 OS에서 이러한 방법을 쓰는 이유는 일단 데드락은 굉장히 드물게 발생한다
드물게 발생하는 데드락에 대해서 위의 여러 방법처럼 제약조건을 미리 걸어버리면 발생한 데드락에 대한 조치를 취할 때 더 큰 overhead가 발생할 수 ㅣㅇㅆ다
따라서 4)의 경우 Deadlock이 발생하면 user가 직접 Deadlock이 발생한 프로세스를 kill하도록 설계하였다
