Deadlock

데드락의 개념과 발생되는 조건, 데드락이 발생 되었을 때 처리하는 방법에 대해 끄적끄적 해볼게요~~~~

KOCW 공개 강의: 반효경, 운영체제와 정보기술의 원리

---

Deadlock

프로세스들이 자신의 자원을 내놓지 않고 서로가 가진 자원을 기다리며 block된 상태

• 예시)binary semaphore A, B

  P0 : P(A) → P(B)
  P1 : P(B) → P(A)

  싸이클이 생기면 데드락..

• 프로세스가 자원을 사용하는 절차
  Request → Allocate → Use → Release

---

Deadlock 발생의 4가지 조건

4가지 조건을 모두 만족해야 데드락이 발생합니다. 정보처리기사 단골 문제네요🙂

Mutual exclusion (상호 배제)

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

No preemption (빼앗기지 않음 : 비선점)

프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않음

Hold and wait (보유 대기)

자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있음

Circular wait (환형 대기)
자원을 기다리는 프로세스 간 싸이클이 형성되어야 함

예시) P0은 P1이 가진 자원을 기다림 + P1은 P2가 가진 자원을 기다림 + P2는 P0가 가진 자원을 기다림

---

Deadlock의 처리 방법

(1) Deadlock Prevention

자원 할당 시, 데드락의 4가지 필요 조건 중 어느 하나가 만족되지 않도록 하는 것.

데드락의 조건을 원천 봉쇄하지만 비효율적인 측면이 있다.

→ Utilization 저하, throughput 감소, starvation 문제

• Mutual Exclusion

  공유해서는 안되는 자원의 경우 반드시 성립해야함

• Hold and Wait 자진해서 내놓도록 함

  프로세스가 자원을 요청할 때 다른 어떤 자원도 가지고 있지 않아야 한다.

  방법1 ) 프로세스 시작 시 모든 필요한 자원을 할당받게 하는 방법
  방법2 ) 자원이 필요할 경우, 보유 자원을 모두 놓고 다시 요청

• No Preemption 빼앗도록 함

  프로세스가 어떤 자원을 기다려야하는 경우, 이미 보유한 자원이 선점됨.

  모든 필요한 자원을 얻을 수 있을 때 그 프로세스는 다시 시작된다
  State를 쉽게 save하고 restore할 수 있는 자원에서 주로 사용(CPU, memory)

  → 빼앗을 수 있는 자원은 한정되어 있어서 매번 쓸수있는 방법은 아니다~

• Circular Wait

  모든 자원에 할당 순서를 정하여 정해진 순서대로만 자원 할당

  예를 들어, 순서가 3인 자원 Ri를 보유 중인 프로세스가 순서가 1인 자원 Rj를 할당 받기 위해서는

  Ri를 release해야 한다.

(2) Deadlock Avoidance

자원 요청에 대한 추가 정보를 이용해서 데드락의 가능성이 없는 경우에만 자원을 할당

시스템 state가 원래 state로 돌아올 수 있는 경우에만 자원 할당

→ 자원 당 인스턴스가 하나밖에 없을 땐, 자원할당 그래프 알고리즘 사용

→ 자원 당 인스턴스가 여러 개인 경우, Banker’s 알고리즘 사용

• 자원 할당 그래프 알고리즘

  Claim edge Pi → Rj(점선으로 표시)

  • 프로세스 Pi가 자원 Rj를 미래에 요청할 수 있음을 뜻함

  • 프로세스가 해당 자원 요청 시 request edge(실선)으로 바뀜

  • Rj가 release되면 assignment edge는 다시 claim edge로 바뀐다

세 번째 그림에서 P1이 R2를 지금 요청해버리면 데드락이 형성됩니다.

따라서 2번 그림의 R2는 비록 자원의 여유가 있더라도 P2의 자원 요청을 안전한 상황(싸이클 가능성X)이 될때 까지 가만히 둡니다.

따라서, deadlock avoidance는 request edge → assignment edge 변경 시 점선을 포함하여 cycle이 생기지 않는 경우에만 요청 자원을 할당합니다.

• Banker’s 알고리즘

프로세스가 최대로 요청할 자원이 무엇임을 안다는 전제하에 처리 됩니다.

5개의 프로세스 : P0, P1, .. P4

3개의 자원 : A(10), B(5), C(7) // A는 인스턴스가 10개

[Allocation]

	A	B	C
P0	0	1	0
P1	2	0	0
P2	3	0	2
P3	2	1	1
P4	0	0	2

[Max] 평생 최대로 쓸 자원

	A	B	C
P0	7	5	3
P1	3	2	2
P2	9	0	2
P3	2	2	2
P4	4	3	3

[Available]

	A	B	C
	3	3	2

[Need] Max - Allocation

	A	B	C
P0	7	4	3
P1	1	2	2
P2	6	0	0
P3	0	1	1
P4	4	3	1

• P0가 추가 요청할 수 있는 자원(available)을 전부 요청하는 경우, 남아있는 자원이 더이상 없어서
  데드락의 가능성이 있으므로 자원을 할당해주지 않습니다.

• P1이 자원(available)을 전부 요청하는 경우, 자원을 할당받고나면 더이상 요청하지 않을 것이므로 자원을 할당해줍니다.

→ 가용 자원으로 프로세스의 요청을 처리할 수 있는 경우만 받아줍니다.
프로세스가 자원을 요청하여 작업이 끝난 후, 프로세스가 종료되면 자원을 다시 내놓으므로 가용 자원이 늘어납니다.

따라서 <P1, P3, P4, P2, P0> 순서로 프로세스를 종료 시켜나가다 보면 시스템의 상태는 safe하다~

(참고) safe sequence

Pi(1≤ i ≤ n)의 자원 요청이 가용 자원 + 모든 Pj (j < i)의 보유 자원에 의해 충족되어야

프로세스의 sequence<P1, P2, .., Pn>가 safe합니다.

---

(3) Deadlock Detection and recovery

데드락의 발생은 허용하되 그에 대한 detection 루틴을 두어 데드락 발견 시 recover하는 방법

• 자원 당 인스턴스가 하나인 경우

  자원 할당 그래프를 보고 파악 → 싸이클이 존재하는 경우, 데드락 발생

  wait-for 그래프로 바꿔서 그리게 되면 데드락 발생 여부를 빠르게 파악할 수 있습니다.

• 자원 당 인스턴스가 여러 개인 경우

  데드락 어보이던스와 달리 최대 자원을 평생 얼마나 쓸 지 알 필요가 없습니다.

  여유 자원이 있으면 주는 방법.

5개의 프로세스 : P0, P2…P4
3개의 자원 : A(7), B(2), C(6)

[Allocation]

	A	B	C
P0	0	1	0
P1	2	0	0
P2	3	0	3
P3	2	1	1
P4	0	0	2

[Request] 프로세스가 요청한 자원

	A	B	C
P0	0	0	0
P1	2	0	2
P2	0	0	0
P3	1	0	0
P4	0	0	2

[Available]

A	B	C
0	0	0

P0, P2의 경우 요청 자원이 없으므로 P0,P2가 종료 된 후 이 프로세스들에게 할당된 자원이 가용 자원이 됩니다.

<P0, P2, P3, P1, P4>의 순서대로 처리되면 데드락이 발생되지 않습니다.

cf) 만약, P2가 C를 요청하게 되면 (Request 0 → 1) 데드락이 발생될 수 있습니다.

• 데드락을 Recovery하는 방법

  프로세스를 하나씩 종료(termination)

  자원 빼앗기 : 비용을 최소화하는 희생양이 될 프로세스를 선정하여 자원을 빼앗고 restart.

  → starvation 문제 : 동일한 프로세스가 계속해서 victim으로 선정되는 경우, 비용에 롤백 횟수도 같이 고려

---

(4) Deadlock Ignorance

데드락을 시스템이 책임지지 않습니다.

• 데드락은 매우 드물게 발생하므로 데드락에 대한 처리가 더 큰 오버헤드일 수 있음

• 만약 데드락이 발생한 경우, 사람이 직접 프로세스를 죽이는 방법으로 대처

• UNIX, Windows 등 대부분 범용 OS가 채택하고 있는 방법