Operating Systems 8. Deadlocks

System Model

- 시스템은 자원으로 구성되어 있다.

- 자원은 CPU 사이클, 메모리 공간, I/O 장치들과 같은 여러 유형으로 구분된다.

-프로세스의 자원 이용 과정

• 요청 : 만약 요청이 즉시 승인될 수 없다면, 요청하는 프로세스는 자원을 획득할 때까지 대기해야 한다.
• 사용 : 프로세스는 자원을 이용한다.
• 방출 : 프로세스는 자원을 놓아준다.

 

Deadlock Characterization

- 데드락은 다음과 같은 4가지 조건이 동시에 성립할 때에 발생한다.

• Mutual exclusion : 한 번에 한 프로세스만 사용할 수 있는 자원이 존재한다.
• Hold and wait : 프로세스가 최소 하나의 자원을 점유한 상태에서 다른 프로세스가 점유한 자원을 대기한다.
• No preemption : 비선점으로, 자원이 강제로 방출될 수 없고 자발적으로만 방출될 수 있다.
• Circular wait : 프로세스 집합 {P0, P1, …, Pn}에서 P0 는 P1 점유자원 대기, P1 는 P2 점유자원 대기, … Pn–1 는 Pn 점유자원 대기 Pn 는 P0 점유자원 대기를 하는 순환 대기의 상태이다.

 

Deadlock with Mutex Locks

-> 데드락이 발생하는 4가지 조건이 모두 성립하는 상황이다.

 

- 데드락 예시

 

 

 

Resource-Allocation Graph

- V : vertex 집합

- E : edge 집합

- vertex 집합 V = 두 종류의 집합 P와 R로 구분됨 

• P = {P1, P2, …, Pn} : 프로세스 집합 
• R = {R1, R2, …, Rm} : 자원의 집합

- edge – 방향성이 있음 

• request edge : Pi  ->  Rj (프로세스가 자원 요청) 
• assignment edge : Rj ->  Pi (자원이 프로세스에 할당됨)

 

- 자원 할당 그래프의 예

- P = { P1, P2, P3 }
- R = { R1, R2, R3, R4}
- E = { P1 → R1, P2 → R3, R1 → P2, R2 → P2, R2 → P1, R3 → P3 }
- 순환 대기 없음 → 사이클이 없음 
- 교착상태가 아님

 

- 자원 할당 그래프가 cycle이 없음 -> no deadlock

- 자원 할당 그래프가 cycle 포함 

• 자원 유형 당 1개의 instance를 보유 -> deadlock
• 자원 유형 당 여러 개의 instance를 보유 -> deadlock 가능성 (cycle 수가 instance 수보다 작으면 no deadlock 가능)

 

Graphs with a Cycle

- 교착상태에 있는 자원할당 그래프 (cycle 이 존재한다)

- 두 개의 cycle 존재

• P1 -> R1 -> P2 -> R3 -> P3 -> R2 -> P1
• P2 -> R3 -> P3 -> R2 -> P2

-> 이때 R2 의 인스턴스가 2개이여도, 2개의 cycle 이 존재하므로 교착상태가 발생한다.

 

- 교착상태가 아닌 자원할당 그래프

- 하나의 cycle 존재 : P1 -> R1 -> P3 -> R2 -> P1

-> 이때 R2 는 2개의 인스턴스를 가지므로 deadlock 이 발생하지 않는다. P4 의 작업이 끝나면 R2는 R3에게 주어지기 때문이다.

 

 

 

Methods for Handling Deadlocks

- 시스템이 절대 deadlock 상태가 되지 않도록 보장한다.

• deadlock prevention (예방) : 4가지 필요조건 중 하나 이상을 만족하지 않게 한다.
• deadlock avoidance (회피) 

- 시스템이 deadlock 상태가 된 후 복구하는 것을 허용한다.

- deadlock 이 자주 발생하지 않기 때문에 예방/회피를 하지 않고 그냥 무시한다.

 

 

 

Deadlock Prevention

- deadlock 이 발생하는 네 가지 조건 중에 적어도 하나가 일어나지 않게 보장함으로써 교착상태를 예방할 수 있다.

- 상호 배제(Mutual Exclusion) 조건 거부

• 공유 가능한 자원들의 배타적인 접근을 요구하지 않는다. ex) 읽기 전용 파일
• 동시 공유 불가능 자원은 상호배제를 해야 한다. ex) 프린터

- 점유하며 대기(Hold and Wait)

• 프로세스가 자원을 요청할 때마다 다른 자원을 점유하지 않았음을 보장해야 한다.
• 1) 프로세스가 실행 시작 전에 필요한 모든 자원을 요청하여 모두 할당 받는다. -> 낮은 자원 이용률을 야기한다.
• 2) 프로세스가 아무 자원도 점유하고 있지 않을 때만 자원을 요청하도록 한다. -> 순차적 자원 할당이 이뤄지고, 기아 현상이 발생할 수 있다.

- 비선점(No Preemption)

• 한 개 이상의 자원을 점유한 프로세스가 즉시 할당 받을 수 없는 추가의 자원을 요청한다면, 현재 잡고 있는 모든 자원을 내려 놓도록 한다.
• 선점된 자원은 기다리고 있는 프로세스를 위한 자원 목록에 추가된다.
• 프로세스는 반납한 자원과 요청한 자원을 모두 할당 받을 수 있을 때에 재개될 수 있다.
• 이는 CPU 레지스터, 메모리 등 상태가 쉽게 저장/복원 가능한 경우에 사용되나, 프린터 등에는 적용이 어렵다.

- 순환 대기(Circular Wait)

• 모든 자원 타입들에 대해 전체적으로 순서를 부여한다.
• 각 프로세스는 오름차순으로만 자원을 요청할 수 있다.
• 사이클이 발생하지 않으므로 교착상태가 발생하지 않으나, 오름차순 요청은 자원을 활용하는데 큰 제약 조건이다.
• 예)

-> lock 을 순차적으로 요청한다.

 

 

- 교착상태 예방 알고리즘 : 요청이 생성되는 방법에 제약을 가하여 교착상태를 예방한다.

- 이 제약에 의해 적어도 교착상태 발생의 필요 조건 중 하나가 일어나지 않게 함으로써 교착상태가 발생하지 않게 한다.

- 그러나, 교착상태 예방에서 가능한 side effect (부작용) 이 발생할 수 있다. (낮은 장치 사용률, 감소된 시스템 처리량)

-> 교착상태 회피로 대체할 수 있다.

 

 

Deadlock Avoidance

- 자원이 어떻게 요청되는지에 대한 추가 정보를 필요로 한다.

- 필요로 하는 각 유형별 자원에 대한 maximum number 을 선언해야 한다.

- 자원 할당 상태를 조사하여 순환 대기 조건이 발생하지 않도록 자원 요청을 제어한다.

- 자원 할당 상태는 할당 가능한 자원의 수, 프로세스의 maximum demand 로 정의된다.

 

 

 

Safe State

- 시스템이 안전 순서가 존재하면, 안전 상태에 있다.

- 안전 순서란 프로세스 시퀀스 <P1, P2, ... , Pn> 에 대해서

• Pi 가 요청하는 자원이 현재의 가용 자원과
• j<i 인 모든 Pj가 점유한 자원(사용 후 반납하는) 에 의해서 만족된다면
• 프로세스 시퀀스는 안전 순서라고 한다.

- 즉, Pi 가 필요로 하는 자원이 즉시 충족되지 못할 때에는, Pi 의 가용자원과 sequence 앞에 있는 모든 Pj 들이 반납한 자원을 가지고 수행할 수 있다. 

 

 

Safe, Unsafe, Deadlock States

- Safe 상태 -> No deadlock

- Unsafe 상태 -> Deadlock 가능성 존재

- 교착상태 회피 : 시스템이 unsafe 상태로 진입하지 않도록 보장해야 한다.

- 교착상태 회피 알고리즘 유형 

• 단일 인스턴스 자원 유형 -> 자원 할당 그래프 사용
• 다수의 인스턴스를 갖는 자원 유형 -> banker's 알고리즘 사용

 

 

Resource-Allocation Graph

- Claim edge : 프로세스 Pi 는 미래에 Rj 를 요청할 수 있다. Pi -> Rj

• 즉, claim edge 는 request edge 로 변환될 수 있다.
• 점선으로 표시한다.

- 자원 요청은 request edge Pi -> Rj 가 assignment edge Rj -> Pi로 변환하는 것이 자원 할당 그래프에 cycle을 형성하지 않을 때에만 승인한다.

 

- Unsafe State

- R2 가 P2 에 할당되었다.

- P1 이 R2 를 요청할 때에 deadlock 이 발생한다.

-> 따라서 P2 의 R2 요청은 승인하지 않는다. Unsafe!

 

 

 

은행원 알고리즘(Banker's Algorithm)

- 자원 할당 그래프는 하나의 타입에 자원 인스턴스가 여러 개 있을 경우에는 적용되지 못한다.

-> 은행원 알고리즘으로 해결 가능

• 프로세스는 자신이 필요로 하는 자원의 최대 개수를 미리 신고한다.
• 시스템은 자원의 최대 개수를 허용했을 경우에도 안전 상태에 있도록 판단한다.

 

은행원 알고리즘의 자료구조

- n = 프로세스의 개수, m = 자원 타입의 개수

- Available : 각 자원 타입별로 사용 가능한 인스턴스를 표시하는 길이가 m인 벡터. Available[j] = k 라면, j번째 자원을 k개 사용할 수 있다는 뜻이다.

- Max : 각 프로세스 자원의 최대 요청량을 표시하는 n*m 행렬. Max[i,j] = k 라면, 프로세스 Pi 는 자원 Rj 를 최대 k까지 요청할 수 있다.

- Allocation : 현재 각 프로세스에 할당되어 있는 각 형태의 자원 수를 정의하는 n*m 행렬. Allocation[i,j] = k 라면, 프로세스 Pi 는 자원 Rj 를 k개 할당받고 있다는 의미다.

- Need : 각 프로세스에 남아 있는 자원 요청을 표시하는 n*m 행렬. Need[i,j] = k 라면, 프로세스 Pi 는 자신의 작업을 종료하기 위해 Rj 를 k개 더 필요로 한다는 의미이다.

-> Need[i,j] = Max[i,j] - Allocation[i,j]

 

 

Safety Algorithm

1. Work 와 Finish 를 각각 길이 m,n 인 벡터라고 할 때,

Work = Available 

Finish[i] = false for i=0,1, ... , n-1 으로 초기화한다.

 

2. Finish[i] = false

Need(i) <= Work 를 만족하는 i 를 찾는다. i 값이 없으면 4단계로 이동한다.

 

3. Work = Work + Allocation(i) 

Finish[i] = true 를 수행하고 다시 2단계로 이동한다.

4. 모든 i 에 대해서 Finish(i) == true 이면 시스템은 safe 상태이다.

 

 

Resource-Request Algorithm for Process Pi

1. Request(i) <= Need(i) 라면 2단계로 이동하고, 그렇지 않으면 error 상태이다.

 

2. Request(j) <= Available 라면 3단계로 이동하고, 그렇지 않다면 자원이 부족하기 때문에 Pi 는 대기한다.

 

3. 시스템은 상태를 다음과 같이 수정하여 요청된 자원을 프로세스 Pi 에 할당한다.

Available = Available – Request(i)
Allocation(i) = Allocation(i) + Request(i)
Need(i) = Need(i) – Request(i)

 

4. safety 알고리즘을 돌린다.

이때 만약 safe 상태라면 -> 자원은 Pi 에게 할당된다.

unsafe 상태라면 -> Pi 는 대기해야 하고, 이전의 자원 할당 상태가 복구된다.

 

 

은행원 알고리즘 예시

Need(i) 를 계산하자.

P0 : 7 4 3

P1 : 1 2 2

P2 : 6 0 0

P3 : 0 1 1

P4 : 4 3 1

 

P1부터 차례로 자원이 할당 가능한지 판별하자.

Need(0) : 7 4 3 >= Work : 3 3 2 이므로 P0은 할당할 수 없다.

Need(1) : 1 2 2 <= Work : 3 3 2 이므로 P1는 할당할 수 있다.

따라서 Work = 3 3 2 + 2 0 0 (Allocation[2]) = 5 3 2

P2 -> Need(2) : 6 0 0 >= Work

p3 -> Need(3) : 0 1 1 <= work 이므로 P3은 할당가능하다.

따라서 Work = 5 3 2 + 2 1 1 = 7 4 3

p4 -> Need(4) : 4 3 1 <= work 이므로 p4 도 할당가능하다.

-> Work = 7 4 3 + 0 0 2 = 7 4 5

p0 -> Need(0) : 7 4 3 <= 7 4 5 이므로 

work = 7 4 5 + 7 4 3  = 14 8 8

p2 -> Need(2) <= Work 이므로

work = 14 8 8 + 3 0 2 = 17 8 10 으로

P1 -> P3 -> P4 -> P0 -> P2 의 sequence 에 대해 safe 상태가 성립함을 확인할 수 있다.

(sequence 가 하나라도 존재하면 safe)

 

 

예)

1. P1 Request (1,0,2) -> true

• Request1 <= Need1 : (1,0,2) <= (1,2,2)
• Request1 <= Available : (1,0,2) <= (3,3,2) 
• -> Allocation = (2,0,0) + (1,0,2) = (3,0,2)
• -> Need = (1,2,2) - (1,0,2) = (0,2,0)
• -> Available = (3,3,2) - (1,0,2) = (2,3,0)

2. P4 Request (3,3,0) -> false

• Request4 <= Need4 : (3,3,0) <= (4,3,1) 
• Request4 <= Available : (3,3,0) <= (2,3,0) -> 불만족이므로 reject

3. P0 Request (0,2,0) ->

• Request0 <= Need0 : (0,2,0) <= (7,4,3)
• Reqeust0 <= Available : (0,2,0) <= (2,3,0)
• -> Allocation = (0,1,0) + (0,2,0) = (0,3,0)
• -> Need = (7,4,3) - (0,2,0) = (7,2,3)
• -> Available = (2,3,0) - (0,2,0) = (2,1,0)
• ->  자원은 충분하지만 unsafe 상태에 도달하므로 reject

 

 

교착상태 탐지 (Deadlock Detection)

- 시스템은 교착상태에 들어갈 수 있으며, 이 환경에서 시스템은 반드시 다음 알고리즘을 지원해야 한다.

• 교착상태를 탐지하는 알고리즘
• 교착상태로부터 회복하는 알고리즘

 

Single Instance of Each Resource Type

- Node 들은 프로세스를 나타낸다.

- Pi -> Pj 는 Pi 가 Pj 의 점유자원을 대기함을 의미한다.

- cycle 이 존재하는지 검사에 O(n^2) 연산이 소요된다.

-> 자원할당 그래프에서 자원을 제외하고 프로세스로만 나타내면 오른쪽과 같은 그래프가 된다.

-> 이는 resource instance 가 하나일때만 판단이 가능하다.

 

 

 

Several Instance of a Resource Type

 

 

Detection Algorithm

- 4단계에서 Finish[i] == false 인 i 가 존재한다면 현재 시스템은 deadlock 상태이다.

- 탐지 알고리즘은 O(m x n^2) 시간이 걸린다.

 

 

예시)

이때 P0 의 자원을 회수하고 P0 은 finish== true 가 될 수 있다. 그러나 그 다음으로 할당가능한 것이 없기 때문에 이 시스템은 P1, P2, P3, P4 에 의해 deadlock 이 발생한다.

 

 

 

탐지 알고리즘 사용

- 언제 얼마나 자주 탐지 알고리즘을 호출할 것인가?

• 교착상태가 얼마나 자주 발생하는가?
• 교착상태가 발생하면 몇 개의 프로세스가 영향을 받는가?

- 탐지 알고리즘을 호출하는 바람직한 시점은?

• 자원을 요청할 때마다 호출하기 -> 오버헤드가 매우 크다.
• 어떤 프로세스가 자원을 요청했는데 그것이 즉시 만족되지 못하는 시점 
• 지정된 시간 간격으로 호출 (한 시간에 한 번 CPU 이용률이 40% 이하로 떨어질때)