교착 상태 해결 - 회피

이번에는 교착 상태를 해결하는 방법 중 회피에 대해 알아볼 것이다.

회피

• 목적 : 덜 엄격한 조건 요구하여 자원을 보다 효율적으로 활용
• 교착 상태의 모든 발생 가능성을 미리 제거하는 게 아닌, 교착 상태 발생 가능성을 인정하고 (3가지 필요조건 허용), 교착 상태가 발생하려고 할 때, 적절히 회피하는 것
• 예방보다 더 나은 병행성 허용

회피 방법1

• 프로세스의 시작 중단
  • 프로세스의 요구가 교착 상태 발생 있다면 프로세스 시작 중단
  • 교착 상태 회피를 위해 자원을 언제 요청하는지 추가 정보 필요
    • 각 프로세스마다 요청과 해제에서 정확한 순서를 파악하고 있다면, 요청에 따른 프로세스 대기 여부 결정 가능
  • 프로세스의 요청 수락 여부는 현재 사용 가능한 자원, 프로세스에 할당된 자원 등 각 프로세스에 대한 자원의 요청 및 해제를 미리 알고 있어야 결정 가능
    • 가장 단순하고 유용한 알고리즘은 각 프로세스가 필요한 자원의 최대치를 선언하는 것
  • 교착 상태 회피 알고리즘은 시스템이 순환 대기 조건이 발생하지 않도록 자원 할당 상태 검사
    • 자원 할당 상태 : 사용 가능 자원 수, 할당 자원 수, 프로세스들의 최대 요청 수로 정의
    • 각 프로세스에 자원을 할당할 수 있고, 교착 상태를 예방할 수 있으면 안정 상태
    • 시스템에 안정 순서가 있으면 그 시스템은 안정 상태

시스템의 상태

• 안정 상태 / 불안정 상태로 구분
• 교착 상태는 불안정 상태에서 발생
• 모든 사용자가 일정 기간 안에 작업을 끝내도록 OS가 할 수 있으면 현재 시스템의 상태는 안정, 아니면 불안정
• 교착 상태는 불안정 상태
  • 그러나 모든 불안정 상태가 교착 상태인 것은 아님, 단지 불안정 상태는 교착 상태가 되기 쉬움
• 상태가 안정하다면 OS는 불안정 상태와 교착 상태를 예방 가능
• 불안정 상태의 운영체제는 교착 상태를 발생시키는 프로세스의 자원 요청 방지 불가

안정 상태와 불안정 상태의 자원 예

프로세스	현재사용량(t0 시간)	최대 사용량
P0	2	7
P1	1	8
P2	2	4
P3	2	10
NULL	여분 자원 수	3

[안정 상태의 자원 예]

프로세스	현재사용량(t0 시간)	최대 사용량
P0	5	7
P1	1	8
P2	2	4
P3	1	7
NULL	여분 자원 수	1

[불안정 상태의 자원 예]

회피 방법2

• 자원 할당 거부 (Banker’s algorithm)
  • 프로세스가 요청한 자원 할당했을 때, 교착 상태가 발생할 수 있다면 요청한 자원을 할당하지 않음
  • 다익스트라의 banker’s algorithm 이용
    • 자원의 할당 허용 여부 결정 전에 미리 결정된 모든 자원의 최대 가능한 할당량을 시뮬레이션하여 안전 여부 검사
    • 그 후 대기 중인 다른 모든 활동의 교착 상태 가능성 조사하여 안정 상태 여부 검사확인
    • 프로세스가 자원 요청때마다 OS로 실행
    • 자원 요청 승낙이 불안정한 상태에서 시스템을 배치할 수 있다고 판단하면 이 요청을 연기, 거부하여 교착 상태 예방
    • 각 프로세스에 자원을 어떻게 할당(자원 할당 순서)할 것인지 정보 필요하므로 각 프로세스가 요청하는 자원 종류의 최대 수를 알아야 함
      • 이 정보로 교착 상태 회피 알고리즘 정의 가능

Banker’s alorithms 구현을 위한 자료구조

• Available : 각 형태별로 사용 가능한 자원 수 (사용 가능량)를 표시하는 길이가 m인 벡터
  • Available[j]=k면, 자원을 k개 사용 가능
• Max : 각 프로세스 자원의 최대 요청량 (최대 요구량)을 표시하나느 n X m 행렬
  • Max[i, j] = k이면, 프로세스 P는 자원 R을 최대 k개까지 요청 가능
• Allocation : 현재 각 프로세스에 할당되어 있는 각 형태의 자원 수(현재 할당량)을 정의하는 n X m 행렬
  • Allocation[i,j]=k면, 프로세스 P는 자원이 R인 자원을 최대 k개 할당받고 있다는 의미
• Need : 각 프로세스에 남아있는 자원 요청(추가 요구량)을 표시하는 n X m 행렬
  • Need[i,j]=k면, 프로세스 P는 자신의 작업을 종료하려고 자원 R을 k개 더 요청

n : 프로세스 수, m : 자원 수
Need[i, j]=Max[i, j]-Allocation[i, j]라는 식 성립

알고리즘 간단 구현을 위한 제약

1. 시간에 따라 벡터의 크기와 값이 변함
2. X와 Y는 길이가 n인 벡터
3. X[i] ≤ Y[i]이고, i=1,2,…,n일 때만 X≤Y
4. X=(0,3,2,1), Y=(1,7,3,2)이면X≤Y
5. X≤Y이고 X≠Y면 X<Y다

프로세스 Pi가 자원 요청 시 일어나는 동작

1단계 : Req_i ≤ Need_i이면 2단계로 이동하고, 그렇지 않으면 프로세스가 최대 요청치를 초과하기 때문에 오류 상태

2단계 : Req_i ≤ Available이면 3단계로 이동, 그렇지 않으면 자원 부족으로 인해 Pi는 대기

3단계 : 시스템은 상태를 다음과 같이 수정하여 요청된 자원을 프로세스 Pi에 할당한다.

Available = Available - Req_i;
Allocation_i = Allocation_i + Req_i;
Need_i = Need_i - Req_i;

안전 알고리즘의 시스템 상태 검사

1단계 : work와 finish를 각각 길이가 m과 n인 벡터라고 하자. Work = Available, Finish[i]=false, i=1,2,…,n이 되도록 초기화

2단계 : 다음 조건을 만족하는 i 값을 찾는다. i 값이 없으면 4단계로 이동

Finish[i] == false
Need_i ≤ Work

3단계 : 다음을 수행하고 2단계로 이동한다.

Work = Work + Allocation_i // 할당된 상태
Finish[i] = true // 일을 끝냈으니 true

4단계 : 모든 i에 대하여 Finish[i]==true이면 시스템은 안정 상태

시간 t0일 때 시스템의 상태 (안정 상태)

프로세스	Allocation	Max	Need	Available
	ABCD	ABCD	ABCD	ABCD
P0	2011	3214	1203	1222
P1	0121	0252	0131
P2	4003	5105	1102
P3	0210	1530	1320
P4	1030	3033	2003
할당량	7375

Banker’s algorithm 단점

• 할당 가능한 자원의 일정량 요청
• 자원의 수시로 유지보수 필요, 일정하게 남아 있는 자원 수 파악 곤란
• 사용자 수가 일정해야 하지만 다중 프로그래밍에서는 사용자 수가 항상 변함
• 교착 상태 회피 알고리즘을 실행하면 시스템 과부하 증가
• 프로세스는 자원을 보유한 상태로 끝낼 수 없음.
• 사용자가 최대 필요량을 미리 요청하지만, 자원 할당 방법이 점점 동적으로 변하면서 사용자의 최대 필요량 파악 곤란
• 항상 불안정 상태를 방지해야 하므로 자원 이용도 낮음