[OS] Deadlock

본 글은 반효경 교수님의 운영체제 강의를 들으며 정리하는 글 입니다.

 

이번 시간에는 서로가 필요로 하는 자원을 가지고 있어 어느 한쪽도 실행되지 못하고 기다리는 DeadLock에 대하여 알아보자.

 

1. DeadLock

일련의 프로세스들이 서로가 가진 자원을 기다리며 block된 상태를 말한다.

예를 들면 다음 그림과 같다.

1 - 1) Resource (자원)

하드웨어, 소프트웨어 등을 포함하는 개념으로, 다음과 같은 예시들이 있다.

ex) I/O device, CPU cycle, memory space, semaphore 등

 

프로세스가 자원을 사용하는 절차는 우측과 같다 -> Request, Allocate, Use, Release

 

1 - 2) 예시

• 1번째 예시
  • 시스템에 2개의 tape drive가 있다.
  • 프로세스 P1과 P2 각각 하나의 다른 tape drive를 보유한 채 다른 하나를 기다리고 있다.
• 2번째 예시
  • 이진 세마포어 A와 B가 있다.
  • 프로세스 P0이 A 자원을 얻은 상태에서 context switch가 발생하여 프로세스 P1에게 CPU 제어권이 넘어갔고, 프로세스 P1가 B 자원을 얻었다.
  • 다시 context switch가 발생하여 프로세스 P0에게 CPU 제어권이 넘어갔고, 프로세스 P0이 B 자원을 얻고 싶어하지만 이미 프로세스 P1가 B 자원을 가지고 있다.
  • 마찬가지로 프로세스 P1이 A 자원을 얻고 싶어하지만 이미 프로세스 P0이 A 자원을 가지고 있다.
  • 무한히 서로를 기다린다. (DeadLock 발생!)

 

2. 데드락이 발생할 4가지 필요 조건

2 - 1) Mutual exclusion (상호 배제)

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

 

2 - 2) No preemption (비선점)

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

 

2 - 3) Hold and wait (보유 대기)

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

 

2 - 4) Circular wait (점유 대기)

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

• 프로세스 P0, P1, ... , Pn이 있을 때
  • P0은 P1이 가진 자원을 기다림.
  • P1은 P2가 가진 자원을 기다림.
  • P(n-1)은 Pn이 가진 자원을 기다림.
  • Pn은 P0이 가진 자원을 기다림.

 

3. Resource-Allocation Graph (자원 할당 그래프)

정점은 프로세스 혹은 자원을 나타내며, 간선은 자원을 요청하거나 할당한다는 의미이다.

 

동그란 process P1을 예시로 생각해보면,

P1은 R1 자원을 요청한 상태이며, R2 자원은 가져다 사용하고 있는 상황이다.

 

3 - 1) 데드락 판단

 

▶ 그래프에 cycle이 없으면 데드락이 아니다.

▶ 그래프에 cycle이 있으면

• 자원 당 하나의 인스턴스만 있는 경우에는 데드락이다.
• 자원 당 여러 인스턴스가 존재하는 경우에는 데드락 가능성이 있다.

 

왼쪽 그래프는 P1에게 R2 자원 1개가 할당되어 있고, P2에게 R2 자원이 할당되어 있는 상황에서 P3가 R2 자원 하나를 요구한다.

P2는 R3 자원을 요청하고, R3는 P3가 가지고 있다. 이때 P1은 R1을 요청하지만, 이것은 P2가 가지고 있으므로 모든 프로세스가 자원을 반납할 수 없다. (데드락)

 

오른쪽 그래프는 P1에게 R2 자원이 할당되어 있고, P4에게 R2 자원이 할당되어 있는 상황이다.

P3가 R2 자원을 요구하고 있는데, P4가 R2 자원을 다 사용한 후 반납하면 되므로 문제가 없다. (데드락 아님)

 

4. 데드락의 처리 방법

데드락 처리 방법으로 다음 4가지가 있는데, 1, 2번 방식은 데드락을 사전에 방지하는 방식이고 나머지 3번은 발생했을때 처리하는 방식, 4번은 그냥 무시하는 방식이다.

 

4 - 1) Deadlock Prevention

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

 

4 - 2) Deadlock Avoidance

자원 요청에 대한 부가적인 정보를 이용해서 데드락의 가능성이 1%도 없는 경우에만 자원을 할당한다.

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

 

4 - 3) Deadlock Detection and recovery

데드락 발생은 허용하되, 그에 대한 탐지 루틴을 두어 데드락 발견시 회복 처리를 수행한다.

 

4 - 4) Deadlock Ignorance

데드락을 시스템이 책임지지 않고 그냥 무시한다. 사람이 직접 해결해줘야 한다.

UNIX를 포함한 대부분의 OS가 채택하는 방식이다.

이는DeadLock이 생각보다 발생할 확률이 적기 때문이다. 발생할 확률도 적은 상황의 문제를 처리하기 위해 위 1, 2, 3번의 방식을 도입하는 것은 overhead가 더 큰 작업이기 때문이다.

 

5. Deadlock Prevention

데드락 예방 같은 경우 위에서 살펴봤던 데드락이 발생할 4가지 조건중 어느 하나를 원천적으로 차단하여 데드락 상태에 빠지지 못하도록 하는 방식이다.

 

5 -1) Mutual Exclusion

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

 

5 - 2) Hold and Wait 

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

 

방법 1. 프로세스 시작 시 모든 필요한 자원을 할당 받게 하는 방법

방법 2. 자원이 필요할 경우 보유 자원을 모두 놓고 다시 요청

 

5 - 3) No Preemption

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

모든 필요한 자원을 얻을 수 있을 때 그 프로세스는 다시 시작되는 방식이다. 다만 이럴경우 자신이 자원을 사용하던 상태를 저장해둬야 하기 때문에, 상태를 쉽게 저장하고 복구할 수 있는 자원에서 주로 사용된다. (CPU, memory)

 

5 - 4) Circular Wait (순환 대기)

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

ex) 순서가 3인 자원 Ri를 보유 중인 프로세스가 순서가 1인 자원 Rj를 할당 받기 위해서는 우선 자신의 Ri를 반납해야 함

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

 

6. Deadlock Avoidance

자원 요청에 대한 부가 정보를 이용해서 자원 할당이 데드락으로부터 안전한지를 동적으로 조사해서 안전한 경우에만 할당하는 방식이다.

가장 단순하고 일반적인 모델은 프로세스들이 필요로 하는 각 자원별 최대 사용량을 미리 선언하도록 하는 방법이다.

 

시스템이 안전 상태에 있으면 데드락이 아니며, 불안전 상태에 있으면 데드락의 가능성이 있다.

Deadlock Avoidance 방식은 이러한 데드락이 발생할 가능성이 조금이나마 있다면 자원이 충분한 상황일지라도 자원을 할당해주지 않는다. 즉, Deadlock Avoidance는 시스템이 불안전 상태에 들어가지 않는 것을 보장한다.

 

자원 유형 당 1개의 인스턴스만 존재하는 경우

-> 자원 할당 그래프 알고리즘 이용

 

자원 유형 당 여러 개의 인스턴스 존재하는 경우

-> Banker's 알고리즘 이용

 

6 - 1) safe state

시스템 내의 프로세스들에 대한 safe sequence(안전 순서열)가 존재하는 상태

 

6 - 2) safe sequence (안전 순서열)

프로세스의 sequence <P1, P2, ... , Pn>가 안전하려면 Pi (1 ≤ i ≤ n)의 자원 요청이 “가용 자원 + 모든 Pj (j < i)의 보유 자원”에 의해 충족되어야 한다.

 

Process가 N개가 있고, 가용자원이 남이 있는 상황이다. 이들 Prcoess중에는 가용 자원만 가지고 최대 요청을 처리할 수 있는 Process가 있을것 이다. 그 Process에게 가용자원을 투자하면, 자신의 작업을 수행한후, (투자한 자원 + 해당 process가 처음 가지고 있던 자원)을 반납하기 때문에 가용자원이 늘어나는 것 이다!

 

따라서 위 조건을 만족하면 다음 방법으로 모든 프로세스의 수행을 보장할 수 있다.

Pi의 자원 요청이 즉시 충족될 수 없으면 모든 Pj (j < i)가 종료될 때까지 기다린다.

P(i-1)이 종료되면 Pi의 자원 요청을 만족하여 수행한다.

 

6 - 3) 자원 할당 그레프 알고리즘

• Claim edge (예약 간선) Pi → Rj
  • 프로세스 Pi가 자원 Rj를 미래에 요청을 할 수 있음을 뜻함 (점선으로 표시)
  • 프로세스가 해당 자원 요청 시 request edge(요청 간선)으로 바뀜 (실선으로 표시)
  • Rj가 반납되면 assignment edge(할당 간선)은 다시 예약 간선으로 바뀐다.
• 요청 간선의 할당 간선 변경 시 (점선을 포함하여) 사이클이 생기지 않는 경우에만 요청 자원을 할당한다.
• 사이클 생성 여부 조사시 프로세스의 수가 n일 때 O(n^2) 시간이 걸린다.

 

6 - 4) Banker's 알고리즘

• 가정
  • 모든 프로세스는 자신이 사용할 수 있는 자원의 최대 사용량을 미리 명시한다.
  • 프로세스가 요청 자원을 모두 할당받은 경우 유한 시간 안에 이들 자원을 다시 반납한다.
• 방법
  • 기본 개념: 자원 요청시 안전 상태를 유지할 경우에만 할당(즉, 가용자원량이 최대 사용량을 넘지 않는경우에만 할당)
  • 요청 자원의 수가 가용 자원의 수보다 적고, 가용 자원수가 Need보다 큰 프로세스를 선택 (그런 프로세스가 없으면 불안전 상태)
  • 그런 프로세스가 있으면 그 프로세스에게 자원을 할당
  • 할당받은 프로세스가 종료되면 모든 자원을 반납
  • 모든 프로세스가 종료될 때까지 이러한 과정을 반복

 

▶ 예제

• A 자원은 10개의 인스턴스, B 자원은 5개의 인스턴스, C 자원은 7개의 인스턴스가 존재한다.
• Allocation은 현재 각 프로세스에 할당된 자원의 수를 뜻한다.
• Max는 각 프로세스마다 최대로 할당 받고 싶은 자원의 수를 뜻한다.
• Available은 각 자원이 프로세스에게 추가로 할당 할 수 있는 가용 자원의 수를 뜻한다.
• Need는 각 프로세스가 현재 최대로 필요로 하는 자원의 수를 뜻하며, Max에서 Allocation을 뺀 값이다.
• 자원은 현재 가용 자원을 보고, Need자원 이상을 줄 수 있는 프로세스를 하나도 찾지 못하면 불안전한 상태가 된다.
• 있다면 해당 프로세스에게 자원을 주고, 프로세스가 끝날 때 모든 자원을 가져온다.
• 이 과정을 반복하면 <P1, P3, P4, P2, P0>라는 안전 순서열을 만들 수 있다.

예를 들어 P0같은 경우 B자원 1개만을 필요로 하고 있다. 또한 가용 자원이 B가 3개가 있기 때문에 할당할수도 있다.

하지만, Banker's 알고리즘에서는 P0가 최대 A:B:C = 7:4:3개를 요청할수도 있다 판단했기 때문에 설령 지금은 1개만 요청하여 자원을 줄 수 있는 상황일지라도 자원을 할당해주지 않는다.

즉, Deadlock이 발생할 조금의 가능성이라도 있다면 자원을 할당해주지 않는다.

 

7. Deadlock Detection and Recovery

7 - 1) 데드락 탐지

• 자원 유형 당 하나의 인스턴스만 존재
  • Wait-for 그래프 알고리즘
    • 자원 유형 당 하나의 인스턴스만 존재
    • Wait-for 그래프
      • 자원 할당 그래프의 변형
      • 프로세스만으로 node 구성
      • Pj가 가지고 있는 자원을 Pk가 기다리고 있는 경우 Pk → Pj
    • 알고리즘
      • Wait-for 그래프에 cycle이 존재하는지 주기적으로 조사
      • 시간 복잡도는 O(N^2)
• 자원 유형 당 여러 개의 인스턴스가 존재
  • 은행원 알고리즘과 유사한 방법 활용

 

▶ Wait-for 그래프 (자원 당 하나의 인스턴스)

자원을 빼 버리고 실선을 이으면 된다. 여기서 Cycle이 생기는지를 확인하면 된다.

 

▶ Banker's 알고리즘 변형 (자원 당 여러 개의 인스턴스)

• Request는 추가 요청 가능량이 아니고 현재 실제로 요청한 자원량을 나타낸다.
• <P0, P2, P3, P1, P4> 라는 안전 순서열이 존재하므로 데드락이 아니다.
• 기존 은행원 알고리즘에 비해 현재를 중시하고 낙관적인 알고리즘이라 볼 수 있다.

 

7 - 2) 데드락 회복

• 프로세스 종료

1) 모든 데드락 상태인 프로세스를 강제 종료

2) 데드락 사이클이 없어질 때까지 하나씩 프로세스를 강제 종료

2번 방식은 Process하나를 죽여봤는데 자원이 부족하다면, 그때 또다른 Process를 죽여보고, 이를 반복하는 방식이다.

 

• 자원 선점
  • 비용을 최소화할 희생 프로세스를 선정
  • 안전 상태로 롤백하여 프로세스를 재시작
  • Starvation 문제
    • 동일한 프로세스가 계속 희생 프로세스로 선정되는 경우
    • 비용 요소에 롤백 횟수도 같이 고려해야 함 (단순히 비용만 최소화하면 안 된다는 뜻)

 

8. Deadlock Ignorance

데드락이 일어나지 않는다고 생각하고 아무런 조치도 취하지 않는 방식이다.

 

데드락이 매우 드물게 발생하므로 데드락에 대한 조치 자체가 더 큰 오버헤드일 수 있기 때문이다.

만약, 시스템에 데드락이 발생한 경우 시스템이 비정상적으로 작동하는 것을 사람이 느낀 후 직접 프로세스를 죽이는 등의 방법으로 대처함

UNIX, Windows 등 대부분의 OS에서 채택하였음

 

참조

https://core.ewha.ac.kr/publicview/C0101020140415131030840772?vmode=f 

반효경 [운영체제] 17. Deadlocks 2

https://steady-coding.tistory.com/547

[반효경 운영체제] Deadlock 1 & 2