Deadlock (교착상태)
- 자신이 가진 자원을 내놓지는 않으면서 다른 Process의 자원을 기다리는 ...
Deadlock 발생의 4가지 조건
Mutual Exclusion
매순간 하나의 프로세스만이 자원을 사용할 수 있음
No Preemption
프로세스는 자원을 스스로 내놓을 뿐, 강제로 빼앗기지는 않음
Hold and Wait
자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있음
Circular wait
자원을 기다리는 프로세스 간에 사이클이 형성되어야 함
자원 할당 그래프
- 그래프에 Cycle 없으면 Deadlock 아니다.
- 그래프에 Cycle 있으면
- 자원이 하나씩 있으면 Deadlock
- 자원이 여러 개 있으면 Deadlock 가능성 있음.
Deadlock 처리 방법
Deadlock Prevention
자원 할당 시 위 Deadlock 필요 조건 4가지 중 하나가 만족되지 않게끔 하는 것
- Mutual Exclusion (이건 어쩔 수 없음. 공유 자원이라)
- Hold and Wait
- 프로세스 시작 시 모든 필요 자원을 한번에 할당 받게끔
- 자원이 필요할 경우 보유 자원을 모두 놓고 다시 요청
- No Preemption
- process가 어떤 자원을 기다려야 하는 경우 이미 보유한 자원을 빼앗음
- 모든 필요한 자원을 얻을 수 있을 때 그 프로세스는 다시 시작된다.
- State를 쉽게 save하고 restore 할 수 있는 자원에서 주로 사용 (CPU, memory)
- Circular Wait
- 모든 자원 유형에 할당 순서를 정하여 정해진 순서대로 자원 할당
- 자원 B를 얻기 위해서는 A를 먼저 얻어야 ...
=> 효율성 저하, 처리량 감소, Starvation 발생 가능
Deadlock Avoidance
Deadlock 발생을 미연에 방지
- Banker's Algorithm
Cycle이 생길 것 같으면 자원을 아예 할당하지 않음.
가용 자원 >= 요구 자원인 경우에만 자원 할당
즉, 자원 할당 시 프로세스를 종료해서 다시 자원 반환이 확실한 경우에만 자원을 할당함. 항상 Deadlock에 대해 Safe 보장
지나치게 안전 -> 자원 비효율 발생
Deadlock Detection and recovery
일단 Deadlock 신경 안쓰고 자원 할당하고 이후 조치.
Deadlock 발생 가능 해도 가용 자원이 있으면 일단 자원을 할당함.
Deadlock 감지 시
- 자원을 요청하지 않은(종료 가능한) 프로세스가 자원을 반환하기를 기다림 : 자원 반환 후 다른 프로세스에 자원 재분배
- 모든 프로세스가 자원을 요청 시 : Deadlock 발생
해결책Process Preemption
- 모든 프로세스 전부 종료
- Deadlock 해결 가능까지 Process 하나씩 종료
Resource Preemption
- 프로세스가 자원을 빼앗을 수 있도록 프로세스 간우선순위 선정
- 비용을 최소화할 victim을 선정
- safe state로 rollback해서 process restart
- cost factor에 rollback 횟수도 같이 고려
Deadlock Ignorance
Deadlock을 고려하고 해결하려 하는 것 자체가 일종의 Overhead임.
Deadlock이 발생하는 것이 매우 드문 Case이기 때문.
Deadlock에 대해 고려하지 않고 자원 할당하다가 Deadlock 발생한다고 사용자가 느낄 때 직접 종료하게 끔...
Unix, Windows 등의 대부분 범용 OS가 채택
