What is deadlock?
- 데드락:
- 둘 이상의 프로세스가 다른 프로세스가 점유하고 있는 자원을 서로 기다릴 때 무한 대기에 빠지는 상황
- 시간이 지나도 안풀림
Deadlock Characterization
데드락이 발생하려면 4가지 조건이 동시에 일어나야한다.
- Mutual exclusion 상호 배제
- 한 번에 프로세스 하나만 해당 자원을 사용할 수 있다
- Hold and wait 점유대기
- 자원을 최소한 하나 보유하고, 다른 프로세스에 할당된 자원을 점유하기 위해 대기하는 프로세스가 존재해야 한다.
- No preemption 비선점
- 이미 할당된 자원을 강제로 빼앗을 수 없다.
- Circular wait 순환 대기
- 대기 프로세스의 집합이 순환 형태로 자원을 대기하고 있어야 한다.
자원 할당 그래프
프로세스가 자원을 요구할 때
- 자원이 프로세스에 할당되었을 때
- 그래프에 사이클이 없으면, 데드락은 없다.
- 그래프에 사이클이 있으면
- 자원 하나당 하나의 인스턴스가 연결되어 있으면, 데드락이다.
- 자원 하나당 여러개의 인스턴스가 연결되어 있으면, 데드락의 가능성이 있다.
Methods for Handling Deadlocks 데드락을 막기 위한 방법
- Prevention 예방
- 시스템이 데드락 상태에 들어가지 못하도록 한다.
- 4개의 조건 중 적어도 하나는 일어나지 않도록 한다.
- Avoidance 회피
- 시스템이 데드락 상태에 들어가지 못하도록 한다.
- 각 프로세스가 자원을 어떻게 활용하는지에 대한 사전 정보가 필요하다.
- Detection and recovery 탐지&복구
- 시스템이 데드락에 들어가는 것을 허용하고 복구한다.
Deadlock Prevention 데드락 예방
- 4개의 조건 중 적어도 하나는 일어나지 않도록 해야한다.
- Mutual Exclusion
- 상호 배제를 만족시키지 않을 수 없음 -> 무조건 만족
- Hold and Wait
- 프로세스가 자원을 요청할 때 다른 어떤 자원도 가지고 있지 않도록 한다.
- No Preemption
- 프로세스가 어떤 자원을 기다려야 하는 경우 보유하고 있던 자원이 선점된다.
- 그리고 모든 필요한 자원을 얻을 수 있을 때 그 프로세스는 다시 시작된다.
- Circular Wait
- 자원을 순환 형태로 대기하지 않도록 일정한 한 쪽 방향으로만 자원을 요구할 수 있도록 한다.
Deadlock Avoidance 데드락 회피
- 데드락 회피 알고리즘
- 프로세스가 사용 가능한 리소스를 요청하면 시스템은 즉각적인 할당이 시스템을 안전한 상태로 유지하는지(데드락에 걸리지 않는지) 판단해야 한다.
- Safe Sequence : 프로세스의 sequence <P1, P2, ..., Pn>이 있을 때, Pi의 자원 요청이 '가용 자원 + 모든 Pj (j < i)의 보유 자원'에 의해 충족되는 경우 sequence를 safe 하다고 말한다.
- Safe state : 시스템 내의 프로세스들에 대한 Safe Sequence가 존재하는 상태
- 자원 할당 그래프에서 할당할 자원을 연결했을 때 사이클이 생기면 자원 할당X
Deadlock Detection & Recovery 데드락 탐지 & 복구
- 시스템이 데드락 상태에 들어가는 것을 허용한다.
- Detection Algorithm
- 그래프에 사이클이 있는지 확인
- Recovery scheme
- Process termination: 교착 상태에 빠진 모든 프로세스를 중단시키는 방법
- Resource preemption: 프로세스에 할당된 자원을 선점해서, 교착 상태를 해결할 때까지 그 자원을 다른 프로세스에 할당해 주는 방법
