교착 상태와 기아 상태

1. 교착 상태의 개념과 발생 원인

1. 교착 상태의 개념

다중 프로그래밍 시스템에서는 프로세스가 결코 일어나지 않을 사건을 기다리는 상태가 되면 교착상태에 빠졌다고 말한다. 교착 상태는 하나 이상의 작업에 영향을 주기 때문에 무한 대기나 기아 상태보다 더 심한 문제를 일으킨다. 교착 상태는 시스템 자원에 요구가 뒤 엉킨 상태로, 두 프로세스가 사용하는 자원(비공유)을 서로 기다리고 있을 때 발생한다. 따라서 둘 이상의 작업이 중단되고 프로세스들은 서로 사용할 자원을 기다리고만 있게 된다.

두 프로세스는 서로 차단되어 영원히 기다리게 되는데 이 상황이 바로 교착상태이다. 둘 이상의 프로세스가 다른 프로세스가 점유하고 있는 자원을 서로 기다릴 때 교착상태가 발생한다. 초기 일괄 처리 시스템에서는 교착 상태가 자주 발생하지 않았다. 일괄처리 시스템에서는 운영체제가 요청한 자원을 준비 큐로 이동시키기 전에 먼저 사용 가능 여부를 확인했다. 반면에 대화식 시스템에서는 동적 자원을 공유하여 자원의 사용률을 높이는 과정에서 교착 상태가 발생할 가능성이 있었다. 

* 보통 프로세스는 다음 순서로 자원을 사용한다.

• 자원의 요청(Request): Blocked -> Ready
• 사용(Allocate,User): Ready -> Running
• 해제(Release): Running -> Terminated
  

2. 교착 상태의 예

* 네트워크에서 발생하는 교착 상태

출발지가 노드 N6과 노드 N7이고 목적지가 노드 N2인 메시지는 노드 N1의출력 큐에 임시 저장된다. 또 출발지가 노드 N3과 노드 N4이고 목적지가 노드 N1인 메세지는 노드 N2의 출력 큐에 임시 저장된다. 이때 트래픽이 증가하면 각 출력 큐의 크기도 증가한다. 노드 N1의 버퍼 공간이 부족하여 메세지를 더 이상 저장할 수 없으면 노드 N1은 노드 N2에서 메세지를 받을 수 없다. 또 노드 N2도 버퍼 공간이 부족하여 노드 N1이나 다른 노드에서 메세지를 수신할 수 없게 되면, 노드 N1과 노드N2 사이의 통신 선로는 더 이상 메세지를 전송할 수 없는 교착상태에 빠진다. N1은 N6와 N7에서는 메세지를  전송받을 수 있지만, 노드 N2로는 메세지 전송이 불가능하므로 곧 교착상태에 빠진다.

3. 교착 상태의 발생 조건

1. 상호배제 : 자원이 최소하나 이상의 프로세스에 의해 비공유되어야 한다. 즉, 한번에 하나만 해당 자원을 사용할 수 있어야한다.
   
2. 점유와 대기 : 자원을 최소한 하나 보유하고 다른 프로세스에 할당된 자원을 얻으려고 기다리는 프로세스가 있어야 한다.
3. 비선점 : 자원은 선점할 수 없다.
4. 순환대기 : 다른 프로세스가 보유한 자원을 각각 얻으려고 기다리는것 

* 선점 자원과 비선점 자원

컴퓨터의 자원은 성질에 따라 선점 자원과 비선점 자원으로 구분하여 생각할 수 있다. 선점 자원은 부작용 없이 소유한 프로세스에서 빼앗아 선점할 수 있는 자원이다. 선점 자원의 예로는 메모리, 버퍼, 프로세스 등이 있다. 반면에 비선점 자원은 하나의 프로세스에서 빼앗아 선점할 수 없고, 부작용 없이 다른 프로세스에 할당할 수 없는 자원이다. 비선점 자원의 예로는 프린터, CD드라이브, 스캐너, 디스크 드라이브, 임계영역 등이 있다. 보통 교착 상태는 비선점 자원이 발생 시킨다.

2. 교착 상태의 해결 방법

교착상태의 해결하는 방법은 크게 다음 세 가지로 나눌 수 있다.

1. 교착 상태가 발생하지 않도록 예방(prevention)하는 방법
2. 교착 상태의 발생 가능성을 배제하지 않고 이를 적절히 회피(Avoidance)하는 방법
3. 교착 상태를 허용하되 교착 상태를 탐지(Detection)하여 다시 회복하는 방법

1. 교착 상태 예방

보통 교착상태는 다음 네 가지 방법으로 예방할 수 있다.

1. 자원의 상호배제 조건 방지
2. 점유와 대기 조건 방지 (일부 자원만 할당 방지)
3. 비선점 조건 방지 (할당된 자원의 반납 가능)
4. 순환(환형) 대기 조건 방지 (순환 대기 상황 회피

* 자원의 상호배제 조건 방지

상호배제는 자원의 비공유가 전제되어야 한다. 공유 자원은 배타적인 접근이 필요 없으므로 교착 상태가 발생하지 않는다. 그러나 일발적으로 상호배제 조건을 허용하지 않으면 교착 상태를 예빙할 수 없다. (비현실 적이다)

* 점유와 대기 조건 방지

프로세스가 실행에 필요한 자원을 한꺼번에 요구하고 허용할 때까지 작업을 보류하여 대기 조건이 성립하지 않도록 하여 교착상태를 예방한다. 시스템 호출된 프로세스 하나를 실행하는 데 필요한 모든 자원을 먼저 할당하여 실행한 후 다른 스세템 호출에 자원을 할당하는 것이다. 또 다른 방법은 프로세스가 자원을 전혀 갖고 있지 않을 때만 자원을 요청할 수 있도록 허용하는 것이다.

단점

• 자원의 효율성이 너무 낮다
• 기아 상태가 발생할 수 있다.

* 비선점 조건 방지

전제조건은 이미 할당된 자원에 선점권이 없어야 한다.

단점

• 프로세서 레지스터나 기억장치 레지스터와 같이 쉽게 저장되고 이후 다시 복원하기 쉬운 자원에 사용가능하다. 하지만 프린터같은 자원에는 적용하기 어렵다.

* 순환(환형) 대기 조건 방지

모든 자원에 일련의 순서를 부여하고 각 프로세스가 오름차순으로만 자원을 요청할 수 있게한다.

단점

• 순환 대기 조건 방지는 프로세스의 속도를 떨어뜨리고 자원 접근을 불필요하게 거부하기 때문에 비효율적이다.

2. 교착 상태 회피

교착상태 예방은 장치의 효율성과 시스템 처리량을 떨어뜨리는 결과를 초래했다. 교착상태 회피 방법은 덜 엄격한 조건을 요구하여 자원을 좀 더 효율적으로 사용하는 것이 목적이다. 교착상태의 회피 방법은 다음 두 가지로 설명할 수 있다.

1. 프로세스의 시작중단
2. 자원 할당 거부
   
   

* 프로세스의 시작중단

교착 상태 회피 알고리즘은 시스템이 순환 대기 조건이 발생하지 않도록 자원 할당 상태를 검사한다. 자원 할당 상태는 사용 가능한 자원 수, 할당된 자원 수, 프로세스들의 최대 요청 수로 정의한다. 시스템의 상태는 안정상태와 불안정 상태로 나눌 수 있다. 교착 상태는 불안정 상태에서 발생한다. 그러나 불안정 상태가 교착 상태인 것은 아니다. 단지 불안정 상태는 교착상태가 되기 쉬울 뿐이다.

안정 상태의 자원

여분 자원 수가 3개 이므로 P2, P0, P1, P3 순서로 할당을 하면 안정조건을 만족한다.

불안정 상태의 자원

불안정 상태에서는 사용 가능한 자원 한 개를 어떤 프로세스에 할당해도 만족 시킬 수가 없다. 그러나 프로세스 P0에 남은 장치를 할당하고 반납하기 전까지 다른 프로세스가 자원을 요청하지 않으면 교착상태를 회피할 수 있다. 불안정 상태는 교착 상태가 발생할 수 있는 가능성이 있다는 의미이지 반드시 교착상태가 발생한다는 의미는 아니다. 위의 안정 상태 자원에서 P0와 P1이 자원을 한 개 더 요청했다면 P0와 P1의 요청의 허용 여부에 따라 안정 상태 또는 불안정 상태로 변한다.

* 자원 할당 거부(은행가 알고리즘)

자원 할당을 효율적으로 수행하여 교착상태를 회피하는 알고리즘. 은행가 알고리즘은 n은 시스템의 프로세스 수, m을 자원의 수라고 하면  다음 자료구조가 필요하다.

• Available : 각 형태별로 사용 가능한 자원 수(사용 가능량)를 표시하는 길이가 m인 벡터이다. Available[j]=k이면, j번쨰 자원을 k개 사용할 수 있다는 의미이다.
• Max : 각 프로세스 자원의 최대 요청량(최대 요구량)을 표시하는 nxm 행렬이다. Max[i , j]=k이면, 프로세스 Pi는 자원 Rj를 최대 k개까지 요청할 수 있다는 의미이다.
• Allocation : 현재 각 프로세스에 할당되어 있는 각 형태의 자원 수(현재 할당량)를 정의하는 n x m행렬이다. Allocation[i , j] = k이면, 프로세스 Pi는 자원 Rj를 k개 할당받고 있다는 의미이다.
• Need : 각 프로세스에 남아 있는 자원 요청(추가 요구량)을 표시하는 n x m 행렬이다. Need[i , j] = k이면 프로세스 Pi는 자신의 작업을 종료하려고 자원 Rj를 k개 더 필요하다는 의미이다.

여기서 Need[i , j] = Max[i , j] - Allocation[i , j]라는 식이 성립한다. 이 알고리즘을 간단하게 구현하려면, 먼저 다음 제약을 두어야 한다.

• 시간이 흐르면서 벡터의 크기와 값이 변한다
• X와 Y는 길이가 n인 벡터이다.
• X[i]＜＝Y[i]이고 i = 1,2, .......,n 일 때만 X<=Y이다.
• X = (0,3,2,1)이고 Y = (1,7,3,2)이면 X <= Y이다.
• X<=Y이고 X != Y 이면 X < Y 이다.

프로세스 Pi가 자원을 요청하면 다음 동작이 일어난다.(은행가 알고리즘)

• 1단계 : Request(i) <= Need(i) 이면 2단계로 이동하고, 그렇지 않으면 프로세스가 최대 요청치를 초과하기 때문에 오류 상태가 된다.
• 2단계 : Request <= Available 이면 3단계로 이동하고, 그렇지 않으면 자원이 부족하기 떄문에 Pi는 대기한다.
• 3단계 : 시스템은 상태를 다음과 같이 수정하여 요청된 자원을 프로세스 Pi에 해당한다.
  Available = Available - Request(i);
  Allocation = Allocation(i) + Request(i);
  Need(i) = Need(i) = Request(i);

이 시스템은 P2 P4 P1 P3 순서일때 안정상태에 있다. 

은행가 알고리즘의 단점

• 일정하게 남아 있는 자원 수를 파악하기가 매우 어렵다.
• 사용자 수가 항상 변한다.
• 시스템 과부하가 증가한다.
• 프로세스는 자원을 보유한 상태로 끝낼 수 없다.
• 사용자의 최대 필요량을 파악하기가 어렵다.
• 항상 불안정 상태를 방지해야 하므로 자원 이용도가 낮다.

3. 교착 상태 회복

교착 상태에서 회복하려면 다음 알고리즘이 필요하다.

• 시스템 상태를 검사하는 교착 상태 탐지 알고리즘
• 교착 상태에서 회복시키는 알고리즘

교착 상태를 파악하려고 교착 상태 탐지 알고리즘을 언제 수행하야 하는지 결정하기 쉽지 않다. 교착 상태 탐지 알고리즘을 자주 실행하면 시스템의 성능은 떨어지지만, 교착상태에 빠진 프로세스를 빨리 발견하여 자원의 유휴 상태를 방지할 수 있다. 하지만 자주 실행하지 않으면 반대의 상황이 발생한다. 또 탐지와 회복 방법은 필요한 정보를 유지하고 탐지 알고리즘을 실행시키는 비용뿐만 아니라 교착 상태에서 회복하는데 필요한 부담까지 요청한다.

3. 기아 상태

기아상태란 프로세스의 우선순위가 낮아서 원하는 자원을 결코 할당 받지 못하는 상태를 의미한다.