Deadlock이란?

운영체제에서의 교착상태(Deadlock)는, 두 개 이상의 작업이 서로 상대방이 점유하고 있는 자원을 기다릴 때 무한 대기에 빠지는 상황을 의미한다. 즉, 멀티프로그래밍 환경에서 한정된 자원을 얻기 위해 서로 경쟁하는 상황이다.

프로세스가 자원을 얻지 못해 다음 처리를 하지 못하는 상태로, 시스템적으로 한정된 자원(CPU,메모리,파일,프린터 등)을 여러 곳에서 동시에 사용하려고 할 때 발생한다.

발생 조건

데드락이 발생하기 위한 조건은 크게 4가지가 있다.

  1. 상호 배제 (Mutual Exclusion)
    • 자원은 한 번에 한 프로세스만 사용할 수 있다. 사용 중인 자원을 다른 프로세스가 사용하려면 요청한 자원이 해제될 때까지 기다려야 한다.
  2. 점유 대기 (Hold and Wait)
    • 자원을 최소한 하나 보유하고, 다른 프로세스에 할당된 자원을 점유하기 위해 대기하는 프로세스가 존재해야 한다.
  3. 비선점  (Non-Preemptive)
    • 다른 프로세스에게 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없다.
  4. 순환 대기 (Circular wait)
    • 자원 할당 그래프에서 사이클이 존재해야 하며, 이는 각 프로세스가 순차적으로 다음 프로세스가 요구하는 자원을 보유하고 있어 서로가 서로를 기다리는 상태를 의미한다.

해결법

1️⃣ 예방

데드락 4가지 발생 조건 중 최소 1가지를 절대 만족시키지 않도록 한다.

1. 상호 배제 부정

  • 여러 프로세스가 자원을 공유하도록 한다.
  • 자원이 독점적으로 사용될 필요가 없을 때 사용된다. - ex) 읽기 전용 파일
  • 현실적으로 불가능하다. (CPU나 프린터 동시 사용 불가능)

    2. 점유 대기 부정

    1. 필요한 자원을 모두 할당받은 후 시작하도록 한다.
    2. 자원을 전혀 갖고 있지 않을 때만 자원을 한 번에 요청하도록 한다. ⇒ 지금 필요하지 않은 자원도 소유할 뿐더러, 필요한 자원을 계속해서 파악하기 위한 비용이 든다.

    ⇒ 할당된 모든 자원이 바로 사용되지 않기에 낮은 자원 효율성

    ⇒ 최소한의 자원이 항상 다른 프로세스에게 할당되어 있기 때문에 기아 발생 가능

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

3. 비선점 부정

  • 사용 중인 자원에 대해 다른 프로세스가 요청할 경우, 자원을 점유하고 있던 프로세스가 그 자원을 해제하고 나중에 다시 요청할 수 있도록 하는 방법

    4. 순환 대기 부정

  • 모든 자원에 고유 번호를 할당하고, 프로세스가 번호가 낮은 순서대로만 자원을 요청할 수 있도록 한다. ⇒ 자원을 순차적으로만 요청할 수 있다.

  • ex) 프로세스는 순서의 증가 방향으로만 자원 요청 가능

    R1, R2, R3, R4

    P1 (R1, 2, 4 모두 필요)

    P2 (R1, 3 모두 필요)

    P1이 먼저 R1을 사용하면, P2는 R1을 못 쓰기 때문에 P2가 실행 불가. 따라서, 자원 3는 아무도 사용하지 않는다.

    => 자원 사용의 효율성이 떨어지고 비용이 많이 든다.

2️⃣ 회피

데드락이 발생할 가능성이 있을 땐 아예 자원을 할당하지 않는 방법이다.

안정 상태(safe state)란 모든 프로세스가 최대 자원 요구량만큼 자원이 필요할 때도, 시스템이 주어진 순서대로 자원을 할당하여 모든 프로세스가 완료될 수 있는 상태이다. 안정 상태에서는 어떠한 프로세스도 데드락에 빠지지 않는다.

안전 순서(Safe Sequence)란 프로세스에 특정 순서로 자원을 할당할 때 모든 프로세스가 성공적으로 완료될 수 있는 순서다. 이 순서대로 자원을 할당하면 시스템은 항상 안전 상태를 유지할 수 있다. 

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

회피 방법의 대표적인 예시로는 은행가 알고리즘(Banker's Algorithm)이 있다. 은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는 데에서 유래한 기법이다. 다중 프로세스 시스템에서 안전한 순서로 자원을 할당하는 방법을 제공한다.

은행이 모든 고객에게 현금을 대출해주는데서 유래됐다. 은행(os)은 최소한 고객(프로세스)에게 대출할 정도의 돈(자원)이 있어야 한다. 그렇지 않으면 은행은 불안정 상태(데드락이 발생 가능한 상태)다.

은행가 알고리즘에는 3가지 전제조건이 있다. 아래 조건들이 충족되면, 시스템은 현재의 자원 할당 상태와 남은 자원량을 계속해서 감시하며, 각 요청이 안정 상태를 유지하는지 확인한다.

  1. 각 프로세스가 평생 요구할 최대 자원량을 예측할 수 있어야 한다.
  2. 각 프로세스는 다른 프로세스의 자원 요구에 독립적이어야 한다.
  3. 자원의 수가 고정되어 있고, 추가/제거가 불가능해야 한다.

각 프로세스의 요구에 따라 자원을 한꺼번에 몰아주지 않는다. 프로세스가 요구하는 자원의 상태를 safe state와 unsafe state로 나누어, safe state일 때만 자원을 할당하는 방법이다. 프로세스에 자원이 할당된 후에 safe state로 남아있는지 사전에 검사하여 교착 상태를 피한다. 즉, safe state면 자원을 할당하고 unsafe state면 다른 프로세스가 자원을 해지할 때까지 대기하게 한다.

시스템은 모든 프로세스가 자신의 최대 요구량만큼 자원을 안전하게 할당받을 수 있는 순서, 즉 안전 순서(Safe Seqeuence)를 찾아낸다. 만약 실험적으로 특정 순서에 따라 모든 프로세스에 자원을 할당했을 때 최종 상태가 안전 상태라면 승인된다. 이 방식으로 시스템은 언제나 안전 상태를 유지하며 각 프로세스의 자원 요구를 최대한 만족시킨다.

3️⃣ 탐지

데드락 발생 가능성을 인정하고, 데드락을 빠르게 발견하고 문제를 해결하는 방법이다.

자원 할당 그래프(Resource Allocation Graph, RAG)를 통해 교착 상태를 탐지할 수 있다. 이 그래프에서 사이클이 존재하면 데드락이 발생했다고 판단할 수 있다.

하지만 자원을 요청할 때마다 탐지 알고리즘을 실행하면, 오버헤드가 발생하게 된다.

4️⃣ 회복

교착 상태를 일으킨 프로세스를 종료하거나 할당된 자원을 해제하면서 회복하는 방법이다.

  1. 프로세스 종료
    • 교착 상태에서 나올 때까지 한 프로세스씩 중지한다.
    • 이때 순서는 무작위로 또는 특정 기준(우선순위 등)에 따라 결정된다.
  2. 자원 선점
    • 데드락을 일으킨 프로세스로부터 자원을 회수하여 다른 프로세스에 재할당하여 문제를 해결한다.

출처

https://velog.io/@shinyejin0212/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9COS-7.-Deadlocks

https://persi0815.tistory.com/6

https://www.boardinfinity.com/blog/deadlock-in-operating-system/