[개념 정리/운영체제] 교착 상태(deadlock)
교착 상태 (deadlock)
교착 상태(deadlock)은 두 개 이상의 프로세스들이
서로가 가진 자원을 기다리며 중단된 상태를 말한다.
이 과정에서 각 프로세스는 서로가 원하는 자원을 유지한 채
다른 프로세스의 자원을 얻고자 기다리는 것이다.
원인
교착 상태가 발생하기 위한 필요조건은 4가지가 있다.
- 상호 배제: 주어진 시간 내에 하나의 프로세스만 자원을 독점할 수 있다. 즉, 다른 프로세스들은 접근이 불가능하다.
- 점유 대기: 특정 프로세스가 점유한 자원을 다른 프로세스가 요청하며 대기하는 상태이다.
- 비선점: 다른 프로세스의 자원을 강제적으로 가져올 수 없다.
- 환형 대기: 프로세스 A는 프로세스 B의 자원을 요구하고, 프로세스 B는 프로세스 A의 자원을 요구하는 등 서로가 서로의 자원을 요구하는 상황을 말한다.
위 4가지 조건이 모두 충족되어도 교착 상태가 발생하지 않을 수 있으나,
교착사건이 일어나기 위해서는 위 4가지 조건이 모두 충족되어야 한다.
해결 방법
- 자원을 할당할 때 애초에 교착 상태의 조건이 성립되지 않게 설계한다.
- 교착 상태 가능성이 없을 때만 자원이 할당되며, 프로세스당 요청할 자원들의 최대치를 통해 자원 할당 가능 여부를 파악하는 은행원 알고리즘을 사용한다.
- 교착 상태가 발생하면 사이클이 있는지 찾아보고 이에 관련된 프로세스를 한 개씩 지운다.
- 교착 상태는 매우 드물게 일어나기 때문에 이를 처리하는 비용이 더 커서, 교착 상태가 발생하면 사용자가 작업을 종료하게 한다. 현대 운영체제는 이 방법을 채택했다. 예를 들어, 프로세스를 실행시키다 '응답 없음'이라고 뜨는 상황이 교착 상태가 발생하여 프로세스를 종료시킬지 계속 대기할지 묻는 경우이다.
은행원 알고리즘
은행원 알고리즘(banker's algorithm)은 교착 상태를 회피하는 알고리즘으로
총 자원의 양과 현재 할당한 자원의 양을 기준으로
안정 또는 불안정 상태로 나누고
안정 상태로 가도록 자원을 할당하는 알고리즘이다.
* 안정 상태:
교착 상태를 일으키지 않은 상태이며, 프로세스의 최대 자원 요구량을 운영체제가 충족시킬 수 있는 상태
* 불안정 상태:
안정 상태로 가는 순서열이 존재하지 않는 상태
은행원 알고리즘 구조
은행원 알고리즘이 사용하는 자료구조는 아래와 같다.
n * m 의 2차원 배열 3개와, n의 1차원 배열 2개를 사용한다.
- available[i]: 운영체제가 프로세스에게 자원을 줄 수 있는 양, i번째 사용 가능한 자원의 양
- max[i][j]: 프로세스 최대 요구량, 프로세스 i가 자원 j를 최대 요청할 수 있는 양
- allocation[i][j]: 프로세스 자원 할당량, 프로세스 i에 자원 j를 할당한 양
- need[i][j]: 프로세스의 자원 추가 요구량, 프로세스 i가 자원 j를 추가 요청하는 양
- finish[i]: i번째 프로세스가 요청하는 양을 운영체제가 만족시킬 수 있는 지 파악하는 boolean 배열
은행원 알고리즘 절차
다음의 프로세스를 기반으로 수행된다.
- request[i] <= need[i] 조건 불충족시 오류
- request[i] <= available[i] 조건 불충족시 대기
- 이후 request[i]의 값이 available[i]에 더해지며, need[i]에 request[i] 값이 빠지게 된다.
- 이러한 과정을 모든 프로세스에 대해 반복한 뒤, 모든 finish[i]가 True라면 안정상태가 된다.
실습 예제
| Process | Allocation | Max | Available | Need |
| A B C | A B C | A B C | A B C | |
| P0 | 0 1 0 | 7 5 3 | 3 3 2 | 7 4 3 |
| P1 | 2 0 0 | 3 2 2 | 1 2 2 | |
| P2 | 3 0 2 | 9 0 2 | 6 0 0 | |
| P3 | 2 1 1 | 2 2 2 | 0 1 1 | |
| P4 | 0 0 2 | 4 3 3 | 4 3 1 |
안정 상태가 되는 순서는 아래와 같다.
P1 -> P3 -> P4 -> P0 -> P2 (P0와 P4는 교체 가능)
- P1: 1, 2, 2에 해당하는 need[1]에 대한 자원을 할당하고, finish[1] = True로 만든다. available += 2 0 0 -> 5 3 2
- P3: 0, 1, 1에 해당하는 need[3]에 대한 자원을 할당하고 finish[3] = True로 만든다. available += 2 1 1 -> 7 4 3
- P4: 4, 3, 1에 해당하는 need[4]에 대한 자원을 할당하고 finish[4] = True로 만든다. available += 0 0 2 -> 7 4 5
- P0: 7, 4, 3에 해당하는 need[0]에 대한 자원을 할당하고 finish[0] = True로 만든다. available += 0 1 0 -> 7 5 5
- P2: 6, 0, 0에 해당하는 need[2]에 대한 자원을 할당하고 finish[2] = True로 만든다. available += 3 0 2 -> 10 5 7
예시 코드는 아래와 같다.
let n, m, i, j, k;
n = 5; //프로세스의 개수 0~4
m = 3; //자원의 개수
//이미 할당한 양
let alloc = [[ 0, 1, 0], //P0
[ 2, 0, 0], //P1
[ 3, 0, 2], //P2
[ 2, 1, 1], //P3
[ 0, 0, 2]]; //P4
//프로세스가 최대로 요구하는 양
let max = [[ 7, 5, 3], //P0
[ 3, 2, 2], //P1
[ 9, 0, 2], //P2
[ 2, 2, 2], //P3
[ 4, 3, 3]]; //P4
//운영체제의 가용 가능량
let avail = [ 3, 3, 2 ], ans = []
let need = Array.from({length: n}, (v, i) => Array.from({length.m}, (v, j) => 0));
for (i = 0; i < n; i++){
for(j = 0; j < m; j++){
need[i][j] = max[i][j] - alloc[i][j]
}
}
//프로세스를 순회하며 확인
for(let k = 0; k < n; k++){
for(let i = 0; i < n; i++) {
if(finish[i] == 0) {
let flag = 0;
for(j = 0; j < m; j++) {
if(need[i][j] > avail[j]) {
flag = 1;
break;
}
}
if(flag == 0) {
ans.push(i)
for(let y = 0; y < m; y++)
avail[y] += alloc[i][y];
finish[i] = 1;
}
}
}
}
let safe_flag = 1;
for(let i = 0; i < n; i++) {
if(finish[i] == 0) safe_flaf = 0;
}
if(safe_flag) {
console.log("안정 상태 순서는 다음과 같다");
for(let i = 0; i < n; i++) {
console.log("Process" + ans[i]);
}
} else {
console.log("불안정 상태이다");
}
은행원 알고리즘의 단점
프로세스가 시스템에 들어갈 때 필요한 최대 자원 수를 예측해야 하는데,
이를 예측하기 쉽지 않고,
해당 알고리즘에 대한 자원 소모량이 증가하게 되며,
프로그램의 수는 고정되어 있지 않고 항상 변하기 때문에
사용하기 어려운 단점이 있다.
참고: inflearn 강의 'CS 지식의 정석 - 큰돌'