Deadlock (교착상태)의 정의와 필요조건, 처리방법

1. 정의 - 하나 또는 여러 개의 프로세스가 일어날 수 없는 사건을 기다리며 영원히 대기(Blocked) 하는 상태.
          Deadlock에 포함된 프로세스는 영원히 중단된다.
   *위에서 일어날 수 없는 사건의 예 : 불가능한 자원 점유 등

ex1) Process1          공유자원 A,B          Process2
      lock(A) ->①                                 lock(B) ->②
               < Schduling                         lock(A) ->③ 대기
      lock(B) ->④대기

      unlock(B)                                      unlock(A)
      unlock(A)                                      unlock(B)

   흐름이 1->2->3->4 순으로 진행되었을 때,
   프로세스2는 프로세스1이 획득하고 있는 공유자원 A를 획득하지 못하고 대기하고
   프로세스1은 프로세스2가 획득하고 있는 공유자원 B를 획득하지 못하고 대기하면서
   두 프로세스 모두 lock에서 영원히 대기 하게 된다.
   이것이 Dead lock.

ex2)     공유자원 A,B,C
     P1                        P2                         P3
   lock(A)                lock(B)                   lock(C)
   schduling-1          schduling-2            lock(A) <-대기
   lock(B)                lock(C)

   스케줄링1이 일어나서 P2가 실행되고 스케줄링2가 일어나서 P3가 실행되면,
   lockA는 P1이, lock(B)는 P2가 lock(C)는 P3가 획득하고
   P1이 lock(B)를 획득하고 있는 P2의 unlock을 기다리고 P2는 lock(C)를 획득하고 있는
   P3를 기다리고 P3는 다시 lock(A)를 기다리고 있는 P1을 기다리면서
   사이클이 생겨 모두 영원히 대기하게 된다.

2. Deadlock의 필요조건
   *4개의 조건이 모두 만족해야 Deadlock이 가능하다. 그러나 4개의 조건을 다 만족하여도 Deadlock이 발생하지 않을수도 있다.
   1) Mutexual exclusion (상호배제)
        한 시점에서는 한 프로세스만 사용가능
   2) Hold and wait (점유와 대기)
        추가적인 자원을 요구하며 대기
   3) Non-preemption (비선점)
        Operation  도중 선점 불가능. ex)프린트 작업. 파일 쓰기
   4) Circular wait (환형대기)
        위의 ex2 에서 예를 들은 것처럼 프로세스간 싸이클이 형성된다.

3. Deadlock의 처리
   Prevention (예방,방지) 
   Deadlock의 발생원인을 제거함으로써 deadlock상태를 예방한다.
      4가지 필요 조건 중 하나를 배제 한다.
      3-1) 상호 배제의 부정 ( Denying mutual exclusion)
        C.S(Critical Section. 임계영역) 진입시에는 상호배제가 필수 임으로 일반적으로 불가능하다.
      3-2) 점유와 대기의 부정( Denying hold and wait)
        모든 자원을 실행 전에 확보한다. (필요한 lock을 동시에 전부획득하거나 아예 전부 획득하지 않는다)
        -> 쓰지 않는 자원을 미리 확보함으로 리소스의 낭비가 심하다
      3-3) Denying non-preemption ( 비 선점의 부정 )
        선점은 상태의 보존과 이의 복구가 필요
        -> 모든 device에 적용가능하지 않다. 적용가능한 device의 대표적인 예로서는 CPU와 메모리
      3-4) Denying circular-wait
         ***실제로 사용가능한 방법.
         각 자원 형태에 증가하는 순서의 번호를 부여한다.
         프로세스에서는 번호가 증가하는 순으로만 자원을 요청하면 환형 대기 방지. (즉 사이클을 막을수 있다)
         ex2의 예를 들어 다시 설명해보면,
         ex2의 공유자원 A,B,C에 각각 R1,R2,R3라는 자원 형태에 순서번호를 부여.
            P1                  P2                 P3
         lock(A)              lock(B)         lock(C)    
         lock(B)              lock(C)         lock(A)
        P1과 P2의 경우 자원의 요청이 각 자원의 할당된 번호가 증가하는 순으로 요청이 이루어져
        정상적으로 처리가 되지만, P3에서 자원의 할당된 번호가 역순으로 진행되어 deadlock의 위험을 감지 할수 있다.