[운영체제] 교착상태(Deadlock, 데드락)

데드락이란?

두 개 이상의 프로세스나 스레드가 서로 자원을 얻지 못해서 다음 처리를 하지 못하는 상태입니다.
쉽게 말해, 무한히 자원을 기다리는 상태로, 한정된 자원을 여러 프로세스가 사용하려고 할 때 발생합니다.

예를 들어, 외나무 다리 양 끝에서 서로가 비켜주기를 기다리는 상황을 떠올리면 이해하기 쉽습니다.

 

데드락 발생 예시

상황:

• 프로세스1은 자원1과 자원2가 필요합니다.
• 프로세스2도 자원1과 자원2가 필요합니다.

시간별 진행:

• t1: 프로세스1이 자원1을, 프로세스2가 자원2를 점유합니다.
• t2: 프로세스1은 자원2를 기다리고, 프로세스2는 자원1을 기다립니다.

서로 상대방이 점유한 자원을 기다리며 무한정 대기 상태에 빠지는 상황이 발생합니다.
→ 이것이 바로 Deadlock(교착 상태)입니다.

---

데드락 발생 조건

데드락이 발생하려면 아래의 4가지 조건이 모두 성립해야 합니다.
하나라도 성립하지 않으면 데드락을 예방할 수 있습니다.

1️⃣ 상호 배제(Mutual Exclusion)

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

2️⃣ 점유 대기(Hold and Wait)

• 최소한 하나의 자원을 점유한 상태에서 다른 자원을 기다리는 프로세스가 존재해야 합니다.

3️⃣ 비선점(No Preemption)

• 다른 프로세스가 점유 중인 자원은 강제로 빼앗을 수 없습니다.

4️⃣ 순환 대기(Circular Wait)

• 자원을 기다리는 프로세스 간에 순환 형태의 대기가 있어야 합니다.

---

데드락 처리 방법

1. 교착 상태 예방 (Prevention)

• 데드락 발생 조건 중 하나를 제거하여 해결합니다.
  단점: 자원 낭비가 많아 비효율적일 수 있습니다.

조건예방 방법

상호 배제	여러 프로세스가 공유 자원을 사용하게 허용
점유 대기	프로세스 실행 전에 필요한 모든 자원을 할당
비선점	자원 요구 시 이미 점유한 자원을 반납하도록 설정
순환 대기	자원에 고유 번호를 부여해 순서대로 요구

 

다음은 순환 대기를 제거한 예시입니다.

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

pthread_mutex_t resource1 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t resource2 = PTHREAD_MUTEX_INITIALIZER;

void* thread1_func(void* arg) {
    pthread_mutex_lock(&resource1); // 자원 1 점유
    printf("Thread 1: 자원 1 점유\n");

    pthread_mutex_lock(&resource2); // 자원 2 요청
    printf("Thread 1: 자원 2 점유\n");

    pthread_mutex_unlock(&resource2);
    pthread_mutex_unlock(&resource1);

    return NULL;
}

void* thread2_func(void* arg) {
    pthread_mutex_lock(&resource1); // 자원 1 요청
    printf("Thread 2: 자원 1 점유\n");

    pthread_mutex_lock(&resource2); // 자원 2 요청
    printf("Thread 2: 자원 2 점유\n");

    pthread_mutex_unlock(&resource2);
    pthread_mutex_unlock(&resource1);

    return NULL;
}

int main() {
    pthread_t thread1, thread2;

    pthread_create(&thread1, NULL, thread1_func, NULL);
    pthread_create(&thread2, NULL, thread2_func, NULL);

    pthread_join(thread1, NULL);
    pthread_join(thread2, NULL);

    return 0;
}

순환 대기를 제거하기 위해 자원에 고유 번호를 부여하고, 프로세스가 항상 고유번호가 작은 자원부터 요청하도록 설정하였습니다. 이를 통해 순환 대기 조건이 성립하지 않아 데드락을 예방할 수 있습니다.

 

2. 교착 상태 회피 (Avoidance)

• 교착 상태가 발생할 가능성을 사전에 회피하는 방법.
• 은행원 알고리즘 (Banker's Algorithm)
  고객의 요구가 충족되도록 자원을 할당하면서 시스템이 안정 상태를 유지하는지 확인.
  안정 상태인 경우 자원을 할당, 그렇지 않으면 대기.
• 자원 할당 그래프 알고리즘 (Resource-Allocation Graph Algorithm)
  요청 간선과 할당 간선을 통해 사이클 유무를 검사하여 교착 상태를 방지.
  • 사이클 O: 교착 상태 발생 가능성.
  • 사이클 X: 교착 상태 미발생

 

다음은 은행원 알고리즘의 간단히 구현한 코드입니다.

#include <stdio.h>
#include <stdbool.h>

#define NUM_PROCESSES 3
#define NUM_RESOURCES 3

int available[NUM_RESOURCES] = {3, 3, 2}; // 현재 사용 가능한 자원 수
int max[NUM_PROCESSES][NUM_RESOURCES] = { // 프로세스별 최대 요구 자원
    {7, 5, 3},
    {3, 2, 2},
    {9, 0, 2}
};
int allocation[NUM_PROCESSES][NUM_RESOURCES] = { // 현재 할당된 자원
    {0, 1, 0},
    {2, 0, 0},
    {3, 0, 2}
};
int need[NUM_PROCESSES][NUM_RESOURCES]; // 남은 필요 자원 계산

void calculateNeed() {
    for (int i = 0; i < NUM_PROCESSES; i++) {
        for (int j = 0; j < NUM_RESOURCES; j++) {
            need[i][j] = max[i][j] - allocation[i][j];
        }
    }
}

bool isSafe() {
    int work[NUM_RESOURCES];
    bool finish[NUM_PROCESSES] = {false};
    for (int i = 0; i < NUM_RESOURCES; i++) {
        work[i] = available[i];
    }

    while (true) {
        bool found = false;
        for (int i = 0; i < NUM_PROCESSES; i++) {
            if (!finish[i]) {
                bool canProceed = true;
                for (int j = 0; j < NUM_RESOURCES; j++) {
                    if (need[i][j] > work[j]) {
                        canProceed = false;
                        break;
                    }
                }
                if (canProceed) {
                    for (int j = 0; j < NUM_RESOURCES; j++) {
                        work[j] += allocation[i][j];
                    }
                    finish[i] = true;
                    found = true;
                }
            }
        }
        if (!found) break;
    }

    for (int i = 0; i < NUM_PROCESSES; i++) {
        if (!finish[i]) return false;
    }
    return true;
}

int main() {
    calculateNeed();

    if (isSafe()) {
        printf("시스템은 안전 상태입니다.\n");
    } else {
        printf("시스템은 교착 상태 위험이 있습니다.\n");
    }

    return 0;
}

isSafe()함수에 while문이 은행원 알고리즘 입니다. 아직 진행중인 프로세스가 필요로 하는 모든 자원을 가질 수 있을지 확인 후 가질 수 있다면 작업 후, 자원을 반납합니다. 이러한 방식으로 시스템이 안정 상태인지 검사하며 자원을 할당할지 결정하는 것으로 데드락을 회피하는 것입니다.

 

 

3. 교착 상태 탐지 및 회복 (Detection & Recovery)

• 교착 상태를 허용한 후 탐지하고 복구합니다.
• 탐지
  자원 할당 그래프를 사용해 교착 상태를 탐지.
  탐지 알고리즘 실행 시 오버헤드 발생 가능.
• 회복
  • 프로세스 종료
    1. 교착 상태에 포함된 프로세스를 모두 종료.
    2. 하나씩 종료해 교착 상태 해제.
  • 자원 선점
    점유 자원을 해제해 다른 프로세스에게 할당.
    우선순위가 낮거나 수행 횟수가 적은 프로세스의 자원을 선점.

---

정리

• 데드락은 한정된 자원을 사용하는 프로세스들 간의 충돌로 발생합니다.
• 발생 조건 중 하나만 제거해도 예방이 가능하지만, 자원 낭비가 클 수 있습니다.
• 효율적인 예방과 회복 방법을 선택하여 시스템 자원을 관리하는 것이 중요합니다.