[OS] DeadLock

✔️ DeadLock ( 교착 상태 )

DeadLock 

◾️ 'DeadLock Example 2'를 살펴보자.

◾️ P0은 A 자원을 가지고 있으면서, B자원을 요구한다.

◾️ P1은 B 자원을 가지고 있으면서, A자원을 요구한다.

◾️ P0과 P1은 DeadLock 상태이다. 

---

✔️ DeadLock 발생의 4가지 조건

◾️ 상호배제, 비선점, 점유대기, 환형대기 4가지 조건을 모두 만족해야 DeadLock이 발생한다.

---

✔️ Resource-Allocation Graph ( 자원 할당 그래프 )

 

Resource-Allocation Graph (1)

◾️ 자원 할당 그래프는 프로세스의 자원 할당 상태를 표현해주는 그래프이다. 

◾️ 동그라미는 프로세스, 네모는 자원을 나타낸다. 네모속의 점은 자원의 인스턴스를 의미한다.

◾️ 프로세스 -> 자원 : 프로세스가 해당 자원을 요청하는 것을 의미한다.

◾️ 자원 -> 프로세스 : 프로세스가 해당 자원을 소유하는 것을 의미한다. 

◾️ 위 Resource-Allocation Graph는 DeadLock인가? 아니다. P3가 작업을 끝마치고 자원 R3를 반납한다면, P2는 R3을 할당 받아 작업을 수행할 수 있다. 다시 한 번 말하자면 DeadLock은 프로세스들이 서로가 가진 자원을 요청하며 대기하는 Blcok 상태이다. 

 

Resource-Allocation Graph (2)

◾️ 자원 할당 그래프에 Cycle이 존재 하지 않으면 DeadLock이 아니다.

◾️ 자원 할당 그래프에 Cycle이 존재 한다면 DeadLock일 수도, 아닐수도 있다. 

◾️ 위 슬라이드의 두 그래프를 살펴보자. 두 그래프 모두 Cycle이 존재하지만, 왼쪽 그래프만 DeadLock이다.

◾️ 오른쪽 그래프는 Cycle를 잘 살펴보자. P2가 자원 R1을 반납합면, P1은 R1을 할당 받아 작업을 수행할 수 있다. 마찬가지로 P4가 자원 R2를 반납하면 P3가 R2를 할당받아 작업을 수행할 수 있다. 따라서 서로가 가진 자원을 요구하면서 무한정 대기하는 DeadLock이 아님을 알 수 있다.

◾️ 왼쪽 그래프는 모든 프로세스가 서로의 자원을 요구하면서 무한정 대기하는 DeadLock임을 알 수 있다. 

---

✔️ DeadLock 처리 방법 4가지

 

◾️ DaedLock 예방(Prevention), 회피(Avoidance)는 DeadLock을 미연에 방지하는 방법이다. 

◾️ DeadLock 발견(Detection and recovery), 무시(lgnorance)는 DeadLock 상황을 허용하고, DeadLock 발생한 후에 후속 처리하는 방법이다. 

◾️ DaedLock 예방(Prevention)은 데드락을 원천적으로 막을 수 있지만 자원이용률이 낮아지고, 성능이 낮아지고, Starvation이 발생할 수 있다. 

◾️ DeadLock 회피(Avoidance)는 보수적으로 자원 할당을 하기 때문에 비효율적이다. 

◾️ DeadLock 발견(Detection and recovery)은 DeackLock을 발견하는 로직에서 시스템 오버헤드가 존재한다. 

◾️ DeadLock은 자주 발생하는 상황이 아니다. 따라서 현재 대부분의 OS는  DeadLock 무시 방법을 채택한다. 

---

1️⃣ 데드락 예방 ( DeadLock Prevention )

◾️ 데드락 예방은 위에서 살펴봤던 데드락 발생 4조건을 위배하여 데드락 발생을 방지하는 것이다.

◾️ Mutual Exclusion : 공유자원을 동시에 여러 프로세스가 사용할 수 있다면 에초에 데드락은 발생하지 않는다. 우리는 여러 프로세스가 동시에 공유자원을 사용할 수 없는 상황을 가정한다. 따라서 이 조건은 위배할 수 없다. 

◾️ Hold and Wait : 프로세스가 자원을 소유하면서 다른 자원을 요청하는 것을 막는다. 프로세스가 시작할 때 필요한 자원을 모두 할당 받게 하거나, 자원을 요청할 경우 현재 보유 자원을 모두 반납하고 다시 모든 자원을 요청하는 방법을 택한다. 

◾️ No Preemption : 자원 선점이 가능하면 DeadLock을 막을 수 있다. DeadLock은 자신이 가진 자원을 내놓지 않으면서 다른 프로세스가 보유한 자원을 요구하는 상황이기 때문이다. 자원 선점이 가능하면 다른 프로세스의 자원을 빼앗아 사용할 수 있다. 

◾️ Circular Wait : 모든 자원에 할당 순서를 정한다. R1, R2를 모두 얻으려면 R1을 먼저얻고 R2를 얻을 수 있다. 이렇게하면 R2를 가지고 있으면서 R1을 요청하는 상황이 발생하지 않는다. 

---

2️⃣ 데드락 회피 ( DeadLock Avoidance )

◾️ DeadLock Avoidance에서는 프로세스가 시작될 때, 최대한으로 사용할 모든 자원을 선언한다. 즉, 프로세스의 최대 자원 요구량을 알 수 있다.

◾️ 데드락 회피는 DeadLock이 발생하지 않도록 보수적으로 자원할당을 하는 것이다. 

◾️ 어떤 프로세스가 자원을 요청했을때 그 프로세스가 요청할 수 있는 최대 자원 요구량보다 현재 가용 자원량이 많을 경우에만 자원을 할당한다. 

 

DeadLock Avoidance (1)

 

DeadLock Avoidance (2)

📌 Avoidance 알고리즘 1 

DeadLock Avoidance ( 자원당 인스턴스가 하나일 경우 ) 

 

◾️ 자원당 인스턴스가 하나일 경우에 쓰는 알고리즘이다. 자원할당 그래프를 사용한다. 

◾️ 가장 오른쪽 그래프에서 P1이 R2을 요청한다면(점선 화살표가 실선으로 바뀜), Cycle이 만들어지고 DaedLock 상황이 된다. 

◾️ 즉, DeadLock을 발생시킬 수 있는 자원 R2에 대한 요청을 받아드리지 않도록 하여 DeadLock을 막는다.

 

📌 Avoidance 알고리즘 2 ( 은행원 알고리즘 )

 

DeadLock Avoidance ( 자원당 인스턴스가 여러개일 경우 ) 

◾️ Allocation : 현재 프로세스에 할당 돼 있는 자원량

◾️ Max : 프로세스가 요구할 수 있는 최대 자원량

◾️ Available : 현재 가용 자원량

◾️ Need : 프로세스가 현재 추가로 요구할 수 있는 자원량 (Max - Allocation)

◾️ P0은 추가적으로 최대 A 7개, B 4개, C 3개를 요청할 수 있다. 

◾️ P1이 A 2개, B 2개, C 2개를 요청했다고 가정해보자, 현재 가용 자원으로 충분히 할당할 수 있지만, P1이 요구할 수 있는 최대 자원량보다 현재 가용 자원량이 적으므로 자원을 할당하지 않는다. (자원 할당에 보수적임을 알 수 있다.)

◾️ P1, P3, P4, P2, P0 순서로 자원을 요청한다면, 모든 요청을 충족할 수 있다. 이러한 순서가 존재할 때  Safe State라고 한다. 

---

3️⃣ 데드락 발견 ( DeadLock Detection and Recovery )

◾️ 데드락 발견은 DeadLock 발생을 허용하고, DeadLock이 발생했을때 그것에 대한 후속처리를 하는 것이다. (프로세스를 죽이거나, 자원을 뺏거나)

 

📌 Detection 알고리즘 1 

◾️ 그래프 (a)에서 자원을 생략하면 그래프 (b)를 만들 수 있다. 이를 wait for graph 라고 한다.

◾️ wait for graph에서 Cycle이 존재 한다면, DeadLock이다. 

◾️ DFS 또는 BFS 알고리즘을 활용하여 Cycle을 찾는 알고리즘을 만들 수 있다. ( 수행시간은 O(n^2) 이다. )

📌 Detection 알고리즘 2 (은행원 알고리즘과 유사)

◾️ 데드락 발견에서는 어떤 프로세스가 자원을 요청하면 그냥 준다. 

◾️ 현재 자원을 요청하고 있지 않은 프로세스들이 보유하는 자원은 반환된 자원이라고 가정한다.

◾️ 현재 P0, P2는 자원을 요청하고 있지 않다. 따라서 A 3개, B 1개, C 3개는 반환된 자원이라고 생각한다.

◾️ 위와 같이 가정하면 P0, P2, P3, P1, P4 순서로 자원할당이 가능하므로 DeadLock이 아님을 알 수 있다. 

 

◾️ 만약 좀 전의 매트릭스에서 P2가 C 1개를 요청했다면, 자원요청을 하지 않은 프로세스는 0번 밖에 없다. 그럼 P0만 자원을 반납한다고 가정하게 된다. 결국 가용자원은 B 1개이다. B 1개로 다른 모든 프로세스들의 요청을 받아드릴 수 없으므로 DeadLcok 이다. 

 

 

◾️ 데드락이 발견되면 회복을 해야한다. 두 가지 방법이 존재한다.

◾️ 데드락에 연루된 모든 프로세스를 한 번에 죽이는 방법을 쓰거나

◾️ 데드락이 없어질 때까지 연루된 프로세스를 하나씩 죽여보는 방법이 있다. (데드락에 연루된 프로세스의 자원을 하나씩 뺏어보는 것)

◾️ 자원을 뺏는 패턴을 조금씩 바꿔야한다. 방금 죽인 프로세스가 또다시 같은 자원을 가져가는 경우가 생길 수 있기 때문이다. 또한 특정 프로세스의 자원만 뺏으면 Starvation이 발생할 수 있는데 이를 막기 위해서도 이다.

---

3️⃣ 데드락 무시 ( DeadLock Ignorance )

◾️ 데드락을 생기지 않게 하는 것은 자원의 비효율성을 유발한다.

◾️ 데드락 발견은 시스템 오버헤드가 존재한다.

◾️ 데드락 무시에서는 데드락이 발생하면 아무처리를 하지 않는다. 즉 사용자가 알아서 DeadLock을 처리해야한다. 

◾️ 현재 대부분의 운영체제들이 채택하는 방법이다.