Deadlock
Process scheduling과 Process synchronization에 대해 배웠다면,
이제는 Deadlock에 대해서 배워보자.
교착상태(Deadlock)
1) 교착상태가 발생하기 위해서는 4가지 조건이 동시에 만족되어야한다.
① 상호배제(mutex exclusion) : 한 번에 한 프로세스만이 자원을 사용해야 하는 경우
② 점유와 대기(block and wait) : 자원을 일부 점유하면서 다른 자원을 기다리는 경우
③ 비선점(non preemption) : 프로세스가 완료되기 전에는 자원을 회수할 수 없는 경우
④ 환형 대기(circular wait) : 자원을 할당 받은 두 프로세스가 서로 할당된 자원을 요청하는 경우
2) 교착 상태 해결방안 3가지
① 교착상태 예방(prevention) : 교착상태의 발생가능성을 없애는 방법 -> 자원낭비가 심하고, 기아상태 초래 가능
상호배제 부정 : 여러 프로세스가 동시에 공유자원을 사용하도록 한다(실현불가능)
점유와 대기조건의 부정 : 자원을 모두 할당하거나 할당된 자원을 없앤 후 재요청
비선점 조건의 부정 : 자원을 점유하고 있는 프로세스는 자원을 강제로 반납
환형 대기 조건의 부정 : 자원을 선형 순서로 분류하여 프로세스에게 할당
② 교착상태의 회피(avoidance) : 시스템 운영 상황을 보아가면서 교착상태 가능성을 피해가는 방법
자원할당 그래프 or 은행원 알고리즘 이용
자원할당 그래프(Resource allocation graph)
-
- 프로세스와 자원과의 관계를 나타내는 그래프
- 자원할당 그래프를 그려 사이클이 생길 것 같으면 사용자의 자원 요구 거부
((교착상태에 빠질 가능성이 있는 지 판단하기 위해 시스템 상태를 2개로 나눔))
- 안전상태(safe state) : 시스템이 교착상태를 일으키지 않으면서,
각 프로세스가 요구한 최대 요구량만큼 필요한 자원을 할당해 줄 수 있는 상태
- 불안전상태(unsafe state) : 교착상태가 일어날 수 있는 상태. 무조건 발생하는 건 아님
은행원 알고리즘에 대해 알아보자.
은행원 알고리즘(Banker's Algorithm)
- 안전상태를 유지할 수 있는 요구만을 수락하고,
불안전 상태를 초래할 사용자의 요구는 나중에 만족될 수 있도록 계속 거절
- 사용하는 자료 구조
1. Available : 사용가능한 자원의 수
2. Max : 프로세스 별 최대 자원의 요구
3. Allocation : 현재 프로세스 별 할당되어 있는 자원 수
4. Need : 프로세스 별 남아 있는 자원 요청 수(Max - Allocation)
- 동작 원리
Work = init Available
예를 들어 프로세스 Pi가 자원을 요청했을 때
step 1. 종료가 안된 프로세스 Pi를 찾으면 step 2로 넘어감
만일 모두 종류가 안된 프로세스가 없다면 그 시스템은 safe state상태
step 2. Pi의 Need가 Work 보다 작다면 step 3으로 넘어감
크다면 pass
step 3. 프로세스 Pi에게 자원을 할당해서, 완료시킨 뒤
프로세스 Pi가 가진 자원을 반환
Work = Work + Allocation(Pi)
다시 step 1으로
- 예시
자원 A는 10개, 자원 B는 5개, 자원 C는 7개가 있다고 가정
즉, 안정 순열(p1,p3,p4,p0,p2) 순으로 자원을 할당해 안정상태 유지
- 은행원 알고리즘의 단점 : 알고리즘이 너무 복잡,
프로세스가 가지고 있어야 할 자원의 최대 개수를 미리 알아야함.
③ 교착상태 탐지(detection) 및 복구(recovery) :
- 이미 발생한 교착상태를 탐지알고리즘이나 자원할당그래프, 대기 그래프의 사이클 유무에 따라 찾아낸 후 복구하는 방법
탐지 알고리즘? Banker’s algorithm의 변형 알고리즘 활용
- 사용하는 자료구조
ⓐ Available : 사용가능한 자원의 수
ⓑ Allocation : 현재 프로세스 별 할당되어 있는 자원 수
ⓒ Request : 각 프로세스가 현재 요청 중인 자원 수
- 동작 원리
(탐지알고리즘은 은행원 알고리즘과 마찬가지로 내용이 달라지는 자료구조를 사용한다.
다른 점은, 은행원 알고리즘의 Max와 Need과 Request로 바뀐 것)
- 예제 1)
이 예제에서는 현재 상황에서 Available 값이 모두 0이지만
P(0)가 아무 자원도 요청하지 않기 때문에 작업을 끝내면 자원을 반납하고
반납한 자원으로 P(2)에게 할당하면서 Safe State Sequence(p0,p2,0p3,p4,p1)를 만들어낼 수 있어서
현재 이 상태는 Deadlock에 빠져 있지 않은 상태임을 탐지
- 예제 2)
예제 1과 달리 P2가 자원 C를 하나 요청했을때
P(0)가 자원을 반납하더라도 P(2)의 현재 요청 자원이 바뀜으로 인해
현재 아무 프로세스에게도 자원을 할당해줄 수 없으므로
P(1), P(2) ,P(3) ,P(4)는 Deadlock에 빠져 있는 프로세스라고 판단 -> 교착상태에 빠져있음을 탐지
- 탐지한 교착상태 복구(recovery) 방법
ⓐ 프로세스 종료 : 교착 상태 프로세스를 모두 종료하거나 희생 프로세스를 정해서 종료
ⓑ 자원선점 : 교착상태의 프로세스로부터 자원을 선점
- Deadlock detection은 지속해서 현재 상태를 검사하며 또한 프로세스를 종료시킨 후 다시 시작해야 하는 등
많은 비용이 들기 때문에 비효율적이라 판단되어 현재 다수의 시스템에서는 사용 되지 않고 있다.