혼자 공부하는 컴퓨터 구조 + 운영체제 Section 13. 교착 상태

강의 링크

교착 상태란

식사하는 철학자 문제

• 철학자 = 프로세스, 스레드
• 포크 = 실행에 꼭 필요한 자원
• 서로가 점거하는 자원을 서로가 기다리고 있을 경우 어떤 프로세스나 스레드도 끝까지 실행될 수 없음

교착 상태

• 일어나지 않을 사건을 기다리며 진행이 멈춰 버리는 현상
• 교착 상태 해결을 위해서는
  • 1. 교착 상태가 발생했을 때의 상황을 정확히 표현해야
    • 자원 할당 그래프
  • 2. 교착 상태가 일어나는 근본적인 이유를 이해해야
    • 교착 상태 발생 조건

자원 할당 그래프

• 교착 상태 발생 조건 파악 가능
  • 어떤 프로세스가 어떤 자원을 할당 받아 사용 중인지 확인 가능
  • 어떤 프로세스가 어떤 자원을 기다리고 있는지 확인 가능

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

교착 상태 발생 조건

• 1. 상호 배제
  • 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없는 상태
• 2. 점유와 대기
  • 자원을 할당받은 상태에서 다른 자원을 할당받기를 기다리는 상태
• 3. 비선점
  • 어떤 프로세스도 다른 프로세스의 자원을 강제로 빼앗지 못하는 상태
• 4. 원형 대기
  • 프로세스들이 원의 형태로 자원을 대기하는 상태
• 네 가지 조건 중 하나라도 만족하지 않으면 교착 상태가 발생하지 않음
• 네 가지 조건을 모두 만족하면 교착 상태가 발생할 수 있음

교착 상태 해결 방법

• 교착 상태 해결: 예방, 회피, 검출 후 회복

교착 상태 예방

• 애초에 교착 상태가 발생하지 않도록
• 교착 상태 발생 조건 (상호 배제, 점유와 대기, 비선점, 원형 대기) 중 하나를 없앰
  • 상호 배제를 없애면
    • 모든 자원을 공유 가능하게 만듦
    • 현실적인 방법은 아님
  • 점유와 대기를 없애면
    • 특정 프로세스에 자원을 모두 할당하거나, 아예 할당하지 않는 방식으로 배분
    • 자원의 활용률을 낮출 수 있는 방식
  • 비선점을 없애면
    • 선점이 가능한 자원(e.g. CPU)에 한해 효과적
    • 모든 자원이 선점 가능한 것은 아님
  • 원형 대기를 없애면
    • 자원에 번호를 붙이고 오름차순으로 할당하면 원형 대기는 발생하지 않음
    • 자원에 번호 붙이는 것은 어려운 작업
    • 어떤 자원에 어떤 번호를 붙이느냐에 따라 활용률이 달라짐
• 교착 상태가 발생하지 않음은 보장할 수 있으나 부작용이 따르는 방식

교착 상태 회피

• 교착 상태를 무분별한 자원 할당으로 인해 발생했다고 간주
• 교착 상태가 발생하지 않을 만큼 조심하여 할당
• 배분할 수 있는 자원의 양을 고려하여 교착 상태가 발생하지 않을 만큼만 자원 배분
• 안전 순서열
  • 교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서
• 안전 상태
  • 교착 상태 없이 모든 프로세스가 자원을 할당 받고 종료될 수 있는 상태
  • 안전 순서열이 있는 상태
    
    • e.g. P2 -> P1 -> P3 (안전 순서열)
    • 프로세스 P1, P2, P3가 모두 최대로 자원을 요구한 최악의 상황을 가정
      • P1, P2, P3가 각각 5개, 2개, 7개의 자원을 요구한 상황
    • P2는 이미 2개의 자원을 갖고 있으므로 남은 자원에서 2개를 배분 (할당 자원 11, 남은 자원 1)
    • P2는 정상적으로 작업을 끝낸 뒤 갖고 있던 자원을 반환 (남은 자원 5)
    • P1에 남은 자원을 모두 할당 (남은 자원 0), 정상적으로 작업 종료 (남은 자원 10)
    • P3에 요구하는 자원을 할당하면 모든 프로세스 실행 가능
• 불안전 상태
  • 교착 상태가 발생할 수도 있는 상태
  • 안전 순서열이 없는 상태
    • 만약 위의 예시에서 운영체제가 남은 자원 3개 중 하나를 P3에 주었다고 했을 때, 불안전 상태
    • P2에 자원 2개를 할당하여 작업을 끝내도 남은 자원으로는 P1, P3 요구를 들어줄 수 없음 (교착상태 발생 위험)
• 안전 상태에서 안전 상태로 움직이는 경우에만 자원을 할당하는 방식
• 항시 안전 상태를 유지하도록 자원을 할당하는 방식
• c.f. 은행원 알고리즘

교착 상태 검출 후 회복

• 교착 상태의 발생을 인정하고 사후에 조치하는 방식
• 프로세스가 자원을 요구하면 일단 할당, 교착 상태가 검출되면 회복
• 선점을 통한 회복
  • 교착 상태가 해결될 때까지 한 프로세스씩 자원을 몰아주는 방식
• 프로세스 강제 종료를 통한 회복
  • 교착 상태에 놓인 프로세스 모두 강제 종료 (-> 작업 내역을 잃을 위험)
  • 교착 상태가 해결될 때까지 한 프로세스씩 강제 종료 (-> 오버헤드)

교착 상태 무시

• 타조 알고리즘