[운영체제] 교착 상태

교착 상태란?

• 일어나지 않을 사건을 기다리며 진행이 멈춰버리는 현상

둘 다 자원 A,B가 모두 필요해서 서로의 자원을 무한정 기다리는 상황

자원 할당 그래프

교착 상태 발생 조건 파악 가능

• 프로세스는 원으로, 자원의 종류는 사각형으로 표현
• 사용할 수 있는 자원의 개수는 자원 사각형 내에 점으로 표현
• 프로세스가 어떤 자원을 할당 받아 사용 중이라면 자원에서 프로세스를 향해 화살표를 표시
• 프로세스가 어떤 자원을 기다리고 있다면, 프로세스에서 자원으로 화살표를 표시

• 자원 할당 그래프로 교착 상태가 언제 발생하는지 확인 가능, 교착 상태가 일어나면 그래프가 원의 형태를 띄고 있음

교착 상태가 발생할 조건

1. 상호 배제 : 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없는 상태
2. 점유와 대기 : 자원을 할당 받은 상태에서 다른 자원을 할당 받기를 기다리는 상태
3. 비선점 : 어떤 프로세스도 다른 프로세스의 자원을 강제로 빼앗지 못하는 상태
4. 원형 대기 : 프로세스들이 원의 형태로 자원을 대기하는 상태

• 네 가지 조건 중 하나라도 만족하지 않으면 교착 상태가 발생하지 않음
• 네 가지 조건을 모두 만족하면 교착 상태가 발생할 수 있음

교착 상태 해결

• 예방, 회피, 검출 후 회복
• 교착 상태 예방
  • 애초에 교착 상태가 발생하지 않도록, 교착 상태 발생 조건(상호 배제, 점유와 대기, 비선점, 원형 대기) 중 하나를 없애버리기
  • 원형 대기 조건을 없애려면 ?
    • 자원에 번호를 붙이고, 오름차순으로 할당하면 원형 대기는 발생하지 않음
  • 교착상태가 발생하지 않음은 보장할 수 있으나 부작용이 따르는 방식
• 교착 상태 회피
  • 교착 상태를 무분별한 자원 할당으로 인해 발생했다고 간주
  • 교착 상태가 발생하지 않을 만큼 조심 조심 할당
  • 배분할 수 있는 자원의 양을 고려하여 교착 상태가 발생하지 않을 만큼만 자원 배분
    • 안전 순서열 : 교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서
    • 안전 상태 : 교착 상태 없이 모든 프로세스가 자원을 할당 받고 종료될 수 있는 상태 (= 안전 순서열이 있는 상태)
    • 불안전 상태 : 교착 상태가 발생할 수도 있는 상태 (= 안전 순서열이 없는 상태)
  • 안전 상태에서 안전 상태로 움직이는 경우에만 자원을 할당하는 방식 -> 항시 안전 상태를 유지하도록 (c.f. 은행원 알고리즘)
• 교착 상태 검출 후 회복
  • 교착 상태의 발생을 인정하고 사후에 조치하는 방식
  • 프로세스가 자원을 요구하면 일단 할당, 교착 상태가 검출되면 회복
  • 선점을 통한 회복
    • 교착 상태가 해결될 때까지 한 프로세스씩 자원을 몰아주는 방식
  • 프로세스 강제 종료를 통한 회복
    • 교착 상태에 놓인 프로세스 모두 강제 종료 (-> 작업 내역을 잃을 위험)
    • 교착 상태가 해결될 때까지 한 프로세스씩 강제 종료 (-> 오버헤드)