deadlock

• 각자 일부자원을 가지고있으면서, 상대방이 가진 자원을 요구하고, 상대방도 내놓지않고 다른자원을 요구하는 상태
• 일련의 프로세스들이 서로가 가진 자원을 기다리며 block된 상태

Resource

• 하드웨어, 소프트웨어 등을 포함하는 개념
• (예) I/O device, CPU cycle, memory space, semaphore 등
• 프로세스가 자원을 사용하는 절차
  - Request, Allocate, Use, Release
  

Deadlock 예시

1. 시스템에 2개의 tape drive가 있다. 프로세스 p1과 p2 각각이 하나의 tape drive를 보유한 채 다른 하나를 기다리는 상태

2. semaphore A와 B
   

Deadlock 발생의 4가지 조건

• Mutual exclusion(상호배제)
  매 순간 하나의 프로세스만이 자원을 사용할 수 있음
• No preemption(비선점)
  프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않음
• Hold and wait(보유대기)
  자원을 가진 프로세스가 다른 자원을 기다릴 때 보유자원을 놓지않고 계속 가지고 있음
• Circular wait(순환대기)
  자원을 기다리는 프로세스간에 사이클이 형성되어야함
  
  

자원할당그래프

deadlock이 발생하는지 그래프를 그려서 확인할 수 있다.

• R이 P를 가리키는 것 : 해당 Resource를 해당 Process가 사용한다.
• P가 R을 가리키는 것 : 해당 Resource를 해당 Process가 요청한다.

그래프에 cycle이 없으면 deadlock이 아니다!

deadlock이 아닌경우

deadlock인 경우

아래의 경우에는 p2와 p4가 deadlock에 연루된 경우는 아니다.
그래서, 만약 p2와 p4가 자원을 다쓰고 반납을 하게된다면 deadlock이 아니다!!!

Deadlock의 처리 방법

1. Deadlock Prevention
   자원 할당시 Deadlock의 4가지 필요 조건 중 어느 하나가 만족되지 않도록 하는것
2. Deadlock Avoidance

• 자원 요청에 대한 부가적인 정보를 이용해서 deadlock의 가능성이 없는 경우에만 자원을 할당
• 시스템 state가 원래 state로 돌아올 수 있는 경우에만 자원 할당

3. Deadlock Detection and recovery
   Deadlock 발생은 허용하되 그에 대한 detection 루틴을 두어 deadlock발견시 recover
4. Deadlock Ignorance(현대의 운영체제는 대부분 이 방식을 채택함)
   Deadlock을 시스템이 책임지지 않음

1. Deadlock Prevention

deadlock을 미연에 방지하는 방법!

아래의 4가지는 아까 위에서 봤던 Deadlock 발생의 4가지 조건이다.
어느 하나의 조건을 만족시키지 않으면 deadlock의 발생을 막을 수 있다.
아래의 방법을 보자!

• Mutual exclusion(상호배제)
  공유해서는 안되는 자원의 경우 반드시 성립해야함
  (이 조건은 항상 만족시켜야 하기때문에 다른 조건을 만족시키지 않는 방법을 찾아야함.)
• No preemption(비선점)
  - 프로세스가 어떤 자원을 기다려야 하는 경우 이미 보유한 자원이 선정됨
  - 모든 필요한 자원을 얻을 수 있을 때 그 프로세스는 다시 시작된다.
  - state를 쉽게 save하고 (빼앗긴 시점 다음부터 실행할 수 있도록)restore 할 수 있는 자원에서 주로 사용(CPU, memory)
• Hold and wait(보유대기)
  - 프로세스가 자원을 요청할 때 다른 어떤 자원도 가지고있지 않아야한다.
  - 방법1. 프로세스 시작 시 모든 필요한 자원을 할당받게 하는 방법(이 방법은 자원을 비효율적으로 관리하게 된다는 단점이있음!)
  - 방법2. 자원이 필요할 경우 보유 자원을 모두 놓고 다시 요청
• Circular wait(순환대기)
  - 모든 자원 유형에 할당 순서를 정하여 정해진 순서대로만 자원 할당
  - 만약, 순서가 3인 자원 R을 보유 중인 프로세스가 순서가 1인 자원 R을 할당받기 위해서는 우선 (순서가 3인)R을 release 해야한다.
  

2. Deadlock Avoidance

deadlock을 미연에 방지하는 방법!

• 자원 요청에 대한 부가정보를 이용해서 자원 할당이 deadlock으로부터 안전한지를 동적으로 조사해서 안전한 경우에만 할당
• 가장 단순하고 일반적인 모델은 프로세스들이 필요로 하는 각 자원별 최대 사용량을 미리 선언하도록 하는 방법

safe state

시스템 내의 프로세스들에 대한 safe sequence가 존재하는 상태

safe sequence

• 프로세스의 sequence<P1, P2, ..., Pn>가 safe하려면 Pi(1<= i <= n)의 자원 요청이 가용자원 + 모든 Pj(j < i)가 의 보유자원에 의해 충족되어야 함

• 조건을 만족하면 다음 방법으로 모든 프로세스의 수행을 보장
  - Pi의 자원 요청이 즉시 충족될 수 없으면 모든 Pj(j < i)가 종료될 때까지 기다린다.

---

(데드락 2번강의 들어야됨)