8. Deadlocks

자원을 대기하는 스레드에 대해 그 자원이 다른 대기 스레드에 의해 선점되고 있다면 무한히 대기하게 된다. 이를 데드락이라 한다. 즉, 어떤 프로세스들이 그 프로세스들 외의 다른 프로세스에 의해서만 발생할 수 있는 이벤트를 대기하는 것을 말한다. 이 장에서는 데드락을 막거나 다루는 법에 대해 다룬다. 운영 체제는 대개 데드락 방지 기능을 제공하지 않으므로 이를 방지하는 것은 프로그래머의 몫이다.

8.1. System Model

시스템은 복수의 경합 중인 스레드에 분배된 유한한 자원으로 이루어진다. 뮤텍스 락이나 세마포어들 또한 시스템 자원인데, 현대 컴퓨터 시스템에서는 이들이 데드락의 주된 원인이 된다. 이 장에서는 커널 자원만 다루지만, 스레드가 다른 자원을 필요로 할 경우 이들 또한 데드락의 원인이 될 수 있다.

스레드는 자원 사용 전 이를 요청하고 이를 사용한 뒤에는 해제해야 한다. 어떤 스레드들이 그 스레드를 외의 다른 스레드에 의해서만 발생할 수 있는 이벤트를 대기해야 할 경우 데드락에 빠진다. 여기서 고려하는 이벤트는 자원 획득과 해제이다. 멀티스레드 애플리케이션을 개발하는 사람은 데드락의 가능성을 염두에 두어야 한다.

8.2. Deadlock in Multithreaded Applications

두 스레드가 뮤텍스 A, B를 두고 경쟁하며 각각 A -> B, B -> A 순으로 획득하고 그 역순으로 해제한다고 하면, 첫째 스레드가 A를 획득하고 둘째 스레드가 B를 획득한 상태에서 데드락이 발생할 수 있다.

8.2.1. Livelock

라이브락은 데드락과 비슷하지만, 스레드가 실패하는 동작을 계속 시도하게 될 경우에 발생한다. 어떤 뮤텍스 A를 획득한 뒤 이미 점유된 다른 뮤텍스 B를 획득하려는 시도를 하는데 B를 획득한 스레드가 A를 획득하려는 시도를 할 경우에서 라이브락이 발생할 수 있다. 이는 실패한 시도를 무작위 시간에 재시도함으로써 대개 해결된다.

8.3. Deadlock Characterization

데드락을 분류해 보자.

8.3.1. Necessary Conditions

다음 4가지 조건이 동시에 발생할 경우 데드락이 발생할 수 있다.

  1. 상호 배제.
  2. 획득 및 대기.
  3. 비선점.
  4. 순환 대기.

8.3.2. Resource-Allocation Graph

자원들은 시스템 자원-할당 그래프라는 방향그래프로 더 정확하게 표현할 수 있다. 이는 스레드가 자원을 요청하는 요청 간선과 자원이 스레드에 할당되는 할당 간선으로 구성된다. 이 때 그래프 내 순환이 있다면 데드락이 발생할 가능성이 있다. 각 자원의 인스턴스가 하나씩만 존재한다면 사이클이 있다면 반드시 데드락이 발생한다.

8.4. Methods for Handling Deadlocks

데드락은 다음 3가지 방법으로 다룰 수 있다.

  • 문제를 무시하고 데드락이 발생하지 않은 것처럼 가장한다.
  • 데드락을 막거나 방지하는 프로토콜을 넣어 데드락이 일어나지 않음을 보장한다.
  • 데드락을 감지하고 복구한다.

운영 체제는 첫 번째 방법을 쓴다. 프로그래머들은 두 번째 방법을 쓰고, 데이터베이스에서는 세 번째 방법을 쓴다. 이 중 어느 것도 그 자체만으로는 자원 할당 문제를 다루는 데 있어 충분하지 않다. 데드락이 일어나지 않음을 보장하기 위해, 시스템은 데드락을 위한 필요조건 중 하나 이상이 발생하지 않게 하는 데드락 방지 또는 운영 체제가 스레드가 요청할 수 있는 자원들을 파악한 뒤 자원 요청에 대해 대기 여부를 결정하게 하는 데드락 회피 방식을 쓸 수 있다. 이것들을 쓰지 않는다면 데드락을 감지한 뒤 이를 푸는 알고리즘을 제공할 수 있다. 이런 경우 시스템 성능이 저하되면서 결국엔 재시작되어야 한다. 데드락은 자주 발생하는 것은 아니기 때문에 운영 체제에서는 따로 이를 다루지는 않는다. 라이브락 해결에 쓸 수 있는 방법들은 데드락 해결에도 쓸 수 있다.

8.5. Deadlock Prevention

데드락에 대한 필요조건 4가지 중 각각을 어떻게 방지하는지 알아보자.

8.5.1. Mutual Exclusion

상호 배제는 막을 수 없다.

8.5.2. Hold and Wait

획득 및 대기를 막으려면 스레드가 자원을 요청할 때 다른 자원을 획득하지 않은 상태임을 보장해야 한다. 이 프로토콜은 비효율적인데, 자원 활용도가 낮고 기아가 발생할 수 있기 때문이다.

8.5.3. No Preemption

비선점을 막으려면 스레드가 어떤 자원을 획득하고 다른 자원을 대기해야 할 때 대기하는 대신 그 자원을 점유하고 있는 스레드를 선점해 버리면 된다. 이는 CPU 레지스터나 데이터베이스 트랜잭션 같이 저장과 복원이 쉬운 자원에 대해서는 적용할 수 있지만, 뮤텍스 락이나 세마포어처럼 정작 데드락이 가장 많이 발생하는 자원에 대해서는 적용할 수 없다.

8.5.4. Circular Wait

위의 세 조건 모두 그 조건을 막는 접근법은 비효율적이다. 하지만 순환 대기에 대해서는 이를 막는 실용적 접근법이 존재한다. 하나의 방법은 자원들에 순서를 준 뒤에 각 스레드들이 자원을 요청할 때 우선도가 증가하는 순서로 요청하게 하는 것이다. 또는 어떤 자원을 요청할 때 그 자원보다 우선도가 큰 자원을 전부 해제한 경우에만 요청을 허가하는 것이다. 이 두 프로토콜을 쓰면 순환 대기는 발생할 수 없다. 이는 순서를 락에 주는 것만으로는 소용이 없고, 개발자가 이 룰을 지켜야 한다. 또한, 락이 동적으로 획득될 수 있다면 락 순서화는 데드락을 막는다는 보장이 없다.

8.6. Deadlock Avoidance

데드락 방지 알고리즘은 기기 활용도를 낮출 수 있고 시스템 처리량을 줄일 수 있다. 데드락을 피하는 다른 방법은 자원들이 어떻게 요청되는지에 대한 정보를 필요로 한다. 이러한 정보를 시스템이 알고 있는 상태에서는, 시스템은 스레드가 어떠한 자원 요청에 대해 대기해야 하는지를 결정해서 데ㄷ락을 막을 수 있다. 가장 유용하고 간편한 모델은 각 스레드가 필요로 하는 각 자원의 최대 수를 정해 놓고 이를 기반으로 데드락을 회피하는 알고리즘을 짤 수 있다.

8.6.1. Safe State

시스템에서 스레드에 자원을 필요한 최대치까지 특정 순서로 할당했을 때 데드락이 나지 않는 경우를 안전 배열이 존재한다고 한다. 이런 배열이 존재하지 않는다면 시스템의 상태는 불안전하다고 한다. 안전 상태는 데드락 상태가 아니며, 데드락 상태는 불안전 상태이지만, 모든 불안전 상태가 데드락은 아니다. 데드락을 회피하는 알고리즘은 자원을 스레드에 할당하ㅡㄴ 것이 불안전 상태에 진입하지 않음을 보장함으로써 짤 수 있다.

8.6.2. Resource-Allocation-Graph Algorithm

각 자원마다 인스턴스가 하나밖에 없다면, 자원 할당 그래프에 스레드가 어떤 자원을 요청할 수 있음을 나타내는 주장 간선을 추가한 뒤 순환이 있는지를 찾음으로써 데드락을 방지할 수 있다.

8.6.3. Banker’s Algorithm

위의 알고리즘은 각 자원마다 인스턴스가 여럿 있다면 성립하지 않는다. 그래서 이럴 때는 은행가의 알고리즘을 쓴다. 이에는 다음의 자료구조들이 필요하다.

  • 가용수. 각 자원의 가용가능한 수.
  • 최대. 각 스레드의 각 자원에 대한 최대 필요수.
  • 할당. 각 스레드에 할당된 각 자원의 수.
  • 필요. 각 스레드의 각 자원에 대한 남은 필요수.

8.6.3.1. Safety Algorithm

시스템이 안전 상태에 있는지는 다음 알고리즘으로 검사할 수 있다.

  1. Work = Available, Finish = false로 벡터를 초기화한다.
  2. Finish[i] = false, Need_i ≤ Work인 i를 찾는다. 없다면, 4단계로 간다.
  3. Work += Allocation_i, Finish[i] = true로 설정한 뒤 2단계로 간다.
  4. 모든 i에 대해 Finish[i] == true면 안전 상태인 것이다.

8.6.3.2. Resource-Request Algorithm

이제 특정 요청이 안전히 수행될 수 있는지는 다음 알고리즘으로 검사할 수 있다.

  1. Request_i ≤ Need_i면 2단계로 간다. 아니면 에러를 낸다.
  2. Request_i ≤ Available이면 3단계로 간다. 아니면 대기한다.
  3. Available -= Request_i, Allocation_i += Request_i, Need_i -= Request_i를 수행한 뒤 안전 상태인지를 검사한다. 안전 상태면 요청을 수행하고 아니면 대기시킨다.

8.6.3.3. An Illustrative Example

예를 들어 은행가의 알고리즘을 살펴보아라.

8.7. Deadlock Detection

데드락 방지 또는 데드락 회피 알고리즘이 없다면 데드락이 발생할 수 있다. 이런 환경에서는 시스템이 다음을 제공해야 한다.

  • 데드락이 발생했는지를 알 수 있는 알고리즘
  • 데드락으로부터 회복할 수 있는 알고리즘

이 모두 얼마간의 오버헤드를 야기한다는 것을 짚고 넘어갈 필요가 있다.

8.7.1. Single Instance of Each Resource Type

모든 자원이 단일 인스턴스만 갖고 있다면 자원 할당 그래프의 변형인 대기 그래프를 통해 데드락을 감지할 수 있다. 대기 그래프에 순환이 있는 것과 데드락의 존재는 동치이다.

8.7.2. Several Instances of a Resource Type

자원이 여러 인스턴스를 갖고 있다면 은행가의 알고리즘과 비슷하게 다음 자료구조들을 사용한다.

  • 가용. 각 자원의 가용 가능한 수.
  • 할당. 각 스레드에 할당된 각 자원의 수.
  • 요청. 각 스레드의 각 자원에 대한 현 요청수.

이 때 데드락은 다음과 같이 감지할 수 있다.

  1. Work = Available, Finish[i] = (Allocation_i == 0) 으로 초기화한다.
  2. Finish[i] == false, Request_i ≤ Work인 i를 찾는다. 이런 i가 없다면 4단계로 간다.
  3. Work += Allocation_i, Finish[i] = true로 만든 뒤 2단계로 간다.
  4. Finish[i] == false라면 그 스레드가 데드락된 것이다.

8.7.3. Detection-Algorithm Usage

감지 알고리즘을 얼마나 자주 써야 하나? 이는 다음의 2가지에 의존한다.

  • 데드락이 얼마나 자주 일어나는가?
  • 데드락이 발생했을 때 얼마나 많은 스레드들이 영향을 받는가?

데드락이 자주 일어나면 감지 알고리즘도 자주 작동되어야 한다. 물론 이는 상당한 오버헤드를 야기하므로 대개 주기적으로 알고리즘을 작동시키는 편이다. 한 시간마다, 또는 CPU 활용율이 40% 이하로 떨어질 떄마다.

8.8. Recovery from Deadlock

데드락 감지 알고리즘이 데드락을 감지했을 때에는 연산에 데드락을 대처하도록 할 수도 있고 시스템이 자동적으로 데드락으로부터 회복하게 할 수도 있다. 이는 두 가지 방법이 있는데 하나는 하나나 그 이상의 스레드를 중지시켜서 순환 대기를 깨는 것이고 다른 방법은 데드락된 스레드로부터 자원을 선점시키는 것이다.

8.8.1. Process and Thread Termination

프로세스나 스레드를 중지해서 데드락을 해소하려면 다음 중 하나의 방법을 사용한다.

  • 데드락된 모든 프로세스를 중지시킨다. 그러나 이는 비용이 크다.
  • 데드락 순환이 없어질 때까지 프로세스를 하나씩 중지시킨다. 각 프로세스가 중지될 때마다 데드락 감지 알고리즘을 수행해야 하므로 이도 오버헤드가 크다.

어떤 프로세스를 중지시킬 지는 비용이 최소인 프로세스를 중지시키는 것으로 결정한다. 비용은 다음 요소들로 결정된다.

  1. 프로세스의 우선도
  2. 프로세스가 얼마나 오래 연산했는지, 지정된 작업을 끝내기까지 얼마나 연산해야 하는지
  3. 프로세스가 어떤 자원을 얼마나 썼는지
  4. 프로세스가 완료되기 위해 얼마나 많은 자원을 필요로 하는지
  5. 얼마나 많은 프로세스가 종료되어야 하는지

8.8.2. Resource Preemption

자원 선점으로 데드락을 방지하기 위해서는, 자원을 프로세스들로부터 선점하고 이를 다른 프로세스에게 나눠주면서, 이를 데드락 순환이 끊어질 때까지 수행해야 한다. 데드락을 다룰 때 선점을 한다면 다음 3가지 요소를 고려해야 한다.

  1. 피해 대상 선정.
  2. 롤백.
  3. 기아.

8.9. Summary

  • 데드락은 어떤 프로세스들이 그 프로세스들 외의 다른 프로세스에 의해서만 발생할 수 있는 이벤트를 대기할 때 발생한다.
  • 데드락에는 4가지 필요 조건이 있다. 1) 상호 배제, 2) 획득 후 대기, 3) 비선점, 4) 순환 대기. 이 4가지 조건이 모두 있을 때만 데드락이 발생할 수 있다.
  • 데드락은 자원 할당 그래프로 모델링될 수 있다. 이 때 순환은 데드락을 나타낸다.
  • 데드락은 4가지 조건 중 하나를 막아서 방지시킬 수 있다. 이 중 순환 대기를 막는 것만이 현실적인 접근법이다.
  • 데드락은 은행가의 알고리즘으로 회피할 수 있다. 이는 자원 할당이 시스템을 불안전 상태로 만들어 데드락을 야기할 수 있다면 그 할당을 하지 않는 것이다.
  • 데드락 감지 알고리즘은 현재 동작 중인 프로세스와 자원을 평가해 프로세스가 데드락 상태에 있는지를 감지한다.
  • 데드락이 발생해싿면 시스템은 데드락으로부터 회복해야 한다. 이 방법에는 순환 대기 중인 프로세스 중 하나를 중지시키거나 데드락된 프로세스에 할당된 자원을 선점시키는 것이 있다.

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중