교착상태

앵우·2026년 1월 10일

교착상태(Deadlock)은 서로 자원을 요구하기만 하고 처리하지를 못하는 상태이다. 이에 대한 해결방법으로 예방, 회피, 감지 및 복구, 무시가 있다.

교착상태

: 자원을 소유한 쓰레드(프로세스)들 사이에서, 각 쓰레드는 다른 쓰레드가 소유한 자원을 요청하여 무한정 대기하고 있는 현상
-> 다중 프로그래밍 시스템 초기에 노출된 문제점이다.

다음 그림처럼 각 쓰레드가 다른 쓰레드가 소유하고 있는 자원을 요청하면서 환형 요청/대기(circular wait)을 이루게 되었다. 환형 고리는 스스로 인식이나 해제가 불가하다.

다음은 교착상태를 확인해볼 수 있는 코드이다. 두 쓰레드가 각각 락을 획득한 이후에 상대의 락을 기다리는 상황이다. 서로가 서로의 락을 기다리며 무한 대기하게 된다.

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <unistd.h>

int x = 0; // shared
int y = 0; // shared
pthread_mutex_t lock1; // mutex lock
pthread_mutex_t lock2; // mutex lock

void* thread1(void* arg) {
    pthread_mutex_lock(&lock1); // lock1 for x
    printf("lock thread1 lock1 \n");
    x++;
    sleep(2);

    pthread_mutex_lock(&lock2);
    printf("unlock thread1 lock2\n");
    y++;
    pthread_mutex_unlock(&lock2); // unlock lock2
    printf("unlock thread1 lock2 \n");

    pthread_mutex_unlock(&lock1); // unlock lock1
    printf("unlock thread1 lock1\n");
}

void* thread2(void* arg) {
    pthread_mutex_lock(&lock2); // lock2 for y 
    printf("lock thread2 lock2\n");
    y++;
    sleep(2);

    pthread_mutex_lock(&lock1); // lock1 for x
    printf("lock thread2 lock1\n");
    x++;
    pthread_mutex_unlock(&lock1); // unlock lock1
    printf("unlock thread2 lock1 \n");

    pthread_mutex_unlock(&lock2); // unlock lock2
    printf("unlock thread2 lock2 \n");
}

int main() {
    pthread_t tid[2];

    pthread_mutex_init(&lock1, NULL);
    pthread_mutex_init(&lock2, NULL);

    pthread_create(&tid[0], NULL, thread1, NULL);
    pthread_create(&tid[1], NULL, thread2, NULL);

    pthread_join(tid[0], NULL);
    pthread_join(tid[1], NULL);

    pthread_mutex_destroy(&lock2);
    pthread_mutex_destroy(&lock1);

    printf("x = %d, y = %d \n", x, y);

    return 0;
}

기아 vs 교착

Starvation - 운영체제가 잘못된 정책을 사용하여 특정 프로세스의 작업이 지연되는 문제
Deadlock - 여러 프로세스가 작업을 진행하다 보니 자연적으로 일어나는 문제

교착상태의 잠재적 요인들

자원

교착상태의 발생지
교착상태는 멀티쓰레드가 자원을 동시에 사용하려는 충돌이 요인
컴퓨터 시스템에는 많은 자원 존재
- 소프트웨어 자원: 뮤텍스, 스핀락, 세마포어, 파일, 데이터베이스
- 하드웨어 자원: 프린터, 메모리, 프로세서 등

자원과 쓰레드

한 쓰레드가 여러 자원을 동시에 필요로 하는 상황이 요인

자원과 운영체제

한 번에 하나씩 자원을 할당하는 운영체제 정책이 요인
만일 쓰레드가 필요한 자원을 한 번에 모두 요청하도록 한다면? -> 교착상태가 발생하지 않게 할 수 있다.

자원 비선점

할당된 자원은 쓰레드가 자발적으로 내놓기 전에 강제로 뺐지 못하는 정책이 요인
운영체제는 쓰레드가 가진 자원을 강제로 뺐지 못함
만일 강제로 뺐을 수 있다면? -> 교착상태가 발생하지 않게 할 수 있다.

교착상태는 공유변수와 관련하여 코딩을 잘못한다면, 커널에서도 정말 가끔 발생한다. 하지만 교착상태를 시스템에서 직접적으로 막지는 않는다. (막는데 많은 시간과 공간의 비용이 들기 때문) 교착상태가 발생하도록 두고, 교착상태가 발생한 것 같으면, 시스템 재시작 혹은 의심스러운 몇몇 프로그램을 종료시킨다.

교착상태 모델링: 자원 할당 그래프(Resource Allocation Graph, RAG)

: 자원에 대한 시스템의 상태를 나타내는 방향성 그래프

컴퓨터 시스템에 실행 중인 전체 쓰레드와 자원의 개수
각 자원의 총 인스턴스 개수와 할당 가능한 인스턴스 개수
각 쓰레드가 할당받아 소유하고 있는 자원의 인스턴스 개수
각 쓰레드가 실행에 필요한 자원 유형과 인스턴스 개수

이러한 요소를 자원할당그래프로부터 확인하고 교착상태를 판단할 수 있다.

그래프는 정점과 간선으로 이루어져 있다.

정점은 프로세스/쓰레드(원), 자원(사각형)을 나타낸다.
간선은 소유/요청 관계를 표시하는데, 할당 간선과 요청 간선이 있다.
- 할당 간선: 자원에서 쓰레드로 향하는 화살표, 할당 받은 상태 표시
- 요청 간선: 쓰레드에서 자원으로 향하는 화살표, 요청 표시

교착상태 해결

교착상태의 발생 필요충분조건

Coffman condition

다음 4가지 상황이 허용되는 시스템은 언제든 교착상태가 발생할 수 있다.

자원적 특성

상호 배제(Mutual Exclusion) - 각 자원은 한 번에 하나의 프로세스/쓰레드에게만 할당(자원이 한 쓰레드에게 할당되면 다른 쓰레드에게는 할당될 수 없음)
비선점(No Preemption) - 프로세스/쓰레드에게 할당된 자원을 강제로 빼앗지 못함

행위적 특성

점유와 대기(Hold & wait) - 쓰레드가 한 자원을 소유(lock)하면서 다른 자원을 기다리기
환형 대기(Circular wait) - 한 그룹의 쓰레드들에 대해, 각 쓰레드는 다른 쓰레드가 요청하는 자원을 소유하는 원형 고리 형성

교착상태 해결

1. 교착상태 예방(prevention)

교착상태 발생 여지를 차단하여 예방
교창상태에 빠지는 4가지 조건(상호 배제, 비선점, 점유와 대기, 환형 대기) 중 하나 이상의 조건이 성립되지 못하도록 시스템 구성

2. 교착상태 회피(avoidance)

미래에 교착상태로 가지 않도록 회피
자원 할당 시마다 미래의 교착 상태 가능성을 검사하여 교착 상태가 발생하지 않을 것이라고 확신하는 경우에만 자원 할당
안전한 상태와 불안전한 상태로 시스템 상태 분류, 안전한 상태인 경우에만 자원 할당
자원 할당 시마다 교착 상태 가능성을 검사하므로 시스템 성능 저하

3. 교착상태 감지 및 복구(detection and recovery)

교착상태를 감지하는 프로그램 구동, 발견 후 교착상태 해제
백그라운드에서 교착 상태를 감지하는 프로세스가 늘 실행되어야 하는 부담

4. 교착상태 무시

아무런 대비책 없음, 교착상태는 없다고 단정
사용자가 이상을 느끼면 재실행할 것이라고 믿는 방법
리눅스, 윈도우 등 현재 대부분의 운영체제에서 사용하는 가장 일반적인 방법
교착상태 예방, 회피, 감지 복구 등에는 많은 시간과 공간이 필요하며 시스템의 성능을 떨어뜨린다.
심각하지 않은 작업들에 대해서는 교착상태 무시

교착상태 예방

코프만의 4가지 조건 중 최소 하나를 성립하지 못하게 한다.

1. 상호 배재 조건 -> 상호 배제 없애기

동시에 2개 이상의 쓰레드가 자원을 활용할 수 있도록 한다.
컴퓨터 시스템에서 근본적으로 적용 불가능한 방법

2. 비선점 조건 -> 선점 허용

모든 자원을 빼앗을 수 있도록 만드는 방법
기아현상이 발생할 수도 있음
자원을 강제로 반환하게 된 쓰레드가 자원을 다시 사용하게 될 때 이전 상태로 되돌아갈 수 있도록 상태를 관리할 필요
간단하지 않고 오버헤드가 매우 크가.

=> 자원적 특성을 제한하기는 어렵다.

3. 점유와 대기 조건 -> 기다리지 않게 한다.

(방법1) 운영체제는 쓰레드 실행 전 필요한 모든 자원을 파악하고 실행시 한 번에 할당

다른 쓰레드는 필요한 자원을 할당 받지 못하고 실행 대기

(방법2) 쓰레드가 새로운 자원을 요청하려면, 현재 할당 받은 모든 자원을 반환하고, 한꺼번에 요청하여 할당
문제점

프로세스가 자신이 사용하는 모든 자원을 자세히 알기 어려움
당장 사용하지 않는 자원을 쓰레드에게 묶어 두기 때문에 자원 활용률이 떨어짐
많은 자원을 사용하는 프로세스가 적은 자원을 사용하는 프로세스보다 불리함
-> 결국 Batch-processing(일괄 처리)화된다.

4. 환형 대기(Circular Wait) 조건 -> 환형 대기 제거

모든 자원에 숫자를 부여하고 숫자가 큰 방향으로만 자원을 할당한다.

예: 마우스를 할당받은 상태에서 프린터를 할당받을 수는 있지만 프린터를 할당받은 상태에서 마우스나 하드디스크를 할당받을 수 없다.

예: 프로세스 P2는 자원을 할당받을 수 없어 강제 종료되고 프로세스 P1은 정상적으로 실행된다.

문제점

프로세스 작업 진행에 유연성이 떨어짐
자원의 번호를 어떻게 부여할 것인지가 문제

=> 점유와 대기, 원형 대기는 프로세스 작업 방식을 제한하고 자원을 낭비하기 때문에 사용이 어렵다.

교착상태 회피

자원 할당 시, 미레에 환형 대기가 발생할 것으로 판단되면 자원 할당하지 않는 정책
프로세스에 자원을 할당할 때 어느 수준 이상의 자원을 나누어주면 교착 상태가 발생하는지 파악하여 그 수준 이하로 자원을 나누어주는 방법
교착 상태가 발생하지 않는 범위 내에서만 자원을 할당하고, 교착 상태가 발생하는 범위에 있ㅇ면 프로세스를 대기시킨다.
=> 할당되는 자원의 수를 조절하여 교착 상태를 피한다.

안전한 상태 Safe state - 현재 프로세스들을 어떤 순서로 실행시켰을 때, 모든 프로세스들이 자신이 요청하는 자원을 가지고 실행할 수 있다면 안전한 상태

불안전한 상태 Unsafe state - 환형 대기에 빠질 수 있는 상태

-> 할당된 자원이 적으면 안정 상태가 크고, 할당된 자원이 늘어날수록 불안정 상태가 커짐

bankers's 알고리즘

자원 할당 전에 미래에 교착상태 발생여부를 판단한다.

알고리즘

각 프로세스가 실행 시작 전에 필요한 전체 자원의 수를 운영체제에게 알린다.
자원을 할당할 때마다, 자원을 할당해주었을 때 교착상태가 발생하지 않을 만큼 안전한 상태인지 판단하여 안전한 상태일 때만 자원을 할당한다.

고려 요소

각 프로세스가 필요한 자원의 개수
현재 각 프로세스가 할당 받은 자원의 개수
시스템 내 할당 가능한 자원의 개수

하지만 이런 알고리즘은 비현실적이다.

각 프로세스가 실행 전에 필요한 자원의 개수를 아는 것은 불가능하고
프로세스의 개수도 동적으로 변하기 때문에, 미리 프로세스의 개수를 정적으로 고정시키는 것은 불가능하다.

교착상태 감지 및 복구

교착상태를 감지하는 프로그램을 통해, 형성된 교착상태를 푼다. 백그라운드에서 교착상태를 감지하는 프로그램을 늘 실행한다.

감지 방법

자원 할당 그래프를 이용한 교착 상태 검출
- 단일 자원을 사용하는 경우 자원 할당 그래프에 사이클이 있으면 교착 상태
타임아웃을 이용한 교착 상태 검출
- 일정 시간 동안 작업이 진행되지 않은 프로세스를 교착 상태가 발생한 것으로 간주하여 처리
- 교착 상태가 자주 발생하지 않을 것이라는 가정하에 사용(타조 알고리즘)
- 타임아웃이 되면 프로세스가 종료

복구 방법

자원 강제 선점(preemption)
- 교착상태에 빠진 쓰레드 중 하나의 자원을 강제로 빼앗아 다른 쓰레드에게 할당
롤백(rollback)
- 운영체제는 주기적으로 교착상태가 발생할 것으로 예측되는 쓰레드의 상태를 저장하여 두고 교착상태가 발생하면 마지막으로 저장된 상태로 돌아가도록 하고, 다시 시작하면서 자원을 다르게 할당
- 시간과 메모리 공간에 대한 부담이 크기 때문에 잘 사용하지 않음
프로세스/쓰레드 강제 종료(kill process)
- 교착상테에 빠지 쓰레드 중 하나 강제 종료, 가장 간단하면서도 효과적인 방법
프로세스를 강제로 종료하는 방법
1. 교착 상태를 일으킨 모든 프로세스를 동시에 종료
2. 교착 상태를 일으킨 프로세스 중 하나를 골라 순서대로 종료
  - 우선순위가 낮은 프로세스를 먼저 종료
  - 우선순위가 같은 경우 작업 시간이 짧은 프로세스를 먼저 종료
- 위의 두 조건이 같은 경우 자원을 많이 사용하는 프로세스를 먼저 종료

교착상태 무시

교착상태는 반드시 발생하지만 자주 발생하지는 않는다. 하지만 발생횟수/확률에 비해 해결에는 상대적으로 많은 비용이 든다.

Ostrich algorithm

타조 알고리즘

타조가 머리를 모래 속에 박고 자신이 보이지 않는 체하는 것
교착상태는 발생하지 않을거야 하고 아무 대책을 취하지 않는 접근법(무시)
Unix와 윈도우 등 현재 거의 모든 운영체제에서 사용
의심 가는 쓰레드를 종료시키거나 시스템 재시작(reboot)

(문제)
교착상태가 발생하면 시스템 재시작 혹은 특정 프로세스/쓰레드를 강제 종료하면서 관련된 데이터를 잃어버릴 수 있다. (하지만 전체적으로 크지 않은 손실)

예: 데이터베이스

데이터베이스에서 타임아웃으로 프로세스가 종료되면 일부 데이터의 일관성이 깨질 수 있다.
데이터의 일관성이 깨지는 문제를 해결하기 위해 체크포인트와 롤백 사용
- 체크포인트: 작업을 하다가 문제가 발생하면 저장된 상태로 돌아오기 위한 표시
- 롤백: 작업을 하다가 문제가 발생하여 과거의 체크포인트로 되돌아가는 것