[OS] 08. Deadlocks

Operating System [OS]

[OS] 08. Deadlocks

Coulson 2024. 1. 2. 23:24

Dining Philosophers Problem

5명의 철학자가 원탁에서 식사하는 문제

Dining Philosophers Problem의 조건

식사 시간은 서로 다름
식사를 위해선 양쪽의 포크를 모두 확보해야 함
서로 소통할 수 없음
왼쪽 포크를 먼저 들고, 오른쪽 포크를 듦
포크가 사용 중이라면 대기함

문제가 발생하는 경우 : 거의 동시에 왼쪽 포크를 들면 오른쪽 포크를 들 수 없는 교착 상태 발생
해결 방법 중 하나 : 4명이 왼쪽 포크를 먼저 잡고 오른쪽 포크를 잡는 순서로 진행
마지막 사람은 오른쪽을 먼저 잡도록 함 -> 원형 상태로 요청이 생기지 않도록 함

Deadlock

System Model - 시스템은 리소스(resource)(자원)를 포함 (CPU cycles / Memory space / I/O Devices)

각 프로세스는 리소스를 다음과 같이 활용

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

Deadlock Characterization
데드록(교착 상태)은 다음 4가지 조건이 동시에 성립할 때만 발생함

Mutual Exclusion 상호 배제
- 한 번에 하나의 프로세스만 자원을 리소스를 사용할 수 있음
Hold and Wait 점유하며 대기
- 최소한 하나의 리소스를 가진 프로세스가 다른 프로세스가 가진 추가 리소스를 얻기 위해 대기함
No Preemption 비선점
- 리소스는 자신을 가진 프로세스가 작업을 끝낸 후에 자발적으로만 방출될 수 있음
Circular Wait 순환 대기
- 대기 중인 프로세스의 집합 {P0, P1, ... Pn}이 각각 P0은 P1가 가진 프로세스를 기다리고 있고
반복 형태로 Pn-1은 Pn이, Pn은 P0이 가진 프로세스를 기다리고 있는 형태를 취함

Deadlock 예시

빨간 줄에서 Deadlock이 발생함

Resource-Allocation Graph

V : 정점들의 집합

E : 간선(edge)들의 집합

V의 2가지 종류

시스템 내 모든 프로세스로 구성된 집합 P = {P1, P2, ... , Pn}
시스템 내 모든 리소스로 구성된 집합 R = {R1, R2, ... ,Rm}

E의 2가지 종류

Request edge (요청선) : directed edge Pi → Rj
Assignment edge (할당선) : directed edge Rj → Pi

Resource-Allocation Graph 예제

Resource-Allocation Graph의 기본 사항

그래프에 사이클이 포함되어 있지 않으면 Deadlock이 발생하지 않음
그래프에 사이클이 포함된 경우
- 각 리소스 타입에 오직 1개의 인스턴스가 있다면 Deadlock 발생
- 각 리소스 타입에 여러 인스턴스가 있다면 Deadlock의 가능성이 있음

Handling Deadlocks

시스템이 절대 Deadlock에 들어가지 않도록 하는 방법 : Deadlock Prevention & Deadlock Avoidance
시스템이 Deadlock 상태에 들어간 후 복구하도록 허락
문제를 무시하고 Deadlock이 일어나지 않은 것처럼 가정 (UNIX를 포함한 대부분의 OS가 사용)

Deadlock Prevention
Deadlock(교착 상태)을 발생시키는 4가지 조건 중 적어도 하나가 일어나지 않게 보장

상호 배제(Mutual Exclusion) - 공유 가능한 자원들의 배타적인 접근을 요구하지 않음
- 예를 들어, 읽기 전용 파일(read-only file)에 대해서는 배타적 접근이 필요하지 않음
- 반면에, 프린터 등의 비공유 자원의 경우는 배타적 접근이 보장되어야 함
점유하며 대기(Hold and Wait) - 프로세스가 자원을 요청할 때마다 다른 자원을 점유하지 않았음을 보장해야 함
1. 프로세스가 실행 시작 전에 필요한 모든 자원을 요청하여 모두 할당받음 → 낮은 자원 이용률 야기
2. 프로세스가 아무 자원도 점유하고 있지 않을 때만 자원을 요청하도록 함
→ 순차적 자원 할당이 이뤄짐. 기아가 발생할 수도 있음
비선점(No Preemption) - 한 개 이상의 자원을 점유한 프로세스가 즉시 할당받을 수 없는 추가의 자원을 요청한다면,
현재 잡고있는 모든 자원을 내려놓도록 함
- 선점된 자원은 기다리고 있는 프로세스를 위한 자원 목록에 추가됨
- 프로세스는 요청했던 새로운 자원뿐 아니라 이전에 소유했던 자원까지 모두 다시 얻었을 때, 다시 시작될 수 있음
- CPU 레지스터, 메모리 등 그 상태가 쉽게 저장/복원 가능한 경우에 사용, 프린터 등에는 적용이 어려움
순환 대기(Circular Wait) - 모든 자원 타입들에 대해 전체적으로 순서(order)를 부여
- 각 프로세스는 오름차순으로만 자원을 요청할 수 있음
- 사이클이 없으므로 Deadlock이 발생하지 않으나, 오름차순 요청은 자원을 활용하는데 큰 제약 조건이 됨

Lock Ordering Deadlock 예시

트랜잭션 1과 2는 동시에 실행
트랜잭션 1은 계정 A에서 B로 25$를 이체하고
트랜잭션 2는 계정 B에서 A로 50$을 이체함

Deadlock Prevention은 요청이 생성되는 방법에 제약을 가하여 Deadlock을 예방
Side Effects 발생 가능 (낮은 장치 사용률 / 감소된 시스템 처리량)

대체 방법이 Deadlock Avoidance

Deadlock Avoidance
시스템이 사용 가능한 추가적인 사전 정보를 가지고 있어야 함이 요구됨

가장 간단하고 유용한 모델은 각 프로세스가 각 타입마다 필요로 하는 리소스의 초대 수를 선언해야 함
데드락 회피 알고리즘은 원형 대기 조건이 발생하지 않기 위해 동적으로 리소스 할당 상태를 검사
리소스 할당 상태는 사용 가능한 리소스의 수, 할당된 리소스의 수, 프로세스의 최대 요구 수로 정의

Safe State

프로세스가 사용 가능한 리소스를 요구할 때, 시스템은 만약 즉시 할당하더라도 시스템이 Safe State인지 결정해야 함
시스템이 Safe State에 있다면, 시스템 내의 모든 프로세스 <P1, P2 ... Pn> 시퀀스가 존재
이 때, 각 Pi는 Pi가 요청할 수 있는 리소스는 현재 가능한 리소스와 모든 Pj( j<i)가 가진 리소스로 충족할 수 있어야 함
만약 Pi가 즉시 필요하지 않다면, Pi는 모든 Pj가 종료될 때까지 기다려야 함
Pj가 끝나면 Pi는 리소스를 얻고 실행되고, 할당된 리소스를 반환하고 종료됨
Pi가 종료되면, Pi+1이 필요한 리소스를 얻고 이 과정이 반복됨

만약 시스템이 Safe State에 있다면 -> No Deadlocks
만약 시스템이 Unsafe State에 있다면 -> Deadlock의 가능성이 있음
Avoidance -> 시스템이 절대 Unsafe State에 들어가지 못하도록 보장하는 것

Avoidance Algorithms

리소스 타입의 단일 인스턴스 -> Resource-Allocation Gragh 사용
리소스 타입의 다중 인스턴스 -> Banker’s Algorithm 사용

Resource-Allocation Graph

Claim Edge : Pi → Rj 는 프로세스 Pi가 리소스 Rj를 요청할 수 있음을 나타냄 / 점선으로 표현
프로세스가 리소스를 요청할 때, Claim Edge는 Request Edge(요청선)로 변환
리소스가 프로세스에 할당되면 Request Edge는 Assignment Edge(할당선)으로 변환
리소스가 프로세스에 의해 해제되면, Assignment Edge는 다시 Claim Edge로 재변환
리소스는 시스템 내에서 사전에 Claim되어야 함

프로세스 Pi가 리소스 Rj를 요청한다고 가정하면 해당 요청은 Request Edge를 Assignment Edge로 변환하면서 Resource-Allocation Graph에 사이클이 형성되지 않는 경우에만 허용 가능

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

프로세스는 자신이 필요로 하는 자원의 최대 개수를 미리 신고

시스템은 자원의 최대 개수를 허용했을 경우에도 Safe State에 있도록 판단

은행원 알고리즘의 데이터 구조

n : 프로세스의 수 / m : 리소스 유형의 수
Available : m 길이의 벡터 / available[ j] = k면 리소스 유형 Rj에 대해 k개의 인스턴스가 사용 가능
Max : n x m 행렬 / Max[i, j] = k면 프로세스 Pi는 리소스 유형 Rj에 대해 최대 k개의 인스턴스 요청 가능
Allocation : n x m 행렬 / Allocation[i, j] = k면 프로세스 Pi는 리소스 유형 Rj에 대해 현재 k개 인스턴스를 할당받음
Need : n x m 행렬 / Need[i, j] = k면 프로세스 Pi는 작업 완료를 위해 리소스 유형 Rj에 대해 인스턴스 k개가 더 필요함
=> Need[i, j] = Max[i, j] - Allocation[i, j]

Safety Algorithm

Work와 Finish를 각각 m과 n의 길이를 갖는 벡터라고 두고
Work = Available / Finish[i] = false for I = 0, 1, ... , n-1 로 초기화
Finish[i] = false이고 Needi ≤ Work인 i를 찾고 존재하지 않으면 4단계로 이동
3. Work = Work + Allocationi, Finish[i] = true로 설정하고 2단계로 이동
4. 만약 모든 I에 대해 Finish[i] = true이면 시스템은 Safe State에 있음

프로세스 Pi의 Resource-Request Algorithm

Requesti = 프로세스 Pi의 요청(Request) 벡터
만약 Requesti[ j] = k이면 프로세스 Pi는 리소스 유형 Rj에 대해 k개의 인스턴스를 요청

만약 Requesti ≤ Needi 이면 2단계로 이동 / 아니면 프로세스가 최대 요청을 초과했으므로 에러 발생
만약 Requesti ≤ Available 이면 3단계로 이동 / 아니면 리소스가 현재 사용 가능하지 않으므로 Pi는 기다림
요청된 리소스를 Pi에 할당하는 것처럼 가장하고 상태를 다음과 같이 수정
- Available = Available – Requesti; - Allocationi = Allocationi + Requesti; - Needi = Needi - Requesti;

만약 안전하다면 리소스는 Pi에게 할당
안전하지 않다면 Pi는 기다리고 이전의 Resource-allocation 상태로 되돌려짐

Banker’s Algorithm 예시

P0부터 P4까지 5개의 프로세스 / A(10인스턴스), B(5인스턴스), C(7인스턴스), 3개의 리소스 타입

T0에서의 Snapshot

어떠한 순서로든 프로세스를 모두 완료할 수 있으면 됨 -> Safe State

<P1, P3, P4, P2, P0> 시퀀스로 가능

<P1, P3, P4, P0, P2>도 가능

만약 P1이 (1,0,2)의 Request를 보냈다면?

Request ≤ Available 인지 확인 (1,0,2) ≤ (3,3,2) => true

Deadlock Detection (교착 상태 탐지)

시스템 성능 저하 방지를 위해 Deadlock Prevention이나 Avoidance를 하지 않는다면 시스템은 Deadlock에 들어가며 이 환경에서 시스템은 반드시 다음 알고리즘을 지원해야 함

Deadlock 탐지 알고리즘 / Deadlock으로부터 회복하는 알고리즘

각 리소스 타입이 단일 인스턴스인 경우

Wait-for Graph를 유지
노드는 프로세스
Pi → Pj는 Pi가 Pj를 기다리고 있다는 의미
주기적으로 그래프에서 사이클을 찾는 알고리즘을 호출
사이클이 있다면 Deadlock이 존재
그래프에서 사이클을 찾는 알고리즘은 그래프의 정점 수 n에 대하여 n²의 연산을 요구

각 리소스 타입이 다중 인스턴스인 경우

Available : m 길이의 벡터 / 각 타입의 사용 가능한 리소스의 수를 나타냄
Allocation : n x m 행렬 / 현재 각 프로세스에 할당된 각 타입의 리소스 수를 나타냄
Request : n x m 행렬 / 각 프로세스의 현재 요청을 나타냄
Request[i][ j] = k는 프로세스 Pi가 리소스 타입 Rj에 대하여 k개의 인스턴스를 추가로 요청한다는 의미

Detection Algorithm

Work와 Finish를 각각 m과 n의 길이를 갖는 벡터라고 두고
Work = Available / 1부터 n까지 i 중에 Allocationi ≠ 0이라면, Finish[i] = false 아니면 true로 초기화
Finish[i] = false이고 Requesti ≤ Work인 i를 찾고 존재하지 않으면 4단계로 이동
Work = Work + Allocationi, Finish[i] = true로 설정하고 2단계로 이동
만약 1≤i≤n 사이의 i 중 Finish[i] = false이면 시스템은 Deadlock 상태에 있음
추가로 Finish[i] = false이면 프로세스 Pi는 Deadlock에 빠진 상태

알고리즘은 시스템이 Deadlock 상태인지 감지하기 위해 O(m x n²)의 연산이 필요

Detection Algorithm 예시

P0부터 P4까지 5개의 프로세스 / A(7인스턴스), B(2인스턴스), C(6인스턴스), 3개의 리소스 타입

T0에서의 Snapshot

<P0, P2, P3, P1, P4>의 시퀀스는 모든 i에

대해 Finish[i] = true의 결과를 보임

오른쪽 Request는 P2가 C타입의 추가 인스턴스를

요청한 경우 ((0,0,0)에서 (0,0,1)이 된 상태)

시스템의 상태는 P0이 보유한 리소스를 회수할 수 있지만 다른 프로세스의 요청을 충족시키기에는 리소스가 부족한 상태

프로세스 P1, P2, P3, P4로 구성된 Deadlock이 존재함

Detection-Algorithm 사용

언제, 얼마나 자주 탐지 알고리즘을 호출할 것인가?
- 교착상태가 얼마나 자주 일어날 것 같은가?
- 교착상태가 발생하면 통상 몇 개의 프로세스가 관련되는가?
탐지 알고리즘이 제멋대로 호출된다면?
- 자원 그래프에 많은 사이클이 존재할 수 있음
- 교착상태인 프로세스가 많아지면, 어떤 프로세스가 교착상태를 유발했는지 알 수 없음
탐지 알고리즘을 호출하는 바람직한 시점은?
- 자원을 요청할 때마다 탐지 알고리즘을 호출할 수도 있음 → 오버헤드가 매우 큼
- 어떤 프로세스가 자원을 요청했는데 그것이 즉시 만족되지 못하는 시점
-> 교착상태와 관련된 프로세스들을 알 수 있고, 누가 교착상태를 유발했는지 알 수 있음
- 지정된 시간 간격으로 호출함
-> 예로, 한 시간에 한 번 CPU 이용률이 40% 이하로 떨어질 때

Deadlock Recovery (교착 상태로부터 회복)

탐지 알고리즘이 교착상태가 존재한다는 것을 파악했다면, 이 상태로부터 회복하기 위해 여러 대안이 가능

1. 운영자에 의한 해결

교착상태 발생을 운영자에게 알리고, 운영자가 교착상태를 수작업으로 처리하도록 함
오늘날 컴퓨터 시스템에서는 비현실적 방법임

2. 프로세스 종료(process termination) : 순환 대기를 깨뜨리기 위해 하나 이상의 프로세스를 종료시킴

3. 자원 선점(resource preemption) : 교착상태로 인해 멈춘 하나 이상의 프로세스들로부터 자원을 내놓게 함

프로세스 종료

교착상태 프로세스를 모두 중지
- 확실하게 교착상태의 사이클을 제거하나, 비용이 많이 들게 됨
교착상태가 제거될 때까지 하나씩 중지
- 중지되는 프로세스 수는 줄일 수 있으나, 중지 후 문제가 해결되었는지 확인을 위해 교착상태 탐지 알고리즘을 계속 호출해야 하는 오버헤드 발생
종료해야 하는 프로세스는 다음 사항을 고려하여 선택함
- 프로세스 우선순위
- 프로세스가 얼만큼 계산되었고, 종료될 때까지 얼마나 남았는가?
- 프로세스가 사용한 자원
- 프로세스가 완료되기 위해 필요한 자원
- 얼마나 많은 프로세스들이 종료될 필요가 있는가?
- 프로세스가 대화형인가, 일괄(batch)처리형인가?

자원 선점

교착상태가 깨질 때까지 프로세스로부터 자원을 선점해(빼앗아) 다른 프로세스에게 주어야 함

자원 선점의 세 가지 요소

희생자 선택(selection of a victim) : 비용 최소화 고려 (위의 종료 프로세스 선택 시 고려 사항을 고려) - 프로세스가 점유한 자원의 수, 지금까지 소요한 시간 등을 고려하여 선택
Rollback : 프로세스를 안전한 상태까지 되돌리고 그 상태에서부터 재시작
- 교착상태를 해결할 수 있는 수준까지 rollback시키는 것이 가장 바람직함
- 그러나, 안전한 상태를 파악하기 어려우므로, 가장 단순한 것은 프로세스를 중지(abort)시키고 재시작
기아(starvation) : 같은 프로세스가 항상 희생자로 선택될 수도 있음 (rollback이 반복되는 상황) - 해결책으로는 희생자를 선택할 때, rollback된 횟수를 고려함