💡해당 게시글은 방송통신대학교 김진욱 교수님의 '운영 체제' 강의를 개인 공부 목적으로 메모하였습니다.

학습 개요

교착 상태의 필요 조건은 제거하지 못하는 경우도 있고 제거할 수는 있지만 자원 이용률이 낮아지는 경우도 있음
특히 환 형 대기 조건을 제거하는 방법은 적용에 어려움이 존재함
교착 상태를 처리하는 다른 기법
- 교착 상태 회피는 안전 순서 열이라는 개념을 이용하여 교착 상태를 피하는 방법임
- 교착 상태 탐지 및 복구는 교착 상태가 발생하면 사후 처리를 하는 방법임
교착 상태를 회피하는 방법을 자세히 알아보고, 교착 상태를 탐지 및 복구하는 방법에 대해서도 살펴봄

학습 목표

교착 상태를 회피하는 방법을 설명할 수 있음
교착 상태를 탐지하고 복구하는 방법을 설명할 수 있음

강의록

교착 상태 회피

프로세스의 자원 사용에 대한 사전 정보를 활용하여 시스템이 교착 상태가 발생하지 않는 상태에 머물도록 하는 방법
사전 정보
- 현재 할당된 자원
- 가용 상태의 자원
- 각 프로세스들의 최대 자원 요구량

안전 상태와 안전 순서열

안전 상태
- 교착 상태가 발생하지 않음
- 교착 상태를 회피하면서 각 프로세스에 그들의 최대 요구량까지 빠짐 없이 자원을 할당할 수 있는 상태
- 안전 순서 열이 존재하는 경우
불안전 상태
- 안전 순서 열이 존재하지 않는 경우
- 불 안전 상태가 반드시 교착 상태를 의미하는 것은 아니지만 교착 상태로 이어질 가능성이 있는 상태임

안전 순서 열

순서 있는 프로세스의 집합 <p₁, p₂, …, pₙ>
각 pᵢ 에 대해, pᵢ 가 추가로 요구할 수 있는 자원의 양이 현재 가용 상태의 자원으로 충당되거나 혹은 여기에 pⱼ(단, j< i)에 할당 된 자원까지 포함하여 충당 가능한 경우
안전 순서 열이 존재하면 시스템은 안전 상태
시스템 상태
- 자원 r₁
  - 단위 자원 8개
- 프로세스 p₁
  - 프로세스가 종료될 때 까지 필요한 자원 최대 요구량 5개
- 프로세스 p₂
  - 프로세스가 종료될 때 까지 필요한 자원 최대 요구량 2개
- 프로세스 p₃
  - 프로세스가 종료될 때 까지 필요한 자원 최대 요구량 8개
시각 T₁ 상태
- p₁ 단위 자원 할당 X, p₂ 단위 자원 할당 1개. p₃ 단위 자원 할당 5개, r₁ 가용 가능한 단위 자원 2개
- p₁ 종료 되기 위해 단위 자원 5개 더 필요, p₂ 종료 되기 위해 단위 자원 1개 더 필요, p₃ 종료 되기 위해 단위 자원 3개 더 필요
  1. p₂에게 r₁의 가용 가능한 단위 자원 1개 할당 → 종료 후 2개 반환 → r₁ 가용 가능한 단위 자원 3개
  2. p₃에게 r₁의 가용 가능한 단위 자원 3개 할당 → 종료 후 8개 반환 → r₁ 가용 가능한 단위 자원 8개
  3. p₁에게 r₁의 가용 가능한 단위 자원 5개 할당
- 안전 순서 열 p₂ → p₃ → p₁
시각 T₂ 상태
- p₁ 단위 자원 할당 X, p₂ 단위 자원 할당 1개. p₃ 단위 자원 할당 5개, r₁ 가용 가능한 단위 자원 2개
- p₁ 단위 자원 1개 할당 요청 → r₁의 가용 가능한 단위 자원은 2개 이므로 1개 할당 → r₁ 가용 가능한 단위 자원 1개
  1. p₂에게 r₁의 가용 가능한 단위 자원 1개 할당 → 종료 후 2개 반환 → r₁ 가용 가능한 단위 자원 2개
  2. p₁ 이 필요한 자원은 4개, p₃는 3개지만 r₁의 가용 가능한 단위 자원 2개이므로 할당 불가능
- 안전 순서 열 p₂ → X → 불안전 상태
시각 T₂ 상태(교착 상태 회피)
- p₁ 단위 자원 할당 X, p₂ 단위 자원 할당 1개. p₃ 단위 자원 할당 5개, r₁ 가용 가능한 단위 자원 2개
- p₁ 단위 자원 1개 할당 요청 → r₁은 요구 간선 그대로 내버려 두고 할당하지 않음 → 그 후 안전 순서 열 계산
- p₁ 종료 되기 위해 단위 자원 5개 더 필요, p₂ 종료 되기 위해 단위 자원 1개 더 필요, p₃ 종료 되기 위해 단위 자원 3개 더 필요
  1. p₂에게 r₁의 가용 가능한 단위 자원 1개 할당 → 종료 후 2개 반환 → r₁ 가용 가능한 단위 자원 3개
  2. p₃에게 r₁의 가용 가능한 단위 자원 3개 할당 → 종료 후 8개 반환 → r₁ 가용 가능한 단위 자원 8개
  3. p₁에게 r₁의 가용 가능한 단위 자원 5개 할당
- 안전 순서 열 p₂ → p₃ → p₁

교착 상태 회피

교착 상태는 불안전 상태에서만 발생 가능
항상 안전 상태를 유지해야 함
프로세스가 가용 상태의 자원을 요구하더라도 프로세스는 대기 상태가 될 수 있음
- 자원 이용율은 다소 낮아질 수 있음

교착 상태 회피 알고리즘

각 자원의 단위 자원이 하나 밖에 없는 경우
- 변형 된 자원 할당 그래프 이용
각 자원의 단위 자원이 여러 개 일 수 있는 경우
- 은행원 알고리즘 이용

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

변형 된 자원 할당 그래프
- 자원 정점에 표시하던 단위 자원의 개수 제거
선언 간선 (pᵢ, rⱼ) 추가
- 앞으로 프로세스 pᵢ가 자원 rⱼ를 요구하게 될 것임
  - 각각의 프로세스가 종료하기 위해 추가적으로 요청할 자원이 있음을 나타냄
- 요구 간선과 구분을 위해 점선으로 표시
자원을 요구 받으면 해당 선언 간선을 요구 간선으로 변경
그 요구 간선을 할당 간선으로 변환해도 사이클이 생기지 않는 경우에만 자원을 할당하고 할당 간선으로 변환
ex) p₁이 r₂를 요구하는 경우
1. 프로세스 p₁가 자원 r₂를 요청하면, 선언 간선 p₁ → r₂를 요청 간선 p₁ → r₂(실선)으로 변경함
2. 이 요청 간선을 할당 간선 r₂ → p₁ 로 변환(즉, 자원을 할당)했을 때, 그래프에 사이클이 생기지 않는 경우에만 실제로 자원을 할당하고 할당 간선으로 변경함
3. 사이클이 생긴다면, 자원을 할당하지 않고 프로세스는 대기함
  - 불안전 상태 초래 가능성 방지
ex) p₂가 r₂를 요구하는 경우
1. 프로세스 p₂가 자원 r₂를 요청하면, 선언 간선 p₂ → r₂를 요청 간선 p₂ → r₂(실선)으로 변경함
2. 이 요청 간선을 할당 간선 r₂ → p₂로 변환했을 때 그래프 상에서 사이클이 생기김
3. 불안정 상태를 방지하기 위해 자원을 할당하지 않고 프로세스 대기

각 자원의 단위 자원이 여러 개 일 수 있는 경우

은행원 알고리즘
- 자원을 요구 받으면 그 자원을 할당해 주고 난 후의 상태를 계산해서 그것이 안전 상태인지 확인
- 안전 상태가 보장 되는 경우에만 자원을 할당
ex)
- p₁의 할당 자원 0, 최대 요구량 5, 추가 요구량 5
- p₂의 할당 자원 1, 최대 요구량 2, 추가 요구량 1
- p₃의 할당 자원 5, 최대 요구량 8, 추가 요구량 3
- r₁의 가용 자원 2
ex)
- p₁의 할당 자원 r₁ 0 ,r₂ 2, 최대 요구량 r₁ 7, r₂ 5, 추가 요구량 r₁ 7, r₂ 3
- p₂의 할당 자원 r₁ 1 ,r₂ 5, 최대 요구량 r₁ 3, r₂ 6, 추가 요구량 r₁ 1, r₂ 5
- p₃의 할당 자원 r₁ 4 ,r₂ 1, 최대 요구량 r₁ 8, r₂ 8, 추가 요구량 r₁ 4, r₂ 1
- r₁의 가용 자원 3, r₂의 가용 자원 3
  1. 새로운 변수 WORK 에 현재 상태에서 가용할 수 있는 자원 AVAIL 값 복사
  2. 각 프로세스마다 FINISH 값 false로 설정
    - 프로세스가 종료되지 않았다는 의미
  3. WORK 값을 할당 해 NEED 값을 할당 할 수 있는 프로세스 체크
    - p₂한테 자원 할당 후 p₂가 종료 된 후 반환 된 1, 5 값 WORK 값에 추가
  4. WORK 값 4, 8을 이용해 NEED 값 할당 할 수 있는 프로세스 체크
    - p₃한테 자원 할당 후 p₃가 종료 된 후 반환 된 4, 1 값 WORK 값에 추가
  5. WORK 값 8, 8을 이용해 NEED 값 할당 할 수 있는 프로세스 체크
    - p₁한테 자원 할당 후 p₁가 종료 된 후 반환 된 0, 2 값 WORK 값에 추가
  6. 모든 프로세스 상태 FINISH = true 이므로 안전 상태가 되므로 자원 할당해줌
- p₁의 할당 자원 r₁ 0 ,r₂ 2, 최대 요구량 r₁ 7, r₂ 5, 추가 요구량 r₁ 7, r₂ 3
- p₂의 할당 자원 r₁ 1 ,r₂ 5, 최대 요구량 r₁ 3, r₂ 6, 추가 요구량 r₁ 1, r₂ 5
- p₃의 할당 자원 r₁ 4 ,r₂ 1, 최대 요구량 r₁ 8, r₂ 8, 추가 요구량 r₁ 4, r₂ 1
- r₁의 가용 자원 3, r₂의 가용 자원 3
  1. p₁이 단위 자원 r₁ 1 ,r₂ 1 요구함 → 바로 할당하지 않고 상태 계산 먼저 함
  2. ALLOC₁에 r₁ 1 ,r₂ 1 자원 할당 → NEED₁ r₁ 6, r₂ 4로 감소
  3. AVAIL r₁ 1 ,r₂ 1 감소 해 r₁ 2 ,r₂ 2로 저장
  4. 새로운 변수 WORK 에 현재 상태에서 가용할 수 있는 자원 AVAIL 값 복사
  5. 각 프로세스마다 FINISH 값 false로 설정
    - 프로세스가 종료되지 않았다는 의미
  6. WORK 값을 할당 해 NEED 값을 할당 할 수 있는 프로세스 체크
    - p₂한테 자원 할당 후 p₂가 종료 된 후 반환 된 1, 5 값 WORK 값에 추가
  7. WORK 값 3, 7을 이용해 NEED 값 할당 할 수 있는 프로세스 체크
    - 할당 할 수 있는 프로세스 존재 하지 않음 → 불안전 상태
  8. REQ₁에 가용할 자원이 있지만 불안정 상태가 되기 때문에 자원을 할당하지 않음
- p₁의 할당 자원 r₁ 0 ,r₂ 2, 최대 요구량 r₁ 7, r₂ 5, 추가 요구량 r₁ 7, r₂ 3
- p₂의 할당 자원 r₁ 1 ,r₂ 5, 최대 요구량 r₁ 3, r₂ 6, 추가 요구량 r₁ 1, r₂ 5
- p₃의 할당 자원 r₁ 4 ,r₂ 1, 최대 요구량 r₁ 8, r₂ 8, 추가 요구량 r₁ 4, r₂ 1
- r₁의 가용 자원 3, r₂의 가용 자원 3
  1. p₃이 단위 자원 r₁ 1 ,r₂ 1 요구함 → 바로 할당하지 않고 상태 계산 먼저 함
  2. ALLOC₁에 r₁ 1 ,r₂ 1 자원 할당 → NEED₁ r₁ 3, r₂ 6로 감소
  3. AVAIL r₁ 1 ,r₂ 1 감소 해 r₁ 2 ,r₂ 2로 저장
  4. 새로운 변수 WORK 에 현재 상태에서 가용할 수 있는 자원 AVAIL 값 복사
  5. 각 프로세스마다 FINISH 값 false로 설정
    - 프로세스가 종료되지 않았다는 의미
  6. WORK 값을 할당 해 NEED 값을 할당 할 수 있는 프로세스 체크
    - p₂한테 자원 할당 후 p₂가 종료 된 후 반환 된 1, 5 값 WORK 값에 추가
  7. WORK 값 3, 7을 이용해 NEED 값 할당 할 수 있는 프로세스 체크
    - p₃한테 자원 할당 후 p₃가 종료 된 후 반환 된 5, 2 값 WORK 값에 추가
  8. WORK 값 8, 9을 이용해 NEED 값 할당 할 수 있는 프로세스 체크
    - p₁한테 자원 할당 후 p₁가 종료 된 후 반환 된 0, 2 값 WORK 값에 추가
  9. 모든 프로세스 상태 FINISH = true 이므로 안전 상태가 됨
  10. 안전 순서열 p₂ → p₃ → p₁으로 안전 상태가 되므로 자원 할당해줌

은행원 알고리즘: 의사 코드

  
// 자원 요청 처리 함수 (pᵢ가 자원 REQᵢ를 요청)
void bank(REQᵢ) {
  // 요청량 <= 최대 필요량 확인
  if (!(REQᵢ <= NEEDᵢ)) { 오류 처리; }
  // 요청량 <= 현재 가용량 확인
  if (!(REQᵢ <= AVAIL)) { pᵢ 대기; }

  // 할당 후와 같은 상태를 만듦
  ALLOCᵢ = ALLOCᵢ + REQᵢ;
  NEEDᵢ = NEEDᵢ - REQᵢ;
  AVAIL = AVAIL - REQᵢ;

  // 할당 후가 안전 상태인지 (안전성 알고리즘 호출)
  status = safe(상태 데이터);

  // 안전하면 실제 할당, 아니면 원상 복구 후 대기
  if (status == true) {
	   REQᵢ 할당;
  } else {
    pᵢ 대기 및 상태 데이터 복구;
  }
}

// 안전성 알고리즘 (현재 상태가 안전한지 검사)
boolean safe(상태 데이터) {
  WORK = AVAIL; // 작업용 가용 자원 벡터
  FINISH[i]=false;(i=1,2,…,n)  // 각 프로세스 종료 여부 (n개)

	for(l=1; l<=n; l++) {
	  for(i=1; i<=n; i++)
	    if(FINISH[i]==false && NEEDᵢ <= WORK ) {
			    WORK = WORK + ALLOCᵢ;
			    FINISH[i] = true;
			    break;
		    }
	    if (i > n) break;
    }
  // 모든 프로세스가 종료될 수 있으면(모든 FINISH[i]가 true) 안전상태
  if (모든 i에 대해 FINISH[i] == true) {
    return true;
  } else {
    return false; // 안전 순서열 찾기 실패 -> 불안전상태
  }
}

교착 상태 탐지 및 복구

사후에 처리하는 방법
교착 상태 탐지
- 시스템의 교착 상태 여부를 조사하기 위해 주기적으로 상태 조사 알고리즘 수행
교착 상태 복구
- 교착 상태가 탐지된 경우 적절한 조치를 취해 정상 상태로 복구

교착 상태 탐지

Shoshani와 Coffman 알고리즘

현재 할당된 ALLOC 값과 REQ 값만 필요함

p₁의 할당 자원 r₁ 0 ,r₂ 2, 요구 자원 r₁ 4, r₂ 6
p₂의 할당 자원 r₁ 1 ,r₂ 5, 요구 자원 r₁ 0, r₂ 3
p₃의 할당 자원 r₁ 4 ,r₂ 1, 요구 자원 r₁ 2, r₂ 9
r₁ 의 가용 가능 자원 3, r₂ 의 가용 가능 자원 3
1. 새로운 변수 WORK 에 현재 상태에서 가용할 수 있는 자원 AVAIL 값 복사
2. 자원 할당 받은 프로세스의 FINISH 값 false로 설정
- 프로세스가 종료되지 않았다는 의미 3. WORK 값을 할당 해 NEED 값을 할당 할 수 있는 프로세스 체크
- p₂한테 자원 할당 후 p₂가 종료 된 후 반환 된 1, 5 값 WORK 값에 추가 4. WORK 값 4, 8을 이용해 NEED 값 할당 할 수 있는 프로세스 체크
- p₁한테 자원 할당 후 p₁가 종료 된 후 반환 된 0, 2 값 WORK 값에 추가 5. WORK 값 4, 10을 이용해 NEED 값 할당 할 수 있는 프로세스 체크
- p₃한테 자원 할당 후 p₃가 종료 된 후 반환 된 4, 1 값 WORK 값에 추가 6. 모든 프로세스 상태 FINISH = true 이므로 교착 상태가 아님을 판단함

p₁의 할당 자원 r₁ 0 ,r₂ 2, 요구 자원 r₁ 5, r₂ 6
p₂의 할당 자원 r₁ 1 ,r₂ 5, 요구 자원 r₁ 0, r₂ 3
p₃의 할당 자원 r₁ 4 ,r₂ 1, 요구 자원 r₁ 2, r₂ 9
r₁ 의 가용 가능 자원 3, r₂ 의 가용 가능 자원 3
1. 새로운 변수 WORK 에 현재 상태에서 가용할 수 있는 자원 AVAIL 값 복사
2. 자원 할당 받은 프로세스의 FINISH 값 false로 설정
- 프로세스가 종료되지 않았다는 의미 3. WORK 값을 할당 해 NEED 값을 할당 할 수 있는 프로세스 체크
- p₂한테 자원 할당 후 p₂가 종료 된 후 반환 된 1, 5 값 WORK 값에 추가 4. WORK 값 4, 8을 이용해 NEED 값 할당 할 수 있는 프로세스 체크
- 할당 할 수 있는 프로세스 존재 하지 않음 → 교착 상태로 판단 5. FINISH 값이 false로 남아있는 프로세스에 대해 복구 작업 진행

  
  boolean detect(상태 데이터) {
  	WORK = AVAIL;
  	if ( ALLOCᵢ != 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 && REQᵢ <= WORK ) {
  					WORK = WORK + ALLOCᵢ ;
  					FINISH[i] = true;
  					break;
  				}
  			if (i > n) break;
  	}
  	if ( FINISH[i] == false인 i 존재)
  		return true;
  	else return false;
  }

시간 복잡도 O(mn²)
- m: 자원 종류
- n: 프로세스 수

알고리즘 수행 시점
- 즉시 받아들일 수 없는 자원 요구가 있을 때
- 정해진 시간 간격
- CPU 효율이 일정 수준 이하로 떨어질 때

교착 상태 복구

교착 상태가 탐지 되면 복구 조치
복구의 주체
- 오퍼레이터
  - 수작업으로 복구
- 운영체제
  - 자동으로 복구
복구 방법
- 교착 상태 프로세스를 종료
- 교착 상태 프로세스가 할당 받은 자원을 해제
교착 상태 프로세스를 종료
- 모든 교착 상태 프로세스를 종료
  - 단점 : 진행했던 내용에 대한 복원 비용 큼
- 사이클이 제거될 때까지 교착 상태 프로세스를 하나씩 종료
  - 단점 : 종료 대상을 선택하기 위한 비용, 매 프로세스 종료 후 교착 상태 재 확인을 위한 비용
교착 상태 프로세스가 할당 받은 자원을 해제
- 사이클이 제거될 때까지 할당 된 자원을 단계적으로 선점하여 다른 프로세스들에 할당
- 프로세스와 자원 선택 기준
  - 프로세스 진척도, 사용 중인 자원의 수 등
- 프로세스의 복귀 시점도 제반 요소를 고려하여 결정
- 기아 상태에 빠지지 않도록 프로세스 선택 시 복구 횟수 고려

정리 하기

교착 상태 회피는 프로세스의 자원 사용에 대한 사전 정보를 활용하여 교착 상태가 발생할 수 있는 불 안전 상태가 되는 것을 피하는 방법임
변형된 자원 할당 그래프에서 요구 간선을 할당 간선으로 바꾸어도 사이클이 생기지 않는 안전 상태일 경우에만 자원 요구를 수용함
은행원 알고리즘은 프로세스가 요구한 자원을 할당해 줄 경우에도 안전 순서 열이 존재하는지 검사하여 자원 요구의 수용 여부를 결정함
교착 상태 탐지 및 복구는 교착 상태가 발생 했는 가를 탐지한 후, 희생자를 선택하여 해당 프로세스를 중지 시키거나 자원을 선점하는 방법임
교착 상태 탐지 알고리즘은 현재 상태의 모든 자원 요구 량을 고려하여 교착 상태 여부를 확인함

[운영 체제] 7강 - 교착 상태

학습 개요

학습 목표

강의록

교착 상태 회피

교착 상태 회피

안전 상태와 안전 순서열

안전 순서 열

교착 상태 회피

교착 상태 회피 알고리즘

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

각 자원의 단위 자원이 여러 개 일 수 있는 경우

은행원 알고리즘: 의사 코드

교착 상태 탐지 및 복구

교착 상태 탐지 및 복구

교착 상태 탐지

교착 상태 복구

정리 하기

Further Reading

[운영 체제] 1강 - 운영 체제 소개

[운영 체제] 2강 - 프로세스와 쓰레드

[운영 체제] 3강 - 프로세스 스케줄링