OS

데드락(Deadlock)이란?

둠치킨 2025. 6. 23. 23:38

데드락(Deadlock)이란?

멀티프로세스나 멀티스레드 환경에서 여러 실행 흐름이 자원을 점유한 채 서로가 가진 자원을 기다리며 영원히 진행되지 못하는 상태를 데드락(Deadlock)이라고 한다.

예를 들어, 스레드 A가 자원 X를 점유한 상태에서 자원 Y를 기다리고, 스레드 B가 자원 Y를 점유한 상태에서 자원 X를 기다리는 상황이면 두 스레드는 서로를 기다리며 영원히 멈춰버리게 된다.

데드락 예시 코드

#include <iostream>
#include <pthread.h>
#include <unistd.h>

pthread_mutex_t lock1 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t lock2 = PTHREAD_MUTEX_INITIALIZER;

void* task1(void*) {
    pthread_mutex_lock(&lock1);
    sleep(1);
    pthread_mutex_lock(&lock2);
    std::cout << "Task 1 done\n";
    pthread_mutex_unlock(&lock2);
    pthread_mutex_unlock(&lock1);
    return nullptr;
}

void* task2(void*) {
    pthread_mutex_lock(&lock2);
    sleep(1);
    pthread_mutex_lock(&lock1);
    std::cout << "Task 2 done\n";
    pthread_mutex_unlock(&lock1);
    pthread_mutex_unlock(&lock2);
    return nullptr;
}

int main() {
    pthread_t t1, t2;
    pthread_create(&t1, nullptr, task1, nullptr);
    pthread_create(&t2, nullptr, task2, nullptr);
    pthread_join(t1, nullptr);
    pthread_join(t2, nullptr);
    return 0;
}

 

이 코드는 lock1, lock2를 서로 반대 순서로 점유하면서 순환 대기가 발생하고, 결국 데드락에 빠진다.

데드락 발생 조건

데드락은 다음 네 가지 조건이 모두 만족될 때 발생한다.

  1. 상호 배제 (Mutual Exclusion)
    • 자원은 한 번에 하나의 프로세스만 사용할 수 있다.
  2. 점유 대기 (Hold and Wait)
    • 자원을 점유한 상태에서 다른 자원을 기다린다.
  3. 비선점 (No Preemption)
    • 점유한 자원을 강제로 빼앗을 수 없다.
  4. 순환 대기 (Circular Wait)
    • 여러 프로세스가 서로의 자원을 기다리며 원형 대기를 형성한다.

데드락 해결 방법

  1. 예방 (Prevention)
    • 네 가지 조건 중 하나를 성립하지 않도록 차단한다.
    • 예: 자원 요청 순서를 고정하거나, 모든 자원을 한꺼번에 요청하게 한다.
  2. 회피 (Avoidance)
    • 데드락 가능성을 미리 예측하고, 위험한 자원 요청은 거절한다.
    • 대표적 방법: 은행원 알고리즘(Banker's Algorithm)
  3. 발견 및 회복 (Detection and Recovery)
    • 데드락을 허용하되, 주기적으로 상태를 검사하여 감지하고 복구한다.
    • 복구 방법: 프로세스 종료, 자원 회수 등
  4. 무시 (Ignore)
    • 데드락 가능성이 낮다고 판단하고 아무 대응도 하지 않는다.
    • 현실적으로 대부분의 운영체제가 사용하는 전략이다.

운영체제에서의 데드락 회피 및 방지 전략

운영체제는 다음과 같은 방식으로 데드락을 방지하거나 회피한다.

  1. 자원 요청 순서 고정
    • 모든 자원에 우선순위를 부여하고 항상 낮은 순서부터 요청하게 한다.
    • 순환 대기를 방지할 수 있다. 커널 락, 파일 시스템 락 등에서 흔히 사용된다.
  2. 타임아웃 기반 락
    • 일정 시간 이상 자원을 얻지 못하면 요청을 포기하거나 재시도하게 한다.
    • pthread에서는 pthread_mutex_timedlock 등이 있다.
  3. 우선순위 상속 (Priority Inheritance)
    • 우선순위가 높은 프로세스가 낮은 프로세스가 점유한 자원을 기다릴 경우,
    • 낮은 프로세스의 우선순위를 임시로 높여 빠르게 실행되게 한다.
      실시간 시스템에서 사용된다.
  4. 은행원 알고리즘
    • 데드락 회피 알고리즘으로, 자원 요청을 수락하기 전에 시스템이 안전한 상태인지 판단한다.
    • 실제 범용 운영체제에서는 잘 사용되지 않지만 이론적으로는 중요한 알고리즘이다.
저작자표시 (새창열림)