운영체제 - 교착 상태(Deadlock)

교착 상태(deadlock)

• 두 개 이상의 프로세스들이 서로가 가진 자원을 기다리며 중단된 상태
• 프로세스 A가 프로세스 B의 어떤 자원을 요청할 때 프로세스 B도 프로세스 A가 점유하고 있는 자원을 요청할 때 발생
  

교착 상태의 원인

• 아래 네 가지 조건이 모두 동시에 충족되어야 함
• 상호 배제 : 자원이 독점적으로 사용되며, 다른 프로세스가 그 자원을 사용할 수 없는 상태
• 점유 대기 : 특정 프로세스가 점유한 자원을 다른 프로세스가 요청하는 상태
• 비선점 : 다른 프로세스가 점유한 자원을 강제로 빼앗을 수 없는 상태
• 순환 대기 : 프로세스 간의 자원 요청이 서로 순환 구조를 이루어 사이클을 형성하는 상황

교착 상태의 해결 방법

교착 상태 예방 (Prevention)

• 교착 상태가 발생하지 않도록 네 가지 조건 중 하나 이상을 제거하는 방법
• 자원 관리에 엄격한 규칙을 적용하여 네 가지 교착 상태 조건이 성립하지 않도록 함

교착 상태 회피 (Avoidance)

• 자원 할당 시 시스템이 교착 상태에 빠지지 않을지 미리 예측하고, 안전한 경우에만 자원을 할당
• 은행원 알고리즘
  - 프로세스들이 자원을 요청할 때, 시스템이 안정적인 상태에서 자원을 할당할 수 있는지 판단하고, 안전한 경우에만 자원을 할당하여 교착 상태를 회피
  
  - 세 번째 고객이 25원이 아닌 45원을 요청하면, 남는 자원이 5원밖에 없어 나머지 고객의 요청을 해결해 줄 수 없어 교착 상태가 발생할 가능성이 있음

교착 상태 탐지 및 복구 (Detection and Recovery)

• 시스템 내에서 교착 상태가 발생했는지 주기적으로 검사
• 자원 할당 그래프나 매트릭스를 이용해 순환 고리를 확인
• 교착 상태가 발생하면, 관련된 프로세스를 종료하거나 자원을 해제하여 해결

교착 상태 무시 (Ignore)

• 교착 상태가 드물게 발생하는 경우, 이를 해결하는 것보다 무시하는 것이 더 효율적일 수 있음
• 현대 운영체제에서는 이 방법을 주로 사용
• 교착 상태가 발생하면 사용자가 직접 작업을 종료함
• 프로그램이 "응답 없음" 상태가 될 때 사용자가 강제로 프로그램을 종료하는 경우가 이에 해당

식사하는 철학자

• 교착상태 원인 : 5명 모두 왼쪽 포크를 가지고 오른쪽 포크를 요청하는 순환 대기
• 교착상태 해결 : 마지막 철학자만 오른쪽 포크를 먼저 잡고 왼쪽 포크를 잡도록 규칙을 수정
  
• 철학자 : 프로세스
• 포크 : 자원
• 스파게티 : 프로세스가 처리해야 하는 작업