쓰레드(or 프로세스)가 요청한 리소스가 다른 쓰레드(or 프로세스)에 점유되어 있고 다른 쓰레드 또한 리소스를 기다리는 상태를 변경할 수 없는 상황
최소한 하나의 자원은 비공유 모드로 점유되어야한다
쓰레드는 최소한 하나의 자원을 소유한 상태에서 다른 쓰레드에 점유된 리소스를 추가로 얻기 위해 대기해야 한다
리소스는 선점할 수 없어야 한다
대기하는 쓰레드는 의존성 그래프가 원형 상태여야 한다
그래프가 사이클을 포함하지 않으면 데드락이 아니다. 그래프가 사이클을 포함하면 데드락 일수도 있고 아닐 수도 있다. 사이클에서 리소스 인스턴스가 정확하게 하나의 인스턴스만 가지면 데드락이다. 사이클이 존재할 때 리소스 인스턴스가 여러개이면 반드시 데드락이 발생한다는 것은 아니다.
데드락 필수 조건 4가지 중 최소한 하나라도 발생하지 않도록 방지한다
Mutual Exclusion -> 불가능
Hold and wait -> 불가능
No preemption -> 불가능
Circular wait -> 가능
디바이스 효율을 떨어뜨리고 시스템 처리율을 줄인다
특정한 순서로 각각의 쓰레드에게 쓰레드가 필요로 하는 리소스를 할당할 수 있을때 데드락을 회피할 수 있다.
safe sequence
라고 하고, safe sequence
가 존재할 때 safe state
라고 한다safe state
일 때는 데드락이 발생하지 않는다.unsafe state
일 때는 데드락이 발생할 수 도 있다.safe state
임을 보장하면 된다자원 인스턴스가 1개일 때는 RAG 그래프에서 claim edge(쓰레드의 미래 요청)를 그래프에 추가하여 Cycle Detection을 통해 데드락을 회피한다.
RAG는 리소스의 인스턴스가 여러개일 경우 데드락 회피에 적용할 수 없다
리소스의 인스턴스가 여러개일 경우 Banker's 알고리즘을 적용한다
Available
= 가용한 자원 타입 개수 벡터
Available[j]==k
= R(j)의 K개 인스턴스가 사용가능하다Max
= 각각의 쓰레드의 맥시멈 요청 행렬
Max[i][j]==k
= T(i)는 R(j)의 최대 k개 인스턴스가 필요하다Allocation
= 현재 각각의 쓰레드에게 할당된 리소스 개수 행렬
Allocation[i][j]==k
= T(i)는 현재 R(j)의 K개 인스턴스를 할당받았다Need
= 각각의 쓰레드에게 필요한 리소스 개수 행렬
Need[i][j]==k
= T(i)는 현재 R(j)의 K개 인스턴스를 필요로 하다시스템 스냅샷이 safe한지 아닌지 판별하는 알고리즘
Work
벡터 = AvailableFinish[n]
벡터 = false (n=쓰레드)i
Finishi[i]==false
Need(i)<=Work
Work
Work = Work + Allocation(i)
Finishi[i]=true
Finish[i] == true
for all i새로운 리소스 요청이 들어왔을 때 시스템 스냅샷이 safe한지 아닌지 판별하는 알고리즘
Request(i) <= Need(i)
Request(i) <= Available(i)
Available = Available - Request(i)
Allocation(i) = Allocation(i) + Request(i)
Need(i) = Need(i) - Request(i)
Wait-for-graph를 유지하고, 주기적으로 싸이클을 확인한다
Wait-for-graph
RAG에서 리소스를 제외한 Dependency graph
banker's 알고리즘과 비슷하게 수행한다.
Process and Thread Termination
Resource Preemption