교착상태(Deadlock)란 무엇이며 발생 조건과 해결 방법은?

교착상태(Deadlock)는 둘 이상의 프로세스/스레드가 서로 상대방이 보유한 자원을 기다리며 영원히 진행되지 못하는 상태입니다. 마치 좁은 다리에서 양쪽에서 오는 차들이 서로 양보하지 않아 모두 멈추는 것처럼, 시스템이 멈추게 됩니다. 운영체제와 데이터베이스 분야에서 반드시 이해해야 하는 중요한 개념입니다.

교착상태 개요

교착상태 발생 시나리오

프로세스 P1: 자원 A를 보유 → 자원 B를 요청 (대기)
프로세스 P2: 자원 B를 보유 → 자원 A를 요청 (대기)

결과: P1은 P2가 B를 놓아줄 때까지 대기
      P2는 P1이 A를 놓아줄 때까지 대기
      → 둘 다 영원히 대기 (교착상태!)

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

원 = 프로세스, 사각형 = 자원

교착상태 있음:                교착상태 없음:
P1 → R1 → P2                 P1 → R1
↑         ↓                        ↓
R2 ← P2   P3               P2 →      P3
          ↑
          R2

(순환 대기 = 교착상태)

교착상태 발생 조건 (4가지)

코프만(Coffman) 조건이라고도 불리며, 4가지 조건이 모두 동시에 충족될 때 교착상태가 발생합니다.

조건 1: 상호 배제 (Mutual Exclusion)

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

import threading

printer = threading.Lock()  # 프린터는 한 번에 한 프로세스만 사용

def print_document(doc):
    with printer:  # 상호 배제 - 다른 스레드는 대기
        print(f"인쇄 중: {doc}")

조건 2: 점유와 대기 (Hold and Wait)

프로세스가 자원을 보유한 채로 다른 자원을 기다립니다.

# P1이 lock_a를 보유한 채로 lock_b를 요청
def process_p1(lock_a, lock_b):
    lock_a.acquire()  # lock_a 획득 (점유)
    print("P1: lock_a 획득")
    # ... 처리 중 ...
    lock_b.acquire()  # lock_b 요청 (대기) - 교착상태 가능!
    print("P1: lock_b 획득")
    lock_b.release()
    lock_a.release()

조건 3: 비선점 (No Preemption)

이미 할당된 자원을 강제로 빼앗을 수 없습니다.

P1이 CPU와 파일 A를 사용 중일 때,
운영체제가 강제로 P1에게서 파일 A를 빼앗아 P2에게 줄 수 없음
→ P1이 자발적으로 놓아줄 때까지 P2는 기다려야 함

조건 4: 순환 대기 (Circular Wait)

프로세스들이 원형 체인을 형성하여 서로의 자원을 기다립니다.

P1 → P2 → P3 → P1 (순환)

P1은 P2의 자원을,
P2는 P3의 자원을,
P3는 P1의 자원을 기다림

실제 교착상태 코드 예시

import threading
import time

lock_a = threading.Lock()
lock_b = threading.Lock()

def thread1():
    with lock_a:
        print("Thread 1: lock_a 획득")
        time.sleep(0.1)  # P2가 lock_b를 획득할 시간을 줌
        print("Thread 1: lock_b 기다리는 중...")
        with lock_b:  # 영원히 대기 가능!
            print("Thread 1: lock_b 획득 (교착상태가 아니면 출력)")

def thread2():
    with lock_b:
        print("Thread 2: lock_b 획득")
        time.sleep(0.1)
        print("Thread 2: lock_a 기다리는 중...")
        with lock_a:  # 영원히 대기 가능!
            print("Thread 2: lock_a 획득 (교착상태가 아니면 출력)")

t1 = threading.Thread(target=thread1)
t2 = threading.Thread(target=thread2)
t1.start()
t2.start()
# 프로그램이 멈춤 - 교착상태 발생!

교착상태 해결 방법

방법 1: 예방 (Prevention)

4가지 발생 조건 중 하나를 제거하여 교착상태가 아예 발생하지 않도록 합니다.

상호 배제 제거

공유 가능한 자원은 상호 배제를 요구하지 않습니다. 단, 쓰기 작업에는 상호 배제가 필요하므로 완전히 제거하기 어렵습니다.

# 읽기 전용 자원은 여러 스레드가 동시 접근 가능
import threading

data = {"key": "value"}
read_lock = threading.RLock()  # 재진입 가능한 락

def read_data():
    with read_lock:
        return data["key"]  # 여러 스레드 동시 읽기 허용 가능

점유와 대기 제거

프로세스 시작 시 필요한 자원을 모두 한꺼번에 요청하거나, 자원을 하나도 보유하지 않은 상태에서만 요청합니다.

def safe_thread(lock_a, lock_b):
    # 방법 1: 모든 자원을 한 번에 획득 (all-or-nothing)
    # timeout을 이용해 모두 못 얻으면 포기
    acquired_a = lock_a.acquire(timeout=1)
    if not acquired_a:
        return False

    acquired_b = lock_b.acquire(timeout=1)
    if not acquired_b:
        lock_a.release()  # 실패 시 보유한 자원 반납
        return False

    try:
        # 두 자원 모두 획득 성공
        print("두 자원 모두 획득!")
        return True
    finally:
        lock_b.release()
        lock_a.release()

비선점 제거

자원을 기다리는 프로세스가 보유한 자원을 선점(강제 회수)할 수 있도록 합니다.

CPU 스케줄링에서 선점(Preemptive) 방식:
- 더 높은 우선순위 프로세스가 오면 현재 프로세스의 CPU를 강제로 빼앗음
- 단, 파일이나 뮤텍스는 선점이 어려움

순환 대기 제거 (가장 실용적)

자원에 순서를 부여하고, 프로세스는 항상 정해진 순서대로만 자원을 요청합니다.

import threading

lock_a = threading.Lock()  # 순서 1
lock_b = threading.Lock()  # 순서 2

# 항상 lock_a → lock_b 순서로 요청 (역방향 불가)
def thread1_safe():
    with lock_a:               # 순서 1 먼저
        with lock_b:           # 순서 2 다음
            print("Thread 1 실행")

def thread2_safe():
    with lock_a:               # Thread 2도 동일한 순서!
        with lock_b:
            print("Thread 2 실행")
# → 순환 대기 불가 → 교착상태 예방!

방법 2: 회피 (Avoidance)

자원 할당 전에 안전한 상태인지 확인하고, 안전한 경우에만 자원을 할당합니다.

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

class BankersAlgorithm:
    def __init__(self, allocation, max_need, available):
        self.allocation = allocation  # 현재 할당량 [프로세스][자원]
        self.max_need = max_need      # 최대 필요량
        self.available = available[:]  # 현재 사용 가능량
        self.n = len(allocation)      # 프로세스 수
        self.m = len(available)       # 자원 종류 수

    def is_safe(self):
        """현재 상태가 안전 상태인지 확인"""
        # need[i][j] = 프로세스 i가 추가로 필요한 자원 j의 양
        need = [[self.max_need[i][j] - self.allocation[i][j]
                 for j in range(self.m)]
                for i in range(self.n)]

        work = self.available[:]
        finish = [False] * self.n
        safe_sequence = []

        while len(safe_sequence) < self.n:
            found = False
            for i in range(self.n):
                if not finish[i] and all(need[i][j] <= work[j]
                                          for j in range(self.m)):
                    # 프로세스 i 실행 가능 → 완료 후 자원 반납
                    work = [work[j] + self.allocation[i][j]
                            for j in range(self.m)]
                    finish[i] = True
                    safe_sequence.append(i)
                    found = True
                    break

            if not found:
                return False, []  # 안전 순서 없음 → 교착상태 가능

        return True, safe_sequence

# 사용 예
allocation = [[0,1,0], [2,0,0], [3,0,2], [2,1,1], [0,0,2]]
max_need   = [[7,5,3], [3,2,2], [9,0,2], [2,2,2], [4,3,3]]
available  = [3, 3, 2]

banker = BankersAlgorithm(allocation, max_need, available)
safe, sequence = banker.is_safe()
if safe:
    print(f"안전 상태 - 실행 순서: {sequence}")
else:
    print("교착상태 위험!")

방법 3: 탐지 (Detection)

교착상태 발생을 허용하되, 주기적으로 탐지하여 해결합니다.

def detect_deadlock(wait_for_graph):
    """Wait-For 그래프에서 사이클 탐지 = 교착상태 탐지"""
    visited = set()
    rec_stack = set()

    def has_cycle(node):
        visited.add(node)
        rec_stack.add(node)

        for neighbor in wait_for_graph.get(node, []):
            if neighbor not in visited:
                if has_cycle(neighbor):
                    return True
            elif neighbor in rec_stack:
                return True  # 사이클 발견!

        rec_stack.remove(node)
        return False

    for node in wait_for_graph:
        if node not in visited:
            if has_cycle(node):
                return True

    return False

# 교착상태 있는 그래프 (P1→P2→P3→P1 순환)
graph = {
    'P1': ['P2'],
    'P2': ['P3'],
    'P3': ['P1']
}
print(detect_deadlock(graph))  # True - 교착상태 탐지!

방법 4: 복구 (Recovery)

교착상태 탐지 후 해결하는 방법입니다.

프로세스 종료:

• 교착상태에 관여된 프로세스를 모두 종료 (비용 크나 확실)
• 또는 하나씩 종료하며 교착상태 해소될 때까지 반복

자원 선점:

• 교착상태 프로세스에서 자원을 강제로 빼앗아 다른 프로세스에 할당
• 선점된 프로세스는 롤백(Rollback)하거나 재시작

-- 데이터베이스에서의 교착상태 탐지 및 복구 예시 (MySQL)
-- 교착상태 발생 시 자동으로 하나의 트랜잭션을 롤백

START TRANSACTION;
UPDATE accounts SET balance = balance - 100 WHERE id = 1;  -- 자원 A 점유
-- 다른 트랜잭션이 accounts id=2를 잠그면 교착상태 가능
UPDATE accounts SET balance = balance + 100 WHERE id = 2;
COMMIT;

-- MySQL은 deadlock 탐지 후 자동 롤백:
-- ERROR 1213 (40001): Deadlock found when trying to get lock;
-- try restarting transaction

교착상태 vs 기아 상태 (Starvation)

교착상태: 관련된 모든 프로세스가 진행 불가 (완전한 멈춤)
기아 상태: 특정 프로세스가 자원을 계속 할당받지 못함 (일부 프로세스는 진행)

기아 해결: 에이징(Aging) - 대기 시간이 길어질수록 우선순위를 높임

교착상태 처리 방법 비교표

방법	전략	오버헤드	적용 예
예방 (Prevention)	4가지 조건 중 하나 제거	자원 낭비 가능	자원 순서 고정
회피 (Avoidance)	안전 상태 확인 후 할당	알고리즘 실행 비용	은행원 알고리즘
탐지 (Detection)	발생 허용 후 탐지	탐지 알고리즘 주기 실행	DB 교착상태 탐지
복구 (Recovery)	탐지 후 프로세스 종료/롤백	작업 손실 가능	DB 트랜잭션 롤백
무시	발생 가능성 무시	없음	일부 OS (타조 알고리즘)