[운영체제] 교착상태 (Deadlock, 데드락)

교착상태 (DeadLock)

✔️ 정의

두 개 이상의 프로세스가 자원을 점유한 상태에서 서로 다른 프로세스가 점유하고 있는 자원을 요구하며, 서로의 작업이 끝나기만을 기다리면서 둘 다 영원히 끝나지 않는 상태이다.

 

 

프로세스가 리소스를 이용하는 흐름

Request → Use → Release

• 요청 (Request)
  • 필요한 자원(resource)을 요청한다.
  • 만약 다른 프로세스가 리소스를 사용중이라서 리소스를 받을 수 없다면 대기
• 사용 (Use)
  • 프로세스가 요청한 자원을 획득해 사용한다.
• 반납 (Release)
  • 프로세스가 리소스를 놓아준다.

✔️ 발생 조건 4가지

다음 4가지 조건을 모두 만족해야 데드락이 발생한다.

• 상호 배제 (mutual exclusion)
  • 적어도 1개 이상의 자원이 공유 불가능해야 함
• 점유 대기 (hold and wait)
  • 스레드가 적어도 1개 이상의 리소스를 점유하고 있는 상태로 대기하고 있어야 함
• 비선점 (no preemption)
  • 자원은 선점이 불가능해야 함
• 순환 대기 (circular wait)
  • 대기 중인 스레드들이 필요로 하는 다른 스레드를 이었을 때 순환 구조를 가져야 함
  • 각 프로세스가 순환적으로 다음 프로세스가 요구하는 자원을 가지고 있는 경우

 

circular wait

 

 

✔️ 처리 방법

1. 예방(prevent)
2. 회피(avoid)
3. 데드락이 발생했을 때 탐지해 복구 (detect, 多)

 

✔️ 교착 상태 예방

운영체제를 설계할 때 교착상태가 발생할 가능성을 없애는 것이다.

따라서 발생 조건 4가지 중 최소 1개 조건을 절대 만족하지 않도록 막는 방법이다.

결론적으로 거의 불가능한 방법임

 

1) 상호 배제 (mutual exclusion) 예방

• 모든 자원을 공유 가능하게 하면 된다.
• ⇒ 상호 배제 조건을 공유 자원의 일관성을 유지하기 위해 반드시 필요하기 때문에 없앨 수 없음

 

2) 점유 대기 (hold and wait) 예방

• 스레드가 자원을 점유한 상태로 기다려서 발생하는 문제였다.
• 자신이 사용할 자원을 한번에 모두 요청해 모든 자원을 할당받을 수 있을 때까지 대기한다.
• ⇒ 매우 비효율적임. 모든 자원을 할당받기 위해 오랜 시간 기다릴 수 있다.

 

3) 비선점 (no preemption) 예방

• 다른 스레드가 점유하고 있는 자원을 선점해 주도권을 뺏을 수 있도록 하면 된다.
• ⇒ 선점당한 스레드가 어떤 작업을 하고 있었는지 모른 채 뺏어버리면 문제가 발생할 수 있음. 따라서 잘 안씀

 

4) 순환 대기 (circular wait) 예방

• 각 리소스마다 순서를 배정해 자원을 요청할 때 가존에 점유하고 있던 자원보다 낮은 순서의 자원은 요청할 수 없도록 한다.
• ⇒ 자원이 순환되지 않게 할 수 있지만 기아 상태(starvation)가 발생할 수 있으며 데드락이 발생하지 않는다는 것을 완벽히 보장 불가능

*기아 상태: 특정 프로세스의 우선순위가 낮아서 원하는 자원을 계속 할당받지 못하는 상태

 

 

✔️ 교착 상태 회피

자원을 할당할 때 교착상태가 발생 가능한 상황으로 진행하지 않도록 고려하는 것이다.

• 스레드의 자원 요청을 받기 전 발생 가능한 데드락이 있는지 확인한다.
  • 이를 위해 자원이 어떻게 요청되었는지에 대한 정보 필요
• 교착상태를 발생시킬 가능성이 있다면 자원을 할당하지 않음

 

 

💫  안전 상태(Safe State)

자원을 각 스레드에 최대치까지 할당할 수 있으며, 스레드의 실행 순서(safe sequence)가 정해져 있어 데드락이 발생하지 않는 상태

↔ 불안전 상태(unsafe state): 교착상태가 될 수 있는 상태

 

 

 

💫 자원 할당 그래프 알고리즘(Resource-Allocation Graph Algorithm)

• 자원 할당 그래프가 오직 1개의 인스턴스를 갖는 자원으로 구성되어 있다고 가정
  • *인스턴스: 일반적으로 실행중인 임의의 프로세스를 가리킨다.
• 자원 할당 그래프를 그려보면서 cycle이 생기지 않게 해 교착상태 회피
• 요청 간선(claim dege)을 그래프에 추가하면서 순환 구조가 발생하는지 판단한다.
• 순환 구조가 없다면 추후 그 요청이 들어왔을 때 허용 가능

 

claim edge를 추가해도 순환 구조가 없는 경우

 

 

• 순환 구조가 있다면 즉시 허용하지 않고 잠시 대기시킴

claim edge를 추가하면 순환 구조가 발생하는 경우

 

 

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

자원의 인스턴스가 여러개인 경우 은행원 알고리즘을 사용한다.

 

 

• n
  • 스레드 개수
• m
  • 자원 개수
• Available[m]
  • 사용 가능한 자원을 나타내는 벡터
• Max [n x m]
  • 각 스레드가 최대로 요구할 수 있는 자원에 대한 행렬
• Allocation [n x m]
  • 각 스레드에 현재 할당되어 있는 자원을 나타내는 행렬
• Need [n x m]
  • 현재 할당되어있는 자원을 제외한 남은 자원

 

 

🌟 안전 알고리즘 (safe Algorithm)

현재 상태가 안전한지 확인하는 알고리즘

1. Work = Available, Finish[i] = false
2. 다음 두 조건을 만족하는 인덱스 i를 탐색
   • Finish[i] = false
   • Need i ≤ Work
3. Work = Work + Allocation i
   • Finish[i] = true
   • 이후 2번으로 이동
4. 모든 i에 대해 Finish[i] = true이면 시스템은 안전 상태인 것이다.
   
   

 

🌟  자원 요청 알고리즘 (resource-request Algorithm)

어떤 요청이 들어왔을 때 허용 가능한지 확인하는 알고리즘

1. Request i ≤ Need i 이면 2번, 그 외는 스레드가 최대 요청(maximum claim)을 넘어선 것이므로 에러 발생
2. Request i ≤ Available 인 경우 3번, 그 외는 자원이 사용 가능하지 않으므로 Ti 스레드는 기다림
3. 시스템은 다음과 같이 상태를 수정해 요청한 자원을 Ti, 스레드에 할당한 것처럼 보이게 함

Available = Available - Request i
Allocation i = Allocation i + Request i
Need i = Need i - Request i

 

 

 

예시

예시

 

처음에 사용 가능한 자원의 개수는

 

현재 할당된 A가 총 7개이므로 10 - 7 = 3

현재 할당된 B가 총 2개이므로 5 - 2 = 3

현재 할당된 C가 총 5개이므로 7 - 5 = 2

 

라서 Available은 3 3 2가 된다.

 

Need는 최대로 요구할 수 있는 양 - 현재 할당된 양이다.

Need = Max - Allocation

 

 

이제 안전 알고리즘을 수행한다.

1. Work = Available = (3, 3, 2) , Finish =(false, false, false, false, false)

 

2. i = 0 ~ 4까지 Need i ≤ Work*인 i 값을 찾음 (벡터의 모든 요소를 하나씩 비교)

i를 찾은 경우 *Work = Work + Allocation i*로 업데이트 + *Finish[i] = true

 

i = 0, (7, 4, 3) ≤ (3, 3, 2) == false

 

i = 1, (1, 2, 2) ≤ (3, 3, 2) == true → Finish[1] = true
→ Work = Work + Allocation1 = (3, 3, 2) + (2, 0, 0) = (5, 3, 2)

 

i = 2, (6, 0, 0) ≤ (5, 3, 2) == false

 

i = 3, (0, 1, 1) ≤ (5, 3, 2) == true → Finish[3] = true
→ Work = Work + Allocation3 = (5, 3, 2) + (2, 1, 1) = **(7, 4, 3)

 

i = 4, (4, 3, 1) ≤ (7, 4, 3) == true → Finish[4] = true
→ Work = *Work + Allocation4 = (7, 4, 3) + (0, 0, 2) = (7, 4, 5)

 

 

 

모든 Finish가 `true`가 아니므로 i = 0으로 다시 돌아감

i = 0, (7, 4, 3) ≤ (7, 4, 5) == `true`  → Finish[0] = `true`
→ Work = Work + Allocation0 = (7, 4, 5) + (0, 1, 0) = (7, 5, 5)

i = 2, (6, 0, 0) ≤ (7, 5, 5) == `true` → Finish[2] = `true`
→ Work = Work + Allocation2 = (7, 5, 5) + (3, 0, 2) = (10, 5, 7)

 

 

 

결론적으로

Work = (10, 5, 7), Finish = (true, true, true, true, true)

T1 -> T3 -> T4 -> T0 -> T2의 순서로 스레드를 실행하면 안전성이 보장된다.

 

 

 

 

---

 

 

 

이 상황에서 T1 스레드가 A 1개, C 2개를 요청한다면 Request1 = (1,0,2)이다.

 

이 요청을 받아들일지 판단하기 위해 자원 요청 알고리즘을 사용한다.

 

1. Request i ≤ Need i 인지 확인
(1,0,2) ≤ (1,2,2) == true

 

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

 

3. Available, Allocation, Need의 값을 각각 Request에 따라 바꿈

 

Available = Available - Request
(3,3,2) - (1,0,2) = (2,3,0)

 

Allocation = Allocation + Request
(2,0,0) + (1,0,2) = (3,0,2)

 

Need = Need - Request
(1,2,2) - (1,0,2) = (0,2,0)

 

바뀐다면..

 

 

가능하군…

이제 다시 안전 알고리즘을 수행해서 이 요청을 받아들여도 되는지 확인한다.

 

문제가 없으면 ㄱㄱ

 

 

 

✔️ 교착상태 탐지

데드락 발생을 허용하되, 지속적인 모니터링을 통해 데드락이 발생하면 즉시 복구하는 방법

 

 

💫  인스턴스가 1개인 경우

대기 그래프(wait-for graph)로 교착상태 탐지 알고리즘 정의

 

 

(a) 자원 할당 그래프 (b) 대기 그래프

 

 

자원 할당 그래프에서 자원에 해당하는 node를 제거하고 각 스레드 사이의 관계만 남겨놓고 cycle을 탐지한다.

 

 

 

💫  인스턴스가 여러개인 경우

은행원 알고리즘과 비슷하게 진행하는데 Need → Request로 바꾼다.

 

 

✔️ 교착상태 복구

탐지 결과 데드락이 발생했다면 복구를 진행할 수 있다.

 

 

💫  프로세스 및 스레드 제거 (process and thread termination)

• 데드락이 발생한 스레드/프로세스를 제거하는 방식
• 1개 없애서 해결되지 않으면 점점 늘리면서 제거함

 

💫  자원 선점 (resource preemption)

• 피해자 선정 (select a victim)
  • 비용을 최소화하는 방향으로 특정 프로세스의 자원을 선점해 요청한 스레드에게 넘겨준다.
• 롤백 (rollback)
  • 프로세스를 안전 상태로 롤백하고 재시작
• 기아 (starvation)
  • 이렇게 되면 계속 선택되는 프로세스가 생기면서 기아 문제가 발생할 수 있다.
  • 따라서 선택되는 횟수를 제한해 무한히 자원을 선점당하는 것을 방지해야 한다.