[Daily morning study] Deadlock (교착 상태)의 4가지 발생 조건과 해결 방법
#daily morning study
Deadlock (교착 상태) 이해하기
Deadlock, 즉 교착 상태는 두 개 이상의 프로세스가 서로 자원을 점유하고 있어, 다른 프로세스의 자원을 기다리며 무한 대기 상태에 빠지는 현상입니다. 교착 상태는 시스템의 성능을 저하시키고 비효율을 초래하므로 이해하고 해결하는 것이 중요합니다.
1. Deadlock 발생의 4가지 조건
교착 상태가 발생하기 위해서는 다음의 네 가지 조건이 모두 만족되어야 합니다:
1.1 상호 배제 (Mutual Exclusion)
- 적어도 하나의 자원(resource)이 비독점적으로 사용될 수 없게 한다는 조건입니다. 즉, 자원은 한 번에 하나의 프로세스만 사용할 수 있어야 합니다.
1.2 점유 및 대기 (Hold and Wait)
- 이미 자원을 점유하고 있는 프로세스가 추가 자원을 요청하며 대기할 수 있어야 합니다. 즉, 최소한 하나의 자원을 점유한 상태에서 다른 자원을 얻기 위해 블록된 상태여야 합니다.
1.3 비선점 (No Preemption)
- 이미 할당된 자원은 강제로 회수할 수 없어야 합니다. 프로세스가 자원을 반납하지 않고 대기하는 상태여야 합니다.
1.4 원형 대기 (Circular Wait)
- 프로세스 집합이 순환구조를 형성하여 대기해야 합니다. 즉, 프로세스 A가 프로세스 B의 자원을 기다리고, 프로세스 B는 프로세스 C의 자원을 기다리며, 이와 같이 연결되어 결국 프로세스 N이 프로세스 A의 자원을 기다리는 형상입니다.
2. Deadlock 해결 방법
Deadlock을 해결하기 위해 사용되는 대표적인 접근 방식은 다음과 같습니다:
2.1 예방 (Prevention)
교착 상태가 발생하지 않도록 시스템이 사전에 조치를 취하는 방법입니다. 이를 위해 교착 상태 발생의 4가지 조건 중 최소 하나를 위반하는 전략을 사용할 수 있습니다.
- 상호 배제 방지: 자원이 비공유되는 형식으로 설계합니다.
- 점유 및 대기 방지: 프로세스는 자원을 요청하기 전에 모든 자원을 우선 대기해야 합니다.
- 비선점 방지: 자원을 요구할 때 다른 자원이 이미 점유되고 있다면 수행을 중단하고 현재 자원을 반납합니다.
- 원형 대기 방지: 모든 자원에 일정한 순서(priority order)를 부여하여 순서를 마련합니다. 프로세스가 자원을 요청할 때는 이 순서를 따라야 합니다.
2.2 회피 (Avoidance)
교착 상태가 발생할 수 있는 상황을 피하는 방법입니다. 이를 위해 다음과 같은 기법이 존재합니다.
- 은행원 알고리즘 (Banker’s Algorithm): 프로세스의 최대 자원 요구량과 현재 시점에서 이용가능한 자원의 수를 바탕으로 안전 상태(safe state)에서만 자원을 할당합니다.
2.3 탐지 및 회복 (Detection and Recovery)
시스템이 주기적으로 상태를 점검하여 교착 상태를 탐지하고 회복하는 방법입니다.
교착 상태 탐지 알고리즘: 그래프 이론을 활용하여 프로세스와 자원의 관계를 나타내는 우선순위 그래프를 구축하고 사이클을 검토합니다.
회복 방법: 탐지 후, 프로세스 중 하나를 종료하거나 자원을 강제로 회수하여 교착 상태를 해소합니다.
# Python으로 구현한 교착 상태 탐지 예시
class Resource:
def __init__(self, total):
self.available = total
self.allocation = []
self.max = []
def request_resource(self, process_id, amount):
# 요청된 자원을 체크하고 할당합니다
if self.available >= amount:
self.allocation[process_id] += amount
self.available -= amount
else:
print("Not enough resources available.")
# 자원과 프로세스 집합
res = Resource(10)
2.4 제거 (Killing Processes)
교착 상태에 빠진 프로세스를 종료하여 자원을 회수하는 방법입니다. 이를 통해 다른 프로세스가 계속 실행되도록 합니다. 이 경우 어떤 프로세스를 종료할지를 결정하는 기준이 필요합니다.
- 우선순위에 기반한 종료: 종료할 프로세스의 중요도나 남은 자원 요구량에 따라 선택합니다.
결론
교착 상태는 시스템 성능에 큰 영향을 미칠 수 있기 때문에 프로세스 설계 시 이를 예방하고 해결하는 방법을 고려해야 합니다. 각 방법의 장단점을 명확히 이해하고 적절한 시기에 알맞은 방법을 적용하는 것이 중요합니다.
