운영체제 - 15

KOCW 운영체제 15강

양희재 교수님 강의를 듣고 쓴 글입니다.

Deadlock

교착 상태. 두 개 이상의 작업이 서로 상대방의 작업이 끝나기 만을 기다리고 있기 때문에 결과적으로 아무것도 완료되지 못하는 상태.

저번 시간에는 이러한 deadlock의 발생에 필요한 조건들을 알아봤다. 물론 필요조건 4개가 전부 발생하더라도 deadlock은 발생하지 않을 수 있음을 알아야 한다.

이번에는 이러한 deadlock을 예방하거나 피할 수 있는 대처방법에 대해 알아보도록 하겠다.

Prevention

필요조건 4개가 발생하지 않도록 사전에 예방하는 방법이다.

• Mutual Exclusion : 자원의 공유가 안되었기에 자원의 공유를 허락하게 되면 해당 조건을 해결할 수 있다!!

  → 그러나 현실적으로 어렵다. 예를 들어서 프린터와 같은 자원을 공유하게 되면… 말이 안되는 것이다. 그나마 한다면 파일에 대한 읽기 상황일 때 여러명에게 공유하여 읽게 해주는 정도가 최선일 것 같다.

• Hold and Wait : 식사하는 철학자얘기처럼, 젓가락 하나를 들고 다음 젓가락을 들 때까지 무한히 기다리게 되는 상황을 해결해야 한다.

  1. 젓가락을 ‘동시에’ 잡게 한다.
  2. 오른쪽 젓가락이 이용 불가능하다면, 들었던 왼쪽 젓가락을 포기하게 만들기.

  위 2가지 방법 중 1개를 사용하여 해결할 수 있을 것이다. 하지만 Starvation이 발생 할 수 있기에 유의해야 한다. 2번의 경우에는 놓아버리는 경우가 많아지기에 자원 활용률도 떨어진다.

• No Preemption : 다른 프로세스가 쓰고 있는 자원을 강제로 뺏을 수 있게 하면 해결된다. 그러나 쓰이고 있는 자원을 갑자기 뺏어오는 것 또한 현실적으로 쉽지는 않다.

• Circular Wait : 자원에 번호를 붙여서 오름차순으로 자원을 요청할 수 있게 만들면 해결된다.

  철학자1이 왼쪽 0번 젓가락 들려고 한다. 그리고 오른쪽 1번 젓가락 들려고 한다.
  철학자2이 왼쪽 1번 젓가락 들려고 한다. 그리고 오른쪽 2번 젓가락 들려고 한다.
  철학자3이 왼쪽 2번 젓가락 들려고 한다. 그리고 오른쪽 3번 젓가락 들려고 한다.
  철학자4이 왼쪽 3번 젓가락 들려고 한다. 그리고 오른쪽 4번 젓가락 들려고 한다.
  철학자5이 왼쪽 0번 젓가락 들려고 한다. 그리고 오른쪽 4번 젓가락 들려고 한다. ← 원형 구조 깨버림
  

  이와 같은 상황에서 마지막 철학자5가 4번 젓가락을 들고 0번을 들려고하는게 아닌, 자원에 번호를 매겼기에 오름차순의 요청만 가능하게 한다면, 0번 젓가락을 요청하고 4번 젓가락을 요청하게 될 것이다. 이는 원형으로 요청하는 구조를 깨버리게 돼서 문제를 해결할 수 있다.

  마찬가지로 자원의 활용률이 떨어지게 된다.

Hold and Wait, Circular Wait정도를 해결하는 방안이 현실적이라고 강의에서는 말하고 있다.

Avoidence

회피하는 방법도 있다. 강의에서는 이 때의 deadlock에 대해

자원을 잘못 나눠줘서 발생한 현상.

이라고 한다. 아래의 예시 상황을 보면서 설명하겠다.

• 가정 : 현재 자원의 총량은 12개 라고 하자
• Max Need : Process 가 온전히 실행되고 종료되는데 필요한 자원의 총량
• Current Need : Process가 지금 당장 요구하는 자원의 양

이제 시뮬레이션을 시작해보겠다. 시간 순서에 따라 진행할 것이다.

1. 현재 Process1,2,3은 각각 5,2,3개의 자원을 요구하는 중이다. 현재 남은 자원은 12개. 따라서 모두에게 자원을 분배할 수 있다.

   1. Process 1 : 5개의 자원 취득. 앞으로 Max Need까지 5개 남음.
   2. Process 2 : 2개의 자원 취득. 앞으로 Max Need까지 2개 남음.
   3. Process 3 : 3개의 자원 취득. 앞으로 Max Need까지 6개 남음.

   분배하고 남은 자원 총 2개.

2. 현재 분배할 수 있는 남은 자원은 2개. Current Need에 따라 Process 2에게 분배가 가능.

   1. Process 1 : 5개의 자원 취득. 앞으로 Max Need까지 5개 남음.(아까와 변함없음)
   2. Process 2 : 2개의 자원 취득. 앞으로 Max Need까지 0개 남음. 프로세스 완료. 받았던 4개의 자원을 반납.
   3. Process 3 : 3개의 자원 취득. 앞으로 Max Need까지 6개 남음.(아까와 변함없음)

   분배하고 남은 자원 총 4개.(Process 2의 작업이 끝났기에 받았던 자원 4개를 반납받았기 때문이다.)

3. 현재 분배할 수 있는 남은 자원은 4개. Current Need에 따라 Process 3에게 분배가 가능.

   1. Process 1 : 5개의 자원 취득. 앞으로 Max Need까지 5개 남음.(아까와 변함없음)
   2. Process 2 : 종료된 상태. 자원을 필요로 하지 않는다.
   3. Process 3 : 3개의 자원을 추가적으로 취득. 앞으로 Max Need까지 3개 남음.

   분배하고 남은 자원 총 1개.

4. 현재 분배할 수 있는 남은 자원 1개.

   1. Process 1 : 5개의 자원 취득. 앞으로 Max Need까지 5개 남음.(아까와 변함없음)
   2. Process 2 : 종료된 상태. 자원을 필요로 하지 않는다.
   3. Process 3 : 3개의 자원을 추가적으로 취득. 앞으로 Max Need까지 3개 남음.(아까와 변함없음)

   분배하고 남은 자원 총 1개.

5. 현재 분배할 수 있는 남은 자원 1개.

   1. Process 1 : 5개의 자원 취득. 앞으로 Max Need까지 5개 남음.(아까와 변함없음)
   2. Process 2 : 종료된 상태. 자원을 필요로 하지 않는다.
   3. Process 3 : 3개의 자원을 추가적으로 취득. 앞으로 Max Need까지 3개 남음.(아까와 변함없음)

   분배하고 남은 자원 총 1개.

6. …? 4번 5번이 계속 반복된다. → Deadlock발생!!

결론적으로 아무리 기다려도 Process 1,3은 완료될 수가 없다. 필요한 만큼의 자원을 할당해줄 수 없기 때문이다. 그리고 어떠한 업무도 완료될 수 없기에 자원은 반납되지 못하여 분배할 수 있는 자원은 모일 수가 없게 된다.

OS는 자원을 할당할 때 이러한 불안정 할당이 안되도록 해야한다. 이 때 Banker's Algorithm or Resource Allocation Graph Algorithm을 쓴다고 한다.

Detection & Recovery

앞서 얘기했던 Prevention과는 달리 Deadlock 문제 해결을 발생한 이후에 해결한다는 것.

따라서 detection 과 발생한 후 recovery를 통해서 문제를 해결한다는 것이다.

Ignore

실제로 Deadlock이 일어날 필요조건을 다 갖춰도 안일어날 수 있고, 실제로도 잘 안일어난다고 한다. 따라서 detection, recovery를 하여 시스템에 overhead를 주지 않고 그냥 무시하는 것도 방법이라고 한다.