참고 자료 : 혼자 공부하는 컴퓨터구조 + 운영체제
사진 출처 : Operating System Concepts 10E
1. 교착 상태란
<식사하는 철학자 문제 (Dining philosophers problem)>
1. 어떤 문제인가..
1) 철학자들은 계속 생각하다가, 왼쪽 포크가 사용 가능하면 집어든다.
2) 철학자들은 계속 생각하다가, 오른쪽 포크가 사용 가능하면 집어든다.
3) 왼쪽과 오른쪽 포크를 모두 집어들면 정해진 시간동안 식사를 한다.
4) 식사 시간이 끝나면 오른쪽 포크를 내려둔다.
5) 오른쪽 포크를 내려놓은 뒤 왼쪽 포크를 내려둔다.
6) 다시 1)부터 반복한다.
사진 출처: https://en.wikipedia.org/wiki/Dining_philosophers_problem
2. 교착 상태란?
- 일어나지 않을 사건을 기다리며 진행이 멈춰 버리는 현상
- 모든 철학자가 1)을 수행하면 사용 가능한 오른쪽 포크가 없으므로 멈춰버림
<dead lock 해결하기 위해서>
1. 개요
- 교착 상태가 발생했을 때의 상황을 정확히 표현하기
- 교착 상태가 일어나는 근본적인 이유 이해하기
2. 자원할당 그래프
- 교착 상태가 발생했을 때의 상황을 표현하는 그래프
- 교착 상태 발생 조건 파악 가능
- 어떤 프로세스가 어떤 자원을 할당 받아 사용 중인지 확인 가능
- 어떤 프로세스가 어떤 자원을 기다리고 있는지 확인 가능
- 그리는 방법
- 프로세스는 원으로, 자원의 종류는 사각형으로 그리기
- 자원의 갯수는 사각형 내의 점으로 표현
- 프로세스가 할당 받은 자원은 화살표(r->p)로 표시
- 프로세스가 기다리는 자원은 반대 화살표(p->r)로 표시
- 교착 상태가 일어나는 자원할당 그래프는 원의 형태이다.
3. 교착상태가 발생할 조건
- 네가지 조건!!
1) 상호 배제 (Mutual exclusion)
-> 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없는 상태
2) 점유와 대기 (Hold and wait)
-> 자원을 할당 받은 상태에서 다른 자원을 할당 받기를 기다리는 상태
3 비선점 (No preemption)
-> 어떤 프로세스도 다른 프로세스의 자원을 강제로 빼앗지 못하는 상태
4) 원형 대기 (Circular wait)
-> 프로세스들이 원의 형태로 자원을 대기하는 상태 - 이 네가지 조건 중 하나라도 만족하지 않으면 교착 상태가 발생하지 않고, 모두 만족해야 교착 상태가 발생한다.
2. 교착 상태 해결 방법
<예방 (Prevention)>
- 애초에 교착 상태가 발생하지 않도록 하기
- 네가지 발생 조건 중 하나를 없애버리기
- 교착 상태가 발생하지 않음을 보장할 수는 있지만, 부작용이 있다...
1. 상호 배제 없애기
- 모든 자원을 공유가능하게 만들기?
-> 현실적으로 불가능
2. 점유와 대기 없애기
- 특정 프로세스에 자원을 모두 할당하거나, 아예 할당하지 않는 방식으로 배분
-> 자원의 활용률이 낮아지는 단점..
3. 비선점 조건 없애기
- 선점이 가능한 자원(CPU)에 한해서 효과적임!
-> 그러나 모든 자원이 선점 가능한 것은 아니다.
4. 원형 대기 조건 없애기
- 자원에 번호를 붙이고, 오름차순으로 할당하면 원형대기는 발생하지 않음
- 예를 들면 원형이 아닌 일자로 된 식탁에서 식사하는 방법
- 그러나
-> 자원에 번호를 붙이는 것은 어려운 작업이며
-> 어떤 자원에 어떤 번호를 붙이느냐에 따라 활용률이 달라진다.
<회피 (Avoidance)>
1. 개요
- 교착 상태를 무분별한 자원 할당으로 인해 발생했다고 간주
- 교착 상태가 발생하지 않을 만큼 조심히 할당하기
- 배분할 수 있는 자원의 양을 고려하기
2. 교착 상태 회피
- 안전 순서열
- 교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서
- 안전 상태
- 교착 상태 없이 모든 프로세스가 자원을 할당 받고 종료될 수 있는 상태
- 안전 순서열이 있는 상태
- 불안전 상태
- 교착 상태가 발생할 수도 있는 상태
- 안전 순서열이 없는 상태
| 프로세스 | 요구량 | 현재 사용량 |
|---|---|---|
| P1 | 10 | 5 |
| P2 | 4 | 2 |
| P3 | 9 | 2 |
- 예시 (안전 순서열이 존재하는 경우 - 위의 표 사용)
- 할당 가능 자원 = 12
- 할당한 자원 = 5+2+2 = 9
- 남은 자원 = 12 - 9 = 3
- 안전 순서열: P2->P1->P3
- 안전 순서열에 따라 동작하는 순서
- P2가 먼저 2만큼 할당
- 할당한 자원 = 9+2 = 11
- 남은 자원 3 - 2 = 1
- 요구한 자원을 모두 할당 받았으므로 P2의 자원 반환
- 할당한 자원 = 11 - 4 = 7
- 남은 자원 = 1 + 4 = 5
- P1에 자원 할당
- 할당한 자원 = 7 + 5 = 12
- 남은 자원 = 5 - 5 = 0
- P1자원 반환
- 할당한 자원 = 12 - 10 = 2
- 남은 자원 = 0 + 10 = 10
- P3에 자원 할당
- 할당한 자원 = 2 + 7 = 9
- 남은 자원 = 10 - 7 = 3
- 결론적으로 모든 프로세스가 자원을 할당 받았음!
- 만약 다른 순서로 동작했다면, 모든 프로세스가 자원을 할당 받지 못하는 상황이 발생한다.
- P2가 먼저 2만큼 할당
- 결론: 교착 상태 회피는 항상 안전 상태만을 유지하도록 자원을 할당하는 방식이다
- ex) 은행원 알고리즘
<검출 후 회복(Detection and Recovery)>
- 교착 상태의 발생을 인정하고 사후에 조치
- 프로세스가 자원을 요구하면 일단 할당, 교착 상태가 검출되면 회복
1. 선점을 통한 회복
- 교착 상태가 해결될 때까지 한 프로세스씩 자원을 몰아주는 방식
2. 프로세스 강제 종료를 통한 회복
- 교착 상태에 놓은 프로세스를 모두 강제 종료
- 작업 내역을 잃을 위험이 있다.
- 교착 상태가 해결될 때 까지 한 프로세스씩 강제 종료
- 오버헤드가 발생
<무시>
1. 타조 알고리즘
- 문제 발생의 확률이나 정도가 약하다면 무시하는 것이 더 효율적인 경우가 있다.
