※ 이 내용은 ‘쉽게 배우는 운영체제’ 책 내용을 바탕으로 작성되었습니다.
교착 상태
교착 상태(dead lock)은 2개 이상의 프로세스가 작업이 끝나기만 기다리며 작업을 더 이상 진행할 수 없는 상태를 말합니다.
교착 상태의 발생
컴퓨터 시스템에서 교착 상태는 다양한 상황에서 발생합니다.
- 시스템 자원어떤 프로세스가 임계구역으로 보호되는 프린터, 스캐너 등 동시에 사용할 수 없는 자원을 할당받은 후 양보하지 않는 경우 발생할 수 있습니다. 이러한 자원을 필요로 하는 다른 자원은 양보하기 전에는 해당 자원을 사용할 수 없어 작업을 더 이상 진행할 수 없게 됩니다.
- 공유 변수임계구역 문제를 해결하기 위한 잠금 공유 변수를 사용할 때 교착 상태가 발생할 수 있습니다.
- 응용 프로그램데이터베이스같은 응용 프로그램에서도 교착 상태가 발생합니다. 여러 프로세스가 데이터베이스에 저장된 데이터를 사용하려면 일관성 유지가 필수입니다. 데이터베이스는 일관성 유지를 위해 잠금을 사용하는데 이때 교착 상태가 발생할 수 있습니다.
자원 할당 그래프
자원 할당 그래프(resource allocation graph)는 프로세스가 어떤 자원을 사용 중이고 어떤 자원을 기다리고 있는지 방향성이 있는 그래프로 표현한 것입니다. 이를 사용하면 어떤 프로세스가 자원이 할당되어 있는지 혹은 어떤 프로세스가 자원을 기다리고 있는지 쉽게 파악할 수 있습니다.
- 프로세스는 원으로, 자원은 사각형으로 표현합니다.
- 자원을 사용하고 있는 경우 자원으로부터 프로세스로 향하는 화살표로 표시합니다.(좌)
- 프로세스가 자원을 기다리는 경우는 프로세스로부터 자원으로 향하는 화살표로 표시합니다.(우)
자원이 2개 이상의 프로세스를 동시에 허용하는 다중 자원이 있습니다. 다중 자원은 수용할 수 있는 프로세스 수를 사각형 안에 작은 동그라미로 표현합니다. 사각형 안에 작은 동그라미가 2개 있으면 그 자원을 2개의 프로세스가 동시에 사용할 수 있다는 의미입니다.
교착 상태를 설명하는 대표적인 예시로 식사하는 철학자 문제가 있습니다. 철학자 4명이 원형 식탁에 둘러앉아 식사를 하는데, 왼쪽 포크를 잡은 뒤 오른쪽 포크도 잡아야 식사가 가능하다는 조건이 있습니다.
철학자들은 음식을 먹기 위해 왼쪽의 포크를 잡은 뒤 오른쪽 포크를 잡으려고 하지만 이미 4명의 철학자들은 자신의 왼쪽 포크를 집었으므로 음식을 먹을 수 없습니다. 결국 모든 철학자들은 굶어 죽게 됩니다. 이를 자원 할당 그래프로 나타내면 다음과 같습니다.
P1은 R1의 자원을 할당받아 사용하고 R4의 자원을 기다리고 있습니다. P4는 R4의 자원을 할당받아 사용하고 있고 R3의 자원을 기다리고 있습니다. 모든 프로세스와 자원이 원형 구조로 연결되어 있습니다. 따라서 한 프로세스가 자원을 놓지 않으면 모든 프로세스는 다른 작업을 수행하지 못하게 됩니다. 이 문제에서 교착 상태가 발생하는 조건은 다음과 같습니다.
- 철학자들은 서로 포크를 공유할 수 없습니다.
- > 자원을 공유하지 못하면 교착 상태가 발생합니다.
- 각 철학자는 다른 철학자의 포크를 뺏을 수 없습니다.
- > 자원을 뺏지 못하면 프로세스가 자원을 놓을 때까지 기다려야 하므로 교착 상태가 발생합니다.
- 각 철학자는 왼쪽 포크를 잡은 상태로 오른쪽 포크를 기다립니다.
- > 한 자원을 잡을 상태로 다른 자원을 기다리면 교착 상태가 발생합니다.
- 자원 할당 그래프가 원형입니다.
- > 자원을 요구하는 형태가 원을 이루면 아무도 양보하지 않기 때문에 교착 상태가 발생합니다.
교착 상태 필요조건
위에서 살펴본 조건을 용어로 정리하면 다음과 같습니다.
- 상호 배제: 한 프로세스가 사용하는 자원은 다른 프로세스와 공유할 수 없는 자원이어야 합니다. 이 자원은 임계구역으로 보호되기 때문에 다른 프로세스가 동시에 사용할 수 없습니다.
- 비선점: 한 프로세스가 사용 중인 자원은 중간에 다른 프로세스가 빼앗을 수 없는 비선점 자원이어야 합니다. 빼앗을 수 있다면 교착 상태가 발생하지 않습니다.
- 점유와 대기: 프로세스가 어떤 자원을 할당받은 상태에서 다른 자원을 기다리는 상태여야 합니다. 다른 프로세스의 진행을 방해하는 교착 상태가 발생하려면 다른 프로세스가 필요로 하는 자원을 할당받은 상태에서 다른 자원을 기다리고 있어야 합니다.
- 원형 대기: 점유와 대기를 하는 프로세스들의 관계가 원을 이루어야 합니다. 프로세스가 특정 자원에 대한 점유와 대기를 한다고 해서 교착 상태에 빠지지는 않습니다. 프로세스들의 관계가 원의 형태를 띠어 프로세스가 서로 양보하지 않는 상황이 되어야 교착 상태가 발생합니다.
위 조건들 중 하나라도 충족하지 않는다면 교착 상태는 발생하지 않습니다. 따라서 위 조건들을 교착 상태 필요조건이라고 부릅니다.
중요한 점은 교착 상태와 아사 상태는 다르다는 점입니다. 아사 현상은 정책상 잘못이나 오류로 인해 특정 프로세스의 작업이 이루어지지 않는 것을 말합니다. 아사 현상은 에이징을 통해 해결할 수 있죠.
하지만 교착 상태는 정책상 문제가 없어도 자연적으로 발생할 수 있습니다. 따라서 에이징으로도 해결할 수 없고 정책 변경으로도 막을 수 없습니다. 교착 상태는 아사 현상보다 해결하기 어려운 문제이기 때문에 이를 해결하기 위해 다양한 방법이 제시되었습니다. 이제 그 방법들을 알아보도록 합시다.
교착 상태 해결 방법
교착 상태의 해결 방법은 예방(prevention), 회피(avoidance), 검출(detection)이며, 추가적으로 교착 상태가 발견된 후에 자원을 회복(recorvery)하는 방법도 있습니다.
- 교착 상태 예방교착 상태를 유발하는 네 가지 조건이 발생하지 않도록 무력화하는 방식입니다. 교착 상태는 상호 배제, 비선점, 점유와 대기, 원형 대기의 조건을 모두 충족해야 발생하므로 하나라도 무력화한다면 교착 상태는 발생하지 않습니다. 하지만 실효성이 적어 잘 사용되지는 않습니다.
- 교착 상태 회피자원 할당량을 조절하여 교착 상태를 해결하는 방법입니다. 즉 자원을 할당하다가 교착 상태를 유발할 가능성이 있다고 판단되면 자원 할당을 중단하고 지켜보는 것입니다. 그러나 자원을 얼마만큼 할당해야 교착 상태가 발생하지 않는다는 보장이 없기 때문에 실효성이 적습니다.
- 교착 상태 검출과 회복어떤 제약을 가하지 않고 자원 할당 그래프를 모니터링하면서 교착 상태가 발생하는지 살펴보는 방식입니다. 교착 상태가 발생하면 교착 상태 회복 단계가 진행됩니다. 교착 상태를 검출한 후 이를 회복시키는 것은 결론적으로 교착 상태를 해결하는 현실적인 접근 방법입니다.
교착 상태 예방
교착 상태 예방은 교착 상태 필요조건 중 하나라도 발생하지 않도록 예방하는 방법입니다.
상호 배제 예방
시스템 자원 중에서 독점적으로 사용할 수 있는 자원을 없애는 방법입니다. 시스템 내의 모든 자원을 공유할 수 있다면 교착 상태는 발생하지 않습니다. 그러나 현실적으로 모든 자원을 공유할 수는 없습니다. 따라서 상호 배제 예방은 사실상 어렵습니다.
비선점 예방
모든 자원을 빼앗을 수 있도록 만드는 방법입니다. 그러나 임계구역을 보호하기 위해 잠금을 사용하면 자원을 빼앗을 수 없을 뿐 아니라 상호 배제도 보장할 수 없습니다. 즉 비선점 조건 또한 예방하기 어렵습니다.
점유와 대기 예방
프로세스가 자원을 점유한 상태에서 다른 자원을 기다리지 못하게 하는 방법입니다. 다르게 말하면 ‘모두 할당하거나 아예 할당하지 않는’ 방식입니다. 이렇게 하려면 프로세스의 시작 초기에 필요한 모든 자원을 할당하고, 그렇지 못할 경우 아예 할당하지 않아야 합니다. 이 방법 또한 어렵습니다.
- 프로세스가 실행될 때 어떤 자원을 사용할지 예측하기 힘듭니다.
- 자원의 활용성이 떨어집니다. 만약 프로세스에 필요한 모든 자원이 할당되어 있는데 현재 사용하지 않는 자원을 다른 프로세스가 필요로 할 경우에도 현재 프로세스가 독점하고 있으므로 비효율적입니다.
- 많은 자원을 사용하는 프로세스가 적게 사용하는 프로세스보다 불리합니다. 자원을 많이 필요로 하는 프로세스는 적게 필요로 하는 프로세스보다 자원을 동시에 확보하기 어렵습니다. 이로 인해 아사 현상이 발생하게 됩니다.
이러한 방식은 결국 일괄 작업 방식으로 동작하게 됩니다. 특정 프로세스가 필요한 모든 작업을 수행하는 동안 다른 프로세스는 해당 자원이 필요한 작업을 하지 못하므로 해당 프로세스가 작업을 모두 마칠 때까지 기다려야 합니다. 이는 분산형 시스템에서 매우 비효율적인 방식이므로 점유와 대기 예방책 또한 어렵습니다.
원형 대기 예방
점유와 대기를 하는 프로세스들이 원형을 이루지 못하도록 하는 방법입니다. 즉 자원을 선형으로 사용하도록 설정함으로써 원형 대기를 예방할 수 있습니다. 예를 들면 다음과 같습니다.
마우스에 1, 하드디스크에 2, 프린터에 3의 작업 순서를 부여하고 하드디스크를 사용하려면 마우스를 먼저 사용하고, 프린터를 사용하려면 마우스->하드디스크의 작업 순서를 거치게 하는 것입니다. 이렇게 되면 원형 대기는 막을 수 있습니다. 하지만 이 방법 역시 문제가 있습니다.
- 프로세스 작업 진행에 유연성이 떨어집니다.만약 프린터 인쇄를 하고 있다면 다른 프로세스에선 마우스와 하드디스크를 사용할 수 없습니다. 즉 인쇄 작업이 끝날 때까지 다른 작업을 할 수 없습니다. 사용자 입장에선 이를 납득할 수 없습니다.
- 자원의 순서를 어떻게 정할지도 문제입니다.프로세스는 순서대로 작업을 시행해야 하기 때문에 순서를 정할 때 매우 신중하게 정해야 합니다. 그리고 순서를 어떻게 정하던지 자원 사용에 제약이 있습니다.
정리하면 상호 배제 예방과 비선점 예방은 현실적으로 어렵고, 점유와 대기 예방, 원형 대기 예방은 프로세스 처리 과정 문제와 효율성 문제로 사실상 어렵습니다.
교착 상태 회피
교착 상태 회피는 프로세스에 자원을 할당할 때 어느 수준 이상의 자원을 나눠주면 교착 상태가 발생하는지를 파악하여 그 수준 이하로 자원을 나눠주는 방법입니다. 교착 상태가 발생하지 않는 범위 내에서만 자원을 할당하고, 교착 상태가 발생하는 범위에 있으면 프로세스를 대기시킵니다.
교착 상태 회피는 할당되는 자원의 수를 조절하여 교착 상태를 피합니다. 이는 프로세스의 작업 방생을 제한하는 교착 상태 예방보다 유연한 방법입니다.
교착 상태 회피는 자원의 총수와 현재 할당된 자원의 수를 기준으로 시스템을 안정 상태(safe state)와 불안정 상태(unsafe state)로 나누고 시스템이 안정 상태를 유지하도록 자원을 할당합니다. 할당된 자원이 적으면 안정 상태가 크고, 할당된 자원이 늘어날수록 불안정 상태가 커집니다. 교착 상태는 불안정 상태의 일부로, 불안정 상태가 커질수록 교착 상태가 될 확률이 높아집니다. 교착 상태 회피는 안정 상태를 유지할 수 있는 범위 내에서 자원을 할당함으로써 교착 상태를 피합니다.
은행원 알고리즘
교착 상태 회피를 위해 에츠허르 다익스트라가 제안한 알고리즘입니다. 은행에서 대출을 해주는 방식, 즉 대출 금액이 가능한 범위 이내(안정 상태이면) 허용되지만 그렇지 않으면 거부되는 것과 유사하기 때문에 이러한 이름이 붙여졌습니다.
| 변수 | 설명 |
|---|---|
| 전체 자원(Total) | 시스템 내 전체 자원의 수 |
| 가용 자원(Available) | 시스템 내 현재 사용할 수 있는 자원의 수(가용 자원=전체 자원 - 모든 프로세스의 할당 자원) |
| 최대 자원(Max) | 각 프로세스가 선언한 최대 자원의 수 |
| 할당 자원(Allocation) | 각 프로세스에 현재 할당되어 있는 자원의 수 |
| 기대 자원(Expect) | 각 프로세스가 앞으로 사용할 자원의 수(기대 자원 = 최대 자원 - 할당 자원) |
은행원 알고리즘에서 각 프로세스는 자신이 사용할 수 있는 자원의 최대 수를 운영체제에 알려줍니다. 운영체제가 자원을 할당할 때 시스템의 상태를 파악하는데 꼭 필요한 정보이기 때문입니다.
각 프로세스에 할당된 자원의 수는 ’할당 자원’에 표시됩니다. 각 프로세스마다 자신이 선언한 최대 자원에서 현재 할당된 자원의 수를 빼면 ’기대 자원’이 됩니다. 또한 전체 자원에서 각 프로세스에 할당되고 남은 자원의 수가 ’가용 자원’입니다. 따라서 가용 자원은 전체 자원에서 모든 프로세스의 할당 자원을 뺀 값입니다. 자원을 할당할 때의 기준은 다음과 같습니다.
- 각 프로세스의 기대 자원과 비교하여 가용 자원이 하나라도 크거나 같으면 자원을 할당합니다.
- 가용 자원이 기대 자원보다 크다는 것은 그 자원을 사용하여 작업을 끝낼 수 있는 프로세스가 있다는 의미이므로 안정 상태입니다.
- 가용 자원이 어떤 기대 자원보다 크지 않으면 할당하지 않습니다. 가용 자원을 사용하여 작업을 마칠 수 있는 프로세스가 없다는 의미이므로 불안정 상태입니다.
이러한 기준을 바탕으로 안정 상태는 다음과 같이 정의됩니다.
각 프로세스의 기대 자원과 비교하여 가용 자원이 크거나 같은 경우가 한 번 이상인 경우를 말합니다.
위 상태는 안정 상태입니다. 가용 자원이 2이고, P2의 기대 자원이 2이므로 P2에 자원을 할당하여 P2의 작업을 마치고 P1과 P3에 나누어주면 되기 때문이죠.
위 상태는 불안정 상태입니다. 가용 자원은 1인데, 이것으로는 어떤 프로세스도 작업을 완료할 수 없습니다. 은행원 알고리즘에서는 현재 실행 중인 프로세스 가운데 하나라도 끝낼 수 있을 때 가용 자원을 할당해야 합니다.
문제점
교착 상태 회피의 원칙은 교착 상태가 발생하지 않을 수준으로만 자원을 할당하는 것입니다. 하지만 여기에는 다음과 같은 문제가 있어 교착 상태 회피를 사용하지 않습니다.
- 프로세스가 자신이 사용할 모든 자원을 미리 선언해야 합니다.
- 시스템의 자원 수가 고정적이어야 합니다.
- 자원이 낭비됩니다.
교착 상태 검출
교착 상태 예방은 실질적으로 구현하기 어렵고, 교착 상태 회피는 구현할 수 있지만 자원 낭비가 심한 문제가 있습니다. 따라서 교착 상태 해결 방법 중 가장 현실적인 것은 교착 상태 검출입니다. 교착 상태 검출은 운영체제가 프로세스의 작업을 관찰하면서 교착 상태 발생 여부를 계속 주시하는 방법입니다. 만약 교착 상태가 발견되면 이를 해결하기 위해 교착 상태 회복 단계를 밟습니다. 교착 상태 검출은 타임아웃을 이용하는 방법과 자원 할당 그래프를 이용하는 방법이 있습니다.
타임아웃을 이용한 교착 상태 검출
타임아웃을 이용한 교착 상태 검출은 일정 시간 동안 작업이 진행되지 않은 프로세스를 교착 상태가 발생한 것으로 간주하여 처리하는 방법입니다. 교착 상태가 자주 발생하지 않을거라는 가정하에 사용하는 것으로, 특별한 알고리즘이 없어 쉽게 구현할 수 있습니다. 하지만 다음과 같은 문제가 있습니다.
- 엉뚱한 프로세스가 강제 종료될 수 있습니다.타임아웃 시간 동안 작업이 진행되지 않은 모든 프로세스가 교착 상태 때문에 작업이 이루어지지 않은 것은 아닙니다. 타임아웃을 이용하면 교착 상태 외의 다른 이유로 작업이 진행되지 못하는 모든 프로세스가 강제 종료될 수 있습니다.
- 모든 시스템에 적용할 수 없습니다.하나의 운영체제 안에서 동작하는 프로세스들은 그 상태를 운영체제가 감시하기 때문에 타임아웃 방법을 적용할 수 있습니다. 하지만 여러 군데에 데이터가 나뉘어있는 분산 데이터베이스의 경우 타임아웃을 적용하기가 어렵습니다. 분산 데이터베이스는 데이터가 여러 시스템에 나뉘어져 있고 각 시스템이 네트워크로 연결되어 있습니다. 이러한 시스템 때문에 원격지에 있는 프로세스의 응답이 없는 것이 교착 상태 때문인지, 네트워크 문제인지, 단순히 처리가 늦어지는 건지 알 수 가 없습니다. 그러므로 타임아웃을 적용하여 교착 상태를 파악하기 어렵습니다.
그럼에도 타임아웃은 대부분의 데이터베이스와 운영체제에서 많이 사용됩니다. 이유는 자원 할당 그래프를 이용한 교착 상태 검출은 작업이 너무 많아 구현하기 힘들기 때문입니다. 자주 발생하지 않는 교착 상태를 찾기 위해 자원 할당 그래프를 유지하면서 모든 자원을 감시하기는 어렵습니다. 그래서 타임아웃을 이용하는 방법을 ’가벼운 교착 상태 검출’이라 부르고, 자원 할당 그래프를 이용하는 방법을 ’무거운 교착 상태 검출’이라고 부릅니다.
자원 할당 그래프를 이용한 교착 상태 검출
자원 할당 그래프를 이용하여 시스템 내의 프로세스가 어떤 자원을 사용하고 있는지 기다리고 있는지를 확인하여 교착 상태를 검출하는 방법입니다. 자원 할당 그래프를 이용하여 교착 상태를 검출하는 방법은 프로세스의 작업 방식을 제안하지 않으면서 교착 상태를 정확하게 파악할 수 있다는 것이 장점입니다. 하지만 자원 할당 그래프를 유지하고, 갱신하고, 사이클을 검사하는 추가 작업으로인해 오버헤드가 발생하는 단점이 있습니다.
교착 상태 회복
교착 상태가 검출되면 교착 상태를 푸는 후속 작업을 하는데 이를 교착 상태회복이라고 합니다. 교착 상태 회복 단계에서는 교착 상태를 유발한 프로세스를 강제로 종료합니다. 프로세스를 종료하는 방법에는 다음과 같이 두 가지가 있습니다.
- 교착 상태를 일으킨 모든 프로세스를 동시에 종료교착 상태를 일으킨 모든 프로세스를 종료하는 방법입니다. 주의할 것은 종료된 프로세스들이 동시에 시작되면 다시 교착 상태를 일으킬 가능성이 있으므로, 다시 실행할 때는 순차적으로 실행해야 하며, 이때 어떤 프로세스를 먼저 실행할 것인지 기준이 필요합니다.
- 교착 상태를 일으킨 프로세스 중 하나를 골라 순서대로 종료교착 상태를 일으킨 프로세스 중 하나를 골라 순서대로 종료하면서 나머지 프로세스의 상태를 파악하는 방법입니다. 프로세르를 종료할 때는 무엇부터 종료할지 기준이 필요합니다.
- 우선순위가 낮은 프로세스를 종료
- 우선순위가 같은 프로세스일 경우 작업 시간이 짧은 프로세스를 먼저 종료
- 위 두 조건이 같은 경우 자원을 많이 사용하는 프로세스를 먼저 종료
Uploaded by Notion2Tistory v1.1.0