[운영체제 공룡책] 8장 교착상태

8.0 교착상태

• 교착 상태(Deadlock): 여러 스레드가 서로가 가진 자원을 기다리며 영원히 진행할 수 없는 상태.
• 예시: 두 기차가 서로를 기다리며 교차로에서 정지해 있는 상황.

---

8.1 시스템 모델 (System Model)

1. 자원: CPU, 파일, I/O 장치 등과 같은 시스템 자원은 유형별로 구분되며, 각 유형에 여러 인스턴스가 존재할 수 있음.
2. 자원의 이용 절차:
   1. 요청(Request): 자원이 사용 중이면 요청한 스레드는 대기 상태로 전환.
   2. 사용(Use): 자원을 사용하여 작업 수행.
   3. 반납(Release): 사용 완료 후 자원 해제.
3. 관리:
   • 운영체제는 자원의 할당 상태를 추적.
   • 자원이 할당 중일 경우 요청한 스레드는 대기열에 추가.

교착 상태 발생 조건

• 대기 조건: 스레드가 자원을 기다리며 진행하지 못함.
• 순환 대기: 자원이 순환적으로 스레드들 간에 기다려지는 상태.

교착 상태의 예

• 철학자 문제: 철학자들이 동시에 왼쪽 젓가락을 집으면 오른쪽 젓가락을 기다리게 되어 교착 상태가 발생.

---

8.3 교착 상태 특성

8.3.1 필요조건들

1. 상호 배제(Mutual Exclusion)
   • 적어도 하나의 자원이 공유 불가능한 상태여야 함.
   • 하나의 스레드만 자원을 사용할 수 있고, 다른 스레드는 해당 자원이 해제될 때까지 대기해야 함.
2. 점유와 대기(Hold and Wait)
   • 스레드가 최소 하나의 자원을 점유하면서, 추가적인 자원을 요청하고 그 자원이 다른 스레드에 의해 점유된 상태여야 함.
3. 비선점(No Preemption)
   • 자원을 강제로 회수할 수 없어야 함.
   • 자원은 점유한 스레드가 작업을 완료한 후 자발적으로 해제해야 함.
4. 순환 대기(Circular Wait)
   • 스레드 집합 {T0, T1, ..., Tn}에서
     • T0​는 T1이 점유한 자원을 기다리고,
     • T1은 T2가 점유한 자원을 기다리며,
     • 마지막으로 Tn은 T0가 점유한 자원을 기다리는 순환 관계가 형성되어야 함.

중요 포인트

• 네 가지 조건이 모두 성립할 때만 교착 상태가 발생함.
• 순환 대기 조건은 점유와 대기 조건을 암시하지만, 각 조건을 개별적으로 분석하는 것이 유용함.

---

8.3.2 자원 할당 그래프

 

시스템 자원 할당 그래프(system resource-allocation graph)는 교착 상태를 시각적으로 설명하는 데 사용되는 유향 그래프로, 다음 요소로 구성됨

 

1. 그래프의 구성 요소

• 정점(V):
  • 스레드(T): 시스템의 모든 활성 스레드 (T = {T1,T2,...,Tn})
  • 자원(R): 시스템의 모든 자원 유형 (R = {R1,R2,...,Rm})
• 간선(E):
  • 요청 간선 (Ti→Rj​): 스레드 Ti가 자원 Rj를 요청 중.
  • 할당 간선 (Rj→Ti​): 자원 Rj의 인스턴스가 스레드 Ti​에 할당됨.

2. 동작 원리

1. 스레드가 자원을 요청하면 요청 간선이 추가됨.
2. 요청이 승인되면 요청 간선이 할당 간선으로 전환됨.
3. 자원이 해제되면 해당 할당 간선이 삭제됨.

 

자원 할당 그래프 예시

자원 할당 그래프

위 자원 할당 그래프의 상황

• 집합 T, R, and E:
  • T = {T1, T2, T3}
  • R = {R1, R2, R3, R4}
  • E = {T1 → R1, T2 → R3, R1 → T2, R2 → T2, R2 → T1, R3 → T3}
• 자원의 인스턴스:
  • 자원 유형 R1 인스턴스 1개
  • 자원 유형 R2 인스턴스 2개
  • 자원 유형 R3 인스턴스 2개
  • 자원 유형 R4 인스턴스 3개
• 스레드 상태:
  • 스레드 T1는  R2의 인스턴스 한 개를 점유, R1의 인스턴스 1개를 기다리며 대기
  • 스레드 T2는 R1과 R2의 인스턴스를 각각 1개 씩 점유, R3의 인스턴스 1개를 기다린다.
  • 스레드 T3는 R3의 인스턴스 1개를 점유

 

3. 교착 상태와 사이클

• 사이클이 없는 경우: 시스템에 교착 상태 없음.
• 사이클이 있는 경우: 교착 상태 여부는 다음에 따라 다름:
  • 모든 자원이 단일 인스턴스일 때: 사이클이 있으면 교착 상태가 발생.
  • 자원이 여러 인스턴스를 가질 때: 사이클이 있어도 교착 상태가 아닐 수 있음.
    • 예: 다른 스레드가 자원을 해제하면 사이클이 깨질 수 있음.

 

교착 상태를 갖는 자원 할당 그래프

교착 상태를 갖는 자원 할당 그래프

교착 상태 존재 (사이클 포함):

• 예: T1→R1→T2→R3→T3→R2→T1
• 모든 스레드가 서로의 자원을 기다리며 진행 불가.

 

사이클이 있으면서 교착 상태가 아닌 자원 할당 그래프

사이클이 있으면서 교착 상태가 아닌 자원 할당 그래프

교착 상태 비존재 (사이클 포함):

• 예: T1→R1→T3→R2→T1
• T4가 R2를 해제하면 사이클이 깨지고 교착 상태가 해소됨.

---

8.4 교착 상태 처리 방법

 

1. 데드락 무시
   데드락이 발생하지 않는 척하는 방법. 이 방법은 구현 비용이 낮고, 데드락이 드물게 발생하는 경우 적합하지만, 데드락 발생 시 시스템 성능이 악화될 수 있다.
2. 데드락 예방 및 회피
   • 데드락 예방: 데드락 발생 조건 중 최소 하나를 방지하기 위해 자원 요청 방식을 제한하는 방법
   • 데드락 회피: 시스템이 각 스레드의 자원 요청 및 사용 정보를 사전에 알고 있어야 하며, 현재 요청이 안전한지 판단해 요청을 허용하거나 지연시킨다.
3. 데드락 탐지 및 복구
   데드락 상태를 허용한 뒤, 시스템 상태를 검사해 데드락 발생 여부를 탐지하고 복구한다.

---

 

8.5 교착 상태 예방

8.5.1 상호 배제 (Mutual Exclusion)

• 자원이 공유 가능하다면 데드락이 발생하지 않는다.
  예: 읽기 전용 파일은 여러 스레드가 동시에 접근 가능.

---

8.5.2 점유 및 대기 (Hold and Wait)

• 스레드가 자원을 요청할 때, 다른 자원을 점유하지 않도록 보장해야 합니다.
  • 방법 1: 실행 시작 전, 모든 필요한 자원을 한 번에 요청.
  • 방법 2: 자원을 점유하고 있는 경우, 추가 요청 전에 기존 자원을 모두 해제.

---

8.5.3 비선점 (No Preemption)

• 자원을 선점할 수 있도록 설계:
  • 스레드가 요청한 자원을 즉시 할당할 수 없다면, 해당 스레드가 점유 중인 자원을 해제.
  • 요청한 자원이 선점 가능한 상태일 경우, 요청 스레드에 재할당.

---

8.5.4 순환 대기 (Circular Wait)

• 자원에 총체적 순서를 부여하고, 스레드가 자원을 순서대로 요청하도록 제한.
  • 모든 자원 유형에 고유한 번호를 부여해, 스레드가 오름차순으로 자원을 요청하게 함.

---

8.6 교착 상태 회피

• 자원 요청을 제한해 교착 상태를 방지하지만, 시스템 처리량과 자원 활용도가 낮아질 수 있음.
• 자원 요청 정보를 추가로 제공받아 시스템이 항상 안전 상태(safe state)를 유지하도록 함.

 

---

8.6.1 안전 상태 (Safe State)

 

• 안전 상태: 모든 스레드가 특정 순서로 작업을 완료할 수 있어 교착 상태가 발생하지 않는 상태.
• 불안전 상태: 교착 상태로 이어질 가능성이 있지만, 반드시 교착 상태는 아님.

 

안전, 불안전, 교착 상태 공간

---

8.6.2 자원 할당 그래프 알고리즘

• 하나의 자원 인스턴스만 있는 시스템에 사용.
• Claim Edge(요구 예측 엣지) 추가:
  • Claim Edge(점선): Ti → Rj (미래에 자원을 요청할 가능성).
  • Request Edge(실선): Ti → Rj (현재 자원을 요청).
  • Assignment Edge: Rj → Ti (자원이 스레드에 할당됨).

교착 상태 회피를 위한 자원 할당 그래프

불안전 상태의 자원 할당 그래프

---

 

8.6.3 Banker’s Algorithm (은행가 알고리즘)

• 다중 자원 인스턴스가 있는 시스템에 사용.
• 자원 할당이 안전 상태를 유지하는지 확인.

필요한 데이터 구조:

1. Available: 각 자원 타입별로 사용 가능한 자원의 개수.
2. Max: 각 스레드가 요청할 수 있는 최대 자원 수.
3. Allocation: 각 스레드에 현재 할당된 자원 수.
4. Need: 스레드가 완료하기 위해 추가로 필요한 자원 수(Max - Allocation).

알고리즘:

1. 안전성 알고리즘:
   • 현재 상태가 안전한지 확인.
   • 자원을 스레드에 순차적으로 할당할 수 있는지 반복적으로 확인.
2. 자원 요청 알고리즘:
   • 특정 스레드 요청이 안전 상태를 유지하면서 허용 가능한지 확인.
   • 요청을 가정하여 자원을 임시 할당 후 안전성 확인. 안전하지 않으면 원래 상태로 복구.

예시:

• 초기 상태:
  • 스레드 T0~T4, 자원 타입 A, B, C:
    • Allocation: T1 = (2,0,0), Max: T1 = (3,2,2), Available: (3,3,2).
    • Need: T1 = (1,2,2).
  • 안전 순서: <T1, T3, T4, T2, T0>.
• T1의 요청: (1,0,2) 요청.
  • 검토 후 요청 허용. 새로운 상태는 여전히 안전.

---

8.7 교착 상태 탐지 (Deadlock Detection)

8.7.1 단일 자원 인스턴스 (Single Instance of Each Resource Type)

• 모든 자원이 단일 인스턴스만 가지는 경우, Wait-For 그래프를 사용해 교착 상태를 탐지할 수 있음.

---

8.7.2 여러 자원 인스턴스 (Several Instances of Each Resource Type)

• 자원이 여러 인스턴스를 가지는 경우, Wait-For 그래프는 적용 불가.
• 교착 상태 탐지를 위해 은행원 알고리과 유사한 데이터 구조 사용

---

8.8 교착 상태로부터 회복 (Recovery from Deadlock)

교착 상태 복구 방법

1. 운영자에게 알리고 수동으로 문제를 해결.
2. 시스템이 자동으로 복구.
   • 교착 상태를 해소하려면 다음 두 가지 방법 중 하나를 선택:
     • 하나 이상의 프로세스나 스레드 강제 종료.
     • 하나 이상의 프로세스에서 자원을 회수(선점).

---

8.8.1 프로세스 및 스레드 종료 (Process and Thread Termination)

교착 상태를 해결하기 위해 프로세스나 스레드를 종료하는 방법:

1. 모든 교착 상태 프로세스 종료:
   • 교착 상태는 해소되지만, 종료된 프로세스의 연산 결과가 폐기되어 재계산 필요.
2. 프로세스를 하나씩 종료:
   • 교착 상태가 해결될 때까지 하나씩 종료하며, 매번 교착 상태 탐지 알고리즘을 실행해야 하므로 오버헤드가 큼.

문제점:

• 종료 중인 프로세스가 파일이나 공유 데이터를 업데이트 중이라면, 데이터 무결성이 손상될 수 있음.
• 락을 사용 중인 경우, 락 상태를 복구해야 함.

종료 대상 결정 요인:

• 종료 비용 최소화를 위해 다음 요소를 고려:
  1. 프로세스 우선순위.
  2. 프로세스가 수행된 시간과 남은 작업 시간.
  3. 사용 중인 자원 종류와 개수.
  4. 작업 완료에 필요한 추가 자원.
  5. 종료해야 할 프로세스 수.

---

8.8.2 자원 선점 (Resource Preemption)

교착 상태를 해결하기 위해 프로세스에서 자원을 회수(선점)하고 다른 프로세스에 할당.

선점 시 고려해야 할 3가지 문제:

1. 희생자 선택:
   • 어떤 프로세스와 자원을 선점할 것인지 결정.
   • 최소 비용 기준으로 선택(예: 점유 중인 자원 개수, 소모된 시간 등).
2. 롤백 (Rollback):
   • 자원을 선점당한 프로세스는 실행을 중단하므로, 안전 상태로 롤백 후 재시작.
   • 간단한 방법은 전체 롤백: 프로세스를 중단 후 처음부터 재시작.
   • 필요한 만큼만 롤백하는 방법은 효율적이지만, 모든 프로세스 상태를 기록해야 하므로 복잡도가 높음.
3. 기아 상태 방지 (Starvation):
   • 특정 프로세스가 반복적으로 선점당해 작업을 완료하지 못하는 상황을 방지.
   • 해결 방법:
     • 롤백 횟수를 비용 요소에 포함하여 동일 프로세스가 계속 희생되지 않도록 제한.