데드락 (Dead Lock)
운영체제 속 데드락이란, 둘 이상의 프로세스가 다른 프로세스가 소유하고 있는 자원을 서로 기다릴 때 무한 대기에 빠지는 상황을 말한다.
발생 조건
상호 배제 (Mutual Exclusion)
•
한 번에 프로세스 하나만 해당 자원을 사용할 수 있다.
점유 대기 (Hold and Wait)
•
자원을 최소한 하나 보유하고, 다른 프로세스에 할당된 자원을 점유하기 위해 대기하는 프로세스가 존재해야 한다.
비선점 (Non-Preemptive)
•
이미 소유한 자원을 강제로 빼았을 수 없다.
순환 대기 (Circular Wait)
•
대기 프로세스의 집합이 순환 형태로 자원을 대기하고 있어야 한다.
해결방법
예방 (Prevention)
발생 조건 4가지 중 하나라도 발생하지 않게 하는 것이 핵심!
•
상호 배제 방지 : 한번에 여러 프로세스가 공유 자원을 사용할 수 있게 한다 → 동기화 문제가 발생..
•
점유 대기 방지 : 프로세스 실행에 필요한 모든 자원을 한꺼번에 요구하고 허용할 때까지 작업을 보류 → 자원 점유를 위한 대기 차단!
•
비선점 방지 : 이미 할당된 자원이 선점권이 없다고 가정할 때, 높은 우선순위의 프로세스가 해당 자원을 선점하도록 한다 → 뺐어오기 가능
•
순환 대기 방지 : 자원에 고유한 번호를 부여하고, 번호 순서대로 자원을 요구하도록 한다.
단점
•
시스템의 처리량이나 효율성이 떨어진다
•
가장 제한적인 방법
회피 (Avoidance)
•
안전 상태 (Safe State) : 프로세스들이 요청하는 모든 자원을 데드락 없이 차례로 모두 할당해 주는 경우
•
안전 순서 (Safe Sequence) : 데드락 없이 모든 자원을 할당해 주었을 때의 순서를 의미
즉, 불안정 상태일 때, 데드락이 발생할 수 있는 상황이고, 회피는 자원 할당 후에도 시스템이 항상 안정 상태에 있도록 할당을 허용하는 것이다.
은행원 알고리즘 (Banker’s Algorithm)
•
어떤 자원의 할당을 허용하는지에 대한 여부를 결정하기 전에, 미리 결정된 모든 자원들의 최대 가능한 할당량을 가지고 시뮬레이션해서 안정 상태일 수 있는지 검사한다.
•
즉, 데드락의 발생 가능성을 미리 조사하는 것이다.
처음 시스템이 총 12개의 자원이 있다고 가정해보자
(t = t0) | Max | Allocation | Need | Available |
P0 | 10 | 5 | 5 | |
P1 | 4 | 2 | 2 | |
P2 | 9 | 2 | 7 |
P0 ~ P2는 프로세스, Max 는 각 프로세스의 최대 자원 요청량, Allocation 은 현재 할당 중인 자원의 양, Need 는 남은 필요한 자원의 양이다.
현재 t0 일 때, 프로세스에 할당된 자원의 합은 5 + 2 + 2 = 9개 이다. 따라서 사용가능한 남은 자원은 3개이다.
안전 순서를 찾아보자
•
P1 은 2개를 추가로 할당받길 기다리고 있다. 남은 자원의 수는 3개이므로 이 중 2개를 P1 에게 할당해준다 → 사용 가능 자원 : 3 - 2 = 1개
•
실행이 끝난 P1 은 자신에게 할당된 자원 4개를 반납한다. → 사용 가능 자원 : 1 + 4 = 5개
•
모두 P0 에게 할당해주면 P0도 실행 가능해진다 → 사용 가능 자원 : 5 - 5 = 0개
•
실행이 끝난 P0 은 자신에게 할당된 자원 10개를 모두 반납한다 → 사용 가능 자원 : 0 + 10 = 10개
•
마지막으로 P2 에게 자원 7개를 할당한다 → 사용 가능 자원 : 10 - 7 = 3개
•
실행이 끝난 P2 는 자신에게 할당된 자원 9개를 모두 반납한다 → 사용 가능 자원 : 3 + 9 = 12개
따라서 안전 순서는 <P1, P0, P2> 가 된다.
만약 P2 가 처음 자원을 2개가 아닌 3개를 할당 받았다면 사용가능 자원은 2개 였을 것이다.
이 상황에서, P1 에게 2개를 모두 할당하고, 끝난 뒤 반납해도 사용 가능 자원은 4개이므로, P0 이나 P2 을 해결할 수 없다.
단점
•
미리 최대 자원 요구량을 알아야 하고, 할당할 수 있는 자원 수가 일정해야하는 제약 조건이 존재한다.
탐지 & 회복 (Detection & Recovery)
탐지 기법
•
Allocation, Request, Available 등으로 데드락의 발생 여부 탐지 → 은행원 알고리즘과 유사하게 자원 할당 상태로 파악
•
자원 할당 그래프 이용
회복 기법
•
데드락을 탐지했다면, 순환 대기에서 벗어나는 회복 방법 사용
•
프로세스 1개 이상 중단시키기
◦
데드락 상태의 모든 프로세스 중단 : 중간 단계 결과가 폐기되는 단점
◦
프로세스를 하나씩 중단하며 데드락 탐지 & 회복 : 매번 탐지해야 하므로, 오버헤드가 크다는 단점
•
자원 선점하기