(운영체제) 6 - 교착 상태(데드락)

## 목차 ##

• 1. 교착 상태 개요
• 2. 교착 상태 필요조건
• 3. 교착 상태 해결방법
• 4. 다중 자원과 교착 상태 검출

## 1. 교착 상태 개요 ##

(1) 교착 상태의 정의

• 2개 이상의 프로세스가 다른 프로세스의 작업이 끝나기만 기다리며 더 이상 진행하지 못하는 상태

(2) 교착 상태의 발생

• 동시에 사용할 수 없는 시스템 자원, 공유 변수, 파일, 응용 프로그램 등을 사용할 때 발생할 수 있다.
  • ex) 임계구역에서 두 개 이상의 프로세스가 다른 프로세스가 걸어놓은 락을 해제할 때까지 대기

(3) 자원 할당 그래프

• 프로세스가 어떤 자원을 사용중이고 기다리는지를 표현한 그래프
  • 방향성을 가진다.
  • 프로세스는 동그라미, 자원은 사각형으로 표기한다.
  • 사각형 안의 점은 동시에 사용가능한 자원 수이다.
  • 여러 프로세스가 동시에 사용가능한 자원을 다중 자원이라고 한다.

P1은 R2를 사용중이고 R1 사용을 대기중이다. P2는 R1, R2를 사용중이고 R3 사용을 대기중이다. P3는 R3를 사용중이다.

R2와 R4는 동시에 여러 프로세스가 사용가능한 다중자원이다.

아래 그림은 두 프로세스가 교착상태에 빠진 상태를 표현하는 자원 할당 그래프이다.

## 2. 교착 상태 필요조건 ##

• 식사하는 철학자 문제

  • 식사를 하기 위해서는 왼쪽, 오른쪽 포크 2개가 필요하다.
  • 모든 철학자들이 식사를 할 수 없어 굶어죽게 된다는 문제이다.
  • 교착 상태의 비유로 자주 쓰인다.

• 철학자가 식사를 할 수 없게되는 필요조건

  • 포크는 공유될 수 없다.(상호 배제)
  • 다른 철학자의 포크를 빼앗을 수 없다.(비선점)
  • 포크 하나를 집은 상태에서 다른 포크를 기다린다.(점유와 대기)
  • 자원 할당 그래프가 원형이다.(원형 대기)

(1) 교착 상태 필요조건

아래의 4가지 조건이 모두 충족되었을 때 교착상태 발생

• 상호 배제

  • 임계구역으로 보호된 배타적인 자원이어야한다.
  • 여러 프로세스가 동시에 한 자원을 사용할 수 없다.

• 비선점

  • 프로세스가 사용중인 자원은 다른 프로세스가 빼앗을 수 없다.
  • 임계구역으로 보호된 자원은 비선점 조건이 보장된다.

• 점유와 대기

  • 어떤 자원을 할당받은 상태에서 다른 자원을 기다려야한다.
  • 다른 프로세스가 필요한 자원을 점유하면서 또 다른 자원을 기다리는 상태여야한다.

• 원형 대기

  • 점유와 대기를 하는 프로세스들 간에 원형을 이루어야한다.
  • 자원 할당 그래프가 원형이 되어야 서로 양보하지 않는다.

## 3. 교착 상태 해결방법 ##

(1) 교착 상태 해결방법

• 예방

  • 교착 상태를 유발하는 4개의 조건을 무력화한다.
  • 상호 배제, 비선점, 점유와 대기, 원형 대기 네 조건 중 하나라도 막는다면 교착 상태가 발생하지 않는다.
  • 실효성이 적어 잘 사용되지 않는다.

• 회피

  • 교착 상태가 발생하지 않는 수준으로 자원을 할당한다.
  • 교착 상태를 유발할 가능성이 있다고 판단되면 자원 할당을 중지한다.
  • 이 방법도 보장이 되지않고 실효성이 적어 잘 사용하지 않는다.

• 검출과 회복

  • 자원 할당 그래프를 보면서 교착 상태가 발생하는지 모니터링 한다.
  • 교착 상태가 검출되면 회복 단계가 진행된다.
  • 가장 현실적인 접근 방법이다.

(2) 교착 상태 예방

• 상호 배제 예방

  • 상호 배제하는 자원을 없애버리는 방법
  • 현실적으로 불가능하다.

• 비선점 예방

  • 모든 자원을 선점형으로 만드는 방법
  • 임계구역을 보호하기 위한 락을 없애버려야한다.
  • 현실적으로 불가능하다.

• 점유와 대기 예방

  • 프로세스가 자원을 점유한 상태에서 다른 자원을 기다리지 못하게 하는 방법
  • 전부 할당하거나 아니면 아예 할당하지 않는 'nothing or all' 방식
  • 프로세스가 필요한 자원을 한 번에 자세히 알기 어렵다.
  • 좀 더 나중에 필요한 자원까지 미리 선점하여 낭비가 생긴다.
  • 많은 자원을 사용하는 프로세스가 적은 자원을 사용하는 프로세스보다 불리하다.
  • 배치 시스템과 비슷하게 동작한다.

• 원형 대기 예방

  • 자원을 한 방향으로만 사용하도록 하는 방식
  • 자원에 번호를 매긴 후 작은 번호의 자원을 점유 후 다른 자원을 점유해야 한다.

프로세스 P2는 R2를 할당받은 상태이기 때문에 R1 요청이 거절되고 프로세스 P1이 R1과 R2를 할당받게 된다.
+ 프로세스 작업의 유연성이 떨어진다.
+ 마우스를 사용 후 프린터를 사용할 수 없는 것과 같은 일이 발생한다.

• 정리
  • 상호 배제와 비선점 예방은 현실성이 없다.
  • 점유와 대기, 원형 대기 예방은 프로세스 작업 방식을 제한하고 자원을 낭비한다.

(3) 교착 상태 회피

• 교착 상태가 일어나지 않는 범위 내에서만 자원을 할당

  • 할당되는 자원의 수를 조절
  • 자원을 많이 할당할수록 교착 상태가 발생할 확률이 커진다는 사실에서 기인한다.
  • 예방과 다르게 시스템 운영 방식에 변경을 가하지 않아 좀 더 유연하다.

• 은행원 알고리즘

  • 자원이 할당 가능한 범위 내이면 할당해주고 아니면 거부하는 방식
  • 각 프로세스는 자신이 사용할 최대 자원 수를 운영체제에 알려준다.

• 은행원 알고리즘의 자원 할당 기준

  • 기대 자원과 비교하여 가용 자원이 크거나 같으면 프로세스에 자원을 할당한다.
  • 가용 자원보다 작거나 같은 기대자원을 가진 프로세스가 존재하는 경우를 안정상태라고 한다.
  • 즉, 안정상태인 프로세스에만 자원을 할당한다.

• 교착상태 회피의 문제점
  • 프로세스가 미리 자신이 사용할 자원을 선언해야 한다.
  • 시스템의 전체 자원 수가 고정적이어야한다.(실제로는 유동적이다.)
  • 자원이 낭비된다.
  • 실제로 발생하지 않을 경우도 발생할 것이라고 예상해 자원할당에 제약을 둔다.

(4) 교착상태 검출

• 타임 아웃을 이용한 교착상태 검출
  • 일정 시간동안 작업이 진행되지 않은 프로세스를 교착상태로 간주
  • 교착상태가 아닌 작업이 오해받아 강제 종료될 수 있다.
  • 분산 시스템의 경우 적용이 어렵다.(네트워크 문제인지 교착 상태인지 확인이 어렵다.)
  • 그럼에도 불구하고 많은 운영체제에서 선호하는 방식이다.

위의 화면을 자주 보았을것이다. 이러한 경고창이 뜨고 좀 기다리면 다시 실행되는 경우가 있는데, 이는 실제로 교착상태가 아니라 단순히 처리량이 많거나 다른 이유로의 지연이었던 것이다.

• 자원 할당 그래프를 이용한 교착상태 검출
  • 자원 요청 혹은 자원 할당이 발생할 때마다 자원 할당 그래프를 갱신한다.
  • 사이클이 발생하면 교착 상태로 판단한다.
  • 교착 상태를 정확하게 파악할 수 있다.
  • 자원 할당 그래프의 유지, 갱신, 사이클 검사에 추가적인 오버헤드가 발생한다.

(5) 교착상태 회복

• 교착 상태를 유발한 프로세스를 강제 종료한다.

  • 교착 상태를 일으킨 모든 프로세스를 동시에 종료
  • 교착 상태를 일으킨 프로세스 중 하나를 골라 순서대로 종료

• 강제 종료된 프로세스가 재실행되기 전에 시스템을 복구한다.

  • 최근의 체크포인트로 돌아간다.
  • 체크포인트 생성은 작업량이 상당하여 무분별하게 생성하면 안된다.

## 4. 다중 자원과 교착 상태 검출 ##

(1) 다중 자원과 사이클

• 다중 자원에서는 교착상태 검출이 복잡하다.
  • 사이클이 교착상태를 의미하지 않는다.

• 대기 그래프와 그래프 감소 방법을 이용해 교착상태를 찾는다.

(2) 대기 그래프와 그래프 감소

• 대기 그래프
  자원 할당 그래프에서 자원 노드를 제거하고 프로세스간의 기다리는 관계만 표시한 그래프

• 그래프 감소
  • 기다리는 자원이 없는 프로세스와 해당 프로세스를 기다리는 프로세스 사이의 화살표를 제거
  • 이 과정을 가능한 범위까지 진행한 후 사이클이 남아있으면 교착상태로 판단