Deadlock & Starvation

Deadlock & Starvation

Deadlock

개념

• 교착 상태
• 두 개 이상의 작업이 서로 상대방의 작업이 끝나기를 기다려 아무것도 완료되지 못하는 상황
• 서로가 원하는 자원이 상대방에게 있어 업무가 진행되지 못하고 대기하는 상태

발생 조건

• 상호 배제
  • 하나의 프로세스가 사용 중일 때 다른 프로세스가 자원을 사용할 수 없다.
• 점유 대기
  • 하나 이상의 자원을 점유하면서 다른 프로세스가 사용 중인 자원을 추가로 사용하기 위해 대기하는 프로세스 존재
• 비선점
  • 다른 프로세스가 사용 중인 자원을 중간에 강제로 뺏어올 수 없다.
• 순환 대기
  • 프로세스 집합에서 순환 형태로 자원을 대기하고 있어야 한다.

예방

• 상호 배제 부정
  • 여러 프로세스가 공유 자원 사용
• 점유 대기 부정
  • 프로세스 실행 전 모든 자원 할당
• 비선점 부정
  • 점유 중인 자원을 다른 프로세스가 요구하는 경우 반납
• 순환 대기 부정
  • 자원에 고유 번호를 부여하고 순서대로 자원 요구
• 은행원 알고리즘
  • 프로세스가 자원을 요청할 때 자원 할당 후에도 안정된 상태를 유지하는지 미리 검사
  • 안정된 경우 자원을 할당해 주고 아닌 경우는 다른 프로세스가 자원 사용까지 대기한다.

회복

• 교착 상태의 프로세스 종료
  • 교착 상태가 제거될 때까지 프로세스 종료
• 할당된 자원 회수
  • 교착상태의 프로세스가 점유하고 있는 자원을 선점해 다른 프로세스에게 할당

대표적인 사례

• 식사하는 철학자
  • 원형 식탁에 철학자들이 둘러 앉고 그 사이에 포크를 두며, 왼쪽 포크를 기다리고, 오른쪽 포크를 기다려 식사하는 방식
  • 모든 철학자가 왼쪽 포크를 집으면 무한 대기 상태
  • 타임아웃을 사용하거나 철학자 중 한 명은 오른쪽 포크를 먼저 집게 하면 해결

Starvation

개념

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

교착 상태와의 차이

• deadlock은 서로 필요한 자원을 가지고 무한 대기 상태인 것인데, starvation은 다른 프로세스가 자원을 가지기 위해 경쟁할 때 특정 프로세스가 자원을 할당받지 못하는 상태이다.

Reference

[운영체제] 교착상태 (Deadlock) 및 기아상태(Starvation)