교착상태(Deadlock)

교착상태(deadlock)란

 

프로세스가 자원을 얻지 못하여 작업이 진행되지 못하는 상태.

한정된 자원을 여러 프로세스에서 동시 접근하려고 할 때 발생.

 

발생하는 경우 
- 멀티프로그래밍 환경에서 한정된 자원을 얻기 위해 프로세스들이 서로 경쟁하는 경우
- 프로세스가 자원을 요청했을 때, 해당 자원이 이미 점유되어 있다면 대기 상태로 빠짐. 대기 상태에서 실행 상태로 변경이 불가능한 경우

예를 들어, P1이 R1을 P2가 R2를 각각 할당받은 상태에서 P1->R2, P2->R1 다음과 같이 자원을 요청한다면 두 프로세스 모두 무한 대기 상태에 빠지는데, 이러한 상태를 DeadLock이라고 하는 것!

 

발생 조건 - 4가지 모두 성립해야 데드락 발생

1. 상호 배제(Mutual Exclusion)
  자원은 한번에 한 프로세스만 사용 가능

2. 점유 대기(Hold and Wait)
  최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용되고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 존재해야 함

3. 비선점(No Preemption)
  다른 프로세스에 할당된 자원은 해당 프로세스가 종료될 때까지 선점할 수 없음

4. 순환 대기(Circular wait)
  프로세스의 집합에서 순환 형태로 자원을 대기하고 있어야 함
  

해결 방법

1. 예방

  앞에서 살펴본 데드락 발생 조건 4가지 중 하나를 제거하여 해결한다(자원의 낭비가 매우 심함)

 

• 상호 배제 부정: 여러 프로세스가 공유자원 사용
• 점유 대기 부정: 프로세스 실행 전 필요한 모든 자원을 할당, 점유한 자원이 없을 때에만 자원 요청 가능하도록 함
• 비선점 부정: 모든 자원에 대한 선점을 허용. 프로세스가 할당받을 수 없는 자원을 요청하는 경우
                   기존에 점유 중인 자원을 모두 반납 후 대기  
• 순환 대기 부정: 자원에 고유 번호를 부여, 순서대로 자원을 요구

 

2. 회피

  데드락 발생 전에 미리 예측하여 안전한 상태에서만 자원 요청을 허용한다

 

• 자원 할당 그래프(Resource Allocation Graph)
  프로세스와 자원, 할당과 할당 예약 관계를 그래프로 표현하여 cycle 여부에 따라 데드락을 판정한다.
  cycle 존재 시 데드락!
  
  
• 은행원 알고리즘(Banker's Algorithm)
  모든 프로세스들이 최대의 요청을 할 것이라고 가정하고 가용 자원으로 해결이 가능한지 판단한다.

 

3. 회복

  데드락을 발생시킨 프로세스를 종료하거나, 할당된 자원을 해제시켜 데드락 상태에서 회복한다

 

• 프로세스 종료
  1. 모든 프로세스를 중지시킨다
  2. 데드락에서 회복할 때까지 프로세스 하나씩 중지시킨다
• 자원 선점
  데드락에 걸려있는 프로세스의 자원을 선점하여 다른 프로세스에게 할당