운영체제
Deadlock (교착 상태)과 Starvation (기아) 요약
n_0_jun
2025. 4. 8. 14:00
반응형
교착 상태(Deadlock)와 기아(Starvation)는 멀티태스킹 환경에서 중요한 문제로, 여러 프로세스가 자원을 동시에 요구하는 상황에서 발생할 수 있습니다. 이 장에서는 교착 상태의 발생 원인, 예방, 회피, 검출, 해결 방법에 대해 다루고 있습니다.
1. Deadlock의 필요조건 및 필요충분조건
교착 상태가 발생하려면 다음 네 가지 조건이 동시에 충족되어야 합니다:
- 상호 배제 (Mutual Exclusion):
- 자원은 한 번에 하나의 프로세스만 사용할 수 있습니다.
- 점유 및 대기 (Hold and Wait):
- 프로세스가 이미 점유한 자원을 유지하면서 추가 자원을 요청하며 대기합니다.
- 비선점 (No Preemption):
- 이미 점유한 자원을 강제로 다른 프로세스가 빼앗을 수 없습니다.
- 환형 대기 (Circular Wait):
- 프로세스 간에 자원을 요청하며 순환적인 대기 상태를 형성합니다.
2. Deadlock Prevention (교착 상태 예방)
교착 상태를 예방하려면 위의 네 가지 조건 중 하나 이상을 제거해야 합니다. 이를 위한 두 가지 예시가 있습니다:
- Traffic Deadlock (교통 시스템 비유):
- 문제: 차들이 사거리에서 서로 진행을 막고 대기하는 상황.
- 해결 방법:
- 일방통행 설정: 순환 대기 방지.
- 우선권 부여: 특정 방향에 우선권을 주어 교차로에서 발생하는 대기 상황을 방지.
- Dining Philosophers Problem (식사하는 철학자 문제):
- 문제: 철학자들이 포크를 동시에 요청하며 교착 상태가 발생합니다.
- 해결 방법:
- 포크를 잡기 전에 조건을 추가하여 데드락을 방지 (예: 두 개의 포크가 모두 가능할 때만 잡기).
- 홀수, 짝수 철학자가 각각 다른 순서로 포크를 잡도록 설계하여 교착 상태를 예방.
3. Deadlock Avoidance (교착 상태 회피)
교착 상태를 발생시키지 않도록 자원 요청 시 안전 상태를 예측하고, 비안전 상태에 빠지지 않도록 회피하는 방법입니다.
- 안전 상태와 비안전 상태:
- 안전 상태 (Safe State): 모든 프로세스가 순서대로 자원을 얻고 작업을 끝낼 수 있는 상태.
- 비안전 상태 (Unsafe State): 데드락 발생 가능성이 있는 상태.
- Banker's Algorithm (은행가 알고리즘):
- 원리: 자원 요청을 허용하기 전에 시스템이 안전 상태인지 확인합니다.
- 작동 과정:
- 각 프로세스의 최대 자원 요청과 현재 사용량을 확인합니다.
- 요청한 자원을 할당한 뒤 시스템이 안전 상태로 유지되는지 검사합니다.
- 시스템이 안전 상태이면 자원을 할당하고, 그렇지 않으면 자원 할당을 거절합니다.
4. Deadlock Detection (교착 상태 검출)
교착 상태를 허용한 후 이를 탐지하고 해결하는 방법입니다.
- Detection 알고리즘:
- 자원 할당 그래프 (Resource Allocation Graph): 노드와 간선을 활용하여 프로세스와 자원의 관계를 나타냅니다.
- 순환 (Cycle): 그래프에서 순환이 발견되면 교착 상태가 발생한 것입니다.
- 가용 자원과 요청 상태를 바탕으로 교착 상태를 탐지합니다.
- 자원이 없는 프로세스를 계속해서 제거하고, 남은 프로세스들 간에 순환이 있는지 확인합니다.
- Deadlock 해결 방법:
- 강제 종료: 교착 상태에 빠진 프로세스를 종료합니다.
- 자원 회수: 특정 프로세스에서 자원을 강제로 빼앗아 다른 프로세스에 할당합니다.
- 롤백(Rollback): 교착 상태 이전의 안전한 상태로 복구합니다.
정리
- Deadlock Prevention(예방)은 주로 이론적인 방법이며, Deadlock Detection and Recovery(검출 및 복구)는 실무에서 더 현실적인 방법으로 많이 사용됩니다.
- 자원의 사용 패턴과 우선순위를 고려하여 알고리즘과 기법을 설계하는 것이 중요합니다. 교착 상태가 발생하지 않도록 자원 관리 및 스케줄링을 효율적으로 처리해야 합니다.
반응형