4-6. 데드락 예방, 회피, 감지

데드락 예방, 회피, 감지

데드락은 여러 프로세스들이 서로 다른 프로세스가 가진 자원을 기다리면서, 어떤 프로세스도 더 이상 진행될 수 없는 교착 상태를 의미합니다. 마치 서로의 발을 묶고 멈춰버린 두 선수가 결승선을 향해 나아가지 못하는 상황과 같습니다. 이 심각한 문제는 시스템의 효율성을 저하시키고, 심지어 시스템 전체를 멈추게 할 수도 있습니다. 따라서 데드락을 이해하고, 이를 효과적으로 관리하는 방법은 운영체제 설계 및 시스템 프로그래밍에서 매우 중요합니다.

1) 데드락 발생 조건 복습

데드락을 이해하기 위해서는 먼저 데드락이 발생하는 기본적인 네 가지 조건(Coffman 조건)을 정확히 알아야 합니다. 이 조건들 중 하나라도 충족되지 않으면 데드락은 발생하지 않습니다.

• 상호 배제 (Mutual Exclusion): 자원은 한 번에 하나의 프로세스만 사용할 수 있어야 합니다. 즉, 자원은 공유될 수 없으며, 한 번에 하나의 프로세스만 해당 자원을 점유할 수 있습니다.
• 점유 대기 (Hold and Wait): 프로세스는 자원을 최소한 하나 점유한 상태에서, 다른 자원을 얻기 위해 대기해야 합니다.
• 비선점 (No Preemption): 프로세스가 다른 프로세스가 점유한 자원을 강제로 빼앗을 수 없습니다. 자원은 프로세스가 스스로 해제할 때만 반환됩니다.
• 순환 대기 (Circular Wait): 프로세스들의 집합에서, 각 프로세스가 다음 프로세스가 점유한 자원을 기다리는 순환 구조가 형성되어야 합니다. A가 B의 자원을, B가 C의 자원을, C가 A의 자원을 기다리는 형태가 대표적입니다.

2) 데드락 예방 (Deadlock Prevention)

데드락 예방은 데드락 발생 조건 중 하나 이상을 사전에 제거함으로써 데드락을 방지하는 방법입니다.

가) 상호 배제 조건 완화

상호 배제 조건은 대부분의 자원에 대해 필수적인 조건입니다. 하지만, 자원을 공유 가능한 방식으로 구현할 수 있다면, 데드락을 예방할 수 있습니다. 예를 들어, 읽기 전용 파일의 경우 여러 프로세스가 동시에 접근할 수 있도록 허용하면 상호 배제 조건을 완화할 수 있습니다. 그러나 이 방법은 모든 자원에 적용할 수 없으며, 자원의 특성에 따라 제한적입니다.

나) 점유 대기 조건 완화

점유 대기 조건을 완화하는 방법은 두 가지가 있습니다.

1. 모든 자원을 한 번에 요청하기 (All-or-None): 프로세스가 필요한 모든 자원을 한 번에 요청하고, 모두 할당받을 수 있을 때만 작업을 시작합니다. 만약 하나라도 할당받을 수 없다면, 아무 자원도 할당받지 않고 대기합니다. 이 방식은 자원 낭비가 발생할 수 있으며, 프로세스가 필요한 자원을 모두 알 수 없는 경우 적용하기 어렵습니다.

2. 자원 요청 전에 모든 자원 해제하기 (Release-All-Before-Request): 프로세스가 자원을 요청하기 전에, 현재 점유하고 있는 모든 자원을 해제합니다. 이 방식은 자원 부족으로 인한 기아 상태(starvation)를 유발할 수 있으며, 프로세스의 실행 흐름을 복잡하게 만들 수 있습니다.

다) 비선점 조건 완화

비선점 조건을 완화하는 방법은 다음과 같습니다.

1. 자원 반환 (Resource Preemption): 프로세스가 다른 프로세스가 점유한 자원을 요청했을 때, 해당 자원을 사용할 수 없다면, 현재 점유하고 있는 자원을 반환하도록 합니다. 반환된 자원은 요청 프로세스에게 할당됩니다.
2. 롤백 (Rollback): 프로세스가 자원을 점유하려고 시도했지만 실패했을 경우, 해당 프로세스가 점유하고 있던 자원들을 모두 반환하고, 처음부터 다시 실행합니다. 이 방법은 자원 낭비를 초래할 수 있으며, 복잡한 롤백 메커니즘을 필요로 합니다.

라) 순환 대기 조건 완화

순환 대기 조건을 완화하는 가장 일반적인 방법은 자원에 번호를 매기는 것입니다.

1. 자원 할당 순서 정의 (Resource Ordering): 모든 자원에 고유한 번호를 할당하고, 프로세스는 자원을 요청할 때, 자원의 번호 순서대로 요청해야 합니다. 즉, 더 낮은 번호의 자원을 먼저 요청하고, 높은 번호의 자원을 나중에 요청해야 합니다.
2. 예시: 자원 A(번호 1), 자원 B(번호 2), 자원 C(번호 3)가 있다고 가정합니다. 프로세스 1이 A와 C를 사용해야 한다면, A를 먼저 요청하고 C를 나중에 요청해야 합니다. 프로세스 2가 B와 A를 사용해야 한다면, A를 먼저 요청하고 B를 나중에 요청해야 합니다. 이렇게 하면 순환 대기가 발생할 수 없습니다.

이 방법은 간단하고 효과적이지만, 자원의 번호를 일관되게 관리해야 하며, 새로운 자원이 추가될 때마다 시스템 전체를 다시 고려해야 하는 단점이 있습니다.

3) 데드락 회피 (Deadlock Avoidance)

데드락 회피는 데드락 발생 가능성을 미리 예측하고, 안전한 상태(safe state)를 유지하도록 자원 할당을 조절하는 방법입니다. 데드락 회피 기법은 데드락 발생 가능성을 최소화하면서 시스템의 효율성을 유지할 수 있도록 설계되었습니다.

가) 안전 상태 (Safe State)

안전 상태란 시스템 내의 모든 프로세스가 데드락 없이 종료될 수 있는 상태를 의미합니다. 안전 상태에서는 시스템이 데드락에 빠지지 않도록 자원 할당을 제어할 수 있습니다. 시스템이 안전 상태에 있지 않다면, 이는 데드락 발생 가능성이 있는 위험한 상태(unsafe state)입니다.

나) 자원 할당 그래프 (Resource-Allocation Graph)

자원 할당 그래프는 데드락을 감지하고 회피하는 데 사용되는 도구입니다. 이 그래프는 프로세스와 자원, 그리고 프로세스와 자원 간의 관계를 시각적으로 표현합니다.

• 프로세스 (Process): 프로세스를 나타내는 노드입니다.
• 자원 (Resource): 자원을 나타내는 노드입니다.
• 할당 간선 (Assignment Edge): 자원에서 프로세스로 연결되는 간선입니다. 자원이 프로세스에 할당되었음을 의미합니다. (예: R -> P)
• 요청 간선 (Request Edge): 프로세스에서 자원으로 연결되는 간선입니다. 프로세스가 자원을 요청하고 있음을 의미합니다. (예: P -> R)

자원 할당 그래프를 통해 데드락 발생 여부를 쉽게 파악할 수 있습니다.

• 그래프에 사이클이 없으면, 데드락이 발생하지 않습니다.
• 그래프에 사이클이 존재하면, 데드락이 발생할 수 있습니다. (단, 자원 인스턴스가 여러 개일 때는 사이클이 존재한다고 해서 반드시 데드락이 발생하는 것은 아닙니다.)

다) 은행원 알고리즘 (Banker's Algorithm)

은행원 알고리즘은 데드락 회피를 위한 대표적인 알고리즘입니다. 이 알고리즘은 각 프로세스가 요청할 수 있는 자원의 최대 개수를 미리 알고 있으며, 현재 자원 할당 상태를 기반으로, 안전한 상태를 유지할 수 있는지를 판단하여 자원 할당을 결정합니다. 마치 은행원이 고객에게 대출을 해줄 때, 모든 고객이 돈을 갚을 수 있는지 안전성을 고려하는 것과 유사합니다.

1. 자료 구조:

   • Available: 각 자원 유형별로 사용 가능한 자원의 개수를 나타내는 벡터입니다.
   • Max: 각 프로세스가 각 자원 유형별로 최대 필요로 하는 자원의 개수를 나타내는 행렬입니다.
   • Allocation: 각 프로세스에 할당된 각 자원 유형별 자원의 개수를 나타내는 행렬입니다.
   • Need: 각 프로세스가 각 자원 유형별로 추가로 필요한 자원의 개수를 나타내는 행렬입니다. Need[i][j] = Max[i][j] - Allocation[i][j]

2. 안전성 알고리즘:

   • Work: Available과 동일한 크기의 벡터로, 가용한 자원의 복사본입니다.
   • Finish: 각 프로세스가 안전하게 완료될 수 있는지 여부를 나타내는 Boolean 벡터입니다. 초기값은 false입니다.

   알고리즘:

   1. Allocation 행렬을 검사하여 Finish[i] = false인 프로세스를 찾습니다.
   2. Need[i][j] <= Work[j]인 프로세스를 찾습니다. 즉, 해당 프로세스가 요청하는 모든 자원을 Work가 충분히 가지고 있는지 확인합니다.
   3. 만약 그런 프로세스가 있다면, 해당 프로세스가 완료될 수 있다고 가정하고, 자원을 해제합니다. Work <mark class="highlight"><strong><u> Work + Allocation[i] 그리고 Finish[i] </u></strong></mark> true
   4. 1~3 단계를 모든 프로세스가 Finish[i] = true가 될 때까지 반복합니다.
   5. 모든 프로세스가 안전하게 완료될 수 있다면, 시스템은 안전 상태입니다. 그렇지 않다면, 시스템은 안전하지 않은 상태이며, 데드락이 발생할 가능성이 있습니다.

   예시:

   프로세스	Max	Allocation	Need
   P0	(7,5,3)	(0,1,0)	(7,4,3)
   P1	(3,2,2)	(2,0,0)	(1,2,2)
   P2	(9,0,2)	(3,0,2)	(6,0,0)
   P3	(2,2,2)	(2,1,1)	(0,1,1)
   P4	(4,3,3)	(0,0,2)	(4,3,1)

   Available = (3,3,2)

   1. P1의 Need (1,2,2) < Available (3,3,2) 이므로, P1을 실행할 수 있습니다. Available (3,3,2) + (2,0,0) = (5,3,2)
   2. P3의 Need (0,1,1) < Available (5,3,2) 이므로, P3을 실행할 수 있습니다. Available (5,3,2) + (2,1,1) = (7,4,3)
   3. P0의 Need (7,4,3) < Available (7,4,3) 이므로, P0을 실행할 수 있습니다. Available (7,4,3) + (0,1,0) = (7,5,3)
   4. P2의 Need (6,0,0) < Available (7,5,3) 이므로, P2을 실행할 수 있습니다. Available (7,5,3) + (3,0,2) = (10,5,5)
   5. P4의 Need (4,3,1) < Available (10,5,5) 이므로, P4을 실행할 수 있습니다. Available (10,5,5) + (0,0,2) = (10,5,7)

   따라서, 이 시스템은 안전 상태입니다.

4) 데드락 감지 (Deadlock Detection)

데드락 감지는 시스템이 데드락 상태에 있는지 실시간으로 감지하는 방법입니다. 데드락 감지 기법은 데드락 발생 시, 이를 감지하고 해결하기 위한 조치를 취합니다.

가) 데드락 감지 알고리즘

데드락 감지 알고리즘은 자원 할당 그래프 또는 다른 자료 구조를 사용하여 시스템 내의 데드락을 주기적으로 검사합니다.

1. 자원 할당 그래프 기반 데드락 감지: 자원 할당 그래프에서 사이클을 찾습니다. 사이클이 발견되면 데드락이 발생한 것으로 간주합니다.

2. 알고리즘:

   • Allocation: 각 프로세스에 할당된 각 자원 유형별 자원의 개수를 나타내는 행렬입니다.
   • Request: 각 프로세스가 각 자원 유형별로 요청하는 자원의 개수를 나타내는 행렬입니다.
   • Available: 각 자원 유형별로 사용 가능한 자원의 개수를 나타내는 벡터입니다.
   • Work: Available과 동일한 크기의 벡터로, 가용한 자원의 복사본입니다.
   • Finish: 각 프로세스가 완료되었는지 여부를 나타내는 Boolean 벡터입니다. 초기값은 false입니다.

   알고리즘:

   1. Allocation 행렬을 검사하여 Finish[i] = false인 프로세스를 찾습니다.
   2. Request[i][j] <= Available[j]인 프로세스를 찾습니다. 즉, 해당 프로세스가 요청하는 모든 자원을 Available이 충분히 가지고 있는지 확인합니다.
   3. 만약 그런 프로세스가 있다면, Available <mark class="highlight"><strong><u> Available + Allocation[i] 그리고 Finish[i] </u></strong></mark> true
   4. 1~3 단계를 모든 프로세스가 Finish[i] = true가 될 때까지 반복합니다.
   5. 만약 Finish[i] = false인 프로세스가 존재한다면, 해당 프로세스는 데드락에 연루된 것입니다.

3. 예시:

   프로세스	Request	Allocation	Available
   P0	(0,0,0)	(0,0,0)	(0,0,0)
   P1	(1,0,0)	(0,1,0)
   P2	(0,0,0)	(1,0,0)

   1. P0의 Request (0,0,0) <= Available (0,0,0) 이므로, P0을 실행할 수 있습니다.
   2. P1의 Request (1,0,0) <= Available (0,0,0) 이 아니므로, P1을 실행할 수 없습니다.
   3. P2의 Request (0,0,0) <= Available (0,0,0) 이므로, P2을 실행할 수 있습니다.
   4. Finish[i] = false인 프로세스가 존재합니다. (P1)
   5. P1은 데드락에 연루되었습니다.

나) 데드락 회복 (Deadlock Recovery)

데드락이 감지되면, 시스템은 데드락을 해결하기 위한 조치를 취해야 합니다.

1. 프로세스 중단 (Process Termination): 데드락에 연루된 프로세스를 중단합니다.

   • 모든 프로세스 중단 (Abort all processes): 가장 간단한 방법이지만, 시스템의 모든 작업을 잃을 수 있습니다.
   • 하나씩 프로세스 중단 (Abort one process at a time): 데드락을 해결할 때까지, 하나씩 프로세스를 중단합니다. 중단할 프로세스를 선택하는 기준은 다음과 같습니다.
     • 프로세스의 우선순위
     • 프로세스가 완료되기까지 남은 시간
     • 프로세스가 사용한 자원의 수
     • 프로세스가 요청한 자원의 수
     • 프로세스가 실행되는 동안의 비용

2. 자원 선점 (Resource Preemption): 데드락에 연루된 프로세스로부터 자원을 빼앗아 다른 프로세스에 할당합니다.

   • 자원 선택 기준은 다음과 같습니다.
     • 자원의 우선순위
     • 자원을 점유한 프로세스의 우선순위
     • 자원의 사용 시간
     • 자원의 반환 비용
     • 자원을 점유한 프로세스의 수

   자원 선점은 자원 낭비를 최소화할 수 있지만, 자원을 빼앗긴 프로세스는 다시 실행해야 하며, 롤백을 수행해야 할 수도 있습니다.

5) 데드락 예방, 회피, 감지 기법 비교

6) 결론

데드락은 운영체제에서 매우 중요한 문제이며, 데드락을 관리하는 다양한 방법이 존재합니다. 데드락 예방은 데드락 발생 조건을 제거하여 데드락을 사전에 방지하는 방법입니다. 데드락 회피는 안전 상태를 유지하여 데드락 발생 가능성을 최소화합니다. 데드락 감지는 데드락 발생 시, 이를 감지하고 해결하기 위한 조치를 취합니다. 각 기법은 장단점이 있으며, 시스템의 특성과 요구 사항에 따라 적절한 기법을 선택해야 합니다. 일반적으로, 시스템은 데드락 예방, 회피, 감지 기법을 함께 사용하여 데드락 문제를 해결합니다.