데드락 DeadLock 해결을 위한 방법들

1. 데드락 DeadLock

• 프로세스들이 서로가 가진 자원을 기다리며 block 된 상태.
• 프로세스가 자원을 배출release 하는 시점은, 자신이 가진 자원use과 필요로한 자원request을 동시에 소유하고 그 작업을 완료할 때임.
• 그러므로 자원의 분배allocate의 방식이 중요한 쟁점임.
• 프로세스가 자원을 사용하는 절차 : request-allocate-use-release

2. 데드락이 발생하는 네 가지 필요 조건
   2.1 상호배제 Mutual exclusion

• 하나의 프로세스만 자원을 사용할 수 있을 때

2.2 비선점 No preemption

• 프로세스는 자원을 내놓을 수만 있고, 빼앗기지는 않음.

2.3 보유대기 Hold and wait

• 자신의 자원을 포기하지 않고 다른 자원이 생기기를 기다리는 것

2.4 순환대기 Circular wait

• 자원을 기다리는 사이클이 형성. P0 -대기-> P1 -대기-> P2 -대기-> P0

3. 자원의 할당을 표현하는 두 가지 방법
   3.1 자원 할당 그래프
   

• 자원(R을 변수로 하는 박스)에 자원이 하나(박스 안에 점)만 있으며, 프로세스(P를 변수로 하는 원)가 사용 중인 자원(프로세스에게 오는 그래프)와 요구하는 자원(프로세스가 가는 그래프)가 순환하면, 데드락 상태.
• 자원이 다수이면 데드락 상태가 아닐 수도 있음.

3.2 뱅커스 알고리즘 Banker's Algorithm

• 자원 할당 그래프로 표현하기 어려운 복잡한 상황에서 사용. 대체로 그래프보단 해당 표를 사용.
• ABC는 자원이며, 각 자원의 소유량(instances)이 있음. 각 프로세스는 현재 허가된 자원Allocation과 최대한으로 사용시 예측되는 자원MAX, 프로세스가 최대한의 자원을 요구할 경우 요구되는 자원의 양Need과 현재 가용한 자원Avaialble로 구성된다.

---

데드락을 피하며 자원을 할당하는 네 가지 방법

4 DeadLock Prevention

• 데드락을 원천적으로 회피하는 방법.
• "2. 데드락이 발생하는 네 가지 필요 조건" 중 어느 하나가 만족되지 않도록 함.

4.1 상호배제 Mutual exclusion

• 상호 배제의 경우 반드시 지켜져야 함.

4.2 보유대기 Hold and wait

• 프로세스가 자원을 요청할 때 어떤 자원도 가지지 않아야 함
• 해결책 1) 프로세스 시작할 때 처음부터 모든 필요한 자원을 할당받음.
• 해결책 2) 자원이 필요할 경우 보유 자원을 모두 포기한 다음 요청.

4.3 비선점 No preemption

• 프로세스가 데드락이 발생한 경우, 보유대기가 가능할 경우에 작동하도록 아예 프로세스를 정지시킨다.
• 상태state를 쉽게 저장하고 복구restore할 수 있는 자원(CPU,Memory)에서 자주 사용된다. (PCB 등)

4.4 순환대기 Circular wait

• 모든 자원의 할당 순서를 정함. 012345 의 자원이 있고 4를 가지고 있는 프로세스가 2를 필요로 하면 4를 배출해야함. 그리고 이후에 2와 4를 가지게 되면 순환대기가 발생하지 않음.

5 데드락 회피 Deadlock Avoidance

• 각 프로세스가 사용할 자원을 예측하고, 자원 할당 과정에서 데드락으로부터 완전하게 자유로운지safe state를 확인한 후 가용 자원을 배분.
• 자원 할당 그래프와 뱅커스 알고리즘을 활용한다. 여기서는 뱅커스 알고리즘을 통해 확인하겠다.
  
• 프로세스 P0이 현재 ABC를 각각 010을 가지고 있으며, 자원을 최대한 점유할 때 각각 753을 가진다. 그러면 만약 최대치로 자원을 차지한다면 743이란 값을 필요로 한다. 그리고 현재 332만 가용하다.
• 이런 경우 커널은 100이라는 단 하나의 자원을 요청하더라도 P0에게 자원을 주지 않는다. 왜냐하면 가용한 자원을 초과하는 자원을 요구할 가능성이 만에 하나 있기 때문이다.
• P1의 경우 Need가 122이며 이는 가용한 자원보다 적기 때문에 어떤 요청을 하더라도 커널은 자원을 배분한다.
• 하지만 어떤 프로세스가 자원을 배출release할지 모르기 때문에 반드시 데드락이 걸린다는 보장을 하지 않는다. 매우 보수적인 방식으로 문제를 해결.

6. Deadlock Detection and Recovery

• 4와 5의 방법으로 데드락을 원천적으로 차단할 경우 효율성 문제가 발생. 많은 규제와 많은 대기, 이로 인한 기아상태 등의 문제가 발생. 더 나아가 데드락은 분명 발생할 수 있으나 자주 발생하는 것은 또한 아님.
• 그러므로 데드락의 발생을 허용 하되, 문제 발생에 대한 처리를 사후적으로 함.

6.1 Deadlock Detection

• 프로세스 중 request가 존재하지 않는 프로세스가 있다. 이 말은 현재 가지고 있는 자원으로 작업을 종료하고 자신이 가진 자원을 배출한다는 의미이다. 그러므로 현재 가용한 자원이 000이라도 데드락이 생기지 않을 가능성이 높다.
• 그러나 만약 P2의 request가 111로 변할 경우, p0이 배출하는 자원이 010 밖에 없으므로 데드락이 발생한다.
  
• Wait-for graph를 통하여 데드락이 발생했는지를 찾는다. 해당 그래프는 (n)(n-1)으로서 O(n^2)만큼의 시간 복잡도를 가진다.

6.2 Recovery

• 해결책1) 데드락에 걸렸다고 확인되면, 모든 프로세스를 종료하거나, 하나씩 종료하여 작동하는지를 확인한다.
• 해결책2) 비용을 최소화 할 victim을 선정한다. 하지만 동일한 문제가 발생할 경우 동일한 victim을 제거한다 하더라도 문제가 반복될 수 있다. 어떤 프로세스는 기아 현상이 생길 수 있다. 그러므로 이를 위한 적절한 알고리즘을 필요로 한다.

7. Deadlock Ignorance

• 6번의 방법 역시도 데드락을 예측하기 위한 비용이 소모 되고, 해결을 위한 비용이 다시 소모된다. 데드락 해소를 위한 오버헤드보다 데드락에 대한 해결 자체를 포기하며 발생하는 이점이 크다는 것을 전제한다.
• 데드락이 발생하면 프로그램이 작동을 멈추거나 오류를 발생할 텐데, 이를 커널이 해소하지 않고, 사용자가 직접 프로세스를 종료함.
• 현재의 대부분의 OS가 채택하는 방식.