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

13-1 교착 상태란

• 교착상태(deadlock)
  • 일어나지 않을 사건을 기다리며 진행이 멈추는 현상
  • 예) 식사하는 철학자 문제

자원 할당 그래프

• resource-allocation graph
• 어떤 프로세스가 어떤 자원을 사용하고, 어떤 자원을 기다리는지를 표현하는 그래프
  • 프로세스 → 원
  • 자원의 종류 → 사각형
  • 사용할 수 있는 자원의 개수 → 자원 사각형 내의 점

교착 상태가 발생하면 자원 할당 그래프가 원의 형태를 갖게 된다. 자원 할당 그래프가 원의 형태를 갖는다고 해서 반드시 교착 상태가 발생하는 것은 아니다.

교착 상태 발생 조건

• 상호 배제(mutual exclusion)
  • 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없는 경우
• 점유와 대기(hold and wait)
  • 자원을 할당받은 상태에서 다른 자원을 할당받기를 기다리는 상태
• 비선점(nonpreemptive)
  • 비선점 자원은 그 자원을 사용 중인 프로세스의 작업이 끝나야 사용 가능
  • 다른 프로세스의 자원을 강제로 빼앗지 못하는 경우
• 원형 대기(circular wait)
  • 자원 할당 그래프가 원으로 그려지는 경우

13-2 교착 상태 해결 방법

교착 상태 예방

교착 상태 발생 조건에 부합하지 않게 자원을 분배하여 교착 상태가 발생하지 않게 할 수 있다. 하지만 여러 부작용이 존재한다.

• 상호 배제 제거
  • 모든 자원을 공유할 수 있게 설정
  • 현실적으로는 무리가 있는 방법
• 점유와 대기 제거
  • 특정 프로세스에 자원을 모두 할당하거나, 아예 할당하지 않는 방식
  • 자원이 필요해 기다리는 프로세스와 사용되지 않으면서 할당된 자원의 수가 많아지므로 자원의 활용률이 낮아짐
  • 많은 자원이 필요한 프로세스에 무한정 기다려야 하는 기아 현상 발생 가능
• 비전점 제거
  • CPU와 같이 선점할 수 있는 일부 자원에 대하여 효과적
  • 프린터와 같이 빼앗기 어려운 자원이 존재하여 범용성이 떨어지는 방법
• 원형 대기 조건 제거
  • 모든 자원에 번호를 붙이고 오름차순으로 자원을 할당하여 구현 가능
  • 자원에 번호를 붙이기 어렵고, 번호에 따라 자원 활용률이 떨어질 수 있음

교착 상태 회피

• 교착 상태는 한정된 자원의 무분별한 할당으로 인해 발생한다고 가정
  ⇒ 교착 상태가 발생하지 않도록 조금씩 자원을 할당 + 교착 상태 위험이 있다면 자원 할당 중지
• 안전 상태(safe state)
  • 교착 상태가 발생하지 않고 모든 프로세스가 정상적으로 자원을 할당받고 종료될 수 있는 상태
  • 안전 순서열이 있는 상태
    • 안전 순서열(safe sequence): 교착 상태 없이 프로세스에 자원을 할당할 수 있는 순서
• 불안전 상태(unsafe state)
  • 교착 상태가 발생할 수 있는 상황
  • 안전 순서열이 없는 상황

시스템 상태가 안전 상태에서 안전 상태로 움직이는 경우에만 자원을 할당하면 운영체제는 교착 상태를 회피할 수 있다.

교착 상태 검출 후 회복

운영체제는 자원을 제약 없이 할당하며 교착 상태 발생 여부를 주기적으로 검사한다. 교착 상태가 검출되면 교착 상태를 회복한다.

• 선점을 통한 회복
  • 교착 상태가 해결될 때까지 한 프로세스씩 자원을 몰아주는 방식
  • 다른 프로세스로부터 자원을 강제로 빼앗아 한 프로세스에 할당
• 프로세스 강제 종료를 통한 회복
  • 교착 상태에 놓인 프로세스 모두를 강제 종료 또는 교착 상태가 없어질 때까지 한 프로세스씩 강제 종료
    • 전부 종료하면 작업 내용을 전부 잃을 수 있고, 한 프로세스씩 종료하면 교착 상태를 매번 확인하느라 오버헤드 발생 가능

교착 상태 무시

• 드물게 발생하는 잠재적 문제를 무시하는 타조 알고리즘(ostrich algorithm) 사용