교착상태

교착상태 (deadlock)

• 여러 개의 프로세스가 서로 상대방의 작업이 끝나기만 기다리고 있어 어느 쪽도 영원히 진행하지 못하는 상태

교착상태의 필요조건

• 상호배제
• 점유대기
• 비선점
• 환형대기
• 네 가지 조건이 동시에 만족될 때 교착상태 발생 가능

자원할당 그래프

• 프로세스와 자원 사이에 요구와 할당 관계를 나타내는 그래프
• 프로세스=p, 자원=r, r 위의 숫자=단위자원
• 사이클의 존재 유무를 통해 교착상태 발생 가능성을 확인할 수 있다.

교착상태 예방

• 교착상태의 네 가지 필요조건 중 어느 하나라도 발생할 수 없도록 막는 방법

상호배제 조건 제거

• 공유할 수 없는 자원(ex. 프린터)은 반드시 상호배제가 필요하므로 조건 제거 불가능

점유대기 조건 제거

자원을 점유했을 떄 대기하지 않거나 점유하지 않아야 함

• 대기하지 않는 방법
  • 프로세스가 필요한 모든 자원을 처음에 한꺼번에 요구하여 할당받음
  • 자원이용률 낮아짐, 기아상태 가능
• 점유하지 않는 방법
  • 새로운 자원을 요구할 때 할당받았던 자원을 모두 해제
  • 점유 도중 해제할 수 없는 자원에는 적용 불가

비전점 조건 제거

• 자원에 특성에 따라 적용 불가능한 자원 존재 (ex. 프린터)

환형대기 조건 제거

• 모든 자원에 일련번호 지정하는 방법
• 점유대기 중인 프로세스는 점유 중인 자원의 일련번호보다 대기 중인 자원의 일련번호가 크므로 환형 대기 발생 불가능
• 프로세스마다 요구 순서가 다를 수 있어 일련번호 설정 어려움
• 요구순서가 일련번호 오름차순을 못 지키면 점유자원의 해제가 필요하나 적용 불가능한 자원이 존재

교착상태 회피

• 프로세스의 자원 사용에 대한 사전 정보를 활용하여 교착상태가 발생하지 않는 상태에 머물도록 하는 방법
• 사전 정보
  • 현재 할당된 자원
  • 가용상태의 자원
  • 프로세스들의 최대 요구량

안전순서열

• 순서 있는 프로세스의 집합
• 각 프로세스가 추가로 요구할 수 있는 자원의 양이 현재 가용상태의 자원으로 충당되거나, 다른 프로세스에 할당된 자원까지 포함하여 충당 가능한 경우

안전상태와 불안전상태

• 안전상태 : 안전순서열이 존재하는 경우
• 불안전상태 : 안전순서열이 존재하지 않는 경우
• 교착상태는 불안전상태에서만 발생 가능

교착상태 회피 알고리즘

• 변형된 자원할당 그래프
  • 선언간선 : 앞으로 프로세스 p가 자원 r을 요구하게 될 것을 점선으로 표시 (p→r)
  • 자원을 요구받으면 해당 선언간선을 요구간선으로 변경
  • 그 요구간선을 할당간선으로 변환(r→p)해도 사이클이 생기지 않는 경우에만 자원을 할당하고 할당간선으로 변환

교착상태 탐지

• Shoshani와 Coffman 알고리즘
• 시간복잡도 : O(mn²)

교착상태 복구

• 교착상태 프로세스를 종료
  • 모든 교착상태 프로세스 종료 : 진행했던 내용에 대한 복원 비용이 큼
  • 사이클이 제거될 때까지 교착상태 프로세스를 하나씩 종료 : 종료 대상을 선택하기 위한 비용, 매 프로세스 종료 후 교착상태 재확인을 위한 비용
• 교착상태 프로세스가 할당받은 자원을 해제
  • 사이클이 제거될 때까지 할당된 자원을 단계적으로 선점하여 다른 프로세스들에 할당