Deadlock

사진 한 장으로 deadlock을 표현해보자.

Deadlock의 개념

Blocked/Asleep state

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

Deadlock state

-프로세스가 발생 가능성이 없는 이벤트를 기다리는 경우
-시스템 내에 deadlock에 빠진 프로세스가 있는 경우

starvation vs deadlock

starvation은 cpu를 기다리는 상태, 운이 없어서 오래 기다릴 뿐 언제가는 진행될 확률이 있다.
반면, deadlock은 죽었다 깨나도 실행이 안된다.

자원의 분류

deadlock은 자원과 밀접한 관련이 있다.
자원의 분류에 대해 먼저 알아보자.

일반적 분류

Hardware resources vs Software resources

다른 분류법

-선점 가능 여부에 따른 분류
-할당 단위에 따른 분류
-동시 사용 가능 여부에 따른 분류
-재사용 가능 여부에 따른 분류

선점 가능 여부에 따른 분류

1.Preemptible resources
-선점 당한 후 돌아와도 문제 없는 자원
예)Processor, memory

2.Non-preemptible resources
-선점 당하면, 이후 진행에 문제 생기는 자원
-예. disk drive(데이터 이전 중 usb뽑아버리면 다 날라감)

할당 단위에 따른 분류

1.Total allocation resources
-자원 전체를 프로세스에게 할당
-ex)Processor, disk drive

2.Partitioned allocation resources
-하나의 자원을 여러 프로세스들에게 할당
-ex>Memory

동시 사용 가능 여부에 따른 분류

1.Exclusive aloocation resources
-한 순간에 한 프로세스만 사용 가능한 자원
-ex)Processor, memory, disk drive 등

2.Shared allocation resource
ex)Program(sw), shared data. 엑셀 파일 동시에 여러 창 띄울 수 있는게 예시

재사용 가능 여부에 따른 분류

1.SR(Serially-reusable Resources)
-시스템 내에 항상 존재하는 자원
-사용이 끝나면 다른 프로세스가 사용 가능
ex)Processor, memory, disk drive, program

2.CR(Consumable Resources)
-한 프로세스가 사용한 후에 사라지는 자원
-ex)signal, message

Deadlock을 발생시킬 수 있는 자원의 형태

Non-preemptible resources

Exclusive allocation resources

Serially reusable resources와 CR은 둘 다 deadlock발생시킬 수 있으나, 너무 복작하니 재끼자.
그리고 할당 단위는 deadlock에 영향 안끼친다.

Deadlock Model

deadlock 발생 예시

deadlock model(표현법)

에는 두개가 있다.
Graph Model, State Transition Model

graph model을 먼저 보자. 아래 그림은 위의 데드락 상태를 표현한 것이다.

State Transition Model

위 그림은 processor1개 일떄 상황이고, 2개가 되면 5x5가 될 수 있다.
그걸 표현한 것이 아래 그림이다.

deadlock 발생 필요 조건

아래 4개 모두 충족해야 된다.
위 2개는 자원의 특성, 아래 2개는 프로세스의 특성이다.

-exclusive use of resources
-Non-preemptible resources
-Hold and wait(Partial allocation). 자원을 하나 hold하고 다른 자원 요청
-Circular wait

Deadlock Prevention (3번째 강의)

deadlock발생요건 4가지 중 하나라도 제거하면, deadlock은 발생 안한다.
지금부터 보는 내용은 다 그걸 구현하는 것들.

deadlock 해결방법

1. deadlcok prevention methods
   -교착상태 예방
2. deadlock avoidance method
   -교착상태 회피
3. deadlock detection and deadlock recovery methods
   -교착상태 탐지 및 복구

deadlcok prevention methods

4개 조건 중 하나를 제거->deadlock절대 발생 안함.
그럼 하나씩 없애봅시다.

1. 모든 자원을 공유 허용

-exclusive use of resources조건 제거
-현실적으로 불가능. ㅂㅇ

2. 모든 자원에 대해 선점 허용

-Non-preemptible resouces조건 제거
-현실적으로 불가능
-유사한 방법이 하나 있긴 하다.
프로세스가 할당 받을 수 없는 자원을 요청한 경우, 기존에 가지고 있던 자원 전부 반납하고 작업 취소하기. 이 후엔 처음부터 다시 시작. 이건 심각한 자원 낭비를 발생시킨다.->비현실적

3. 필요한 자원 한번에 모두 할당(Total allocation)

-Hold and wait조건 제거
-끝날 때 까지 절대 반납 안함
-자원 낭비 발생(필요하지 않은 순간에도 가지고 있음)
-무한 대기 현상 발생 가능

4. Circular wait조건 제거

-Totally allocation을 일반화 한 방법
-자원들에게 순서 부여
-프로세스는 순서의 증가 방향으로만 자원 요청 가능
-자원 낭비 발생

deadlock prevention결론

-4개 데드락 필요조건 하나를 제거
-데드락 절대 발생 안함
-심각한 자원낭비
-한 마디로 비현실적이다.

Deadlock avoidance

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

safe state

-모든 프로세스가 정상적 종료 가능한 상태(safe sequence가 존재)

unsafe state

-Deadlock상태 될 가능성 있음(반드시 발생한다는 의미x)

deadlock avoidence하는 방법을 구체적으로 알아보자.

가정

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

4번째 가정은 당연하지만 나머지 3개를 고려했을 떄, 이 방법은 not practical.
여하튼, deadlock avoidence알고리즘은 2개다.
1. Dijkstra's algorithm :"Banker's lagorithm"
2. Habermann's algorithm

Dijkstra's Banker's lagorithm

-deadlock avoidance를 위한 간단한 이론적 기법.
-가정: 한 종류(resource type)의 자원이 여러 개(unit)
-시스템을 항상 safe state로 유지

safe state example

unsafe state example

Harbermann's algorithm

-다익스트라 버전 확장
-여러 종류의 자원 고려
Multiple resource types
Multiple resource units for each resource type
-시스템을 항상 safe state로 유지

(강사님 말에 의하면 엄청 쉬움)

deadlock avoidance 결론

1.deadlock 발생 막을 수 있음
2.High overhead
항상 시스템을 감시하고 있어야 하기 때문에.

3.low resouce utilization
-safe state유지를 위해, 사용되지 않는 자원 존재

not practical
-프로세스 수, 자원 수 고정, 필요한 최대 자원 알고있다는 가정 자체가 실용적이지 않다.

Deadlock detection and deadlock recovery methods

이 방법은 데드락 방지 위한 사전작업 안한다.
그냥 발생하게 놔둔다.
발생 하면 그때서 후속조치 취하는 방법.
해서, 주기적으로 deadlock발생 확인한다.
구체적으론, 시스템이 데드락 상태인지, 만약 그렇다면 어떤 프로세스가 데드락 상태인지.
이를 Resoucrce Allocation Grpah(RAG)를 사용하여 감시한다.

아래 사진을 보자.
bipartite graph는 단방향만 가능한 그래프를 의미한다.

N은 노드, E는 Edge.
N = {Np, Nr}에서 p는 프로세스, r은 자원을 의미한다. 즉, N은 프로세스 노드와 자원 노드의 집합이다.

화살표 방향에 따라 의미가 달라진다. 요청, 할당

t는 자원 숫자 의미한다. 절대값 a,b요건 뭐냐면, (a,b) a에서 b로가는 edge의 수를 의미한다.

아래 그림을 뜯어보고, 데드락 상태인지를 맞춰봐라. 헷갈린다.

데드락 판단하는 방법이 따로 있다.

Graph reduction

-주어진 RAG에서 edge를 하나씩 지워가는 방법.

completyle reduced
-모든 edge가 제거 됨
-deadlock에 빠진 프로세스가 없음

Irreducible
-지울 수 없는 edge가 존재
-하나 이상의 프로세스가 deadlock상태

graph reduction을 이제 실제로 자세히 들여다보자.

Unblocked process

edge가 남았다는 것은, 자원 할당 못받은 프로세스가 있다는 뜻이다. 즉 데드락 발생.

아래는 에지 지우는 그림. 먼저 자원 다 충당받은 애가 그걸 반납하고, 뒤에 기다리던 애가 그걸 가져다 쓴다.
이렇게 해서 문제 없이 모두 지워지면 노 데드락.
아래 사진은 데드락이 없는, 엣지가 모두 지워진 상황.

아래 예시는 데드락 발생

데드락 디텍션 정리

Deadlock avoidance vs Detection

deadlock avoidance

-최악의 경우를 생각(앞으로 일어날 일 고려)
-deadlock이 발생 x

deadlock detection

-최선의 경우를 생각(현재 상태만 고려)
-deadlock발생 시 recovery 과정 필요.
이제부터 그 recovery방법 알아보자.

deadlock recovery

데드락 검출 후 해결하는 과정
방법은 2개
1.process termination
2.resource preemption
3. checkpoint-restart method

process termination

-데드락 상태의 프로세스 강종.
-데드락 상태인 프로세스 중 일부 종료
-강종된 프로세스는 이후 재시작

종료시킬 때 Termination cost model을 기준으로 종료시킬 프로세스 선택한다.
1.termination cost
-우선순위/process priority
-종류/process type
-총 수행 시간/accumulated execution time of the process
-남은 수행 시간/remaining time of the process
-종료 비용/accunting cost

이 중에 두개만 알아보자
lowest-termination cost process first
simple, low overhead, but 불필요한 프로세스들이 종료 될 가능성이 있음
(한 바퀴 돌면서 비용 낮은 애 죽임)

Minimum coast recovery
-최소 비용으로 데드락 상태 해소할 수 있는 프로세스 선택해서 죽임
-모든 경우의 수 고려해야됨
-복잡, high overhead

resource preemption

-데드락 상태 해결 위해 선점할 자원 선택
-선정되 ㄴ자원 가지고 있는 프로세스에서 자원 뻇기(뺏긴 프로세스는 강종됨)
-데드락 상태 해결 위해 선점할 자원 선택
-해당 자원 가지고 있는 프로세스 죽임(근데 죽은 프로세스는 데드락 상태 아닐 수도 있음...억울쓰, 해당 프로세스는 이후 재시작됨)
얘도 마찬가지로 preemption cost model, Minimum cost recovery method사용

checkpoint-restart method

세이브 한 지점으로 롤백