[혼공컴운] ch.13 교착 상태

13-1. 교착 상태란

1. 식사하는 철학자 문제

• 교착 상태를 설명하기 위한 상황

• 상황

  • 계속 생각을 하다 왼쪽 포크가 사용 가능하면 집어든다.
  • 계속 생각을 하다 오른쪽 포크가 사용 가능하면 집어든다.
  • 왼쪽과 오른쪽 포크를 모두 집어들면 정해진 시간동안 식사를 한다.
  • 식사 시간이 끝나면 오른쪽 포크를 내려놓는다.
  • 오른쪽 포크를 내려놓은 뒤 왼쪽 포크를 내려놓는다.
  • 다시 1번부터 반복한다.

[문제 발생]
모든 철학자가 동시에 포크를 집어 식사를 하면 어떤 철학자도 식사를 할 수 없고 영원히 생각만 하는 상황이 발생할 수 있다.

• 교착 상태 : 일어나지 앟을 사건을 기다리며 진행이 멈춰 버리는 현상

2. 자원 할당 그래프

• 어떤 프로세스가 어떤 자원을 사용하고 있고, 또 어떤 프로세스가 어떤 자원을 기다리고 있는지를 표현하는 간단한 그래프

• 규칙

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

3. 교착 상태 발생 조건

• 상호 배제(mutual exclusion)
• 점유와 대기(hold and wait)
  • 자원을 할당받은 상태에서 다른 자원을 할당받기를 기다리는 상태
• 비선점(nonpreemptive)
  • 그 자원을 이용하는 프로세스의 작업이 끝나야만 비로소 이용 가능
• 원형 대기(circular wait)
  • 프로세스들이 원의 형태로 자원을 대기하는 것

/

13-2. 교착 상태 해결 방법

1. 교착 상태 예방

• 교착 상태 발생 필요 조건 네 가지 중 하나의 조건이라도 만족하지 않는다면 교착 상태 발생하지 않음

• 상호 배제 없앨 경우 : 현실 사용에 무리

• 점유와 대기 없앨 경우 : OS는 특정 프로세스에 자원을 모두 할당하거나 아예 할당하지 않는 방식으로 배분

• 비선점 조건 없앨 경우 : 일부 자원에는 효과적이나 범용성이 떨어지는 방안

• 원형 대기 조건 없앨 경우 : 가장 현실적이로 실용적이나, 특정 자원의 활용률 저하 가능성

2. 교착 상태 회피

• 교착 상태가 발생하지 않을 정도로만 자원을 할당하는 방식
  • 안전 상태(safe state) : 교착 상태가 발생하지 않고 모든 프로세스가 정상적으로 자원을 할당받고 종료될 수 있는 상태
  • 불안전 상태(unsafe state) : 교착 상태가 발생할 수도 있는 상황
  • 안전 순서열(safe sequence) : 교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서
    • 즉, 안전 상태 = 안전 순서열 존재 / 불완전 상태 = 안전 순서열 존재 X

3. 교착 상태 검출 후 회복

• 교착 상태 발생을 인정하고 사후에 조치하는 방식

• 선점을 통한 회복 : 교착 상태 해결될 때까지 한 프로세스씩 자원을 몰아주는 방식

• 프로세스 강제 종료를 통한 회복