교착상태 발견

교착상태 발견

• 예방 전략
  • 상당히 보수적인 방법
  • 교착상태가 발생하지 않도록 하기 위해 자원 접근에 대한 제한과 프로세스의 수행 제한
• 발견 전략
  • 좀 더 낙관적인 방법
  • 자원 접근에 대한 제한이나 프로세스의 행위에 제한 없음
  • 즉 자원 할당이 가능한 상황이면 항상 할당함
  • 단 주기적으로 시스템에 환형 대기 조건이 발생했는지 검사하고 발생하면 해결

교착상태 발견 알고리즘

• 자원할당이 요구될 때마다 수행 vs 주기적인 수행

  • 자원 할당이 요구될 때마다 매번 수행하면 빨리 교착 상태 발견 가능하고 알고리즘이 간단
  • 처리 비용이 더 많이 들 수 도 있다.

• 알고리즘

  • 할당 행렬 A, 가용 벡터 V, 요청 행렬 Q 사용

  • Qij는 프로세스 i에 의해 요청된 자원 j의 개수

  • 교착상태가 아닌 프로세스들을 찾아 표시 (mark)

  • 초기에는 모든 프로세들이 표시되어 있지 않는다.

  • 알고리즘 실행

    1. 할당 행렬에서 행의 값이 모두 0 인 프로세스를 우선 표시
    2. 임시 벡터 W를 만들고 현재 사용 가능한 자원의 개수 (가용 벡터의 값)를 벡터 W의 초기값으로 설정
    3. 표시되지 않은 프로세스들 중에서 요청 행렬 Q의 특정 행 값이 모두 W보다 작은 프로세스를 찾음. 즉 Qik <= Wk (1 <= k <= m) 인 i를 찾고 프로세스 i를 표시. 만일 이러한 프로세스가 없으면 알고리즘 종료
    4. 단계 3의 조건을 만족하는 행을 Q에서 찾았다면, 할당 행렬에서 그 행에 대응되는 값으로 W를 갱신. Wk = Wk + Aik (1 <= k <= m)을 수행한다. 그리고 3단계를 다시 수행

  • 이 알고리즘이 종료된 이후에도 mark되지 않은 프로세스가 존재한다면, 교착상태가 발생

  • 이 알고리즘의 원리는 우선 현재 가용 자원으로 수행이 완료될 수 있는 프로세스를 찾고 그런 프로세스가 있다면 그 프로세스가 완료된 이후 반납할 자원을 가용 자원에 추가.

  • 그리고 다시 이 가용 자원으로 수행이 완료될 수 있는 프로세스를 찾음

  • 이와 같은 과정을 반복한 후 알고리즘이 종료 되었을 때, 모든 프로세스가 완료되면 교착상태가 없는 것이고, 그렇지 않으면 교착상태가 있는 것임

• 단점

  • 현재 교착상태의 존재 여부만 파악할 뿐, 이후에 더 진행되면 교착상태가 생길지 여부는 모른다.

• 수행 예시
  

  

  1. P4는 할당 받은 자원이 없다. P4 Mark
  2. W = (0, 0, 0, 0, 1) 로 초기화
  3. P3의 요청을 W가 만족할 수 있기 때문에 P3를 Mark하고 W = W + (0,0,0,1,0) 을 수행 => W = (0,0,0,1,1) 이 된다.
  4. 표시가 되지않은 프로세스들 중에서 W로 요청을 만족할 수 있는 프로세스가 더이상 없음 => 알고리즘 종료
  5. 알고리즘 종료 후에 P1과 P2가 표시되지 않은 상태로 남아 있으며, 결국 P1과 P2가 교착상태에 있음을 발견할 수 있다.

교착상태 회복 알고리즘

• 교착상태에 포함되어 있는 모든 프로세스를 중지시킴 => Victim이 발생
  • 실제 많은 운영체제에서 채용하고 있는 방법중 하나
• 교착상태에 포함되어 있는 각 프로세스의 수행을 롤백시킴, 미리 정의된 특정 체크포인트 시점까지 되돌린 후 재수행
  • 단점 : 재수행시 다시 교착상태 발생 가능, 병행 처리의 비결정인 특성으로 인해 가능성은 낮다.
• 교착상태가 없어질 때 까지 교착상태에 포함되어 있는 프로세스들을 하나씩 종료
  • Victim의 선택은 비용이 가장 적은 것 부터
  • 하나씩 종료시킨 후, 교착상태 발견 알고리즘을 다시 수행시키면 아직 교착상태가 존재하는지 확인할 수 있음
• 교착 상태가 없어질 때 까지 교착상태에 포함되어 있는 자원부터 하나씩 선점시킴
  • 비용이 가장 적은 자원부터
  • 하나씩 선점시키고 교착상태 발견 알고리즘을 수행하여 교착상태 여부를 확인
  • 자신의 자원을 선점당한 프로세스는 자원 할당 전의 시점으로 롤백, 그 시점부터 다시 실행