1. 교착 상태(Dead Lock)
프로세스가 작업을 진행하기 위해서는 필요에 따라 CPU, 메모리, 파일, 하드웨어 등 다양한 자원이 요구된다.
A프로세스와 B프로세스가 작업을 진행하기 위해서는 X자원과 Y자원이 요구된다. X자원은 A프로세스가 가지고 있고, Y자원은 B프로세스가 가지고 있다고 할 경우 각각의 프로세스는 요구 조건을 충족하지 못하므로 작업을 진행할 수 없다.
(병렬처리, 자원 공유 방식에 따른 부작용 중 하나이다)
이처럼 2개 이상의 프로세스가 서로 다른 프로세스의 작업이 끝나기만 기다리며 작업을 더 이상 진행하지 못하는 상태를 교착 상태(Dead Lock)라 부른다.
1-1. 교착 상태 필요조건(Necessary Conditions)
교착 상태가 일어나기 위해서는 아래 네 가지 조건이 모두 충족해야 한다. (모두 충족해도 발생하지 않을 수 있음)
- Mutual exclusion (상호배타)
필요한 A자원을 다른 프로세스가 사용하고 있다면, A자원은 사용할 수 없다. - Hold and wait (보유 및 대기)
B자원을 가지고 다른 프로세스가 사용 중인 A자원을 다 사용할 때까지 대기한다. - No Preemption (비선점)
A자원을 강제로 뺏을 수 없다. - Circular wait (환형 대기)
자원이 필요한 프로세스들끼리 원형을 이루며 대기 (꼬리물기)
1-2. 아사(기아)(Starvation) 현상
교착 상태가 지속되어 여러 프로세스가 부족한 자원을 점유하기 위해 경쟁을 하게 되면서 특정 프로세스의 작업이 끊임없이 지연되는 문제를 아사(기아) 현상이라 부른다.
(스케줄링 과정에서 높은 우선순위를 가지고 있는 프로세스 때문에 계속된 양보 문제 또한 아사(기아) 현상이다.)
2. 교착 상태의 예시
2-1. 식사하는 철학자 문제
식사하는 방법
1. 식사하기 위해서는 두 개의 포크가 필요하다.
2. 한순간에 하나의 포크만 잡을 수 있다. (한 번에 두 개의 포크를 동시에 잡을 수 없다.)
3. 왼쪽에 있는 포크를 잡은 뒤 오른쪽에 있는 포크를 잡아야 식사가 가능하다.
식사하는 철학자 교착 상태
1. 철학자들은 서로 포크를 공유할 수 없음 (Mutual exclusion)
2. 철학자는 다른 철학자의 포크를 뺏을 수 없음 (No Preemption)
3. 모든 철학자는 왼쪽에 포크를 잡고 오른쪽 포크를 기다리고 있음 (Hold and wait)
4. 원형을 이루며 오른쪽 포크를 원하고 있음 (Circular wait)
3. 교착 상태 해결 방법
3-1. 교착 상태 예방(Dead Lock Prevention)
교착 상태 예방(Dead Lock Prevention)은 교착상태의 네 가지 필요 조건 중 한 가지 이상을 만족시키지 않게 하는 방법입니다.
- 상호배타(Mutual exclusion)
자원을 공유하는 것은 현실적으로 불가능하다. (자원 공유 시 원하는 결과가 나올 수 없다) - 보유 및 대기(Hold & Wait)
한 프로세스가 자원을 점유하면 다른 프로세스는 자원을 점유하지 못하는 방법이다. 자원을 할당받은 프로세스가 작업을 완료하기 전까지 다른 프로세스들은 무한 대기를 하므로 starvation(아사) 현상이 발생할 수 있다. (대기현상이 발생하기 때문에 자원 효율성이 떨어진다.) - 비선점(No preemption)
자원을 뺏긴 프로세스는 처음부터 작업을 다시 수행해야 하므로 자원적/시간적으로 낭비가 심하기 때문에 현실적으로 불가능하다. - 환형 대기(Circular wait)
자원에 번호를 부여하여 번호의 오름 차수로 자원을 요청하는 방법이다.
프로세스는 순서대로 자원을 요청할 수 있지만, 이 또한 대기현상이 발생하여 자원의 효율성이 떨어진다.
3-2. 교착 상태 회피(Dead Lock Avoidance)
교착 상태 회피(Dead Lock Avoidance)는 시스템의 상태를 계속 감시하는 방법이다.
자원을 요구하는 프로세스가 Dead Lock 상태가 될 가능성이 있는지를 확인하여 될 가능성이 있는 경우 자원의 할당을 보류한다.
또한 시스템은 항상 Safe State(안전 상태)를 유지해야 하며, 안전 할당(Safe allocation)을 해야 한다.
- Safe State: 모든 프로세스가 정상적으로 종료 가능
- Unsafe State: 교착 상태가 발생할 가능성이 있음
- Safe allocation: 안전 할당
- Unsafe allocation: 불안정 할당(교착 상태 유발)
3-2-1. 은행원 알고리즘(Banker's Algorithm)
은행원 알고리즘(Banker's Algorithm)은 사람을 프로세스로, 돈을 자원으로 비교하여 교착 상태 회피를 쉽게 설명하는 이론이다.
프로세스에 자원을 할당한 뒤 작업이 종료되어 자원을 다시 회수 했을 때 Safe State를 유지하면 다른 프로세스에도 자원을 할당한다. 그렇지 않다면 Unsafe State 상태가 되어 교착 상태에 빠지게 된다.
3-3. 교착 상태 탐지 및 복구(Dead Lock Detection & Recovery)
시스템에서 교착상태가 발생했는지를 주기적으로 검사하고, 교착 상태 발생 시 복구하는 방법이다. (교착 상태가 발생하는 것을 허용)
교착 상태를 탐지하는 방법으로는 자원 할당 그래프를 활용한 탐지 알고리즘이 있다. 탐지 알고리즘을 사용하여 주기적으로 검사를 한다.
교착 상태를 복구하는 방법으로는 프로세스 종료와 자원 선점이 있다.
- 프로세스 종료
교착 상태에 있는 프로세스를 종료시켜 처음부터 다시 시작 - 자원 선점
교착 상태를 해결하기 위해 선점할 자원을 일부 선택하여 프로세스에게 할당
3-4. 교착 상태 무시
교착 상태는 네 가지 필요 조건을 모두 만족해도 발생할 가능성이 작다. 현실에서 교착 상태는 매우 드물게 나타나는 현상이기 때문에 교착 상태를 그냥 무시하는 것도 하나의 방법이다. 만약 교착 상태가 발생하더라도 재부팅 하여 다시 시작한다.
Reference
