교착 상태 (Deadlock)
교착 상태(Deadlock)란 2개 이상의 작업이 동시에 이루어질 때, 다른 작업이 끝나기만 기다리며 더 이상 진행하지 못하는 상태를 말한다. 교착 상태는 시스템 자원을 사용하거나 잠금을 사용할 때, 발생할 수 있다. 교착 상태가 발생할 경우 강압적으로 문제를 해결해야 한다.
교착 상태 필요조건
교착 상태는 다음의 네 가지 조건을 동시에 만족해야 발생한다. 이 중 단 한 가지라도 충족되지 않으면 교착 상태는 발생하지 않는다.
- 상호 배제(Mutual Exclusion): 한 프로세스가 사용하는 자원은 다른 프로세스와 공유할 수 없는 배타적인 자원이어야 한다.
- 비선점(Non-Preemption): 한 프로세스가 사용 중인 자원은 중간에 다른 프로세스가 빼앗을 수 없는 비선점 자원이어야 한다.
- 점유와 대기(Hold and Wait): 프로세스가 어떤 자원을 할당받은 상태에서 다른 자원을 기다리는 상태여야 한다.
- 원형 대기(Circular Wait): 점유와 대기를 하는 프로세스 간의 관계가 원을 이루어야 한다.
상호 배제와 비선점 조건은 자원에 어떤 특징이 있는가를 나타내고, 점유와 대기 그리고 원형 대기 조건은 프로세스가 어떤 행위를 하는지를 나타낸다.
교착 상태 해결 방법
교착 상태를 해결하는 방법은 "예방", "회피", "검출"이다. 그리고 교착 상태가 발견된 후 자원을 "회복"하는 방법이 있다.
교착 상태 예방 (Deadlock Prevention)
교착 상태를 유발하는 네 조건 중 하나라도 예방하면 교착 상태를 방지할 수 있다. 교착 상태를 예방하는 방법도 네 가지가 있다.
- 상호 배제 예방: 시스템 내의 상호 배타적인 모든 자원을 없애버리는 방법이다. 현실적으로 모든 자원을 공유할 수 없고 상호 배제를 적용하여 보호해야 하는 자원이 분명히 존재하기에 상호 배제를 무력화하기는 어렵다.
- 비선점 예방: 모든 자원을 빼앗을 수 있도록 만드는 방법이다. 그러나 시스템의 모든 자원을 빼앗기는 어려우며, 어떤 기준으로 빼앗을지와 빼앗은 시간을 얼마나 사용할지 등을 결정하는 것은 어렵다. 자원을 빼앗을 수 있도록 만들면 아사 현상이 발생할 가능성이 매우 높다. 이때 아사 현상을 해결하기 위해 에이징을 사용하면 또 교착 상태에 빠질 수 있다. 따라서 비선점 조건을 무력화하기는 어렵다.
- 점유와 대기 예방: 프로세스가 자원을 점유한 상태에서 다른 자원을 기다리지 못하게 하는 방법이다. 자원에 대한 제약을 푸는 것이 아닌 프로세스의 자원 사용 방식을 바꿈으로 교착 상태를 해결한다. 다만, 프로세스가 자신이 사용하는 모든 자원을 자세히 알기 어렵고, 자원의 활용성이 떨어지며, 많은 자원을 사용하는 프로세스가 불리해지고 결국 일괄 작업 방식으로 동작한다는 단점이 있다.
- 원형 대기 예방: 점유와 대기를 하는 프로세스들이 원형을 이루지 못하도록 막는 방법이다. 한 줄로 길게 늘어세우는 것이다. 자원을 한 방향으로만 사용하면 원형 대기를 예방할 수 있다. 그러나 프로세스 작업 진행에 유연성이 떨어지고 자원에 번호를 어떻게 부여할지 결정하는 것이 어렵다는 단점이 있다.
결국, 교착 상태를 예방하는 방법은 실효성이 적어 사용하기가 어렵다.
교착 상태 회피 (Deadlock Avoidance)
교착 상태 회피 방식은 프로세스에 자원을 할당할 때 어느 수준 이상의 자원을 나누어주면 교착 상태가 발생하는지 파악하고 그 수준 이하로 자원을 할당하는 방법이다.교착 상태 회피는 시스템의 운영 방식에 변경을 가하지 않는다. 교착 상태 회피 방식에서는 자원의 총수와 현재 할당된 자원의 수를 기준으로 시스템을 "안정 상태(Safe State)"와 "불안정 상태(Unsafe State)"로 분류한다. 불안정 상태가 커질수록 교착 상태 발생 가능성은 높아진다.(무조건 발생하는 것은 아니다.)
교착 상태 회피를 구현하는 방법 중 은행원 알고리즘(Banker's Algorithm)이 있다. 최악의 경우를 기준으로 삼아 문제 상황을 철저히 피함으로 교착 상태를 막는 방법이다. 은행원 알고리즘에서는 각 프로세스가 자신이 사용할 자원의 최대 수(Max)를 운영체제에 알려준다. 은행원 알고리즘에서 사용되는 변수는 다음과 같다.
- Total(전체 자원): 시스템 내 자원의 수
- Available(가용 자원): 시스템 내 현재 사용 가능한 자원의 수 (전체 자원 - 모든 프로세스의 할당 자원)
- Max(최대 자원): 각 프로세스가 선언한 최대 자원의 수
- Allocation(할당 자원): 각 프로세스에 현재 할당된 자원의 수
- Expect(기대 자원): 각 프로세스가 앞으로 사용할 자원의 수 (최대 자원 - 할당 자원)
은행원 알고리즘을 기준으로 "안정 상태"는 다음과 같이 정의된다.
💡 안정 상태
각 프로세스의 기대 자원과 비교하여 가용 자원이 크거나 같은 경우가 한 번 이상인 경우를 말한다.
교착 상태 회피는 교착 상태가 발생하지 않을 수준까지만 자원을 나누어주는 것이다. 프로세스가 자신이 사용할 모든 자원을 미리 선언해야 하고, 시스템의 전체 자원 수가 고정적이어야 하며, 자원이 낭비된다는 단점으로 인해 실제 시스템에서는 교착 상태 회피를 사용하지 않는다.
교착 상태 검출 (Deadlock Detection)
교착 상태를 검출하는 방법으로는 크게 "타임아웃"을 이용한 방법과 "자원 할당 그래프"를 이용한 방법이 있다.
첫 번째로 타임아웃을 이용한 교착 상태 검출은 일정 시간 동안 작업이 진행되지 않은 프로세스를 교착 상태가 발생한 것으로 간주하여 처리하는 방법이다. 특별한 알고리즘 없이 간단하게 구현할 수 있다는 장점이 있다. 그러나, 엉뚱한 프로세스가 강제 종료될 수 있으며, 모든 시스템에 타임아웃 방법을 적용할 수 없다는 문제가 있다. 대중적인 운영체제에서는 주로 타임아웃 방식을 사용한다. 전문적인 시스템에서는 타임아웃으로 인한 문제를 방지하기 위해 체크포인트와 롤백 개념을 사용한다.
두 번째로 자원 할당 그래프를 이용한 교착 상태 검출은 자원 할당 그래프를 이용하여 시스템 내의 프로세스가 어떤 자원을 사용하는지, 또는 기다리는지를 확인하는 방법이다. 자원 할당 그래프를 이용하여 교착 상태를 검출하는 방법은 프로세스의 작업 방식을 제한하지 않으면서 교착 상태를 정확하게 파악할 수 있다는 장점이 있다. 그러나, 자원 할당 그래프를 유지/갱신/검사하는 추가 작업으로 인한 오버헤드가 발생한다는 단점이 있다.
교착 상태 회복 (Deadlock Recovery)
교착 상태 회복이란 교착 상태가 검출되면 교착 상태를 푸는 후속 작업을 하는 것이다. 교착 상태 회복 단계에서는 교착 상태를 유발한 프로세스를 강제로 종료한다. 프로세스를 강제로 종료하는 방법은 두 가지가 있다.
첫 번째는 "교착 상태를 일으킨 모든 프로세스를 동시에 종료한다."
두 번째는 "교착 상태를 일으킨 프로세스 중 하나를 골라 순서대로 종료한다". 이때, 종료 순서는 다음과 같다.
- 우선순위가 낮은 프로세스를 먼저 종료한다.
- 우선순위가 같으면 작업 시간이 짧은 프로세스를 먼저 종료한다.
- 위의 두 조건이 같으면 자원을 많이 사용하는 프로세스를 먼저 종료한다.
이 단계에서는 강제 종료된 프로세스가 실행되기 전에 시스템을 복구하는 일도 한다. 시스템 복구는 명령어가 실행될 때마다 체크포인트를 만들어 가장 최근 검사 시점으로 돌아가는 방식으로 이루어진다. 다만 이 방법은 작업량이 많아 시스템에 과부하를 주기에 무분별하게 사용해서는 안 된다.
