교착상태
프로세스 자원 사용 순서
- 자원 요청 : 필요한 자원을 요청하고, 다른 프로세스가 사용 중이면 대기(block)한다.
- 자원 사용 : 프로세스가 요청한 자원을 획득하여 사용한다.
- 자원 해제 : 프로세스가 자원 사용을 마친 후 해당 자원을 되돌려준다.
Blocked/Asleep state
- 프로세스가 특정 이벤트를 기다리는 상태
- 프로세스가 필요한 자원을 기다리는 상태
교착상태(Deadlock)
- 다중 프로세스가 발생 가능성이 없는 이벤트를 기다리는 경우 (Blocked 상태)
- 프로세스가 교착 상태에 빠지면 작업이 정지되어 명령 진행 불가
- 두 개 이상의 프로세스가 사용하는 자원(비공유 자원)을 서로 기다리고 있을 때 발생
교착 상태를 해결하기 위한 외부 간섭이 필요하다.
교착 상태 발생의 네가지 조건
- 상호배제
- 자원을 최소 하나 이상 비공유 (한 번에 프로세스 하나만 해당 자원을 사용할 수 있어야 한다.)
- 자원 점유와 대기
- 자원을 최소한 하나 보유, 다른 프로세스에 할당된 자원을 얻으려고 대기하는 프로세스가 있어야 함
- 비선점형 자원
- 자원 선점 불가 (강제로 빼앗을 수 없고, 점유하고 있는 프로세스가 끝나야 해제)
- 순환(환형) 대기
Ex
- t2에 P1이 R2를 요청하여 R2를 할당 받았다. P1->R2
- t3에 P2가 R1를 요청하여 R1을 할당 받았다. P2->R1
- t4에 P1이 R2를 요청했지만, P2가 점유 중이므로 대기한다.
- t5에 P2가 R1를 요청했지만, P1이 점유 중 이므로 대기한다.
-> 무한 대기 = 교착 상태
그래프로 표현하는 방법
G = (N, E)로 구성된다.
- 프로세스 P1이 R1을 요청 : P1 -> R1, (P1, R1)
- 자원 R2를 프로세스 P2에 할당 : R2-> P2, (R2, P2)
교착 상태의 할당 그래프와 사이클
P2가 작업을 끝낸 뒤 R1을 반납하면 교착상태가 발생하지 않는다.
자원 할당 그래프에 사이클이 없다면 교착상태가 아니다. 그러나, 사이클이 있다면 시스템은 교착 상태일 수도 있고 아닐 수도 있다.
사이클은 교착 상태 발생의 필요 조건이지 충분조건이 아니다.
교착 상태 해결 방법
- 예방 (prevention)
- 회피 (avoidance)
- 탐지, 회복 (detection, recovery)
예방
교착 상태를 일으킬만한 요소 중 하나 제거
- 자원의 상호배제 조건 방지
- 점유와 대기 조건 방지
- 비선점 조건 방지
- 순환(환형) 대기 조건 방지
자원의 상호배제 조건 제거
-> 모든 자원을 공유하게 만들면, 동시성 문제가 발생해 불가능하다.
점유와 대기 조건 제거
프로세스가 작업 수행 전에 필요한 자원 모두 한꺼번에 요청하고 획득해야 한다.
-> 필요한 자원을 모두 한번에 요청받아 처리할 수 있을 경우에만 자원을 할당하는 방법
- 자원 효율성이 너무 낮다 : 순차적으로 처리하기 때문에 필요하지 않은 순간에도 가지고 있음
- 기아 상태 발생 가능 : 대화식 시스템에서 사용 불가능하다.
비선점 조건 제거
- 실행 중인 중요한 프로세스를 중단시킬 수 있다.
유사한 방법 : 프로세스가 할당 받을 수 없는 자원을 요청한 경우에, 기존에 가지고 있던 자원을 모두 반납하고 작업 취소, 처음부터 다시 시작 -> 심각한 자원 낭비 발생
순환(환형) 대기 조건 제거
모든 자원에 일련의 순서를 부여한다. 각 프로세스가 오름차순으로만 자원을 요청할 수 있게 함
계층적 요청 방법으로 순환 대기의 가능성을 제거한다.
-> 자주 쓰이는 자원에 병목현상이 발생한다. (다른 여유 자원을 먼저 사용할 수 없다.)
4개의 Deadlock 발생 필요 조건 중 하나를 제거하면, Deadlock이 절대 발생하지 않지만, 심각한 자원 낭비가 발생한다.
- Low device utilization
- Reduced system throughput
결론 : 예방은 비현실적이다.
회피
시스템의 상태를 계속 감시한다.
- 시스템이 Deadlock 상태가 될 가능성이 있는 자원의 할당요청을 보류한다.
- 시스템을 항상 safe state로 유지
cf. 모든 사용자가 일정 기간 안에 작업을 끝낼 수 있으면 안정 상태, 그렇지 않으면 불안정 상태 (불안정 상태는 교착 상태가 발생할 수 있는 가능성이 있다는 의미이지 반드시 교착 상태가 발생한다는 의미는 아니다.)
예방과의 차이점 : 발생 가능성을 미리 제거하는 것이 아닌 교착 상태가 발생할 가능성을 인정하고, 발생하려고 할 때 적절히 회피하는 것을 말한다.
회피방법
- 프로세스의 시작 중단 : 자원 요청이 교착 상태를 발생시킬 수 있다면 프로세스 시작을 중단
- 자원 할당 거부 : 요청한 자원을 할당했을 때 교착 상태가 발생할 수 있다면 요청한 자원을 할당하지 않는다.
(ex. Banker's algorithm)
다익스트라의 은행가 알고리즘 (Banker's algorithm)
- 자원 할당 여부를 결정하기 전에, 모든 자원의 최대 가능한 할당량을 시뮬레이션하여 안전 여부를 검사한다.
- 불안정할 가능성이 있다고 판단하면 이 요청을 연기, 거부하여 교착 상태를 예방한다.
- 프로세스가 요청하는 자원 종류의 최대 수를 알아야 한다.
예제
10 resource units, 3 processes
Safe state example
Available resource units : 2
실행 종료 순서 : P1 -> P3 -> P2 (Safe sequence)
현재 상태에서 안전 순서가 하나 이상 존재하면 안전 상태이다.
Available resource units >= Additional Need : 안전상태
반대로 Available resource units < Additional Need 이면 불안전 상태이다.
추가적으로 Habermann 알고리즘도 있다. ( 요청 자원의 종류만 늘었지, 비슷함 -> 궁금하면 찾아보자!)
회피 결론 :
- High overhead : 항상 시스템을 감시하고 있어야 한다.
- Low resource utilization : Safe state 유지를 위해, 사용 되지 않는 자원이 존재한다.
- 프로세스 수, 자원수가 고정되어 있다는 가정이 필요하므로 비현실적이다.
교착 상태 탐지-회복
교착상태가 발생하는걸 인정하고, 교착상태 발생을 탐지한 후 복구(회복) 시킨다.
특징
- 교착 상태 파악을 위해 알고리즘을 언제 수행해야 하는지 결정하기 어려움
- 자주 실행하면 시스템의 성능이 떨어지지만, 교착 상태에 빠진 프로세스를 빨리 발견하여 자원의 유휴 상태 방지 가능, 자주 실행하지 않으면 반대 상황 발생
- 탐지와 회복 방법은 필요한 정보를 유지하고 탐지 알고리즘을 실행시키는 비용 뿐 아니라 교착 상태 회복에 필요한 부담까지 요청한다.
예방과의 차이점 : 최선의 경우만을 고려하고, 현재 상태만 고려한다 (Deadlock 발생 시 Recovery 과정이 필요)
탐지 방법 : 그래프에서 edge를 하나씩 지워가는 방법으로 deadlock 판단
상태 1 : Completely reduced
- 모든 edge가 제거 됨
- Deadlock에 빠진 프로세스가 없음
상태 2 : Irreducible
- 지울 수 없는 edge가 존재
- 하나 이상의 프로세스가 deadlock 상태
j에 대한 모든 요청 수 <= 리소스 자원(j) 총 수 - 할당된 수
요청수 <= 남은 리소스 -> unblocked
최종 Graph에서
- 모든 edge가 제거 (Completely reduced) == deadlock이 없음
- 일부 edge가 남음 (irreducible) == 현재 deadlock이 존재
회복 방법
- 프로세스 중단 : 교착 상태에 빠진 프로세스를 모두 중단한다 (자원 사용과 시간면에서 cost가 높다)
- 한 프로세스씩 중단 : 교착 상태 탐지 알고리즘을 호출하는 부담이 상당히 크다
-> 최소 비용으로 프로세스들을 중단하는 우선 순위를 선정한다.
- 프로세스가 수행된 시간과 앞으로 종료하는데 필요한 시간
- 프로세스가 사용한 자원 형태와 수
- 프로세스를 종료하는 데 필요한 자원 수
자원 선점 : Deadlock 상태를 해결하기 위해 선점할 자원을 선택한다
- Deadlock 상태가 아닌 프로세스가 종료될 수 있다.
- 우선순위 기반으로 빼앗기므로 기아상태가 발생할 수 있다.
각 방법마다 장단점이 있으므로 트레이드 오프 해야한다.
Reference
운영체제:그림으로 배우는 구조와 원리 - 한빛 아카데미
