Deadlocks

본 자료 정리는 'Operating System Concepts'(Tenth Edition) - Abraham Silberschatz 원서에 출처합니다.
Copyright © 2020 John Wiley & Sons, Inc.

Chapter 8: Deadlocks

• System Model
• Deadlock in Multithreaded Applications
• Deadlock Characterization
• Methods for Handling Deadlocks
• Deadlock Prevention
• Deadlock Avoidance
• Deadlock Detection
• Recovery from Deadlock

Objectives

• Mutex lock(상호배제)을 사용할때 어떻게 데드락이 발생하는지 설명

• 데드락을 특징 짓는 4가지 필수 조건 정의

• 리소스 할당 그래프에서 데드락 상황 식별

• 데드락을 방지하기 위한 4가지 접근 방식 평가

• 데드락을 피하기 위한 banker's 알고리즘 적용

• 데드락 감지 알고리즘 적용

• 데드락으로부터 복구하기 위한 접근 방식 평가

Deadlock

스레드가 한정된 자원에 대해서 경쟁할 때, 만약 자기가 원하는 자원을 다른 애가 사용하고 있다면 자신이 쓸 수 있을 때까지 대기를 한다. 근데, 다른 애가 계속 사용하고 있으면 나는 평생 기다려야한다. 이 상황을 데드락 deadlock이라 한다. (일종의 라이브니스 실패 상황)

즉, 데드락이란 한 프로세스 집합에서 모든 프로세스가 집합의 어떤 한 프로세스가 일으켜야할 이벤트에 대해 대기하고 있는 상태이다.

Example:

아기 A: (자동차 장난감을 갖고) 자동차 내꺼야 리모콘 내놔!
아기 B: (자동차 리모콘을 갖고) 내꺼야 내 자동차 내놔!

-> 둘 다 장난감 이용 못함

System Model

시스템엔 한정된 수의 자원이 있고 자원을 서로 경쟁하는 스레드에게 배분해줘야 한다. 스레드가 어떤 자원형에 대한 개체를 요청한다면, 해당 형을 갖는 임의의 개체를 할당해도 요구사항을 만족한다. 만약 그렇지 않다면 개체가 동일하지 않다는 것이고 자원형 클래스가 제대로 정의가 안 된 것이다.

(상호배제 락, 세마포어도 시스템 자원이다. 요즘 시대에 데드락을 일으키는 가장 일반적인 자원이기도 하다.)

스레드는 자원을 사용하기 전에 반드시 요청을 해야하고, 사용 후 반납해야한다. 원하는 만큼 요청 가능하다.(시스템 총 자원 수 내에서)

다시 말해 시스템에 네트워크 인터페이스가 하나 밖에 없다고 치면, 스레드가 인터페이스를 두 개 이상 요청할 수 없다.

Each resource type Ri has Wi instances.

• e.g. 4 CPUs in a system -> resource type CPU has 4 instances.

• e.g. each instances of a lock -> its own resource class

스레드는 다음 순서로 자원을 사용한다.

• request(요청)

  -> 상호배제 락이 다른 스레드가 사용하고 있는 경우, 자원 받을 때까지 대기해야 한다.

• use(사용)

• release(반납)

request와 release는 시스템콜을 일으킬 수 있다.

장치 -> request()와 release()
파일 -> pen()과 close()
메모리 시스템 콜 -> allocate()과 free()
세마포어의 -> wait()과 signal()
상호배제 락 -> acquire()과 release()

스레드가 커널에서 관리하는 자원을 쓸 경우 ->
스레드의 요청과 할당을 운영체제에서 보장해줘야 한다. (자원이 사용 중인지 아닌지를 기록한 시스템 표가 있다.)

위에서 언급한 데드락의 정의에서 말하는 이벤트란 자원 얻기와 반납을 의미한다. 여기서 말하는 자원은 보통 논리적(상호배제 락, 세마포어, 파일 등)인 애들이지만, 네트워크 인터페이스 혹은 IPC(프로세스 간 통신)로부터 읽어오기 등과 같은 다른 이벤트형도 데드락 문제를 일으킬 수 있다.

Deadlock with Multithreaded Applications

데드락은 시스템 콜, lock 등을 통해 발생할 수 있다.
(e.g. POSIX 뮤텍스 잠금을 사용하는 다중 스레드 프로그램)

• 데드락은 일어날 수도 있고 일어나지 않을 수도 있다.
  (데드락이 발생할 수 있지만 항상 발생하는 것이 아니기에 감지가 어렵다.)

thread 1 이 first_mutex를 얻는 동시에 thread 2가 second_mutex를 얻었다면 데드락이 발생한다.

Livelock

스레드 집합의 모든 스레드가 집합의 다른 데드락이 걸린 스레드에 의해서만 발생할 수 있는 이벤트를 기다리고 있을 때 데드락이 발생한다.

무한 반복 livelock은 라이브니스 실패 중 하나이다.
두 개 이상의 스레드가 앞으로 진전하지 못하게 해준다는 점에서 데드락과 유사하나 그 사유가 다르다.

데드락은 한 놈이 이벤트를 대기 중이라는 사유가 있다면, 무한 반복은 스레드가 계속해서 실패하는 행동을 할 때 발생함.

둘만 건널 수 있는 좁은 길목에서 서로 반대 방향으로 가는 도중 만났다고 가정해보자. 그럼 둘이 중간에 만날텐데, 그럼 한 명은 가만히 있고 다른 한 명이 옆으로 가서 지나치면 되는데, 둘 다 배려심이 넘쳐서 둘 다 옆으로 움직인다.
그럼 또 둘 다 부딪힐텐데, 그럼 또 옆으로 움직인다.

이런 게 무한 반복하는 상황을 livelock이라 한다. 이 경우, 대기 중이 아닌데도 진전이 없게된다.

즉, 스레드가 실패한 작업을 동시에 재시도할 때 livelock이 발생한다.

무한 반복은 보통 스레드가 동시에 실패할 연산을 할 때 발생한다. 그래서 임의의 시간마다 재시작하게 해주는 것으로 회피해줄 수 있다.

이게 네트워크 충돌 일어날 때 이더넷에서 사용하는 전략이다.(e.g. CSMA/CA)

Deadlock Characterization

다음의 4가지 조건이 동시에 성립하면 데드락이 발생할 수 있다.

• Mutual Exclusion (상호배제): 한 번에 하나의 스레드만 리소스를 사용할 수 있다. (최소한 한 자원은 반드시 공유 불가능한 상태여야 한다.)

• Hold and Wait (붙잡고 기다리기): 스레드는 반드시 최소한 한 자원을 붙잡은 상태에서 다른 스레드가 현재 붙잡고 있는 추가적인 자원을 얻기 위해 대기해야한다.

• No preemption (비선점): 자원은 선점될 수 없다. (스레드가 일 볼 거 다 보고 스스로 반납해줘야함.)

• Circular wait (순환 대기): 대기 중인 스레드 집합 { T0, …, Tn }이 다음 규칙에 따라 반드시 존재해야 한다: T0이 T1이 붙잡고 있는 자원을 기다리고, Tn - 1은 Tn이 붙잡고 있는 자원을 기다리고, Tn은 T0이 붙잡고 있는 자원을 기다린다.

Resource-Allocation Graph

데드락은 시스템 자원 할당 그래프 system resource-allocation graph라 부르는 방향성 그래프로 더 정확하게 표현해줄 수 있다.

• 꼭짓점 집합 V와 모서리 집합 E가 있다.

• 정점 V는 두 가지로 분류된다.

  • T = { T1, …, Tn} 은 모든 활성화 스레드
  • R = { R1, …, Rm } 은 모든 자원형.

• request edge - 스레드 Ti에서 자원 Rj로의 방향성 모서리는 Ti → Rj

(즉, 스레드 Ti가 자원형 Rj의 개체를 요청했으며, 현재 대기 중이라는 의미이다.)

• assignment edge - 반대 방향 Rj → Ti의 경우 자원형 Rj의 개체가 스레드 Ti에 할당되었다는 의미이다.

Resource-Allocation Graph 2

스레드는 원으로, 자원은 직사각형으로 보통 그려준다. 요청 모서리는 그냥 화살표, 할당 모서리는 점에서 시작하는 화살표의 형태이다.

Resource-Allocation Graph with a Deadlock

• POSIX 뮤텍스 잠금을 사용하는 다중 스레드 프로그램

스레드 Ti가 자원형 Rj의 개체를 요청하면 요청 모서리가 우선 그래프에 추가된다. 요청이 수행 가능해지면 요청 모서리는 즉시 할당 모서리로 변한다. 더 이상 자원 필요없어지면 자원 반환해주어 할당 모서리가 삭제된다.

4가지 조건을 모두 만족하므로 해당 그래프는 deadlock 상태이다.

Example of a Resource-Allocation Graph

• T, R, E 집합:
  • T = {T1, T2, T3}
  • R = {R1, R2, R3, R4}
  • E = {T1->R1, T2->R3, R1->T2, R2->T2, R2->T1, R3->T3}

• 자원 개체:

  • 자원형 R1 개체 하나
  • 자원형 R2 개체 둘
  • 자원형 R3 개체 하나
  • 자원형 R4 개체 셋

• 스레드 상태:

  • 스레드 T1은 자원형 R2 개체 하나 붙잡고 있고, 자원형 R1 개체 대기 중.
  • 스레드 T2은 자원형 R1 개체 하나랑 자원형 R2 개체 하나 붙잡고 있고, 자원형 R3 개체 대기 중.
  • 스레드 T3은 자원형 R3 개체 하나 붙잡고 있는 중.

  즉, 그래프엔 순환 구조가 없기 때문에 데드락 상태인 스레드가 없다. 만약 순환 구조가 존재한다면 데드락이 있을 수도 있다.

만약 순환 구조 내의 자원이 오로지 하나의 개체만 존재하는 자원형이라면 데드락이 발생한 것이다. 순환 구조 내의 스레드가 데드락 상태인 것. 이 경우 이 그래프 내의 순환구조는 데드락 존재 여부의 필요충분조건이다.

만약 각 자원형의 개체 수가 둘 이상이라면 순환 구조가 있다고 해서 데드락이 발생했다는 건 아니다. (이 경우 순환구조는 데드락의 필요조건이지 충분조건은 아니다.)

만약 스레드 T3가 자원형 R2의 개체 하나를 요청했다고 가정해보면, 현재 받을 수 있는 개체가 없으니 요청 모서리 T3 → R2를 그린다.

이러면 최소한 두 개의 순환이 존재한다:

• T1 → R1 → T2 → R3 → T3 → R2 → T1
• T2 → R3 → T3→ R2 → T2

스레드 T1, T2, T3은 데드락 상태이다.

Graph With A Cycle But No Deadlock

이 그래프의 경우 다음 순환이 존재한다.

• T1 → R1 → T3 → R2 → T1

데드락이 없다. T4가 자원형 R2의 개체를 반납해줄수도 있기때문이다.

Basic Facts

• 만약 그래프에 순환이 없다면? -> 데드락이 없다.

• 만약 그래프에 순환이 있다면?
  -> 자원형 마다 하나의 인스턴스만 있는 경우 데드락
  -> 자원형 마다 인스턴스가 여러 개인 경우 데드락 가능성이 있다.

Methods for Handling Deadlocks

일반적으로 다음 세 가지 방법으로 데드락을 처리 할 수 있다.

• 문제를 무시하고 시스템에서 데드락이 발생하지 않는 척한다.

(데드락이 드물게 발생하고 교착 상태를 처리하는 데 비용이 많이 들기 때문에 Linux 및 Windows를 포함한 대부분의 운영 체제에서 처리하는 방식)

• 다음 프로토콜을 통해 시스템이 절대로 데드락 상태에 빠지지 않게 한다. (커널 개발자/어플리케이션 개발자가 처리)

  • Deadlock prevention
  • Deadlock avoidance

• 시스템이 데드락에 빠지면 이를 감지하고 복구하도록 한다. (데이터베이스와 같은 시스템의 경우)

  • Deadlock detection
  • Recovery from Deadlock

Deadlock prevention

데드락 발생의 네 가지 필수 조건 중 적어도 하나가 유지되지 않도록 한다.

하지만 데드락 사전예방은 현실적으로 어렵기 때문에 이런 방법이 있구나 개념만 알아두면 된다.

• Mutual Exclusion: 공유 가능한 리소스(예: 읽기 전용 파일)에는 필요하지 않다. 그러나 공유할 수 없는 리소스(예: 뮤텍스 잠금)에 대해서는 유지해야한다.

• Hold and wait: hold and wait가 절대안 일어나도록 하려면 스레드가 리소스를 요청할 때마다 다른 리소스를 보유하지 않도록 보장해야한다.

• No Preemption: 비선점을 보장하지 않게 하기 위해 스레드가 어떤 자원을 붙들고 있고, 당장 자신에게 할당될 수 없는 자원을 요청한다면, 스레드가 현재 붙들고 있는 모든 자원을 선점시켜주면 된다.

• Circular Wait: 원형 대기 조건 중 필요조건 하나를 무효화 시키면 된다. 모든 리소스 유형의 총 순서를 부과하고 각 프로세스가 열거 순서대로 리소스를 요청하도록 요구하면 된다.

Deadlock Avoidance

• 가장 간단하고 가장 유용한 모델은 각 스레드가 필요할 수 있는 각 유형의 최대 리소스 수를 선언하는 것이다.

• 데드락 회피 알고리즘은 자원 할당 상태를 동적으로 검사하여 순환 대기 상태가 절대 발생하지 않도록 합니다.

• 자원 할당 상태는 사용 가능하고 할당된 자원의 수와 스레드의 최대 수요로 정의된다.

Safe State

시스템 호출이 각 스레드에 어떤 순서에 따라 자원을 할당하면서도 데드락을 회피할 수 있다면, 안전한 상태(safe state)에 있다고 부른다.

이때, 시스템이 안전할 필요충분조건은 안전 순서 safe sequence의 존재성이다. 연속된 스레드 <T1, …, Tn>가 현재 할당에 대해 안전한 순서려면 각 Ti마다 Ti이 할 수 있는 자원 요청이 현재 사용 가능한 자원 상태 + j < i인 Tj이 붙잡고 있는 자원들에 대해서도 요청 가능해야한다.

이 경우 Ti이 필요로 하는 자원이 당장 사용 불가능하면 Ti는 모든 Tj가 끝날 때까지 대기해야 한다. 다 끝나면 Ti이 그제야 필요한 자원을 전부 얻고 자신의 일을 다 하고 반납하고 종료할 수 있다. Ti이 종료되면 Ti + 1가 자기가 필요한 자원 요청하는 순으로 계속 진행이 된다. 이런 순서가 존재하지 않으면 시스템은 안전하지 않다.

• 시스템이 안전항 상태에 있는 경우
  -> no deadlock

• 시스템이 안전하지 않은 상태에 있는 경우
  -> deadlock의 가능성이 있음

• avoidance
  -> 시스템이 절대 안전하지 않은 상태(unsafe state)에 들어가지 않도록 보장한다.

Avoidance Algorithms

• 자원 유형의 단일 인스턴스

  • resource-allocation graph 사용

• 자원 유형의 다중 인스턴스

  • Banker's algorithm 사용

Resource-Allocation Graph Scheme

만약 각 자원형이 오로지 한 개체(instance)로만 구성되어있으면 자원 할당 그래프를 확장해서 데드락 회피를 해줄 수 있다. (기존 개념에 요청 가능 모서리 claim edge라는 모서리 개념을 추가해주는 것이다.)

요청 가능 모서리(Claim edge) Ti → Rj란 스레드 Ti가 나중에 자원 Rj를 요청할 수도 있다는 의미이다. 그림으로 그릴 땐 요청 선이랑 똑같이 그리되 점선으로 그린다. 요청이 실제로 들어가게 되면 요청 가능 모서리가 요청 모서리로 바뀌게 된다. 마찬가지로 Ti가 자원 Rj를 반환하면, 할당 모서리 Rj → Ti가 요청 가능 모서리 Ti → Rj로 바뀐다.

참고로 자원은 시스템 전(priori)에 요청이 가능해야 한다. 즉, 스레드 실행 이전에 모든 요청 가능 모서리가 이미 그래프 상에 표기되어야 한다는 의미이다. 대신, Ti에 연결된 모든 모서리가 요청 가능 모서리라는 가정하에 실행 전에도 그래프에 그려줄 수 있다.

이제 스레드가 자원을 요청을 하는 경우, 요청 모서리를 할당 모서리로 바꿀 때 전체 그래프에 순환구조가 존재하지 않을 때만 이 요청을 받아줘야 한다. 이때 순환구조 탐지 알고리듬으로 n이 시스템 내의 스레드 수일 때 n2 복잡도로 순환을 탐지할 수 있다.

순환이 없으면 할당해도 안전한 상태가 된다. 순환이 있으면 스레드는 우선 요청을 받아들여도 안전해질 때까지 대기한다.

• T2가 R2를 요청한다고 가정하자. 그렇다면 R2를 T2에 할당해줄 수 있나?
  -> 안된다.

Banker's Algorithm

각 자원형마다 개체(instance)가 여러 개인 자원할당 시스템의 경우 자원 할당 그래프 알고리즘을 적용해줄 수 없다. 그래서 덜 효율적이지만 은행원 알고리즘 (banker's algorithm)을 적용한다.

이 이름은 이 알고리즘을 은행에 적용해서 은행이 더 이상 모든 고객의 요구를 충족시킬 수 없는 방식으로 사용 가능한 현금을 할당하지 않도록 하기 위해 보장해줄 수 있기 때문이다.

새 스레드가 시스템에 추가되면 반드시 필요한 자원형들에 대해 최대 수요를 선언해줘야한다. 이 숫자는 시스템의 총 자원 수를 초과해서는 안 된다. 사용자가 자원을 요청하면 시스템은 이걸 들어줬을 때 안전한지 아닌지를 판단한다.

안전하면 할당해주고, 아니면 안전한 요청이 될 때까지 대기시킨다.

• n= 시스템 안의 스레드 개수, m= 사용가능한 자원의 개수

• Available (사용 가능): 길이 m인 벡터로, 각 자료형마다 사용 가능한 자원의 개수를 의미한다.
  (available[j] = k인 경우, 사용가능한 Rj의 인스턴스가 k개 있다는 뜻이다.)

• Max (최대): n x m 행렬로 각 스레드의 자원형 별 최대 수요를 의미한다.
  (Max [i,j] = k이면 스레드 Ti는 자원 유형 Rj의 최대 k 개의 인스턴스를 요청할 수 있다.)

• Allocation (할당): n x m 행렬로 각 스레드의 자원형 별 할당된 자원의 개수를 의미한다.
  (Allocation[i,j] = k이면 Ti는 현재 Rj의 k 개의 인스턴스에 할당된 것이다.

• Need (수요): n × m 행렬로 각 스레드의 자원별 남은 수요를 의미한다.
  (Need[i,j] = k이면 Ti는 작업을 완료하기 위해 k개의 Rj 인스턴스가 더 필요할 수 있다.)

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

은행원 알고리듬을 단순화하기 위해 몇 가지 표기법을 소개하자면 다음과 같다.

X와 Y가 길이 n의 벡터라 가정한다.
이때 X ≤ Y일 필요충분조건은 모든 i = 1, …, n인 X[i] ≤ Y[i]에 대해 만족하는 경우이다.
즉, X = (1, 7, 3, 2)와 Y = (0, 3, 2, 1)일 경우 Y ≤ X이다.
또한 Y < X라면 Y ≤ X이면서 Y ≠ X인 경우이다.

행렬 Allocation과 Need의 각 행을 벡터로서, 즉 Allocationi, Needi로 표기한다. Allocationi의 경우 스레드 Ti에 현재 할당된 자원을 의미한다. Needi의 경우 스레드 Ti이 작업을 완료하기 위해 앞으로 더 요청할 수도 있는 추가적인 자원의 수를 의한다.

Safety Algorithm

1. Work 및 Finish를 각각 길이 m, n의 벡터라고 가정한다.
   초기화:
   Work = Available
   Finish[i] = false for i = 0, 1, ..., n-1

2. 다음을 만족하는 i 찾기:
   (a) Finish[i] = false
   (b) Needi <= Work
   만약 이를 만족하는 i가 없을 경우, 4단계로 이동

3. Work = Work + Allocation
   Finish[i] = true
   2단계로 이동

4. 모든 i에 관해 Finish[i] == true이면 시스템은 안전한 상태에 있다.

Resource-Request Algorithm for thread Ti

Requesti 는 Ti 스레드에 대한 요청 벡터이다. 만약 Requesti[j] = k 이면 스레드 Ti는 자원형 Rj의 k개의 개체를 원한다.

1. Requesti <= Needi 인 경우, 2단계로 이동한다. 그렇지 않으면 스레드가 최대 요청을 초과했기 때문에 오류 조건을 발생시킨다.

2. Requesti <= Available 인 경우, 3단계로 이동한다. 그렇지 않으면 리소스를 사용할 수 없으므로 Ti는 기다려야 한다.

3. 다음과 같이 상태를 수정하여 요청된 리소스를 Ti에 할당하는 척한다.

• safe인 경우, 리소스가 스레드 Ti에게 할당된다.

• unsafe인 경우, Ti가 반드시 기다려야 하며, 이전 리소스 할당 상태가 복원된다.

Example of Banker's Algorithm 1

• 5 개의 스레드 {T0, T1, T2, T3, T4}
• 3 개의 자원형:
  A (10개의 인스턴스), B(5개의 인스턴스), C(7개의 인스턴스)
  

시스템의 현재 상태

Example of Banker's Algorithm 2

• Need 행렬의 내용물은 Max - Allocation으로 정의한다.

work에 자원 A,B,C 가 (3,3,2) 가 있을 때, 해당 자원으로 실행 가능한 스레드는 우선, T1과 T3이 있다. 따라서 T1, T3 스레드를 우선 실행하며 allocation을 할당한 뒤, 현재 자원 값들을 만족하는 스레드를 살펴보면 모든 스레드가 실행될 수 있다. ((7,4,3)은 모든 스레드의 need를 만족한다.)

따라서 < T1, T3, T4, T2, T0 > 순서가 안전 기준을 만족하므로 시스템은 안전상태이다.
이때 순서는 여러가지가 있을 수 있는데 시퀀스 <T1, T3, T4, T0, T2> 또한 가능하다.

Example: T1 Request1(1,0,2)

Request1 <= Available인지 확인하다. (즉, (1,0,2) <= (3,3,2) -> true)

앞선 내용과 이어서 work엔 (3,3,2)가 있고, Request1이 (1,0,2)를 요청한 경우 work에 자원 (2,3,0)이 남게된다. ((3,3,2)-(1,0,2))

따라서 업데이트 된 자원을 바탕으로 내용을 다시 그리면 다음과 같다.

그리고 좀 이해하고 다시 작성하고 수정해야됨..

Deadlock Detection

• 시스템이 데드락 상태에 진입하도록 허용
• 감지 알고리즘
• 회복 스킴