Deadlock 교착 상태의 조건과 자원 할당 대응 전략

자원 할당이 멈추는 지점

여러 프로세스가 한정된 자원을 함께 쓰는 환경에서는 요청과 할당의 순서가 잘못 맞물릴 수 있다. 둘 이상의 프로세스가 상대가 점유한 자원을 기다리면서 자신이 가진 자원은 반환하지 않으면, 관련 프로세스는 더 이상 진행하지 못한다. 이것이 Deadlock, 즉 교착 상태다.

교착 상태는 개별 작업의 지연으로 끝나지 않을 수 있다. 연루된 프로세스가 계속 대기하면서 시스템 성능이 떨어지고, 심한 경우 시스템 전체가 응답하지 않는 상태로 이어질 수 있다.

서로의 자원을 기다리는 구조

⤢✕

이 상태에서는 프로세스가 무한히 대기하고, 자원 요청 관계가 순환한다. 각 프로세스는 점유한 자원을 반환하지 못하므로 관련 작업은 진행할 수 없다.

좁은 다리에 양쪽 차량이 진입해 서로를 막고 후진도 할 수 없는 상황이 비슷한 비유다. 식사하는 철학자 문제에서는 5명의 철학자가 원형 테이블에서 왼쪽 포크를 든 채 오른쪽 포크를 기다린다. 네거리의 모든 방향에서 차량이 진입해 움직이지 못하는 경우도 같은 구조로 볼 수 있다.

교착 상태를 만드는 조건

교착 상태는 다음 조건이 동시에 성립할 때 발생한다.

상호 배제

⤢✕

한 자원은 한 번에 하나의 프로세스만 사용할 수 있다. 프린터, 테이프 드라이브, 데이터베이스 레코드처럼 배타적으로 다뤄야 하는 자원이 여기에 해당한다. 이런 성질은 자원의 일관성과 무결성을 유지하는 데 필요하다.

점유 대기

⤢✕

프로세스가 최소 하나의 자원을 점유한 채 다른 자원을 기다리는 상태다. 예를 들어 프로세스 A가 파일을 열어둔 상태에서 네트워크 소켓 할당을 기다릴 수 있다. 부분 할당 상태에서 이미 확보한 자원을 놓지 않고 대기한다는 점이 문제다.

비선점

⤢✕

이미 할당한 자원을 다른 프로세스가 강제로 빼앗을 수 없는 조건이다. 프로세스가 사용 중인 메모리 페이지를 다른 프로세스가 강제로 가져갈 수 없는 경우가 예시다. 자원은 자발적 반환만 가능하며, 이는 자원의 일관성과 프로세스 안전성을 위한 제약이다.

순환 대기

⤢✕

프로세스-자원 할당 그래프에 순환 구조가 존재하는 경우다. {P1, P2, ..., Pn}에서 P1은 P2가 점유한 자원을 기다리고, P2는 P3가 점유한 자원을 기다리며, Pn은 P1이 점유한 자원을 기다리는 관계다. 이 조건이 없으면 Deadlock은 발생하지 않으며, Resource Allocation Graph에서는 사이클로 표현된다.

안전 상태를 확인하는 자원 요청

Banker's Algorithm은 은행이 대출 전에 안전성을 확인하는 방식에 비유한 회피 기법이다. 자원을 할당하기 전에 시스템이 안전 상태인지 검사한다. 안전 상태란 모든 프로세스가 정상적으로 끝날 수 있는 실행 순서가 존재하는 상태이며, 불안전 상태는 Deadlock이 발생할 가능성이 있는 상태다.

⤢✕

안전성 판단에는 현재 사용 가능한 자원인 Available, 각 프로세스의 최대 요구량인 Max, 현재 할당량인 Allocation, 추가 요구량인 Need를 사용한다.

Need[i][j] = Max[i][j] - Allocation[i][j]

안전성 검사는 완료 가능한 프로세스를 찾아 할당 자원을 Work에 되돌리고, 이 과정을 더 이상 진행할 수 없을 때까지 반복한다.

# 의사 코드
def is_safe_state():
    Work = Available.copy()
    Finish = [False] * n  # n은 프로세스 개수

    while True:
        found = False
        for i in range(n):
            if not Finish[i] and Need[i] <= Work:
                Work += Allocation[i]
                Finish[i] = True
                found = True
                break

        if not found:
            break

    return all(Finish)  # 모든 프로세스가 완료 가능하면 안전

타임스탬프로 순환을 끊는 방식

Wait-Die는 각 프로세스의 생성 시간을 기준으로 대기와 종료를 선택한다. 오래된 프로세스는 대기하고, 새로운 프로세스는 종료한 뒤 재시작한다.

⤢✕

규칙은 다음과 같다.

if TS(Pi) < TS(Pj) then Wait else Die

이 방식은 순환 대기를 막지만, 새로운 프로세스는 반복적으로 종료될 수 있다.

Wound-Wait는 같은 타임스탬프 기준을 사용하지만 처리 방향이 다르다. 오래된 프로세스는 자원을 선점하고, 새로운 프로세스는 대기한다.

⤢✕

if TS(Pi) < TS(Pj) then Wound else Wait

오래된 프로세스의 우선순위를 보장하는 대신, 새로운 프로세스가 자주 선점당할 수 있다. 프로세스가 재시작해도 기존 타임스탬프를 유지하는 Timestamp Rollback은 이 문제를 완화한다. 반복적으로 종료된 프로세스가 결국 가장 오래된 프로세스가 되어 실행 기회를 얻도록 하는 방식이다.

예방부터 복구까지의 대응

예방은 교착 상태의 필요조건 중 하나 이상을 성립하지 않게 만들어 발생 자체를 막는 접근이다.

공유가 가능한 자원은 상호 배제를 제거할 수 있다. 읽기 전용 파일은 여러 프로세스가 동시에 접근할 수 있다. 다만 프린터처럼 본질적으로 배타적인 자원에는 적용할 수 없다.

⤢✕

점유 대기를 없애려면 프로세스 시작 시 필요한 자원을 한 번에 요청하게 하거나, 아무 자원도 점유하지 않은 상태에서만 새 자원을 요청하도록 한다. Deadlock은 완전히 막을 수 있지만 자원 활용률이 낮아지고 Starvation이 발생할 수 있다.

비선점을 부정하는 방식에서는 다른 자원을 기다리는 프로세스가 점유한 자원을 선점할 수 있게 한다. CPU 레지스터나 메모리처럼 상태를 저장할 수 있는 자원에 적용할 수 있지만, 프린터와 테이프 드라이브처럼 선점할 수 없는 자원도 존재한다.

순환 대기는 자원에 순서를 부여해 차단한다. 프로세스는 오름차순으로만 자원을 요청할 수 있다.

⤢✕

F(Ri) < F(Rj) 순서로만 요청하게 하면 순환 대기 구조를 만들 수 없다. 구현이 비교적 간단하고 실용적인 방법이다.

회피는 요청이 들어올 때마다 시스템 상태를 검사해 안전한 경우에만 할당한다. Banker's Algorithm이나 Resource Allocation Graph의 사이클 검사가 사용된다. 자원 활용률은 높일 수 있지만, 최대 자원 요구량을 미리 알아야 하고 검사 오버헤드가 따른다.

탐지는 자원 할당을 허용한 뒤 주기적으로 교착 상태를 찾는 방식이다.

⤢✕

Resource Allocation Graph에서 사이클을 찾으며, 일정 주기 또는 자원 활용률이 저하될 때 검사할 수 있다.

# 자원 할당 그래프에서 사이클 탐지
def detect_deadlock():
    Available = get_available_resources()
    Allocation = get_allocation_matrix()
    Request = get_request_matrix()

    Work = Available.copy()
    Finish = [False] * n

    while True:
        found = False
        for i in range(n):
            if not Finish[i] and Request[i] <= Work:
                Work += Allocation[i]
                Finish[i] = True
                found = True
                break

        if not found:
            break

    # Deadlock에 연루된 프로세스 반환
    deadlocked = [i for i in range(n) if not Finish[i]]
    return deadlocked

탐지 후에는 복구가 필요하다. 연루된 모든 프로세스를 종료하면 빠르게 해결할 수 있으나 작업 손실이 크다. 하나씩 종료하는 방식은 손실을 줄일 수 있지만 반복 검사가 필요하다.

⤢✕

종료 대상은 우선순위가 낮은 프로세스, 실행 시간이 짧은 프로세스, 사용한 자원이 적은 프로세스, 대화형이 아닌 배치 프로세스 등을 기준으로 선택할 수 있다. 자원 선점으로 복구할 때는 비용이 가장 낮은 자원을 고르고, 프로세스를 이전 안전 상태로 Rollback한다. 같은 프로세스가 반복적으로 선점당하지 않도록 관리해야 한다.

교착 상태와 기아 상태의 차이

Deadlock에서는 2개 이상의 프로세스가 서로의 자원을 기다린다. 4가지 필요조건이 모두 충족되어야 하며, 외부 개입 없이는 해결할 수 없다.

⤢✕

Starvation은 특정 프로세스가 자원을 할당받지 못해 계속 대기하는 상태다. 불공정한 스케줄링이나 우선순위 시스템의 부작용으로 발생하며, 우선순위 조정과 Aging 기법으로 대응할 수 있다.

⤢✕

특성	Deadlock	Starvation
대기 프로세스 수	2개 이상 (상호 대기)	1개 (일방적 대기)
발생 조건	4가지 조건 모두 필요	자원 할당 정책의 문제
자원 점유	서로 다른 자원 점유	자원 점유하지 않을 수 있음
대기 관계	순환적 대기	일방적 대기
해결 방법	프로세스 종료/자원 선점	우선순위 조정, Aging
심각도	매우 심각 (시스템 마비)	심각 (개별 프로세스 진행 불가)

Aging은 대기 시간에 비례해 우선순위를 점진적으로 높이는 방식이다. 오래 대기한 프로세스가 결국 최고 우선순위를 얻어 실행될 기회를 보장한다.

⤢✕

시스템별 관리 방식

데이터베이스 시스템은 트랜잭션 Lock과 2단계 잠금 프로토콜을 사용한다. Wait-for Graph를 주기적으로 검사하고, Deadlock을 발견하면 트랜잭션을 롤백해 복구한다.

운영체제는 발생 확률과 오버헤드를 고려해 Deadlock을 무시하는 경우가 많다. 일부 자원, 예를 들어 메모리에는 Banker's Algorithm을 적용할 수 있으며, 응용 프로그램 수준에서의 예방도 권장된다.

분산 시스템에서는 Wait-Die와 Wound-Wait 같은 타임스탬프 기반 기법을 활용할 수 있다. 전역 Wait-for Graph를 구성해 검사하거나, 일정 시간 동안 대기한 뒤 자동 Rollback하는 타임아웃 방식도 사용한다.