[운영체제] Deadlocks(교착상태)

Deadlocks (1), (2)

🔊 이화여자대학교 반효경 교수님의 KOCW 2014년 1학기 운영체제 강의를 들으며 정리한 노트입니다.
      캡쳐한 이미지 중 따로 출처 명시를 하지 않은 이미지 또한 반효경 교수님 강의 자료에 있음을 밝힙니다.

The Deadlock Problem

• Deadlock

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

• Resource (자원)

  • 하드웨어, 소프트웨어 등을 포함하는 개념

  • (예) I/O device, CPU cycle, memory space, semaphore 등

  • 프로세스가 자원을 사용하는 절차

    • Request, Allocate, Use, Release

      프로세스가 자원을 사용하는 절차는 크게 네 단계를 거치게 되있다.
      자원을 요청하는 단계, 요청한 다음에 자원을 획득하는 단계, 자원을 얻은 다음에 사용하는 단계, 사용이 끝났으면 반납하는 단계

• Deadlock Example 1

  • 시스템에 2개의 tape drive가 있다

  • 프로세스 P₁과 P₂ 각각이 하나의 tape drive를 보유한 채 다른 하나를 기다리고 있다

    테잎 드라이브가 2개 있는데, 프로세스가 하려는 역할은 하나의 테잎 드라이브에서 읽어가지고 다른 테잎 드라이브에다가 카피 작업을 하고 싶은 경우를 생각해보자. 그럴 때, 두 프로세스가 각각 테잎 두개를 다 점유해야지만 한쪽에서 카피해서 다른 쪽에 집어넣을텐데 P₁는 테잎 하나를 가지고 있고, P₂도 또다른 테잎 드라이브를 가지고 있는 채로 상대방이 가진 자원을 계속적으로 요구하게 되면 어느 누구도 더이상 진행이 안되는 Deadlock 상태에 도달
    (이런건 하드웨어 자원을 기다리면서 Deadlock이 된 경우)

• Deadlock Example 2

  • Binary semaphores A and B

  • P0	P1
    P(A);	P(B);
    P(B);	P(A);

    (소프트웨어 자원을 기다리면서 Deadlock이 되는 경우)
    2개의 프로세스가 락을 거는 세마포어 2개를 획득해서 뭔가 일을 하고 싶은 것임. 그런데, 프로세스 0번은 A를 먼저 획득한 다음에 B를 획득하려고 하는 상황에서 CPU를 빼앗기고 프로세스 1번은 B를 획득한 다음에 A를 획득하고 싶은 상황인데 이미 A는 프로세스 0번이 가지고 있다. 그래서, 이 상황에서는 CPU가 어느 누구한테 가더라도 둘 중에 하나는 획득이 안되기 때문에 Deadlock 상황에 이르게 되는 것이다.

Deadlock 발생의 4가지 조건

4가지 조건이 동시에 성립할 때 발생한다
4가지 조건 중 하나라도 성립하지 않는다면 교착 상태를 해결할 수 있다

• Mutual exclusion (상호 배제)

  • 매 순간 하나의 프로세스만이 자원을 사용할 수 있음
    (상대를 고려하지 않고, 독점적으로 사용)

• No preemption (비선점)

  • 프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않음
    (자원을 빼앗길 수가 있으면 Deadlock은 생기지 않음)

• Hold and wait (보유 대기)

  • 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있음
    (내가 가진 자원은 내어놓지 않으면서 추가적으로 자원을 요청해야지만 Deadlock이 생긴다)

• Circular wait (순환 대기)

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

  • 프로세스 P₀, P₁, …, P_n이 있을 때

    P₀은 P₁이 가진 자원을 기다림
    P₀은 P₂가 가진 자원을 기다림
    P_n-1은 P_n이 가진 자원을 기다림
    P_n은 P₀이 가진 자원을 기다림

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

Deadlock이 발생했는지를 알아보기 위해서 자원할당그래프라는 것을 그려서 알아보게 된다.

• Vertex
  • Process P = {P₁, P₂, …, P_n}
  • Resource R = {R₁, R₂, …, R_m}
• Edge
  • request edge P_i → R_j
  • assignment edge R_j → P_i

그림을 보면 동그라미는 프로세스를 나타내고 있고, 사각형은 자원을 나타내고 있다. 그리고, 동그라미와 사각형 사이에 화살표들이 있다. 화살표는 2가지 종류가 있는데 한 가지는 자원에서 프로세스 쪽으로 나가는 화살표고, 또 한 가지는 프로세스에서 자원 쪽으로 나가는 화살표이다.

(그림 맨 왼쪽 화살표들을 보자)
자원에서 프로세스 쪽으로 나가는 화살표의 의미는 이 자원이 지금 이 프로세스에 속해 있다. 즉, 이 프로세스가 이 자원을 가지고 있다는 의미.
프로세스에서 자원 쪽으로 가는 화살표는 지금 이 프로세스가 이 자원을 요청을 한 것, 요청을 했는데 아직 획득하지는 못한 상태임

그리고 R₂ 사각형 안에 작은 점들이 있다. 이것은 자원의 수(인스턴스)를 얘기하는 것이다. R₄ 자원은 3개가 있는 것임 3개가 있다는 얘기는 아무거나 필요하면 어느 것을 가져가서 써도 상관은 없는 상황이다.

그럼 이 상황이 Deadlock이냐 아니냐? 그것을 체크해봐야 된다.
먼저, P₁(프로세스 1번)은 2번 자원을 가지고 있으면서 1번 자원을 기다리고 있는데, 그 1번 자원은 지금 P₂가 가지고 있다. 그리고, P₂는 2번 자원을 하나 가지고 있으면서 3번 자원을 기다리고 있는데, 3번 자원은 P₃한테 가있는 상황
이게 과연 데드락이냐 아니냐? 데드락인지 아닌지를 자원할당그래프에서 알 수 있는 방법은 일단 그래프 안에 사이클이 없으면 데드락이 아니다. (화살표를 따라가 보자)

• 그래프에 cycle이 없으면 deadlock이 아니다
• 그래프에 cycle이 있으면
  • if only one instance per resource type, then deadlock
  • if several instances per resource type, possibility of deadlock

왼쪽 그림의 경우 두개의 사이클이 있고, 오른쪽 그림의 경우 하나의 사이클이 있음. 사이클이 없는 상황은 아님. 그럼 둘다 데드락일까? 데드락일 수도 있고 아닐 수도 있음.

만약 자원 당 인스턴스가 하나밖에 없으면 사이클은 곧 데드락을 의미함, 만약에 자원의 인스턴스가 여러개 있는 상황이라고 하면 데드락일 수도 있고, 아닐 수도 있다.

왼쪽 그림 상황은 데드락이다. 비록, 자원의 인스턴스가 2개 있지만 사이클이 두개가 만들어져갖고 인스턴스 2개가 있는데도 불구하고 더이상 진행이 전혀 불가능한 상황이 됨.
오른쪽 그림 상황은 사이클이 만들어져 있긴 한데, 사이클과 관련된 자원이 2개씩이 있고 2개가 다 할당이 되있는 상황이지만 데드락은 아니다. 왜냐하면, 프로세스 1번은 자원 1번을 요청했는데 그 자원이 2개가 있는데 하나는 3번 프로세스한테 가있고, 3번은 2번 자원을 요청했는데 그 자원 중 하나는 1번한테 가있고, 하나는 4번 프로세스한테 가있다. 만약에, 이 자원이 하나씩 밖에 없다면 1번하고 3번 프로세스 둘이서 서로 가진 자원을 가지면서 데드락이 만들어졌을 것이다.
그러나, 여분의 자원이 하나씩 더 있고, 그 자원은 2번 프로세스하고 4번 프로세스가 가지고 있는데 이 2개의 프로세스는 데드락에 연루된 프로세스는 아니다. 그래서, 4번 프로세스가 만약에 자원을 가지고 있지만 쓰고나서 반납을 하면 사용 가능해지고 그때 이 자원을 3번 프로세스가 획득하면 사이클이 없어짐, 또는 2번 프로세스가 가진 자원을 반납하면 그것을 1번 프로세스한테 내어주면서 사이클이 없어질 것이다.
그래서, 이 상황은 자원이 여러개 인스턴스가 있기 때문에 사이클이 있지만 데드락이 생기지 않은 경우이다.

그러나, 더 위에서 봤던 이 상황은 어떤가? 되돌아오는 화살표들은 없다.
즉, 사이클이 없으므로 Deadlock이 아닌 상황이다.

Deadlock의 처리 방법

• Deadlock Prevention

  • 자원 할당시 Deadlock의 4가지 필요 조건 중 어느 하나가 만족되지 않도록 하는 것

• Deadlock Avoidance

  • 자원 요청에 대한 부가적인 정보를 이용해서 deadlock의 가능성이 없는 경우에만 자원을 할당
  • 시스템 state가 원래 state로 돌아올 수 있는 경우에만 자원 할당

• Deadlock Detection and recovery

  • Deadlock 발생은 허용하되 그에 대한 detection 루틴을 두어 deadlock 발견시 recover

• Deadlock Ignorance

  • Deadlock을 시스템이 책임지지 않음

  • UNIX를 포함한 대부분의 OS가 채택

    그럼, 데드락이 생겼을 때 어떻게 해결이 되냐?
    사람이 알아서 프로세스를 죽이든지 알아서 해결

위에 있는 2가지 방법은 Deadlock이 생기지 않게 미연에 방지하는 방법
위로 갈수록 더 강한 방법임, 밑에 있는 두 방법들은 데드락이 생기도록 놔두는데 3번째 방법은 시스템이 느려졌거나 그럴 때 혹시 데드락이 있는게 아닌가.. 그런 상황에서 detection을 한 다음에 데드락이 있으면 recovery를 하는 방법, 4번째 방법은 방법이라고 하기도 뭐하지만 데드락에 대해서 아무 일도 하지 않는 방법, 현대의 운영체제들은 대부분 4번째 방법을 채택하고 있다, Deadlock이 생기든 말든 관여하지 않음

데드락이라는 것은 빈번히 발생하는 이벤트가 아니기 때문에 그런 것을 미연에 방지하기 위해서 훨씬 더 많은 오버헤드를 들이는 것이 현대적인 시스템에서는 비효율적이기 때문에 데드락을 미연에 방지하지 않고 생기든 말든 놔두는 이러한 방법을 주로 쓰고 있다.

Deadlock Prevention

데드락이 발생하는 4가지 조건 중 어느 하나를 원천적으로 차단해서 데드락에 들어가지 못하게 하는 방법

• Mutual Exclusion

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

    막을 수 있는 조건은 아님…

• Hold and Wait

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

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

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

    방법 1 대로 하면 프로세스가 종료될 때까지 그 모든 자원을 다 쓰는게 아니라 매 시점마다 필요로 하는 자원이 다를텐데 미리 다 보유하고 있게 되면 자원에 대한 비효율성이 생기므로 적합하지 않음… 그래서 방법 2를 생각해볼 수 있다.

    Hold and Wait인 방법 2는 자진해서 반납을 함으로써 문제를 해결한 것임

• No Preemption

  • process가 어떤 자원을 기다려야 하는 경우 이미 보유한 자원이 선점됨

  • 모든 필요한 자원을 얻을 수 있을 때 그 프로세스는 다시 시작된다

  • State를 쉽게 save하고 restore할 수 있는 자원에서 주로 사용 (CPU, memory)

    데드락이 생기는 이유가 가지고 있는 자원을 뺏어올 수 없기 때문에 데드락이 생기는 것이었는데, 반대로 데드락을 뺏어올 수 있게 (자원을 Preemption할 수 있게) 해서 데드락이 안생기도록 함.
    그러나 중간에 빼앗아오면 하던 일에 문제가 생겨서 Preemption을 허용하기 어려운 자원들이 있다. 그럴 때는 이 방법을 사용하기 어렵다.

• Circular Wait

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

  • 예를 들어 순서가 3인 자원 R_i를 보유 중인 프로세스가 순서가 1인 자원 R_j을 할당받기 위해서는 우선 R_i를 release해야 한다

    Circular wait은 필요한 자원들이 꼬리에 꼬리를 물고 있으면서 사이클이 형성된 경우. 이럴 때 데드락이 생기는 거였다.
    이 상황을 막기 위해서 자원에 번호를 매겨 순서를 정해놓는다. 항상 낮은 번호부터 먼저 획득을 해야지만 높은 번호를 획득할 수 있게 한다. (1, 3, 5번 자원이 필요하면 나는 1번 자원을 획득해야지만 3번 자원을 획득할 수가 있고, 1번 3번 자원을 획득해야지만 5번 자원을 획득할 수 있게 한다.) 그러면, 데드락이 안생김

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

이 방법은 데드락을 원천적으로 막을 순 있지만 자원에 대한 이용률이 낮아지고 전체 시스템의 성능이 나빠지는 문제, starvation 문제 등이 발생할 수 있다.

생기지도 않을 데드락을 미리 생각해서 이렇게 제약조건을 많이 달아놓기 때문에 상당히 비효율적이라는 것이다.

Deadlock Avoidance

• Deadlock avoidance

  • 자원 요청에 대한 부가정보를 이용해서 자원 할당이 deadlock으로부터 안전(safe)한지를 동적으로 조사해서 안전한 경우에만 할당

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

    프로세스가 시작되서 종료될 때까지 그때그때 상황마다 쓰려는 자원의 수나 종류가 다르다. Deadlock avoidance는 보통 프로세스가 시작 될 때 이 프로세스가 평생에 쓸 자원의 최대량을 미리 알고있다고 가정하고, 데드락을 피해가는 것.
    평생에 쓸 자원을 미리 알고 있기 때문에 어떤 프로세스가 자원 요청을 했을 때 혹시 내가 이 자원을 할당해주면 데드락이 생길 가능성이 있겠다면 자원에 여분이 있는데도 불구하고 주지 않는다.

• safe state

  • 시스템 내의 프로세스들에 대한 safe sequence가 존재하는 상태

• safe sequence

  • 프로세스의 sequence <P₁, P₂, …, P_n>이 safe하려면 P_i (1 ≤ i ≤ n)의 자원 요청이 “가용 자원 + 모든 P_j (j < i)의 보유 자원”에 의해 충족되어야 함
  • 조건을 만족하면 다음 방법으로 모든 프로세스의 수행을 보장
    • P_i의 자원 요청이 즉시 충족될 수 없으면 모든 P_j (j < i)가 종료될 때까지 기다린다
    • P_i-1 이 종료되면 P_i의 자원 요청을 만족시켜 수행한다

• 시스템이 safe state에 있으면
  → no deadlock
• 시스템이 unsafe state에 있으면
  → possibility of deadlock
• Deadlock Avoidance
  • 시스템이 unsafe state에 들어가지 않는 것을 보장
  • 2가지 경우의 avoidance 알고리즘
    • Single instance per resource types
      • Resource Allocation Graph Algorithm 사용
    • Multiple instances per resource types
      • Banker's Algorithm 사용

Resource Allocation Graph Algorithm

자원에 대한 인스턴스가 하나밖에 없는 환경에서 데드락을 피해가는 알고리즘

• Claim edge P_i → R_j
  • 프로세스 P_i가 자원 R_j를 미래에 요청할 수 있음을 뜻함 (점선으로 표시)
  • 프로세스가 해당 자원 요청시 request edge로 바뀜 (실선)
  • R_j가 release되면 assignment edge는 다시 claim edge로 바뀐다
• request edge의 assignment edge 변경시 (점선을 포함하여) cycle이 생기지 않는 경우에만 요청 자원을 할당한다
• Cycle 생성 여부 조사시 프로세스의 수가 n일 때 O(n²) 시간이 걸린다

아까처럼 자원으로부터 프로세스에게 가는 화살표는 이 자원이 이 프로세스한테 할당되어 있는 상황을 의미.
프로세스로부터 자원쪽으로 가는 화살표는 이 자원을 프로세스가 요청을 했는데 아직 할당받지는 못한 것 (자원이 1번 프로세스한테 할당되어 있기 때문)

위 그림은 아까 봤던 자원할당그래프인데 여기서는 화살표가 한 가지 종류가 추가되었다. 점선 화살표는 항상 프로세스로부터 자원한테 가는 화살표만 있고, 의미는 이 프로세스가 평생에 적어도 한 번은 이 자원을 사용할 일이 있다(요청할 수 있다)는 것을 표시한 것임.
이 상황에서 만약에 프로세스 2번이 지금 2번 자원을 요청하게되면 이 점선 화살표가 위 이미지 중간부분처럼 실선으로 바뀔 것이다. 지금 상황은 1번 프로세스가 1번 자원을 가지고 있고 2번 프로세스는 1번과 2번 자원을 요청한 상태이다. 이때 2번 자원은 아무도 가지고 있지 않기 때문에 요청한 프로세스한테 줄 수가 있다. 주면 마지막 맨 오른쪽 그림과 같이 바뀌게 된다.
이 마지막 그림은 프로세스 1번이 1번 자원을 가지고 있고, 프로세스 2번이 2번 자원을 가지고 있는 상황이다. 지금 이 상황은 데드락이 아니다. 왜 데드락이 아니냐하면 1번 프로세스가 2번 자원을 평생에 한 번은 요청할 수는 있다고 했지만 당장 요청한 상황은 아님,
이 상황에서 앞으로 미래에 벌어질 수 있는 일이 여러가지 상황이 있는데… 만약에 이 시점에 1번 프로세스가 2번 자원을 정말 요청한다고 하면 그럼 점선이 실선으로 바뀔 것이다. 그때는 사이클이 만들어지고 데드락이 되는 것이다.
그런데, 1번 프로세스가 평생에 한번 이상은 2번 자원을 요청한다고 했지 그걸 지금 요청한다고 한건 아니다.
만약 지금 시점이 1번 프로세스가 2번 자원을 요청하는 시점이 아니고 1번 프로세스가 1번 자원을 잘 쓰고 반납을 할 수도 있을 것이다. 그러면 이 화살표가 없어질 것이다(정확하게는 다시 점선으로 바뀌긴 하겠지만). 없어지면 그때 1번 자원을 2번 프로세스한테 넘겨주면 아무런 문제가 없이 계속 진행이 될 수가 있을 것이다.

그런데, 이 Deadlock Avoidance 방식은 최악의 상황을 가정하는 것이다. 되돌아와서 이미지 중간 부분 상황에서 만약에 2번 프로세스한테 2번 자원을 넘겨주게 되면 그 다음 단계에서는 점선을 포함해서 사이클이 만들어진다. 이것은 분명히 데드락은 아니지만 만약에 그때 재수없게도 프로세스 1번이 정말 자원 2를 요청해버린다면 데드락이 생긴다.
즉, (이미지 중간 부분과 같은) 데드락의 가능성이 있는 자원 요청에 대해서는 애초부터 받아들이지 않고 이대로 놔두는 것이다. 이게 Deadlock Avoidance임.
그러면 2번 프로세스는 2번 자원을 요청했는데 이 자원은 아무도 가지고 있지 않는데도 불구하고 안 주는 것이다. 그러면 데드락은 적어도 안생기고, 이 상황에서 만약 1번 프로세스가 2번 자원을 요청했다. 그러면 그때는 사이클이 생길 염려가 전혀 없기 때문에 이 자원을 준다.
그래서, 언젠가는 1번 프로세스가 자원을 다 반납해서 2번한테 두개의 자원이 다 갈 날이 올거기 때문에 그래서 Deadlock Avoidance는 이렇게 Available한 자원이 있다고해서 다 내어주는게 아니고 혹시 데드락의 위험성이 있다고하면 애초부터 자원을 주지 않는 그러한 방식으로 데드락을 막는다는 것이다.

Banker’s Algorithm

자원 당 인스턴스가 여러개 있는 경우에는 Banker’s Algorithm이라는 것을 사용해서 데드락을 막게된다.

Example of Banker’s Algorithm

• 5 processes P₀ P₁ P₂ P₃ P₄

• 3 resource types A (10), B (5), and C (7) instances. 10 5 7

• Snapshot at time T₀

  

• ＊sequence <P₁, P₃, P₄, P₂, P₀>가 존재하므로 시스템은 safe state
  (가용자원과 그리고 그 프로세스가 최대요청하는 자원을 다 얻어서 프로세스를 끝까지 실행시킬 수 있는 과정을 순서대로 나열한 것임. 이러한 sequence가 존재한다면 시스템은 안전하다.)

이 예제는 프로세스가 5개가 있고, 자원이 A, B, C 세 종류가 있는데 각 종류별로 인스턴스가 A는 10개 B는 5개 C는 7개가 있는 것이다.
그런 상황에서 5가지의 프로세스들이 위 이미지를 보면 지금 할당 받은 자원을 Allocation 부분에 표시하고 있는 것이다. (보면 0번 프로세스는 B 자원 하나를 가지고 있고, 1번 프로세스 A 자원을 2개를 가지고 있고… 이런 상황)
Deadlock Avoidance는 프로세스가 시작될 때 평생 사용할 Maximum 자원을 미리 Declare(선언)한다고 했는데 그게 Max 부분에 표시되어 있는 것이다. (그래서 예를 들면 2번 프로세스는 내 평생에 자원을 최대로 쓴다면 A 9개 C 2개를 쓰고, B는 평생 사용할 일이 없다는 얘기가 될것임)

그래서, 지금 할당된 자원들이 Allocation 부분과 같기 때문에 이미지에 나와있는 전체 자원 인스턴스(A = 10, B = 5, C= 7)에서 할당된 자원을 빼면 Available한 가용 자원이 이미지의 Available부분과 같이 A 3개, B 3개, C 2개 이렇게 되는 상황이다. 이런 상황에서 프로세스들이 자원을 요청하면 남아있는 자원은 줄 수가 있지만 무조건 주는게 아니라 문제가 생길 수 있을 때는 자원이 남아있다 하더라도 안 주는 것이다.

일단 여기서 Need라는 하나의 테이블을 더 계산했는데 이것은 추가요청 가능 양이다. 최대 요청 가능한 양(Max)에서 현재 할당된 것(Allocation)을 빼면 Need 테이블이 만들어진다. 추가로 요청할 수 있는 양이 위 이미지와 같이 표시되고 있음.

이 상태에서 예를 들어서 프로세스 1번이 자원을 A 1개, C 2개를 요청했다고 해보자.
그러면 분명히 A 1개 C 2개는 A가 3개 C가 2개 남아있기 때문에 가용자원에서 프로세스 1번한테 줄 수는 있다. 근데, 그냥 주는게 아니라 뭘 비교해보느냐 하면 프로세스 1번이 추가 요청할 수 있는 양(Need)이 있다. 그것이 가용자원을 가지고 모두 충족이 되는가를 보는 것이다. 그래서 프로세스 1번 같은 경우는 앞으로 추가로 요청해봐야 A 1개, B 2개, C 2개인데 그게 지금 남아있는 것(Available) 가지고도 모두 충족이 된다. 이런 상황에서는 프로세스 1의 요청이라면 지금 가용 자원만 가지고도 Maximum이 다 처리가 되기 때문에 요청하면 그냥 주는 것임. 줘도 데드락으로부터 안전하다는 것이다.

그런데 예를 들어서 프로세스 0번이 B를 2개 요청했다고 해보자.
프로세스 0번이 B를 2개 요청했는데 B는 지금 2개 여분이 있다. 그렇지만 프로세스 0번은 추가로 요청할 수 있는게 A 7, B 4, C 3 이 되는데, 그 추가 요청 가능한게 지금 남아있는거 가지고는 전부 충족이 안된다. 그런 경우에는 프로세스 0번한테 줄 자원이 있지만 안주는 것이다. 혹시라도 프로세스 0번이 최대로 모두 다 요청을 해버리면 가용 자원만 가지고는 처리가 안되기 때문에 이런 경우에는 그 요청을 받아들이지 않고 그냥 기다리게 하는 것이다.
그러면 언젠가 다른 프로세스들이 가용자원만 가지고 다 처리가 가능하고… 그래서 처리가 끝나면 어차피 그 프로세스들은 언젠가 종료될거고 그렇게 되면 지금 할당되있는 것도 다 뱉어내면 그것이 가용자원이 될 것이다. 그걸 가지고 0번 프로세스와 같은 충족 안되던 프로세스한테 자원을 나눠줄 수가 있다는 것이다.

즉, Banker’s Algorithm은 Available한 것만 가지고 추가 요청 가능한 양(Need)이 커버가 되는 그런 프로세스의 요청이라면 무조건 받아들여주고, Available한 자원을 가지고는 추가 요청이 충족이 안되는 프로세스의 요청은 받아들이지 않는 것이다.
이런식으로 하면 항상 안전함.

safe한 상태에서 가용자원만으로 충족되지 않는 프로세스에게 자원을 줬다고해서 그게 데드락은 아니다. (만약에, 이 상태에서도 다른 프로세스들이 다 최대 자원 요청을 해버리면 본인이 가진건 내어놓지 않고, 가용자원이 없는 상태가 되면 데드락이 되지만…) 가용자원만 가지고 지금 처리안되는 요청이 있다고해서… 즉, unsafe상태로 간다고해서 데드락인 것은 아님.
어쨋거나, Deadlock avoidance 방법은 아주 안전하게 가자는 것이다. 가용자원만 가지고 그 프로세스의 최대 자원 요청을 처리할 수 있는 그런 프로세스의 요청만 받아들이면 언제나 safe한 상태가 유지가 되서 데드락에 빠지지 않는다.

이 예제도 그런 생각으로 보면 된다.
즉, 프로세스 1번이 A 하나, C 2개를 요청했을 때 지금 A하고 C가 남아있기 때문에 주는게 아니고, 더 위에 이미지를 보면 프로세스 1번이 최대 요청 가능한(추가 요청 가능한) 1, 2, 2개가 3, 3, 2개인 가용자원보다 작아서 가용자원을 가지고 충분히 처리를 할 수 있기 때문에…
그래서, 프로세스 1번이 요청한 A 1개, C 2개는 요청하면 주는 것이다.

Deadlock Detection and Recovery

• Deadlock Detection
  • Resource type 당 single instance인 경우
    • 자원할당 그래프에서의 cycle이 곧 deadlock을 의미
  • Resource type 당 multiple instance인 경우
    • Banker’s algorithm과 유사한 방법 활용
• Wait-for graph 알고리즘
  • Resource type 당 single instance인 경우
  • Wait-for graph
    • 자원할당 그래프의 변형
    • 프로세스만으로 node 구성
    • P_j가 가지고 있는 자원을 P_k가 기다리는 경우 P_k → P_j
  • Algorithm
    • Wait-for graph에 사이클이 존재하는지를 주기적으로 조사
    • O(n²)

앞에 Deadlock avoidance와 비슷하게 자원 당 인스턴스가 하나 밖에 없는 경우에는 자원할당그래프를 이용해서 Deadlock Detection을 하는 것이 가능하고(그래프를 굳이 안그리고 테이블 그려서 하는 것이 더 좋은 방법), 자원 당 인스턴스가 여러개 있을 때는 테이블을 그려서 현재 상태가 데드락인지를 Detection할 수 있다.

자원 당 인스턴스가 하나 밖에 없을 경우 자원할당그래프를 아래 이미지와 같이 이용해서 Deadlock Detection을 한다.

• 자원의 최대 사용량을 미리 알림 필요 없음 → 그래프에 점선이 없음

자원 당 인스턴스가 하나 밖에 없는 상황에서는 자원할당그래프에서 사이클이 있으면 deadlock 상황이다. 근데, 이 자원할당그래프를 조금 더 간결하게 그릴 수 있다.(우측 이미지가 그 그림이다) 왼쪽 이미지에서 자원은 빼버리고 프로세스들끼리만 화살표를 이어주는 1대1로 대등한 그래프를 그려줄 수 있다.

자원 당 인스턴스가 하나밖에 없는 상황에서 자원할당그래프를 자원을 빼버리고 거기에 대응하는 wait-for graph라는 걸로 바꿔줄 수가 있다는 것이다. 이렇게 하면 좀 더 간결하고 사이클의 상황은 똑같다. 그렇기 때문에 deadlock detection을 할 때 wait-for graph를 그려놓고 이 그래프에서 사이클이 있는지 보면 된다.
(위 wait-for graph 예제에서는 사이클이 2개 있음. 100% 데드락 상황)

wait-for graph에서 사이클을 찾는 오버헤드는 얼마나 될까?
프로세스가 n개 있다고할 때 wait-for graph에서 사이클을 찾는 것은 Order of N 제곱(O(n²))의 시간이 걸린다.
왜 그러냐? 프로세스가 n개가 있는데 여기에 사이클이 있는지를 알아보려면 화살표를 다 따라가보면 될 것이다. 근데 지금 점이 n개가 있으면 화살표는 전부 몇개가 있을 수 있을까? n개 각각의 점들로부터 화살표가 나머지 점들로 다 나간다고 가정하면 n개 각각에 대해서 n-1개의 화살표가 있을 수가 있다.(최대의 경우) 그래서, n개의 프로세스에서 화살표가 많아봐야 n * n-1 이다. 그 화살표 다 따라가봐야 O(n²)의 시간이 걸린다.

그래프에 대해서 너비우선탐색과 깊이우선탐색이라는 방법이 있다.

이게 결국 뭐냐하면 모든 점을 다 탐색을 해보는 것이다. 처음에 시작해서 갈 때까지 가보고 더 진행이 안되면 다른 점으로해서 쭉 진행을 하다가 더이상 진행이 안되면 아까 빠져나왔던 점으로해서 이렇게 다 탐색을 해보는 것이다.
이렇게 탐색을 하는 깊이우선탐색이나 너비우선탐색을 (이 알고리즘 조금만 바꾸면) 해보면 사이클이 있는지를 알 수가 있다.

그래서, 이러한 방법은 점이 n개 있을 때 n²의 시간이면 탐색이 다 가능하다.

여튼 그래서… wait-for graph에서 사이클이 있는지를 찾는 것은 O(n²)이면 된다.
이것은 자원 당 인스턴스가 하나 밖에 없을 때의 이야기…

아래는 자원 당 인스턴스가 여러개 있는 경우에 현재 데드락이 있는지를 찾는 방법이다.

위 이미지에 보듯이 프로세스가 5개가 있고, 자원이 세 종류가 있는데 A 7개, B 2개, C 6개 있는 상황이다. 이 상황에서 현재 할당된 자원이 Allocation에 표시되어있다. 자원이 모두 할당이 되서 가용자원은 전부 0인 상황이다. Request 부분은 뭐냐하면 지금 현재 요청을 한 것이다. 1번 프로세스가 A를 2개 가지고 있는데, A 2개하고 C 2개를 추가로 요청 한 것이다. 그러나, 지금 가용자원은 없기 때문에 이 요청을 받아들일 수는 없을 것이다. 3번과 4번 프로세스도 A 1개, C 2개를 요청했는데 가용자원이 없으니까 요청을 받아들일 수는 없는 상황이다.
과연 지금 이게 데드락이냐?

우리가 정말 데드락이 있는지 없는지를 확인할 때는 아까처럼 아주 보수적인 접근을 하는게 아니고, 아주 낙관적인 접근을 하면 된다.(데드락이 정말 데드락만 데드락으로 알아내야 되기 때문에)
그래서, 이게 데드락인지 아닌지 알려면 일단 0번 프로세스는 B 1개를 가지고 있다. 추가로 요청할지도 모르나 (낙관적으로 보라고 했기 때문에) “이것은 반납할 것이다”라고 가정하면 된다. 그러면 그 반납 된거 1개를 가지고 또, 2번 프로세스는 A 3개 C 3개가 있는데 2번 프로세스도 지금 추가로 요청한게 없으니까 반납할 것이라고 보는 것이다. 즉, 현재 요청된게 없는 프로세스로부터 할당된 자원을 일단 반납한다고 가정한다. 그럼 A 3개 B 1개 C 3개가 가용자원에 생길 것이다.
그럼 그걸 가지고 지금 1번 프로세스가 실제 요청한 A 2개 C 2개를 받아들일 수 있을 것이다. 그것도 방금 전에 가용자원에 된걸 가지고 받아들여서 1번 프로세스가 추가로 요청할 수도 있겠지만 그냥 지금 A 2개 C 2개만 얻으면 또 쓰고나서 반납한다고 가정하는 것이다. 그러면 가용자원에 A 2개 C 2개가 더 쌓일 것이다. 그걸 가지고 3번과 4번 프로세스가 요청한 A 1개 C 2개가 받아들여지느냐 이걸 보는 것이다.

그래서, 지금도 이런식으로 아무것도 요청하지 않은 프로세스가 가진 자원을 반납해서 그것을 쌓고 쌓고 쌓아서 지금 요청된 것들을 다 허용을 하고, 그리고나서 그 친구들도 요청된게 추가로 없는 상황에서 반납을 하고… 이런식으로해서 요청을 다 받아들이는 sequence가 존재한다고 하면 데드락이 없다는 얘기다.

이 예제는 데드락이 없는 상황이다.

그러나, 다르게…

만약에 P₂가 자원 C를 하나 더 요청하는 경우에는 어떻게 될까?
이 상황은 이제는 자원 요청을 안한 프로세스는 P₀밖에 없음. 그래서, P₀이 가진 자원 B 1개를 지금 반납한다고 가정하면 B 하나가 반납이 됐지만 지금 다른 프로세스들이 전부 A하고 C를 요청한 상황이다. 그러나, A하고 C는 가용자원에 없다.
그러니까 프로세스는 항상 본인이 가진 자원은 가지고 있으면서 내가 요청한 자원이 만족될 때까지는 가진 자원을 안 내어놓는 원칙이 있는데… B 1개가 가용자원에 있어봐야 어느 프로세스들의 요청을 받아들일 수 없는 상황이 된 것이다.

그러면, 이것은 데드락이다.

그래서, 데드락이 있는지 찾아볼 때에는 일단 가용자원이 몇개 있는지를 보고 가용자원으로 처리 가능한게 있는지를 보고, 또 지금 요청하지 않은 프로세스의 것은 일단 가용자원으로 다 합쳐놓고 그런 다음에 그걸 가지고 처리 가능한 프로세스가 있는지 봐서 있으면 그 프로세스한테 할당된 것을 계속 가용자원에 합쳐나가면서 문제가 생기지 않고 끝까지 갈 수 있는지를 한번 체크해보면 될 것이다.

이렇게해서 만약 데드락이 발견이 되면 Recovery를 해야된다.
Recovery를 어떻게 하느냐하면 크게 2가지 방법이 있다. (아래)

• Recovery

  • Process termination

    프로세스를 종료시키는 방법

    • Abort all deadlocked processes

    • Abort one process at a time until the deadlock cycle is eliminated

      하나는 데드락에 연루된 프로세스들을 사살하는 것이다.
      그 중에서도 데드락에 연루된 모든 프로세스들을 한꺼번에 죽이는 방법이 첫번째 방법.

      두번째 방법은 데드락에 연루된 프로세스를 하나씩 죽여보는 것이다. 하나를 죽였더니 데드락이 없어졌다면 ok… 하나를 죽였는데도 여전히 데드락이라면 또 하나의 프로세스를 죽여보는 것이다. 데드락이 없어질 때까지…

  • Resource Preemption

    데드락에 연루된 프로세스로부터 자원을 뺏는 방법

    • 비용을 최소화할 victim의 선정

    • safe state로 rollback하여 process를 restart

      프로세스 중에서 누구한테 자원을 뺏을지 희생양을 찾은 다음에 그 친구로부터 자원을 뺏어서 데드락을 없앤다. 그래서 다시 safe state로 rollback을 해서 process를 restart하면 데드락이 없어질 수가 있다.

    • Starvation 문제

      • 동일한 프로세스가 계속해서 victim으로 선정되는 경우
      • cost factor에 rollback 횟수도 같이 고려

      문제는 어떤 프로세스한테서 자원을 뺏었는데 다른 프로세스가 갖기 전에 뺏은 프로세스에서 또 자원을 요청해버리고 가져가버리는 상황이 생길 수 있다.

      즉, 데드락을 없애놨더니 똑같은 패턴이 다시 일어날 수도 있는 것이다. 그렇게 되면 문제가 생기기 때문에 그래서… 데드락이 발생했을 때 자원을 뺏는 패턴을 똑같은 방식으로만 하는게 아니라 조금씩 바꿔서 해야지만 데드락이 없어질 수가 있고, 또 이렇게 하는 이유는 starvation 문제를 막아야 될 필요가 있기 때문이다.

      데드락이 생겼을 때 항상 비용을 최소화 해야된다고해서 특정 프로세스만 선정이 되고 그 친구만 자원을 뺏기면 비용을 최소화 하는데는 성공했지만, 그 프로세스 개인 입장에서는 계속 앞 부분으로 rollback을 해야되기 때문에 희생이 크다는 것이다.
      그래서, 꼭 비용만 최소화하는 프로세스를 고르는게 아니라 어떤 프로세스가 몇번 자원을 뺏겼는지 이런것도 고려해서 자원을 어떻게 뺏을지를 결정해주는 것이 필요하다는 것이다.

Deadlock Ignorance

데드락이 일어나든 일어나지 않든 아무 일도 안하는 것

• Deadlock이 일어나지 않는다고 생각하고 아무런 조치도 취하지 않음
  • Deadlock이 매우 드물게 발생하므로 deadlock에 대한 조치 자체가 더 큰 overhead일 수 있음
  • 만약, 시스템에 deadlock이 발생한 경우 시스템이 비정상적으로 작동하는 것을 사람이 느낀 후 직접 process를 죽이는 등의 방법으로 대처
  • UNIX, Windows 등 대부분의 범용 OS가 채택

Deadlock이 생기지 않게 하는 것도 대단히 자원을 비효율적으로 쓰는 방법이 되고, Deadlock을 Detection하는 것도 조금만 느려졌을 때 Deadlock Detection Routine이 발동하고 이러면 시스템의 오버헤드가 크기 때문에 굳이 그렇게 하지 않고 데드락이 생기든 말든 운영체제나 시스템은 책임을 지지 않고, 가만히 놔두는 것이다.

그렇게 되면 만약 데드락이 생겼을 때 시스템이 느려지고 뭔가 프로세스가 정지가 되고 이런 상황이 생길 것이다. 그러면 사용자가 문제가 생겼다는 것을 알고 일부 프로세스를 종료시키던지 이런식으로 사용자가 알아서 처리하도록 하고, 운영체제는 데드락에 대해서 대처하지 않는 방법이다.

맨 위로 이동하기