[OS] 교착상태(Deadlocks)

교착상태란

세마포어 사용 예

교착상태

• 차단된 프로세스 집합의 경우 각 프로세스는 리소스를 보유하고 있으며 집합의 다른 프로세스가 보유한 리소스를 획득하기 위해 대기

 

---

교착 상태 특성화

시스템 모델링

• 프로세스: P1, P2, … Pn.
• 자원 유형: R1, R2, …, Rm
  
  • CPU 주기, 메모리 공간, I/O 장치, 파일 등.
• 각 리소스 유형의 Ri에는 Wi 인스턴스가 있다.
• 각 프로세스는 다음과 같이 리소스를 활용
  
  • request
  • use
  • release

네 가지 조건이 동시에 유지되면 교착 상태가 발생

1. 상호 배제(Mutual exclusion)
   
   • 한 번에 하나의 프로세스만 리소스를 사용 가능
2. 점유 및 대기(Hold and wait)
   
   • 하나 이상의 리소스를 보유한 프로세스가 다른 프로세스에서 보유한 추가 리소스를 획득하기 위해 대기 중
3. 비선점(No preemption)
   
   • 리소스는 보유 프로세스에 의해서만 자발적으로 해제 가능
4. 순환 대기(Circular wait)
   
   • P0, P1, …, P0개의 대기 프로세스 집합
     
     • P0이 P1이 보유한 리소스를 대기
     • P1이 P2가 보유한 리소스를 대기
     • ...,
     • Pn–1은 Pn이 보유한 리소스를 대기
     • Pn이 P0이 보유한 리소스를 대기

리소스 할당 그래프

• V는 두 가지 유형으로 분할
  
  • P = {P1, P2, …, Pn}, 시스템의 모든 프로세스 집합
  • R = {R1, R2, …, Rm} 시스템의 모든 리소스 유형 집합
• E도 두 가지 유형으로 분할
  
  • Pi → Rj : 요청
    Rj → Pi : 할당

예

Pi가 Rj의 인스턴스를 요청

Pi는 R의 인스턴스를 보유

리소스 할당 그래프를 사용한 교착 상태 예제

• 그래프에 주기가 없는 경우,
  • 교착 상태 없다.
• 그래프에 주기가 포함된 경우,
  
  • 리소스 유형당 하나의 인스턴스만 있는 경우 교착 상태
  • 리소스 유형당 여러 인스턴스가 있는 경우 교착 상태일 가능성

 

---

교착 상태 처리 방법

예방

• 시스템이 교착 상태에 빠지지 않는다.
• 네 가지 조건 중 하나 이상을 유지할 수 없다.

회피

• 시스템이 교착 상태에 빠지지 않는다.
• 각 프로세스가 리소스를 어떻게 활용할 것인지에 대한 사전 정보가 필요

탐지 및 복구

• 시스템이 교착 상태에 빠졌다가 복구될 수 있다.

 

---

교착 상태 방지

네 가지 조건 중 하나 이상을 유지할 수 없다.

상호 배제(Mutual Exclusion)

• 상호 배제를 부인하는 것은 불가능

점유 및 대기(Hold and Wait)

• 프로세스가 실행을 시작하기 전에 모든 리소스를 요청하고 할당 가능

비선점(No Preemption)

• 일부 리소스를 보유하고 있는 프로세스가 즉시 할당할 수 없는 다른 리소스를 요청하면 현재 보유한 모든 리소스 해제
• 프로세스는 요청 중인 새 리소스뿐만 아니라 이전 리소스도 되찾을 수 있을 때만 다시 시작

순환 대기(Circular Wait)

• 모든 리소스 유형의 총 순서를 지정하며, 각 프로세스에서 열거 순서가 증가하는 리소스를 요청

 

---

교착 상태 회피

교착 상태 회피 알고리즘

• 프로세스가 사용 가능한 리소스를 요청할 때 시스템은 즉시 할당이 시스템을 안전한 상태로 유지하는지 여부 결정
  
  • 시스템이 각 프로세스에 리소스를 어떤 순서로(최대치까지) 할당할 수 있지만 교착 상태를 피할 수 있다면 상태는 안전
• 시스템에 몇 가지 추가적인 사전 정보가 있어야 한다.

시스템이 안전한 상태(safe state)인 경우,

• 교착 상태 없음

시스템이 안전하지 않은 상태(unsafe state)인 경우,

• 교착 상태가 발생 가능성

리소스 할당 그래프

• 클레임 에지 Pi → Rj
  
  • Pj는 Rj를 요청할 수 있다.
  • 점선으로 표시
• 클레임 에지가 요청 에지로 변환
  
  • 프로세스가 리소스를 요청할 때
• 요청 에지가 할당 에지로 변환
  
  • 리소스가 프로세스에 할당될 때
• 할당 에지가 클레임 에지로 다시 변환
  
  • 프로세스에 의해 리소스가 해제될 때

[참고]

• 리소스 유형의 인스턴스가 여러 개일 경우 banker 알고리즘을 사용

안전하지 않은 상태 예제

주기 없음 -> 안전 -> 허가 / 주기 -> 안전하지 않음 -> 거부

 

---

교착 상태 감지 및 복구

시스템이 교착 상태로 전환되도록 허용

탐지 알고리즘

• 그래프에서 주기적으로 주기를 검색하는 알고리즘을 호출
  
  • 주기가 있으면 교착 상태가 발생
• [참고] 리소스 유형의 인스턴스가 여러 개인 경우 더 복잡한 알고리즘을 사용

복구 구성표

• 프로세스 종료
  
  • 교착 상태의 모든 프로세스를 중단
  • 교착 상태 주기가 제거될 때까지 한 번에 하나의 프로세스를 중단
• 자원 선점
  
  • 프로세스에서 일부 리소스를 선점하고 교착 상태 주기가 중단될 때까지 이러한 리소스를 다른 프로세스에 제공

---

요약

• 교착 상태
  • 프로세스가 대기 프로세스로 인해 발생하는 이벤트를 무한정 기다리는 상황
  • 네 가지 조건이 동시에 유지될 경우 발생
    
    1. 상호 배제(mutual exclusion)
    2. 점유 및 대기(hold and wait)
    3. 비선점(no preemption)
    4. 순환 대기(circular wait)
• 교착 상태 방지
  • 네 가지 조건 중 하나 이상을 유지할 수 없도록 한다.
  • 시스템이 안전하지 않은 상태(unsafe state)로 전환되지 않는다.
• 교착 상태 감지 및 복구
  • 시스템을 교착 상태로 전환