OS 8. Deadlocks

서론

  다중 프로그래밍 환경에서는 여러 스레드가 한정된 자원을 사용하려고 서로 경쟁할 수 있다. 한 스레드가 자원을 요청했을 때, 그 시각에 그 자원을 사용할 수 없는 상황이 발생할 수 있고, 그때는 스레드가 대기 상태로 들어간다. 이 처럼 대기 중인 스레드들이 결코 다시는 그 상태를 변경시킬 수 없으면 이런 상황을 교착상태(Deadlocks)라 부른다.

---

교착 상태(Deadlocks)

 교착 상태는 프로세스 집합 내의 모든 프로세스가 그 집합의 다른 프로세스에 의해서만 일어날 수 있는 이벤트를 기다리는 상황이라고 정의할 수 있다. 교착 상태를 간단히 이해하기 위해 7장의 식사하는 철학자 문제를 상기해 보자. 이 상황에서 자원은 젓가락으로 표시된다. 모든 철학자가 동시에 배가 고프고 각 철학자가 왼쪽에 있는 젓가락을 잡으면 더 사용 가능한 젓가락이 없다. 그런 다음 각 철학자느 오른쪽 젓가락을 사용할 수 있을 때까지 기다리는 상황을 교착상태라고 이해할 수 있다. 6장과 같은 도구들을 사용할 때 개발자는 락이 획득되고 방출되는 방식에 대해 주의를 기울여야 한다. 그렇지 않을 경우 교착 상태가 발생할 수 있다.

교착 상태 특성

 각 프로세스는 요청(request), 사용(use), 릴리스(release)와 같은 자원을 활용한다. 교착 상태는 한 시스템에 다음 네 가지 조건이 동시에 성립될 때 발생할 수 있다.

• 상호 배제(mutual exclusion): 한 번에 하나의 프로세스만 리소스를 사용할 수 있다. 즉, 최소한 하나의 자원이 비공유모드로 점유되어야 한다.
• 점유하며 대기(hold and wait): 스레드는 최소한 하나의 점유한 채, 현재 다른 스레드에 의해 자원을 추가로 얻기 위해 반드시 대기해야 한다.
• 비선점(no preemption): 자원들을 선점할 수 없어야 한다. 즉, 자원이 강제적으로 방출될 수 없고 점유하고 있는 스레드가 태스크를 종료한 후 그 스레드에 의해 자발적으로만 방출될 수 있다.
• 순환 대기(circular wait): 대기하고 있는 스레드의 집합 {P0, P1,..., Pn}에서 P0은 P1이 점유한 자원을 대기하고, P1은 P2가 점유한 자원을 대기하고,..., Pn-1은 Pn이 점유한 자원을 대기하며, Pn은 P0가 점유한 자원을 대기한다.

자원 할당 그래프(Resource allocation graph)

 교착 상태는 시스템 자원 할당 그래프라는 방향 그래프로 더욱 정확하게 기술할 수 있다. 이 그래프는 정점(vertex) V의 집합과 간선(Edge) E의 집합으로 구성된다. V와 E는 각각 두 가지 유형으로 분할된다. 정점(V)은 시스템 내의 모든 활성 스레드의 집합 P = {P1, P2, …, Pn}과 시스템 내의 모든 자원 유형의 집합인 R = {R1, R2, …, Rm}으로 구별된다. 간선(E)은 스레드 P로부터 자원 유형 R로의 방향(Pi → Rj)의 간선을 요청 간선(Request edge)이라 하며, 자원 유형 R로부터 시르데 P로의 방향(Rj → Pi)의 간선을 할당 간선(Assignment edge)이라 한다.

교착 상태 처리 방법(Methods for Handling Deadlocks)

 원칙적으로 교착 상태 문제를 처리하는 데는 다음과 같은 세 가지 다른 방법이 있다.

• 문제를 무시하고, 교착 상태가 시스템에서 절대 발생하지 않는 척
• 시스템이 결코 교착 상태가 되지 않도록 보장하기 위하여 교착 상태를 예방(네 가지 조건 중 적어도 하나가 성립하지 않도록 함)하거나 회피(각 프로세스가 리소스를 활용하는 방법에 대한 선험적 정보가 필요)하는 프로토콜을 사용
• 시스템이 교착 상태가 되도록 허용한 다음에 복구시키는 방법

교착 상태 예방(Deadlock Prevention)

 아래 네 가지 조건 중 적어도 하나가 성립하지 않도록 한다.

• 상호 배제(Mutual Exclusion): 교착 상태를 예방하기 위해서는 여러 프로세스가 동시에 하나의 자원을 사용할 수 없도록 해야 한다. 즉, 한 자원에 대한 배타적인 액세스를 보장해야 한다. 이를 위해 상호 배제 기법을 사용합니다. 상호 배제는 여러 프로세스가 동시에 공유 자원을 사용할 수 없도록 제어하는 것을 의미합니다.
• 보류 및 대기(Hold and Wait): 교착 상태를 예방하기 위해서는 프로세스가 자원을 요청할 때 다른 자원을 보유하지 않은 상태에서만 요청할 수 있도록 해야 한다. 즉, 프로세스가 자원을 요청할 때는 현재 보유한 자원을 모두 해제한 상태여야 한다.
• 선점 없음(No Preemption): 교착상태를 전시하기 위해 자원을 점유한 프로세서가 다른 프로세서의 자원을 선점할 수 있어야 한다. 즉, 다른 프로세스가 점유한 자원을 저항할 수 없습니다. 이를 비선점이라고 할 수 있다.
• 순환 대기(Circular Wait): 교착 상태를 예방하기 위해서는 자원 점유 순서를 정하여 순환 대기를 방지해야 한다. 즉, 자원들 간에 선형 순서를 정하고, 프로세스는 자원을 요청할 때에는 그 순서에 맞추어 요청해야 한다.

 이러한 방법들을 함께 적용하면 교착 상태를 예방할 수 있습니다. 그러나 이러한 방법들만으로는 교착 상태가 발생하지 않는 것을 완전히 보장할 수는 없다.

교착 상태 회피(Deadlock Avoidance )

 교착상태 회피 알고리즘(Deadlock avoidance algorithm)은 요청 방법에 제한을 두어 교착 상태를 예방한다. 이 제한은 교착 상태가 발생하기 위한 필요조건 중 적어도 한 가지는 성립되지 않도록 보장한다. 또한, 회피 알고리즘은 프로세스가 사용 가능한 리소스를 요청할 때 시스템은 즉각적인 할당이 시스템을 안전한 상태로 유지하는지 여부를 결정해야 한다. 시스템이 어떤 순서로 각 프로세스에 자원을 할당(최대)하고 여전히 교착 상태를 피할 수 있는 경우 상태는 안전하다. 이를 위해 시스템에 사용 가능한 추가 선험적 정보가 있어야 한다. 그러나 이런 방식으로 교착 상태를 예방할 때 가능한 부수적인 문제는 장치의 이용률이 저하되고 시스템 총처리율이 감소하는 것이다.

• 시스템이 안전한 상태인 경우 → 교착 상태가 없다.
• 시스템이 안전하지 않은 상태인 경우 → 교착 상태 가능성.

 만약 각 자원 유형마다 단지 하나의 인스턴스를 갖는 자원 할당 시스템을 갖고 있다면, 우리는 교착 상태 회피를 위해 앞서 정의한 자원 할당 그래프의 변형을 사용할 수 있다. 이를  자원 할당 그래프 알고리즘(Resource allocation graph)라 한다. 자원 할당 그래프에 예약 간선(Claim edge)이라는 새로운 간선을 추가한다. 예약 간선 Pi → Rj는 미래에 자원 Rj를 요청할 것이라는 의미이다. 이 간선의 방향은 요청 간선(Request edge)과 유사하자지만 점선(dashed line)으로 표시된다. 프로세스 Pi가 자원 Rj를 요청하면, 예약 간선 Pi → Rj는 요청 간선으로 변환된다. 마찬가지로 Pi가 자원 Rj를 방출할 때, 할당 간선(assignment edge) Rj → Pi는 예약 간선 Pi → Rj로 다시 변환된다.

• 프로세스가 리소스를 요청할 때, 예약 간선이 요청 간선으로 변환됨.
• 리소스가 프로세스에 할당된 경우, 요청 간선이 할당 간선으로 변환됨.
• 리소스가 프로세스에 의해 해제된 경우, 할당 간선이 예약 간선으로 재변환됨.

리소스 유형의 인스턴스가 여러 개인 경우 뱅커 알고리즘을 사용한다.

No cycle -> safe -> grant / Cycle -> unsafe -> deny

교착 상태 감지 및 복구(Deadlock Detection & Recovery)

 만일 시스템이 교착 상태 예방이나 교착 상태 방지 알고리즘을 사용하지 않는다면 즉, 시스템이 교착 상태에 들어가도록 허용한하다면, 아래와 같은 알고리즘들을 반드시 지원해야 한다.

탐지 알고리즘(Detection algorithm)

 그래프에서 주기를 검색하는 알고리즘을 주기적으로 호출하여 순환이 있는지 확인한다. 만약 순환(deadlock cycle)이 있으면 교착상태가 존재한다.(자원 유형이 여러 인스턴스인 경우 더 복잡한 알고리즘을 사용)

복구 계획(Recovery scheme)

 복구 계획에는 크게 두 가지가 있다. 첫 번째는 즉시 프로세스 종료(Process termination)하여 모든 교착 상태 프로세스를 중단한다. 이때 교착 상태 주기가 제거될 때까지 한 번에 하나의 프로세스를 중단한다. 둘째로 프로세스에서 일부 리소스를 선점하고 이 리소스를 교착 상태 사이클(deadlock cycle)이 끊어질 때까지 다른 프로세스에 제공하는 리소스 선점(Resource preemption)이 있다.

---

핵심

• 교착 상태는 프로세스가 대기 중인 프로세스로 인해 발생하는 이벤트를 무한정 기다리는 상황이다.
• 교착 상태는 다음 네 가지 조건에서 발생할 수 있습니다. 즉, 상호 배제, 보류 및 대기, 선점 없음 및 순환 대기가 동시에 성립되어야 한다.
• 교착 상태 방지는 네 가지 조건 중 적어도 하나가 유지되지 않도록 한다.
• 교착 상태 회피는 시스템이 절대 안전하지 않은 상태에 들어가지 않도록 한다.
• 교착 상태 감지 및 복구를 통해 시스템이 교착 상태에 들어갈 수 있다.