Deadlock의 개념

Blocked/Asleep State
프로세스가 특정 이벤트를 기다리는 상태
프로세스가 필요한 자원을 기다리는 상태

Deadlock state
프로세스가 발생 가능성이 없는 이벤트를 기다리는 경우
시스템 내에 deadlock에 빠진 프로세스가 있는 경우
=> 가능성 zero
starvation => 운이 없어서

자원의 분류
일반적 분류
Hardware resources vs Software resources

다른 분류
선점 가능 여부에 따른 분류
Preemptible resources 선점 당한 후, 돌아와도 문제가 발생하지 않는 자원 - processor, memory  
Non-preemptible resources 선점 당하면, 이후 진행에 문제가 발생하는 자원 - disk drive

할당 단위에 따른 분류
Total allocation resources  자원 전체를 프로세스에게 할당 Processor, disk drive
partitoned allocation resources 하나의 자원을 여러 조각으로 나누어, 여러 프로세스들에게 할당 Memory

동시 사용 가능 여부
Exclusibe allocation resources 한 순간에 한 프로세스만 사용 가능한 자원
Shared allocation resources 여러 프로세스가 동시에 사용 가능한 자원

재사용 가능 여부
SR (Serially-reusable resources) 시스템 내에 항상 존재 하는 자원 Processor, memory, disk
CR (Consumable Resources) 한 프로세스가 사용한 후에 사라지는 자원 signal, message

Deadlock을 발생시킬 수 있는 자원의 형태
Non-preemptible resources
Exclusibe allocation resources
Serially reusable resources

CR을 대상으로 하는 Deadlock model이 있지만 복잡

Deadlock 발생의 예
2개의 프로세스 (P1,P2)
2개의 자원 (R1,R2)

Deadlock Model
Graph Model

State Transition Model

Deadlock 발생 필요 조건
자원의 특성        - Exclusive use of resources, Non-preemptible resources
프로세스의 특성   - Hold and wait (partial allocation), Circular wait



Deadlock Prevention


4개의 deadlock 발생 필요 조건 중 하나를 제거
deadlock이 절대 발생하지 않음, 심각한 자원 낭비 발생

- 모든 자원을 공유 허용 , 현실적 불가능
- 모든 자원에 대해 선점 허용 , 현실적 불가능
- 필요 자원 한번에 모두 할당 , 무한 대기 현상 발생 가능
- Circular wait 조건 제거 , 프로세스는 순서의 증가 방향으로만 자원 요청 가능 자원 낭비 발생

Deadlock avoidance

시스템의 상태를 계속 감시
시스템이 deadlock 상태가 될 가능성이 있는 자원 할당 요청 보류
시스템을 항상 safe state로 유지

Safe state
모든 프로세스가 정상적 종료 가능한 상태
Safe sequence가 존재 찾을 수 있으면 safe state

Unsafe state
deadlock 상태가 될 가능성이 있음

가정
프로세스의 수가 고정됨
자원의 종류와 수가 고정됨
프로세스가 요구하는 자원 및 최대 수량을 알고 있음
프로세스는 자원을 사용 후 반드시 반납한다.

avoidance algorithm

Dijkstra's algorithm - banker's algorithm
시스템을 safe state로 유지하는 알고리즘

자원을 주었다고 가정해보고 safe sequence가 있다면 빌려주고 없다면 안 빌려준다.

Habermann's algorithm
dijkstra's의 확장

High overhead - 항상 시스템을 감시하고 있어야 한다.
Low resource utilization - safe state 유지를 위해, 사용 되지 않는 자원이 존재
not practical - 프로세스 수, 자원 수가 고정, 필요한 최대 자원 수를 알고 있음

Deadlock Detection

Deadlock 방지를 위한 사전 작업을 하지 않음
주기적으로 deadlock 발생 확인 - 시스템이 deadlock 상태인가?, 어떤 프로세스가 deadlock 상태인가?

Resource Allocation Graph(RAG) 사용
- Directed, bipartite Graph

Graph reduction을 이용해서 deadlock을 확인
주어진 RAG에서 edge를 하나씩 지워가는 방법

completely reduced - 모든 edge가 제거 됨 ~ deadlock에 빠진 프로세스가 없음
Irreducible - 지울 수 없는 edge가 존재 ~ 하나 이상의 프로세스가 deadlock 상태
Unblocked process
필요한 자원을 모두 할당 받을 수 있는 프로세스를 지운다.

high overhead - 검사 주기에 영향을 받음, node의 수가 많은 경우


Deadlock Recovery
process termination
: deadlock 상태인 프로세스 중 일부 종료
termination cost model - 누구를 종료할지 (우선순위, 종류, 총 수행 시간, 남은 수행 시간, 종료 비용)

Resource preemption
: deadlock 상태 해결을 위해 선점할 자원 선택
해당 자원을 가지고 있는 프로세스를 종료 시킴
deadlock 상태가 아닌 프로세스가 종료 될 수 있음

Checkpoint-restart method
프로세스의 수행 중 특정 지점마다 context를 저장,
Rodllback을 위해 사용 - 프로세스 강제 종료 후, 가장 최근의 checkpoint에서 재시작

+ Recent posts