교착상태(deadlock) 발생 조건
교착상태란?
두 개 이상의 작업들이 서로의 작업이 끝나기를 기다리면서 더이상 처리와 응답이 불가능해지는 상태
프로세스(스레드)는 아래 4가지 조건을 모두 만족할 경우 교착상태에 빠질 수 있습니다.
-
상호배제 (mutual exclusion)
프로세스들이 필요로 하는 자원에 대해 배타적인 통제권을 요구한다.
ex) 프로세스 1번, 2번과 자원 A가 있다고 하였을때,
1번이 자원 A를 점유하게 되면 1번이 자원 A를 반환할때까지 2번은 자원 A를 점유할 수 없습니다.
1번이 자원 A를 무한히 점유하게 되면 2번은 자원 A를 기다리며 교착상태에 빠질 수 있습니다.
-
점유와 대기 (hold and wait)
프로세스가 할당된 자원을 가진 상태에서 다른 자원을 기다린다.
ex) 프로세스 1번, 2번, 3번과 자원 A, B가 있다고 하였을때,
1번이 자원 A를 점유하고 2번이 자원 B를 점유한 상태에서,
1번이 자원 A를 반환하지 않고 자원 B까지 점유하지 위해 2번이 B를 반환하기를 기다릴 경우,
3번이 1번이 반환하지 않은 자원 A를 점유하려 시도하게 되면서 교착상태에 빠질 수 있습니다.
-
비선점 (non-preemptive)
프로세스가 어떤 자원의 사용을 끝낼 때까지 그 자원을 뺏을 수 없다.
ex) 프로세스 1번, 2번, 3번과 자원 A가 있다고 하였을때,
1번이 자원 A를 점유한채 무한루프 상태에 빠지게 된 경우에도 2번과 3번은 자원을 선점하지 못하고 1번이 끝나기만을 기다리며 교착상태에 빠질 수 있습니다.
-
순환 대기(circle wait)
각 프로세스는 순환적으로 다음 프로세스가 요구하는 자원을 가지고 있다.
ex) 프로세스 1번, 2번과 자원 A, B가 있다고 하였을때,
1번이 자원 A를 점유하고, 2번이 자원 B를 점유한 후, 자원들을 반환하지 않고 (두 자원을 모두 얻어야 모든 작업을 처리하고 두 자원을 함께 반환하는 구조라고 가정)
1번은 자원 B를 점유하려 시도하고, 2번은 자원 A를 점유하려 시도하게 되면서 교착상태에 빠질 수 있습니다.
교착 상태 해결방법
교착상태를 해결하는 방법은 크게 예방, 회피, 탐지-복구 세 가지로 나눌 수 있습니다.
교착 상태 예방 (Deadlock Prevention)
교착상태는 교착상태 발생조건 네 가지를 모두 만족할 때 발생하므로, 특정 조건이 만족하지 않도록 방지함으로써 교착상태를 예방할 수 있습니다.
- 상호배제 (mutual exclusion)
-
상호배제가 필요하지 않은 작업의 경우 자원을 공유하여 사용
ex) 읽기 전용 파일
- 점유와 대기 (hold and wait)
-
프로세스가 부분적으로 자원을 점유하는 일이 발생하지 않기 위해 프로세스 실행시 필요한 모든 자원을 한번에 할당
=> 자원 낭비 발생 위험 있음
-
프로세스가 자원을 점유하지 않은 경우에만 자원 요청이 가능하도록 함
=> 프로세스의 우선순위가 낮은 경우 계속해서 자원을 할당 받을 수 없어 starvation(기아상태) 발생 가능
- 비선점 (non-preemptive)
-
선점 가능하도록 변경
=> 기존에 실행중이던 프로세스가 중단되어 작업 내용을 잃을 수 있음 - 자원 낭비 발생
- 순환 대기(circle wait)
-
모든 자원에 할당 순서를 부여하여 제어
ex) 프로세스1번, 자원 A, B가 있을때 자원 할당 순서를 A->B 라고 가정하면, 프로세스1번은 자원 B를 점유하기 위해서는 반드시 자원 A를 먼저 점유해야 함
=> 불필요한 자원을 할당 받아 자원 낭비가 발생할수 있고, 자원 할당 순서로 인해 불필요한 점유시간이 길어져 전체적으로 비효율적인 처리가 발생할 수 있음
교착 상태 회피 (Deadlock Avoidance)
교착 상태가 발생하기 예상하여 안전한 상태(safe state)에서만 자원을 할당하고, 안전하지 않은 상태(unsafe state)에서는 자원을 할당하지 않도록 회피하는 방법입니다.
교착상태 회피를 하기 위해서는 다음과 같은 가정이 필요합니다.
- 프로세스 수가 고정되어 있어야 한다.
- 자원의 종류와 수가 고정되어 있어야 한다.
- 프로세스가 요구하는 자원 및 최대 자원의 수를 알아야 한다.
- 프로세스는 반드시 자원을 사용 후 반납해야 한다.
교착상태 회피 방법은 이러한 가정들이 필요하기 때문에 현실성이 부족합니다.
또한 자원 요청이 있을 때마다 교착상태 회피 알고리즘을 사용한다 것은 상당한 오버헤드입니다.
Safe state
safe sequence 가 존재하여 모든 프로세스가 정상적으로 종료할 수 있는 상태를 말합니다.
- safe sequence : 교착 상태를 발생 시키지 않고 자원을 할당하는 순서
Unsafe state
교착상태가 될 수 있는 상태입니다.
불안정 상태라서 반드시 교착상태가 발생하는 것은 아닙니다.
은행원 알고리즘 (Banker's Algorithm)
각 자원 유형마다 다수의 인스턴스를 갖는 경우 은행원 알고리즘으로 교착상태를 회피할 수 있습니다.
방법
- 프로세스 시작시 자신이 필요한 각 자원의 최대(Max) 개수를 미리 선언합니다.
- 각 프로세스에서 자원요청이 있을때 요청을 승인하면 시스템이 안전한 상태(safe state)로 유지되는 경우에만 자원을 할당합니다.
- 불안정 상태(unsafe state)가 예상되면 다른 프로세스가 끝날 때까지 대기를 합니다.
탐지와 복구(Detection and Recovery)
교착상태 탐지
탐지 알고리즘을 사용하여 교착상태가 발생했는지 탐지합니다.
탐지 알고리즘의 수행 빈도가 잦으면 오버헤드로 성능저하가 발생하게 됩니다.
Resource Allocation Graph(RAG)를 사용하면 교착상태 탐지에 용이합니다.
RAG
RAG는 시스템에서 자원의 할당 상태를 나타냅니다.
- 프로세스가 어떤 자원을 점유하고 있고 대기하고 있는지 나타냅니다.
- 어떤 자원이 사용 가능한지 혹은 특정 프로세스에 점유되어있는지를 나타냅니다.
그래프 표현
-
정점 표현
- 프로세스(P): 원(circle)
- 자원(R): 직사각형(rectangle)
-
간선 표현
- 점유 : R->P
- 대기 : P->R
교착상태 탐지 방법
RAG에서 자원을 제거후 간선들을 결합하여 대기 그래프를 표현 할 수 있습니다.
대기 그래프에서 Pi -> Pj는 프로세스 Pi가 Pj 프로세스가 보유하고 있는 자원을 기다리는 것을 나타냅니다.
대기 그래프에 cycle이 있다면 교착 상태를 의미합니다.
복구
교착 상태가 발생했다면 교착 상태를 일으킨 프로세스를 종료하거나, 할당된 자원을 해제함으로써 복구를 합니다.
1. 프로세스 종료
교착상태에 있는 프로세스를 종료하여 해결하는 방식입니다. 프로세스 종료에는 두가지 방법이 있습니다.
-
교착 상태의 프로세스 모두 중지
-
교착 상태가 해결될 때까지 한 프로세스씩 중지
2. 자원 선점
교착 상태에 있는 프로세스가 점유하고 있는 자원을 선점하여 다른 프로세스에게 할당하여 해당 프로세스를 일시 정지시키는 방법입니다.
자원 선점에 있어서 다음 사항들을 고려해야 합니다.
-
희생자 선택 (selection of a victim)
- 최소의 피해를 줄 수 있는 프로세스를 선택
- 한 프로세스가 계속 선점되는 starvation을 방지하기 위해 선점될 때마다 프로세스 우선순위를 높이는것과 같은 방법을 사용
-
롤백(rollback)
-
선점 된 프로세스를 문제가 없는 이전 상태로 롤백
=> 프로세스 실행 중간 마다 해당 시점의 상태를 표시 해두는 검사점 지정(checkpoint) 방식을 이용할 수 있습니다. 만약 프로세스가 교착 상태를 유발해 종료하기로 결정되면 checkpoint를 이용해 해당 지점으로 돌아가며 적절한 복구 지점을 찾습니다.
-
프로세스를 중지시키고 재시작
-
[참고]
