Deadlocks

Deadlocks

 Deadlock

 - 일련의 프로세스들이 서로가 가진 자원을 기다리며 block(sleep)된 상태.

  Resource(자원)

 - 하드웨어, 소프트웨어 등을 포함하는 개념 ex)I/O device, CPU cycle, memory space, semaphore등

 - 프로세스가 자원을 사용하는 절차(Request, Allocate, Use, Release)

  Deadlock 발생 조건

 - Mutual exclusion(상호배제) : 매 순간 하나의 프로세스만이 자원을 사용할 수 있다. 자원을 독점적으로 사용.

 - No preemption(비선점) : 프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않는다.

 - Hold and wait(보유대기) : 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있다.

 - Circular wait(순환대기) : 자원을 기다리는 프로세스 간에 사이클이 형성되어야 한다.

  Deadlock 처리방법

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

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

 - Deadlock Detection and recovery : Deadlock 발생은 허용하되 그에 대한 detection 루틴을 두어 deadlock을 발견하는 경우 recover

 - Deadlock Ignorance : Deadlock을 시스템이 책임지지 않음. UNIX를 포함한 대부분의 OS가 채택.

 위에서부터 두 가지가 deadlock 걸리기전 미리 방지하는 것이고, 나머지 두 가지가 deadlock이 걸린 후에 처리하는 방식이다. Deadlock Ignorance의 경우 현재 시스템에 있는 방법이다. 거의 deadlock 안 일어나고 일어나도 우리가 재부팅하기 때문. 방지작업이 오히려 overhead일 수 있다.

  

  Deadlock Prevention(발생조건 4개 차단)

 - Mutual Exclusion : 공유해서는 안 되는 자원의 경우 반드시 성립해야 함. 여러 프로세스가 공유할 수 있다면 deadlock이 되지 않겠지만 한 개 프로세스만 사용가능하면 deadlock -> 조건을 없앨 방법이 없다.

 - Hold and Wait : 프로세스가 자원을 요청할 때 다른 어떤 자원도 가지고 있지 않아야 한다. 

                    1. 프로세스 시작 시 모든 필요한 자원을 할당 받게 하는 방법. but 모든 자원을 가지고 있으므로 비효율적.

                    2. 자원이 필요한 경우 보유 자원을 모두 놓고 다시 요청. (현재 가지고 있는 자원도 반남하고 다시 요청)

 - No Preemption : (자원을 선점할 수 있게 변경하면 해결.) process가 어떤 자원을 기다려야 하는 경우 이미 보유한 자원이 선점됨. 모든 필요한 자원을 얻을 수 있을 때 그 프로세스는 다시 시작된다. 한 개 작업이라도 실패 시, 모든 자원을 release한다. State를 쉽게 save하고 restore할 수 있는 자원에서 주로 사용한다.(CPU, memory). -> 강제로 뱉어내면 끝난지 안 끝난지 알 수 없다. 따라서 현 상태 저장하는 PCB가 있어야 가능하다. 즉, 현 상태를 저장하고 다시 시작할 수 있는 자원에서 사용이 가능하다.

 - Circular Wait : 모든 자원 유형에 할당 순서를 정하여 정해진 순서대로만 자원 할당. 예를 들어 순서가 3인 자원 Ri를 보유 중인 프로세스가 순서가 1인 자원 Rj을 할당 받기 위해서는 우선 Ri를 release해야 한다.

   Utilization 저하, throughput 감소, starvation 문제

  Deadlock Avoidance

 - Deadlock avoidance : 자원 요청에 대한 부가정보를 이용해서 자원 할당이 deadlock으로부터 safe한지를 동적으로 조사, 안전한 경우에만 할당. 프로세스 시작 시, 프로세스가 앞으로 쓸 자원의 전체 양을 알고 있다고 가정한다. 가장 단순하고 일반적인 모델은 프로세스들이 필요로 하는 각 자원 별 최대 사용량을 미리 선언하도록 하는 방법.

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

   safe sequence : 프로세스의 sequence<P1,P2...Pn>이 safe하려면 Pi(1<=i<=n)의 자원 요청이 "가용 자원 + 모든 Pj(j<i)의 보유자원" 에 의해 충족되어야 함.  조건을 만족하면 다음 방법으로 모든 프로세스의 수행을 보장 - Pi의 자원 요청이 즉시 충족될 수 없으면 모든 Pj(j<i)가 종료될 때까지 기다린다. P의 i-1이 종료되면 Pi의 자원요청을 만족시켜 수행한다.

  시스템이 safe state에 있으면 no deadlock.  시스템이 unsafe state에 있으면 possibility of deadlock.

  Deadlock avoidance - 시스템이 unsafe state에 들어가지 않는 것을 보장. 2가지 경우의 avoidance 알고리즘

  1. Single instance per resource types : Resource Allocation Graph algorithm 사용

  2. Multiple instances per resource types : Banker's Algorithm 사용

  Resource Allocation Graph Algorithm

  - Claim edge Pi -> Rj : 프로세스 Pi가 자원 Rj를 미래에 요청할 수 있음을 뜻함.(점선으로 표시)  프로세스가 해당 자원 요청 시 request edge로 바뀜(실선).  Rj가 release되면 assignment edge는 다시 claim edge로 바뀐다.

  - request edge의 assignment edge 변경 시 (점선을 포함하여) cycle이 생기지 않는 경우에만 요청 자원을 할당한다.(위험방지)

  - Cycle 생성 여부 조사 시 프로세스 수가 n일 때 O(n2) 시간이 걸린다.

  Banker's Algorithm

  - 가정 : 모든 프로세스는 자원의 최대 사용량을 미리 명시. 프로세스가 요청 자원을 모두 할당 받은 경우 유한 시간 안에 이들 자원을 다시 반납한다.

  - 방법 : 기본 개념 - 자원 요청 시 safe 상태를 유지할 경우에만 해당.  총 요청 자원의 수가 가용 자원의 수보다 적은 프로세스를 선택.(그런 프로세스가 없으면 unsafe상태)  그런 프로세스가 있으면 그 프로세스에게 자원을 할당.  할당 받은 프로세스가 종료되면 모든 자원을 반납.  모든 프로세스가 종료될 때까지 이러한 과정 반복.

  Deadlock Detection and Recovery

 - Deadlock Detection : Resource type 당 single instance인 경우, 자원할당 그래프에서의 cycle이 곧 deadlock을 의미.  Resource type 당 multiple instance인 경우, Banker's algorithm과 유사한 방법 활용.

 - Wait-for graph 알고리즘 : Resource type당 single instance인 경우 => Wait-for graph 

   자원할당 그래프의 변형, 프로세스만으로 node 구성, Pj가 가지고 있는 자원을 Pk가 기다리는 경우 Pk->Pj,  Wait-for graph에 사이클이 존재하는지를 주기적으로 조사. O(n2)

 - Recovery

   Process termination : 프로세스 종료. deadlock에 연결된 프로세스를 없애는 방식. 연결된 모든 프로세스를 없애거나, 연결된 프로세스를 하나씩 없애봄.

   Resource Preemption : 자원뺏기. 비용을 최소화할 victim 선정. safe state로 roll back하여 process를 restart.(자원을 뺏어서 다시 시작.)  Starvation 문제 - 동일한 프로세스가 계속해서 victim으로 선정되는 경우.(자원을 뺏어서 다시 시작하자마자 다시 자원을 할당하는 경우) ==> cost factor에 rollback 횟수도 같이 고려. rollback은 껐다가 다시 회복하는 것.    ex) 5번 roll back 했는 데 계속 deadlock? -> 다른 것을 없앤다.

  Deadlock Ignorance

 - Deadlock이 일어나지 않는다고 생각하고 아무런 조치도 취하지 않음

   Deadlock이 매우 드물게 발생하므로 deadlock에 대한 조지 자체가 더 큰 overhead일 수 있다.

   만약, 시스템에 deadlock이 발생한 경우 시스템이 비정상적으로 작동하는 것을 사람이 느낀 후 직접 process를 죽이는 등의 방법으로 대처.

   UNIX, Windows 등 대부분의 범용 OS가 채택.