📌 Deadlock 1

📖 01. 교착상태(deadlock)

• 일부 자원을 가지고 있으면서 상대방이 원하는 자원을 요구하고 있는데 상대방이 원하는 것을 내놓고 있지 않을 때 이를 deadlock이라고 한다.

• 어느 누구도 양보하지 않으면 진행되지 않는 상태

📖 02. The Deadlock Problem

📖 03. Deadlock 발생의 4가지 조건

📖 04. Resource-Allocation Graph (자원할당그래프)

• Deadlock이 발생했는 지 알아보는 방법

• R -> P : 프로세스가 자원을 가지고 있다
• P -> R : 프로세스가 자원을 요청

• 자원의 인스턴스가 하나밖에 없을 때 사이클이 생기면 deadlock을 의미한다.

• 자원의 인스턴스가 여러개 있다면?
  -> Deadlock 일수도 있고 아닐 수도 있다.

• 첫번째 그림
  -> R2의 자원이 2개임에도 불구하고 사이클이 2개이다. => Deadlock

• 두번째 그림
  -> P4가 자원을 다쓰고 내놓으면 P3가 그 자원을 가져가게 되고 사이클이 없어지게 된다. => Deadlock X

📖 05. Deadlock의 처리 방법

• 위로 갈수록 Deadlock 처리방법이 강한 것

• Deadlock Ignorance
  -> 운영체제가 처리를 안하면 어떻게 Deadlock이 처리되나?
  -> 프로세스를 돌리다가 이상한 낌세가 느껴지면(느려지는 등) 사람이 알아서 프로세스를 종료 할 것이다.
  -> Deadlock을 자주 발생하는 것이 아니기 때문에 미연에 방지하기 위해서 훨씬 더 많은 오버헤드를 들이는 것이 비효율적이다.

📖 05-1. Deadlock Prevention

• Deadlock이 발생하는 4가지 조건 중 하나를 원천적으로 차단해서 Deadlock에 들어가지 못하게 하는 방법이다.

• Mutual Exclusion : 한 번에 하나의 프로세스만 사용할 수 있는 자원이라면 우리가 배제할 수 있는 조건은 아니다.

• Hold and Wait : 내가 가진 자원은 내놓지 않으면서 다른 자원을 기다리기 때문에 Deadlock이 생긴다.
  -> 이 조건을 없애려면?
  -> 자원을 기다려야 하는 상황에서는 자원을 보유하고 있지 않으면 된다.
  -> 방법 1: 어떤 프로세스가 시작 될 때 이 프로세스가 평생에 필요로 하는 것을 모두다 할당받게 하면 이 친구가 다 쓰고나서 프로세스가 종료 될 때 자원을 반납을 할 것이다.
  -> 중간에 필요한 자원이 없을 것이다.
  -> Wait을 할 일이 없을 것이다.
  -> 그러나 그 때 마다 필요한 자원만 있으면 되는데 처음부터 다 가지고 있으면 자원배분에 대한 비효율이 생길 것이다.

• 방법 2: 내가 자원을 가지고 있던 도중 기다려야 한다면 가지고 있던 자원을 모두 내려놓고 다시 요청한다.

• No Preemption : 다른 프로세스가 자원을 가져갈 수 있도록 한다면 Deadlock이 걸리지 않을 것이다.

• CPU는 timer같은 것을 걸어서 Preemptive하게 할 수 있었다.
  -> 이런 자원은 Deadlock이 걸리지 않는다.
  -> 즉, 빼앗아 올 수 있는 자원이라면 Deadlock은 걸리지 않는다.

• Circular Wait : 필요한 자원들이 꼬리의 꼬리를 물고 있으면서 사이클이 형성된 경우 Deadlock이 생성될 수 있다.
  -> 예를 들어 내가 1, 3, 5번 자원이 필요하다면 낮은 번호부터 자원을 획득해야 높은 번호를 획득 할 수 있도록 하자.
  -> 1번을 가지고 있고 3번을 요청하고 3번을 가지고 있고 1번을 요청해야하는 경우 Deadlock이 걸리는데 위와 같은 방법으로 진행한다면 Deadlock이 걸리지 않는다.

• Prevention은 Deadlock을 막을 수 있지만 자원에 대한 이용률이 낮아지고 전체 시스템에 대한 성능이 떨어지며 starvation 현상이 발생 할 수 있다.

📖 05-2. Deadlock Avoidance

• Deadlock Prevention과 마찬가지로 미연에 방지하는 방법이다.

• 프로세스가 시작되서 종료 될 때까지 그때그때 사용하려는 종류와 자원의 수가 다르다.
  -> Deadlock Avoidance는 프로세스가 시작 될 때 평생에 쓸 자원의 최대량을 미리 알고 있다고 가정하고 Deadlock을 피해가는 것이다.
  -> 어떤 프로세스가 자원을 요청하였지만 혹시 내가 자원을 할당 해주면 Deadlock이 발생할 가능성이 있겠다 싶으면 자원의 여분이 있더라도 주지 않는다.
  -> Deadlock을 미연에 방지하는 방법이다!

• 2가지로 나누어 생각 할 수 있다.

1. 자원의 인스턴스가 하나씩 밖에 없을 때
   -> 자원 할당 그래프를 통해 adoidance를 할 수 있다.
2. 2개 이상의 인스턴스가 존재 할 때
   -> Banker's Algorithm 사용
   -> 이 두가지를 사용하여 Deadlock을 피해 갈 수 있다.

• 자원이 1개 밖에 없을 때 Deadlock을 피하는 방법
  
• 프로세스와 자원이 2개씩 있다.
• P -> R : 자원요청(아직 할당 받지는 못한 상태)
• R -> P : 프로세스가 자원을 가지고 있다.
• '점선'은 P -> R 밖에 없으며 해당 프로세스는 해당 자원에 일평생 적어도 한번은 사용할 일이 있다는 뜻이다.
  -> 지금은 아니지만 평생 적어도 한번은 요청 할 수 있다.
  -> 실제로 요청을 한다면 실선으로 바뀐다.

-2번째 그림이 대표적인 그림
-> 자원을 가지고 있음에도 주게되면 사이클이 만들어질 위험이 생기므로 P2에게 자원을 주지 않는다.
-> 만약 P1이 R2에게 요청한다면 자원을 준다.
-> 줬을 때 어떤일이 생겨도 사이클은 만들어지지 않기 때문이다.

• 자원이 여러개 있을 경우

-> 문제가 생길 것 같다면 자원이 남아있더라도 주지 않는다.

• 위와 같은 상황에서 P1이 A:1개, C:2개를 요청했다고 하자.
  
  -> 추가 요청할수 있는 양이 가용자원가지고 모두 충족 시킬 수 있는지 확인하자.
  -> P1에 경우 앞으로 필요로 하는 자원(Need)이 1, 2, 2인데 가용자원이 3, 3, 2로 이를 넘는다.
  -> 자원을 넘겨 줄 수 있다는 얘기!! (Deadlock으로부터 안전하다)

• P0이 B를 2개 요청한다.
  -> B는 3개로 여분이 존재하지만 추가 요청(Need)가 남아있는(Available)을 충족시키지 못한다.
  -> P0한테 줄 자원이 있지만 주지 않는다.
  -> 다른 프로세스들이 끝나기를 기다린다.
  -> 종료된 프로세스는 할당된 자원을 뱉어내며 가용자원을 바꾸고 필요로 하는 자원보다 가용자원이 많아진다면 자원할당이 가능해진다.

• 가용자원 > 요청할 수 있는 자원 이 성립할 경우 자원을 줄 수 있다.

📖 05-3. Deadlock Detection and Recovery

• DFS의 시간복잡도 O(n^2)

• P0, P3의 Request가 없으니까 잘 끝나고 자원을 반납할 것이다.
  -> Available (3,1,3)
  -> 이용 가능한 자원이 생겼으니 P1도 잘 끝낼 수 있을 것이다.
  -> 이런식으로 막히지 않고 sequence가 생긴다면 Deadlock이 발생하지 않을 것이다!

• P2가 자원 C를 요청하면?
  

• 어느 누구의 요청도 받아드릴 수 없는 상황이 초래된다.
  -> Deadlock!

• Deadlock이 발생하면 Recovery하자
  

• Process termination : Deadlock에 연류된 프로세스들을 종료하자!
  -> 1. 모두 죽이자.
  -> 2. 하나씩 죽여봐서 Deadlock이 없어지면 ok
  -> Deadlock이 없어질 때까지

• Resource Preemption : Deadlock에 연류된 프로세스로부터 자원을 뺏자!

📖 05-4. Deadlock Ignorance

• Deadlock이 일어나든 일어나지 않든 처리를 하지 않는 것을 말함

• Deadlock이 발생하지 않게 하는 것도 자원을 비효율적으로 사용하는 방법이 되고 Deadlock을 Detection 하는 것도 Detection이 발생했을 때 rutine을 실행하는 것 또한 오버헤드가 된다.
  -> 따라서, Deadlock이 생기든 그렇지 않든 운영체제는 책임을 지지 않고 그냥 두는 것이다.
  -> 시스템이 느려지고 정지 할 것이다.
  -> 사용자가 알아서 처리하도록 하는 것!
  -> 현재 대부분의 운영체제는 이를 채택한다.

[출처] 반효경 교수님 강의