[OS] DeadLock(교착상태)

1. Dining philosophers problem(식사하는 철학자 문제)

식사하는 철학자

 

5명의 철학자가 원탁에 앉아서 식사를 한다. 철학자들 사이에는 포크가 하나씩 놓여 있고, 철학자들은 다음의 과정을 통해 식사를 한다.

1. 일정 시간 생각을 한다.
2. 왼쪽 포크가 사용 가능해질 때까지 대기한다. 만약 사용 가능하다면 집어든다.
3. 오른쪽 포크가 사용 가능해질 때까지 대기한다. 만약 사용 가능하다면 집어든다.
4. 양쪽의 포크를 잡으면 일정 시간만큼 식사를 한다.
5. 오른쪽 포크를 내려놓는다.
6. 왼쪽 포크를 내려놓는다.
7. 다시 1번으로 돌아간다.

 

간단하게 생각해, 만약 모든 철학자들이 동시에 자신의 왼쪽 포크를 잡는다면, 모든 철학자들이 자기 오른쪽의 포크가 사용 가능해질 때까지 기다려야 한다. 그런데 모든 철학자들이 그러고 있다. 이 상태에서는 모든 철학자가 영원히 3번 상태에 머물러있어 아무것도 진행할 수가 없게 되는데, 이것이 교착(Deadlock)상태이다.

 

2. 교착상태란?

DEAD LOCK 즉, 교착상태란 두 개 이상의 프로세스나 스레드가 서로 자원을 얻지 못해서 다음 처리를 하지 못하는 상태 즉, 무한히 다음 자원을 기다리게 되는 상태를 말한다. 쉽게 말해 시스템적으로 한정된 자원을 여러 곳에서 사용하려고 할 때 발생한다.

프로세스1과 2가 자원1, 2를 모두 얻어야 한다고 가정해보자

t1 : 프로세스1이 자원1을 얻음 / 프로세스2가 자원2를 얻음

t2 : 프로세스1은 자원2를 기다림 / 프로세스2는 자원1을 기다림

 

현재 서로 원하는 자원이 상대방에 할당되어 있어서 두 프로세스는 무한정 wait 상태에 빠짐

→ 이것이 바로 DeadLock!!!!!!

public class DeadlockExample {
    // 두 개의 락 객체
    private static final Object lock1 = new Object();
    private static final Object lock2 = new Object();

    public static void main(String[] args) {
        // 첫 번째 스레드: lock1 -> lock2 순서로 획득
        Thread thread1 = new Thread(() -> {
            synchronized (lock1) {
                System.out.println("Thread-1: lock1 획득");
                
                // 일부러 지연을 줘서 데드락을 유도
                try { Thread.sleep(100); } catch (InterruptedException e) {}

                System.out.println("Thread-1: lock2 획득 시도");
                synchronized (lock2) {
                    System.out.println("Thread-1: lock2 획득 완료");
                }
            }
        });

        // 두 번째 스레드: lock2 -> lock1 순서로 획득
        Thread thread2 = new Thread(() -> {
            synchronized (lock2) {
                System.out.println("Thread-2: lock2 획득");
                
                // 일부러 지연을 줘서 데드락을 유도
                try { Thread.sleep(100); } catch (InterruptedException e) {}

                System.out.println("Thread-2: lock1 획득 시도");
                synchronized (lock1) {
                    System.out.println("Thread-2: lock1 획득 완료");
                }
            }
        });

        // 두 스레드 실행
        thread1.start();
        thread2.start();
    }
}

위 코드 실행 결과: 여기서 멈춰서 아무 출력도 없음

3. 교착상태(DeadLock) 발생 조건 < 코프만 조건 >

코프만은 1971년 6월 논문에서 컴퓨터 시스템에서 교착 상태를 유발할 수 있는 4가지의 필요충분 조건을 찾아내어 증명하였다. 그의 이론은 아래 4가지 조건을 모두 허용된 컴퓨터 시스템은 언제든 교착상태가 발생할 수 있다는 것이다.(가능성)

• 상호 배제(Mutual exclusion) - 자원을 한번에 한 프로세스만 사용할 수 있음
• 점유 대기(Hold and wait) - 최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용하고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 존재해야 함
• 비 선점(No preemption) - 다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없음
• 순환 대기(Circular wait) - 프로세스의 집합에서 순환 형태로 자원을 대기하고 있어야 함

 

4. 교착상태(Dead Lock)의 해결법 ( 예방과 무시는 다르다. )

교착상태의 해결법에는 4가지가 있다.

 

4.1. 교착상태 예방(prevention) -> 교착상태 발생 조건을 반대로 생각

교착상태예방은 앞에서 언급한 코프만 4가지 조건 중 하나 이상의 조건이 아예 성립되지 못하도록 시스템을 설계하고 구성하여 교착상태가 발생할 여지가 없도록 예방하는 것이다.

 

1) 상호배제 삭제

시스템 내에 있는 상호 배타적인 자원을 없애버리는 방법이다. 애초에 시스템 내의 모든 자원을 공유할 수 있다면 데드락은 발생하지 않는다. 하지만 공유 자원에 대한 상호 배제 처리를 하지 않는다면 그에 따르는 문제가 추가된다.

=> 현실적이지 않은 방법

 

2) 점유 대기 삭제

점유와 대기 예방은 프로세스가 자원을 점유한 상태에서 다른 자원을 기다리는 상황을 없애는 방식이다. All or Nothing 방식으로 자원을 배분하는 것이죠. 필요한 모든 자원을 얻을 수 있을 때만 프로세스를 시작하는 것이다. 하지만 이러한 방식은 자원의 활용성이 떨어진다는 큰 단점이 있다.

 

3) 자원의 선점 허용

자원의 선점을 허용한다면 자원을 할당받은 프로세스에게서 자원을 빼앗을 수 있도록 처리해야 한다. 하지만 임계 구역을 보호하기 위해 잠금을 사용하면 자원을 빼앗을 수 없다. 설령 자원을 빼앗더라도 어떤 기준으로 빼앗을지, 빼앗은 시간 중 얼마나 사용할지 등의 결정( 우선순위 기준 )이 어렵다. 또한 이런 방법이 Starvation을 일으킬 수 도 있다.

=> 현실적이지 않은 방법

 

4) 환형 대기 제거

원형 대기 예방은 자원에 번호를 매기는 방식으로 구현할 수 있다. 낮은 번호의 자원을 사용하는 프로세스가 높은 번호의 자원을 요청하는 것은 허용하지만 그 반대는 허용하지 않는 식이다. 하지만 이러한 방식은 프로세스 작업 진행에 유연성을 떨어뜨리며 자원의 번호를 어떤 방식으로 부여할 것인지에 대한 문제가 발생한다.

 

데드락 예방 방식은 자원에 대한 이용률을 대단히 감소시킨다. 데드락은 기본적으로 자주 생기는 문제가 아니다. 그럼에도 불구하고 이를 위해서 하는 데드락 예방 방식은 Overhead가 너무 커 실효성이 적다고 볼 수 있다.  

 

4.2. 교착상태 회피(avoidance)

교착상태 회치는 운영체제가 자원을 할당할 때 교착상태에 빠지지 않을 것이라고 확신하는 경우에만 자원을 할당하여 미래에 교착상태로 가지 않도록 하는 방법이다.

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

교착상태 회피 방법의 대표적인 알고리즘이다.

Edsger Dijstra에 의해 개발된 알고리즘으로 시스템을 안전한 상태와 불안전한 상태로 나누고, 자원을 할당하였을 때 안전한 상태로만 갈 때만 자원을 할당한다.

이 알고리즘을 사용하기 위해서는 각 스레드는 실행 전에 필요한 전체 자원의 수를 운영체제가 알고 있어야 하는데, 스레드의 실행 전에 필요한 자원의 개수를 아는 것은 사실상 불가능하므로 비현실적인 알고리즘이다.

import java.util.Arrays;

public class Bankers {
    private int numProcesses;   // 프로세스 개수
    private int numResources;   // 자원 종류 개수
    private int[] available;    // 사용 가능한 자원
    private int[][] max;        // 각 프로세스가 최대 요구하는 자원
    private int[][] allocation; // 현재 할당된 자원
    private int[][] need;       // 추가로 필요한 자원

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

        // Need 행렬 초기화: Need[i][j] = Max[i][j] - Allocation[i][j]
        for (int i = 0; i < numProcesses; i++) {
            for (int j = 0; j < numResources; j++) {
                need[i][j] = max[i][j] - allocation[i][j];
            }
        }
    }

    // 안전한 상태인지 확인하는 함수 (Safety Algorithm)
    private boolean isSafe() {
        boolean[] finish = new boolean[numProcesses]; // 프로세스 완료 여부
        int[] work = Arrays.copyOf(available, available.length); // 가용 자원 복사

        int count = 0;
        while (count < numProcesses) {
            boolean found = false;
            for (int i = 0; i < numProcesses; i++) {
                if (!finish[i]) { // 아직 완료되지 않은 프로세스
                    boolean possible = true;
                    for (int j = 0; j < numResources; j++) {
                        if (need[i][j] > work[j]) {
                            possible = false;
                            break;
                        }
                    }
                    if (possible) { // 실행 가능한 경우
                        for (int j = 0; j < numResources; j++) {
                            work[j] += allocation[i][j]; // 프로세스가 자원을 반환
                        }
                        finish[i] = true;
                        found = true;
                        count++;
                    }
                }
            }
            if (!found) return false; // 교착 상태 발생 가능
        }
        return true; // 모든 프로세스가 실행될 수 있으면 안전 상태
    }

    // 자원 요청 처리 (Resource Request Algorithm)
    public boolean requestResources(int processID, int[] request) {
        // 요청이 Need[i]보다 크면 요청 거부
        for (int j = 0; j < numResources; j++) {
            if (request[j] > need[processID][j]) {
                System.out.println("Error: 요청이 최대 필요량을 초과함!");
                return false;
            }
        }

        // 요청이 Available보다 크면 대기
        for (int j = 0; j < numResources; j++) {
            if (request[j] > available[j]) {
                System.out.println("자원이 부족하여 요청 대기");
                return false;
            }
        }

        // 자원 가정 할당 (임시 할당 후 안전 상태 확인)
        for (int j = 0; j < numResources; j++) {
            available[j] -= request[j];
            allocation[processID][j] += request[j];
            need[processID][j] -= request[j];
        }

        // 안전 상태 확인
        if (isSafe()) {
            System.out.println("자원 요청 승인");
            return true;
        } else {
            // 안전하지 않다면 원래 상태로 복구
            for (int j = 0; j < numResources; j++) {
                available[j] += request[j];
                allocation[processID][j] -= request[j];
                need[processID][j] += request[j];
            }
            System.out.println("자원 요청 거부: 시스템이 불안전 상태가 됨");
            return false;
        }
    }

    public static void main(String[] args) {
        // 프로세스 개수 및 자원 종류 개수
        int numProcesses = 5, numResources = 3;

        // 사용 가능한 자원 수
        int[] available = {3, 3, 2};

        // 각 프로세스의 최대 요구량 (Max Matrix)
        int[][] max = {
            {7, 5, 3},
            {3, 2, 2},
            {9, 0, 2},
            {2, 2, 2},
            {4, 3, 3}
        };

        // 현재 할당된 자원 (Allocation Matrix)
        int[][] allocation = {
            {0, 1, 0},
            {2, 0, 0},
            {3, 0, 2},
            {2, 1, 1},
            {0, 0, 2}
        };

        // Banker's Algorithm 객체 생성
        BankersAlgorithm ba = new BankersAlgorithm(numProcesses, numResources, available, max, allocation);

        // 자원 요청 시뮬레이션 (예: 프로세스 1이 [1,0,2] 요청)
        int[] request1 = {1, 0, 2};
        ba.requestResources(1, request1);

        // 추가 요청 예제 (예: 프로세스 4가 [3,3,0] 요청)
        int[] request2 = {3, 3, 0};
        ba.requestResources(4, request2);
    }
}

 

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

교착상태의 예방이나 회피전략을 가동하지 않고, 운영체제가 교착상태를 감지하는 별도의 프로그램을 구동시켜 교착상태에 빠진 스레드 그룹을 발견하면 교착상태로부터 해제하는 방법이다. 즉,  데드락이 발생한 후 해결하는 방식이다. 현실적으로 가장 많이 사용되는 방식이다.

1. 데드락 검출 방식

데드락이 발생했는지를 검출하는 방식은 다음과 같이 두 가지로 나뉜다.

(1) 타임아웃을 이용한 데드락 검출

타임아웃을 기반으로 일정 시간 동안 작업이 진행되지 않은 프로세스를 데드락 상태로 간주하는 방식이다.

• 장점: 구현이 단순하여 데이터베이스 및 운영체제에서 선호됨
• 단점: 프로세스가 데드락이 아닌 다른 이유로 작업을 수행하지 못하는 경우에도 데드락으로 오판될 수 있음

(2) 자원 할당 그래프를 이용한 데드락 검출

자원 할당 그래프(Resource Allocation Graph, RAG)는 프로세스와 자원의 할당 및 요청 관계를 나타내는 그래프이다.

• 검출 방식:
  • 자원이 하나뿐인 경우: 사이클이 존재하면 데드락 상태
  • 자원이 여러 개일 경우: 사이클이 존재한다고 해서 반드시 데드락은 아님, 추가적인 분석이 필요함
• 장점: 타임아웃 방식보다 정확한 데드락 검출 가능
• 단점: 자원 할당 그래프를 지속적으로 관리해야 하므로 추가적인 오버헤드 발생

2. 데드락 회복 방식

데드락이 검출되면 운영체제는 해당 프로세스를 풀어주어야 합니다. 회복 방식은 크게 두 가지로 나뉩니다.

(1) 프로세스 종료

데드락이 발생한 프로세스를 종료하면 자원이 반납되어 데드락이 해결될 수 있다. 종료 방식에는 다음 두 가지가 있다.

1. 모든 데드락 프로세스 종료:
   • 단순한 해결책이지만, 많은 프로세스를 종료해야 하므로 성능 저하 가능성이 큼
2. 하나씩 프로세스를 종료하며 확인:
   • 한 번에 하나의 프로세스를 종료하고 데드락 사이클이 사라지는지 확인하는 방식
   • 시스템의 부담을 줄일 수 있으나, 종료해야 할 프로세스를 결정하는 과정이 필요

(2) 자원 빼앗기

자원의 부족으로 인해 데드락이 발생하는 점을 이용하여, 특정 프로세스로부터 자원을 강제로 회수하는 방법.

• 방법: 비용을 최소화하면서 가장 적절한 프로세스를 선택하여 자원을 회수함
• 문제점:
  • 자원을 빼앗긴 프로세스는 정상적인 실행을 보장할 수 없음
  • 자원 회수 후 롤백(Rollback)이 필요하여 추가적인 오버헤드 발생
  • 특정 프로세스가 지속적으로 자원을 빼앗길 경우 기아 상태(Starvation) 발생 가능

 

데드락 검출과 회복 방식은 현실적인 해결 방법이지만, 검출 과정에서의 정확성과 회복 과정에서의 비용을 고려해야 한다. 

 

4.3. 교착 상태 무시(ignore and reboot)

교착상태 예방, 회피, 감지 및 복구 방법에는 많은 시간과 공간을 필요로 하여 컴퓨터 시스템 성능을 떨어뜨리기 때문에, 또한 범용 시스템에서는 교착상태가 발생한다고 하더라도 파국을 부를 만한 작업을 실행시키지 않기 때문에 아무런 대책없이 교착상태가 발생하도록 내려두는 방법이다. 교착상태 무시 알고리즘을 ostrich 알고리즘(타조 알고리즘) 이라고 부른다.

 

Ostrich 알고리즘 (타조 알고리즘)

교착 상태 무시 방법의 대표적인 알고리즘이다.

타조 알고리즘은 교착상태에 대한 아무런 대책 없이 컴퓨터 시스템을 가동시키고, 교착상태가 발생하면 시스템을 재시작(reboot)하거나 특정 스레드를 강제 종료하는 쉬운 방법으로, 교착상태를 해결한다.

컴퓨터 시스템에서 교착상태는 얼마나 자주 발생하는가에 대한 통계치는 없다.

어떤 문헌에서는 1년에 한 번 정도 발생한다고도 하고, 멀티스레드 프로그램을 오래 작성한 개발자들 사이에서는 이보다는 자주 발생한다고도 한다. 교착상태가 발생할 가능성이 극히 적은 반면 교착상태를 피하기 위한 비용이 많이 들어간다면, 굳이 많은 시간과 비용을 소면서 까지 교착상태 예방, 회피, 혹은 감지 복구등의 방법을 사용할 필요가 있을까? 라는 의문에서 탄생한 알고리즘이다.

 

Not everything worth doing is worth doing well.

public class Ostrich {
    private static final Object lock1 = new Object();
    private static final Object lock2 = new Object();

    public static void main(String[] args) {
        Thread thread1 = new Thread(() -> {
            synchronized (lock1) {
                System.out.println("Thread-1: lock1 획득");

                // 일부러 지연을 줘서 데드락 유도
                try { Thread.sleep(100); } catch (InterruptedException e) {}

                System.out.println("Thread-1: lock2 획득 시도");
                synchronized (lock2) {
                    System.out.println("Thread-1: lock2 획득 완료");
                }
            }
        });

        Thread thread2 = new Thread(() -> {
            synchronized (lock2) {
                System.out.println("Thread-2: lock2 획득");

                // 일부러 지연을 줘서 데드락 유도
                try { Thread.sleep(100); } catch (InterruptedException e) {}

                System.out.println("Thread-2: lock1 획득 시도");
                synchronized (lock1) {
                    System.out.println("Thread-2: lock1 획득 완료");
                }
            }
        });

        thread1.start();
        thread2.start();

        // 데드락 감지를 위한 감시 스레드
        new Thread(() -> {
            try {
                Thread.sleep(5000); // 5초 동안 대기 후 검사
                System.out.println("⚠️ 교착 상태 감지됨! 시스템 강제 종료...");
                System.exit(1); // 시스템 강제 종료 (Ostrich Algorithm 방식)
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }).start();
    }
}