Chapter 6-1. Concurrency : Deadlock and Starvation

deadlock을 아예 발생시키지 않으면 좋지만, deadlock을 막을 수 없는 경우가 존재한다.
⇒ OS가 deadlock을 막아줘야 한다.

Deadlock 정의

A set of processes is deadlocked when each process in the set is blocked awaiting an event that can only be triggered by another blocked process in the set.

• Deadlock 이 발생하기 위해서는 최소한 둘 이상의 프로세스가 필요하다.
• block 이 되어야 한다. (프로세스가 멈추지 않고 실행하고 있으면 deadlock이 아니다.)
• block 이 되었다고 해서 무조건 deadlock은 아니다.
  ↳ block 이 존재하면 이 block 을 깨워줄 이벤트가 존재한다.
• ex) semWait(s), semSignal(s), ...
• 한 프로세스가 block 이 되고, 그 이벤트를 해 줄 프로세스가 같이 block 된 것을 deadlock 이라고 한다. ⇒ 영영 deadlock 상태에서 빠져나올 수 없다.

즉, deadlock 의 조건은 두 가지이다.

1. 최소 두 개 이상의 프로세스가 block 상태이다.
2. block 상태에서 빼 줄 수 있는 이벤트를 실행하는 프로세스가 같이 block 이 되는 상황이다.

Deadlock 예시

• s1과 s2가 전부 초기값이 1이다.

Process A	Process B
semWait(s1) ⇒ s1값: 1 → 0 ⇒ Timeout
	semWait(s2) ⇒ s2값: 1 → 0
	semWait(s1) ⇒ s1값: 0 → -1 ⇒ Process B Block
semWait(s2) ⇒ s2값: 0 → -1 ⇒ Process A Block

이 block 상태를 해결하려면 서로의 프로세스가 semSignal()을 해주어야 하는데 semSignal() 를 줄 프로세스가 같이 block됐기 때문에 block 상태에서 아무도 빠져나올 수 없다.
⇒ 두 프로세스가 Deadlock에 빠졌다.

---

Deadlock 발생 조건 네가지

다음의 네가지 조건을 모두 만족해야 Dealock 이 발생한다.

1. Mutual Exclusion

only one process may use a resource at a time.

한번에 하나의 프로세스만 자원을 사용할 수 있어서 Dealock 이 발생한다.

2. Hold-and-Wait

a process may hold allocated resources while awaiting assignment of others.

다들 자신의 자원을 1개 이상 가지고 있고, 다른 프로세스에게 자원을 하나 이상 요청할 때 Dealock 이 발생한다.
만약 자원을 가지고 있지 않거나, 자원을 요청하지 않으면 Dealock 이 발생하지 않는다.

Process A: s1 통과 O, s2 통과 X
Process B: s2 통과 O, s1 통과 X

3. No Preemption

no resource can be forcibly removed from a process holding it.

할당된 resource를 강제로 빼앗지 못하기 때문에 Dealock 이 발생한다.

semaphore 값을 0 → 1로 강제로 바꿀 수 없다.

4. Circular Wait

a closed chain of processes exists, such that each process holds at least one resource needed by the next process in the chain.

Process 1: 자원 A를 가짐 & Process 2 에게 자원 B 요청 
Process 2: 자원 B를 가짐 & Process 1 에게 자원 A 요청

                        Process 1
                            ↑ ↓   (cricular)
                        Process 2

---

Resource Allocation Graphs

OS는 프로세스가 시스템 안에서 자원을 요청하고 할당받는 사이에 이와 같은 Cricular Wait가 발생하는지 알아보기 위해 Resource Allocation Graph를 그릴 수 있다.

ex) semaphore 의 값이 5라면, 네모 안에 ● 은 5개 존재하게 된다.

오른쪽의 그림은 사이클이 있는 것처럼 보이지만 사이클이 존재하지 않는다.
Ra 타입 자원이 한 개가 아니라 3개이기 때문에,
OS가 요청을 받아주면, P1에게도 자원이 할당될 수 있다.

위와 같은 Resource Allocation Graph 는 드물다.
보통 사이클은 두 프로세스 사이에서 주로 나타난다.

P1과 P2 사이에서 사이클이 발생해 Deadlock이 발생한다.
P1과 P2가 원래 가지고 있던 자원이 존재하고, 이 자원들을 필요로 하는 프로세스들이 존재한다. 이와 같이 P1과 P2에 엮인 나머지 Process들이 존재한다.

P1과 P2에 엮인 나머지 Process 들은 Deadlock 과 관련이 없지만, P1과 P2와 관련이 있어 block이 되어 시스템이 정지되게 된다. ⇒ 심각

---

Dealing with Deadlock

Deadlock을 해결하는 3가지 방법이 존재한다.

1. Prevent Deadlock

방지
→ 자원 할당 과정에서
다음의 시점에 미리 규칙을 세워둔다.

• 자원 요청 시점
• 자원 할당 시점
• 자원 할당이 거절 됐을 때 어떻게 할 것인지 하는 것 까지

2. Avoid Deadlock

회피
→ 자원 요청
→ OS가 검사
↳ 자원을 할당해 줬을 때, Deadlock이 발생하는지 검사 후 발생하지 않으면
자원 할당 O, 발생하면 자원 할당 X

3. Detect Deadlock

1번 Prevent Deadlock 과 2번 Avoid Deadlock 은 Deadlock 발생 자체를 방지한다면, 3번 Detect Deadlock 은 시스템에서 Deadlock 이 발생하는 건 일단 방치 한다.
그렇기 때문에 제일 비용적으로 좋다.

대신 빠르게 감지하고 Deadlock 이 발생한 두 프로세스를 중지시킨다.
→ 나머지 프로세스들은 정상적으로 작동한다.
⇒ 전체 시스템은 정상적으로 작동한다.

---

Deadlock Prevention Strategy

Deadlock 을 발생시키는 4가지 조건 중 어느 한 조건을 만족하지 않는 상황을 만든다.
단, Mutual Exclusion은 무조건 지켜져야 한다.
↳ 나머지 조건을 방지하는 방식으로

Design a system in such a way that the possibility of deadlock is excluded.

Mutual Exclusion

Mutual Exclusion 은 무조건 지켜져야 한다.

Hold and Wait

Require a process request all of its required resources at one time.

Hold와 Wait를 동시에 만족해야 Deadlock 이 발생하기 때문에 Hold가 안되게 한다.

• 처음 프로세스 실행 → 필요한 자원 한번에 요청 → OS가 자원을 한번에 줄 수 있으면 준다. → 자원을 Hold만 한다. Wait 하지 않는다.
  ↳ Q. 애초에 필요한 자원은 어떻게 알 수 있지?
  → Compiler가 이미 프로그램 전체를 프로세스로 만들기 위해 훑기 때문에 자원을 파악하는데는 문제가 없다.
• 자원 준비가 다 안됐을 경우 (5개 중 4개만 준비) ⇒ block
  → 나중에 1개가 가능해도, 다른게 다시 준비가 안될 경우가 있기 때문에 다시 block 될 수 있는데 결국 Starvation 문제를 유발할 수 있다.

이론적으로 시스템에 적용할 수 없다.

No Preemption

• Process must release resource and request again.
• OS may preempt a process to require it releases its resources.

자원을 뺏는다.

자원을 바로 뺏을 수 없기 때문에, 만약, OS가 모종의 이유로 일정 시간 동안 자원을 할당하지 않으면,
해당 프로세스가 가진 자원을 전부 뺏고, 처음부터 다시 시작한다.

이론적으로 시스템에 적용할 수 없다.

Circular Wait

Define a linear ordering of resource types.

Circular Wait를 방지한다.

모든 자원에 정수 번호를 붙인다. 번호순으로 자원을 요청한다.

필요한 자원요청 자원

1	1
2	2
3	3

↑ 위와 같이가 아니라 밑에와 ↓ 같이 요청한다.

필요한 자원요청 자원

1	1
2	1 → 2 (1먼저 요청)
3	1 → 2 →3 (1과 2 먼저 요청)

즉, 내가 필요한 자원의 순서대로가 아니라, 번호 순서대로 요청해야 하기 때문에 필요 없는 자원도 요청하게 될 수 있어 자원 낭비의 가능성이 존재하게 된다.

이론적으로 시스템에 적용할 수 있다.

Q. 정말 이렇게 하면 Deadlock이 방지 될 수 있을까? (증명)

Cycle이 생기려면 회색 박스의 두 상황을 동시에 만족해야하는데,
불가능한 상황이기 때문에 모순이 발생한다.

R1의 수와 R2의 수가 동시에 서로에게 클 수 없다.

---

Deadlock Avoidance

Process가 자원을 요청하거나 실행을 시도할 때, OS가 시작을 해도 좋겠다 혹은 보류해야겠다 또는 이 자원을 할당해도 좋겠다 혹은 보류해야겠다 등의 결정을 계속 하는 것.
(당연히 Deadlock이 발생하지 않는 방식으로 결정해야 한다.)

가정: 프로세스가 얼마나의 자원을 요청할지 미리 알고 있어야 한다.

A decision is made dynamically whether the current resource allocation request will, if granted, potentially lead to a deadlock.

Requires knowledge of future process requests.

---

Two Approaches to Deadlock Avoidance

1. Process Initiation Denial

Do not start a process if its demands might lead to
deadlock.

프로세스가 실행을 시작할 때 실행을 시킬지 말지를 결정하는 방식.

2. Resource Allocation Denial

Do not grant an incremental resource request to a process if this allocation might lead to deadlock.

리소스를 달라고 요청했을 때, 리소스를 줄지 말지를 결정하는 방식.

---

Process Initiation Denial Deadlock Avoidance

A process is only started if the maximum claim of all current processes plus those of the new process can be met.
↳ 프로세스가 자신이 필요한 자원 최대를 OS에게 미리 보고 → OS가 검사 → 내가(OS) 가진 Resource를 Process들이 전부 사용해도 부족한지, 안부족한지 검사한다.
⇒ Optimal 하지 않다.

Process1과 Process2가 위와 같이 자원을 원하고, 겹치는 자원을 겹치는 시간대에 요구하지 않아도, OS는 둘 중하나만 실행한다.
⇒ Optimal 하지 않다.

Not Optimal

Assumes the worst that all processes will make their maximum claims together.

---

Determination of Safe State (Process Initiation Denial)

Claim matrix : 지금 이 시스템에는 R1, R2, R3 세가지 타입의 자원이 있다.
각 프로세스가 나는 각 타입의 자원을 몇개를 쓸거다 라고 하는 자원 사용의 최대치를 말한다.

P1, P2, P3, P4이 동시에 도착한 것이 아니라 P1 → P2 → P3 → P4 의 순으로 순서대로 도착했다.

Resource Vector R : 시스템이 가진 리소스의 개수

P1, P2 는 실행을 시작할 수 있지만, P3는 실행을 시작하지 못한다 (Block).

---

Resource Allocation Denial Deadlock Avoidance

가장 구현 가능성이 높다.

banker’s algorithm

Referred to as the banker’s algorithm.

↳ banker’s algorithm 이라고 불린다.

프로세스 실행 → 자원을 요청 → OS가 자원을 줄 수도, 안줄 수도 있다.

가정: 시스템 안에서 리소스 개수는 변하지 않는다.

Consider a system with fixed number of resources.

• State of the system is the current allocation of resources to process.
• Safe state is where there is at least one sequence that does not result in deadlock.
• Unsafe state is a state that is not safe.

시스템의 상태 정의

현재 이시각, 프로세스에 자원이 몇개씩 할당되는가?

safe

safe : 현재시스템 상태에서 지금 실행하고 있는 프로세스들을 deadlock에 걸리지 않고, 무사하게 실행시킬 수 있는 시퀀스가 존재하는 상태.

unsafe

unsafe : 지금 상태는 deadlock은 아니지만, 어떤 순서로 실행하던 결국 deadlock이 발생하게 되는 상태.

---

Determination of Safe State (Deadlock Avoidance)

A system consisting of four processes and three resources.

Claim matrix : 각각의 프로세스들이 자원을 최대 얼마나 요구할것이다라고 하는 것

Allocation matrix : 현시점에서 각각의 프로세스들이 자원을 얼마나 할당 받았나 라고 하는 것

Resource Vector R : 시스템이 가진 리소스의 개수

Claim-Allocation : C - A, Claim matrix에서 Allocation matrix를 뺀 값이다. 즉, 각각의 프로세스들이 앞으로 더 요청할 자원의 최대치를 의미한다.

Available vector : 프로세스들에게 할당하고 남은, 시스템 안에 남아 있는 자원

Is this a safe state?

→ Deadlock 없이 Process들이 무사히 종료할 수 있는가?
↳ 누가 종료가 가능한지를 따져봐야 한다.

제일 먼저 누가 종료 가능? → P2가 제일 먼저 종료할 수 있다.

종료할 수 있다의 의미: 지금 현재 남아있는 자원인 Available vector에 있는 자원을 전부 주면 종료할 수 있다는 의미이다.

즉, C-A <= Available vector (C-A의 값이 Available vector의 값보다 작거나 같으면 된다,)

⇒ P2가 먼저 무사히 종료가능하다. ↔ P1, P3, P4는 종료 불가능
⇒ P2가 먼저 종료 했다고 가정 → P2에 할당 됐던 자원을 모두 반환.

↳ 다음에 종료할 프로세스? → Banker's Algorithm
⇒ 1번부터 (보통 for문으로 구성되기 때문이다.) ⇒ P1 종료

프로세스가 종료하면 그저 자기가 가지고 있던 자원을 반납한다. (Allocation maxtrix 만큼)

여기서의 state는 초기의 상태, 밑에 ↓ 그림의 상태를 말하며, safe한 것을 알 수 있다.

 

---

Determination of an Unsafe State

초기 상태 (a)에서 P1에게 자원 R1과 R3 (1 0 1)를 할당한다.
남은 Available vector로는 아무것도 종료할 수 없으므로 Unsafe인 것을 알 수 있다.

프로세스 → 자원 요청
↳ OS가 자원을 바로 주는게 아니라, 주었다 치고 상태를 검사한다. (b)처럼
→ safe이면 자원을 할당해주고, unsafe이면 자원할당을 거절한다.
→ (b) 는 unsage였기 때문에 (a)로 다시 환원한다.

Banker's algorithm

자원을 요청할 때마다 OS가 검사를 진행하고 (이 자원을 줬다 가정하고 자원을 준 상태가 safe 상태인지 확인) 자원을 할당할지 말지를 결정하는 것