방송대/운영체제
7강. 교착상태(2)
monimoni
2025. 4. 7. 12:09
1. 교착상태 회피
- 프로세스의 자원 사용에 대한 사전 정보를 활용하여 교착상태가 발생하지 않는 상태에 머물도록 하는 방법
- 사전정보
- 현재 할당된 자원
- 가용상태의 자원
- 프로세스들의 최대 요구량
2. 안전상태와 안전 순서열
- 안전 상태 → 교착상태가 발생하지 않음
- 교착상태를 회피하면서 각 프로세스에 그들의 최대 요구량까지 빠짐없이 자원을 할당할 수 있는 상태
- 안전순서열이 존재하는 경우
- 불안전 상태
- 안전순서열이 존재하지 않는 경우
- 교착상태가 발생할 수 있음
3. 안전 순서열
- 순서가 있는 프로세스의 집합 <p1, p2, …, pn>
- 각 pi에 대해, pi가 추가로 요구할 수 있는 자원의 양이 현재 가용상태의 자원으로 충당되거나, 혹은 여기에 pj( 단, j < i )에 할당된 자원까지 포함하여 충당 가능한 경우
4. 교착상태 회피
- 교착상태는 불안전 상태에서만 발생 가능
- 항상 안전상태를 유지해야 함
- 프로세스가 가용상태의 자원을 요구하더라도 프로세스는 대기상태가 될 수 있음
- 자원 이용율은 다소 낮아질 수 있음
5. 교착상태 회피 알고리즘
- 각 자원의 단위자원이 하나밖에 없는 경우
- 변형된 자원할당 그래프 이용
- 각 자원의 단위자원이 여러 개일 수 있는 경우
- 은행원 알고리즘 이용
6. 각 자원의 단위자원이 하나밖에 없는 경우
- 변형된 자원할당 그래프
- 자원 정점에 표시하던 단위자원의 개수 제거
- 단위자원이 하나밖에 없기에 가능
- 선언간선(pi, rj) 추가
- 앞으로 프로세스 pi가 자원 rj를 요구하게 될 것임을 의미
- 요구간선과 구분을 위해 점선으로 표시
- 자원을 요구받으면 해당 선언간선을 요구간선으로 변경
- 그 요구간선을 할당간선으로 변환해도 사이클이 생기지 않는 경우에만 자원을 할당하고 할당간선으로 변환
- 자원 정점에 표시하던 단위자원의 개수 제거
7. 각 자원의 단위자원이 여러 개일 수 있는 경우
- 은행원 알고리즘
- 자원을 요구받으면 그 자원을 할당해 주고 난 후의 상태를 계산해서 그것이 안전상태인지 확인
- 안전상태가 보장되는 경우에만 자원을 할당
- 변수
- MAXᵢ : pᵢ의 최대요구
- ALLOCᵢ : pᵢ의 할당자원
- NEEDᵢ : pᵢ의 추가요구
- AVAIL : 가용자원
void bank(REQi) {
if (!(REQi <= NEEDi)) 오류;
if (!(REQi <= AVAIL)) pi 대기;
// 할당 후와 같은 상태를 만듬
ALLOCi = ALLOCi + REQi;
NEEDi = NEEDi - REQi;
AVAIL = AVAIL - REQi;
// 할당 후가 안전상태인지 조사
status = safe(상태 데이터);
if (status == true)
REQi 할당;
else
pi 대기 및 상태 데이터 복구;
}
// 안전 알고리즘
boolean safe(상태 데이터) {
WORK = AVAIL;
FINISH[i] = false; (i = 1, 2, ..., n)
for (l = 1; l <= n; l++) {
for (i = 1; i <= n; i++) {
if (FINISH[i] == false && NEEDi <= WORK) {
WORK = WORK + ALLOCi;
FINISH[i] = true;
break;
}
}
if (i > n) break;
}
if (모든 i에 대해 FINISH[i] == true)
return true;
else
return false;
}
8. 교착상태 탐지 및 복구
- 사후에 처리하는 방법
- 교착상태 탐지
- 시스템의 교착상태 여부를 조사하기 위해 주기적으로 상태 조사 알고리즘 수행
- 교착상태 복구
- 교착상태가 탐지된 경우 적절한 조치를 취해 정상상태로 복구
9. 교착상태 탐지
- Shoshani와 Coffman 알고리즘
- 현재 상태의 교착상태를 탐지
- 시간 복잡도 : O(mn²)
- 알고리즘 수행 시점
- 즉시 받아들일 수 없는 자원 요구가 있을 때
- 정해진 시간 간격
- CPU 효율이 일정 수준 이하로 떨어질 때
boolean detect(상태 데이터) {
WORK = AVAIL;
if (ALLOCA != 0) FINISH[i] = false;
else FINISH[i] = true; (i = 1, 2, ..., n)
for (l = 1; l <= n; l++) {
for (i = 1; i < n; i++) {
if (FINISH[i] == false && REQi <= WORK) {
WORK = WORK + ALLOCi;
FINISH[i] = true;
break;
}
}
if (i > n) break;
}
if (FINISH[i] == false인 i 존재)
return true;
else
return false;
}
10. 교착상태 복구
- 교착상태가 탐지되면 복구조치
- 복구의 주체
- 오퍼레이터 : 수작업으로 복구
- 운영체제 : 자동으로 복구
- 복구 방법
- 교착상태 프로세스를 종료
- 모든 교착상태 프로세스를 종료
- 단점 : 진행했던 내용에 대한 복원비용이 큼
- 사이클이 제거될 때까지 교착상태 프로세스를 하나씩 종료
- 단점 : 종료 대상을 선택하기 위한 비용, 매 프로세스 종료 후 교착상태 재확인을 위한 비용
- 모든 교착상태 프로세스를 종료
- 교착상태 프로세스가 할당받은 자원을 해제
- 사이클이 제거될 때까지 할당된 자원을 단계적으로 선점하여 다른 프로세스들에게 할당
- 프로세스와 자원 선택 기준
- 프로세스 진척도, 사용 중인 자원의 수 등
- 프로세스의 복귀 시점도 제반 요소를 고려하여 결정
- 기아상태에 빠지지 않도록 프로세스 선택 시 복구 횟수 고려
- 교착상태 프로세스를 종료
728x90