Chapter 8 Deadlocks

Chapter 8 Deadlocks

Chapter 8 Deadlocks

• Illustrate how deadlock can occur when mutex locks are used.
• Define the four necessary conditions that characterize deadlock.
• Identify a deadlock situation in a resource allocation graph.
• Evaluate the four different approaches for preventing deadlocks.
• Apply the banker’s algorithm for deadlock avoidance.
• Apply the deadlock detection algorithm
• Evaluate approaches for recovering from deadlock.

8.1 System Model 318

다중 프로그래밍 환경에서는, 여러 스레드가 한정된 자원을 사용하려고 경쟁한다. 자원들은 다수의 유형(클래스)로 나누어지며, 각각의 단일 혹은 다수의 인스턴스들로 구성된다. 스레드는 자원 사용 이전에 반드시 필요한 만큼의 자원을 요청해야 하며, 사용 후에는 반드시 방출해야한다 (당연히, 시스템에서 사용 가능한 전체 자원의 수 이내에서만 요청 가능하다.)

즉, 1.  스레드의 자원 요청 및 대기, 2. 사용, 3. 방출 의 순서로만 자원을 사용할 수 있고 이러한 자원 요청과 방출은 시스템 콜을 통해 이루어진다.

한 스레드 집합 내의 모든 스레드가 그 집합 내의 다른 스레드에 의해서만 발생될 수 있는 이벤트를 기다린다면, 그 스레드 집합은 교착상태에 있다.

→ 미리 정해진 특정 스레드 집합에서 교착상태가 발생한다는 뜻이 아니라, 특정 자원을 대기하는 스레드와 해당 자원을 점유한 스레드들이 서로 닫힌 집합을 구성할 수 있기만 하면, 그 집합은 교착상태에 빠지게 된다는 뜻.

그리고 이러한 교착상태는 프로세스가 전혀 처리되지 않는 상태로 자원을 점유하고있기 때문에 전체 시스템의 성능을 저하한다.

8.2 Deadlock in Multithreaded Application 319

다음의 삽화는 POSIX mutex 락을 사용하는 다중 스레드 Pthread 프로그램에서 어떻게 교착상태가 발생할 수 있는지 설명한다.

8.3 Deadlock Characterization 321

Necessary Conditions

1. mutual exclusion

   최소한 하나의 자원이 비공유 모드로 점유되어야 함.

2. hold-and-wait 각각의 스레드는 최소한 하나의 자원을 점유한 채로, 다른 스레드에 의해 점유된 자원을 추가로 얻기위해 대기해야 함
3. no preemption 자원들을 선점할 수 없어야 함.
4. circular wait 대기하고 있는 스레드의 집합은 순환적으로 다른 스레드가 점유한 자원을 대기해야한다.
   • 네 **조건들이 **모두 **독립적인것은 **아니다 , 4. 순환 **대기 **조건은 2. 점유 **대기를 **포함하기 **때문

Resource Allocation Graph

스레드의 집합 T= {T1, T2, … Tn} 과 자원의 집합R = {R1, R2, …, Rm} 의 이항관계를, Vertex가 T와 R로 이루어진 유향 그래프(graph with directed edge)로 기술 가능하다.

직사각형으로 표현된 자원들은 첨자 종류의 자원 클래스의 인스턴스로 표현되며, 각각 점의 갯수 혹은 숫자로 표시된 인스턴스 개수를 갖는다. 또한, 임의의 스레드에서 자원으로의 방향 간선은 자원에 대한 요청을(점유된 자원의 경우 대기 상태), 자원에서의 스레드로의 방향 간선은 자원에 대한 점유를 표현한다.

(당연히 loop나 parallel edge는 없다.)

자원 할당 그래프의 사이클은 교착상태의 필요조건이다.

즉, 교착상태가 일어나면 사이클이 반드시 있어야 하지만, 사이클이 있다고 반드시 교착상태인 것은 아니다.

다음은 모두 사이클이 발생한 자원 할당 그래프이나, 각각 교착상태 여부가 다르다.

• 만일 각 자원 유형이 정확하게 하나의 인스턴스만을 가지면 (=각각의 자원이 하나씩밖에 없다면) 사이클이 있으면 반드시 교착상태가 발생한다.

8.4 Method for Handling Deadlocks 326

이하의 8.5절 부터 8.7에서 교착상태의 예방, 회피, 탐지 및 복구에 대해서 다룰것이다.

8.5 Deadlock Prevention 327

8.3 에서 기술한 교착상태가 되기 위한 4가지 필요조건 (1. 상호 배제, 2. 점유 대기, 3. 비선점, 4. 순환 대기)중 하나만 무효화 시켜도 교착상태는 발생하지 않는다. → 따라서 각 조건들을 만족되지 못하게 하는 방법을 다룬다.

1. 상호 배제

Read_Only로 열린 파일처럼, 자원이 여러 스레드로부터의 동시 접근을 허용하면 상호 배제를 무효화 할 수 있다. 그러나 기본적으로 여러 스레드가 공유할 수 없는 자원들이 있기때문에 모든 자원에 대해 상호배제를 무효화시키기란 사실상 불가능하다.

2. 점유 대기

스레드가 자원을 요청할 때는 자원을 점유하고 있지 않도록 보장한다.

a. 실행 시작 전 사용할 모든 자원을 요청하고 할당받는다.

⇒  실행 전에 실행 중 필요한 모든 자원을 예측할 수 없다. 장기간 사용되지 않거나, 실행이 끝날때쯤 잠깐 사용되는 자원도 처음부터 할당되어야 함

b. 추가적인 자원요청을 허용하는 경우, 우선 자신에게 할당 된 모든 자원을 먼저 방출해야한다.

⇒ 자주 사용되는 자원의 경우, 항상 다른 스레드에 할당되어 있을 가능성이 있으므로 어떤 필요한, 사용가능한 자원 집합을 구성하기 어려운 스레드들의 경우 기아가 발생가능

3. 비선점

비선점 조건을 무효화하기위해, 책에서는 다음과 같은 프로토콜을 제시한다.

스레드가 즉시 할당받을 수 없는 다른 자원을 요청하면, 현재 점유하고 있는 모든 자원이 선점된다.(즉각 방출되어 그 스레드가 기다리고 있는 자원 리스트에 추가된다.) 혹은, 좀더 복잡한 방법으로는, 해당 상황에 스레드가 점유하고 있는 자원이 다른 스레드에 의해 요청받는 경우에만 선점 될 수 있도록 하는 방법이 있다. 그러나 이러한 방식은 CPU 레지스터나 데이터베이스 트랜잭션처럼 상태가 쉽게 저장되고 복원될 수 있는 자원에만 적용될 수 있으며, 교착 상태가 가장 흔하게 발생하는 mutex 락이나 세마포어같은 자원에서는 일반적으로 적용할 수가 없다.

4. 순환 대기

모든 자원 유형에 대해 유일한 순서를 부여하여, 오름차순 혹은 내림차순으로만 자원을 추가요청할 수 있도록 하면, 교착상태의 네번째 조건인 순환 대기를 수학적으로 무효화 시킬 수 있다. (2. 점유 대기의 예시처럼 단 한번에 모든 자원을 할당받아야 함)

• 그러나 그 자체로 자원의 자유로운 할당을 제한하여 처리율(throughput)이 감소하므로 비 실용적이다.

8.6 Deadlock Avoidance 330

8.5절의 교착상태 예방 알고리즘은, 프로세스의 자원 요청 방법에 제한을 두어 교착상태를 예방한다. 그러나 이런 방식들은 장치의 이용률을 저하하고 시스템 총 처리율(throughput)을 감소시켜 매우 비 실용적이다. 대신, 자원이 앞으로 어떻게 요청될지에 대한 추가 정보를 제공받아, 가능한 교착상태의 발생을 회피할 수 있다. (다만, 이 역시 모든 자원 요청 정보를 미리 알고있을 수 있는지의 문제가 있다.)

8.6.1 Safe State

시스템의 상태가 안전하다는 말은, 스레드들이 요청하는 모든 자원을 교착상태를 야기하지 않고, 차례대로 모두 할당해 줄 수 있다는 뜻이다. 즉, ‘안전 순서(열)’을 구성할 수 있다(=안전 순서열이 존재한다)는 뜻이다.

• 안전 순서열 (safe sequence) : 스레드의 처리 순서를 표시한 것으로, 안전 순서열대로 자원을 할당해주면 교착상태에 빠지지 않고 모든 요구를 처리 가능하다.

반대로 이처럼 모든 스레드를 무사히 마칠 수 있는 순서를 찾을 수 없다면, 시스템은 불안전 상태에 있는 것이다.

다음의 삽화는 안전 상태와 불안전 상태, 교착상태의 관계를 제시한다.

8.6.2 Resource Allocation Graph Algorithm

각 자원 유형(클래스)마다 유일한 인스턴스를 갖는 시스템이라면, 교착상태 회피를 위해 8.3절에서 정의한 자원 할당 그래프를 사용할 수 있다. 바로, 스레드가 미래에 특정 자원을 요청할 것이라는 의미인, ‘예약 간선’(claim edge)을 점선으로 표시하는 방법이다.

위 상황에서는 사이클이 생기는 것으로, 미래에 그 자원을 스레드에 할당한다면 (점선을 실선으로 바꾼다면) 교착상태가 발생할 것임을 알 수 있다.

8.6.3. Banker’s Algorithm

위의 자원 할당 그래프 알고리즘은, 자원 유형별로 둘 이상의 인스턴스가 있는 경우에는 사용할 수 없는데. 이를 해결하기 위해 ‘은행원 알고리즘’을 소개한다.

위의 삽화로 정의된 자료구조에 Safety Algorithm과 Resource-Request Algorithm을 사용함으로써 좀더 일반적인 상황에 대한 교착상태 회피가 가능하다.

8.7 Deadlock Detection 337

교착상태를 완전히 예방하거나 회피하지 않았다면, 교착상태가 발생할 수 있으므로 탐지를 위해 시스템의 상태를 검사하는 알고리즘이 필요하다.

8.7.1 Single Instance of Each Resource Type

이 역시 이전과 같이, 각 자원 유형이 유일한 인스턴스를 갖는 경우 보다 간단한 방식으로 탐지가 가능하다.

대기 그래프 (wait-for graph) : 자원 할당 그래프에서 자원 유형 노드를 제거 하고, 스레드간의 관계를 표현하여자원할당 그래프와 그에 대응하는 대기 그래프를 표현하였다. 단일 인스턴스 환경에서는 대기 그래프 상의 사이클이 곧 교착상태를 의미한다.

8.7.2. Several Instances of a Resource Type

8.7.2. Several Instances of a Resource Type

다중 인스턴스 환경에서는, 은행원 알고리즘처럼 시시각각 내용이 달라지는 자료구조를 사용하며, 그 내용은 다음과 같다.

8.8 Recovery from Deadlock 341

탐지 알고리즘에 의해 교착상태가 존재한다고 결정되면, 다음과 같은 처리 방법들이 존재한다.

1. 운영자(operator)에게 통지, 2. 한개 이상의 스레드를 중지(abort), 3. 자원 선점(preempt)

8.8.1 Process and Thread Termination

스레드의 종료는 다시 두가지 방법으로 나뉜다.

1. 교착 상태 프로세스를 모두 중지

• 지금까지 처리했던 작업 결과를 폐기해야한다. 아마도 이후에 다시 계산해야할 것이므로 비용이 크다.

2. 교착 상태가 제거될 때까지 한 프로세스씩 중지

• 각 프로세스가 중지될 때마다 교착 상태 탐지 알고리즘을 호출하여 여전히 교착상태에 있는지 확인해야한다. 또한, 어떤 프로세스들을 중지해야할지를 반드시 결정해야하므로 역시 오버헤드가 크다.

후자의 경우 어떤 프로세스들을 중지할지 결정하는데는 1. 프로세스 우선순위, 2. 프로세스가 기 수행된 시간과 종료까지 더 필요한 시간 3. 프로세스가 사용한 자원 유형과 수 및 자원 선점의 용이성 4. 프로세스가 종료하기 위해 더 필요한 자원의 수 5. 얼마나 많은 수의 프로세스가 종료되어야하는지 등을 고려하여 결정해야한다.

8.8.2 Resource Preemption

자원 선점을 통한 교착상태 제거는, 교착상태가 깨어질 때까지 프로세스로부터 자원을 계속 선점하여 다른 프로세스에 할당해야한다. 이에 대한 고려사항으로는

1. 희생자 선택 (selection of a victim) : 어느 자원과 어느 프로세스들이 선점될 것인가.
2. 후퇴 (rollback) : 완전히 후퇴 (프로세스를 중지하고 재시작)에서 부터, 교착 상태를 깨뜨릴 수 있을 정도로만 후퇴시키는 방법, 후자의 경우 보다 효과적이나, 시스템 내 프로세스의 상태에 대한 더 많은 정보의 유지가 필요할 것이다.
3. 기아 상태 (starvation) : 특정 시스템에서는 희생자 선택에서 동일한 프로세스가 항상 희생자로 선택될 수도있다. 따라서 이 프로세스가 태스크를 결코 완료하지 못하는 기아상태에 빠지는 것을 방지해야 할 것이다. 일반적인 해결 방법으로, 비용 요소에 후퇴의 횟수를 포함하는 방식이 있다.