[운영 체제] 6강 - 교착 상태

💡해당 게시글은 방송통신대학교 김진욱 교수님의 '운영 체제' 강의를 개인 공부 목적으로 메모하였습니다.

학습 개요

---

• 병행 프로세스들은 컴퓨터 시스템의 제한된 자원을 사용하기 위해 서로 경쟁할 수 있음
• 만일 어떤 프로세스가 사용하고자 하는 자원을 다른 프로세스가 온전히 점유하고 있다면 그 프로세스는 대기해야 함
• 이렇게 요구와 점유 및 이에 따른 대기 상태가 서로 꼬리를 물고 있게 되면, 이러한 관계에 포함된 프로세스들은 더 이상 진행하지 못하게 되는 상태인 교착 상태에 빠질 수 있음
• 운영체제는 이러한 교착 상태를 예방하거나 제거함으로써 프로세스의 동작이 원활하게 이루어지도록 해야 함
• 교착 상태의 개념과 특성을 살펴보고, 교착 상태를 다루는 여러 기법 중 교착 상태를 예방하는 방법에 대해 알아봄

학습 목표

---

• 교착 상태의 개념을 설명할 수 있음
• 교착 상태가 발생하기 위한 필요 조건을 설명할 수 있음
• 자원 할당 그래프의 개념을 설명할 수 있음
• 교착 상태를 예방하는 방법을 설명할 수 있음

강의록

---

교착 상태의 개요

프로세스의 자원 사용 절차

• 요구 → 사용 → 해제
• 요구 과정에서 가용한 자원이 없으면
  • 자원을 획득할 때까지 대기

교착 상태(deadlock)

• 여러 개의 프로세스가 서로 상대방의 작업이 끝나기만 기다리고 있어 어느 쪽도 영원히 진행하지 못하는 상태

교착 상태와 기아 상태의 차이

• 교착 상태

  

  • 영원히 멈춰 있는 상태

• 기아 상태

  

  • 현재도 멈춰있고 당분간 멈춰있지만 분명히 해소될 가능성이 있는 상태

교착 상태의 특성

교착 상태의 필요 조건

• 네 가지 조건이 동시에 만족 될 때 교착 상태 발생 가능
  • 상호 배제
  • 점유 대기
  • 비선점
  • 환형 대기

상호 배제(mutual exclusion) 조건

• 프로세스가 자원에 대한 배타적인 통제권을 요구
• 적어도 하나 이상의 자원은 여러 프로세스에 의해 동시에 사용될 수 없음
• 다른 프로세스가 점유한 자원이 필요하면 반드시 대기

점유 대기(hold and wait) 조건

• 프로세스가 이미 한 자원을 할당 받아 점유하고 있는 상황에 다른 프로세스가 점유하고 있는 또 다른 자원을 요구하여 해제 되기를 기다리는 상황

비선점(no preemption) 조건

• 프로세스 할당 된 자원은 그 프로세스가 사용을 마치고 스스로 반환하기 전에는 해제되지 않음
• 할당 된 자원은 타의에 의해서 해제 되지 않음

환형 대기(circular wait) 조건

• 프로세스의 자원 점유 및 점유 된 자원의 요구 관계가 환형을 이루며 대기하는 상황

자원 할당 그래프 G = (V, E)

• V
  • 정점의 집합 V = P ∪ R
  • P = {p₁, p₂, …, pₙ}
    • n개의 프로세스
  • R = {r₁, r₂, …, rₘ}
    • m개의 자원
• E
  • 방향 있는 간선의 집합 E = Q ∪ S
  • Q = { (pᵢ, rⱼ) pᵢ ∈ P, rⱼ∈ R }

    • 프로세스 pᵢ가 자원 rⱼ를 요구

      

  • S = { (rⱼ, pᵢ) : rⱼ∈ R, pᵢ ∈ P }

    • 자원 rⱼ가 프로세스 pᵢ에 할당

      

자원 할당 그래프 예

• 정점의 집합 V = P ∪ R
  • 프로세스 집합 P = {p₁, p₂, p₃}
  • 자원 집합 R = {r₁, r₂, r₃}
• 방향 있는 간선의 E = Q ∪ S
  • 요구 간선 집합 Q = { (p₁, r₁) }
  • 할당 간선 집합 S = { (r₁, p₁), (r₂, p₂), (r₃, p₃) }

자원 할당 그래프의 변화

• p₂가 r₃을 요구하는 경우
  • 요구 간선(p₂, r₃) 추가
  • 가용한 단위 자원 존재하면 할당 간선 (r₃, p₂)로 바꿈

자원 할당 그래프

• 교착 상태의 필요 조건 표현

  

  • 상호 배제
    • 하나의 할당 간선
  • 점유 대기
    • 한 프로세스에 할당 간선과 요구 간선 연결
  • 비선점
    • 요구 간선
  • 환형 대기
    • 사이클(cycle)
• 사이클 없음
  • 교착 상태 없음
• 사이클 있음
  • 교착 상태 발생 가능

• ex) 교착 상태 예

  

• ex) 교착 상태 아닌 예

  

교착 상태의 처리 기법

• 교착 상태 예방
  • 교착 상태의 네 가지 필요 조건이 동시에 만족 되는 것을 피하여 교착 상태가 발생하지 않도록 하는 방법
• 교착 상태 회피
  • 프로세스에 필요한 자원의 최대 량에 대한 정보를 이용하여 교착 상태가 발생하지 않도록 하는 방법
• 교착 상태 탐지 및 복구
  • 교착 상태의 발생 여부를 조사하여 발생한 경우에는 적절한 조치를 취해 정상 상태로 복구하는 방법

교착 상태 예방

상호 배제 조건 제거

• 공유할 수 있는 자원
  • 상호 배제 필요 없음
  • ex) 읽기 전용 파일
• 공유할 수 없는 자원
  • 반드시 상호 배제 필요
  • ex) 프린터
  • 상호 배제 조건 제거로 교착 상태 예방은 불가능

점유 대기 조건 제거

• 자원을 점유했을 때 대기하지 않아야 함
  • 프로세스가 앞으로 필요한 모든 자원을 처음에 한꺼번에 요구하여 할당 받음
    • 자원 이용률 낮아짐, 기아 상태 가능
• 대기할 때 자원을 점유하고 있지 않아야 함
  • 새로운 자원을 요구할 때 할당 받았던 자원을 모두 해제
    • 점유 도중 해제할 수 없는 자원에는 적용 불가

비선점 조건 제거

• 선점이 가능하도록 해야 함
  • 자원의 특성에 따라 불가능한 경우 존재
  • ex) 프린터
• 다른 프로세스가 대기할 가능성 줄이기
  • 점유 대기 상황이 발생하면 할당 받았던 자원을 모두 해제
    • 프린터 같은 자원에는 적용 불가

환형 대기 조건 제거

• 모든 자원에 일련 번호를 지정
  • 함수 f:R → N (R: 자원 집합, N: 자연수 집합)
    • rᵢ ≠ rⱼ이면 f(rᵢ) ≠ f(rⱼ)
• 방법 1
  • 프로세스는 자원을 요구할 때 일련 번호 기준으로 항상 오름차순이 되도록 요구
  • 가장 최근에 할당 받은 자원이 rᵢ이면 다음에 요구할 자원rⱼ는 f(rᵢ) < f(rⱼ) 만족
• 방법 2
  • 프로세스가 자원을 요구할 때 그보다 일련번호가 작은 자원만 점유하도록 함
  • 자원 rⱼ 요구하려면 점유 중인 자원 중 f(rⱼ) ≤ f(rᵢ) 인 rᵢ는 모두 해제
• 점유 대기 중인 프로세스는 점유 중인 자원의 일련 번호보다 대기 중인 자원의 일련 번호가 큼
  • 환형 대기 발생 불가능
• 프로세스마다 요구 순서가 다를 수 있어 자원의 일련 번호 설정이 어려움
• 요구 순서가 일련번호 오름차순을 못 지키면 점유 자원 해제 필요하나 적용 불가한 자원 존재

정리 하기

---

• 교착 상태는 여러 개의 프로세스가 서로 상대방의 작업이 끝나기만 기다리고 있기 때문에 결과적으로 어느 쪽도 영원히 진행하지 못하는 상태임
• 교착 상태의 네 가지 필요조건은 상호 배제, 점유 대기, 비선점, 환형 대기로, 이 조건들이 모두 만족 될 경우 교착 상태가 발생할 수 있음
• 자원 할당 그래프는 프로세스와 자원 사이에 요구와 할당 관계를 나타내는 그래프로, 사이클의 존재 유무를 통해 교착 상태의 발생 가능성을 확인할 수 있음
• 교착 상태를 처리하는 기법에는 교착 상태 예방, 교착 상태 회피, 교착 상태 탐지 및 복구가 있음
• 교착 상태 예방은 교착 상태의 네 가지 필요조건 중 어느 하나라도 발생할 수 없도록 막는 방법임