이번에는 교착 상태를 해결하는 방법 중 회피에 대해 알아볼 것이다.
회피
- 목적 : 덜 엄격한 조건 요구하여 자원을 보다 효율적으로 활용
- 교착 상태의 모든 발생 가능성을 미리 제거하는 게 아닌, 교착 상태 발생 가능성을 인정하고 (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]라는 식 성립
알고리즘 간단 구현을 위한 제약
- 시간에 따라 벡터의 크기와 값이 변함
- X와 Y는 길이가 n인 벡터
- X[i] ≤ Y[i]이고, i=1,2,…,n일 때만 X≤Y
- X=(0,3,2,1), Y=(1,7,3,2)이면X≤Y
- 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 단점
- 할당 가능한 자원의 일정량 요청
- 자원의 수시로 유지보수 필요, 일정하게 남아 있는 자원 수 파악 곤란
- 사용자 수가 일정해야 하지만 다중 프로그래밍에서는 사용자 수가 항상 변함
- 교착 상태 회피 알고리즘을 실행하면 시스템 과부하 증가
- 프로세스는 자원을 보유한 상태로 끝낼 수 없음.
- 사용자가 최대 필요량을 미리 요청하지만, 자원 할당 방법이 점점 동적으로 변하면서 사용자의 최대 필요량 파악 곤란
- 항상 불안정 상태를 방지해야 하므로 자원 이용도 낮음
'Computer Science > Operating System' 카테고리의 다른 글
| 교착 상태 해결 - 예방 (1) | 2024.04.12 |
|---|---|
| 교착 상태란? (0) | 2024.04.12 |