1. Deadlock 상태란
Deadlock 상태, 교착 상태란 서로 원하는 리소스가 상대 프로세스에 할당되어, 프로세스들이 무한정 대기하는 상태를 의미한다.
2. Deadlock 상태의 필수 조건 4가지
아래 조건들이 AND로 모두 성립되어야 Deadlock 상태라고 한다.
1. 상호배제
자원은 한번에 한 프로세스만 이용이 가능해야 한다.
2. 점유대기
- (이미 한 자원을) 점유(하면서 다른 자원도) 대기
하나 이상의 자원을 점유하면서, 다른 프로세스에 점유 중인 자원 사용을 위해 대기하는 프로세스가 있어야 한다.
3. 비선점
- 자원사용에 있어 선점(앞서서 차지함)이 허용되지 않음
다른 프로세스에 할당된 자원은 사용이 끝날 때 까지 강제로 빼앗아 선점하는 것이 불가능하다.
4. 순환대기
- 아래와 같이 꼬리에 꼬리를 물어 순환형 구조를 이루는 대기
프로세스의 집합 P = {p0, p1, ..., pn}에서
p0 --대기-> p1이 사용중인 자원
p1 --대기-> p2이 사용중인 자원
...
pn-1 --대기-> pn이 사용중인 자원
pn --대기-> p0이 사용중인 자원3. Deadlock 예방
Deadlock 상태의 필수 조건 4가지 중 한 가지만 부정해도 Deadlock이 발생하지 않는다. 이를 이용해 각 조건을 부정하는 방식으로 Deadlock을 예방할 수 있다.
1. 상호배제 부정
자원은 한번에 한 프로세스만 이용이 가능해야 한다.
👉 여러 프로세스가 한번에 한 공유 자원을 사용할 수 있도록 한다.
2. 점유대기 부정
하나 이상의 자원을 점유하면서, 다른 프로세스에 점유 중인 자원 사용을 위해 대기하는 프로세스가 있어야 한다.
👉 프로세스 실행 전 필요한 모든 자원을 할당하여, 다른 프로세스에 점유 중인 자원을 대기하지 않도록 한다.
3. 비선점 부정
다른 프로세스에 할당된 자원은 사용이 끝날 때 까지 강제로 빼앗아 선점하는 것이 불가능하다.
👉 자원 R1을 점유 중인 프로세스 P1이 다른 프로세스 P2 에서 사용 중인 자원 R2을 요구할 때, P1이 사용 중인 자원 R1을 반납하게 하고 요구한 자원 R2을 사용하기 위해 대기시킨다.
4. 순환대기 부정
꼬리에 꼬리를 물어 순환형 구조를 이루는 대기
👉 자원에 고유 번호를 할당하여 번호 순서대로 자원을 할당받게 한다.
4. Deadlock 회피
1. 은행원 알고리즘
프로세스가 자원을 요구할 때, 시스템이 교착 상태가 되지 않는 지를 사전에 검사하여 교착상태가 되지 않을 때만 요구를 수락하고, 교착 상태가 예상되는 프로세스의 자원 요구는 나중에 교착상태가 되지 않을 때까지 계속 거절한다.
5. Deadlock 으로부터의 회복
1. 프로세스 종료
- 교착 상태의 프로세스를 모두 종료
- 교착 상태 프로세스를 교착 상태 해소 시 까지 하나씩 늘려가며 종료
2. 자원 선점
- 교착 상태의 프로세스가 점유하고 있는 자원을 선점하여 다른 프로세스에 할당하고, 기존 점유 중이던 프로세스는 종료
- 최소 비용이 들도록 희생자를 선택함. 롤백이나 기아상태에 대한 고려가 필요함.
