교착상태

1. 교착상태란?

둘 이상의 프로세스들이 다른 프로세스가 차지하고 있는 자원을 서로 무한정 기다리고 있어 프로세스의 진행이 중단된 상태를 의미한다.

1. 교착상태의 필수 조건

1. 상호 배제(mutual exclusion) 조건 : 프로세스들이 그들이 필요로 하는 자원에 대해 베타적인 통제권을 요구하는 것으로, 한 프로세스가 사용 중이면 다른 프로세스는 반드시 기다려야 하는 경우이다. -> 동시 사용 불가
2. 점유와 대기(hold and wait) 조건 : 프로세스가 적어도 하나 이상의 자원을 할당받은 채로 다른 프로세스의 자원이 해제되기를 기다리는 경우이다.
3. 비선점 조건(nonpreemption) : 프로세스가 점유한 자원은 사용이 끝날 때까지 해제할 수 없는 경우이다.
4. 환형 대기 조건(circular wait) : 프로세스의 환형 사슬이 존재해서 이를 구성하는 각 프로세스는 사슬 내의 다음에 있는 프로세스가 요구하는 하나 또는 그 이상의 자원을 갖고 있는 경우이다. -> 사이클 형성

2. 자원할당 그래프(System Resource Allocation Graph)

1. 프로세스와 자원들 간의 교착상태 판별을 위해 필요
2. 자원할당 그래프틑 G = (V, E)로 나타내며, V는 꼭지점의 집합을 E는 간선의 집합을 나타낸다. V는 프로세스의 집합 P와 모든 유형의 자원들의 집합 R로 양분된다.
3. 요구 간선 : (Pi, Rj)∈E이면 Pi로부터 Rj로의 방향 간선이 존재함을 말하며, 프로세스 Pi가 자원 Rj를 요청하여 대기중임을 의미한다.
4. 할당 간선 : (Rj, Pi)∈E이면 Rj로부터 Pi로의 방향 간선이 존재함을 말하며, 자원 Rj가 프로세스 Pi에 할당되었음을 의미한다.
5. 자원할당 그래프에서 환형대기를 나타내는 사이클이 있으면 교착상태가 존재할 수 있고, 없으면 교착상태는 존재하지 않는다. -> Cycle은 교착상태의 필요조건(필요충분조건 X)

교착상태 : 사이클이 있으면서 요청 간선이 계속 대기해야할 경우

2. 교착상태의 해결책

1. 교착상태의 예방

필요조건 4가지 중 한가지 이상 발생하지 않도록 하는 것

1. 상호배제 조건의 제거
   • 모든 자원을 공유 허용
   • 현실적으로 불가능
2. 점유와 대기 조건의 제거
   • 필요 자원 한 번에 모두 할당 -> 자원 낭비 발생, 무한 대기 현상 발생 가능
3. 비선점 조건의 제거
   • 모든 자원에 대해 선점 허용 -> 현실적으로 불가능
   • 유사한 방법
     • 프로세스가 할당받을 수 없는 자원을 요청한 경우, 기존에 가지고 있던 자원을 모두 반납하고 작업취소(이후 처음 또는 check-point부터 다시 시작)
     • 위의 방법은 심각한 자원 낭비 발생 -> 비현실적
4. 환형 대기 조건의 제거
   • 자원들에게 순서를 부여
   • 프로세스는 순서의 증가 방향으로만 자원 요청 가능

교착상태 예방은 교착상태가 절대 발생하지 않지만 심각한 자원 낭비가 발생하며, 비현실적이다. -> 회피, 발견, 회복을 이용한다.

2. 교착상태의 회피

1. 시스템의 상태를 계속 감시
2. 시스템이 교착상태가 될 가능성이 있는 자원 할당을 요청 보류
3. 시스템을 항상 안전 상태(safe state: 교착상태를 일으키지 않으면서 각 프로세스에게 필요한 자원을 할당해 줄 수 있는 상태)로 유지
   • 안전 상태(safe state) : 모든 프로세스가 정상적 종료 가능한 상태, 안전순서열(safe sequence)이 존재 -> 교착상태가 되지 않을 수 있음을 보장
   • 불안전 상태(unsafe state) : 교착상태가 될 가능성이 있음. 하지만 반드시 발생한다는 의미는 아님.
4. 안전 상태 vs 불안전 상태
5. Dijkstra’s 은행원 알고리즘
   • 교착상태 회피를 위한 간단한 이론적 기법
   • 한 종류의 자원이 여러 개라는 가정하에 시스템을 항상 안전 상태로 유지
   • Habermann’s Algorithem : 여러 종류의 자원을 고려한 Dijkstra’s 은행원 알고리즘의 확장판
   • 자료구조 : 가용자원, 최대요구, 할당자원, 추가요구

교착상태의 회피(Deadlock Avoidance)

• 교착상태의 발생을 막을 수 있음
• 항상 시스템을 감시하고 있어야 한다. -> Overhead가 큼
• 안전 상태 유지를 위해 사용되지 않는 자원이 존재 -> 자원 활용도가 낮음
• 실현 가능성이 낮음 -> 프로세스 수와 자원 수가 고정, 필요한 최대 자원 수를 알고 있다는 가정이 전제됨.

3. 교착상태의 탐지(Detection)

1. 교착상태 방지를 위한 사전 작업을 하지 않음 -> 교착상태 발생 가능
2. 주기적으로 교착상태 발생 확인
   • 시스템이 교착상태인가?
   • 어떤 프로세스가 교착상태인가?
3. 반드시 회복 과정이 필요
4. 탐지 알고리즘
   • 자료 구조 : 가용자원, 할당자원, 요청자원 -> Max 필요없음

교착상태 회피 vs 탐지

교착상태 회비

• 최악의 경우를 생각(앞으로 일어날 일을 고려)
• 교착상태가 발생하지 않음

교착상태 탐지

• 최선의 경우를 생각(현재 상태만 고려)
• 교착상태 발생 시 회복 과정이 필요

4. 교착상태의 회복

1. 교착상태를 검출한 후 해결하는 과정
2. 프로세스 종료
   • 교착상태에 있는 프로세스를 종료시킴
   • 강제 종료된 프로세스는 이후 재시작 됨.
3. 자원 선점
   • 교착상태 해결 위해 선점할 자원 선택
   • 선정된 자원을 가지고 있는 프로세스에서 자원을 빼앗음 -> 자원을 빼앗긴 프로세스는 강제 종료됨
4. 복귀(Rollback) : 프로세스 강제 종료 후, 가장 최근의 checkpoint에서 재시작