Index
1. 교착상태 회피
•
자원 사용에 대한 사전 정보를 활용하여 교착상태가 발생하지 않는 상태(안전상태) 에 머물도록 하는 방법
•
사전 정보
◦
현재 할당된 자원
◦
가용 상태의 자원
◦
프로세스들의 최대 요구량
1.1. 안전상태와 안전순서열
•
안전상태
◦
교착상태를 회피하면서 각 프로세스에 그들의 최대 요구량까지 빠짐없이 자원을 할당할 수 있는 상태
◦
안전 순서열이 존재하는 경우
•
불안전상태
◦
안전순서열이 존재하지 않는 경우
◦
교착상태가 발생 가능
1.2. 안전순서열
•
순서가 있는 프로세스의 집합 <p1, p2, p3, …. pn>
•
각 pi에 대해 pi가 추가로 요구할 수 있는 자원의 양이 현재 가용상태의 자원으로 충당되거나,
혹은 여기에 pj( 단, j < i)에 할당된 자원까지 포함하여 충당 가능한 경우
•
예시
◦
안전순서열: <p2, p3, p1>
•
예시 2
◦
불안전상태
◦
p1에게 자원을 할당하지 않음으로서 불안전상태(교착) 회피
▪
안전순서열: <p2, p3, p1>
1.3. 교착상태 회피
•
교착상태는 불안전상태에서만 발생 가능
•
항상 안전상태를 유지해야 함
•
프로세스가 가용상태의 자원을 요구하더라도 프로세스는 대기상태가 될 수 있음
◦
자원이용률은 다소 낮아질 수 있음
1.4. 교착상태 회피 알고리즘
•
각 자원의 단위자원이 하나밖에 없는 경우
◦
변형된 자원할당 그래프 이용
◦
요구간선을 할당간선으로 바꾸어도 사이클이 생기지 않는 안전상태일 경우에만 자원 요구를 수용
•
각 자원의 단위자원이 여러개 인 경우
◦
은행원 알고리즘 사용
◦
프로세스가 요구한 자원을 할당해 줄 경우에도 안전순서열이 존재하는지 검사하여 자원 요구의 수용 여부를 결정
1.5. 교착상태 회피 알고리즘 (1) -각 자원의 단위자원이 하나밖에 없는 경우
•
변형된 자원할당 그래프
◦
자원 정점에 표시하던 단위 자원 개수 제거
◦
선언간선 (Pi, Rj) 추가
▪
앞으로 프로세스 Pi가 자원 Rj를 요구하게 될 것임
▪
요구간선과 구분을 위해 점선으로 표시
•
프로세스
◦
자원을 요구받으면 해당 선언간선을 요구간선으로 변경
◦
그 요구간선을 할당간선으로 변환해도 사이클이 생기지 않는 경우에만 자원을 할당하고 할당간선으로 변환
1.6. 교착상태 회피 알고리즘 (2) - 각 자원의 단위자원이 여러개 인 경우
•
은행원 알고리즘
◦
자원을 요구받으면 그 자원을 할당해주고 난 후의 상태를 계산해서 그것이 안전상태인지 확인
◦
안전상태가 보장되는 경우에만 자원을 할당
◦
수도코드
•
예시
◦
초기 설정 값
◦
안전상태 예시 (1)
◦
안전상태 예시 (2)
◦
불안전상태 예시
2. 교착상태 탐지 및 복구
교착상태 회피는 많은 비용이 듦.
일단 교착상태를 발생시키고, 이후에 상태를 탐지하여 복구하는것이 어떨지?
2.1. 교착상태 탐지 및 복구
•
사후에 처리하는 방법
◦
교착상태가 발생했는가를 탐지한 후, 희생자를 선택하여 해당 프로세스를 중지시키거나 자원을 선점하는 방법
•
교착상태 탐지
◦
시스템의 교착상태 여부를 조사하기 위해 주기적으로 상태 조사 알고리즘 수행
•
교착상태 복구
◦
교착상태가 탐지된 경우 적절한 조치를 취해 정상상태로 복구
2.2. 교착상태 탐지
•
Shoshani와 Coffman 알고리즘
◦
시간복잡도 O(mn^2)
◦
수도 코드
•
알고리즘 수행 시점
◦
즉시 받아들일 수 없는 자원 요구가 있을 때
◦
정해진 시간 간격
◦
CPU 효율이 일정 수준 이하로 떨어질 때
•
예시 1 - 교착상태 아님
•
예시 2 - 교착상태
◦
P1, P2 에 대한 복구 작업 필요
2.3. 교착상태 복구
•
교착상태가 탐지되면 복구
•
복구의 주체
◦
오퍼레이터: 수작업으로 복구
◦
운영체제: 자동으로 복구
•
복구 방법
◦
교착상태 프로세스를 종료
◦
교착상태 프로세스가 할당받은 자원을 해제
2.4. 교착상태 복구 방법 (1) - 교착상태 프로세스 종료
1.
모든 교착상태 프로세스를 종료
•
단점: 진행했던 내용에 대한 복원 비용이 큼
2.
사이클이 진행될 때까지 교착상태 프로세스를 하나씩 종료
•
단점: 종료 대상을 선택하기 위한 비용
◦
매 프로세스 종료 후 교착상태 재확인을 위한 비용
2.5. 교착상태 복구 방법 (2) - 교착상태 프로세스가 할당 받은 자원 해제
•
사이클이 제거될때까지 할당된 자원을 단계적으로 선점하여 다른 프로세스에 할당
•
프로세스와 자원 선택 기준
◦
프로세스 진척도, 사용 중인 자원의 수 등
•
프로세스의 복귀 시점도 제반 요소를 고려하여 결정
•
기아상태에 빠지지 않도록 프로세스 선택시 복구 횟수 고려