📚 Deadlock(교착 상태)
둘 이상의 프로세스가 다른 프로세스가 점유하고 있는 자원을 서로 기다릴 때 무한 대기에 빠지는 상황
즉, 두 개의 프로세스가 자원을 점유한 상태에서 서로가 점유한 자원을 요구하며 작업을 진행하지 못하고 대기하고 있는 상태를 말한다.
Deadlock의 발생 조건
교착 상태는 아래 4가지 조건이 모두 만족되어야 발생할 수 있으며, 하나라도 만족하지 않으면 발생하지 않는다.
1) 상호 배제 (Mutual Exclusion)
한 번에 하나의 프로세스만 공유 자원을 점유할 수 있다.
2) 점유 대기 (Hold and Wait)
프로세스가 자원을 할당받은 상태에서 다른 프로세스에 할당된 자원을 점유하기 위해 대기하고 있다.
3) 비선점 (No Preemption)
프로세스가 작업을 마친 후 자원을 자발적으로 반환해야 다른 프로세스가 공유 자원에 접근할 수 있다.
(자원을 강제로 빼앗을 수 없다.)
4) 순환 대기 (Circular Wait)
대기 프로세스 집합이 순환 형태로 자원을 대기하고 있다.
(자원 점유 및 점유 자원 대기의 요구 관계가 원형을 이루는 상태)
📚 Deadlock의 해결 방법
예방 (Prevention)
교착 상태의 발생 조건이 만족하지 않게 하는 것
상호 배제 조건 방지
동시에 여러 프로세스가 공유 자원을 사용할 수 있게 한다.
- 동기화 문제 발생 가능
점유 대기 조건 방지
프로세스 실행에 필요한 모든 자원을 한번에 요구하도록 하거나 자원을 점유하지 않은 상태에서만 자원을 요청할 수 있도록 한다.
비선점 조건 방지
자원에 대한 선점을 허용한다.
순환 대기 조건 방지
자원을 선형으로 분류하여 고유번호를 할당하고, 각 프로세스는 한 쪽 방향으로만 자원을 요구할 수 있도록 한다.
교착 상태 예방 방법은 시스템의 처리량이나 자원 사용의 효율을 떨어뜨린다는 단점이 있다.
회피 (Avoidance)
교착 상태가 발생할 가능성이 없는 안전한 상태(safe state)에서만 자원 요청을 허용하는 방법
- 프로세스 수 고정
- 자원의 종류와 수 고정
- 프로세스가 요구하는 최대 자원의 수를 알아야 함
- 프로세스는 자원 사용 후 반드시 반납
Unsafe state (불안정 상태)
교착 상태 발생 가능성이 있는 상태
Safe state (안정 상태)
safe sequence가 존재하며 모든 프로세스가 정상적으로 종료될 수 있는 상태
safe sequence (안전 순서)
교착 상태를 발생시키지 않고 자원을 할당할 수 있는 순서
은행원 알고리즘 (Banker's Algorithm)
프로세스가 자원을 요구할 경우 시스템은 자원을 할당한 후에 안정 상태를 유지할 수 있는지 사전에 검사하여 교착 상태를 회피하는 알고리즘
가정
: 시스템이 총 12개의 자원을 가지고 있다.
| (t=t0) | Max | Allocation | Need Available |
|---|---|---|---|
| P0 | 10 | 5 | 5 |
| P1 | 4 | 2 | 2 |
| P2 | 9 | 2 | 7 |
현재 할당 중인 자원량의 합 은 5+2+2 = 9 입니다. 시스템은 총 12개의 자원을 가지고 있으므로 현재 상태에서 가용 자원량은 12 - 9 = 3 이 됩니다.
여기서 가용자원을 어느 프로세스에게 할당해주느냐에 따라서 자원을 효율적으로 이용할 수 있게 됩니다.
남은 가용자원 3개를 P1에게 할당
가용자원은 3 - 2 = 1P1의 작업이 끝나고 할당되어 있던 자원 4개 반납
▶ 가용자원은 1 + 4 = 5
남은 가용자원 5개를 P0에게 할당
▶ 가용자원은 5 - 5 = 0
P0의 작업이 끝나고 할당되어 있던 자원 10개 반납
▶ 가용자원은 0 + 10 = 10
남은 가용자원 10개 중 7개를 P2에게 할당
▶ 가용자원은 10 - 7 = 3
P2의 작업이 끝나고 할당되어 있던 자원 9개 반납
▶ 가용자원은 3 + 9 = 12
이렇게 P1 - P0 - P2 순서로 자원 할당 시 Safe sequence를 만족하게 됩니다.
문제점
미리 자원의 최대 요구량을 알아야 하고, 할당할 수 있는 자원의 수가 일정해야 하는 등 제약이 많다.
▶ 현실적으로 문제 발생에 대한 일관성과 가정이 완벽하다는 것을 보장하기가 어렵다.
자원 할당 그래프 알고리즘 (Resource-Allocation Graph Algorithm)
자원 할당 그래프에 예약 간선을 추가하여 예약 간선으로 설정한 자원에 대해서만 자원 할당을 요청할 수 있고 사이클이 형성되지 않을 때만 자원을 할당받는 방법
탐지 (Detection) 및 회복 (Recovery)
시스템에 교착 상태가 발생했는지 여부를 탐색하고 회복 기법 알고리즘에 활용하는 방법
탐지
현재 시스템의 자원 할당 상태(Allocation, Request, Available) 또는 자원 할당 그래프를 통해 교착 상태 발생 여부를 탐지
회복
교착 상태가 탐지되면 강제 종료 또는 자원 선점을 통해 교착 상태에서 회복
프로세스(또는 스레드) 종료
1) 교착 상태의 프로세스를 모두 중지
확실하게 교착 상태에서 벗어날 수 있지만 더 큰 비용이 발생할 수 있다.
만약 프로세스가 오래 걸리는 연산을 완료한 경우, 연산의 부분 결과들이 모두 버려지고 재작업해야 한다.
2) 교착 상태가 회복될 때까지 프로세스 하나씩 중지
각 프로세스가 중지될 때마다 교착 상태 탐지 알고리즘을 호출해 교착 상태인지 확인해야 하기 때문에 오버헤드가 발생한다.
자원 선점
프로세스로부터 자원을 빼앗아 교착 상태가 해결될 때까지 다른 프로세스들에게 자원을 할당
질문1
데드락 회피 방법에 대해 간단히 설명하세요.
데드락 회피는 교착 상태의 가능성이 없는 안전한 상태, 안정 상태에서만 자원 요청을 허용하는 방법입니다. 안정 상태에서는 교착 상태를 발생시키지 않는 자원 할당 순서인 안전 순서가 존재해야 한다는 조건이 있습니다. 예로는 은행원 알고리즘, 자원 할당 그래프 알고리즘이 있습니다.
질문2
데드락 발생 조건에 대해 설명하세요.
데드락 발생 조건에는 상호 배제, 점유 대기, 비선점, 순환 대기가 있습니다.
상호 배제는 하나의 프로세스만 공유 자원에 접근할 수 있는 것이고, 점유 대기는 둘 이상의 프로세스가 자원을 점유한 상태로 서로 다른 프로세스의 자원을 얻기 위해 대기하는 상태 입니다. 비선점은 프로세스에게서 강제로 자원을 뺏을 수 없는 것이고, 순환 대기는 자원을 요청하는 프로세스들이 순환 상태인 것입니다.
질문3
데드락이란 무엇인지 간단히 설명하세요.
둘 이상의 프로세스가 자원을 점유한 상태에서 서로가 점유한 자원을 요구하며 작업을 진행하지 못하고 대기하고 있는 상태를 말합니다.
