교착 상태(Deadlock)
: 교착 상태란 두 개 이상의 프로세스가 서로 자원을 기다리며 아무도 앞으로 진행할 수 없는 상태를 말한다.
자원 할당 그래프
: 프로세스가 자원을 사용하는 관계를 노드(Node)와 화살표(Edge)로 표현한 그래프
→ 교착 상태가 일어난 자원 할당 그래프는 원의 형태를 띤다.
- 프로세스(Process) → 원(Circle)으로 표시
- 자원(Resource) → 사각형(Square)으로 표시
- 자원 인스턴스(Resource Instance) → 사각형 안의 점(.)으로 표시
- 요청(Request) 에지 → P → R
- 할당(Assignment) 에지 → R → P
ex) 교착 상태가 발생한 그래프
교착 상태(Deadlock)가 발생하려면 반드시 필요한 4가지 조건
: 운영체제에서는 아래 네 가지 조건이 모두 성립할 때 교착 상태가 발생한다.
1) 상호 배제(Mutual Exclusion)
- 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없는 상태
- 하나의 자원은 한 프로세스만 사용할 수 있다.
2) 점유와 대기(Hold and Wait)
- 자원을 할당받은 상태에서 다른 자원을 할당받기를 기다리는 상태
- 프로세스가 자원을 보유한 상태에서 새로운 자원을 기다리고 있다.
3) 비선점(Non-preemption)
- 어떤 프로세스도 다른 프로세스의 자원을 강제로 빼앗지 못하는 상태
- 다른 프로세스가 이미 보유한 자원을 강제로 빼앗을 수 없다.
4) 원형 대기(Circular Wait)
- 프로세스들이 원의 형태로 자원을 대기하는 상태
교착 상태 해결 방법
예방
: 애초에 교착 상태가 발생하지 않도록 교착 상태 발생 조건 중 하나를 없애 버리는 방법
(1) 상호 배제 없애기
- 모든 자원을 공유 가능하게 만들까? → 이론적으로는 가능하지만 현실적으로는 불가능하다.
(2) 점유와 대기 없애기
- 특정 프로세스에 자원을 모두 할당하거나 아예 할당하지 않는 방식으로 배분
→ 자원의 활용률을 낮출 수 있는 방식
(3) 비선점 조건 없애기
- 선점이 가능한 자원에 한해 효과적
→ 모든 자원이 선점 가능한 것은 아니다. 즉, 범용적인 방법은 되지 못한다.
(4) 원형 대기 조건 없애기
-
자원에 번호를 붙이고 오름차순으로 할당하면 원형 대기는 발생하지 않는다.
- 자원에 번호를 붙이는 것은 어려운 작업이다.
- 어떤 자원에 어떤 번호를 붙이느냐에 따라 활용률이 달라진다.
→ 가장 현실적이고 실용적인 방법이다.
회피
-
교착 상태가 무분별한 자원 할당으로 인해 발생한다고 간주
-
교착 상태가 발생하지 않을 만큼 조심스럽게 할당
-
배분할 수 있는 자원의 양을 고려하여 교착 상태가 발생하지 않을 만큼만 자원을 배분한다.
-
안전 순서열
- 교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서
-
안전 상태
- 교착 상태 없이 모든 프로세스가 자원을 할당받고 종료될 수 있는 상태
-
불안전 상태
- 교착 상태가 발생할 수도 있는 상태
EX) 은행원 알고리즘(Banker's Algorithm)
은행에서 대출하는 상황을 예로 들면 다음과 같다.
-
고객이 대출을 조금 요청했다.
-
모두 빌려주면 나중에 다른 고객에게 빌려줄 돈이 없어서 문제가 생길 수 있다.
-
“지금 빌려줘도 모든 고객이 언젠가는 돈을 다 갚을 수 있을까?”
→ 안전하면 승인, 위험하면 거절
예시 상황
자원 종류 A가 총 10개 있다고 하자.
현재 상태
| 프로세스 | 현재 보유(Allocation) | 최대 필요(Max) |
|---|---|---|
| P1 | 3 | 7 |
| P2 | 2 | 4 |
| P3 | 2 | 6 |
현재 사용 중: 3 + 2 + 2 = 7개
남은 자원: 10 - 7 = 3개
상황: P1이 자원 2개를 추가로 요청
→ OS가 가능한 실행 순서를 찾아본다(Safe Sequence 찾기).
→ Step 1) 남은 자원으로 실행 가능한 프로세스를 찾는다.
→ 현재 남은 자원은 1개
→ Need(남은 필요)가 1개 이하인 프로세스?
→ 없음
→ 즉, 어떤 프로세스도 끝까지 실행시킬 수 없는 상태
→ Unsafe State(불안전 상태)
→ 교착 상태가 발생할 가능성이 매우 높음
→ 결론: OS는 요청을 거부한다.
검출 후 회복
- 교착 상태가 발생했다는 것을 인정하고 사후에 회복하는 방식
선점을 통한 회복
- 교착 상태가 해결될 때까지 한 프로세스씩 자원을 몰아주는 방식
프로세스 강제 종료를 통한 회복
- 교착 상태에 놓인 프로세스를 모두 강제 종료(→ 작업 내역을 잃을 위험)
- 교착 상태가 해결될 때까지 한 프로세스씩 강제 종료(→ 오버헤드)
정리
교착 상태(Deadlock)는 두 개 이상의 프로세스가 서로가 가진 자원을 기다리며 아무도 진행하지 못하는 상태로, 자원 할당 관계를 나타내는 그래프에서는 보통 원형 형태로 나타난다. 교착 상태가 발생하려면 상호 배제, 점유와 대기, 비선점, 원형 대기의 네 가지 조건이 모두 충족되어야 한다. 이를 해결하기 위한 방법으로는 예방(Prevention), 회피(Avoidance), 검출 후 회복(Recovery)이 있다. 예방은 네 가지 조건 중 하나를 제거하는 방식으로, 상호 배제를 없애거나 점유와 대기를 금지하거나 비선점을 허용하거나 자원에 번호를 부여해 순차적으로 할당하여 원형 대기를 막는 방법 등이 있다. 회피는 대표적으로 은행원 알고리즘처럼 현재 자원 상태로 모든 프로세스가 언젠가 종료될 수 있는지, 즉 안전 상태인지를 판단하여 위험한 요청은 거부한다. 예를 들어 남은 자원으로 어떤 프로세스도 완료할 수 없는 불안전 상태(Unsafe State)가 된다면 OS는 요청을 거부한다. 마지막으로 검출 후 회복은 교착 상태가 발생했음을 인정하고 선점이나 프로세스 강제 종료 등을 통해 문제를 해결하는 방식이다.
참고
