전체 목록
운영체제Medium#83

데드락(Deadlock)이란 무엇이며, 발생 조건 4가지와 해결 방법을 설명해주세요.

#OS#데드락#프로세스#동기화
힌트

Coffman 조건 4가지를 떠올려보세요.

정답 및 해설

데드락(Deadlock)이란 무엇이며, 발생 조건 4가지와 해결 방법을 설명해주세요.

데드락(Deadlock)은 둘 이상의 프로세스(또는 스레드)가 서로가 점유하고 있는 자원을 기다리며 영원히 대기하는 상태를 말합니다. 어떤 프로세스도 앞으로 진행할 수 없는 교착 상태이므로 시스템 전체가 멈추게 됩니다. 운영체제, 데이터베이스, 멀티스레드 프로그래밍에서 모두 발생할 수 있는 중요한 개념입니다.

데드락 발생 상황 예시

프로세스 A: 자원 1 보유, 자원 2 요청
프로세스 B: 자원 2 보유, 자원 1 요청

상황:
┌────────────┐        보유         ┌──────────┐
│ 프로세스 A │ ──────────────────> │  자원 1  │
└────────────┘                     └──────────┘
       │                                 ↑
       │ 요청                            │ 요청
       ▼                                 │
┌──────────┐         보유         ┌────────────┐
│  자원 2  │ <────────────────── │ 프로세스 B │
└──────────┘                     └────────────┘

→ A는 자원 2를 기다리고, B는 자원 1을 기다림
→ 서로 무한 대기 = 데드락!

데드락 발생 조건 (Coffman 조건)

1969년 Coffman이 제시한 4가지 조건이 모두 동시에 만족될 때 데드락이 발생합니다. 하나라도 없으면 데드락이 발생하지 않습니다.

1. 상호 배제 (Mutual Exclusion)

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

자원 R1: 프로세스 A가 점유 중
         → 프로세스 B는 A가 자원을 해제할 때까지 대기해야 함

예: 프린터, 데이터베이스 레코드 락, 뮤텍스(Mutex)

2. 점유와 대기 (Hold and Wait)

프로세스가 최소 하나의 자원을 보유한 채로 다른 프로세스가 점유 중인 자원을 기다립니다.

프로세스 A: 자원 R1 보유 (Hold) + 자원 R2 대기 (Wait)

예: 파일을 열어둔 채로 데이터베이스 연결을 기다림

3. 비선점 (Non-Preemption)

프로세스가 보유한 자원을 강제로 빼앗을 수 없으며, 자원은 오직 보유한 프로세스가 자발적으로 해제할 때만 반환됩니다.

프로세스 A가 자원 R1을 보유 중
→ OS나 프로세스 B가 강제로 R1을 빼앗을 수 없음
→ A가 작업을 마치고 스스로 해제해야만 함

4. 순환 대기 (Circular Wait)

프로세스들이 원형(환형)으로 서로의 자원을 기다립니다.

P1 → P2 → P3 → P1 (순환)

P1: P2가 보유한 자원 대기
P2: P3가 보유한 자원 대기
P3: P1이 보유한 자원 대기

자원 할당 그래프에서 사이클(Cycle) 발생

데드락 해결 방법

데드락 처리 방법은 크게 4가지로 분류됩니다.

1. 예방 (Prevention): Coffman 조건 중 하나 제거

조건 1 제거: 상호 배제 제거
────────────────────────────
- 자원을 공유 가능하게 만듦
- 읽기 전용 파일 등에 적용 가능
- 뮤텍스 등 본질적으로 배타적인 자원에는 적용 불가

조건 2 제거: 점유와 대기 제거
──────────────────────────────
- 방법 1: 모든 자원을 한꺼번에 요청하고, 하나라도 불가능하면 아무것도 할당하지 않음
  → 자원 낭비, 기아(Starvation) 발생 가능
- 방법 2: 자원을 요청하기 전에 보유 중인 모든 자원 해제

조건 3 제거: 비선점 제거
──────────────────────────
- 프로세스가 새 자원을 얻을 수 없으면, 보유 중인 자원을 모두 반환
- CPU 스케줄링(선점형)에 적용 가능
- 프린터 등 일부 자원에는 선점 불가

조건 4 제거: 순환 대기 제거 (가장 실용적)
────────────────────────────────────────
- 자원에 번호를 부여하고, 오름차순으로만 자원을 요청하도록 강제
- 순환이 형성되지 않음

순환 대기 제거 코드 예시

// 잘못된 방법 - 데드락 발생 가능
public class DeadlockExample {
    private final Object lock1 = new Object();
    private final Object lock2 = new Object();

    // 스레드 A
    public void methodA() {
        synchronized (lock1) {        // lock1 획득
            synchronized (lock2) {    // lock2 획득
                // 작업
            }
        }
    }

    // 스레드 B - lock 순서가 반대!
    public void methodB() {
        synchronized (lock2) {        // lock2 획득
            synchronized (lock1) {    // lock1 획득 (A가 보유 중이면 데드락!)
                // 작업
            }
        }
    }
}

// 올바른 방법 - 항상 같은 순서로 락 획득
public class DeadlockFreeExample {
    private final Object lock1 = new Object();
    private final Object lock2 = new Object();

    // 스레드 A
    public void methodA() {
        synchronized (lock1) {
            synchronized (lock2) { /* 작업 */ }
        }
    }

    // 스레드 B - 동일한 순서로 락 획득
    public void methodB() {
        synchronized (lock1) {  // 항상 lock1 먼저!
            synchronized (lock2) { /* 작업 */ }
        }
    }
}

2. 회피 (Avoidance): 은행원 알고리즘

시스템이 항상 **안전 상태(Safe State)**를 유지하도록 자원을 할당합니다.

은행원 알고리즘 (Banker's Algorithm):
- 각 프로세스가 최대 요청량을 미리 선언
- 자원 요청 시 할당 후에도 안전 상태인지 검사
- 안전 상태: 모든 프로세스를 완료할 수 있는 실행 순서가 존재하는 상태

예시:
총 자원: 12개
현재 할당 상태:
  P1: 할당 5개, 최대 9개 필요 → 추가 필요: 4개
  P2: 할당 2개, 최대 3개 필요 → 추가 필요: 1개
  P3: 할당 2개, 최대 7개 필요 → 추가 필요: 5개
가용 자원: 12 - 5 - 2 - 2 = 3개

안전 순서: P2(1개 추가) → P1(4개 추가) → P3(5개 추가)
→ 안전 상태, 자원 할당 허용

# 은행원 알고리즘 (Python 의사 코드)
def is_safe_state(available, max_need, allocation):
    n_processes = len(allocation)
    n_resources = len(available)

    work = available.copy()
    finish = [False] * n_processes
    need = [[max_need[i][j] - allocation[i][j]
             for j in range(n_resources)]
             for i in range(n_processes)]

    # 안전 시퀀스 찾기
    safe_sequence = []
    while len(safe_sequence) < n_processes:
        found = False
        for i in range(n_processes):
            if not finish[i] and all(need[i][j] <= work[j] for j in range(n_resources)):
                # Pi의 자원을 모두 해제
                for j in range(n_resources):
                    work[j] += allocation[i][j]
                finish[i] = True
                safe_sequence.append(i)
                found = True
                break

        if not found:
            return False, []  # 교착 상태 발생 가능

    return True, safe_sequence

3. 탐지 (Detection) + 복구 (Recovery)

데드락을 허용하되, 발생 후 탐지하고 복구합니다.

탐지 방법:
1. 자원 할당 그래프(Resource Allocation Graph) 분석
2. 사이클 감지 알고리즘 실행
3. 주기적으로 또는 성능 저하 감지 시 탐지 수행

복구 방법:
1. 프로세스 종료
   - 데드락에 관련된 프로세스 모두 종료 (가장 단순, 비용 큼)
   - 데드락 해소까지 하나씩 종료 (반복 탐지 필요)

2. 자원 강제 회수 (Preemption)
   - 데드락에 관련된 프로세스의 자원 일부를 강제 회수
   - 해당 프로세스를 이전 안전 상태로 롤백
   - 기아(Starvation) 방지 필요

4. 무시 (Ostrich Algorithm)

데드락 발생 빈도가 매우 낮은 경우, 처리 비용이 이득보다 클 때 무시합니다.

- UNIX/Linux를 포함한 대부분의 범용 OS에서 채택
- 데드락이 발생하면 사용자가 재시작
- 실용적이지만 중요 시스템에는 부적합

데이터베이스 데드락

발생 시나리오

-- 트랜잭션 A
BEGIN;
UPDATE accounts SET balance = balance - 100 WHERE id = 1; -- 행 1 락 획득
UPDATE accounts SET balance = balance + 100 WHERE id = 2; -- 행 2 락 대기

-- 트랜잭션 B (동시 실행)
BEGIN;
UPDATE accounts SET balance = balance - 50 WHERE id = 2;  -- 행 2 락 획득
UPDATE accounts SET balance = balance + 50 WHERE id = 1;  -- 행 1 락 대기

-- 결과: A는 B를 기다리고, B는 A를 기다림 → 데드락

DB 데드락 해결 방법

// 방법 1: 락 순서 고정
@Transactional
public void transfer(Long fromId, Long toId, int amount) {
    // 항상 작은 ID의 계좌를 먼저 락
    Long firstId = Math.min(fromId, toId);
    Long secondId = Math.max(fromId, toId);

    Account first = accountRepository.findByIdWithLock(firstId);   // SELECT FOR UPDATE
    Account second = accountRepository.findByIdWithLock(secondId); // SELECT FOR UPDATE

    // ... 이체 처리
}

// 방법 2: 타임아웃 + 재시도
@Retryable(
    value = { DeadlockLoserDataAccessException.class },
    maxAttempts = 3,
    backoff = @Backoff(delay = 100, multiplier = 2)
)
@Transactional
public void processOrder(Long orderId) {
    // 데드락 발생 시 최대 3번 재시도
}

// 방법 3: 낙관적 락 (버전 기반)
@Entity
public class Account {
    @Id
    private Long id;

    private int balance;

    @Version  // 버전 컬럼 추가
    private int version;
}

// 충돌 시 OptimisticLockingFailureException 발생 → 재시도 처리

Java 멀티스레드 데드락 탐지

// Java에서 데드락 탐지 방법
import java.lang.management.ManagementFactory;
import java.lang.management.ThreadMXBean;

public class DeadlockDetector {

    public static void detectDeadlock() {
        ThreadMXBean threadMXBean = ManagementFactory.getThreadMXBean();
        long[] deadlockedThreads = threadMXBean.findDeadlockedThreads();

        if (deadlockedThreads != null) {
            ThreadInfo[] threadInfos = threadMXBean.getThreadInfo(deadlockedThreads);
            System.out.println("데드락 탐지!");
            for (ThreadInfo info : threadInfos) {
                System.out.println("스레드: " + info.getThreadName());
                System.out.println("락 대기: " + info.getLockName());
                System.out.println("락 보유자: " + info.getLockOwnerName());
            }
        }
    }
}

// java.util.concurrent.locks.ReentrantLock + tryLock 타임아웃
Lock lock1 = new ReentrantLock();
Lock lock2 = new ReentrantLock();

public boolean transfer() throws InterruptedException {
    if (lock1.tryLock(1, TimeUnit.SECONDS)) {     // 1초 타임아웃
        try {
            if (lock2.tryLock(1, TimeUnit.SECONDS)) { // 1초 타임아웃
                try {
                    // 작업 수행
                    return true;
                } finally {
                    lock2.unlock();
                }
            }
        } finally {
            lock1.unlock();
        }
    }
    return false; // 타임아웃 발생 → 재시도 가능
}

요약 표

Coffman 조건설명예방 방법
상호 배제자원 독점 사용자원 공유 허용 (읽기 전용 등)
점유와 대기자원 보유 + 다른 자원 대기모든 자원 한꺼번에 요청
비선점자원 강제 회수 불가자원 반환 후 재요청
순환 대기프로세스 간 환형 대기자원 번호 순서대로 요청
해결 전략방법장점단점
예방Coffman 조건 1개 제거데드락 원천 차단자원 활용도 저하, 기아 가능
회피은행원 알고리즘자원 효율적 활용최대 자원량 사전 파악 필요
탐지+복구그래프 분석 + 강제 종료자원 활용도 높음복구 비용, 작업 손실 가능
무시데드락 방치구현 비용 없음시스템 중단 가능
이전 질문다음 질문