[운영체제] 교착상태

• 교착상태 회피
  • 프로세스의 자원 사용에 대한 사전 정보를 활용하여 교착상태가 발생하지 않는 상태에 머물도록 하는 방법
    • 사전 정보: 현재 할당된 자원, 가용상태의 자원, 프로세스들의 최대 요구량
  • 프로세스의 상태 영역
    • 안전상태
      • 교착상태를 회피하면서 각 프로세스에게 그들의 최대 요구량까지 빠짐없이 자원을 할당할 수 있는 상태
      • 안전 순서열이 존재
    • 불안전상태
      • 교착상태
      • 안전 순서열이 존재하지 않음
  • 안전 순서열
    • 순서 있는 프로세스의 집합<p1, p2, ..., pn>
    • 각 pi에 대해 pi가 추가로 요구할 수 있는 자원 소요량이 현재 가용 상태이거나 혹은 현재 가용인 자원에 pj(단, j<i)에 할당된 자원까지 포함하여 할당 가능한 경우
  • 교착상태는 불안전상태에서 발생
    • 불안전상태: 할당 과정에 따라 교착상태가 될 수도 있는 상태
  • 프로세스가 가용상태의 자원을 요구하더라도 상전상태를 유지하기 위해 프로세스는 대기상태가 될 수 있음
  • 교착상태 회피 알고리즘
    • 각 자원 유형의 단위자원이 여러 개일 경우
      • 은행원 알고리즘
        • 자원을 요청받으면 그 자원을 할당해주고 난 후의 상태를 계산해서 그것이 안전상태가 보장되는 경우에만 자원을 할당
          • AVAIL: 가용자원
          • MAXi: pi의 최대요구
          • ALLOC: pi의 할당자원
          • NEEDi: pi의 추가요구 
        • 시간복잡도: O(mn^2)

 

•  
  •  각 자원 유형의 단위자원이 하나밖에 없는 경우
    • 변형된 자원할당 그래프
      • 할당간선(rj, pj):  자원 rj가 프로세스 pj에 할당됨
      • 요구간선(pi, rj): 프로세스 pi가 자원 rj를 요구함
      • 선언간선(pi, rj): 앞으로 프로세스 pi가 자원 rj를 요구하게 될 것임
      • 자원을 요청받으면 그 요구간선을 할당간선으로 변환하여도 사이클이 발생되지 않는 경우에만 자원을 할당

 

 

• 교착상태 탐지 및 복구
  • 교착상태 탐지
    • 시스템의 교착상태 여부를 탐지하기 위해 주기적으로 상태 조사 알고리즘을 수행
    • Shoshani와 Coffman 알고리즘
      • 알고리즘 수행시점
        • 즉시 받아들일 수 없는 할당요구가 있을 때
        • 정해진 시간간격 또는 CPU효율이 일정수준 이하로 떨어질 때

 

•  
  • 교착상태 복구
    • 교착상태가 탐지된 경우 복구조치에 들어감
    • 복구의 주체
      • 오퍼레이터: 교착상태 발생을 알려주면 수작업으로 복구
      • 시스템: 자동적으로 복구
    • 복구의 방법
      • 교착상태 프로세스를 종료
      • 교착상태 프로세스로부터 자원을 회수
    • 프로세스 종료
      • 모든 교착상태 프로세스를 종료
        • 단점: 그동안 진행했던 내용들에 대한 복원 비용이 큼
      • 사이클이 제거될 때까지 프로세스를 하나씩 종료
        • 단점: 종료 대상을 선택하기 위한 비용, 매번 교착상태 재확인을 위한 비용
    • 자원 회수
      • 사이클이 제거될 때까지 자원을 단계적으로 선점하여 다른 프로세스들에 할당
      • 고려사항: 희생자 선택, 복귀, 기아상태
• 복합적 접근방법
  • 방지, 회피, 탐지 및 복구를 복합적으로 사용
    • 자원을 유형에 따라 계층적으로 분류
    • 각 계층에 대하여 자원순서를 부여
    • 각 계층별로 방지, 회피, 탐지 및 복구 중 적절한 방법을 적용