Dead Lock (데드락)
정의
•
프로세스가 자원을 얻지 못해서 다음 처리를 하지 못하는 상태
•
'교착 상태'라고도 부름
•
시스템적으로 한정된 자원을 여러 곳에서 사용하려고 할 때 발생
Dead Lock이 일어나는 경우
•
프로세스 1과 2가 자원 1,2를 모두 얻어야 한다고 가정해보자
Thread1 : 첫번째 mutex를 얻음 / 두번째 mutex 대기 중
Thread2 : 두번째 mutex를 얻음 / 첫번째 mutex 대기 중
•
현재 서로 원하는 자원이 상대방에 할당되어 있어서 두 thread는 무한정 wait 상태에 빠짐
→ 이 상태가 바로 Dead Lock
주로 발생하는 경우
•
멀티 프로그래밍 환경에서 한정된 자원을 얻기 위해 서로 경쟁하는 상황 발생
•
한 프로세스가 자원을 요청했을 때, 동시에 그 자원을 사용할 수 없는 상황이 발생할 수 있음.
이때 프로세스는 대기 상태로 돌아감
•
대기 상태로 들어간 프로세스들이 실행 상태로 변경될 수 없을 때 '교착 상태' 발생
Dead Lock 발생 조건
•
4가지 모두 성립해야 Dead Lock 발생 (하나라도 성립하지 않으면 Dead Lock 문제 해결 가능)
1. Mutual Exclusion(상호 배제)
•
자원은 한번에 한 프로세스만 사용할 수 있음
2. Hold and Wait(점유 대기)
•
최소한 하나의 자원을 점유하고 있으면서, 다른 프로세스에 할당되어 사용되고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 존재
•
반대 상황에서는 Dead Lock 발생 안함.
◦
최소한 하나의 자원을 점유하고 있으면서, 다른 프로세스에 할당되어 사용하고 있는 자원을 추가로 요청하거나 대기하지 않음
3. No Preemption(비선점)
•
다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없음
•
해당 자원을 소유한 프로세스가 작업을 완료 후, 자발적으로 release 해야함
4. Circular Wait(순환 대기)
•
프로세스의 집합에서 순환 형태로 자원을 대기하고 있어야 함
Dead Lock 예시
•
Dining Philosophers Problem
◦
5명의 철학자가 스파게티 접시와 함께 원형 테이블에 앉아 있습니다.
◦
모든 철학자는 생각하고 먹는 것을 영원히 반복합니다.
◦
모든 접시 사이에는 포크가 하나만 있습니다.
◦
스파게티를 먹으려면 왼쪽 포크와 오른쪽 포크가 모두 있어야 합니다.
◦
다른 사람들이 내 필요한 포크를 사용하는 동안 철학자는 기다려야 합니다.
각 철학자가 자신의 왼쪽 젓가락을 가지고 있는 동안 오른쪽 젓가락을 기다리고 있다면 어떻게 될까요?
⇒ 기존에 1~3번 조건 만족
1.
각 철학자가 자신의 왼쪽 젓가락을 가지고 있으면서 오른쪽 젓가락 대기 (hold and wait)
2.
점유 중인 다른 젓가락 빼앗을 수 없음 (비선점)
3.
젓가락은 한번에 한 사람만 접근 가능 (상호 배제)
4.
+ 순환 대기 발생 ⇒ 교착상태 발생
Resource-Allocation Graph
•
vertice 세트 V와 edge 세트 E
◦
vertice 세트 V는 2가지 타입으로 분리
▪
T = {T1, T2, …, Tn}, 시스템의 모든 스레드(Thread)로 구성된 집합
▪
R = {R1, R2, …, Rm}, 시스템의 모든 리소스(Resource) 유형으로 구성된 집합
•
request edge(빨강) – 방향성 edge Ti → Rj
◦
Rj에 대해 Ti가 block됨(요청)
•
assignment edge(파랑) – 방향성 edge Rj → Ti
◦
Rj는 Ti에 할당됨(할당)
•
Circle: Process
•
Rectangle: Resource
•
unblocked process(thread)
◦
필요한 모든 자원을 할당 받을 수 있는 프로세스
◦
요청 수(request edge num) ≤ 할당되는 남은 자원 수(assignment edge num)
•
사이클 = 순환 대기
•
사이클 없음
⇒ 교착 상태(dead lock) 없음
•
사이클 있음
◦
하나의 인스턴스 리소스 유형
▪
교착 상태(데드락)
예) 순환 대기가 존재합니다.
그리고 T1, T2, T3를 끝낼 방법이 없습니다.
교착 상태가 발생
◦
여러 인스턴스
▪
데드락 가능성 존재
순환 대기가 존재합니다.
그러나 가능한 시나리오:
•
완료 순서는 T4, T3, T2 및 T1입니다.
현재 아직 교착 상태가 아니다
Dead Lock 처리 방법
해당 시스템이 교착 상태로 진입하지 못하는 것을 보장한다. (3가지 방법)
1. Prevention (예방)
•
교착 상태 발생 조건 중 하나를 제거하면서 해결한다. (자원 낭비가 심함)
◦
상호배제(Mutual Exclusion) 부정
▪
여러 프로세스가 공유 자원을 사용
◦
점유대기(Hold and Wait) 부정
▪
프로세스 실행 전 모든 필요한 자원을 할당 (자원 요청 시, 다른 자원을 가지고 있으면 안됨)
▪
낮은 자원 활용성, 기아상태 발생 가능
◦
비선점(No Preemption) 부정
▪
자원 점유 중인 프로세스가 즉시 사용 못하는 다른 자원을 요구할 때, 가진 자원 반납
◦
순환 대기(Circular Wait) 부정
▪
자원에 고유번호 할당 후 순서(낮은 번호)대로 자원 이 할당 됨
•
[ex] A = 1, B = 2, C = 3; // id numbers for resources
– Lock(A) → Lock(C) is OK!
– Lock(C) → Lock(B) is not possible!
◦
Must be Lock(B) → Lock(C) // pre-allocation of B
▪
낮은 자원 활용성, 유연하지 못한 프로세스 절차, 번호 할당의 모호함
2. Avoidance (회피)
•
교착 상태 발생 시, 피해나가는 방법
•
cricular wait를 무효화하는 방법
자원의 상태(state)를 판단하여 할당할지 안 할지를 판단한다. 이때 상태라고 함은 3가지 상태를 판단한다.
1. the number of available ( 사용 가능한 자원의 수 )
2. allocated resources ( 할당된 자원의 수 )
3. the maximum demands of the processes ( 프로세스가 요구한 최대 자원의 수 )
•
Avoidance = unsafe state에 진입하지 않도록 하는 것 (safe state에 머무르는 것)
safe state : 모든 프로세스가 요청하는 최대 자원을 교착 상태를 야기시키지 않고,
차례대로 모두 할당해 줄 수 있는 상태 ⇒
프로세스의 동작 순서(safe sequence)를 정해서 cricular wait를 만들지 않는 상태
unsafe state : 모든 프로세스를 완료하는 프로세스 시퀀스가 없는 상태
◦
할당된 리소스의 수가 증가함에 따라 unsafe state의 확률이 증가합니다.
◦
unsafe state는 항상 데드락을 초래하지는 않습니다.
▪
프로세스가 최대 요청 값(max request)을 요청할 때만 교착 상태가 발생할 수 있습니다.
▪
cricular wait을 만들더라고 Deadlock이 아닌 상태가 있지만 여기선 cricular wait를 만든다면 무조건 safe state라고 판단하지 않는다.
•
Single instance of a resource type (1 Resource Type Case)
◦
자원 할당 그래프 사용
◦
Claim edge : 쓰레드(프로세스) i가 당장 자원이 필요하지 않지만 가까운 미래에 요청할 것 (검은 점선)
◦
claim edge를 할당해서 safety 상태를 확인 가능
▪
방향성 그래프에서 cycle-detection 알고리즘을 적용
▪
할당 후 사이클이 발생하면 unsafe 상태 (데드락 발생 가능 상태)
•
claim edge grant해주어도 됨
▪
사이클이 발생하지 않으면 safe 상태
정리하면 자원을 할당할 때 Claim edge도 고려하여 할당
◦
claim edge 추가 후 사이클 발생 X
▪
데드락 발생 X
◦
자원 요청 하였을 때, cycle 존재 시 → Dead Lock 발생 가능
▪
P2의 자원 요청, 할당이 끝난 이후 P1의 자원 요청, 할당을 진행
▪
P2가 R2의 자원을 할당받는 것을 막아주는 것이 피할 수 있는 방법이 된다
•
Multiple instances of a resource type
◦
Banker's Algorithm (은행원 알고리즘) 사용
◦
은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는데서 유래함
◦
프로세스가 자원을 요구할 때, 시스템은 자원을 할당한 후에도 safe state로 남아있게 되는지 사전에 검사하여 교착 상태 회피 (프로세스의 상환 능력까지 검토)
▪
스레드의 개수 : n
▪
리소스 타입의 개수 : m
▪
프로세스와 자원 정보를 matrix 형태로 표시
Availlable : 사용 가능한 자원의 수
Max : 프로세스가 요청한 최대 자원 수
Allocation : 이미 할당된 자원의 수
Need : 필요한 자원의 수 (Max - Allocation)
▪
safety algorithm
•
2번의 조건을 만족하는 인덱스 i를 찾은 후 3번 과정에 맞춰서 work vector 갱신
◦
초록 : work vector
•
finish 리스트의 인덱스가 모두 True가 될 때까지 work vector 갱신
•
T1 → T3 → T4 → T0 → T2 순서로 진행하게 되면 Thread safety state가 보장이 된다. (T0과 T2는 순서가 바뀌어도 문제가 없다)
•
현재 스레드 safety snapshot이 safe state인가?
⇒ finish 리스트를 All True로 만들어주는 safety sequence가 존재하는가?
▪
Resource-Request algorithm
▪
위의 결과를 거친 후 request의 수락 여부를 결정해야 한다.
•
request를 수락한 상태의 matrix에서 safety 알고리즘을 돌려본다
•
돌려본 이후 safety state를 만족하는 safety sequence가 존재하면 request를 수락한다
▪
만약 어떤 쓰레드에서 자원 요청을 했을 때 resource-request algorithm 조건에 부합하지 않을 경우 요청을 기각한다.
◦
정리하자면 safety algorithm과 resource-request를 거친 후 safe state이면 자원 할당, 아니면 다른 프로세스들이 자원 해지까지 대기한다
◦
연산 비용이 비싸고 비효율적인 알고리즘
▪
detection과 recovery를 개발하게 된 이유
(3~4) 해당 시스템이 교착 상태로 진입하는 것을 탐지 후, 교착상태 진입 시 회복하는 방법
3.
Detection (탐지)
•
각 자원마다 Single Instance일 경우
◦
Wait-for 그래프 유지
▪
자원 할당 그래프에서, 자원을 제외 하여 오직 프로세스 만으로 그린 그래프
•
Pi → Pj : Pi는 Pj의 task가 끝나기를 대기함
▪
주기적으로 알고리즘을 돌려서 wait for 내 사이클이 존재하는 지 확인
▪
cycle(circular wait 구조) 존재 시, Dead Lock 존재 가능(unsafe)
▪
an algorithm to detect a cycle in a graph: O(n2) operations, where n is the
number of vertices in the graph
•
각 자원마다 Several Instance일 경우
◦
Available[m], Allocation[n][m], Request[n][m]
◦
4번에서 false인 쓰레드가 있을 시 감지
▪
데드락을 일으킨 프로세스를 강제 종료시킴
◦
algorithm
•
탐지 알고리즘을 실행 시, 그에 대한 오버 헤드 발생
◦
운영체제가 지속적으로 자원 할당 그래프를 유지하고 검사하기 때문
•
탐지 알고리즘의 호출 시기 및 빈도는 다음에 따라 다릅니다.
◦
얼마나 자주 교착 상태가 발생할 가능성이 있는지
◦
교착 상태가 발생하면 얼마나 많은 스레드가 교착 상태의 영향을 받는지
▪
데드락 사이클에 포함되는 스레드의 수는 커질 수 있음
•
탐지 알고리즘의 오버헤드로 인해, 탐지 알고리즘을 임의로 호출할 경우
◦
탐지 주기 빈도를 드물게 호출할 수 있는데, 이 경우 자원 그래프에 너무 많은 사이클이 존재할 수 있다.
◦
즉, 자원 그래프에 많은 사이클이 있을 수 있으므로 많은 교착 상태 스레드 중 교착 상태를 "일으킨" 스레드를 알 수 없습니다.
◦
모든 요청마다 vs 규정된 주기마다 호출을 잘 조절해주어야 한다
•
탐지 알고리즘이 데드락 존재 확인 시
◦
교착상태를 일으킨 프로세스를 종료하거나, 할당된 자원을 해제시켜 회복
4.
Recovery (회복)
•
교착상태를 일으킨 프로세스를 종료하거나, 할당된 자원을 해제시켜 회복시키는 방법
•
프로세스 종료 방법
◦
교착 상태의 프로세스들을 모두 중지
◦
교착 상태가 제거될 때까지 하나씩 프로세스 중지 (아래 기준들로)
▪
프로세스의 우선순위
▪
프로세스 실행 기간, 완료까지 남은 실행 시간
▪
프로세스 자원 사용 수
▪
프로세스가 처리 해야 할 남은 자원 수
▪
이어서 종료되어야 할 남은 프로세스 수
▪
프로세스의 iteractive, batch 여부
•
자원 선점 방법
◦
교착 상태의 프로세스가 점유하고 있는 자원을 선점해 다른 프로세스에게 할당
◦
select a victim(비용 최소화를 위해 아래 기준 위주로 프로세스 자원 선점)
▪
우선 순위가 낮은 프로세스
▪
기아 문제 방지를 위해 rollback 횟수를 비용 요소에 포함
◦
Rollback : 다시 실행시킬 때 safe state 체크포인트로 롤백 시킴 ⇒ 비용이 비싸다