[운영체제] 3-3. (2) 동기화와 교착 상태

교착 상태 (Deadlock)

 

💡교착 상태 (Deadlock) 이란?

 

 프로세스를 실행하기 위해서는 자원이 필요하다. 하지만 2개 이상의 프로세스가 각자 가지고 있는 자원을 무작정 기다린다면 더 이상 어떤 프로세스도 진행할 수 없는 교착 상태가 발생할 수 있다. 이렇듯 교착 상태(Deadock)란, 일어나지 않을 사건을 기다리며 프로세스의 진행이 멈춰 버리는 현상이다.

 예를 들어, 아래 그림과 같은 현상이 발생하는 것이다.

교착 상태 (Deadlcok)

• 프로세스 A는 자원 X를 점유한 상태에서 자원 Y를 요청하고,
• 프로세스 B는 자원 Y를 점유한 상태에서 자원 X를 요청하는 경우 → 서로 대기 → 교착 발생

결국 두 프로세스는 서로가 가진 자원을 기다리다가 프로세스를 실행하지 못하는 교착 상태가 발생하게 된다.

---

교착 상태의 발생 조건

 

 교착 상태가 발생하는 상황에는 4가지 필요 조건이 있다. 바로 상호 배제, 점유와 대기, 비선점, 원형 대기이다. 이 중 하나라도 만족하지 않는다면 교착 상태는 발생하지 않고, 4개의 조건이 모두 만족할 때 교착 상태가 발생할 가능성이 생긴다.

 

💡상호 배제 (Exclusive use of resources)

• 한 번에 하나의 프로세스만 해당 자원을 사용할 수 있는 상황으로, 이로 인해 교착 상태가 발생할 수 있다.
• 예를 들어, 한 프린터를 두 개의 프로세스가 동시에 출력하지 못하는 상황이다.

 

💡점유와 대기 (Hold and wait, Partial allocation)

• 자원을 하나 이상 점유하고 있으면서, 추가로 다른 자원을 요청하며 대기하는 상태이다.
• 예를 들어, 프로세스 A가 프린터를 점유한 채, 스캐너가 필요해 스캐너 할당을 기다리는 상황이다.

 

💡비선점 (Non-premptible resource)

• 자원이 비선점되었다는 말은 해당 자원을 이용하는 프로세스의 작업이 끝나야만 비로소 자원을 이용할 수 있다는 것을 의미한다.
• 즉, 자원은 해당 프로세스가 자발적으로 반납해야만 반환되기 때문에 어떤 프로세스도 다른 프로세스의 자원을 강제로 빼앗지 못하는 경우 교착 상태가 발생할 수 있다.
• 예를 들어,
  • A : 프린터를 사용 중 + 스캐너 필요해서 대기
  • B : 스캐너를 사용 중 + 프린터 필요해서 대기
  • 운영체제 : 이미 잡힌 프린터/스캐너를 강제로 회수(선점)할 수 없음
  • → 둘 다 상대방이 자원을 반납할 때까지 영원히 대기
  • → 아무도 반납하지 않으니 둘 다 멈춤
  • → 이게 바로 비선점 때문에 발생하는 교착 상태(Deadlock)

 

💡원형 대기 (Circular wait)

• 위 교착 상태에서 설명한 이미지에서 처럼 여러 프로세스가 원형(Loop)으로 자원을 점유한 채, 서로 다음 자원을 기다리는 상태이다.
• 예를 들어, A가 프린터 점유, B가 스캐너 점유, 각자 상대방 자원을 요청하며 서로 대기하는 상황이 있다.

---

교착 상태의 해결 방법

 

💡교착 상태 예방 (Deadlock Prevention)

• 교착 상태를 발생시키는 4가지 필요 조건 중 하나를 충족하지 못하게 하는 방법
• 프로세스에 자원을 할당할 때 상호 배제, 점유와 대기, 비선점, 원형 대기 중 하나라도 만족하지 않으면 교착 상태가 발생하지 않기 때문이다.
• 아래 각 교착 상태를 발생시키는 원인들을 미리 방지할 수 있는 방법들이다.

전략	설명
상호 배제 금지	자원을 여러 프로세스가 공유하도록 설계 (실제로는 어렵다)
점유와 대기 방지	자원을 모두 확보한 후 실행, 하나라도 안 되면 반납하고 다시 시도
비선점 해제	자원 선점 가능하게 설계, 필요 시 강제로 회수
환형 대기 금지	자원에 고유 번호 부여 → 순서대로만 요청하게 하여 순환 방지

 

✅ 할당 가능한 모든 자원에 번호를 매기고 오름차순으 로 할당하는 경우, 원형 대기 조건을 예방하는 경우 예시

원형 대기로 인한 교착 상태 예방

 

💡교착 상태 회피 (Deadlock Avoidance)

• 교착 상태가 발생하지 않을 정도로만 조심하면서 자원을 할당하는 방법
• 교착 상태를 한정된 자원의 무분별한 할당으로 인해 발생하는 문제로 보고, 프로세스가 자원을 요청할 때 미래의 자원 할당 상황을 시뮬레이션한다. 그 결과 교착 상태에 빠지지 않는다면 자원을 할당, 교착 상태에 빠질 위험이 있다면 할당을 거부하는 방식이다.
• 교착 상태 회피 알고리즘의 예시로, 은행원 알고리즘 (Banker's Algorithm)이 있다.

✅ 은행원 알고리즘 (Banker's Algorithm)

• E.W. Dijkstra가 제안한 대표적인 교착 상태 회피 알고리즘
• 은행원이 모든 대출 요청을 승인하면 은행이 파산할 수 있으니, 고객이 요청한 금액을 대출해준 뒤에도 “은행이 파산하지 않는지” 매번 계산하는 것과 동일한 원리

public class BankersAlgorithm {
    // 총 자원 수
    static int[] totalResources = {10, 5, 7};

    // 각 프로세스가 최대 필요로 하는 자원
    static int[][] maximum = {
        {7, 5, 3},
        {3, 2, 2},
        {9, 0, 2},
        {2, 2, 2},
        {4, 3, 3}
    };

    // 현재 각 프로세스에 할당된 자원
    static int[][] allocation = {
        {0, 1, 0},
        {2, 0, 0},
        {3, 0, 2},
        {2, 1, 1},
        {0, 0, 2}
    };

    // 각 프로세스가 앞으로 더 필요로 하는 자원 (maximum - allocation)
    static int[][] need = new int[5][3];

    // 현재 가용 자원(available) = totalResources - 모든 프로세스에 할당된 자원 합
    static int[] available = new int[3];

    public static void main(String[] args) {
        // need 계산
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 3; j++) {
                need[i][j] = maximum[i][j] - allocation[i][j];
            }
        }

        // available 계산
        for (int j = 0; j < 3; j++) {
            int sum = 0;
            for (int i = 0; i < 5; i++) sum += allocation[i][j];
            available[j] = totalResources[j] - sum;
        }

        // 안전성 검사 실행
        if (isSafe()) {
            System.out.println("안전한 상태입니다.");
        } else {
            System.out.println("교착 상태 위험이 있습니다.");
        }
    }

    // Banker's Algorithm 안전성 검사
    public static boolean isSafe() {
        boolean[] finish = new boolean[5];
        int[] work = available.clone();

        int count = 0;
        while (count < 5) {
            boolean progress = false;
            for (int i = 0; i < 5; i++) {
                if (!finish[i] && canProceed(i, work)) {
                    for (int j = 0; j < 3; j++) {
                        work[j] += allocation[i][j];
                    }
                    finish[i] = true;
                    progress = true;
                    count++;
                }
            }
            if (!progress) break; // 더 이상 진전이 없으면 중단
        }
        for (boolean f : finish) if (!f) return false; // 미완료 프로세스가 있으면 unsafe
        return true;
    }

    // 프로세스 i가 현재 work 자원으로 실행 가능한지
    public static boolean canProceed(int i, int[] work) {
        for (int j = 0; j < 3; j++) {
            if (need[i][j] > work[j]) return false;
        }
        return true;
    }
}

 

💡교착 상태 검출 후 회복

• 교착 상태가 발생하는 걸 허용하고, 발생 후 해결하는 방식
• 회복방법
  • 교착 상태가 발생하면 이를 검출하고, 자원 선점 또는 프로세스 강제 종료 등을 통해 복구
  • 자원 섬점을 통한 회복 방법은, 자원 회수가 가능한 순서대로 프로세스를 중단시켜 문제를 해결한다.

---

출처

https://www.hanbit.co.kr/store/books/look.php?p_code=B3079890360

이것이 취업을 위한 컴퓨터 과학이다 with CS 기술 면접