Deadlock
일련의 프로세스들이 서로가 가진 자원을 기다리며 block된 상태
프로세스가 자원을 사용하는 절차
1.request, 2. Allocate 3.Use 4.Release
1. Deadlock 발생의 4가지 조건
1) Mutal exclusion (상호 배제)
매 순간 하나의 프로세스만이 자원을 사용할 수 있음
2) No preemption (비선점)
프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않음
3) Hold and wait (보유대기)
자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있음
4) Circular wait (순환대기)
자원을 기다리는 프로세스간에 사이클이 형성되어야 함
- 자원할당 그래프
자원에서 프로세스로 가는 화살표 (이 자원이 해당 프로세스에게 할당되어있다.)
프로세스에서 자원으로 가는 화살표 (이 자원을 요청했는데 아직 할당 못받음 )
그래프에 Cycle이 없으면 Deadlock이 아니다.
있으면 ?
1> 한자원 당 instance가 하나다 ? -> deadlock
2> 하나가 아니면? -> deadlock일수도 아닐수도
2. Deadlock의 처리 방법
1) Deadlock Prevention
2) Deadlock Avoidance
3) Deadlock Detection and recovery
4) Deadlock Ignorance <현대 OS>
- Deadlock을 시스템이 책임지지 않음
- UNIX를 포함한 대부분의 OS가 채택
- Deadlock은 자주 발생하는 것이 아니라서 미연에 방지하는 것이 효율적이지 못하다.
1) Deadlock Prevention
4가지 Deadlock 발생 조건중 하나를 원천적으로 차단하여 Deadlock을 방지하는 방법
Hold and wait을 해결하는 방법
-> 프로세스가 시작될 때 필요한 모든 자원을 할당받게 하는 방법
No Preemption
- 빼앗아 올 수 있게 한다.
Circular wait
- 모든 자원 유형에 할당 순서를 정하여 정해진 순서대로만 자원 할당
2) Deadlock Avoidance
자원 요청의 부가적인 정보를 이용해서 deadlock의 가능성이 없는 경우에만 자원을 할당
점선 화살표 : 이 프로세스가 평생에 적어도 한번은 이 자원을 요청할 것이다.
"Safe"
3) Deadlock Detection and Recovery
사이클이 있는지 찾는 것은 O(n^2)
깊이 우선 탐색
Recovery
1. Process termination
2. Resource Preempation
