OS - 교착상태
교착상태
둘 이상의 프로세스들이 각각 자원을 점유한 상태에서 또 다른 프로세스가 현재 점유하고 있는 자원을 요구하며 상대 프로세스가 양보하기를 무한정 기다리는 현상
1. 필수조건
1.1. 상호배제 조건
- 하나의 프로세스가 사용 중이면 다른 프로세스는 반드시 기다려야 하는 경우
- 한 번에 한 프로세스만이 공유자원을 사용할 수 있어야 한다
1.2. 점유와 대기 조건
- 임의의 프로세스가 최소한 하나 이상의 자원을 할당받은 상태에서 다른 프로세스의 자원이 해제되기를 기다를 프로세스가 존재하는 경우
1.3. 비선점, 비중단 조건
- 프로세스에게 할당된 자원을 중간에 강제로 빼앗지 못함을 의미하는 것
- 자원이 임의의 프로세스에게 할당이 되면 프로세스가 작업을 끝내고 반납하기 전 까지는 돌이킬 수 없는 것
1.4. 환형대기 조건
- 프로세스 간에 환형 사슬이 존재하여 이를 구성하는 각 프로세스는 사슬 내에서 자신의 다음에 있는 프로세스가 요구하는 하나 이상의 자원을 가지고 있는 상태에서 자신의 이전 프로세스가 점유 중인 자원을 요청하고 있는 상황
- 공유자원을 사용하기 위해 대기하는 프로세스들이 원형으로 구성되어 있다 가정
2. 자원할당 그래프
- 방향 그래프
- 각 프로세스별 할당자원 및 대기자원의 상태를 나타낼 수 있다
- 자원할당 그래프 G는 정점의 집합 V와 간선의 집합 E를 이용하여 표시한다
- G = (V, E)
2.1. 요청 연결선과 할당 연결선
- 프로세스 P는 원으로 자원 Rj는 사각형으로 표시
- 자원할당 그래프에 cycle이 존재할 때 원형 안의 프로세스와 자원이 교착상태에 있음을 의미한다
자원할당 그래프를 구성하는 집합 P, R, E
P = {P1, P2, P3}
R = {R1, R2, R3}
E = {P1 -> R1, P2 -> R3, R1-> P2, R2 -> P1, R2 -> P2, R2 -> P3, R3 -> P3}
3. 교착상태 방지
교착상태가 발생하지 않도록 사전에 시스템을 제어하는 방법
교착상태 발생의 4가지 조건 중 상호배제를 제외한 3가지 중 어느 하나를 제거(부정)함으로써 수행된다
3.1. 상호배제 조건의 방지
- 여러 프로세스가 공유자원을 이용하는 것
- 공유할 수 있는 자원은 상호배제적인 엑세스를 요구하지 않기 때문에 교착상태가 일어나지 않는다
3.2. 대기 조건의 방지
- 프로세스가 자원을 요청할 때 자신이 점유하고 있는 자원이 없도록 하는 것
- 프로세스가 자신의 작업에 필요한 모든 자원을 확보할 수 있을 때에만 시작하는 방법
3.3. 비중단 조건의 방지
- 비선점 조건을 선점형으로 변경해서 사용하는 것
- 임의의 자원을 점유하는 프로세스의 자원에 대한 추가요구가 더 이상 받아들여지지 않으면 운영체제가 프로세스의 작업이 종료되기 전에 점유하고 있던 자원을 강제로 시스템에 반환시키는 것
- 원래 점유 중인 자원을 일단 반납하고 필요한 경우에 다시 요구하도록 하는 기법
3.4. 환형대기 조건의 방지
- 시스템 내에 순환이 없도록 한쪽 방향으로만 자원을 요구하도록 하는 것
- 시스템의 자원을 할당하려고 할 때 어떤 순서를 지키며 할당하는 것
- 자원을 선형 순서로 분류한 후 고유번호를 부여하여 모든 프로세스에 각 자원의 유형별로 할당순서를 부여
- 자신이 점유한 자원보다 높은 순번을 가진 자원을 할당받으려 할 때, 요청하는 자원보다 낮은 순번을 갖는 자원을 모두 반환하고 요청하는 것
4. 교착상태 회피
교착상태의 발생 가능성을 인정하고 교착상태가 발생하려 할 때 사전정보를 가지고 교착상태가 발생하지 않도록 처리하는 방법
은행원 알고리즘이 주로 사용된다
4.1. 단일 유형의 여러 자원이 존재하는 경우
- 은행원 알고리즘의 데이터 구조로 각 프로세스에 자원을 할당
n은 시스템의 프로세스 수, m을 자원형태의 수라 가정할 때 다음과 같은 자료구조가 필요하다
- available(가용자원) : 각 형태별로 사용 가능한 자원의 수를 표시하는 길이가 m인 벡터
- max(최대요구) : n * m 행렬로 각 프로세스의 자원에 대한 최대 요구량
- allocation(할당자원): n * m 행렬로 각 프로세스에 현재 할당된 자원의 수
- need(추가요구) : n * m 행렬로 각 프로세스가 앞으로 더 요구할 수 있는 자원의 수
4.1.1. 안전상태와 불안전상태 교착상태
안전상태의 예
| 프로세스 | allocation (할당자원) | max(최대요구) | need(추가요구) | available(가용자원) |
|---|---|---|---|---|
| P1 | 3 | 6 | 3 | 2 |
| P2 | 3 | 7 | 4 | |
| P3 | 2 | 4 | 2 | |
| P4 | 2 | 8 | 6 |
불안전상태의 예
| 프로세스 | allocation | max | need | available |
|---|---|---|---|---|
| P1 | 4 | 6 | 2 | 1 |
| P2 | 3 | 7 | 4 | |
| P3 | 2 | 4 | 2 | |
| P4 | 2 | 8 | 6 |
- Request (need) <= Available 인 상황
- 할당을 시작할 수 없기 때문에 불안정 상태이다
4.1.2은행원 알고리즘 (Banker's algorithm)
프로세스 p1, p2, p3, p4 가 자원 ABC 에 대해 각각을 할당받은 후 추가필요량을 요구하는 경우
| allocate | need | available | |||||||
|---|---|---|---|---|---|---|---|---|---|
| A | B | C | A | B | C | A | B | C | |
| P1 | 1 | 3 | 1 | 1 | 0 | 1 | 1 | 4 | 2 |
| P2 | 1 | 0 | 0 | 1 | 7 | 5 | |||
| P3 | 1 | 3 | 5 | 2 | 3 | 3 | |||
| p4 | 0 | 6 | 3 | 0 | 6 | 5 |
할당 순서
| 가용 자원 | A | 1 | 2 | 3 | 4 | 4 |
|---|---|---|---|---|---|---|
| B | 4 | 7 | 10 | 10 | 16 | |
| C | 2 | 3 | 8 | 8 | 11 | |
| 프로세스 | P1 | P3 | P2 | P4 | ||
| 할당 자원 | A | 1 | 1 | 1 | 0 | |
| B | 3 | 3 | 0 | 6 | ||
| C | 1 | 5 | 0 | 3 |
단점
할당할 수 있는 자원이 일정량 존재해야 한다
일정한 수의 사용자 프로세스가 있어야 사용 가능하다
모든 프로세스는 유한한 시간 내에 할당된 자원을 반납해야 한다
사용자가 미리 최대 자원필요량을 알고 있어야 한다
4.2. 각 유형의 자원이 한 개 뿐인 경우
- 기존의 요구간선과 할당간선에 선언간선을 추가
- 선언간선은 앞으로 프로세서가 자원을 요구하게 될 것임을 의미
- 사이클의 탐지는 n^2의 연산으로 가능한 데, 여기서 n은 프로세스의 수 이다
5. 교착상태 탐지
시스템에 교착상태가 발생했는지를 점검하여 교착상태에 있는 프로세스와 자원을 발견하는 것
5.1. 교착상태 탐지 알고리즘
남아 있는 프로세스들에 대한 할당 가능 순서를 모두 찾는 방법
- Work 와 Finish는 각각 길이가 m과 n인 벡터
- Work = Available로 초기화
- Work가 가용자원의 수를 가지도록 한 후 i = 1, 2, ..., n 일때 Allocationi != 0 이면 Finish[i] = false
- Finish[i] = false, Requesti <= Work 조건을 만족하는 색인 i를 찾는다
- 만족하는 i가 존재하는 경우 다음 단계로
- i가 없는 경우 4단계로 이동
- 다음과 일치하는지 판단 후 일치하면 2단계로 이동
- Work = Work + Allocationi
- Finish[i] = true
- Finish[i] = false 라면, 1 <= i <= n 인 범위에서 프로세스 Pi는 교착상태이다
6. 교착상태 복구
교착상태를 일으킨 프로세스를 종료하거나 교착상태의 프로세스에 할당된 자원을 선점하여 프로세스나 자원을 회복하는 것
6.1. 프로세스 종료
6.1.1 교착상태 프로세스 모두 중지
- 교착상태에 있는 모든 프로세스들을 종료하는 방법
- 교착상태 사이클을 제거할 수는 있지만 많은 비용이 소모된다
6.1.2 한 프로세스씩 중지
- 교착상태 사이클이 제거될 때 까지 프로세스를 하나씩 종료해가는 것
- 상당한 오버헤드를 요구한다
- 한 프로세스가 종료될 때 마다 교착상태 탐지 알고리즘을 호출하여 프로세스가 교착상태인지 여부를 확인한다
- 종료할 프로세스를 선택하기 위한 고려요소
- 프로세스의 우선순위
- 프로세스가 수행된 시간과 앞으로 종료하는데 필요한 시간
- 프로세스가 사용한 자원의 수와 형태
- 프로세스 종료를 위해 필요한 자원의 수 (작업 완료까지 필요한 자원의 수)
- 프로세스를 종료하는데 필요한 프로세스의 수
- 프로세스의 형태 (대화식인지 일괄처리식인지)
6.2. 자원선점
6.2.1 희생자 선택
- 선점자원을 선택하는 것
- 프로세스가 종료될 때 소요되는 비용을 최소화하기 위해 적절한 선점의 순서를 결정해야 한다
- 비용은 교착상태의 프로세스가 점유한 자원의 수, 실행되는데 걸린 시간 등을 이용해 계산한다
6.2.2 복귀
- 프로세스로부터 자원을 선점한다면 필요한 자원을 잃은 프로세스는 정상적인 실행이 안 된다
- 그 프로세스를 어떤 상태로 놓을 것인지를 결정
- 정상적인 수행을 계속할 수 없을 때 = 프로세스를 안전한 상태로 되돌려 놓은 후 그 상태로부터 재시작