Blocked state : 프로세스가 특정 이벤트를 기다리는 상태
Deadlock state : 프로세스가 발생 가능성이 없는 이벤트를 기다리는 경우
Deadlock vs Starvation
자원의 분류
선점 가능 여부에 따른 분류
preemptible resources : 선점 당한 후, 돌아와도 문제가 발생하지 않는 자원 (processor, memory 등)
non-premptible resources : 선점 당하면, 이후 진행에 문제가 발생하는 자원 (disk drive 등)
할당 단위에 따른 분류
total allocation resources : 자원 전체를 프로세스에 할당 (processor, disk drive 등)
partitioned allocation resources : 하나의 자원을 여러 조각으로 나누어, 여러 프로세스들에게 할당 (memory 등)
동시 사용 가능 여부에 따른 분류
exclusive allocation resources : 한 순간에 한 프로세스만 사용 가능한 자원 (processor, memory, disk dirve 등)
shared allocation resources : 여러 프로세스가 동시에 사용 가능한 자원 (program, shared date 등)
재사용 가능 여부에 따른 분류
SR (serially-reusable resources) : 시스템 내에 항상 존재하는 자원으로, 사용이 끝나면 다른 프로세스가 사용 가능
CR (consumable resources) : 한 프로세스가 사용한 후에 사라지는 자원 (signal, message 등)
Deadlock을 발생시킬 수 있는 자원의 형태
non-preemptible resources
exclusive allocation resources
serially reusable resources
* CR을 대상으로 하는 Deadlock 모델은 너무 복잡
Deadlock Model (표현법)
Graph Model
Node
- 프로세스 노드(P), 자원 노드(R)
Edge
- R → P : 자원 R이 프로세스 P에 할당됨
- P → R : 프로세스 P가 자원 R을 요청(대기 중)
State Transition Model
예) 2개의 프로세스(P1, P2)와 자원 2개 존재, 프로세스는 한번에 자원 하나만 요청/반납 가능
Deadlock 발생 필요 조건
- Exclusive use of resources
- Non-preemptible resources
- Hold and wait (Partial allocation)
- Circular wait
1. Deadlock Prevention
: 자원 낭비 발생, 비현실적
(1). Exclusive use of resources 조건 제거
- 모든 자원을 공유 허용 : 현실적으로 불가능
(2) Non-premptible resources 조건 제거
- 모든 자원에 대해 선점 허용 : 현실적으로 불가능
- 유사한 방법 : 할당 받을 수 없는 자원을 요청한 경우,
- 가지고 있던 자원을 모두 반납하고 작업 취소 : 심각한 자원 낭비 발생
(3) Hold and wait 조건 제거
- 필요 자원을 한번에 모두 할당 (Total allocation)
- 자원 낭비 발생 : 필요하지 않은 순간에도 가지고 있음
- 무한 대기 현상 발생 가능
(4) Circular wait 조건 제거
- 자원들에게 순서를 부여
- 프로세스는 순서의 증가 방향으로만 자원 요청 가능
- 자원 낭비 발생
2. Deadlock avoidance
: 시스템이 deadlock 상태가 될 가능성이 있는 자원 할당 보류
High overhead, Low resource utilization, Not practical
Safe state
- 모든 프로세스가 정상적 종료 가능한 상태
- Safe sequence가 존재 : deadlock 상태가 되지 않을 수 있음을 보장
Unsafe state
- deadlock 상태가 될 가능성이 있음
- 반드시 발생한다는 의미는 아님
(1) Dijkstra's banker's algorithm
- 가정 : 한 종류의 자원이 여러개
- 현재 상태에서 safe sequence가 하나 이상 존재하면 safe state이다
- 프로세스들이 모두 자기 일을 마칠 수 있는 순서가 하나라도 존재하면 safe state
- 자원 요청이 들어왔을 때, 자원을 주었다고 가정해보고, 그 결과
safe sequence가 있으면 : accept, safe sequence가 없으면 : reject
(2) Habermann's algorithm
- dijkstra's algorithm 확장, 여러 종류의 자원 고려
3. Deadlock detection & recovery
Deadlock detection
Resource Allocation Graph (RAG)
- Deadlock 검출을 위해 사용
- Directed, bipartite Graph
Graph reduction
- 주어진 RAG에서 edge를 하나씩 지워나가는 방법
- Completely reduced : 모든 edge가 제거 됨, deadlock에 빠진 프로세스가 없음
- Irreducible : 지울 수 없는 edge가 존재, 하나 이상의 프로세스가 deadlock 상태
Unblocked process에 연결된 edge를 지운다
: 필요한 자원을 모두 할당 받을 수 있는 프로세스
Graph reduction procedure
① Unblocked process에 연결된 모든 edge를 제거
② 더 이상 unblocked process가 없을 때까지 ① 반복
③ 최종 graph에서 모든 edge가 제거되면, 현재 상태에서 deadlock이 없는 것이고
일부 edge가 남는다면 현재 deadlock이 있는 것이다.
Deadlock Recovery
Process termination
- deadlock 상태인 프로세스 중 일부 종료
- termination cost model
Resource preemption
- deadlock 상태 해결 위해 선점할 자원 선택
- 선점된 자원을 가지고 있는 프로세스에서 자원을 빼앗음, 자원을 빼앗긴 프로세스는 강제 종료
- preemption cost model
checkpoint-restart method : checkpoint마다 context 저장, rollback을 위해 사용