6주차. DeadLock (prevention, avoidance, detection & recovery, ignore)

데드락 (교착 상태)

• 자신이 가진 자원은 포기하지 않은채 상대방의 자원을 원하는게 맞물린 상태

Deadlock

• 일련의 프로세스들이 서로가 가진 자원을 기다리면 block된 상태

Resource

• 하드웨어, 소프트웨어 등을 포함하는 개념
• i/o device, cpu cycle, memory space, semaphore 등
• 프로세스가 자원을 사용하는 절차 : (1)request → (2)allocate → (3)use → (4)release

Deadlock 발생 조건 4가지

Mutual exclusion

• 매 순간 하나의 프로세스만이 자원을 사용할 수 있다

No Preemption

• 프로세스는 자원을 스스로 내놓을 뿐, 강제로 빼앗을 수 없는 경우

Hold and wait

• 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 갖고 있는다

Circular wait

• 자원을 기다리는 프로세스간에 사이클이 형성 되어야 한다
• 0 → 1 → 2 → ... → 0

Resource-Allocation Graph 해석

R → P : P 프로세스가 R 자원을 갖고 있는 것

P → R : P 프로세스가 R 자원을 요청하고 있는 것

R(i) 내부의 점 : R(i)의 자원의 개수

 

그래프 상황

p1은 r2를 갖고 r1을 요청
p2는 r1, r2를 갖고 r3 요청
p3는 r3 갖고있음
→ 현재 싸이클이 돌지 않고 있으므로 Deadlock 아니다.
3번 프로세스가 r3를 반납하면 p2가 가질수 있고, p2가 r1을 반납하면 p1이 가질 수 있다.

그래프 해석

• 그래프 내에 Cycle이 없으면 Deadlock 아니다

Cycle이 있다면

• 자원 당 개수가 한개라면 Deadlock이다.
• 자원 당 개수가 여러개라면 Deadlock 일 수도 아닐 수도 있다 → 그래프를 보고 판단을 해야한다

 

예시

좌측 경우

r2 → p1 → r1 → p2 → r3 → p3 → r2 : 싸이클 존재

r2 → p2 → r3 → p3 → r2 : 싸이클 존재

• r2의 자원이 2개라서 확인 해봐야 하는데, 싸이클도 2개 존재해서 Deadlock 상황이 맞다

우측의 경우

r2 → p1 → r1 → p3 → r2 : 싸이클 존재

• r2, r1의 자원이 2개씩 있으니 확인해봐야 한다.
• 둘다 남는 자원이 싸이클과 무관한 프로세스에서 사용중이므로 해당 프로세스가 놓아주게 되면 진행이 가능하다.
  따라서 Deadlock이 아니다.

Deadlock 해결 방법 4가지

참고로 현대에는 DeadLock이 발생하든지 말든지 상관하지 않는 Deadlock Ignorance 방식을 취하고 있다. 자주 발생하지 않는 Deadlock을 위해 발생하지 않도록 하기위해 overhead를 갖는것이 비효율적이며 사용자가 문제가 발생하면 프로그램 종료 등 적절한 조치로 해결할 수 있으므로 사용자에게 맡기는 형태이다.

 

데드락이 발생하기 이전에 미리 예방하는 방법 2가지

1. Deadlock Prevention

Deadlock이 발생하지 않도록 미연에 방지 하는 방법

→ deadlock이 발생하는 4가지 조건이 동시에 생기지 않도록 한다

 

1. Mutual Exclusion → 변경 x
   • 따로 건들지 않는다, critical section에 경우 반드시 성립해야한다.
2. Hold and Wait → All hold or No hold
   • 해결방법 1) 프로세스 시작 시 모든 필요한 자원을 할당받게 하는 방법.
   • 단점) 자원을 미리 다 갖게 하면 그동안 그걸 필요로 하는 모든 프로세스는 기다리게 되고 해당 프로세스의 메모리도 커지므로 비효율적이다.
   • 해결방법 2) 자원이 필요할 경우 보유 자원을 모두 내려 놓고 다시 요청한다.
     단점) 자원을 필요로 할때마다 자원을 다 내려놓고 다시 요청해야하므로 매우 반복적인 요청이 발생할 수 있다.
3. No Preemption → preemption
   • 해결방법) process가 어떤 자원을 기다려야 하는 경우 상대가 보유한 자원을 빼앗아서 선점한다. (preemption)
     → State를 쉽게 save하고 restore할 수 있는 자원에서 주로 사용 (CPU, Memory)
     단점) 자원을 빼앗으면 해당 프로세스에 문제가 생기는 경우에는 활용하기 힘들다.
4. Circular Wait → 싸이클 안생기게 하기
   • 해결방법) 모든 자원 유형에 할당 순서를 정해서 정해진 순서대로만 자원을 할당한다.
     → 예를 들어서 3번 자원을 갖고있는 프로세스가 2번 자원을 요청하게 되면, 역순이므로 일단 3번 자원을 놓아야 1번을 요청할 수 있게되고, 2번 요청을 하고 나서야 3번을 요청할 수 있게 되는 구조이다.
     단점 1) 프로세스 작업 진행에 유연성이 매우 떨어진다. 3번 프로세스를 하고 2번 프로세스를 하려면 3번 -> 1번 -> 2번 순서로해야 한다.
     단점 2) 자원에 번호를 어떤 순서로 매겨야할지 정확히 알 수 없다. 마우스, 키보드, 프린터기가 있을 때 어떤순서로 매겨야 맞는건지 알 수 없다.

Deadlock Prevention 결론

→ 자원에 대한 이용률이 나빠지고 (utilization 저하), 시스템 성능이 나빠지고 (throughput 감소), Starvation 문제가 발생할 수 있어서 매우 비효율적이다.

---

2. Deadlock Avoidance

• 자원 요청에 대해 부가정보를 이용해서 Deadlock의 가능성이 없는 경우에만 (자원이 있어도) 자원을 할당해준다.
• 가장 단순한 모델은 프로세스들이 처음 생성될 때 평생 실행동안 필요로 하는 모든 자원의 최대 사용량을 미리 계산해서 선언하도록 하는 방법이다.
• unsafe 상태가 예상되는 요청이면 수락하지 않고 safe상태를 유지한다.

safe state (안전상태)

• 각 프로세스의 기대 자원과 비교하여 가용자원이 더 크거나 같은 경우가 한번 이상인 경우를 말한다.
• 기대자원 : 앞으로 사용할 자원의 총 수, 가용자원 : 현재 사용할 수 있는 자원의 총 수

unsafe / safe

시스템이 safe state에 있다면 → no deadlock

시스템이 unsafe state에 있다면 → possibility of deadlock

-> deadlock avoidance는 시스템이 unsafe state에 들어가지 않는 것을 보장한다.

• Single instance per resource types (인스턴스 당 자원 종류를 하나만 배정)
  • → Resource Allocation Graph algorithm 사용, 자원 할당 그래프
• Multi instance per resource types (인스턴스 당 여러 자원 종류를 배정)
  • → Banker's Algorithm 사용, 자원 할당 표

Case 1 ) single instance per resource types (인스턴스 당 자원 종류를 하나만 배정)

Resource Allocation Graph algoritthm

Claim edge : P(i) → R(j)

• 점선의 경우 : 프로세스 i가 자원 j를 평생에 최소 한번은 요청할 수 있음을 뜻한다
• 실선의 경우 : 프로세스 i가 자원 j를 요청시 request edge(실선)로 바뀐다
• 자원 j가 release되면 assignment edge는 다시 claim edge로 바뀐다

request edge의 assignment edge 변경 시 (점선과 실선 포함해서) cycle이 생지 않는 경우에만 요청 자원을 할당해 준다.

즉 그림의 첫번째 경우에서 R(2)를 프로세스 1 or 2 누구에든 주면 최악의 경우 할당 후 바로 다른 프로세스가 R(2)를 요청해서 Deadlock이 발생할 수 있다. 따라서 R(2)가 할당 가능 상태임에도 아무에게도 할당하지 않게 된다.
→ 최악의 경우를 가정해서 할당하거나 안하게 된다

-> 위 경우 세번째 상황에서 프로세스(1)이 R(2)를 실제 요청하게 되면 deadlock이 발생한다.

 

Case 2) Multi instance per resource types (인스턴스 당 여러 자원 종류를 배정)

조건

• 모든 프로세스는 자원의 최대 사용량을 미리 표시
• 프로세스가 요청 자원을 모두 할당받은 경우 유한 시간내에 해당 자원을 다시 반납

Banker's Algorithm

프로세스 1 ~ 5번, 자원 A(10), B(5), C(7)

• 프로세스 별로 평생동안 사용할 자원의 값을 계산해서 MAX 배열에 저장
• 현재 프로세스에 할당한 자원의 값을 Allocation 배열에 저장
• 여유분 가용 자원을 Available 배열에 저장
• 각 프로세스별로 아직 더 필요로 하는 자원의 값을 Need 배열에 저장

이때, 각 프로세스가 필요로 하는 자원을 그냥 바로 주는것이 아니라 safe 상태를 유지할 경우에만 할당해 준다.

1. 해당 프로세스의 기대 자원의 수 < 가용 자원의 수 에 부합하는 프로세스에게 자원을 할당
   할당 후 프로세스 종료 & 자원 반납 → "가용 자원의 수 += 요청한 프로세스가 할당 받은 자원의 수" 가 된다.
2. 늘어난 가용 자원으로 그다음 조건에 맞는 프로세스가 자원을 받고 처리 반복.
3. 할당 받은 프로세스는 명시된 조건에 따라 종료 후 할당 받은 자원을 모두 반납하게 된다.
4. "기대자원의 수 < 가용 자원의 수" 인 프로세스가 없다면 → unsafe상태이므로 주지 않는다.
5. 위 프로세스의 safe sequence ⇒ <p1, p3, p4, p2, p0> 순서.

예시

Can request for (0, 2, 0) by P(0) be granted?

• 프로세스 0번이 자원 B만을 2개 요청하는 것이 허용될까? → 안된다
• 프로세스 0번의 Need (최대 필요로하는 자원의 값 - 현재 갖고있는 값) 이 총 자원의 개수 보다 크므로
  즉 -> 총 가용 자원 < P(0)의 Need 이므로 최악의 경우를 가정해서 할당해 주지 않는다.

결론

최악의 경우로 가정해서 자원을 할당하게 되므로 매우 비효율적이다. 해당 프로세스가 필요로하는 자원의 최악의 경우가 만족해야만 현재 요청값과 상관없이 받아들이거나 거절하므로, 자원이 남는데도 할당하지 않게 되는 경우가 발생한다.

 

예를 들면 자장면 10개, 탕수육 8개가 준비되어있는 식당에 예약을 8명까지만 받는 것이다. 18명의 손님을 받아서 10개의 자장면과 8개의 탕수육을 줄 수도 있지만, 10명이와서 전부 탕수육만 시킬 수도 있으므로 8명까지만 손님을 받는 매우 보수적인 방법인 것이다.

 

또한, 각 프로세스가 앞으로 사용할 자원을 미리 선언해야 하는데 이 부분에서도 어려움이 있다. 해당 프로세스가 정확히 얼만큼 자원을 사용할 지 특정할 수 없을 뿐더러 이를 위반하면 데드락이 발생하게 되므로 정확한 방어가 되지 않는다.

 

---

데드락이 발생하던 말던 놔두고 발생 시 확인 후 해결하는 방법 3개

3. Deadlock Detection and Recovery

1) Single instance의 경우에서 Deadlock Detection 방법

좌) 자원-할당 그래프, 우) Wait-for-graph 알고리즘

• 좌측의 기존 자원 할당 그래프에서 자원을 빼고 프로세스로만 그래프를 구성한 것이 wait-for-graph이다.
• Resource type당 자원 인스턴스가 한개인 경우에 가능하다.
• 프로세스만을 가지고 그래프를 구현, p(i) → r(k) → p(j) => p(i) → p(j)
• single instance의 경우 → 사이클이 존재하는지 확인하면 된다
• 사이클 확인을 위한 DFS 알고리즘
  DFS 알고리즘을 이용하여 그래프내에 사이클이 존재하는지 확인할 수 있으며 O(n^2)의 시간복잡도를 갖는다. 각 노드는 최대 n - 1개의 간선을 가질수 있으므로 최대 간선의 개수는 N * (N - 1) 이므로 최악의 경우 모든 간선을 확인하기 위해 N^2개를 탐색해야한다

2) Multi instance의 경우에서 Deadlock Detection 방법

• multiple instance의 경우 → banker's 알고리즘과 유사한 방식을 활용하여 확인한다.

상황

최대 사용량을 구하지 않고, 현재 요청하는 자원의 양과 이용 가능한 자원 그리고 현재 할당 받은 자원을 가지고 판단한다

• baker's와 다르게 상황을 매우 낙관적으로 본다. 즉, request가 0, 0, 0인 모든 프로세스의 Allocation 된 자원을 Available에 더하고, 이후 그 것보다 큰 자원을 현재 요청하는 프로세스가 없다면 deadlock은 발생하지 않는 것이다.
• 단, 현재 available에 반납가능한 모든 자원을 더했는데도 요청 자원이 더 크다면 → Deadlock이 발생한 것
• Request는 현재 요청하는 자원만을 나타내는데, 현재 요청 자원이 없다면 할당 받은 자원을 모두 반납할 것이라 가정하고 Available자원에 해당 자원을 쌓고, 그 자원보다 요청 자원값 이내라면 deadlock이 아닌 것으로 본다

3) 타임아웃을 이용한 Deadlock Detection

일정시간 동안 작업이 진행되지 않는 프로세스를 교착상태가 발생한 것으로 간주하여 처리하는 방법이다.

많은 운영체제가 선호하는 방법이다.

 

문제점

• 타임아웃시간 동안 작업이 진행되지 않은 모든 프로세스가 교착 상태 때문에 작업이 이뤄지지 않은 것은 아니다. 교착 이외의 이유로 작업이 진행되지 못하는 프로세스가 강제 종료될 수 있다.

Detection 된 Deadlock Recovery

Process termination (프로세스 종료하는 방법)

1) Abort All deadlocked process

• deadlock과 연류된 모든 프로세스를 죽인다

2) Abort one process at a time

• deadlock과 연류된 프로세스를 하나씩 죽여본다 → deadlock이 풀릴때까지

Resourcee Preemption (자원을 빼앗는 방법)

• 비용을 최소화할 victim 선정
• safe state로 rollback하여 process를 재시작

Starvation 문제

• 동일한 프로세스가 계속해서 victim으로 선정되는 경우 해당 프로세스는 계속해서 일을 수행할 수가 없다.
  → cost factor에 rollback 횟수도 같이 고려해준다.

---

데드락을 완전 무시하는 방법

4. Deadlock Ignorance

• Deadlock이 일어나지 않는다고 생각하고 아무런 조치도 취하지 않는다.
• Deadlock이 매우 드물게 발생하므로 그에 대한 조치 자체가 더 큰 overhead를 가질 수 있다.
• Deadlock이 발생하여 시스템이 느려지거나, 먹통이 되거나 하면 사용자가 이를 감지해서 프로세스를 재시작하는 방법으로 대처할 수 있다.
• 대부분의 OS가 이 방식을 채택하고 있다.