📌 Deadlock 해결 방법
Deadlock을 해결하기 위한 방법으로 Prevention, Avoidance, Detection/Recovery 방법이 있다.
1) Deadlock Prevention Methods
🌳 4가지 필요 조건 중 하나를 제거함으로써, 아예 교착 상태가 발생하지 못하도록 하는 방법
✔️ 심각한 자원의 낭비를 초래할 수 있기 때문에 실제로 사용하기는 어렵다.2) Deadlock Avoidance Methods
🌳 교착 상태의 발생 위험이 없도록 컴퓨터 시스템을 유지하는 방법3) Deadlock Detection and Deadlock Recovery Methods
🌳 교착 상태가 발생할 수 있지만, 교착상태를 발견하고 복구하는 방법
Deadlock Prevention Methods
1. 자원의 배타성
➡️ 모든 리소스를 sharable 하게 만든다.
❌ 불가능하다! 하드웨어적으로 CPU 등은 한번에 한 프로세스만 이용 가능하다.
2. 자원의 비선점성
➡️ 모든 자원이 선점 가능하도록 만들어보자!
CPU, Memory 자원은 기본적으로 preemption, swap-in/swap-out이 가능하다. 그럼 Non-preemptible resource의 경우 어떻게 할까?
✔️ 방법 1
프로세스 Pb가 다른 프로세스 Pa가 사용중인 자원을 요청하면, Pb는 wait하지 않고 Pb가 사용중이던 모든 자원을 반납한다. 그리고 Pb는 처음부터 다시 시작하는 방법이다. 즉 wait하면 deadlock상태에 빠질 수 있으므로 wait하지 않기 위한 방법이다.
✔️ 방법 2
어떤 프로세스 Pb가 어떤 자원을 요청하는데 그 자원이 다른 프로세스 Pa에게 할당중인 상태라면, Pa로부터 빼앗아서 선점하는 방법이다. 이 경우 프로세스 Pa가 죽을 수 있는 방법이다.
⭕ 이 방법을 통해 'deadlock'은 절대 발생하지 않을 것이다. 다른 자원을 사용하기 위해 Wait하지 않을 것이기 때문이다.
❌ 현실적으로 불가능(비실용적)하다. 원래 사용중이던 프로세스던 사용하려는 프로세스던 비정상적으로 종료되고 처음부터 다시 시작해야 하기 때문이다. 심각한 자원의 낭비를 초래하기 때문에 실용적이지 않다.
3. Hold and Wait
➡️ Hold and Wait 불가능하게 만들자!
✔️ 방법 1
프로세스가 실행하는 동안, R1 자원을 요청하고, 그 다음 R2 자원을 요청하고, 그 다음 R3 자원을 요청하는 것이 아니라 처음 실행할 때부터 Total Allocation 즉 R1, R2, R3를 모두 요청하고 할당받은 이후에 시작한다. 이렇게 되면 중간에 Wait할 필요가 없다. 그러나 자원이 필요하지 않을 때에도 hold하고 있기 때문에 자원의 낭비가 생긴다.
✔️ 방법 2
아무 자원도 가지고 있지 않은 상태에서만 자원을 요청할 수 있는 방법이다. 처음부터 모든 자원을 요청하는 것이 아니라 하나의 자원이 필요해지는 시점에서 그 R1, R2, R3를 모두 요청하는 것이다. 그런데 만약 R1만 필요한데 R2, R3를 다른 프로세스가 사용중이라면 Wait해야 한다. 따라서 이 경우 역시 리소스의 낭비가 발생한다.
❌ 모두 자원의 낭비가 발생한다.
❌ Indefinite Postponement가 발생할 수 있다. R1, R2, R3를 모두 한꺼번에 할당받고 시작하기 때문에 R3을 다른 프로세스가 사용중이면 기다려야 한다. 그러다가 R3가 가능해졌는데 R1을 다른 자원이 사용중이면 또 기다려야 한다. 즉 세 자원이 모두 사용가능하려면 계속 기다려야 한다. => 현실적 방법이 아님!
4. Circular Wait Condition
➡️ Circular Wait Condition을 불가능하게 만들자!
✔️ Process의 Cycle이 생기는 것을 방지하는 방법
리소스를 모두 Grouping을 한다.
각 프로세스는 Grouping 된 자원들 중에서, 내가 가진 자원의 group order보다 더 높은 자원만 요청할 수 있다.✔️ Example
group1에 속한 r1을 사용중인 p1이 group2에 속한 r2를 요청하는 것은 가능하다. 그리고 r2를 위해 wait하는 것은 가능하다.
그러나, group2에 속한 r2를 할당받은 p2가 order가 더 낮은 group1에 속한 r1을 요청하는 것은 불가능하다.
따라서 p1은 r1을 먼저 사용하다가 r2를 요청할 수 있지만, p2는 처음 r2를 사용할 때부터 r1과 r2를 함께 할당받아야 한다.✔️Hold and Wait 조건을 deny하는 total allocation 방법의 generalization이다.
❌ 자원의 낭비가 완화되기는 했지만, (p2의 경우처럼) 역시 자원의 낭비가 발생한다. => practical 하진 않다!
💬 Deadlock Prevention Methods 요약
Deadlock의 4가지 조건 중 하나를 부정하는 방식은 심각한 자원의 낭비를 초래한다.
결과적으로, 실용적이지 않다.
