[OS] 교착상태와 해결 방법

교착상태(deadlock)

두 개 이상의 작업이 서로 상대방의 작업이 끝나기 만을 기다리고 있기 때문에 결과적으로 아무것도 완료되지 못하는 상태.

둘 이상의 프로세스나 스레드가 서로 필요한 자원을 얻지 못하고 무한히 대기하는 상태.

 

교착상태의 발생 조건

아래의 4가지 조건을 모두 만족했을 때 교착상태의 발생 가능성이 있다.

• 상호 배제 : 동시에 자원 사용이 불가능한 경우
• 점유와 대기 : 자원을 할당받을 채 다른 자원의 할당을 기다리는 경우
• 비선점 : 강제로 자원을 빼앗을 수 없는 경우
• 원형 대기 : 자원을 원형으로 대기할 경우

 

교착상태 해결 방법

교착상태 예방

• 교착상태 발생 조건 중 네가지 중 하나를 없애는 것
• 교착상태가 발생 배경 원천을 차단한다.
• 교착상태가 발생하지 않음을 보장할 수 있지만 여러 부작용이 따르는 방식
  
  • 상호 배제 조건 없애기
    • 자원을 공유하도록 변경
    • 모든 자원에 대해 적용할 수 없음(ex. 프린터기)
  • 점유와 대기 조건 없애기
    • 특정 프로세스에 자원을 모두 할당, 아예 할당하지 않기
    • 자원의 활용률이 저하
  • 비선점 조건 없애기
    • 선점하여 사용 가능한 자원에 대해서는 효과적(ex. CPU)
    • 모든 자원에 대해 적용가능할 것은 아님(ex. 프린터기)
  • 원형 대기 조건 없애기
    • 자원에 번호 매기기
    • 오름차순으로 자원 할당

 

교착상태 회피

• 교착상태가 발생하는 이유를 자원의 무분별한 할당으로 간주하고 교착상태가 발생하지 않을 정도만 자원을 할당하는 방법이다.
• 교착상태가 발생하지 않는지 판단하는 것은 대표적인 알고리즘은 은행원 알고리즘(banker's algorithm)이다.

 

교착상태 검출 후 회복

• 교착 상태가 발생하면 그때 회복하는 방식
  • 선점을 통한 회복
  • 프로세스 강제 종료를 통한 회복

(교착상태가 발생할 빈도 낮은 확률에 대해서 교착상태를 무시하는 타조 알고리즘이라는 것도 있다.)

---

정리

• 교착상태(deadlock)이란 둘 이상의 프로세스나 스레드가 서로 필요한 자원을 얻지 못하고 무한히 대기하고 있는 상태를 말한다.
• 교착상태 발생 조건은 상호 배제, 점유와 대기, 비선점, 원형 대기가 있으며 4가지 발생 조건을 모두 만족해야 교착상태가 발생할 가능성이 있다.
• 상호 배제는 동시에 자원을 사용할 수 없는 경우를 의미한다.
• 점유와 대기는 자원을 할당받은 채 다른 자원의 할당을 기다리는 경우를 의미한다.
• 비선점은 강제로 자원 빼앗을 수 없는 경우를 의미한다.
• 원형 대기는 자원을 원형으로 대기하는 것을 의미한다.
• 교착상태 해결 방법으로 교착상태 예방, 교착상태 회피, 교착상태 검출 후 회복이 있다.
• 교착상태 예방은 교착상태가 발생하지 않도록 발생 배경 원천을 차단하는 것으로 교착상태가 발생하지 않지 않음을 보장할 수 있지만 자원의 활동률이 감소하는 등의 부작용이 있을 수 있다.
• 교착상태 회피는 교착상태가 발생하지 않을 정도로만 자원을 할당하는 방법이다. 교착상태가 발생하지 않을 정도로 자원을 할당하는 방법에 대표적인 예로 은행원 알고리즘이 있다.
• 교착상태 검출 후 회복은 교착상태가 발생하면 프로세스를 강제 종료하거나 선점을 통해서 그 때 회복하는 방식이다.