Chapter 8: Deadlocks

이 글은 고려대학교 김민호 교수님의 운영체제강의를 토대로 작성한 글입니다.
This post is based on the operating system lecture by Prof. Kim Min-ho of Korea University.

 

#8. Deadlocks

 

 

❖ Deadlock이란 무엇인가?

     • 데드락은 한 세트의 스레드(또는 프로세스)가 모두 특정 이벤트를 기다리는 상태입니다. 이 이벤트는 해당 세트의 다른 스레드에 의해서만 발생할 수 있는 이벤트이지만, 실제로는 발생하지 않습니다.

 

 

다리 건너기 예제

❖ 교통 상황

     • 한 방향으로만 차량이 통행할 수 있는 다리

❖ 다리 구간

     • 다리의 각 구간은 자원으로 볼 수 있습니다.

     • 차량이 다리 구간을 차지하는 동안 다른 차량은 그 구간을 사용할 수 없습니다.

❖ 데드락 발생 시나리오

     • 차량들이 서로 반대 방향에서 접근하여 다리 중간에서 만나는 경우 데드락이 발생할 수 있습니다.

     • 이 경우, 모든 차량이 멈추고, 서로의 통행을 기다리게 됩니다.

❖ 데드락 해결 방법

     • 데드락을 해결하려면 한 차량이 후진하여 자원을 반환해야 합니다.

     • 지원 선점 및 롤백: 차량이 후진하면 자원을 반환하고, 다른 차량이 전진할 수 있는 길을 열어줍니다.

     • 데드락이 발생하면 여러 차량이 차례로 후진해야 할 수도 있습니다.

❖ 자원 유형 (Resource Types)

 • 시스템에서는 여러 유형의 자원이 존재합니다. 예를 들어:

     • CPU 사이클 (CPU cycles)

     • 메모리 공간 (Memory Space)

     • 입출력 장치(I/O devices)

 

❖ 자원 인스턴스 (Resource Instances)

 • 각 자원 유형 Ri는 여러 개의 인스턴스 Wi를 가집니다.

 

❖ 프로세스의 자원 사용 단계

 • Request: 

     • 프로세스가 자원을 요청합니다.

     • 요청이 즉시 승인되지 않으면, 해당 프로세스는 자원을 획득할 수 있을 때까지 대기해야 합니다.

 • USE:

     • 프로세스는 자원을 사용하여 작업을 수행합니다.

 • Release:

     • 프로세스가 자원 사용을 마치면 자원을 해제합니다.

데드락(교착 상태)은 네 가지 필수 조건이 동시에 만족될 때 발생할 수 있습니다. 이 조건들은 다음과 같습니다.

❖ 상호 배제 (Mutual Exclusion)

     • 한 번에 하나의 프로세스만 자원을 사용할 수 있습니다.

❖ 점유 및 대기 (Hold and Wait)

     • 최소한 하나의 자원을 점유한 프로세스가 추가 자원을 기다리고 있습니다.

❖ 비선점 (No Preemption)

     • 자원은 그 자원을 점유하고 있는 프로세스가 작업을 마치고 자발적으로 해제할 때만 헤제될 수 있습니다.

❖ 순환 대기 (Circular wait)

• 기다리고 있는 프로세스들의 집합 (P0, P1, ..., Pn)이 존재하며,

     • P0는 P1이 점유하고 있는 자원을 기다리고, 

     • P1은 P2가 점유하고 있는 자원을 기다리고, 

     • ... 

     • Pn-1은 Pn이 점유하고 있는 자원을 기다리며, 

     • Pn은 P0가 점유하고 있는 자원을 기다립니다.

❖ 자원 할당 그래프는 시스템에서 프로세스와 자원의 상태를 시각적으로 표현한 것으로, 교착 상태를 분석하고 이해하는 데 유용합니다.

그래프는 다음과 같이 구성됩니다.

 

• 노드 집합 (V)

  • V는 두 가지 타입으로 나눌 수 있습니다:

     • 프로세스 집합 (P): 시스템 내 모든 프로세스로 구성된 집합 [EX] P= {P1,P2,...,Pn}

     • 자원 타입 집합 (R): 시스템 내 모든 자원 타입으로 구성된 집합 [EX] R = {R1, R2, ..., Rm}

 

• 엣지 집합 (E)

  •  E는 두 가지 타입으로 나눌 수 있습니다.

     • 요청 엣지 (request edge): 프로세스가 자원을 요청하는 경우, 방향은 프로세스에서 자원으로, [EX] Pi -> Rj

     • 할당 엣지 (assignment edge): 자원이 프로세스에 할당된 경우, 방향은 자원에서 프로세스로. [EX] Rj -> Pi

❖ 프로세스가 자원의 인스턴스를 요청 (Request)

     • 프로세스 Pi가 자원 Rj의 인스턴스를 요청하는 경우: Pi → Rj

     • 이는 Pi가 Rj의 인스턴스 중 하나를 얻기 위해 기다리고 있음을 나타낸다.

 

❖ 프로세스가 자원의 인스턴스를 보유 (Holding)

     • 프로세스 Pi가 자원 Rj의 인스턴스를 보유하고 있는 경우: Rj → Pi

     • 이는 Rj의 인스턴스 중 하나가 Pi에게 할당되었음을 나타낸다.

자원 할당 그래프의 예시

시스템이 교착 상태에 있는지 확인하기 위해,

교착 상태의 네 가지 필요조건 (상호 배제, 보유 및 대기, 비선점, 순환대기)을 사용하여 그래프를 분석해야 한다.

 

• 상호 배제: 자원 R1, R2, R3, R4는 상호 배제되어 한 번에 하나의 프로세스만 해당 자원을 가질 수 있습니다.

• 보유 및 대기: 프로세스 P1과 P2는 자원을 보유하면서 다른 자원을 대기하고 있습니다.

• 비선점: 자원은 프로세스가 자발적으로 반납하기 전까지 강제로 빼앗을 수 없습니다.

• 순환 대기: 순환대기 조건이 없습니다.

자원 할당 그래프에서의 교착 상태 예시

교착 상태 여부를 판단하기 위해 자원 할당 그래프를 통해 네 가지 교착 상태 조건을 검토해 보겠습니다. 각 조건이 어떻게 시스템에 적용되는지 확인해 봅시다.

주어진 조건:

• 자원 종류: R1, R2, R3, R4
• 프로세스: P1, P2, P3
• 상호 배제: 자원 R1, R2, R3, R4는 상호 배제되어 한 번에 하나의 프로세스만 해당 자원을 가질 수 있습니다.
• 보유 및 대기: P1, P2, P3는 자원을 보유하면서 추가 자원을 대기하고 있습니다.
• 비선점: 자원은 프로세스가 자발적으로 반납하기 전까지 강제로 빼앗을 수 없습니다.
• 순환 대기: 순환 대기가 존재합니다.

자원 할당 그래프 분석:

1. 상호 배제:

• 자원 R1, R2, R3, R4는 한 번에 하나의 프로세스만 사용할 수 있습니다.
• 이 조건은 시스템에서 만족됩니다.

2. 보유 및 대기:

• P1은 R1을 보유하고 R2를 요청하고 있습니다.
• P2는 R2를 보유하고 R3를 요청하고 있습니다.
• P3는 R3를 보유하고 R1을 요청하고 있습니다.
• 각 프로세스가 최소한 하나의 자원을 보유하고 다른 자원을 대기하고 있으므로 이 조건은 만족됩니다.

3. 비선점:

• 자원은 강제로 빼앗을 수 없으며, 프로세스가 자발적으로 반납해야 합니다.
• 이 조건도 만족됩니다.

4. 순환 대기:

• 순환 대기를 확인하기 위해 자원 할당 그래프에서 사이클을 찾아봅니다: 
  P1 → R2 → P2 → R3 → P3 → R1 → P1
• P1은 R1을 보유하고 R2를 요청합니다.
• P2는 R2를 보유하고 R3를 요청합니다.
• P3는 R3를 보유하고 R1을 요청합니다.
• 위와 같이 순환 대기가 발생하여 사이클이 존재합니다.

순환이 있는 자원 할당 그래프에서 교착 상태가 없는 경우

자원 할당 그래프에서 순환이 존재하지만 교착 상태가 없는 경우를 살펴보겠습니다. 각 조건이 어떻게 적용되는지 확인하여 실제로 교착 상태가 발생하는지 판단해보겠습니다.

주어진 조건:

• 자원 종류: R1, R2
• 프로세스: P1, P3
• 상호 배제: R1, R2
• 보유 및 대기: P1, P3
• 비선점: 예 (YES)
• 순환 대기: 예 (YES)

자원 할당 그래프 분석:

1. 상호 배제:

• 자원 R1과 R2는 상호 배제되어 한 번에 하나의 프로세스만 해당 자원을 사용할 수 있습니다.
• 이 조건은 만족됩니다.

2. 보유 및 대기:

• P1은 R1을 보유하고 R2를 요청합니다.
• P3은 R2를 보유하고 R1을 요청합니다.
• 각 프로세스가 최소한 하나의 자원을 보유하고 다른 자원을 대기하고 있으므로 이 조건은 만족됩니다.

3. 비선점:

• 자원은 강제로 빼앗을 수 없으며, 프로세스가 자발적으로 반납해야 합니다.
• 이 조건도 만족됩니다.

4. 순환 대기:

• 순환 대기를 확인하기 위해 자원 할당 그래프에서 사이클을 찾아봅니다:
• P1 → R2 → P3 → R1 → P1
• P1은 R1을 보유하고 R2를 요청합니다.
• P3은 R2를 보유하고 R1을 요청합니다.
• 위와 같이 순환 대기가 발생하여 사이클이 존재합니다.

결론:

순환 대기가 존재하지만, 순환 대기가 항상 교착 상태를 의미하는 것은 아닙니다. 교착 상태 여부를 더 정확히 판단하려면 자원 할당 상태와 프로세스 실행 상태를 고려해야 합니다.

예시 시나리오:

1. 초기 상태:
   • P1은 R1을 보유하고 R2를 요청.
   • P3은 R2를 보유하고 R1을 요청.
2. 자원 해제 및 재요청 시나리오:
   • 만약 P1이 R1을 보유한 채로 작업을 완료하고 R1을 해제한 다음 R2를 요청하는 순서로 진행된다면, P3이 R1을 요청하는 동안 R1을 사용할 수 있습니다.
   • 이후 P3가 R2를 해제하고 R1을 사용하여 작업을 완료하고 해제할 수 있습니다.

위와 같은 시나리오에서는 자원이 순환하지만, 프로세스가 서로 자원을 점진적으로 해제하고 요청할 수 있는 기회가 있기 때문에 교착 상태가 발생하지 않습니다.

 

❖ 사이클이 없는 경우: 교착 상태가 발생하지 않습니다.

❖ 사이클이 있는 경우:

• 자원 종류당 하나의 인스턴스만 있을 때는 교착 상태가 발생합니다.
• 자원 종류당 여러 인스턴스가 있을 때는 교착 상태의 가능성이 존재하지만, 반드시 발생하는 것은 아닙니다.

 

 

교착 상태를 절대 발생시키지 않도록 하는 방법:

교착 상태 예방 (Deadlock Prevention): 자세한 내용은 8.5 절에서 다룹니다.

교착 상태 회피 (Deadlock Avoidance): 자세한 내용은 8.6 절에서 다룹니다.

 

 

교착 상태 문제를 무시 (Ignore the Problem):

• 교착 상태가 발생하는 것을 무시하고, 시스템이 교착 상태에 빠질 가능성을 인정하는 방법입니다.
• 많은 운영 체제(예: UNIX, Linux, Windows)는 이 방법을 사용합니다.
• 교착 상태를 처리하는 것은 응용 프로그램 개발자가 직접 관리하도록 합니다.

교착 상태가 발생하지 않도록 하기 위해서는 교착 상태가 발생하기 위한 네 가지 필요 조건 중 하나를 무효화해야 합니다.

❖ 상호 배제 (Mutual Exclusion)

• 조건: 적어도 하나의 자원이 공유 불가능해야 합니다.
• 무효화 방법: 모든 자원을 공유 가능하게 만듭니다 (예: 읽기 전용 파일).
• 한계: 일부 자원은 본질적으로 공유 불가능합니다 (예: 뮤텍스 락). 따라서 실질적으로 모든 자원을 공유 가능하게 만드는 것은 불가능합니다.

❖ 점유 대기 (Hold and Wait)

• 조건: 최소 하나의 자원을 점유한 프로세스가 다른 프로세스가 점유하고 있는 추가 자원을 기다립니다.
• 무효화 방법: 프로세스가 자원을 요청할 때 다른 자원을 점유하지 않도록 보장해야 합니다.
  • 방법 1: 프로세스가 실행을 시작하기 전에 필요한 모든 자원을 요청하고 할당받도록 합니다.
  • 방법 2: 프로세스가 자원을 점유하고 있지 않을 때만 자원을 요청할 수 있도록 합니다.
  • 단점: 자원 이용률이 낮아지고, 기아 상태가 발생할 수 있습니다.

 

❖ No Preemption (비선점)

교착 상태의 비선점 조건을 무효화하는 방법은 자원을 선점하는 것입니다.

무효화 방법: 자원의 선점

• 조건: 프로세스가 자원을 점유한 상태에서 다른 자원을 요청하고, 그 자원이 즉시 할당되지 않는 경우 현재 점유한 모든 자원을 해제합니다.
• 구현 방법:
  1. 자원 요청 시점: 프로세스가 추가 자원을 요청했을 때, 그 자원이 즉시 할당될 수 없는 경우 현재 점유하고 있는 모든 자원을 해제합니다.
  2. 자원 반환: 해제된 자원은 요청된 자원의 대기 목록에 추가됩니다.
  3. 프로세스 재시작: 프로세스는 요청한 자원과 해제된 자원을 모두 할당받을 수 있을 때만 다시 시작됩니다.

한계와 조건:

• 이 방법은 상태를 쉽게 저장하고 나중에 복원할 수 있는 자원에만 적용됩니다

Circular Wait (순환 대기) 조건 무효화 방법

순환 대기 조건을 무효화하는 방법은 모든 자원 유형에 대해 전체 순서를 부과하고, 각 프로세스가 자원을 요청할 때 증가하는 순서로 자원을 요청하도록 요구하는 것입니다.

방법:

1. 자원 유형의 전체 순서 부과: 시스템 내 모든 자원 유형에 대해 순서를 매깁니다. 예를 들어, R1, R2, R3, R4와 같이 자원에 번호를 매깁니다.
2. 증가하는 순서로 자원 요청: 프로세스가 자원을 요청할 때, 이미 할당된 자원의 번호보다 높은 번호를 가진 자원만 요청할 수 있도록 합니다

예시:

• 요청 자원 번호 > 할당된 자원 번호: 프로세스가 이미 R1 자원을 점유하고 있다면, R2, R3, R4와 같은 자원만 추가로 요청할 수 있습니다.
• 응용 프로그램 개발자의 역할: 단순히 자원에 순서를 매기는 것만으로는 교착 상태를 방지할 수 없습니다. 응용 프로그램 개발자가 프로세스가 자원을 올바른 순서로 요청하도록 프로그램을 작성해야 합니다.

교착 상태 회피 (Deadlock Avoidance)

교착 상태 회피는 시스템이 미리 추가 정보를 제공하여 자원 요청에 대한 정보를 사전에 알려주어 교착 상태를 회피하는 방법입니다.

 

주요 개념:

• 사전에 자원 요청에 대한 정보 제공: 각 프로세스는 필요한 각 자원 유형의 최대 수를 선언합니다.
• 동적으로 자원 할당 상태 검사: 자원 할당 상태를 동적으로 검사하여 순환 대기 조건이 발생하지 않도록 합니다.
• 자원 할당 상태: 사용 가능한 자원 수, 할당된 자원 수, 프로세스의 최대 요구 자원 수로 정의됩니다.

교착 상태 회피 알고리즘:

1. 안전 상태 확인: 현재 시스템 상태가 안전한지 확인합니다. 안전 상태는 모든 프로세스의 최대 요구 자원 수를 충족하는 자원 할당 순서가 있는지 여부를 나타냅니다.
2. 자원 요청 검사: 프로세스가 자원을 요청할 때 요청이 현재 시스템 상태를 안전하게 유지하는지 확인합니다.
3. 자원 할당: 안전한 상태라면 자원을 할당하고, 그렇지 않으면 대기합니다.

안전 상태

시스템이 안전한 상태에 있다는 것은 다음과 같은 조건을 만족하는 경우를 말합니다.

• 안전한 시퀀스 존재: 모든 프로세스에 대한 안전한 시퀀스가 존재합니다.
• 안전한 시퀀스: 시퀀스 <P₁, P₂, ..., Pn>가 안전한 시퀀스이며, 각각의 Pi에 대해 다음을 만족합니다.
  • Pi가 요청한 자원은 현재 사용 가능한 자원과 Pi 이전의 모든 프로세스가 보유한 자원으로 충족될 수 있습니다.
  • 즉, Pi가 필요로 하는 자원이 즉시 사용 가능하지 않으면 Pi는 모든 이전 프로세스가 종료될 때까지 기다릴 수 있습니다.
  • 이후에 Pi는 필요한 자원을 얻고 실행하며, 할당된 자원을 반환하고 종료할 수 있습니다.
  • Pi가 종료되면 Pi+1이 필요한 자원을 얻을 수 있습니다.

요약:

• 안전한 상태에서는 모든 프로세스에 대해 안전한 시퀀스가 존재합니다.
• 안전한 시퀀스는 각 프로세스의 자원 요청이 보장되는 상태입니다.
• 시스템은 자원 요청 시 즉시 할당하더라도 안전한 상태로 유지되는지를 판단해야 합니다.

안전한 상태 예시

시스템에는 총 12개의 자원이 있다고 가정해보겠습니다.

• 시간 𝑡0에서 우리는 3개의 무료 자원을 가지고 있습니다. (12-5-2-2=3)
• 그런 다음, 시퀀스 <𝑇 1, 𝑇 0, 𝑇 2>는 안전한 상태를 만족합니다.

하지만, 만약 𝑇 2가 3개의 자원을 보유하고 있다면, 안전한 상태를 만족하지 못합니다.

• 𝑇 0: 최대 10개의 자원 필요, 현재 보유량 5개
• 𝑇 1: 최대 4개의 자원 필요, 현재 보유량 2개
• 𝑇 2: 최대 9개의 자원 필요, 현재 보유량 2개

 

 

 

기본 사실

• 시스템이 안전한 상태에 있다면, 데드락이 발생하지 않습니다.
• 시스템이 불안전한 상태에 있다면, 데드락의 가능성이 있습니다.
• 회피(avoidance)는 시스템이 불안전한 상태에 절대로 들어가지 않도록 보장합니다.

 

 

• 단일 자원 유형의 경우
  • 자원 할당 그래프 사용
• 다중 자원 인스턴스의 경우
  • 은행원 알고리즘(Hierarchical allocation algorithm) 사용
  • 안전 상태에 도달할 수 있는 모든 프로세스 조합을 고려하여 자원 할당 요청 승인
  • 시스템이 안전 상태에 있음을 확인하는 알고리즘 중 하나

Resource-Allocation Graph Algorithm

 

❖ 클레임 엣지 (Claim edge)

• 점선으로 표시된 P i → R j는 프로세스 P i가 미래에 리소스 R j를 요청할 수 있음을 나타냅니다.
• 프로세스가 리소스를 요청하면 클레임 엣지는 요청 엣지로 변환됩니다.

❖ 요청 엣지 (Request edge)

• 리소스가 프로세스에 할당되면 요청 엣지가 할당 엣지로 변환됩니다.

❖ 할당 엣지 (Assignment edge)

• 프로세스가 리소스를 해제하면 할당 엣지는 클레임 엣지로 다시 변환됩니다.

• 시스템에서 리소스는 미리 요청되어야 함

리소스 할당 그래프 알고리즘

• 프로세스 P i가 리소스 R j를 요청하는 경우
• 요청 엣지를 할당 엣지로 변환해도 리소스 할당 그래프에 사이클이 형성되지 않는 경우에만 요청이 허용됩니다.

리소스 할당 그래프를 사용한 교착 상태 회피

 

그래프에 사이클이 없습니다.

→ 안전한 상태

 

안전한 순서를 찾습니다!

• P1, P2 → 가능
• P2, P1 → 불가능 각 리소스 타입에 단일 인스턴스가 있습니다.

리소스 할당 그래프에서의 불안전한 상태

P2가 R2를 요청하고 요청이 승인될 때

 

그래프에 사이클이 있음

P1 → R2 → P2 → R1 → P1 → 불안전한 상태

 

안전한 순서를 찾습니다.

P1, P2 → 아니오

P2, P1 → 아니오

 

• 따라서 요청은 승인되지 않습니다! 각 리소스 타입에 단일 인스턴스가 있습니다.

 

리소스 할당 그래프 알고리즘

리소스 할당 그래프는 각 리소스 유형의 여러 인스턴스가 있는 리소스 할당 시스템에는 적용되지 않습니다.

 

리소스 유형의 여러 인스턴스의 경우

뱅커 알고리즘을 사용

뱅커 알고리즘은 다음과 같습니다.

• 각 프로세스는 미리 최대 리소스 사용을 요청해야 합니다.
• 프로세스가 리소스를 요청하면, 기다려야 할 수 있습니다.
• 프로세스가 모든 리소스를 획득하면, 유한한 시간 내에 이를 반환해야 합니다.
• 두 개의 하위 알고리즘으로 구성됩니다.
  • 안전 알고리즘
  • 리소스 요청 알고리즘

뱅커 알고리즘을 위한 데이터 구조는 다음과 같습니다:

• Available: 길이가 m인 벡터
  • 만약 available [ j ] = k이면, R j 타입의 자원이 k개 사용 가능합니다.
• Max: n x m 행렬
  • 만약 Max [ i,j] = k 이면, 프로세스 P i는 최대 k개의 R j 타입 자원을 요청할 수 있습니다.
• Allocation: n x m 행렬
  • 만약 Allocation[ i,j] = k 이면, 프로세스 P i가 현재 R j 타입 자원을 k개 할당받았음을 의미합니다.
  • 또한, Allocatoni는 Allocation의 i번째 행을 나타냅니다.
• Need: n x m 행렬
  • 만약 Need [ i,j] = k 이면, 프로세스 P i가 작업을 완료하기 위해 추가로 k개의 R j 타입 자원을 필요로 합니다.
  • Need[ i,j] = Max[ i,j] – Allocation [ i,j]

 

 

다음과 같은 단계로 구성됩니다.

1. 길이가 m인 Work와 n인 Finish 벡터를 초기화합니다.
   • Work = Available로 초기화합니다.
   • Finish [ i ] = false (i = 0, 1, …, n-1)로 초기화합니다.
2. 모든 다음의 조건을 만족하는 프로세스 i를 찾습니다. (a) Finish [ i ]가 false인지 확인합니다. (b) Needi가 Work보다 작거나 같은지 확인합니다. (요소별 비교) 만약 그러한 i가 존재하지 않으면, 단계 4로 이동합니다.
3. Work = Work + Allocationi 로 업데이트하고, Finish [ i ]를 true로 설정합니다. 그런 다음 단계 2로 이동합니다.
4. 모든 프로세스에 대해 Finish [ i ]가 true이면, 시스템은 안전한 상태입니다.

여기서 n은 프로세스의 수이고, m은 자원의 종류 수입니다. Work를 잠재적으로 사용 가능한 자원으로 생각할 수 있습니다.

프로세스 Pi의 자원 요청 알고리즘은 다음과 같습니다. Request = 프로세스 Pi의 요청 벡터입니다. 만약 Requesti [ j ] = k라면, 이것은 프로세스 Pi가 자원 유형 Rj의 k개의 인스턴스를 요청한다는 것을 의미합니다.

 

1. 만약 Request i ≤ Need i 이면 단계 2로 이동합니다. 그렇지 않으면, 프로세스가 최대 요구량을 초과했기 때문에 오류 조건을 발생시킵니다.

2. 만약 Request i ≤ Available 이면, 단계 3으로 이동합니다. 그렇지 않으면, 자원이 사용 가능하지 않기 때문에 Pi는 대기해야 합니다.

3.요청된 자원을 Pi에 할당한 것처럼 가정하고, 상태를 다음과 같이 수정합니다.

 

Available = Available - Request i;

Allocation i = Allocation i + Request i;

Need i = Need i - Request i;

 

4.안전 알고리즘을 실행합니다.

T0에서의 스냅샷 정보는 다음과 같습니다:

5개의 프로세스 P0부터 P4까지가 있고, 리소스 유형은 A(10개 인스턴스), B(5개 인스턴스), C(7개 인스턴스)입니다.

예시에서 사용되는 Need 행렬의 내용은 (Max - Allocation)으로 정의됩니다.

시스템은 안전 상태에 있으며, 시퀀스 <P1, P3, P4, P2, P0>가 안전성 기준을 충족합니다.

예시: P 1 요청 (1,0,2)

• Request ≤ Available인지 확인 (즉, (1,0,2) ≤ (2,3,0)임을 확인합니다)

• 안전 알고리즘 실행 결과, 시퀀스 <P 1, P 3, P 4, P 0, P 2>가 안전 요구 사항을 충족합니다.
• P1의 요청이 발생하지 않은 경우
  • P4가 (3,3,0)을 요청할 수 있습니까?
  • P0이 (0,2,0)을 요청할 수 있습니까?

• Request ≤ Available 인지 확인: 즉, (3,3,0) ≤ (3,3,2)인지 확인합니다.

• 안전 알고리즘 실행 결과, 안전한 시퀀스가 없음을 보여줍니다.

 

❖시스템이 교착 상태에 진입하는 것을 허용

❖검출 알고리즘

❖복구 방법

각 리소스 유형에 단일 인스턴스 유지

• 대기 그래프 유지
  • 노드는 프로세스입니다.
  • P i가 P j를 기다리는 경우 P i → P j
• 주기적으로 그래프에서 사이클을 탐색하는 알고리즘을 호출합니다. 사이클이 있으면 교착 상태가 존재합니다.

 

리소스 할당 그래프와 대기 그래프는 같은 정보를 나타냅니다.

그러나 대기 그래프는 리소스 할당 그래프를 변환하여 교착 상태를 검출하기 위한 보조 도구로 사용될 수 있습니다.

 

그래프에서 사이클을 감지하는 알고리즘은 그래프의 정점 수인 n에 대해 n^2의 연산이 필요합니다.

여러 인스턴스가 있는 리소스 유형의 경우 다음과 같은 데이터 구조가 사용됩니다:

• Available: 길이가 m인 벡터
• Allocation: n x m 행렬
• Request: n x m 행렬

Request[i][j] = k 인 경우, 프로세스 P i가 리소스 유형 R j의 k개의 인스턴스를 요청하고 있음을 나타냅니다.

 

 

탐지 알고리즘은 다음과 같습니다:

1. Work 및 Finish를 길이가 m 및 n인 벡터로 초기화합니다.  초기화:
   • Work = Available
   • 만약 Allocationi ≠ 0이면, Finish[i] = false; i=0, 1, ..., n-1
   • 그렇지 않으면, Finish[i] = true.
2. 다음을 만족하는 인덱스 i를 찾습니다: (a) Finish[i] == false (b) Needi Requesti ≤ Work 만약 이러한 i가 존재하지 않으면, 단계 4로 이동합니다.
3. Work = Work + Allocationi Finish[i] = true 단계 2로 이동합니다.
4. 만약 어떤 i에 대해 Finish[i] == false이면, 0 ≤ i ≤ n-1, 그러면 시스템은 데드락 상태에 있습니다. 더 나아가, Finish[i] == false이면, Pi가 데드락에 걸렸습니다.

이 알고리즘은 시스템이 데드락 상태에 있는지 여부를 감지하기 위해 O(m x n^2)의 작업을 수행합니다.

 

 

• 다섯 개의 프로세스 P0부터 P4
• 세 개의 리소스 유형
  • A (7개 인스턴스), B (2개 인스턴스), C(6개 인스턴스).

위의 스냅샷을 바탕으로 시퀀스 <P0, P2, P3, P1, P4>를 실행하면 모든 i에 대해 Finish [i] = true가 됩니다.

이 시점에서 P2가 C 유형의 추가적인 인스턴스를 요청했습니다. 현재 시스템 상태는 다음과 같습니다

 

이 시점에서 P0의 리소스를 회수하여 P1의 요청을 충족시킬 수 있지만, 나머지 프로세스의 요청을 충족시키기에 충분한 리소스가 없습니다. 따라서 P1, P2, P3 및 P4가 포함된 데드락이 발생했습니다.

감지 알고리즘을 언제 호출할지 및 얼마나 자주 호출할지 결정하는 것은 다음과 같은 사항에 따라 달라집니다:

1. 데드락이 발생할 가능성이 얼마나 있는가?
2. 몇 개의 프로세스가 롤백되어야 하는가?
   • 각각의 상이한 사이클마다 하나씩 필요합니다.

또한, 감지 알고리즘을 임의로 호출할 경우 다음과 같은 문제가 발생할 수 있습니다:

• 자원 그래프에 많은 사이클이 존재할 수 있습니다.
• 그러므로 여러 데드락 프로세스 중 어느 것이 데드락을 "유발"시켰는지 알 수 없게 됩니다.

데드락에서의 복구는 프로세스를 종료하는 여러 가지 방법이 있습니다:

1. 모든 데드락된 프로세스를 중단합니다.
2. 데드락 사이클이 제거될 때까지 한 번에 하나의 프로세스를 중단합니다.

중단할 프로세스를 선택하는 방법은 다음과 같은 요소를 고려할 수 있습니다:

1. 프로세스의 우선순위
2. 프로세스가 계산한 시간 및 완료까지 남은 시간
3. 프로세스가 사용한 자원
4. 프로세스가 완료하기 위해 필요한 자원
5. 종료해야 할 프로세스의 수
6. 프로세스가 대화형인지 배치인지 여부

데드락에서의 리소스 선점은 세 가지 문제가 있습니다:

1. 피해자 선택 - 비용을 최소화합니다.
2. 롤백 - 안전한 상태로 돌아가고 해당 상태의 프로세스를 다시 시작합니다.
3. 기아 - 항상 같은 프로세스가 희생자로 선택될 수 있습니다. → 비용 요소에 롤백 횟수를 포함하여 이 문제를 해결합니다.