OS - 교착 상태(Deadlock) 정리!

교착상태(Deadlock)

교착상태는 다중 프로그래밍 환경에서 나타날 수 있는 문제점으로, 2개 이상의 프로세스들이 자원을 점유한 상태에서 서로 다른 프로세스가 점유하고 있는 자원을 요구하며 무한정 기다리는 현상이다.

 

 

교착상태는 위와 같이 그림으로 표현할 수 있다.

 

프로세스1은 자원 A가 필요하다. 자원 A는 프로세스2에 의해 잠겨져있다.

프로세스2는 자원 B가 필요하다. 자원 B는 프로세스1에 의해 잠겨져있다.

 

즉, 어느 한 프로세스를 강제적으로 종료하지 않으면 컴퓨터가 정지된 것 처럼 어떤 작업도 수행할 수 없다.

 

발생 조건

교착상태의 발생 조건은 아래 4가지를 모두 만족하는 것이다. 하나라도 만족하지 않으면 절대로 데드락이 발생하지 않는다.

• 상호 배제(Mutual exclusion)
  • 한 리소스는 한 번에 한 프로세스만 사용할 수 있다.
• 점유와 대기(Hold and wait)
  • 어떤 프로세스가 하나 이상의 리소스를 점유하고 있으면서 다른 프로세스가 가지고 있는 리소스를 기다리고 있다.
• 비선점(No preemption)
  • 프로세스가 태스크를 마친 후 리소스를 자발적으로 반환할때까지 기다린다.(강제로 빼앗지 않는다)
• 환형 대기(Circular wait)
  • Hold and wait 관계의 프로세스들이 서로 기다린다.

 

교착상태의 대처 방안

교착상태의 대처 방안으로는 사전에 방지하거나, 회피하거나, 발생한 뒤에 회복하는 방법이 있다.

1. 방지
   • 할당 구조 측면에서, 교착상태가 발생할 수 있는 요구조건을 만족시키지 않게 한다.
2. 회피
   • 리소스 할당 측면에서, 교착상태가 발생할 가능성이 있는 자원 할당(unsafe allocation)을 하지 않는다
   • 대표적으로 은행원 알고리즘, 자원 할당 그래프가 있다.
3. 탐지 및 회복(Detection and Recovoery)
   • 교착상태가 발생할 수 있도록 두고 교착상태가 발생 할 경우 찾아내어 고친다.

 

교착상태 - 방지

앞에서 말했듯 교착상태를 방지하기 위해서는 4가지 조건중에 하나 이상을 불만족시키면 된다.

 

하지만 상호 배제, 점유와 대기, 비선점, 환형 대기 중 1가지 조건을 깨는 것은 쉽지 않다.

 

예)

 

1. 상호 배제를 깨면 여러 프로세스가 자원을 공유하게 되면서 의도치 않은 결과를 얻을 수 있다.

 

2. 점유와 대기를 깨면 자원이 오랫동안 할당되고 사용되지 않으면서 낭비될 수 있다.

 

3. 비선점을 깨면 공유 자원에 대한 동기화(상호 배제) 의미가 없어진다.

 

4.  환형대기가 그나마 부정 가능하다. 환형이 아니라, 선형대기로 만들어서 공유 자원 사이에 순서를 정해주는 방법이다.

 

교착상태 - 회피

교착상태 회피 기법은 교착상태를 피해가는 기법이다.

 

대표적으로 은행원 알고리즘(Banker's Algorithm)이 있다.

 

은행원 알고리즘은 "최소한 하나의 프로세스에게 할당해줄 만큼의 자원은 CPU가 보유하고 있어야 한다."의 개념이다.

 

즉,  교착 상태를 피하기 위해 시스템은 자원에 대한 2가지 상태를 가진다.

 

안전 상태 - 시스템이 교착상태를 일으키지 않으면서 모든 프로세스들이 완료될 수 있는 상태를 의미한다.

불안전 상태 - 교착상태가 발생할 수 있는 상태를 의미한다.

 

특정 프로세스가 자원을 요청했을 때, 시스템이 요청을 수락했을 때 불안전 상태에 빠진다면 해당 요청을 거절하는 방식이다.

 

하지만 이 방법 역시 단점이 여럿 존재한다.

• 자원 사용률이 굉장히 낮다. (안전상태를 유지해야 하므로)
• 프로세스는 최대 자원 요구량을 미리 파악해야 한다.
• 프로세스들은 자원을 반드시 순환시켜야 한다.
• 할당할 수 있는 자원의 수가 일정해야 한다.

 

교착상태 - 회복

교착상태 회복기법은 교착상태가 발생했을 때, 이를 탐지하고 해결하는 기법이다.

• 사용자가 직접 처리
  • 교착상태에 걸려있는 프로세스 중 하나를 사용자가 강제로 종료시켜 버린다.
• 시스템에 의한 처리
  • 프로세스 중지
    • 교착상태가 해결될 때까지 1개의 프로세스씩 중지 -> 탐지를 N번 해야 하므로, 프로세스가 많으면 오버헤드가 크다.
    • 교착상태에 속한 모든 프로세스 중지 -> 비용이 많이 발생한다.
  • 자원 선점
    • 교착상태에 빠진 프로세스들의 자원을 빼앗아서 해결될 때까지 다른 프로세스에게 할당해 준다.
    • 아래의 3가지 사항을 해결해야 한다.
      • 선점 프로세스 선택
        • 우선 순위 설계
      • 복귀
        • 자원을 잃은 프로세스를 안정상태로 복구
      • 기아
        • 비용에 근거한 선점은 계속 동일한 프로세스가 선택되어 재발할 수 있다.
        • 매번 결과가 다르도록 선점 횟수 등을 포함해야 한다.

 

 

감사합니다.

 

---

 

 

Reference: https://yabmoons.tistory.com/662