13-1 교착 상태란
식사하는 철학자 문제
- dining philosophers problems
- 원탁에서 모두가 자신의 오른쪽 포크를 들고 왼쪽 포크를 기다리는 상태
- 교착상태(deadlock)
자원 할당 그래프
자원 할당 그래프(resource-allocation graph)
출처: https://www.geeksforgeeks.org/operating-systems/resource-allocation-graph-rag-in-operating-system/
- 프로세스는 원, 자원의 종류는 사각형
- 자원 사각형 내의 점은 사용할 수 있는 자원의 갯수
- 프로세스가 자원을 할당받아 사용 중이라면 자원 내 점 → 프로세스 화살표 표시
- 프로세스가 자원을 기다리고 있다면 프로세스 → 자원 화살표 표시
교착 상태가 발생한 상황은 보통 자원 할당 그래프가 원의 형태를 띄고 있음.
교착 상태 발생 조건
4가지 조건이 모두 만족해야 발생
상호 배제
mutual exclusion
한 자원을 한 번에 하나의 프로세스만 이용 가능한 경우
점유와 대기
hold and wait
자원을 보유한 채 다른 자원을 기다리는 경우
비선점
nompreemptive
어떤 프로세스도 다른 프로세스의 자원을 강제로 빼앗지 못하는 경우
원형 대기
circular wait
자원 할당 그래프가 원으로 그려지듯이 프로세스들이 원의 형태로 자원을 대기하는 것
원형 대기라고 해서 반드시 교착 상태가 발생하는 것은 아님
13-2 교착 상태 해결 방법
교착 상태 예방
교착 상태 발생 조건 네 가지 중 한 가지를 방지
상호 자원 배제 방지
모든 자원을 공유 가능하게 함 ⇒ 현실적으로 불가능
점유와 대기 방지
- 하나를 점유한 채 다른 것을 대기하지 않도록
- 한 프로세스가 모든 자원을 점유하거나
- 한 프로세스가 모든 자원을 대기하거나
- 자원 활용률이 낮아짐
- 사용하지 않는 자원도 점유하고 있는 경우가 생김(A만 쓰는데 A,B를 모두 점유하므로)
- 자원을 많이 사용하는 프로세스에게 기아 현상을 야기할 우려
비선점 조건 방지
- 비선점 조건을 없애면 자원을 이용 중인 프로세스로부터 자원을 빼앗을 수 있음
- 어떤 자원은 한 프로세스의 작업이 끝날때 까지 기다려야 하므로 범용성이 떨어지는 방법(ex. 프린터)
원형 대기 조건 방지
- 모든 자원에 번호를 붙이고 오름차순으로 자원을 할당
- 모든 자원에 번호를 붙이는 비효율성과 번호로 인해 특정 자원의 활용률이 떨어질 수 있음
교착 상태 회피
- 교착 상태는 프로세스의 수에 비해 자원이 부족하여 발생하므로 교착 상태가 발생하지 않을 만큼만 자원 할당
- 안전 상태(safe state): 교착 상태가 발생하지 않고 모든 프로세스가 정상적으로 자원을 할당받고 종료될 수 있는 상태
- 불안전 상태(unsafe state): 교착 상태가 발생할 수도 있는 상황
- 안전 순서열(safe sequence): 교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서
- 안전 상태는 안전 순서열대로 프로세스들에 자원을 배분한 것
- 불안전 상태는 안전 순서열이 없는 상황
- 운영체제는 안전 순서열이 존재하는 안전 상태인 수준에서 자원을 배분함
예시
프로세스가 3개, 자원이 12개 있을 때
| 프로세스 | 요구량 | 현재 보유 자원 |
|---|---|---|
| P1 | 10 | 5 |
| P2 | 4 | 2 |
| P3 | 9 | 2 |
- 현재 남은 자원은 3개인 상태
- P2에게 2개를 분배하면 남은 자원은 1개가 됨
- P2의 작업이 종료되면 P2는 보유한 모든 자원을 반환하므로 다시 5개가 됨
- 이후 남은 자원 5개를 P1에게 분배하여 P1의 작업을 완료함
- P1이 반환하면 남은 자원은 10개가 되므로 P3에게 분배
- P2 → P1 → P3 라는 안전 순서열이 존재하므로 안전 상태임
만약 P3에게 1개를 더 분배한다면?
| 프로세스 | 요구량 | 현재 보유 자원 |
|---|---|---|
| P1 | 10 | 5 |
| P2 | 4 | 2 |
| P3 | 9 | 3 |
- 위와 달리 P3는 3개를 보유하므로 남은 자원은 2개
- P2에게 남은 2개를 분배하여 작업을 완료
- P2는 자원을 반환하여 남은 자원은 4개가 됨
- 이 4개는 P1과 P3 그 누구의 작업도 끝낼 수 없음(P1은 5개, P3는 6개가 필요함)
- 교착상태가 발생
- 5개, 2개, 3개를 분배한 상태는 불안전 상태
교착 상태 검출 후 회복
선점을 통한 회복
교착 상태가 해결될 때까지 다른 프로세스로부터 자원을 강제로 빼앗고 한 프로세스에 할당
프로세스 강제 종료를 통한 회복
- 교착 상태에 놓인 프로세스를 모두 강제 종료
- 교착 상태가 없어질 때까지 한 프로세스씩 강제 종료