18. 교착 상태

1. 교착 상태

2개 이상의 프로세스가 다른 프로세스의 작업이 끝나기만 기다리며 작업을 더 이상 진행하지 못하는 상태를 교착 상태라고 한다. 교착 상태는 시스템 자원, 공유 변수(또는 파일), 응용 프로그램 등을 사용할 때 발생할 수 있다.

 

 

시스템 자원

다른 프로세스와 공유할 수 없는 자원을 사용할 때 발생한다. P1은 프린터를 할당받은 후 CD 레코더를 기다리고 P2는 CD 레코더를 할당받은 후 프린터를 기다리면 교착 상태가 발생한다. 두 자원은 동시에 사용할 수 없기 때문이다.

 

 

공유 변수

프로세스 P1은 공유 변수 lock1을 true로 만든 다음 lock2가 false가 될 때까지 기다리고, 프로세스 P2는 lock2를 true로 만든 다음 lock1이 false가 될 때까지 기다리면 교착 상태가 발생한다. 둘 다 true인 상태에서 무한 대기만 이루어질 뿐이다.

 

 

응용 프로그램

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

 

 

 

2. 교착 상태 필요조건

교착 상태가 발생하기 위해선 4가지 조건이 필요하다. 이 중 단 하나라도 충족하지 않으면 교착상태는 발생하지 않는다.

 

 

상호 배제

배타적인 자원 즉, 다른 프로세스와 공유할 수 없는 자원이어야 한다.

 

 

비선점

한 프로세스가 사용 중이라면 다른 프로세스는 사용이 끝날 때가지 기다려야 하는 비선점 자원이어야 한다.

 

 

점유와 대기

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

 

 

원형 대기

점유와 대기를 하는 프로세스들의 방향이 원을 이뤄야 한다.

 

 

 

3. 교착 상태 해결방법

교착 상태를 해결하는 방법은 크게 4가지로 나눌 수 있다. 예방, 회피, 검출, 회복이다.

 

 

예방

교착 상태의 필요조건 4가지 중 하나라도 발생하지 않도록 막는 방법이다.

 

(1) 상호 배제 예방

시스템 내의 모든 자원을 공유 가능하게 만드는 방법이다. 하지만 공유해선 안 되거나 공유할 수 없는 자원들도 있기 때문에 현실적으로 예방하기 어렵다.

 

(2) 비선점 예방

모든 자원을 사용 중에도 빼앗을 수 있도록 만드는 방법이다. 하지만 임계구역처럼 비선점으로 운영되어야 하는 곳도 있고 자원을 빼앗는 기준, 시간 등을 설정하는 것도 어려워 현실적으로 예방하기 어렵다.

 

(3) 점유와 대기 예방

프로세스가 자원을 점유한 상태에서 다른 자원을 기다리는 것을 막는 방법이다. 필요한 자원을 모두 사용하거나 어떤 자원도 사용하지 않거나 프로세스는 둘 중의 하나의 상태를 가지게 된다. 하지만 다음과 같은 단점이 있다.

 

• 프로세스가 자신이 필요한 모든 자원을 사전에 알기 어렵다. 중간에 자원이 추가되는 경우도 생긴다.
• 당장 사용하지 않을 자원까지도 선점하기 때문에 비효율적이다. 그 자원이 필요한 다른 프로세스는 계속 대기하게 되기 때문이다.
• 자원을 많이 사용하는 프로세스일수록 불리하다. 아사 현상이 발생할 수 있다.
• 결국 일괄 작업 방식으로 동작하게 되기 때문에 비효율적이다.

 

(4) 원형 대기 예방

자원에 번호를 부여해 자원을 한 방향으로만 사용하도록 한다. 작은 번호의 자원을 가진 상태에서 큰 번호의 자원을 요구하는 것은 가능하지만, 반대의 경우에는 운영체제가 거부한다.

 

하지만 자원의 번호를 어떻게 부여할 지도 애매하고 큰 번호의 자원을 가진 상태에서 작은 번호의 자원을 요청할 수 없는 것 또한 비효율적이라는 단점이 있다.

 

 

회피

교착 상태 회피는 프로세스에 할당하는 자원의 총량을 제한함으로써 교착 상태를 방지하는 방법이다. 자원을 많이 부여할수록 시스템은 불안정 상태에 가까워지기 때문에 적절하게 자원의 수를 조절해 안정 상태에 머무를 수 있도록 한다.

 

 

은행원 알고리즘

대표적인 교착 상태 회피 알고리즘이다. 은행이 대출을 해줄 때, 대출 금액이 대출 가능한 범위 내이면 허용되지만 그렇지 않으면 거부되는 것과 유사하기 때문에 붙여진 이름이다.

 

각 프로세스는 운영체제에 자신이 사용할 자원의 최대 수를 알려준다. 이를 바탕으로 운영체제는 자원을 할당할 때 시스템의 안정성을 판단한다. 은행원 알고리즘의 변수 목록은 아래와 같다.

 

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

 

은행원 알고리즘에서 정의하는 안정 상태란 다음과 같다.

 

안정 상태

어떤 프로세스의 기대 자원보다 가용 자원이 크거나 같은 상태

 

어떤 프로세스에 자원을 할당했을 때 안정 상태가 깨진다면 자원을 할당하지 않는다. 그 순간 가용 자원을 통해 어떤 프로세스의 작업도 끝내지 못하기 때문이다. 하지만 다음과 같은 단점 때문에 이 방식도 잘 사용하지 않는다.

 

• 프로세스가 자신이 사용할 모든 자원을 미리 선언하기 어렵다.
• 시스템의 전체 자원 수는 유동적인 경우가 많다.
• 가용 자원이 있음에도 할당하지 않는 것은 자원을 낭비하는 것이다.

 

 

검출

교착 상태 예방은 실제로 구현하기 어렵고, 교착 상태 회피는 구현할 수는 있지만 자원 낭비의 단점이 있다. 교착 상태 해결 방법 중 가장 현실적인 것이 바로 교착 상태 검출이다.

 

교착 상태 검출은 운영체제가 프로세스의 작업을 관찰하면서 교착 상태 발생 여부를 계속 주시하는 방식이다. 만약 교착 상태가 발견되면 이를 해결하기 위한 회복 단계에 돌입한다. 교착 상태 검출은 타임아웃을 이용하는 방법과 자원 할당 그래프를 이용하는 방법이 있다.

 

(1) 타임아웃을 이용한 교착 상태 검출

일정 시간동안 작업이 진행되지 않은 프로세스를 교착 상태가 발생한 것으로 간주하여 처리한다. 교착 상태가 자주 발생하지 않을 것이라는 가정하에 사용하는 것으로, 특별한 알고리즘 없이 쉽게 구현 가능하다.

 

하지만 작업이 진행되지 않는다고 해서 무조건 교착 상태가 발생한 것은 아니기 때문에 엉뚱한 프로세스가 강제 종료될 수 있고, 운영체제같이 모든 프로세스를 감시할 수 있는 형태의 시스템이 아니면 적용하기 어렵다는 단점이 있다.

 

이런 단점에도 불구하고 대부분의 데이터베이스와 운영체제에서 많이 선호하는 방법이다. 자주 발생하지 않는 교착 상태를 잡기 위해 너무 복잡한 방법을 사용하는 것을 선호하지 않기 때문이다.

 

데이터베이스는 운영체제보다 복잡하게 처리해주어야 한다. 데이터의 일관성을 유지해야 하기 때문이다. 이를 위해 중요한 데이터에 잠금을 요청하면 체크포인트를 설정하고 타임아웃이 걸려 프로세스를 중단하거나 잠금을 포기해야할 경우 저장했던 체크포인트로 데이터를 롤백한다.

 

(2) 자원 할당 그래프를 이용한 교착 상태 검출

프로세스의 자원 할당 상황을 볼 수 있는 그래프를 이용하는 방법이다. 단일 자원의 경우 그래프 내에 사이클이 존재하면 교착 상태가 발생한 것으로 간주한다. 다중 자원의 경우에는 사이클이 있다고 하더라도 교착 상태가 아닐 수 있기 때문에 다른 방법이 필요하다.

 

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

 

 

회복

교착 상태를 검출하면 교착 상태를 푸는 후속 작업이 이루어지는데 이를 교착 상태 회복이라고 한다. 교착 상태를 일으킨 모든 프로세스를 동시에 종료하거나 순차적으로 하나씩 종료하는 방법이 있다.

 

강제 종료된 프로세스가 실행되기 전에 시스템을 복구하는 일도 해야 한다. 시스템 복구는 명령어가 실행될 때마다 체크포인트를 만들어 가장 최근의 검사 시점으로 돌아가는 식으로 이루어진다.