[CS] 교착상태(Deadlock)와 기아상태(Starvation)

데드락(Deadlock, 교착 상태)이란?

• 운영체제에서 데드락(교착상태)이란, 시스템 자원에 대한 요구가 뒤엉킨 상태입니다. 즉, 둘 이상의 프로세스가 다른 프로세스가 점유하고 있는 자원을 서로 기다릴 때 무한 대기에 빠지는 상황을 일컫습니다.

데드락(Deadlock)의 발생조건

• 상호 배제
  • 한 번에 프로세스 하나만 해당 자원을 사용할 수 있다. 사용 중인 자원을 다른 프로세스가 사용하려면 요청한 자원이 해제될 때까지 기다려야 한다.
• 점유 대기
  • 자원을 최소한 하나 보유하고, 다른 프로세스에 할당된 자원을 점유하기 위해 대기하는 프로세스가 존재해야 한다.
• 비선점
  • 이미 할당된 자원을 강제로 빼앗을 수 없다(비선점).
• 순환 대기
  • 대기 프로세스의 집합이 순환 형태로 자원을 대기하고 있어야 한다.

데드락(Deadlock) 해결법

• 데드락이 발생하지 않도록 예방(prevention) 하기
• 데드락 발생 가능성을 인정하면서도 적절하게 회피(avoidance) 하기
• 데드락 발생을 허용하지만 데드락을 탐지(detection)하여, 데드락에서 회복하기

기아 상태(Starvation)란?

• 특정 프로세스의 우선 순위가 낮아서 원하는 자원을 계속 할당 받지 못하는 상태.

교착 상태와의 차이

• 교착상태는 프로세스가 자원을 얻지 못해 다음 처리를 하지 못하는 상태를 말하고 기아 상태는 프로세스가 원하는 자원을 계속 할당 받지 못하는 상태이다.
• 즉, 교착 상태는 여러 프로세스가 동일한 자원 점유를 원할 때 발생하고 기아 상태는 여러 프로세스가 자원을 점유하기 위해 경쟁 할 때 특정 프로세스는 영원히 자원 할당을 받지 못하는 것이다.

기아상태(Starvation) 해결 방안

• 우선순위 변경
  • 프로세스 우선순위를 수시로 변경해서, 각 프로세스가 높은 우선순위를 가질
    기회주기
  • 오래 기다린 프로세스의 우선순위를 높여주기
  • 우선순위가 아닌, 요청 순서대로 처리하는 FIFO 기반 요청큐 사용