[운영체제] 공룡책🦖 ch08. Deadlocks

Reference

1. Abraham Silberschatz, Greg Gagne, Peter B. Galvin - Operating System Concepts (2018)

2. Operating System class by Professor Sukyong-Choi at Korea University 

3. 혼자 공부하는 컴퓨터구조 + 운영채재 (강민철)

중요한 내용 위주로 요약 && 정리했습니다.

목차

1. System Model
2. Deadlock in Multithreaded Applications
3. Deadlock
4. Methods for Handling Deadlocks
5. Deadlock Prevention
6. Deadlock Avoidance
7. Deadlock Detection
8. Recovery from Deadlock

---

mulitiprogramming 환경에서는 여러 thread들이 유한한 자원을 두고 경쟁한다.

대기 중인 thread가 다른 대기중인 thread가 점유한 자원을 요청하여 계속 waiting state인 경우가 발생할 수 있다.

이러한 경우를 dead lock 이라고 한다. ⇒ liveness failure !

8.1 System Model

• 자원이 한정되어 있다.
• 자원은 여러 type으로 나눠지며, 각각은 동일한 instances들로 구성된다.
• 어떤 resource type의 instance를 요청하면, 임의의 instance가 할당된다.
• 동기화 도구(lock, semaphore) 역시 system 자원이다. ⇒ deadlock 발생 원인

Thread는 자원 사용 전에는 request, 사용 후에는 release해야 한다.

(1) Request : 만약 즉시 사용할 수 없다면 대기한다.

(2) Use : 자원이 mutex lock이라면, 스레드는 CS에 진입 가능

(3) Release

• task 실행에 필요한 만큼만 자원을 요청한다.
• 요청한 자원의 수는 가용한 자원의 수를 초과하지 못한다.
• Request, Release는 system call이다. semaphore: wait(), signal() mutex lock: acquire(), release()

kernel-managed resource에 대해 OS가 자원 할당을 확인한다.

• thread가 커널 관리 자원을 사용 시, OS는 스레드가 요청했는지 할당 받았는지를 확인
• system table에 각 자원의 할당 여부를 기록함
• 할당 자원에 대해, table에 어느 스레드에 할당되었는지도 기록함
• 다른 스레드에 할당된 자원 요청 시, 스레드는 해당 자원에 대한 waiting 큐에 추가

Deadlocked state

• 스레드 집합 내의 모든 스레드가, 집합 내 다른 스레드에 의해서만 일어나는 event를 기다림
• event : 자원의 획득 및 해제 (mutex locks, semaphores, files)

---

8.2 Deadlock in Multithreaded Applications

• 서로 hold 중인 lock을 요청하는 상황 → deadlock!

⇒ 하지만, thread 실행 순서에 따라서 deadlock이 안 일어날 수도 있다! ⇒ 스레드2가 lock 획득하기 전에, 스레드1이 mutex1,2에 대한 lock을 획득하고 해제함

하지만, 특정 스케줄링 상황에서만 발생하는 deadlock에 대한 식별과 검사는 어렵다.

8.2.1 Livelock

deadlock과 유사한 상황을 나타내는 용어이다.

Deadlock과의 유사점

• 둘 이상의 thread가 진행되지 않음

Deadlock과의 차이점

• deadlock: Block O, Progress X ↔ livelock: Block X, Progress X
• ex) 길에서 두 사람이 멈춰 있지 않고(block은 아님), 좌우로 피해가려 하지만 진행은 안됨

Example

• 보통 livelock 은 스레드가 실패하는 작업을 동시에 재시도할 때 일어난다.
• deadlock보다 덜 일반적 (특정 스케줄링에서만 발생한다.)
• 각 스레드가 random 시간에 retry해서 해결 (이더넷 네트워크 충돌 시 사용하는 방법)

---

8.3 Deadlock Characterization

deadlock을 특징 짓는 조건들이 4가지 있다.

8.3.1 Necessary Conditions

4개의 조건을 동시에 만족하면 deadlock이다. 각 조건은 완벽히 독립적이지 않다.

1. Mutual exclusion → 그래서 공유 자원은 deadlock이 발생하지 않는다. ******
2. Hold and wait → thread는 적어도 하나의 자원을 holding, 추가적인 자원을 얻기 위해선 waiting
3. No preemption → 선점 시 deadlock 발생하지 않는다.
4. Circular wait : T0 → T1 → T2 → …. → Tn → T0 ….

⇒ deadlock이 발생하려면 4가지 조건이 모두 유지되어야 한다.

8.3.2 Resource-Allocation Graph

위와 같은 기호를 통해서 thread의 자원 request 및 holding을 표현할 수 있다.

• request edge: process → resource 방향의 edge
• assignment edge: resoutce → process 방향의 edge, 요청이 받아들여지면 변환
• 자원에는 가용한 instance의 개수만큼 표현한다.

Example

• 그래프에 cycle이 없다면 시스템 내 어떤 스레드도 deadlock이 아니다.
• 만약 그래프 내 cycle이 있다면 deadlock일 가능성이 있다.

(1) instance가 하나인 경우 → cycle은 곧 deadlock을 의미한다. (2) instance가 여러 개인 경우 → cycle이 deadlock을 의미하진 않는다.

With Cycle deadlock Example

⇒ T1, T2, T3 간 deadlock 발생

With Cycle No deadlock Example

⇒ T1과 T3 사이의 cycle이 존재하지만, deadlock은 없다.

---

8.4 Methods for Handling Deadlocks

deadlock을 처리하는 방법은 다음과 같다.

(1) 무시하고, deadlock이 일어나지 않은 척 한다. (ostrich algorithm)

만약 deadlock을 탐지하거나 복구할 알고리즘이 없는 경우, system이 deadlock 발생 자체를 모른다.
이때, 실행되지 않는 스레드에 의해서 자원이 hold되고, 더 많은 스레드가 자원을 요청함에따라 deadlock state로 진입하여 시스템 성능이 저하된다.
하지만, 비용면에서는 강점이 있다.

(2) deadlock 예방/회피 프로토콜 사용 → deadlock 상태가 되지 않음을 보장

• Deadlock prevention: 4가지 필요조건 중 최소 하나가 성립되지 않도록 보장하는 일련의 방법 자원 요청이 처리되는 것을 제한하여 방지한다.
• Deadlock avoidance: 사전에 스레드가 요구/사용하는 자원에 대한 부가적 정보를 OS에 제공 OS는 각 요청에 대해 스레드가 wait 할지를 결정한다. 현재 요청에 대해 현재 가용 자원, 현재 할당된 자원, 향후 요청/해제 등을 고려하여 결정

(3) 시스템이 deadlock이 되도록 허용한 후, detect/recover 함

• Deadlock detection: deadlock이 발생했는지를 결정하기 위해 시스템 상태를 확인하는 알고리즘
• Deadlock recovery: deadlock이 발생했다면, deadlock으로부터 정상으로 복구하는 알고리즘

(4) livelock에서의 방법을 사용

 

---

8.5 Deadlock Prevention

• 4가지 필수조건 중 하나 이상을 성립할 수 없도록 하여 deadlock을 예방한다.
• 하지만 장치 이용률 저하, 시스템 처리율 감소 등 단점이 있다.

각 조건에 대해서 성립할 수 없도록 할 수 있는지 검토해보자.

8.5.1 Mutual Exclusion

⇒ 자원이 공유되도록 하면 된다. ⇒ But, 특정 자원은 근본적으로 공유가 불가능 ⇒ 현실적으로 어렵다.

 

8.5.2 Hold and wait

⇒ Hold와 Wait을 동시에 하지 않도록 하면 된다. ⇒ 특정 프로세스에 자원을 모두 할당하거나 모두 해제해야 한다.

• 자원 요청 시, 다른 자원을 hold하지 않도록 보장한다.
• 각 스레드가 실행 전에 모든 자원을 요청하고 할당하도록 한다. ⇒ 자원 요청의 동적인 특성으로 비현실적이다.
• 자원을 갖고 있지 않을 때만 요청하도록 한다. ⇒ 스레드는 자원을 추가로 요청하기 전에 현재 할당된 자원을 해제해야 함

단점

1. Resource utilization 저하 한꺼번에 할당 → 할당은 되어도 오랫동안 사용 안될 수 있음
2. Starvation 발생 가능 여러 자원을 요청한 경우 필요 자원 중 최소 하나가 항상 다른 스레드에 할당 → 무한 대기

 

8.5.3 No Preemption

⇒ 자원 Preemption을 허용하면 된다. ⇒ 자원을 이용 중인 프로세스로부터 해당 자원을 빼앗을 수 있다.

(1) 즉시 할당이 불가능한 추가 자원을 요청 시 모두 해제시킨다.

Hold한 상태에서 즉시 할당되지 않는 다른 자원을 요청한 경우, hold한 모든 자원이 선점된다. 즉 즉시 해제된다. 선점된 자원은 스레드가 waiting 하던 자원의 list에 추가된다.
새로 요청한 자원 뿐 아니라, 기존에 holding 했던 자원을 얻을 때만 재시작된다.

(2) 자원 요청 시 가용한 지 먼저 확인한다.

1. 요청한 자원이 가용하면 할당
2. 만약 가용하지 않는다면 추가 자원을 기다리는 다른 스레드에 할당되었는지 확인 후 선점
3. 1,2가 아니면 스레드는 wait해야 한다. waiting 중에 다른 스레드가 이 스레드의 자원을 요청하면 선점된다. 요청하던 자원을 할당 받고, 대기 중에 선점된 자원을 회복했을 때만 restart된다.

• 상태가 쉽게 저장되고, 나중에 restore되는 자원들에 적용됨
• deadlock이 흔하게 일어나는 자원에는 적용이 안 된다.

 

8.5.4 Circular Wait ⇒ 가장 실용적인 해결법

⇒ chain을 끊으면 된다. (모든 자원에 번호를 붙이고, 오름차순으로 자원을 할당)

• 모든 자원 유형에 전체 순서를 매기고, 각 스레드가 열거된 오름차순으로 자원을 요청하게 한다.
• 자원을 비교하여 순서상 빠른 것을 결정한다.
• 시스템의 모든 동기화 객체 간 순서를 정해서 Application에서 처리한다.
• 각 자원에 번호를 붙이는 비용이 든다.

Protocol to prevent deadlocks (i < j)

(1) 각 스레드는 증가하는 순서로만 자원을 요청할 수 있다.
Ri을 요청한 후 Rj를 요청할 수 있다.

(2) 번호가 낮은 자원 j를 요청하는 스레드는 번호가 높은 자원 i를 해제해야만 한다.
동일 유형의 여러 instance가 필요한 경우, 한번의 request로 모두 할당받는다.

증명

만약 lock을 동적으로 획득 가능한 경우, lock 순서 여부가 deadlock 예방을 보장하지는 않는다.

 

 

---

8.6 Deadlock Avoidance

⇒ 프로세스들에 배분할 수 있는 자원의 양을 고려하여 deadlock이 발생하지 않을 정도의 양만큼만 자원을 배분하는 방법

⇒ 자원이 요청에 대한 “추가적 정보”를 요구한다.

각 요청에 대해, 시스템은 현재 가용한 자원, 현재 할당된 자원, 향후 할당/해제 등을 고려하여 wait할 지를 결정한다.

필요한 정보의 양과 유형에 따라 다양한 회피 알고리즘이 있다.

• 각 스레드가 필요한 유형의 자원의 최대수를 선언하도록 함
• circular wait 조건이 없도록 자원-할당 상태를 동적으로 확인
• 자원-할당 상태는 스레드에 대한 가용자원, 할당자원, 최대요구자원의 수로 정의됨
• safe sequence : deadlock없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서
• safe state : safe sequnce대로 프로세스들에 자원을 배분하여 deadlock이 발생하지 않는 상태

8.6.1 Safe State

⇒ 시스템이 어떤 순서로든 각 스레드에 자원을 할당하고 deadlock을 피할 수 있다면 safe하다.
⇒ safe sequence 가 있으면 시스템은 safe state 이다. [not deadlock state]
⇒ 없다면 unsafe state 이다. [무조건 deadlock state는 아니며, deadlock state로 갈 수 있음]

• unsafe state에서는, 스레드가 deadlock을 발생시키는 자원 요청을 막지 못함

<T1, T2, …. , Tn> 이 현재 할당 상태에서의 safe sequence라고 하자.

• 스레드Ti가 현재 가용자원 외에 “Tj가 점유한 자원”에 의해 만족 ⇒ safe 왜냐하면, Tj가 수행 후 자원을 해제할 것이기 때문이다.
• 자원이 가용하지 않다면, Ti는 Tj를 wait한다.
• Tj 종료 후, Ti는 자원획득/정상처리/자원반납/종료

Example

• 12개의 자원, 3개의 thread (T0, T1, T2)
• 각각 5, 2, 2개를 holding 중

T1→ 2개를 할당받고 작업을 끝낸 후 4개를 해제한다 (가용: 1개 → 5개)

T0 → 5개를 할당받고 작업을 끝낸 후 10개를 해제한다 (가용: 0개 → 10개)

T2 → 7개를 할당받고 작업을 끝낸 후 9개를 해제한다 (가용: 3개 → 12개)

⇒ sequence <T1, T0, T2>는 safety 조건을 만족하므로 safe sequence이다.

T2에 두 개의 자원을 배분하고 T2의 작업이 끝난다고 하더라고, 반환된 자원은 모두 4개이다. 4개로는 T0, T1의 요구를 들어줄 수 없다.

⇒ T2가 자원을 더 요청하는 것을 받아준 것이 문제이다! ⇒ T2가 다른 스레드 중 하나가 끝나서 자원을 해제할 때까지 대기한다면 avoid 가능

8.6.2 Resource-Allocation-Graph Algorithm

• 각 자원 유형의 인스턴스가 한 개인 경우
• claim edge : 예약 간선

• T1이 나중에 Rj를 요청하도록 예약 → dashed line으로 표시 (claim edge)
• T1이 Rj을 요청하면 → request edge로 변경
• T1이 Rj을 해제하면 → claim edge로 다시 변경

⇒ 자원 요청은, request edge → assignment edge로 변환 시 cycle을 형성하지 않을 때만 허용됨

cycle-detection algorithm으로 safety를 확인한다.

• cycle이 발견되지 않는다면 safe state
• cycle이 발견된다면 unsafe state ⇒ 스레드는 요청이 충족될 때까지 wait해야 됨

8.6.3 Banker’s Algorithm

• 각 자원의 유형의 인스턴스가 여러 개인 경우 사용됨
• Deadlock-avoidance algorithm 이다.
• 스레드가 자원 요구 시, 시스템은 자원 할당 후 safe state를 유지하는지를 판단함
• unsafe state이면, 다른 스레드가 자원을 해제할 때까지 wait한다.

Data structures for Banker’s Algorithm

• Available: 자원별 가용 instance
• Max: 스레드별 최대 요구 수
• Allocation: 스레드별 할당 자원 수
• Need: 스레드별 추가 필요 자원 수
• Need[i][j] = Max[i][j] - Allocation[i][j] // i: 스레드 수, j: 자원 종류 수
• Available = Available - Request_i
• Allocation_i = Allocation_i + Request_i
• Need_i = Need_i - Request_i

8.6.3.1 Safety Algorithm

• 현재 시스템이 safe state인지 확인

8.6.3.2 Resource-Request Algorithm

• 자원 요청 시 허용되는지를 결정

8.6.3.3 Example (중요)

---

8.7 Deadlock Detection

• deadlock 발생 여부를 결정하기 위해 시스템 상태를 검사하는 알고리즘
• overhead 발생: 필수 정보 유지, 알고리즘 실행 비용

8.7.1 Single Instance of Each Resource Type

• 각 자원 유형의 인스턴스가 한 개인 경우
• wait-for graph 사용

Wait-for Graph

• resource-allocation graph에서 자원(node)과 적절한 edge들을 제거한 그래프
• Edge Ti → Tj : 스레드 i가 스레드 j가 가진 자원을 방출하기를 기다림
• 
• wait-for graph에 cycle이 있으면, 시스템에 deadlock이 존재한다

⇒ wait-for graph 유지 + cycle을 찾기 위한 algorithm 주기적 호출

8.7.2 Serveral Instances of a Resource Type

• 각 자원 유형의 인스턴스가 여러 개인 경우

time-varting data structures

• Available: m개의 각 data type에 대한 가용 자원의 수
• Allocation: 각 스레드에 현재 할당된 자원 수
• Request: 각 스레드가 현재 요청한 자원 수

Detection Algorithm

Example

8.7.3 Detection-Algorithm Usage

• “언제 알고리즘을 실행할 것인가”에 대한 결정

deadlock이 자주 발생한다면 detection algorithm도 자주 호출되어야 한다.

• deadlock은 어떤 스레드가 즉시 승인되지 않는 요청을 한 시점에 일어난다. 요청 (chain 완성 x) → 요청 (chain 완성 o)

Detection Algorithm 호출 시기

1. 할당 요청이 즉시 승인되지 않을 때마다 detection 알고리즘을 호출 장점: deadlock된 스레드 뿐 아니라 deadlock을 야기한 스레드로 식별 단점: overhead 문제
2. 기준을 두고 정해진 간격마다 알고리즘을 호출 → 알고리즘이 임의 시점에 호출되면, 여러 cycle이 포함될 수 있어서 어느 스레드가 deadlock을 야기시켰는지 판단 불가능

---

8.8 Recovery from Deadlock

• deadlock 발생을 확인한 이후 처리할 복구 작업

8.8.1 Process and Thread Termination

(1) 모든 프로세스 중지

• 오래 실행되던 프로세스가 중지되고 나중에 다시 실행되어야 함

(2) cycle이 제거될 때까지 한번에 하나씩 중지

• 각 프로세스가 중지될 때마다 알고리즘이 호출되어야 함

어떤 프로세스부터 종료시킬 것인가

• 경제적인 면에서 희생자를 선정한다.

8.8.2 Resource Preemption

1. Selecting a victim : 선점되는 프로세스 선택(비용 최소화)
2. Rollback : 선점되는 프로세스를 어떻게 할 것인가 → 안전한 상태로 후퇴 후 다시 시작
3. Starvation : 동일 프로세스가 항상 선점되지 않도록 보장