1. 교착 상태

2개 이상의 프로세스가 다른 프로세스의 작업이 끝나기만 기다리며 작업을 진행하지 못하는 상태를 교착 상태 라고 한다. 교착 상태는 아사 현상과 비슷해 보이지만 차이가 있다. 아사 현상은 운여에제가 잘못된 정책을 사용하여 특정 프로세스의 작업이 지연되는 문제이고, 교착 상태는 여러 프로세스가 작업을 진행하다 보니 자연적으로 일어나는 문제이다.

1-1) 교착 상태의 발생

교착 상태는 시스템 자원 , 공유 변수, 응용 프로그램 등을 사용할 때 발생할 수 있다.

• 시스템 자원
  교착 상태는 다른 프로세스와 공유할 수 없는 자원을 사용할 때 발생한다. 아래 그림처럼 P1은 프린터를 할당받은 후 CD 레코더ㅏ를 기다리고 프로세스 P2는 CD 레코더를 할당받은 후 프린터를 기다린다.
  

• 공유 변수
  교착 상태는 공유 변수를 사용할 때도 발생한다. 프로세스 P1이 lock1을 true로 만든 다음에 P2가 lock2를 true로 만들었다고 가정해보자. 이후 P1과 P2는 둘다 무한 반복을 하게 되며 임계구역에 진입할 수 없게된다. 이처럼 한 변수를 할당받은 상태에서 다른 변수를 기다리면 교착 상태가 발생한다.
  

• 응용 프로그램
  데이터베이스 같은 응용 프로그램에서도 교착 상태가 발생한다. 데이터베이스에서는 데이터의 일관성을 유지하기 위해 잠금을 사용하는데 이때 교착 상태가 발생할 수 있다.

1-2) 자원 할당 그래프

자원 할당 그래프는 프로세스가 어떤 자원을 사용 중이고 어떤 자원을 기다리고 있는지를 방향성 있는 그래프로 표현한 것이다.

자원 할당 그래프에서는 프로세스는 원으로, 자원은 사각형으로 표현한다.

자원이 2개 이상의 프로세스를 동시에 허용하는 경우가 있다. 여러 프로세스가 하나의 자원을 동시에 사용하면 이를 다중 자원이라고 부른다. 다중 자원은 수용할 수 있는 프로세스 수를 사각형 안에 작은 동그라미로 표현한다.

2. 교착 상태의 필요조건

교착 상태는 여러 가지 조건에 의해 발생한다. 상호 배제 , 비선점, 점유와 대기, 원형 대기를 모두 충족해야 발생한다. 이 중 하나라도 충족하지 않으면 교착상태가 발생하지 않는다.

• 상호 배제
  한 프로세스가 사용하는 자원은 다른 프로세스와 공유할 수 없는 배타적인 자원이어야 한다.

• 비선점
  한 프로세스가 사용 중인 자원은 중간에 다른 프로세스가 빼앗을 수 없는 비선점 자원이어야 한다.

• 점유와 대기
  프로세스가 어떤 자원을 할당받은 상태에서 다른 자원을 기다리는 상태여야 한다.

• 원형 대기
  점유와 대기를 하는 프로세스 간의 관계가 원을 이루어야 한다.

교착 상태의 필요조건중 상호 배제와 비선점 조건은 자원이 갖는 특징을 나타낸다. 사용하는 자원을 동시에 공유할 수도 없고 빼앗을 수도 없다면 자원을 가진 프로세스가 자원을 내놓을 때까지 무작정 기다리는 교착 상태가 발생한다. 점유와 대기, 원형 대기 조건은 프로세스의 행위를 나타낸다. 프로세스가 자원을 점유 및 대기하고 있는 상태에서 다른 프로세스를 방해하는 방향이 원을 이루면 서로 양보하지 않기 때문에 교착 상태가 발생한다.

2-1) 식사하는 철학자 문제와 교착 상태 필요조건

식사하는 철학자 문제는 철학자들이 둥그런 식탁에 앉아 식사를 하는데, 왼쪽에 있는 포크를 잡은 뒤 오른쪽에 있는 포크를 잡아야하만 식사가 가능한 상황을 나타낸 문제이다. 철학자들은 음식을 먹기 위해 왼쪽 포크를 잡은뒤 오른쪽 포크를 잡으려고 할 것이다. 하지만 오른쪽에는 이미 왼손에 포크를 들고 있는 또 다른 철학자가 있다.

상호 배제와 비선점 조건은 임계구역과 관련이 있다. 임계구역을 보호하기 위해 잠금 장치를 사용하면 상호 배제와 비선점 조건이 보장되기 때문에 교착 상태가 발생할 수 있다.

• 상호 배제
  포크는 한 사람이 사용하면 다른 사람이 사용할 수 없는 배타적인 자원이다.

• 비선점
  배타적인 자원을 사용한다고 하더라도 자원을 빼앗을 수 있다면 교착 상태가 발생하지 않을 것이다. 자원을 빼앗을 수 있다는 것은 시간 간격을 두고 그 자원을 공유할 수 있다는 의미이므로 상호 배제가 성립되지 않는다.

• 점유와 대기
  한 철학자가 두 자원을 다 점유하거나, 반대로 두 자원을 다 기다리는 상태라면 교착 상태가 발생하지 않는다. 여기서 두 자원을 점유하거나 기다린다는 말은 작업을 진행하는 쪽과 기다리는 쪽의 선후 관계를 만든다는 의미이다.

• 원형 대기
  원을 이루어 식사를 한다는 것은 선후 관계를 결정할 수 없어 문제가 계속 맴돈다는 의미이다. 점유와 대기를 하는 프로세스들이 원을 이루면서 서로 진행을 방해하므로 교착 상태가 발생한다.

3. 교착 상태의 해결 방법

교착 상태를 해결하는 방법은 예방 , 회피 , 검출이며 추가적으로 교착 상태가 발견된 후에 자원을 회복하는 방법도 있다.

해결 방법	특징
교착 상태 예방	교착 상태를 유발하는 네 가지 조건을 무력화
교착 상태 회피	교착 상태가 발생하지 않는 수준으로 자원을 할당
교착 상태 검출	자원 할당 그래프를 사용하여 교착 상태를 발견
교착 상태 회복	교착 상태를 검출한 후 해결

• 교착 상태 예방
  교착 상태는 상호 배제, 비선점, 점유와 대기, 원형 대기라는 네 가지 조건을 동시에 충족해야 발생하기 때문에 이 중 하나라도 막는다면 교착 상태가 발생하지 않는다.

• 교착 상태 회피
  자원 할당량을 조절하여 교착 상태를 해결하는 방식이다. 즉 자원을 할당하다가 교착 상태를 유발할 가능성이 있다고 판단되면 자원 할당을 중단하고 지켜보는 것이다.

• 교착 상태 검출
  교착 상태 검출은 어떤 제약을 가하지 않고 자원 할당 그래프를 모니터링하면서 교착 상태가 발생하는지 살펴보는 방식이다. 만약 교착 상태가 발생하면 교착 상태 회복 단계가 진행된다. 교착 상태를 검출한 후 이를 회복시키는 것은 결론적으로 교착 상태를 해결하는 현실적인 접근 방법이다.

3-2) 교착 상태 예방

상호 배제 예방

시스템 내에 있는 상호 배타적인 모든 자원을 없애버리는 방법이다. 시스템 내의 모든 자원을 공유할 수 있다면 교착 상태가 발생하지 않는다. 하지만 현실적으로 모든 자원을 공유할 수 없으며 상호 배제를 적용하여 보호해야 하는 자원이 있다. 이처럼 임계 구역이 보호받지 못하면 작업의 결과가 달라지는 것을 알 수 있다. (프린터를 공유하면 여러 데이터가 엉켜서 출력물이 꼬인다.)

비선점 예방

모든 자원을 뺏어올 수 있도록 하는 방법이다. 임계구역을 보호하기 위해 잠금을 사용하면 자원을 뺏어올 수 없을 뿐 아니라 상호 배제도 보장할 수 없다. 설령 어떤 자원을 빼앗을 수 있도록 할지라도 어떤 기준으로 빼앗을지, 빼앗은 시간 중 얼마나 사용할지 결정하기 힘들다. 게다가 이러한 방법은 아사 현상을 일으킨다. 우선순위가 낮은 프로세스는 자원을 받지 못하기 때문이다.

점유와 대기 예방

프로세스가 자원을 점유한 상태에서 다른 자원을 기다리지 못하게 하는 방법이다. 이를 위해 프로세스는 시작 초기에 자신이 사용하려는 모든 자원을 한번에 점유하거나 전부 반납해야 한다. 식사하는 철학자 문제에서 왼쪽 포크를 든 후, 오른쪽 포크를 잡는 것이 아닌 양손으로 동시에 포크를 잡도록 하는 것과 같다. 이렇게 하면 동작이 빠른 철학자만이 식사를 할 수 있게 된다.
하지만 점유와 대기 예방은 다음과 같은 단점이 있다.

• 프로세스가 자신이 사용하는 모든 자원을 자세히 알기 어렵다 (추가 자원을 확보하기 힘들다)
• 프로세스가 앞으로 사용할 자원까지 미리 선점하기 때문에 활용성이 떨어진다.
• 자원을 많이 사용하는 프로세스가 불리하다.
• 결국 일괄 작업 방식으로 동작한다.

원형 대기 예방

점유와 대기를 하는 프로세스들이 원형을 이루지 못하도록 막는 방법이다. 자원을 한 방향으로만 사용하도록 설정함으로써 원형 대기를 예방할 수 있다. 즉 모든 자원에 숫자를 부여하고 숫자가 큰 방향으로만 자원을 할당하는 것이다. 즉, 숫자가 작은 자원을 확보한 후 숫자가 큰 자원을 획득할 수는 있지만 숫자가 큰 자원을 확보한 후 숫자가 작은 자원을 획득하지 못하게 하는 것이다.

원형 대기 예방은 다음과 같은 단점이 있다.

• 프로세스 작업 진행에 유연성이 떨어진다. (ex 프린터를 사용한 후 마우스 사용 거부)
• 자원의 번호를 어떻게 부여할지 판단하기 힘들다.

3-2) 교착 상태 회피

교착 상태 회피는 프로세스에 자원을 할당할 때 어느 수준 이상의 자원을 나누어주면 교착 상태가 발생하는지 파악하여 그 ㅅ준 이하로 자원을 나누어주는 방법이다.

시스템에 총 20개의 자원이 있다고 할 때 1개의 자원을 할당하면 교착 상태가 발생하지 않는다(점유와 대기 만족X) 그러나 20개의 자원을 모두 할당하면 교착 상태가 발생할 확률이 매우 높아진다. 교착 상태 회피는 자원의 총 수와 현재 할당된 자원의 수를 기준으로 시스템을 안정 상태와 불안정 상태로 나누고 시스템이 안정 상태를 유지하도록 자원을 할당한다.

아래 그림처럼 할당된 자원이 적으면 안정 상태가 크고, 할당된 자원이 늘어날수록 불안정 상태가 커진다. 또한 불안정 상태에서도 반드시 교착 상태가 발생하는 것이 아니다.

[a] 은행원 알고리즘

교착 상태 회피를 구현하는 방법은 여러가지인데 그 중 하나는 다익스트라가 제안한 은행원 알고리즘이다. 은행이 대출을 해주는 방식, 즉 대출 금액이 대출 가능한 범위 내이면 허용되지만 그렇지 않으면 거부되는 것과 유사하기 때문에 이렇게 불리게 되었다.

은행원 알고리즘에서 사용하는 변수들은 다음과 같다.

변수	설명
전체 자원(Total)	시스템 내 전체 자원의 수
가용 자원(Availble)	시스템 내 현재 사용할 수 있는 자원의 수
최대 자원(Max)	각 프로세스가 선언한 최대 자원의 수
할당 자원(Allocation)	각 프로세스에 현재 할당된 자원의 수
기대 자원(Expect)	각 프로세스가 앞으로 사용할 자원의 수

• 각 프로세스의 기대 자원과 비교하여 가용 자원이 하나라도 크거나 같으면 자원을 할당한다. 가용 자원이 기대 자원보다 크다는 것은 그 자원을 사용하여 작업을 끝낼 수 있는 프로세스가 있다는 의미이므로 안정 상태이다.

• 가용 자원이 어떤 기대 자원보다 크지 않으면 할당하지 않는다. 가용 자원을 사용하여 작업을 마칠 수 있는 프로세스가 없다는 의미이므로 불안정 상태이다.

안정 상태
각 프로세스의 기대 자원과 비교하여 가용 자원이 크거나 같은 경우가 한 번 이상인 경우

아래 그림은 안정 상태의 예이다.
1. 시스템에 있는 전체 자원의 수는 14개이고, 각 프로세스가 필요로 하는 최대 자읜의 수는 P1이 5개, P2가 6개, P3가 10개이다.
2. 각 프로세스에 현재 할당된 자원은 P1이 2개 , P2가 4개, P3가 6개로 총 12개이다. 따라서 시스템 전체에서 사용할 수 있는 가용 자원은 2개이다.
3. 또한 기대 자원은 프로세스가 선언한 최대 자원에서 현재 할당된 자원의 수를 뺀 값이므로 P1은 3개 P2는 2개 P3은 4개이다.

위의 그림이 안정 상태인 이유는 현재 가용 자원이 2개인데 P2가 필요로 하는 자원이 2개이기 때문이다. 가용 자원 2개를 활용하여 작업을 마친 후 자원을 6개 반환하고 이를 P1혹은 P3에 할당하면 전체 작업을 마무리 할 수 있다.

[b] 교착 상태 회피의 문제점

교착 상태 회피의 원칙은 교착 상태가 발생하지 않을 수준까지만 자원을 나눠주는 것이다. 교착 상태 회피에는 다음과 같은 문제점들이 있다.

• 프로세스가 자신이 사용할 모든 자원을 미리 선언해야 한다.
• 시스템의 전체 자원 수가 고정적이어야 한다.
• 모든 불안정 상태가 교착 상태가 되는 것은 아님에도 자원을 할당하지 않아서 자원이 낭비된다.

3-3) 교착 상태 검출

교착 상태 예방은 구현하기 힘들고, 교착 상태 회피는 자원을 낭비하는 문제가 있다. 따라서 교착 상태의 해결 방법 중 가장 현ㅅㄹ적인 것은 교착 상태를 검출하는 것이다. 그리고 교착 상태가 검출되면 교착 상태 회복 단계를 거친다.

교착 상태 검출은 타임아웃을 이용하는 방법과 자원 할당 그래프를 이용하는 방법이 있다.

[a] 타임아웃을 이용한 교착 상태 검출

타임아웃을 이용한 교착 상태 검출은 일정 시간 동안 작업이 진행되지 않은 프로세스를 교착 상태가 발생한 것으로 간주하여 처리하는 방법이다. 특별한 알고리즘 없이 구현할 수 있다는 장점이 있지만 다음과 같은 단점들이 있다.

• 엉뚱한 프로세스가 강제 종료될 수 있다.
• 모든 시스템에 적용할 수 없다. (분산 데이터베이스 등)

자원 할당 그래프를 이용하여 교착 상태를 찾는 방법은 구현이 힘들어 타임아웃을 이용한 교착 상태의 검출을 많이 선호한다.

데이터베이스의 교착 상태 처리는 운영체제보다 복잡하다. 데이터베이스에서는 특히 데이터의 일관성이 깨지면 안 된다. 데이터를 조작하는 경우 잠금을 얻은 후 작업을 시작하는데, 잠금을 얻어 작업을 하던 중 타임아웃으로 프로세스가 종료되면 데이터에 문제가 발생할 가능성이 있다.

타임아웃으로 데이터의 일관성이 깨지는 문제를 해결하기 위해 데이터베이스에서는 체크포인트와 롤백을 사용한다. 체크포인트는 작업을 하다가 문제가 발생하면 저장된 상태로 돌아오기 위한 표시이다. 롤백은 작업을 하다가 문제가 발생하여 과거의 체크포인트로 되돌아가는 것을 말한다.

[b] 자원 할당 그래프를 이용한 교착 상태 검출

교착 상태를 거물하는 또 다른 방법은 자원 할당 그래프를 이용하는 것이다. 자원 할당 그래프를 보면 시스템 내의 프로세스가 어떤 자원을 사용하고 있는지 혹은 기다리고 있는지 알 수 있다.

위의 그림에서 알 수 있듯 사이클이 발생하면 교착 상태가 검출된 것으로 판단한다. 오른쪽 그림에서는 P1->P2->P4->P1로 이어지는 사이클이 존재하기 때문에 운영체제는 교착 상태가 발생한 것으로 판단한다.

그러나 다중 자원을 사용하는 경우에는 자원 할당 그래프에 사이클이 있다고 해서 모두 교착상태라고 판단할 수 없다.

자원 할당 그래프를 이용하여 교착 상태를 검출하는 방법은 프로세스의 작업 방식을 제한하지 않으면서 교착 상태를 정확하게 파악할 수 있다는 것이 장점이다. 그러나 그래프를 유지하고 갱신하고 사이클을 검사하는 작업으로 인해 오버헤드가 발생한다는 단점이 있다.

3-4) 교착 상태 회복

• 교착 상태를 일으킨 모든 프로세스를 동시에 종료
  교착 상태를 일으킨 모든 프로세스를 종료하는 방법. 이 방법은 종료된 프로세스들이 동시에 작업을 시작하면 다시 교착 상태를 일으킬 가능성이 크다. 그러므로 모든 프로세스를 강제로 종료한 후 다시 실행할 때는 순차적으로 실행해야 한다.

• 교차 상태를 일으킨 프로세스 중 하나를 골라 순서대로 종료
  교착 상태를 일으킨 프로세스를 종료해가며 다른 프로세스의 상태를 파악하는 방법이다. 우선순위가 낮은 프로세스, 작업 시간이 짧은 프로세스 , 자원을 많이 사용하는 프로세스 순으로 종료한다. 또한 교착 상태 회복에는 강제 종료된 프로세스가 실행되기 전에 시스템을 복구하는 일도 해야한다.

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

교착 상태 검출 시 단일 자원을 하나의 프로세스만 사용할 수 있다고 가정했다. 이 경우 자원 할당 그래프에 사이클이 존재하면 교착 상태가 발생한 것으로 본다. 그러나 다중 자원, 즉 하나의 자원을 여러개의 프로세스가 동시에 사용할 수 있는 경우 어떤 식으로 검출할 수 있는지 알아보자.

4-1) 다중 자원과 사이클

아래 그림을 보면 R1은 두 프로세스가 동시에 사용할 수 있는 다중 자원이다. P1은 R1을 사용하면서 R2를 기다리고 P2는 자원 R1과 R2를 사용하고 있다. R1의 자원 수가 2개이므로 P2가 자원을 사용한 후 반환하면 P1이 자원 R2를 사용하여 작업을 마칠 수 있다. 따라서 교착 상태가 발생하지 않는다.

이처럼 다중 자원이 포함된 자원 할당 그래프에서는 대기 그래프와 그래프 감소 방법을 이용하여 사이클을 찾는다.

4-2) 대기 그래프와 그래프 감소

대기 그래프는 자원 할당 그래프에서 프로세스와 프로세스 간에 기다리는 관계만 나타낸 그래프이다. 그리고 그래프 감소는 대기 그래프에서 작업이 끝날 가능성이 있는 프로세스의 화살표와 관련 프로세스의 화살표를 연속적으로 지워가는 작업을 말한다. 다중 자원이 있는 대기 그래프에서 그래프 감소를 완료한 후에도 사이클이 남아 있다면 교착 상태가 발생한 것으로 판단한다.

1. 작업이 끝날 수 있는 프로세스, 즉 기다리는 자원이 없는 프로세스 P2에 대해 P1에서 P2로 가는 화살표를 지운다.
2. P1이 작업을 종료할 수 있으므로 P4에서 P1으로 가는 화살표를 지운다.
3. P4가 작업을 종료할 수 있으므로 P3에서 P4로 가는 화살표를 지운다.
4. P3이 작업을 종료할 수 있으므로 P1에서 P3로 가는 화살표를 지운다.

그래프 감소 결과 사이클이 남아 있지 않으므로 교착 상태가 발생하지 않는다.

그래프 감소를 해도 여전히 사이클이 남아 있어 교착 상태가 발생한다.
결론적으로 단일 자원만 있는 자원 할당 그래프에서는 사이클만으로 교착 상태 검출이 가능하지만, 다중 자원을 사용할 때는 그래프 감소를 한 후 사이클이 남아 있는지 확인하여 교착 상태를 검출한다.