Deadlock?

In a multiprogramming environment, several processes may compete for a finite number of resources. A process requests resources; if the resources are not available at that time, the process enters a waiting state. Sometimes, a waiting process is never again able to change state, because the resources it has requested are held by other waiting processes. This situation is called a deadlock.
멀티 프로그래밍 환경에서, 프로세스들은 유한한 자원을 두고 경쟁한다. 이 때 프로세스 A가 자원 R을 요청했는데, 자원 R이 현재 이용 불가능하면 프로세스 A는 WAIT상태가 된다. 하지만 종종 자원 R이 다른 WAIT 상태에 있는 프로세스 B가 가지고 있는 상태라면 프로세스 A는 계속해서 WAIT 상태에 있게 되는데 이를 데드락이라고 한다.

starvation 과 deadlock의 차이

데드락은 asleep(blocked) 상태에서 어떤 자원/Event를 기다리는데 일어날 가능성이 zero인 경우이다. 기아는 CPU를 할당 받기를 기다리는데 운이 없어서/우선순위가 밀려서 계속해서 기다리는 상황이다. 하지만 기아는 언젠가 해소될 가능성이 있다.

자원의 분류

데드락은 위에서 보다시피 자원과 굉장히 밀접한 관련이 있다. 한번 자원에 대해 알아보도록 하자.

• 일반적 분류
  Hardware resource vs Software resource
• 다른 분류 법

1. 선점 가능 여부에 따른 분류
   • preemptible resources: 선점 당한 후 , 돌아와도 문제가 발생하지 않는 자원 ex)cpu(processor), memory 등 ( 컨텍스트 스위칭)
   • non-preemptible resources: 선점 당하면 , 이후 진행에 문제가 발생하는 자원. rollback, restart 등 특별한 동작이 필요
     ex) disk drive 같은 경우는 disk에 뭐를 쓰고 있다가 선점 당하면 데이터가 날라감.
2. 할당 단위에 따른 분류
   • total allocation reosurces: 자원 전체를 프로세스에게 할당
     ex)cpu, disk drive
   • partitioned allocation resources : 하나의 자원을 여러 조각으로 나누어 여러 프로세스에게 할당
     ex) memory
3. 동시 사용이 가능 여부에 따른 분류
   • exclusive allocation resources : 한 순간에 한 프로세스만 사용 가능한 자원 ex) cpu, memory, disk drive
   • shared allocation resources: 여러 프로세스가 동시에 사용 가능한 자원
     ex)프로그램(sw), shared data
4. 재사용 가능 여부에 따른 분류
   • SR(Serially reusable ersources) : 시스템 내에 항상 존재하는 자원, 사용이 끝나면 다른 프로세스가 사용가능
     ex) cpu,memory,disk drive,program
   • CR(Consumable resources) : 한 프로세스가 사용한 후에 사라지는 자원 ex)signal, message 등

데드락을 발생시킬 수 있는 자원의 형태

non-preemptible resources , exclusive allocation resources, serially reusable resources
(할당 단위는 영향을 미치지 않음)

CR을 대상으로 하는 데드락 모델-> 너무 복잡

프로세스가 자원을 사용하는 과정

1. Request : The process requests the resource. If the request cannot be granted immediately (for example, if the resource is being used by another process), then the requesting process must wait until it can acquire the resource.
2. Use : The process can operate on the resource (for example, if the resource is a printer, the process can print on the printer).
3. Release: The process releases the resource.

---

데드락이 발생하는 필요 조건

밑에 4가지 조건은 데드락의 필요조건이기 때문에 모두 만족했다고 데드락이 발생하는 건 아닙니다. 4가지 조건을 만족하면 데드락이 발생할 수 있는 것입니다.

자원의 특성 측면

1. exclusive use of resources

At least one resource must be held in a nonsharable mode; that is, only one process at a time can use the resource. If another process requests that resource, the requesting process must be delayed until the resource has been released.

2. non - preemptible resource

Resources cannot be preempted; that is, a resource can be released only voluntarily by the process holding it, after that process has completed its task.
자원이 선점 불가능할 때입니다. 즉 해당 프로세스가 자발적으로 자원을 놓아줘야만 다른 프로세스가 그 자원을 이용할 수 있습니다.

프로세스의 특성 측면

3. hold and wait

A process must be holding at least one resource and waiting to acquire additional resources that are currently being held by other processes
말 그대로 욕심 쟁이.

4. Circular wait

프로세스와 자원의 요청을 그래프로 나타냈을 때 원형을 이루는 것.

---

다음 그림이 데드락인 이유
1. exclusive use of resources : 하나의 차가 소유한 공간(도로)는 공유 불가능
2. non - preemptible resource : 차가 공간을 내어주지 않는 이상 공간(도로)을 가질 수 없음
3. hold and wait : 각각의 차량은 자신의 공간을 가진 채 다른 차가 나오기를 기다리고 있음
4. circular wait : 원형!

데드락 처리 방법

Deadlock Prevention(예방)

4가지 발생 조건 중 하나를 없애면 된다. -> 그렇다면 데드락 발생할 일 없다

1. 모든 자원을 공유 허용

-> exclusive use of reosurce 조건 제거. 현실적으로 불가능

In general, however, we cannot prevent deadlocks by denying the mutual-exclusion condition, because some resources are intrinsically nonsharable.For example, a mutex lock cannot be simultaneously shared by several processes.

2. 모든 자원에 대해 선점 허용

-> non preemptible resources 조건 제거. 현실적으로 불가능.
-> 유사한 방법으로, 프로세스가 할당 받을 수 없는 자원을 요청한 경우 기존에 가지고 있던 자원을 모두 반납하고 작업 취소.
이후 처음부터 다시 시작해야함 => 심각한 자원 낭비 발생(비현실적)

3. 필요한 자원 한번에 모두 할당(totally allocation)

->hold and wait 조건 제거.
-> 자원 낭비 발생(필요하지 않은 순간에도 가지고 있음).
-> 다른 프로세스들은 무한 대기 현상 발생 가능

4. circular wait 조건 제거

-> totally allocation을 일반화 한 방법
-> 자원들에게 순서 부여. 프로세스는 순서의 증가 방향으로만 자원을 요청 할 수 있도록 함. 마찬가지로 자원 낭비 발생.

---

Deadlock Avoidance(회피)

• 시스템의 상태를 계속 감시해야 한다.
• 시스템이 deadlock 상태가 될 가능성이 있는 자원 할당 요청 보류한다.
• 시스템을 항상 safe state로 유지해야 한다.

  프로세스들이 요청하는 모든 자원을, 데드락을 발생시키지 않으면서도 차례대로 모두에게 할당해줄 수 있는 상태라면 이것을 안정 상태에 있다고 말한다.

safe state

• 모든 프로세스가 정상적 종료 가능한 상태
• 즉, safe sequence가 존재하는 상태

  그리고 이처럼, 특정한 순서로 프로세스들에게 자원을 할당하고 실행, 종료 등의 작업을 할 때 데드락이 발생하지 않는 순서를 찾을 수 있다면, 그것을 안전 순서 라고 부른다.

unsafe state

• safe sequence가 존재하지 않는 상태. 데드락의 필요조건.
• 데드락 상태가 될 가능성이 있음
• 반드시 발생한다는 의미는 아님

가정)
1. 프로세스의 수가 고정됨
2. 자원의 종료와 수가 고정됨
3. 프로세스가 요구하는 자원 및 최대 수량을 알고 있음
4. 프로세스는 자원을 사용한 후 반드시 반납한다.
-> 1,2,3이 비현실적

방법1) 다익스트라의 banker's 알고리즘

-> 한 종류의 자원이 여러 개.

• 프로세스가 자원을 요구할 때, 시스템은 자원을 할당한 후에도 안정 상태로 남아있게 되는지 사전에 검사하여 데드락 회피
• 안정 상태라면 자원을 할당하고, 아니라면 다른 프로세스들이 자원을 해제할 때까지 대기

EX) 리소스 R이 10개 존재하고 ,3개의 프로세스 P1,P2,P3가 있을 때 MAX. Claim은 요구한 최대 자원의 수, Cur.Alloc은 현재 할당 받은 자원의 수, Additional Need는 추가로 필요한 자원의 수(Max. Claim - Cur.Alloc)

이 상황에서 현재 사용가능한 자원의 수는 2개이다. 따라서 P1에 먼저 자원을 할당하면 P1은 자원을 사용하고 Release 한다. 그렇게 되면 총 3개의 자원을 사용할 수 있고 P3에 자원 할당하면 그 다음에는 P4에 자원을 할당하면 된다.

방법2) Habermann's 알고리즘

-> 다익스트라 확장
-> 다양한 종류의 자원에 적용

장점: 데드락의 발생을 막을 수 있음.
단점:
-> 오버헤드가 너무 큼(계속 해서 감시해야함)
-> safe state 유지를 위해, 사용 되지 않는 자원이 존재
-> not practical..

---

Deadlock detection and recovery(탐지와 회복)

• An algorithm that examines the state of the system to determine whether a deadlock has occurred.
• An algorithm to recover from the deadlock
데드락 탐지와 리커버리 방식의 시스템은 데드락 탐지 알고리즘과 리커버리 알고리즘을 제공한다.

• 데드락 방지를 위한 사전 작업을 하지 않음-> 데드락이 발생 가능. 발생하면 recovery하자는 마인드.
• 주기적으로 데드락 발생을 확인해야함
  (시스템이 데드락 상태인가? 어떤 프로세스가 데드락 상태인가?)
• RAG 사용해서 데드락 확인

RAG(Resource Allocation Graph)

• 데드락 검출을 위해 사용
• 방향 그래프 , 이분 그래프
• Edge는 Np 와 Nr 사이에만 존재
  • e = (Rj,Pi) : 자원 할당
  • e = (Pi,Rj) : 자원 요청
• Rk : k type의 자원
• tk : RK 의 단위 자원 수
• |(a,b)| : (a,b) edge의 수

Graph reduction

-  주어진 RAG에서 edge를 하나씩 지워가는 방법

- Completely reduced
	• 모든 edge가 제거 됨
	• Deadlock에 빠진 프로세스가 없음

- Irreducible
	• 지울 수 없는 edge가 존재
	• 하나 이상의 프로세스가 deadlock 상태

Unblocked process

Deadlock이 아닌 상태 -> 모든 edge가 제거 됨

Deadlock인 상태 -> 일부 edge가 남음

데드락 탐지 알고리즘은 그럼 언제 사용해야 하나? 이 답은 두 질문에 답에 따라 달라진다.
1. How often is a deadlock likely to occur?
2. How many processes will be affected by deadlock when it happens?
데드락 탐지 알고리즘은 비용 측면에서 비싸기 때문에 언제 데드락 탐지를 할지 또한 중요하다.
ex) 한 시간에 한 번, CPU 사용률이 40프로 미만일 때 등

Recovery 방법

방법1) process termination -> 데드락 상태인 프로세스 중 일부 종료

-> cost model 사용(누굴 terminate할까?)
-> 우선순위 ,종류, 총 수행 시간, 남은 수행 시간, 종료 비용 등을 고려

ex) lowest-termination cost process first
-> simple, low overhead O(p), 불필요한 프로세스들이 종료될 가능성 있음
ex) minimum cost recovery
-> 최소 비용으로 deadlock 상태를 해소 할 수 있는 process 선택=>모든 경우의 수 고려
-> 복잡함. high overhead - O(2^p)

방법2) resource preemption -> 어떤 자원을 뺏을까

• 데드락 상태 해결을 위해 선점할 자원 선택
• 해당 자원을 가지고 있는 프로세스를 종료 시킴
  - 데드락 상태가 아닌 프로세스가 강제 종료 될 수 있음. 해당 프로세스는 이후 재시작 됨
  
• 선점할 자원 선택 방법
  1) preemption cost model 필요
  minimum cost recovery method - O(r)

-> 종료된 애들은 처음부터 수행해야함-> 자원 낭비임.

종료된 애들을 어떻게 효율적으로 다시 실행시킬 것인가? checkpoint 사용

checkpoint restart method

• 프로세스의 수행 중 특정 지점마다 context 저장
• rollback을 위해 사용. 프로세스 강제 종료 후, 가장 최근의 checkpoint에서 재시작
  

---

출처
OS System CPA310 강의
공룡 책