운영체제 - 6

 

1. 교착 상태

1.1 교착 상태

임계구역이 존재하면 프로세스 간 상호 배제가 보장되지만, 작업이 더 이상 진행되지 않는 교착 상태에 빠지는 경우가 있다. 이처럼 2개 이상의 프로세스가 다른 프로세스의 작업이 끝나기만 기다리며 작업을 더 이상 진행하지 못하는 상태를 교착 상태(Dead Lock)라고 한다.

교착 상태는 아사 현상과는 전혀 다르다. 아사 현상은 운영체제가 잘못된 정책을 사용하여 프로세스의 작업이 크게 지연되는 것을 의미한다. 반면 교착 상태는 여러 프로세스가 진행되는 과정에서 자연적으로 일어난다. 컴퓨터 시스템에서 교착 상태는 시스템 자원, 공유 변수(혹은 파일), 응용 프로그램 등을 함께 사용할 때 발생할 수 있다.

 

1.2 자원 할당 그래프

자원 할당 그래프(Resource Allocation Graph)는 각각의 프로세스가 어떤 자원을 사용 중이고 어떤 자원을 기다리고 있는지를 방향성이 있는 그래프(Directional Graph)로 표현한 것이다. 다중 자원(Multiple Resource)란 여러 프로세스가동시에 사용할 수 있는 자원을 일컫는다.

 

2. 교착 상태 필요 조건

교착 상태는 여러 가지 조건이 만족될 때 발생한다.

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

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

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

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

교착 상태는 상호 배제, 비선점, 점유와 대기, 원형 대기를 모두 충족해야만 발생한다. 상호배제와 비선점 조건은 임계구역과 관련이 있다. 임계구역의 자원을 사용하는 프로세스들이 점유와 대기, 원형 대기 상황에 처하면 교착 상태가 발생한다.

 

3. 교착 상태 해결 방법

3.1 교착 상태 예방

교착 상태를 일으키는 네 가지 조건이 발생하지 않도록 무력화하는 방식이다. 그러나 이 방법은 실효성이 적어 사용하지 않는다. 이는 프로세스가 사용하는 자원을 파악하는게 용이하지 않다는 점 때문이며, 운용 측면에서도 자원의 활용성이 떨어진다는 단점이 있다.

 

3.2 교착 상태 회피

자원 할당량을 통제하여 교착 상태를 해결하는 방법이다. 그러나 이 방법 역시 실효성이 적다. 교착 상태 회피는 자원의 총수와 현재 할당된 자원의 수를 기준으로 시스템을 안정 상태(safe state)와 불안정 상태(unsafe state)로 나누고 시스템이 안정 상태를 유지하도록 자원을 할당한다. 다만 불안정 상태에서 항상 교착 상태가 발생하는 것은 아니고, 교착 상태는 불안정 상태의 일부분이다. 이를 구현하는 방법 중 하나는 '은행원 알고리즘'이다. 다만 프로세스가 사용하는 자원을 파악하는게 용이하지 않다는 점과, 시스템 자원의 수가 실제로는 유동적이라는 점이 문제가 된다.

 

3.3 교착 상태 검출과 회복

프로세스의 상태나 자원 할당 그래프를 모니터링하면서 교착 상태가 발생하는지 살펴보는 방식이다. 교착 상태가 검출되면 이를 회복시킨다.

A. 타임아웃을 이용한 교착 상태 검출

타임아웃을 이용한 교착 상태 검출은 일정 시간 동안 작업이 진행되지 않은 프로세스를 교착 상태가 발생한 것으로 간주하여 처리하는 방식이다. 이 방식은 단순하여 대부분의 데이터베이스와 운영체제에서 많이 선호된다. 윈도우에서 '프로그램 응답이 없어 종료합니다'라는 것이 이에 해당된다. 

다만 엉뚱한 프로세스가 강제 종료될 수 있는 점이 단점이다. 데이터베이스의 교착 상태 처리는 운영체제보다 까다로운데, 이는 데이터의 일관성 문제와 관련이 있다. 타임아웃으로 데이터의 일관성이 깨지는 문제를 해결하기 위하여 데이터베이스에는 체크포인트(check point)와 롤백(roll back)을 사용한다. 즉, 작업을 하다 문제가 생기면 저장된 상태로 돌아오는 것이다.

B. 자원 할당 그래프를 이용한 교착 상태 검출

말 그대로 교착 상태를 검출하기 위해 자원 할당 그래프를 활용한다. 단일 자원을 사용하는 경우에는 자원 할당 그래프가 사이클을 이루는지 확인하면 되지만, 다중 자원을 사용하는 경우에는 이보다 복잡한 방식이 필요하다. 다만 이 방식은 자원 할당 그래프를 유지, 갱신, 검사 등의 오버헤드가 발생한다는 점이 단점이다.

다중 자원이 포함된 자원 할당 그래프에서는 대기 그래프와 그래프 감소 방법을 이용하여 사이클을 찾는다. 대기 그래프(wait for graph)는 자원 할당 그래프에서 프로세스 간에 기다리는 관계만 나타낸 것이다. 그래프 감소(graph reduction)은 그래프에서 작업이 끝날 가능성이 있는 프로세스와 관련된 그래프의 화살표를 연속적으로 지워나가는 작업을 의미한다. 다중 자원이 있는 대기 그래프에서 그래프 감소를 완료한 후에도 사이클이 남아 있다면 교착 상태가 발생한 것이다.