CS/운영체제

[공룡책🦖] ch8 Deadlocks

설기똥꼬 2023. 7. 23. 20:13

본 포스팅은 공룡책으로 불리는 Abraham Silberschatz, Peter B. Galvin, Greg Gagne의 『Operating System Concept 10th』 기반으로 정리한 글입니다.

System Model

Multiprogramming 환경에서는 여러 스레드들이 유한한 자원을 두고 경쟁하며 스레드에 분배한다. 

스레드가 다른 대기 중인 스레드가 점유 중인 자원을 요청해 waiting state인 경우가 계속 발생할 수 있다.

이처럼 데드락은 모든 프로세스들이 다른 프로세스의 이벤트를 대기하고 있을 때를 말한다.

 

  • 시스템 모델에서 한정된 리소스로 구성된 시스템을 여러 스레드로 공유해야함
  • 리소스 타입은 여러 개의 동일한 인스턴스 타입으로 구성 : e.g., CPU cycles, files, and I/O devices(such as printers, drive, etc.)
  • 스레드(혹은 프로세스)가 어떤 리소스의 한 인스턴스를 요청시 동일 리소스의 인스턴스를 할당하여 요청을 충족
    • 리소스의 타입이 중요하고, 안의 인스턴스의 개수는 중요하지 않음
  • 스레드가 리소스를 실행할 때 과정
    ⇒ Request(요청) → Use(사용) → Release(해방)

 

 

Deadlock in Multithreaed Applications

서로 hold 중인 lock을 요청하는 상황 (deadlock)

스레드 실행 순서에 따라 데드락이 안 일어 날 수 있다.

스레드2가 lock을 획득하기 전, 스레드1이 mutex1, mutex2에 대한 lock을 획득하고 해제한다.

그러나 특정 스케줄링 상황에서만 발생하는 데드락에 대한 식별과 검사는 어렵다.

 

 

Deadlock Characterization

데드락을 발생시키기 위해 특정 짓는 네 가지 조건이 있다.

 

1. Mutal Exclusion (상호 배제)

  • 어떤 리소스에 접근할 때 순간적으로 하나의 프로세스만 접근할 수 있음
  • 적어도 하나의 리소스가 non-sharable mode

2. Hold and Wait (점유 후 대기)

  • 프로세스는 적어도 하나의 리소스를 점유하고 있고 다른 스레드의 추가 리소스 획득을 대기하고 있음
  • 프로세스가 리소스를 점유하고 있지 않으면, 애초에 데드락이 일어나지 않음.

3. No preemption (선점 불가)

  • 리소스는 선점될 수 없음
  • 선점이 되어버리면 프로세스가 실행을 종료하니 데드락이 일어나지 않음

4. Circular Wait (순환 대기)

  • 프로세스가 순환적으로 서로를 기다리고 있음
  • 스레드 circular RAP
  • T0 → T1 → T2 → ... → Tn → T0

 

Resource-Allocation Graph(RAP)

  • 데드락을 정확하게 묘사한 단방향 그래프
  • 각 정점을 V 라고 칭하며 V에는 두 가지 타입 존재
    • T : 스레드 집합
    •  R : 리소스 집합
  • 각 간선은 E 라고 칭하며 두 가지 타입 존재
    • Ti → Ri (Request edge) Ti가 Ri를 요청
    • Ri → Ti (assignment edge) Rj가 Ti에 할당됨

 

  • 왼쪽 그림 : 순환 대기로 데드락이 일어나지 않은 상황 (만약 그래프 내 사이클이 있다면 데드락 가능성 O)
    • 인스턴스가 하나인 경우 → 사이클은 데드락 의미
    • 인스턴스가 여러 개인 경우 → 사이클이 데드락 의미 X
  • 오른쪽 그림 : T3가 R2에게 리소스를 요청하면서 데드락 발생
    • T1, T2, T3간 데드락 발생

 

  • T1과 T3 사이 사이클이 존재하지만 R2의 인스턴스는 2개
    → T4가 작업을 완료하고 리소스를 놓아주면 T3가 R2에 접근할 수 있으므로 데드락 발생하지 않음

RAP에서 사이클을 그리지 않으면 데드락은 절대 발생하지 않는다.

사이클이 발생한다고 해서 데드락이 무조건 발생하는 것은 아니다.

 

 

 

Methods for Handling Deadlocks

1. 문제 발생 무시 (발생하지 않을 것이라고 가정)

2. 데드락을 방지/회피하기 위한 프로토콜 사용

  • 프로토콜을 이용하여 어떤 상황에서도 데드락에 빠지지 않게 설정
    • Deadlock prevention
    • Deadlock avoidance

3. 시스템이 데드락 상황에 빠진 것을 확인했을 때 회복

  • Deadlock detection
  • Deadlock recovery

 

Deadlock Prevention

  • 데드락을 완전히 방지하는 방법
  • 데드락 발생의 네 가지 조건 중 하나를 완전히 해결해 데드락을 예방하는 방법

 

1. Mutual Exclusion

  • 리소스가 공유할 수 있도록 함
  • 특정 자원은 근본적으로 공유가 불가능하므로 현실적으로 어려움

2. Hold and Wait

  • 프로세스가 리소스를 점유하고 있지 못하게 하는 방법
  • Hold와 Wait을 동시에 하지 않도록 함
  • 프로세스가 리소스를 요청할 때, 가지고 있는 리소스를 모두 내려놓고 리소스를 요청하고, 이후 획득시 가지고 있던 리소스 다시 요청
    • Resource utilization 저하
    • Starvation 발생 가능

3. No preemption

  • 다른 프로세스가 리소스를 점유하고 있을 때 해당 리소스 빼앗을 수 있음
  • 선점당한 프로세스는 어떤 작업을 하든 waiting 상태로 전환
  • 이전 리소스와 새 리소스를 되찾아야 이전 프로세스 실행 가능

 

4. Circular Wait

  • 4가지 방법 중 가장 실용적
  • 리소스에 순서를 부여하여 오름차순으로 리소스를 할당하는 방법
  • 우선순위를 부여하는 것과 마찬가지로 기아 상태가 발생할 가능성 존재

 

Deadlock Avoidance

데드락 방지를 사용하면 디바이스 사용률이 낮아지고, 시스템의 처리량이 감소할 위험이 높아지며 멀티 스레딩으로 얻은 장점이 사라진다.

이를 피하기 위해 데드락 회피 방법을 사용한다.

프로세스들에 배분할 수 있는 자원의 양을 고려해 데드락이 발생하지 않을 정도로 자원을 배분하는 방법이다.

 

  • 프로세스의 리소스 요청을 받을 때 시스템은 발생 가능한 데드락이 있는지 먼저 확인
  • 데드락이 발생하지 않으면 리소스 요청 허용O, 데드락이 발생하면 요청 허용X
  • 얼만큼의 리소스 양이 필요하며 어느 타입의 리소스 요구되는지?
    ⇒ 필요한 정보의 양과 유형에 따라 다양한 회피 알고리즘 존재

 

Safe State

Safe, unsafe, and deadlocked state spaces

  • 시스템이 특정 순서대로 스레드에 리소스를 할당하고 데드락도 발생하지 않는 상태
    • 해당 순서 : 안전 배열(safe sequence)
    • 안전 배열이 있으면 시스템은 safe state(not deadlock state)
  • 데드락을 회피하기 위해서는 알고리즘을 이용하여 안전하지 않은 상태에서 안전한 상태로 이동할 수 없게 설정
  • 안전한 상태의 스레드는 계속해서 안전한 상태로 머물러야 함

 

 

Resource-Allocation-Graph Algorithm

  • 각 리소스 유형의 인스턴스가 한 개만 존재할 때
  • 새로운 간선을 그릴 때 실선이 아닌 점선 → 클레임 엣지(claim edge) (스레드가 나중에 리소스를 요청할 수 있음)
  • 점선을 이용하여 선을 그렸을 때 사이클이 일어나지 않는지 확인
    → 사이클이 그려지지 않으면 안전 상태로 판단
    → 사이클이 그려지면 안전하지 않은 상태로 판단
  • 사이클이 발견되면 스레드는 요청이 충족될 때까지 wait

 

Banker's Algorithm

  • RAG는 multiple instance에 사용못하기에 은행원 알고리즘 사용
    • 여러 인스턴스가 있을 때 데드락 회피를 위한 방법으로 적합
    • RAG에 비해 복잡하고 효율이 떨어짐
  • 리소스의 최대 개수를 할당해도 안전한 상태가 유지되는지 확인
  • 안전하지 않은 상태면 다른 스레드가 자원 해제할 때까지 wait

 

Data structures for Banker's Algorithm

  • n : 시스템에 있는 스레드의 수
  • m : 시스템에 있는 리소스의 수
  • Available : 사용 가능한 리소스의 인스턴스 수
  • Max : 각 스레드가 요청할 인스턴스의 최대 수
  • Allocation : 각 스레드에 할당된 리소스의 수 
  • Need : 앞으로 요청할 리소스의 수
  • Request : 스레드가 요청한 리소스의 수 

 

Safety Algorithm

1. Work, Finish 벡터를 아래와 같이 초기화한다.
	Work = Available, Finish[i] = false
    
2. 아래의 두 조건을 만족하는 인덱스를 찾는다.
	Finish[i] == false, Need[i] <= Work
	만족하는게 없다면 4번으로 간다.
	조건을 만족한다면 아래를 실행한다.

3. Work = Work + Allocation[i]
	Finish[i] = true
	다시 2번으로 돌아가 끝날 때까지 반복한다.
    
4. 만약 Finish[i]가 모두 true라면, 안전한 상태라는 의미이다.

 

 

Resource - Request Algorithm

1. Request[i] <= Need[i] 이면 2번으로 간다.
	반대의 경우 최초 등록한 Max 보다 더 많은 양의 리소스를 요청했다는 것을 의미한다.
    
2. Request[i] <= Available[i] 이면 3번으로 간다.
	반대의 경우 할당 가능한 인스턴스의 양보다 요청 양이 더 많다는 것을 의미한다.

3. 요청을 받아주며 아래의 식을 적용한다.
	Allocation[i] = Allocation[i] + Request[i];
	Available = Available - Request[i];
	Need[i] = Need[i] - Request[i];

4. 이 후 다시 위의 안전 알고리즘을 적용하여 안전한 상태라면 리소스를 완전히 할당한다.

 

 

Deadlock Detection

  • 데드락이 일어났는지 확인하기 위한 시스템 상태를 검사하는 알고리즘
  • 데드락을 허용하고 발생하는지 감시하고, 데드락에 빠지면 그 때 복구

 

Single Instance of Each Resource Type

  • 리소스에 인스턴스가 1개 있는 경우에는 위의 RAG를 변형한 wait-for graph 사용
  • 주기적으로 알고리즘을 실행하여 사이클이 있는지 확인
  • 그래프에서 리소스를 제외

 

Several Instances of a Resource Type

  • 은행원 알고리즘을 변형하여 데드락 탐지
1. Work = Available 로 초기화하고, Allocation[i] 가 0이면 Finish[i] 를 true로 설정한다.

2. 아래의 두 조건을 만족하는 스레드를 찾는다.
	Finish[i] == false, Request[i] <= Work
	마찬가지로 조건에 만족하는 스레드가 없다면 4번으로 간다.
    
3. 아래의 두 연산을 실행한다.
	Work = Work + Allocation[i], Finish[i] == true
    
4. Finish[i] == false 이면 해당 스레드는 데드락이 발생한 상태임을 의미한다.

 

Recovery from Deadlock

데드락 발생을 확인한 후 처리할 복구 작업이 여러 가지 있다.

 

1. Process and Thread Termination

  • 데드락에 걸린 모든 프로세스를 종료하는 방법
  • 오래 실행되던 프로세스 중지되고 나중에 다시 실행

 

2. Resource Preemption

  • Selecting a victim : 희생할 리소스를 선점(비용 최소화)
  • Rollback :요청한 스레드에 주고 안전한 상태로 후퇴 후 다시 시작
  • Starvation : 동일 프로세스가 항상 선점되지 않도록 보장