[운영체제] 교착상태 란??

1. 교착상태란?

 

• 교착상태란 여러 프로세스가 서로가 점유하고 있는 자원을 기다리며 무한히 대기하는 상태를 말함.

 

📌 예시

• 두 차량이 다리에서 마주 보고 멈춘 채, 서로가 후진하길 기다리는 상황
• 시스템에 2개의 테이프 장치가 있고, P1과 P2가 각각 하나씩 점유한 상태에서 서로의 장치를 기다리는 상황

---

2. 교착상태 발생의 4가지 조건

조건명	설명
1. 상호 배제 (Mutual Exclusion)	자원은 한 번에 하나의 프로세스만 사용 가능
2. 점유와 대기 (Hold and Wait)	자원을 점유한 프로세스가 추가 자원을 요청하며 대기
3. 비선점 (No Preemption)	자원을 강제로 회수할 수 없음
4. 순환 대기 (Circular Wait)	프로세스들이 원형 구조로 자원을 기다리는 상황

 

• 이 네 가지 조건이 모두 동시에 만족될 때 교착상태가 발생

---

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

• 프로세스: 원(circle)
• 자원: 사각형(rectangle, 점은 인스턴스 수)
• 요청 간선: 프로세스 → 자원
• 할당 간선: 자원 → 프로세스

 

그래프에 사이클이 존재하고, 자원 유형이 하나의 인스턴스만 가지면 교착상태가 발생인스턴스가 여러 개일 경우 교착상태 가능성은 있지만 반드시 발생하지는 않음

교착상태를 해결하기 위해서는 시스템의 네가지 전략을 사용할 수 있음. 

• 예방(Prevention)
• 회피(Avoidance)
• 탐지(Detection)
• 복구(Recovery)

---

4. 교착상태 예방 (Prevention)

개념

교착상태가 아예 발생하지 않도록 4가지 필요 조건 중 하나 이상을 사전에 제거하는 방식

 

방법

• 상호배제 제거: 자원을 공유 가능하게 만들어 동시 사용 허용
• 점유와 대기 제거: 프로세스가 시작 전에 모든 자원을 한꺼번에 요청하게 하거나, 자원을 점유하지 않은 상태에서만 요청 가능하도록 제한
• 비선점 제거: 추가 자원 요청 시, 점유한 자원을 반납하고 대기
• 순환대기 제거: 자원에 고유 번호를 부여하고, 프로세스가 항상 오름차순으로만 요청하도록 제한

장점

• 교착상태 발생 가능성 자체가 사라짐

단점

• 자원 활용률 저하
• 기아 상태 가능성
• 프로세스의 실행 유연성 낮아짐

---

5. 교착상태 회피 (Avoidance)

개념

교착상태가 발생할 가능성이 있는 **위험 상태(불안정 상태)**로 진입하지 않도록 자원 요청 시 미리 판단하고 회피하는 방식

 

대표 알고리즘: 은행가 알고리즘 (Banker's Algorithm)

• 각 프로세스는 자원에 대한 최대 수요량을 미리 선언
• 자원 요청이 들어오면, 해당 요청을 처리했을 때 시스템이 **안전 상태(Safe State)**를 유지할 수 있는지 판단
• 안전하면 자원 할당, 아니면 거절하고 대기
  
  

장점

• 자원을 보다 효율적으로 사용할 수 있으며, 불필요한 자원 대기를 줄임
• 교착상태를 발생시키지 않으면서도 유연한 자원 관리 가능

단점

• 프로세스가 최대 수요량을 미리 알려야 함
• 안정 상태 판단을 위한 계산이 복잡하고 오버헤드 발생 가능

---

6. 교착상태 탐지 (Detection)

개념

교착상태가 일어날 수 있도록 허용한 뒤, 주기적으로 시스템 상태를 점검하여 교착상태가 발생했는지를 탐지하는 방식

 

방법

• 자원 할당 그래프 또는 Wait-for Graph를 이용해 사이클(주기) 존재 여부 판단
• 자원 유형이 하나만 있는 경우에는 사이클이 교착상태를 의미
• 자원 유형이 여러 개인 경우는 교착상태일 가능성만 있음
  
  

장점

• 자원 활용률이 높음
• 시스템 자원을 유동적으로 사용할 수 있음

단점

• 탐지 알고리즘 수행 오버헤드 발생
• 교착상태가 실제로 발생한 뒤에야 대응 가능

---

7. 교착상태 복구 (Recovery)

개념

탐지 알고리즘에 의해 교착상태가 확인되었을 때, 해당 상태에서 벗어나기 위한 조치를 수행하는 단계

 

방법

• 프로세스 종료: 교착 상태에 있는 모든 프로세스를 강제 종료하거나, 일부만 종료하여 자원 회수
• 자원 선점: 특정 프로세스로부터 자원을 강제로 회수하여 다른 프로세스에게 재할당

장점

• 교착상태에서 자동으로 벗어날 수 있음

단점

• 프로세스 종료 또는 자원 회수는 데이터 손실 및 시스템 불안정을 유발할 수 있음
• 복구 시점 판단이 민감하고 어려움