교착상태

교착상태(deadlock)

• 2개 이상의 프로세스가 서로 상대방의 작업이 끝나기만을 기다리고 있는 상태
• 결과적으로 아무도 완료되지 못함

교착상태의 필요조건

네 가지가 동시에 만족되어야만 교착상태가 발생할 확률이 생김.

• 상호배제 조건
• 점유 대기 조건
• 비선점 조건
• 환형 대기 조건

상호배제 조건

• 프로세스들이 자원에 대한 배타적인 통제권을 요구
• 적어도 하나 이상의 자원은 공동 사용될 수 없음
• 즉, 필요로 하는 자원을 다른 프로세스가 점유하고 있으면 반드시 대기해야함!

점유 대기 조건

• 프로세스가 자원을 점유하고 있는 상황에서 다른 프로세스가 점유하고 있는 자원이 해제되기를 기다리는 상황

비선점 조건

• 프로세스에 할당된 자원은 프로세스가 스스로 반환하기 전에 제거되지 않음
• 즉, 다른 프로세스에 의해 제거되지 않음

환형 대기 조건

프로세스의 자원 점유 및 점유된 자원의 요구 관계가 환형(원 모양)을 이루며 대기

자원할당 그래프 G = (V, E)

• 정점의 집합 V = P U R

  • P = { P1, P2, ... , Pn } : n개의 프로세스
  • R = { R1, R2, ... , Rm } : m개의 자원

• 방향 있는 간선의 집합 E = Q U S

  • 요구 간선 : 프로세스 Pi가 자원 Rj를 요구함
  • 할당 간선 : 자원 Rj가 프로세스 Pi에 할당됨

교착상태와의 관계

• 상호배제 조건 - 할당간선
• 점유 대기 조건 - 할당간선 (+ 요구간선)
• 비선점 조건 - 요구간선
• 환형 대기 조건 - 사이클(cycle)

TIP

• 자원할당 그래프에 사이클이 없으면? => 교착상태 발생 X
• 자원할당 그래프에 사이클이 존재하면? => 교착상태가 발생할 수도 있음

교착상태 방지

교착상태의 필요조건 중 하나라도 발생할 수 없도록 막음

• 상호배제 조건의 제거

  • 공유할 수 있는 자원: 상호배제와 무관
  • 공유할 수 없는 자원: 반드시 상호배제 해야 함

• 점유 대기 조건의 제거

  • 프로세스가 자원을 요청할 때 그 프로세스는 어떠한 자원도 할당받지 않은 상태여야 함
  • 점유 대기 조건 제거 방법
    1. 프로세스가 수행을 시작하기 전에 필요한 모든 자원을 한꺼번에 요구하여 할당받음 (자원 이용률이 매우 낮아질 수 있음)
    2. 자원을 부분적으로 요청하여 할당받을 수 있도록 하되, 자원을 추가로 요청할 때에는 이전에 가지고 있던 자원을 반드시 모두 해제한 후 할당받음 (기아상태가 발생할 수 있음)

• 비선점 조건의 제거

  • 비선점 조건 제거 방법
    • 방법 1
      1. 자원을 점유하고 있는 프로세스가 즉시 사용할 수 없는 상황의 다른 자원을 요청하는 경우 점유하고 있던 자원을 해제
    • 방법 2
      1. 프로세스가 가용하지 않은 자원을 요청
      2. 그 자원이 할당된 프로세스가 대기 중인지 조사
      3. 대기 중이면 대기상태인 프로세스로부터 자원을 선점하여 요청한 프로세스에게 할당. 대기중이 아니라면 요청한 프로세스는 대기

• 환형 대기 조건의 제거

  • 모든 자원의 유형에 일련번호를 지정하기 위해 함수 f 정의
  • 환형 대기 조건 제거 방법
    • 방법1: 프로세스는 자원을 일련번호 기준으로 항상 오름차순으로 요청.
      (즉, 자원 ri를 점유하고 있는 경우 반드시 f(ri) < f(rj)인 경우만 rj를 요청할 수 있음)
    • 방법2: 프로세스가 자원 rj 를 요구할 때 마다 f(rj <= f(ri)인 자원 ri는 모두 해제

TIP

함수 f의 정의는 전체 시스템의 성능에 큰 영향을 미치므로 실제로 사용되는 순서를 감안하여 정의해야 함

교착상태 회피

• 프로세스의 자원 사용에 대한 사전 정보를 활용하여 교착상태가 발생하지 않는 상태(안전상태) 하는 방법

용어 설명

사전 정보: 현재 할당된 자원, 가용상태의 자원, 프로세스들의 최대 요구량
안전 상태: 교착상태를 회피하면서 각 프로세스에게 그들의 최대 요구량까지 빠짐없이 자원을 할당할 수 있는 상태
(= 안전 순서열이 존재하는 상태)

• 안전 순서열
  • 순서 있는 프로세스의 집합 <p1, p2, ... , pn>
  • 각 pi에 대해, pi의 추가 요구 자원 소요량이 현재 가용 상태이거나 혹은 현재 가용인 자원에 pj(단, j < i)에 할당된 자원까지 포함하여 할당 가능한 경우

교착상태 회피 알고리즘

은행원 알고리즘

각 자원 유형의 단위자원이 여러 개일 경우

• 자원을 요청받으면 그 자원을 할당해 주고 난 후의 상태를 계산해서 그것이 안전상태가 보장되는 경우에만 자원을 할당

변형된 자원할당 그래프

각 자원 유형의 단위자원이 하나밖에 없는 경우

• 자원을 요청받으면 그 요구간선을 할당간선으로 변환하여도 사이클이 발생되지 않는 경우에만 자원을 할당

교착상태 탐지 및 복구

• 교착상태가 발생하면 이에 따른 적절한 조치를 취하여 정상 상태로 복구

교착상태 탐지

Shoshani와 Coffman 알고리즘

• 즉시 받아들일 수 없는 할당요구가 있을 때 사용
• 정해진 시간간격 또는 CPU 효율이 일정 수준 이하로 떨어질 때 사용

교착상태 복구

복구의 주체

• 오퍼레이터 : 교착상태 발생을 알려주면 수작업으로 복구
• 시스템 : 자동적으로 복구

복구의 방법

• 모든 교착상태의 프로세스를 종료 (단점: 그동안 진행했던 내용들에 대한 복원 비용이 큼)
• 사이클이 제거될 때까지 프로세스를 하나씩 종료 (단점: 종료 대상을 성택하기 위한 비용, 매번 교착상태 재확인을 위한 비용)

자원 회수

• 사이클이 제거될 때까지 자원을 단계적으로 선점하여 다른 프로세스들에 할당
• 고려사항: 희생자 선택, 복귀, 기아상태

복합적 접근방법

• 방지, 회피, 탐지 및 복구를 복합적으로 사용
  • 자원을 유형에 따라 계층적으로 분류
  • 각 계층에 대하여 자원순서를 부여
  • 각 계층별로 방지, 회피, 탐지 및 복구 중 적절한 방법을 적용