교착 상태
교착 상태의 개요
교착 상태의 정의
2개 이상의 프로세스가 다른 프로세스의 작업이 끝나기만을 기다리며 작업을 더 이상 진행하지 못하는 상태를 교착 상태라고 한다.
교착 상태의 발생
- 시스템 자원 : 다른 프로세스와 공유할 수 없는 자원(ex 프린터, CD 레코더)을 사용할 때 발생한다. 프로세스 P1은 프린터를 할당받은 후 CD 레코더를 기다리고 프로세스 P2는 CD 레코더를 할당받은 후 프린터를 기다리면 교착 상태가 발생한다.
- 공유 변수 : 프로세스가 임계 구역에 들어가기 전에 무한 대기에 빠졌을 때 발생한다. (262p 한정 대기 문제)
- 응용 프로그램 : 데이터베이스는 데이터의 일관성을 유지하기 위해 잠금을 사용하는데, 이때 교착 상태가 발생할 수 있다.
자원 할당 그래프
프로세스가 어떤 자원을 사용 중이고 어떤 자원을 기다리고 있는지를 방향성이 있는 그래프로 표현한 것이다.
교착 상태 필요조건
교착 상태 필요조건
교착 상태는 상호 배제, 비선점, 점유와 대기, 원형 대기를 모두 충족해야 할생하고, 이 중 단 하나라도 충족하지 않으면 발생하지 않는다.
- 상호 배제 : 한 프로세스가 사용하는 자원은 다른 프로세스와 공유할 수 없는 배타적인 자원이어야 한다.
- 비선점 : 한 프로세스가 사용 중인 자원은 다른 프로세스가 빼앗을 수 없는 비선점 자원이어야 한다.
- 점유와 대기 : 프로세스가 어떤 자원을 할당받은 상태에서 다른 자원을 기다리는 상태여야 한다.
- 원형 대기 : 점유와 대기를 하는 프로세스 간에 관계가 원을 이루어야 한다.
교착 상태 해결 방법
- 교착 상태 예방 : 교착 상태를 유발하는 네 가지 조건을 무력화한다.
- 교착 상태 회피 : 교착 상태가 발생하지 않는 수준으로 자원을 할당한다.
- 교착 상태 검출 : 자원 할당 그래프를 사용하여 교착 상태를 발견한다.
- 교착 상태 회복 : 교착 상태를 검출한 후 해결한다.
교착 상태 예방
- 상호 배제 예방
시스템 내에 있는 상호 배타적인 모든 자원, 즉 독점적으로 사용할 수 있는 자원을 없애버리는 방법이다.
그러나 현실적으로는 모든 자원을 공유할 수 없으며 상호 배제를 적용하여 보호해야 하는 자원이 있다.
- 비선점 예방
모든 자원을 빼앗을 수 있도록 만드는 방법이다.
그러나 임계구역을 보호하기 위해 잠금을 사용하면 자원을 빼앗을 수 없을 뿐만 아니라 상호 배제도 보장할 수 없다.
게다가 이런 방법은 우선순위가 가장 낮은 프로세스에 아사 현상을 일으킨다.
- 점유와 대기 예방
프로세스가 자원을 점유한 상태에서 다른 자원을 기다리지 못하게 하는 방법이다.
다시 말해 ‘전부 할당하거나 아니면 아예 할당하지 않는’ 방식을 적용하는 것이다.
- 추가로 필요한 자원이 생기면 이를 다시 확보하기가 어렵다.
- 자원의 활용성이 떨어진다.
- 많은 자원을 사용하는 프로세스가 적은 자원을 사용하는 프로세스보다 불리하다.
- 결국 일괄 작업 방식으로 동작한다.
- 원형 대기 예방
점유와 대기를 하는 프로세스들이 원형을 이루지 못하고 자원을 한 방향으로만 사용하도록 설정함으로써 원형 대기를 예방할 수 있다.
- 프로세스 작업 진행에 유연성이 떨어진다.
- 프로세스가 큰 번호의 자원을 사용한 후 작은 번호의 자원을 사용할 수 없다.
교착 상태 회피
자원의 수를 기준으로 시스템을 안정 상태와 불안정 상태로 나누고 시스템이 안정 상태를 유지하도록 자원을 할당한다.
- 은행원 알고리즘
- 전체 자원 : 시스템 내 전체 자원의 수
- 가용 자원 : 시스템 내 현재 사용할 수 있는 자원의 수 (전체 자원-할당 자원)
- 최대 자원 : 각 프로세스가 선언한 최대 자원의 수
- 할당 자원 : 각 프로세스에 현재 할당된 자원의 수
- 기대 자원 : 각 프로세스가 앞으로 사용할 자원의 수 (최대 자원-할당 자원)
안정 상태 : 각 프로세스의 기대 자원과 비교하여 가용 자원이 크거나 같은 경우가 한 번 이상인 경우를 말한다.
- 교착 상태 회피의 문제점
- 프로세스가 자신이 사용할 모든 자원을 미리 선언해야 한다.
- 시스템의 전체 자원 수가 고정적이어야 한다.
- 자원이 낭비된다.
교착 상태 검출
- 타임아웃을 이용한 교착 상태 검출
일정 시간 동안 작업이 진행되지 않은 프로세스를 교착 상태가 발생한 것으로 간주하여 처리하는 방법이다.
- 엉뚱한 프로세스가 강제 종료될 수 있다.
- 모든 시스템에 적용할 수 없다.
- 자원 할당 그래프를 이용한 교착 상태 검출
자원 할당 그래프를 유지하고, 갱신하고, 사이클을 검사하는 추가 작업으로 인해 오버헤드가 발생하는 단점이 있다.
교착 상태 회복
- 교착 상태를 일으킨 모든 프로세스를 동시에 종료
- 교착 상태를 일으킨 프로세스 중 하나를 골라 순서대로 종료
- 우선순위가 낮은 프로세스를 먼저 종료한다.
- 우선순위가 같은 경우 작업 시간이 짧은 프로세스 먼저 종료한다.
- 위의 두 조건이 같은 경우 자원을 많이 사용하는 프로세스를 먼저 종료한다.