[운영체제] 7.Deadlocks 교착상태

목적) 교착 상태 정의, 교착 상태 예방 및 회피 방법

The Deadlocks Problem

교착상태(Deadlock)이란?

• 교착상태란 어떤 다른 프로세스에 의해서 발생된 이벤트에 의해서 모든 프로세스가 대기하는 현상
• 요청한 자원을 다른 대기 중인 점유하고 있기 때문에 자원을 요청한 대기 중인 스레드(또는 프로세스)는 다시는 스레드 상태를 변경할 수 없다.
  • 봉쇄된 프로세스들의 집합
  • 각 프로세스가 자원을 가진 상태에서 다른 자원을 요구하는 상황
  • 요구하는 자원이 다른 프로세스에 의해 점유된 상태 (서로 진행되지 못함)

 

System Model for a deadlock (교착 상태의 시스템 모델)

자원의 종류는 여러 인스턴스 인스턴스로 구성된다.

• CPU cycles, memory space, I/O devices 등

각 프로세스의 자원 활용 순서

• request (자원 요청)
• use (자원 사용)
• release (자원 해제)

여기서 자원의 사용은 임계 영역(Critical Section)을 의미하고 임계 영역에는 여러 개의 자원을 사용하는 것을 의미함.

 

Deadlock Characterization (교착상태 특징)

• Mutual exclusion (상호 배제 조건)
  • 특정 자원은 할당되어 한 프로세스만 사용 (공유되지 않음)
• Hold and wait (보유 대기 조건)
  • 프로세스가 자원 가지고 있는 상태에서 추가 자원을 필요할 때 추가 자원을 할당받을 때까지 기다림
• No preemption (비 선점 조건)
  • 할당된 자원을 빼앗기지 않음
• Circular wait (환형 대기 조건)

 

교착상태 시스템 예시

교착상태 특징을 모두 만족하여 교착상태가 발생한 시스템 모델이다.

 

Resource-Allocation Graph : modeling (자원 할당 그래프)

• 자원 할당 그래프는 교착상태를 더 쉽게 이해하기 위한 방향성 그래프
• 정점(V)의 두 가지 종류
  • T = {T1, T2,..., Tn) : 시스템에서 활성화된 프로세스의 집합
  • R = {R1, R2,..., Rn) : 시스템에서 모든 자원 유형의 집합
• 방향성 간선(E) : Ti -> Rj (요청 가선)
  • 프로세스 i가 자원 Rj를 요청
• 방향성 간선(E) : Rj -> Ti (할당 간선)
  • 자원 Rj가 프로세스 i에게 할당

Example of a Resource Allocation Graph (자원 할당 그래프 예시)

• 사이클(Cycle) 없음 : No deadlock
• P1, P2 : 자원 기다리는 중 (waiting 상태)
• P3 : execution 상태

P3가 R3 사용 후 반납 시, R3는 P2에 할당되고 정상 실행 종료가 가능한 상태이다. (교착상태 X)

 

사이클 존재 교착상태 발생

• 사이클(Cycle) 존재 : deadlock
• P1, P2, P3 모두 자원을 기다리는 중 (waiting 상태)

Cycle이 생길 경우, 교착상태 발생 가능. 모든 프로세스가 대기상태이므로 교착상태이다.

사이클은 있지만 교착상태 X

• 사이클은 존재
• P2, P4는 execution 실행 중인 상태로 정상 종료 가능
• 이후 P1, P3 자원 할당받을 수 있으므로 교착상태는 아니다.

Basic Facts

• 자원 할당 그래프가 Cycle을 가지고 있지 않다면 교착상태 아니다.
• Cycle 있는 경우
  • 해당 자원이 하나의 인스턴스만 존재 : 교착상태 발생
  • 각 자원 인스턴스가 여러 개 존재 : 교착상태 발생 가능성 있음. (교착상태 가능성 파악이 중요)

 

Methods for Handling Deadlocks (교착상태 다루는 방법)

• 사용자 프로세스에 의한 교착상태 전혀 신경 쓰지 않음 (대부분의 시스템)
• 교착상태에 빠지지 않도록 함.
  • Deadlock prevention (교착상태 예방) - 교창 상태 예방은 거의 불가능
  • Deadlock avoidance (교착상태 회피) - Banker's Algorithm
• 교착상태 허용하나, 복구할 수 있도록 함 (deadlock recover)
  • 탐색(Detect)
  • 회복(Recover)

 

Deadlock Prevention (교착상태 예방)

교착상태의 4가지 조건 중 1개를 무효화 시킴

• Mutual Exclusion 상호 배제 -> 무효화 불가능
• Hold and Wait 보유 대기 무효화-> 기아 발생 가능 
• No Preemption 비 선점 -> 무한 연기 발생 가능
• Circular Wait 환형 대기의 부정
  • 자원에 번호를 부여하여 현재 보유한 자원 번호보다 같거나 큰 번호의 자원만을 요구하도록 함.

 

Circular Wait 환형 대기의 부정

• 환형 대기를 부정함으로 교착상태를 제거하는 예시
• P2가 R2를 보유한 상태에서 R1요구함으로써 교착상태 발생
• P2가 R1을 먼저 요구하도록 변경

• P4는 R4를 보유한 상태에서 낮은 수의 R1을 요구함으로 교착상태를 발생
• R1을 먼저 요구하고 R4를 요구하도록 변경

 

Deadlock Avoidance (교착상태 회피)

교착상태 회피하려면 사전 정보 필요

• 각 프로세스는 자원 최대 요구량 실행 전에 명시해야 한다.
• 원형 대기 조건에 빠지지 않도록 한다.
• 현재 사용 가능한 자원의 수, 최대 요구 자원의 수에 의해서 자원 할당 상태가 정의된다.

Safe State definition (안전 상태 정의)

한 프로세스가 사용 가능한 자원 요구할 때, OS는 시스템이 안전상태에 있는지 판단해야 한다.

(시스템이 안전 상태에 있도록 한다.)

 

Safe State (안전 상태)

• 최대 요구량을 만족한 프로세스가 반납하는 자원을 사용하여, 나머지 프로세스를 종료시킬 수 있을 때
• 모든 프로세스는 작업 완료에 필요한 최대 자원 양을 미리 선언

 

Basic Facts & Example

• 시스템이 안전상태 (safe state) : 교착상태 X
• 시스템이 불안전 상태 (unsafe state) : 교착상태 발생 가능

교착상태 회피 (Avoidance) : 즉, 불안전 상태에 빠지지 않도록 보장하는 것

• 최대 자원 12, 남은 자원 3
• p1의 추가 자원 필요량 2 이므로, 종료 가능. 종료 후 할당 자원 회수 -> 남은 자원 5
• p0 종료 가능 -> 남은 자원 10
• p2 종료 가능 -> 남은 자원 12
• 모든 프로세스 종료 (안전 상태)
• safe sequence가 존재한다. <p1,p0,p2>

만약 p2가 자원 1개 더 요청할 경우, p1종료 후 가용 자원 4개이므로 p0, p2종료 불가하여 교착상태가 발생한다.

 

 

안전상태(Safe State)와 위험상태(Unsafe State)의 관계

unsafe 불안전 상태가 반드시 교착상태를 의미하지는 않는다.

 

Avoidance algorithms (교착상태 회피 알고리즘)

• 자원 인스턴스 1개인 경우
  • 자원 할당 그래프 이용 회피 -> 일반적이지 않음 (생략)
• 여라 자원 인스턴스 가진 경우
  • Banker's algorithm 사용 (은행원 알고리즘)

 

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

자원 최대 사용량 알고 있어야 함

프로세스가 자원 요구 시, 할당 요구 허가될 때까지 대기

• 미리 정의된 프로세스의 자원 최대 요구량을 만족시키는 프로세스를 종료하여 할당된 자원을 반납받는다.
• 반납받은 자원과 현재 사용 가능 자원을 합하여, 다른 프로세스의 최대 요구량을 만족시킨 후 프로세스 종료하여 자원을 반납받는다.
  • 위 두 단계 반복하여 모든 프로세스 종료 가능하다면 안전상태
  • 종료 안 되는 프로세스 남아 있다면, 불안전 상태

 

Data Structures for the Banker's Algorithm (은행원 알고리즘의 데이터 구성)

프로세스 수 : n, 자원 유형 수 : m

 

Available (사용 가능 자원) : 사용 가능 자원 유형의 개수를 나타내는 벡터

• Available [m] : 만약 Available [j] == k이라면 Rj의 k개의 인스턴스가 이용 가능

Max (자원 최대 요구량) : 자원 최대 요구량을 정의한 매트릭스 (배열)

• Max [n x m] : 만약 Max [i][j] == k라면 스레드 i가 자원 유형 Rj에 대해서 최대 k개까지 요청 가능

Allocation (현재 할당량) : 프로세스에 현재 할당된 각각의 자원 유형의 개수를 정의한 배열

• Allocation [n x m] : 만약 Allocation [i][j] == k라면 스레드i는 자원 유형 Rj에 대해서 k개의 인스턴스를 할당됨

Need (추가 요구량) : 각각의 프로세스가 앞으로 요청할 자원을 나타내는 매트릭스 배열

• Need [n x m] : 만약 Need [i][j] == k라면 스레드 i가 자원 유형 Rj에 k개 요청
• Need = Max - Allocation

 

Safety Algorithm (안전 상태 판별)

1. Work와 Finish는 m과 n의 길이를 가진 배열. Work = Available로 초기화하고 Finish 배열의 각각의 모든 요소를 false로 초기화

2. 두 조건을 만족하는 인덱스 i를 탐색합니다. 만약 그러한 인덱스 i가 존재하지 않으면 4번 과정으로 이동.

3. 다음 로직을 수행하고 2번 과정으로되돌아갑니다.

 

4. 만약 모든 i에 대해서 Finish [i] == true라면 시스템은 안전상태에 있는 것을 의미.

 

자원 할당 전략 for Process Pi

1. 만약 Request_i <= Need_i라면 2번 과정으로 이동. 이외에는 에러를 발생. 왜냐하면 그 스레드는 최대 차후 요청(Claim)을 초과했기 때문.
2. 만약 Request_i <= Available라면 3번 과정으로 이동. 이외에는 스레드 i는 대기해야한다. 왜나하면 그 자원들은 이용이 불가능하기 때문.
3. 시스템은 쓰레드 i에게 요청한 자원을 할당합니다. 할당할 때 다음과 같은 과정이 수행됩니다. 
   1. Available = Available - Request_i : 이용 가능한 자원에서 요청한 자원을 차감
   2. Allocation_i = Allocation_i + Request_i : 할당된 자원 집합에서 요청한 자원을 추가
   3. Need_i = Need_i - Request_i : 스레드가 요청한 자원 중에서 방금 요청한 자원을 차감

 

Example of Banker's Algorithm

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

 

새로운 요청이 들어온 경우 (P1 Request (1,0,2)) -> 허가 가능)

 

새로운 요청이 들어온 경우 (P4 Request (3,3,0)) -> 할당 불가능)

• 자원 요청량(3,3,0)보다Available(2,3,0)이 부족하므로 해당 요청은 거부된다.

 

새로운 요청이 들어온 경우 (P0 Request (0,2,0)) -> 할당 가능)

 

 

Banker's algorithm의 한계점 (실적용 어려움)

• 교착상태를 회피하기 위해 교착상태가 일어나지 않을 때만 작업을 진행
• 할당할 수 있는 자원의 일정량을 요구함
  • 일정하게 남아있는 자원의 수 파악하기 어려울 수도 있음
• 사용자 수 일정해야 함
  • 다중 프로그래밍 시스템에서 가변적
• 동적인 자원 할당 방법
  • 사용자의 최대 필요량 파악 어려움
• 시스템 과부하 증가
• 자원 이용도 낮음

 

Deadlock Detection (교착상태 발견)

일반적인 시스템은 교착 상태를 예방/회피하지 않음

교착상태에 빠지도록 허용

• 교착상태 발견 알고리즘 이용
• 교착상태에서 복구(회복)

 

교착상태 발견 : Several Instances of a Resource Type (자원 여러 인스턴스)

교착상태 탐색 알고리즘의 데이터 구성

• Available [m] : 사용 가능한 자원을 나타내는 1차원 배열
• Allocation [n x m] : 얼마나 많은 자원이 프로세스에 할당되는지 나타내는 2차원 배열
• Request [n x m] : 현재 프로세스가 요구하는 자원의 정보를 담은 2차원 배열.
  • 만약 Request [i][j] == k라면 스레드 i가 자원 유형 Rj의 k개의 인스턴스를 요청한다는 의미.

 

Detection Algorithm (교착상태 탐색 알고리즘 수행 과정)

1. 길이 m과 n을 가진 Work과 Finish 배열을 초기화. (Work:사용 가능 자원, Finish: 프로세스 종료 여부)

• Work 배열의 각각의 값은 Available 배열의 요소 값으로초기화
• Finish 배열의 모든 요소에 대해서 초기화
• 만약 Allocation [i] != 0라면 Finish [i] = false, Allocation[i] == 0이라면 Finish[i] = true

2. 다음 두 조건을 만족하는 인덱스 번호 i를 탐색합니다. 만약 두 조건을 만족하는 i가 없다면 4번 과정으로 이동

• Finish[i] == false
• Request [i] <= Work

3. 2번 과정의 두 조건을 만족하는 인덱스 번호 i가 있다면 다음 과정을 수행합니다.

• Work = Work + Allocation [i]
• Finish [i] = true
• 2번 과정으로 이동

4. 만약 0 <= i <n에 대해서 Finish[i] == false라면 해당 시스템은 교착상태에 있는 상태입니다. 더욱이 스레드 Ti는 교착상태에 있는 스레드를 의미합니다.

 

현재 사용 가능한 자원(available resource)으로 모든 프로세스 종료 가능한지를 판단한다. 종료 불가하다면 교착상태.

 

Example of Detection Algorithm (교착상태 탐색 알고리즘 예제)

• 위 수행 결과와 같이 Safe Sequence가 계산되므로 위는 교착상태가 없는 상태

 

P2가 추가 자원 C를 원하는 경우

• 수행결과 스레드 T0을 제외한 다른 모든 스레드가교착상태에 빠지게 된다.

 

다른 예시

 

Recovery from Deadlock : Process Termination (교착상태 복구 방법 : 프로세스 종료)

교착상태 복구 방법

• 모든 프로세스 종료
• 프로세스 하나씩 종료하여 교착상태 사이클을 제거
  • 우선순위에 따른 종료 - 우선순위 낮은 프로세스 종료
  • 지금까지 계산 시간, 향후 완료 가능 시간 고려
  • 지금까지 자원의 사용량 기준
  • 향후 추가 자원 필요량 (많은 자원 필요한 프로세스 종료)
  • 종료되는 프로세스 수
  • 대화식 작업(Interactive) or 일괄처리 작업(batch) -> (batch 종료)