Deadlock state
프로세가 발생 가능성이 없는 이벤트를 기다리는 경우 프로세스가 deadlock 상태에 있음
시스템 내에 deadlock에 빠진 프로세스가 있는 경우 시스템이 deadlock 상태
※ starvation vs deadlock starvation은 프로세스 상태로 따지면 ready에서 계속 대기중인 상태
deadlock은 프로세스 상태가 block(asleep)으로 transition이 불가능한 상태
※ 자원의 분류(Deadlock 관점)
- 선점 가능 여부
- Preemptible resources : 선점당한 후 돌아와도 문제가 발생하지 않는 자원(cpu(context switching), memory(swap-device))
- Non-preemptible resources : 선점 당하면 이후 진행에 문제가 발생하는 자원(disk, device)
- 할당 단위에 따른 분류
- Total allocation resources : 자원 전체를 프로세스에게 할당(processor)
- Partitioned allocation resources : 하나의 자원을 여러 조각으로 나누어 프로세스에게 할당(memory)
- 동시 사용 가능 여부
- Exclusive allocation resources : 한 순간에 한 프로세스만 사용 가능 자원(Processor, memory, disk drive)
- Shared allocation resources : 여러 프로세스가 동시에 사용 가능 자원(Program(ex.한글, excel등), shared data)
- 재사용 가능 여부
- SR(Serially-reusable Resources) : 시스템 내에 항상 존재, 사용이 끝나면 다른 프로세스가 사용 가능(Processor, memory, program)
- CR(Consumable Resources) : 한 프로세스가 사용 후 사라지는 자원(signal, message)
Deadlock을 발생시킬 수 있는 자원 상태
- Non-preemptible resources
- Exclusive allocation resources
- SR(Serailly reusable resources)
※ CR(Consumable resources)을 대상으로 하는 Deadlock model 은 우선 제외
Deadlock 발생 필요조건
< 자원의 특성 >
- 상호배제 (Exclusive use of resources)
- 비선점 (Non-preemptible resources)
< 프로세스의 특성 >
- 점유와 대기 (Hold and wiat(Partial allocation)) : 자원을 하나 Hold하고 다른 자원을 요청
- 순환대기(Circular wait)
Deadlock 해결 방법
1. 교착상태 예방(Deadlock prevention methods)
Deadlock 발생 필요조건 4가지 중 하나를 제거
- 상호배제 -> 모든 자원을 공유 허용(현실적으로 불가능)
- 비선점 -> 모든 자원애 대해 선점 허용(현실적으로 불가능)
- 점유와 대기 -> 필요자원 한번에 모두 할당(자원 낭비 발생, 무한 대기 현상 발생가능)
- 순환대기 -> 자원들에게 순서를 부여, 프로세스는 순서의 증가방향으로만 자원 요청 가능(자원낭비 발생)
=> 심각한 자원 낭비 발생, 비현실적
2. 교착상태 회피(Deadlock avoidance methods)
시스템의 상태를 계속 감지(-> High overhead)
deadlock 상태가 될 가능성이 있는 자원할당 요청 보류하며 시스템을 항상 safe state로 유지
※ safe state : 모든 프로세스가 정상적으로 종료 가능한 상태(Deadlock 상태가 되지 않을 수 있음을 보장)
가정)
- 프로세스 수가 고정됨
- 자원의 종류와 수가 고정됨
- 프로세스가 요구하는 자원 및 최대 수량을 알고 있음
- 프로세스는 자원을 사용 후 반드시 반납
=> 비현실적
이론적 기법)
- Dijkstra’s algorithm(=Banker’s algorithm) :
가정) 한 종류의 자원이 여러개(wait)
safe sequence 존재 여부가 중요(요청이 들어오면 요청에 따른 결과를 시뮬레이션 해봄) - Haberman’s algorithm :
여러 자원을 고려함(Dijkstra’s algorithm 확장)
3. 교착상태 탐지 및 복구(Deadlock detection and recovery methods)
Deadlock Detection
사전 작업 없이 주기적으로 Deadlock 발생 확인
방법)
Resources Allocation Graph(RAG) 사용
Graph reduction : 주어진 RAG에서 edge를 하나씩 지워감
Graph reduction 과정)
- Unlocked process에 연결된 모든 edge를 제거
- 더이상 Unlocked process가 없을 때까지 반복
결과)
Completely reduced : 모든 edge가 제거됨 => deadlock 에 빠진 프로세스가 없음
Irreducible : 지울 수 없는 edge가 존재 => 하나 이상의 프로세스가 deadlock 상태
=> High overhead(검사주기, Node의 수가 많은 경우)
Deadlock Recovery
- Process termination : Deadlock 상태인 프로세스를 일부 종료
➕ Termination cost model (어떤 프로그램을 종료할지)고려사항)
우선순위, 종류, 총 수행시간, 남은 수행시간, 종료비용, …
방법)
Lowest-termination cost process first
Minimum cost recovery(최소 비용으로 교착상태를 해지할 수 있음) - Resources preemption : Dead lock 상태 해결을 위해 선점할 자원을 선택 -> 해당 자원을 가진 프로세스 종료
단점) Deadlock 상태가 아닌 프로세스가 종료될 수 있음
해당 프로세스는 이후 재시작
※ 해결방안 : Checkpoint-restart method ( Rollback을 위해 특정 시점마다 context를 저장)
※ 선점할 자원 선택
Preemption cost model 필요
Minimum cost recovery method 사용