[운영체제] 08. 교착 상태: 예방, 회피, 탐지, 복구

[교착 상태의 일상적 비유]

좁은 다리에서 양쪽에서 온 차가 마주침:
  <--- 차 A      차 B --->
        [다리]
둘 다 상대방이 물러나기를 기다림 -> 교착 상태

시스템에서의 예:
스레드 1: lock(A) -> lock(B) 시도 (대기)
스레드 2: lock(B) -> lock(A) 시도 (대기)

// 교착 상태를 유발하는 코드 예시
#include <pthread.h>

pthread_mutex_t mutex_a = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t mutex_b = PTHREAD_MUTEX_INITIALIZER;

void *thread1(void *arg) {
    pthread_mutex_lock(&mutex_a);    // A 획득
    sleep(1);                         // 타이밍 문제 유발
    pthread_mutex_lock(&mutex_b);    // B 대기 (교착!)
    // ...
    pthread_mutex_unlock(&mutex_b);
    pthread_mutex_unlock(&mutex_a);
    return NULL;
}

void *thread2(void *arg) {
    pthread_mutex_lock(&mutex_b);    // B 획득
    sleep(1);                         // 타이밍 문제 유발
    pthread_mutex_lock(&mutex_a);    // A 대기 (교착!)
    // ...
    pthread_mutex_unlock(&mutex_a);
    pthread_mutex_unlock(&mutex_b);
    return NULL;
}

[자원 할당 그래프 요소]

프로세스: 원 (O)
자원 유형: 사각형 안의 점 (인스턴스)
요청 간선: Pi -> Rj  (프로세스가 자원을 요청)
할당 간선: Rj -> Pi  (자원이 프로세스에 할당됨)

[교착 상태가 있는 자원 할당 그래프]

    P1 --요청--> R1 (1개) --할당--> P2
    ^                               |
    |                               |
  할당                            요청
    |                               |
    R2 (1개) <--요청-- P3 <--할당-- R3 (1개)

P1은 R1을 요청 (P2가 보유)
P2는 R3를 요청 (P3가 보유)
P3는 R2를 요청 (P1이 보유)
-> 순환 존재 -> 교착 상태!

[교착 상태가 없는 자원 할당 그래프 - 자원 인스턴스가 여러 개]

    P1 --요청--> R1 (2개)  인스턴스1 --할당--> P2
                           인스턴스2 --할당--> P3

P2나 P3 중 하나가 R1을 반납하면 P1이 진행 가능
-> 순환이 있어도 교착 상태가 아닐 수 있음
   (자원 인스턴스가 2개 이상일 때)

방법 A: 실행 전 필요한 모든 자원을 한꺼번에 요청
  장점: 단순
  단점: 자원 이용률 저하, 기아 가능

방법 B: 새 자원 요청 시 보유 자원을 모두 반납 후 재요청
  장점: 유연
  단점: 구현 복잡

프로세스 P가 자원 A를 보유하고 B를 요청:
  B를 사용할 수 없으면:
    A를 강제로 해제 (선점)
    P를 A와 B 모두 기다리는 상태로 전환
    A와 B 모두 사용 가능해지면 재시작

// 순환 대기 예방: 자원 순서 규약
// 자원 번호: mutex_a = 1, mutex_b = 2, mutex_c = 3

// 올바른 사용: 항상 낮은 번호부터 획득
void safe_function() {
    pthread_mutex_lock(&mutex_a);    // 번호 1
    pthread_mutex_lock(&mutex_b);    // 번호 2
    pthread_mutex_lock(&mutex_c);    // 번호 3

    // 임계 영역

    pthread_mutex_unlock(&mutex_c);
    pthread_mutex_unlock(&mutex_b);
    pthread_mutex_unlock(&mutex_a);
}

// 잘못된 사용: 번호 역순으로 요청하면 교착 위험
void unsafe_function() {
    pthread_mutex_lock(&mutex_c);    // 번호 3
    pthread_mutex_lock(&mutex_a);    // 번호 1 (순서 위반!)
}

[안전 상태와 교착 상태의 관계]

+-------------------------------------------+
|              전체 상태                      |
|  +----------------------------------+     |
|  |          안전 상태                 |     |
|  |                                  |     |
|  |                                  |     |
|  +----------------------------------+     |
|            불안전 상태                     |
|       (교착 가능 영역 포함)                |
|                 +------+                  |
|                 |교착   |                  |
|                 |상태   |                  |
|                 +------+                  |
+-------------------------------------------+

안전 상태 -> 교착 상태 없음 (보장)
불안전 상태 -> 교착 상태 가능 (반드시는 아님)

Available[m]:  각 자원 유형의 가용 인스턴스 수
Max[n][m]:     각 프로세스의 최대 요구량
Allocation[n][m]: 현재 각 프로세스에 할당된 양
Need[n][m]:    각 프로세스의 잔여 필요량 (Max - Allocation)

[안전성 검사 알고리즘]

1. Work = Available 복사
   Finish[i] = false (모든 i에 대해)

2. 다음 조건을 만족하는 i를 찾음:
   Finish[i] == false AND Need[i] <= Work

3. 찾으면:
   Work = Work + Allocation[i]
   Finish[i] = true
   2단계로 돌아감

4. 못 찾으면:
   모든 Finish[i]가 true이면 -> 안전 상태
   아니면 -> 불안전 상태

[은행원 알고리즘 예제]

자원: A(10), B(5), C(7)

        Allocation    Max        Need       Available
        A  B  C      A  B  C    A  B  C    A  B  C
P0      0  1  0      7  5  3    7  4  3    3  3  2
P1      2  0  0      3  2  2    1  2  2
P2      3  0  2      9  0  2    6  0  0
P3      2  1  1      2  2  2    0  1  1
P4      0  0  2      4  3  3    4  3  1

안전 순서 찾기:
1. Work = [3,3,2]
   P1의 Need[1,2,2] <= [3,3,2]? 예!
   Work = [3,3,2] + [2,0,0] = [5,3,2], Finish[P1] = true

2. Work = [5,3,2]
   P3의 Need[0,1,1] <= [5,3,2]? 예!
   Work = [5,3,2] + [2,1,1] = [7,4,3], Finish[P3] = true

3. Work = [7,4,3]
   P4의 Need[4,3,1] <= [7,4,3]? 예!
   Work = [7,4,3] + [0,0,2] = [7,4,5], Finish[P4] = true

4. Work = [7,4,5]
   P2의 Need[6,0,0] <= [7,4,5]? 예!
   Work = [7,4,5] + [3,0,2] = [10,4,7], Finish[P2] = true

5. Work = [10,4,7]
   P0의 Need[7,4,3] <= [10,4,7]? 예!
   Finish[P0] = true

안전 순서: P1 -> P3 -> P4 -> P2 -> P0
현재 시스템은 안전 상태!

[P1이 자원 (1,0,2)를 추가 요청한 경우]

1. Request[1] = [1,0,2] <= Need[1] = [1,2,2]? 예 (유효한 요청)
2. Request[1] = [1,0,2] <= Available = [3,3,2]? 예 (자원 있음)
3. 가정적으로 할당:
   Available = [3,3,2] - [1,0,2] = [2,3,0]
   Allocation[1] = [2,0,0] + [1,0,2] = [3,0,2]
   Need[1] = [1,2,2] - [1,0,2] = [0,2,0]

4. 안전성 검사 실행:
   새로운 Available = [2,3,0]으로 안전 순서 존재 확인
   -> 안전하면 요청 허용, 아니면 거부

// 은행원 알고리즘 Java 구현
public class BankersAlgorithm {
    private int[][] max;
    private int[][] allocation;
    private int[][] need;
    private int[] available;
    private int numProcesses;
    private int numResources;

    public BankersAlgorithm(int[][] max, int[][] alloc,
                             int[] avail) {
        this.max = max;
        this.allocation = alloc;
        this.available = avail;
        this.numProcesses = max.length;
        this.numResources = avail.length;
        this.need = new int[numProcesses][numResources];

        for (int i = 0; i < numProcesses; i++)
            for (int j = 0; j < numResources; j++)
                need[i][j] = max[i][j] - allocation[i][j];
    }

    public boolean isSafe() {
        int[] work = available.clone();
        boolean[] finish = new boolean[numProcesses];
        int count = 0;

        while (count < numProcesses) {
            boolean found = false;
            for (int i = 0; i < numProcesses; i++) {
                if (!finish[i] && canAllocate(need[i], work)) {
                    // 자원 회수
                    for (int j = 0; j < numResources; j++)
                        work[j] += allocation[i][j];
                    finish[i] = true;
                    count++;
                    found = true;
                    System.out.println("P" + i + " 실행 가능");
                }
            }
            if (!found) return false;
        }
        return true;
    }

    private boolean canAllocate(int[] need, int[] work) {
        for (int j = 0; j < numResources; j++)
            if (need[j] > work[j]) return false;
        return true;
    }
}

[대기 그래프]

자원 할당 그래프에서 자원 노드를 제거하고
프로세스 간 직접 의존 관계만 표시

P1 --> P2 --> P3
 ^            |
 |            v
 +---- P4 <--+

순환 존재: P1->P2->P3->P4->P1 -> 교착 상태!

[교착 상태 탐지 알고리즘]

1. Work = Available
   Allocation[i] != 0이면 Finish[i] = false
   Allocation[i] == 0이면 Finish[i] = true

2. Finish[i] == false AND Request[i] <= Work인 i를 찾음

3. 찾으면: Work = Work + Allocation[i]
           Finish[i] = true
           2단계로 돌아감

4. Finish[i] == false인 프로세스가 있으면
   -> 해당 프로세스들이 교착 상태

[자원 선점 시 고려 사항]

1. 희생자 선택: 어떤 프로세스에서 자원을 빼앗을 것인가?
   비용 최소화 기준으로 선택

2. 롤백: 자원을 빼앗긴 프로세스를 안전한 상태로 되돌림
   - 완전 롤백: 처음부터 다시 시작
   - 부분 롤백: 교착을 벗어나기에 충분한 시점까지만 롤백

3. 기아 방지: 같은 프로세스가 항상 희생자로 선택되지 않도록
   롤백 횟수를 비용 요소에 포함

// trylock을 사용한 교착 방지
int try_acquire_both(pthread_mutex_t *a, pthread_mutex_t *b) {
    while (1) {
        pthread_mutex_lock(a);

        if (pthread_mutex_trylock(b) == 0) {
            return 0;  // 성공: 두 잠금 모두 획득
        }

        // b를 얻지 못하면 a도 해제하고 재시도
        pthread_mutex_unlock(a);
        usleep(rand() % 1000);  // 잠시 대기 후 재시도
    }
}

// Java의 tryLock을 사용한 교착 방지
import java.util.concurrent.locks.ReentrantLock;
import java.util.concurrent.TimeUnit;

public class DeadlockFree {
    private final ReentrantLock lockA = new ReentrantLock();
    private final ReentrantLock lockB = new ReentrantLock();

    public void safeMethod() throws InterruptedException {
        while (true) {
            boolean gotA = lockA.tryLock(100, TimeUnit.MILLISECONDS);
            boolean gotB = lockB.tryLock(100, TimeUnit.MILLISECONDS);

            if (gotA && gotB) {
                try {
                    // 두 잠금 모두 획득 - 안전하게 작업
                    System.out.println("두 자원 모두 획득!");
                    break;
                } finally {
                    lockA.unlock();
                    lockB.unlock();
                }
            }

            // 하나라도 실패하면 보유한 잠금 해제
            if (gotA) lockA.unlock();
            if (gotB) lockB.unlock();

            // 랜덤 대기 후 재시도 (라이브락 방지)
            Thread.sleep((long)(Math.random() * 100));
        }
    }
}