Deadlock
Deadlock이란
- Deadlock
일련의 프로세스들이 서로가 가진 자원을 기다리며 block되어 더이상 진행이 될 수 없는 상태.
(한 스레드 집합 내의 모든 스레드가 그 집합 내의 다른 스레드에 의해서만 발생될 수 있는 이벤트를 기다리는 상황)
- 프로세스가 자원을 사용하는 절차
- Request : 자원을 요청하고 다른 프로세스가 사용중이라면 대기한다.
- Allocate : 자원을 받는다.
- Use : 자원 사용
- Release : 자원을 놓아준다.
Deadlock은 모든 자원이 request상태인 것.
Deadlock Characterization
-
DeadLock이 발생하기 위한 4가지 조건
- Mutual Exclusion(상호 배제)
매 순간 하나의 프로세스만이 자원을 사용할 수 있다. - Hold and Wait(보유 대기)
자원을 가진 프로세스가 다른 다원을 기다릴 때, 보유하고 있는 자원을 놓지 않고 계속 가지고있는다. - No Preemptive(비선점)
프로세스는 OS에 의해 강제로 자원을 빼앗기지 않는다. - Circular wait(순환 대기)
자원을 기다리는 프로세스 간 사이클이 형성되어야 한다.
- Mutual Exclusion(상호 배제)
-
Resource Allocation Graph(자원 할당 그래프)
R:자원
P:프로세스
· : 자원(인스턴스)의 개수
자원-> 프로세스 간선은 해당 자원을 프로세스가 보유(Allocate)
프로세스-> 자원 간선은 프로세스가 해당 자원을 요청(Request)
그래프에 cycle이 없다면 deadlock이 아니고, 사이클이 있다면 deadlock이 발생할 필요조건이다.
자원 당 하나의 인스턴스만 있는 경우에는 deadlock이지만 여러 인스턴스가 존재하는 경우에는 deadlock일 수도 있고 아닐수도 있음.
: Circular Wait 조건을 발견하기 위한 목적으로 사용한다.
Method for handling deadlocks
- 교착상태에 빠지지 않도록 예방(Prevention) / 회피(Avoidance)방식 도입
- 교착상태에 빠지게 된다면 탐지(Detection) / 복구(Recovery)방식 도입
- 마치 아무 일도 없던 것처럼 행동(사용자가 처리하도록 유도, 대부분 운영체제가 채택)
Deadlock Prevention
교착상태를 발생하게 하는 4가지 조건 중 적어도 하나가 일어나지 않게 보장함으로써 교착상태를 예방.
-
상호배제(Mutual Exclusion)
Critical Section Problem을 해결하기 위해서는 이 조건은 반드시 만족해야 하므로 공유자원이 존재한다면 이 조건은 만족시킬 수밖에 없다. -
보유대기(Hold and Wait)
프로세스가 자원을 요청할 때 다른 어떤 자원도 가지고 있지 않도록 하여 보유대기조건을 제거한다.
방1)프로세스를 시작할 때 모든 필요한 자원을 할당받게 함 : 동적 요청이 아니므로 실용적이지 않음.
방2)자원이 필요한 경우 보유하고 있던 자원을 모두 반납하고 다시 요청하는 방식(자원을 가지고있지 않을 때만 요청 가능) : Low 자원 utilization, starvation 발생 가능성 존재 -
비선점(No Preemptive)
선점이 가능하도록 하여 비선점조건을 제거한다.
자원 점유중인 스레드(프로세스)가 할당 불가한 자원을 요청하면 현재 점유하고 있는 모든 자원이 선점된다(다른 프로세스,스레드가 사용 요청시 넘겨줌). 스레드,프로세스가 요청중인 새로운 자원을 할당받고, 대기 중 선점되었던 모든 자원을 회복할 때만 다시 시작 가능하다. -
순환대기(Circular Wait)
할당 순서를 정하여 정해진 순서대로만 자원을 할당해 순환대기 조건을 제거한다.
모든 자원 유형에 전체적인 순서를 부여해 각 프로세스가 열거된 순서대로 오름차순으로 자원을 요청하도록 요구.
Deadlock Avoidance
Deadlock이 발생할 가능성이 있는 경우엔 아예 자원을 할당하지 않는 방식. 데드락 발생 가능성 없는 경우만 자원 할당
- Safe Sequence
특정 순서로 프로세스들에게 자원을 할당, 실행 및 종료 작업을 할 때 데드락이 발생하지 않는 순서. - Safe State
안전 상태 : 시스템의 프로세스들이 요청하는 모든 자원을 데드락을 발생시키지 않으면서 차례로 모두에게 할당해줄 수 있는 상태. (safe sequence가 존재하는 상태)
회피 알고리즘은 자원 할당 후에도 시스템이 항상 safe state에 있을 수 있도록 할당을 허용함.
- bankers algorithm)
어떤 자원의 할당을 허용하는지 어결정 전 미리 결정된 자원들의 최대 할당량을 가지고 simulation, safe state에 들 수 있는지 여부를 검사하는 것. 대기중인 다른 프로세스들의 활동에 대한 교착 상태 가능성을 미리 조사하는 것.
| t=t0 | max | allocation | need | available |
|---|---|---|---|---|
| P0 | 10 | 5 | 5 | |
| P1 | 4 | 2 | 2 | |
| P2 | 9 | 2 | 7 |
max:각 프로세스별 최대 자원 요청량
allocation : 현재 프로세스에 할당중인 자원 양
need : 남은 필요한 자원의 양(max-allocation)
처음 시스템이 총 12개의 자원을 가지고 있음 가정.
처음 프로세스에 할당된 자원의 합은 5+2+2로 0개이고 availble은 12-9로 3개이다.
safe sequnce를 찾아보면 P1,P0,P2가 safe sequence에 해당한다.
1. P1에 2개를 할당함으로써 P1이 가지고있던 자원 반환-> available 5
2. P0에 5개를 할당함으로써 P0가 가지고있던 자원 반환-> availble 10
3. P2에게 7개 할당함으로써 P2 max 만족.
-> 모든 프로세스 실행 가능.
정리하자면
현재 가용자원과 각 프로세스들이 작업 완료하기위한 필요 자원 비교해 당장 작업 마칠 수 있는 프로레스부터 자원을 할당, 그 프로세스가 작업을 완료하고 반환하는 자원으로 다시 할당->반환 -> 할당하며 가용자원을 늘려가는 것.
이 때 최대한 자원을 뱉어내도록 할당 해줬는데 최종적으로 availble이 부족하다면 unsafe한 것이다. (allocation들 중 하나를 선택해서 뱉어내게하던 방법들이 필요.)
Deadlock Detection
Allocation, Request, Available 등 시스템에 데드락이 발생했는지 여부를 탐색. bankers algorithm과 유사하게 현재 시스템 자원 할당 상태로 파악. (multiple instance)
자원 할당 그래프를 탐지하는 방법도 존재.(single instance)
Recovery from deadlock
detection된 deadlock을 circular wait을 해결해 deadlock으로부터 recovery하는 방법 사용.
- 프로세스 1개 이상 중단
- 교착상태에 빠진 모든 프로세스를 중단(연산중이던 프로세스들도 중단되어 부분 결과가 옳지 않는 부작용 가능성)
- 프로세스를 하나씩 중단시킬 때 마다 detection하는 방법. (탐지 알고리즘 오버헤드)
- 자원 선점
프로세스에 할당된 자원을 선점해 deadlock해결까지 그 자원을 다른 프로세스에 할당해주는 방법.(victim process선정하여 뺴앗는다)
Deadlock Ignore
데드락은 드물게 발생하므로 데드락에 대한 조치 자체가 overhead가 될 수 있고,
데드락이 발생하는 경우 프로그래머가 직접 process를 죽이는 방법으로 대처. 리눅스, windows등 대부분 OS가 채택하고있다.
