Deadlock

Process scheduling과 Process synchronization에 대해 배웠다면,

이제는 Deadlock에 대해서 배워보자.

교착상태(Deadlock)

 둘 이상의 프로세스가 더 이상 계속할 수 없는 어떤 특정 사건을 기다리고 있는 상태

 

 1) 교착상태가 발생하기 위해서는 4가지 조건이 동시에 만족되어야한다.

   ① 상호배제(mutex exclusion) : 한 번에 한 프로세스만이 자원을 사용해야 하는 경우

   ② 점유와 대기(block and wait) : 자원을 일부 점유하면서 다른 자원을 기다리는 경우

   ③ 비선점(non preemption) : 프로세스가 완료되기 전에는 자원을 회수할 수 없는 경우

   ④ 환형 대기(circular wait) : 자원을 할당 받은 두 프로세스가 서로 할당된 자원을 요청하는 경우

 2) 교착 상태 해결방안 3가지

   ① 교착상태 예방(prevention) : 교착상태의 발생가능성을 없애는 방법 -> 자원낭비가 심하고, 기아상태 초래 가능

           상호배제 부정 : 여러 프로세스가 동시에 공유자원을 사용하도록 한다(실현불가능)

           점유와 대기조건의 부정 : 자원을 모두 할당하거나 할당된 자원을 없앤 후 재요청

           비선점 조건의 부정 : 자원을 점유하고 있는 프로세스는 자원을 강제로 반납

           환형 대기 조건의 부정 : 자원을 선형 순서로 분류하여 프로세스에게 할당

   ② 교착상태의 회피(avoidance) : 시스템 운영 상황을 보아가면서 교착상태 가능성을 피해가는 방법

                                              자원할당 그래프 or 은행원 알고리즘 이용

자원할당 그래프(Resource allocation graph)

-

- 프로세스와 자원과의 관계를 나타내는 그래프

- 자원할당 그래프를 그려 사이클이 생길 것 같으면 사용자의 자원 요구 거부

           ((교착상태에 빠질 가능성이 있는 지 판단하기 위해 시스템 상태를 2개로 나눔))

- 안전상태(safe state) : 시스템이 교착상태를 일으키지 않으면서, 

   각 프로세스가 요구한 최대 요구량만큼 필요한 자원을 할당해 줄 수 있는 상태

- 불안전상태(unsafe state) : 교착상태가 일어날 수 있는 상태. 무조건 발생하는 건 아님

은행원 알고리즘에 대해 알아보자.

은행원 알고리즘(Banker's Algorithm)

- 안전상태를 유지할 수 있는 요구만을 수락하고, 

  불안전 상태를 초래할 사용자의 요구는 나중에 만족될 수 있도록 계속 거절

            - 사용하는 자료 구조

              1. Available : 사용가능한 자원의 수

              2. Max : 프로세스 별 최대 자원의 요구

              3. Allocation : 현재 프로세스 별 할당되어 있는 자원 수

              4. Need : 프로세스 별 남아 있는 자원 요청 수(Max - Allocation)

            - 동작 원리

   Work = init Available

   예를 들어 프로세스 Pi가 자원을 요청했을 때

              step 1. 종료가 안된 프로세스 Pi를 찾으면 step 2로 넘어감

 만일 모두 종류가 안된 프로세스가 없다면 그 시스템은 safe state상태

              step 2. Pi의 Need가 Work 보다 작다면 step 3으로 넘어감

                                      크다면 pass

              step 3. 프로세스 Pi에게 자원을 할당해서, 완료시킨 뒤

      프로세스 Pi가 가진 자원을 반환

Work = Work + Allocation(Pi)

다시 step 1으로

- 예시

  자원 A는 10개, 자원 B는 5개, 자원 C는 7개가 있다고 가정

즉, 안정 순열(p1,p3,p4,p0,p2) 순으로 자원을 할당해 안정상태 유지

- 은행원 알고리즘의 단점 : 알고리즘이 너무 복잡,

 프로세스가 가지고 있어야 할 자원의 최대 개수를 미리 알아야함.

           

   ③ 교착상태 탐지(detection) 및 복구(recovery) :

 - 이미 발생한 교착상태를 탐지알고리즘이나 자원할당그래프, 대기 그래프의 사이클 유무에 따라 찾아낸 후 복구하는 방법

           

   탐지 알고리즘? Banker’s algorithm의 변형 알고리즘 활용

         - 사용하는 자료구조

             ⓐ Available : 사용가능한 자원의 수

             ⓑ Allocation : 현재 프로세스 별 할당되어 있는 자원 수            

             ⓒ Request : 각 프로세스가 현재 요청 중인 자원 수

         - 동작 원리

             (탐지알고리즘은 은행원 알고리즘과 마찬가지로 내용이 달라지는 자료구조를 사용한다.

              다른 점은, 은행원 알고리즘의 Max와 Need과 Request로 바뀐 것)

 

         - 예제 1)

이 예제에서는 현재 상황에서 Available 값이 모두 0이지만

      P(0)가 아무 자원도 요청하지 않기 때문에 작업을 끝내면 자원을 반납하고 

반납한 자원으로 P(2)에게 할당하면서 Safe State Sequence(p0,p2,0p3,p4,p1)를 만들어낼 수 있어서

            현재 이 상태는 Deadlock에 빠져 있지 않은 상태임을 탐지

   - 예제 2)

예제 1과 달리 P2가 자원 C를 하나 요청했을때

P(0)가 자원을 반납하더라도 P(2)의 현재 요청 자원이 바뀜으로 인해 

현재 아무 프로세스에게도 자원을 할당해줄 수 없으므로 

P(1), P(2) ,P(3) ,P(4)는 Deadlock에 빠져 있는 프로세스라고 판단 -> 교착상태에 빠져있음을 탐지

 - 탐지한 교착상태 복구(recovery) 방법

ⓐ 프로세스 종료 : 교착 상태 프로세스를 모두 종료하거나 희생 프로세스를 정해서 종료

ⓑ 자원선점 : 교착상태의 프로세스로부터 자원을 선점

 - Deadlock detection은 지속해서 현재 상태를 검사하며 또한 프로세스를 종료시킨 후 다시 시작해야 하는 등 

  많은 비용이 들기 때문에 비효율적이라 판단되어 현재 다수의 시스템에서는 사용 되지 않고 있다.