[OS] Deadlock과 Banker's Algorithm

데드락(DeadLock)이란?

데드락

 

두 개 이상의 프로세스들이 서로가 가진 자원을 기다리며 중단된 상태를 말합니다. 

이 과정에서 각 프로세스는 서로가 원하는 자원을 유지한 채 다른 프로세스의 자원을 얻기를 기다립니다.

 

1. Process1은 Process2의 자원을 필요로 함.
2. Process2은 Process1의 자원을 필요로 함.
3. 서로가 가진 자원을 요청하며 기다리기 때문에 서로 무한정 기다리는 현상이 발생.

 

예시 그림

 

자동차를 프로세스, 현재 위치한 길을 자원이라고 생각하면 좀 더 이해하기 쉬울 겁니다.

자동차와 자동차, 즉 서로 다른 프로세스가 현재 위치한 길에서 중간 교차로(서로가 필요로 하는 자원)에서 직선으로 나아가야 하는데, 동시에 다른 길을 사용할 수 없으며 현재 길에서도 벗어나지 못하는 상황이 바로 데드락입니다.

 

 

데드락 필요충분 조건

프로세스에서 데드락 상태가 되기 위해서는 아래의 네 가지 조건이 모두 충족되어야 합니다.

1. 상호 배제(Mutual Exclusion) : 주어진 시간 내에 하나의 프로세스만 자원을 독점할 수 있습니다. 즉, 다른 프로세스들은 이 자원에 접근할 수 없도록 설정된 상황.
2. 점유 대기(Hold And Wait) : 프로세스가 최소한 하나의 자원을 점유하고 있으면서, 다른 프로세스에 할당되어 사용되고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 있어야 하는 상황. 즉, 특정 프로세스가 점유한 자원을 다른 프로세스가 요청하며 대기하는 상태.
3. 비선점(Non-Preemptive) : 다른 프로세스의 자원을 강제적으로 가져올 수 없도록 설정된 상황.
4. 환형 대기(Circular Wait) : 두 개 이상의 프로세스가 서로의 자원을 요구하는 상황.

 

위 네가지 조건이 모두 충족되어도 교착상태가 발생하지 않을 수 있지만, 반대로 교착상태가 발생했다면 위 네가지 조건이 모두 충족되어야 합니다. (필요 충분 조건)

 

교착상태 발생 ----> 네 가지 조건 모두 만족
네 가지 조건 모두 만족 --X--> 교착상태 발생

데드락 해결 방법

데드락 해결 방법으로는 4가지 방법이 존재합니다.

 

첫 번째, 예방

• 애시당초, 시스템을 설계할 때 교착상태가 발생하지 않도록 사전에 제어하는 방법입니다.
• 네 가지 조건 중 어느 하나를 제거함으로써 수행되는 방법.

두 번째, 발견

• 시스템에 교착상태가 발생했는지 점검하여 교착상태에 있는 프로세스와 자원을 발견하고 관련된 프로세스를 제거하는 방법
• 데드락 발견 알고리즘, 자원 할당 그래프 등을 사용.

세 번째, 회복

• 교착상태는 사실 매우 드물게 일어납니다. 때문에 이를 처리하는 비용이 더 크기 때문에 교착상태가 발생하면 작업을 종료시켜 버리는 방법입니다. 
• 현대 운영체제에서 데드락 해결방법으로 채택하는 방법으로, 흔히 볼 수 있는 '응답 없음'이 회복 기법을 사용했다고 보면 됨.

네 번째, 회피

• 교착상태가 발생할 가능성을 배제하지 않고, 데드락이 발생하면 교착상태를 회피하는 방법으로 은행원 알고리즘이 사용됩니다.
• 교착 상태 가능성이 없을 때 자원을 할당하는 방식.

 

데드락 회피 기법 - Banker's Algorithm

교착상태를 회피하는 알고리즘으로, 총 자원의 양과 현재 할당한 자원의 양을 기준으로 안정/불안정 상태로 나눠 안정 상태로 가도록 자원을 할당하는 알고리즘입니다.

 

- 여기서 말하는 안정 상태는 "교착 상태를 일으키지 않는 상태"로, 프로세스의 최대 자원 요구량을 운영체제가 충족시켜줄 수 있는 상태를 말합니다. 

- 불안정 상태는 "안정 상태로 가는 순서열이 존재하지 않는 상태"로 데드락이 발생할 수 있는 상태를 말합니다.

 

은행원 알고리즘을 코드로 살펴보겠습니다.

 

먼저 전체 코드입니다.

import java.util.ArrayList;
import java.util.List;

public class BankersAlgorithm {

    static int n = 5; // 프로세스 갯수
    static int m = 3; // 자원 갯수
    static int[][] need = new int[n + 1][m + 1];
    static boolean[] finish = new boolean[n + 1];
    static List<Resource> allocations = new ArrayList<>(); // 이미 할당한 양
    static List<Resource> maxRequires = new ArrayList<>(); // 최대치로 요구하는 양
    static List<Integer> ans = new ArrayList<>(); // 최대치로 요구하는 양

    public static void main(String[] args) {
        initAllocations();
        initMaxRequires();

        Resource available = new Resource(3, 3, 2);

        // 프로세스가 필요한 자원양을 needs에 담음.
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                need[i][j] = maxRequires.get(i).get(j) - allocations.get(i).get(j);
            }
        }

        for (int i = 0; i < n; i++) {
            System.out.print(i + "번째 프로세스의 자원 요구량 : ");
            for (int j = 0; j < m; j++) {
                System.out.print(need[i][j] + " ");
            }
            System.out.println();
        }

        for (int k = 0; k < n; k++) {
            for (int processNum = 0; processNum < n; processNum++) {
                if (finish[processNum] == false) {
                    boolean flag = false;
                    for (int j = 0; j < m; j++) {
                        if (need[processNum][j] > available.get(j)) {
                            flag = true;
                            break;
                        }
                    }
                    if (flag == false) {
                        ans.add(processNum);
                        // 자원 헌납
                        available.a += allocations.get(processNum).get(0);
                        available.b += allocations.get(processNum).get(1);
                        available.c += allocations.get(processNum).get(2);

                        finish[processNum] = true;
                    }
                }
            }
        }

        boolean isAllSafe = true;
        for (int i = 0; i < n; i++) {
            if (finish[i] == false) {
                isAllSafe = false;
                break;
            }
        }

        if (isAllSafe) {
            System.out.println("-- 안정상태 순서 --");
            for (int i = 0; i < n; i++) {
                System.out.println("Process" + i + " " + ans.get(i));
            }
            System.out.println();
            return;
        }

        System.out.println("불안정 상태");
    }

    private static void initMaxRequires() {
        maxRequires.add(new Resource(7, 5, 3));
        maxRequires.add(new Resource(3, 2, 2));
        maxRequires.add(new Resource(9, 0, 2));
        maxRequires.add(new Resource(2, 2, 2));
        maxRequires.add(new Resource(4, 3, 3));
    }

    private static void initAllocations() {
        allocations.add(new Resource(0, 1, 0));
        allocations.add(new Resource(2, 0, 0));
        allocations.add(new Resource(3, 0, 2));
        allocations.add(new Resource(2, 1, 1));
        allocations.add(new Resource(0, 0, 2));
    }

    static class Resource {
        int a;
        int b;
        int c;

        public int get(int order) {
            if (order == 0) {
                return this.a;
            }

            if (order == 1) {
                return this.b;
            }

            return this.c;
        }

        public Resource(int a, int b, int c) {
            this.a = a;
            this.b = b;
            this.c = c;
        }
    }
}

 

 

여기서 전역(static)으로 선언해준 변수들을 먼저 봅시다.

static int n = 5; // 프로세스 갯수
static int m = 3; // 자원 갯수
static int[][] need = new int[n + 1][m + 1];
static boolean[] finish = new boolean[n + 1];
static List<Resource> allocations = new ArrayList<>(); // 이미 할당한 양
static List<Resource> maxRequires = new ArrayList<>(); // 최대치로 요구하는 양
static List<Integer> ans = new ArrayList<>(); // 최대치로 요구하는 양

 

• n은 현재 실행중인 프로세스 갯수이고, m은 자원 갯수로 실제로는 CPU나 메모리를 의미합니다.
• need는 프로세스가 필요로하는 자원의 요구량을 담은 이차원 배열로, need[i][j]에는 i번째 프로세스가 필요로하는 j번째 자원의 양이 담깁니다.
• finish는 프로세스가 정상적으로 마쳤는지에 대한 여부를 담은 일차원 boolean 배열입니다.
• allocations는 프로세스에 이미 할당되어서 프로세스가 가지고 있는 자원의 양이 담긴 List입니다.
  • allocation.get(i).get(0) = i번째 프로세스가 이미 할당되어 가진 a 자원의 양
  • allocation.get(i).get(1) = i번째 프로세스가 이미 할당되어 가진 b 자원의 양
  • allocation.get(i).get(2) = i번째 프로세스가 이미 할당되어 가진 c 자원의 양
• maxRequires는 프로세스가 최대치로 요구하는 자원의 양이 담긴 List 입니다.
  • maxRequires.get(i).get(0) = i번째 프로세스가 요구하는 a 자원의 최대량
  • maxRequires.get(i).get(1) = i번째 프로세스가 요구하는 b 자원의 최대량
  • maxRequires.get(i).get(2) = i번째 프로세스가 요구하는 c 자원의 최대량 
• ans에는 프로세스가 안정상태로 도달하는 순서대로 프로세스 번호를 담을 List

 

먼저 5개의 프로세스가 각 필요로 하는 최대 자원량과 현재 가지고 있는 자원량을 초기화 해봅시다.

private static void initMaxRequires() {
    maxRequires.add(new Resource(7, 5, 3));
    maxRequires.add(new Resource(3, 2, 2));
    maxRequires.add(new Resource(9, 0, 2));
    maxRequires.add(new Resource(2, 2, 2));
    maxRequires.add(new Resource(4, 3, 3));
}

private static void initAllocations() {
    allocations.add(new Resource(0, 1, 0));
    allocations.add(new Resource(2, 0, 0));
    allocations.add(new Resource(3, 0, 2));
    allocations.add(new Resource(2, 1, 1));
    allocations.add(new Resource(0, 0, 2));
}

 

 

프로세스	Allocation ( A, B, C )	Max_Requires ( A, B, C )
P0	( 0, 1, 0 )	( 7, 5, 3 )
P1	( 2, 0, 0 )	( 3, 2, 2 )
P2	( 3, 0, 2 )	( 9, 0, 2 )
P3	( 2, 1, 1 )	( 2, 2, 2 )
P4	( 0, 0, 2 )	( 4, 3, 3 )

 

 

Resource available = new Resource(3, 3, 2);

• 현재 운영체제가 프로세스에 할당해 줄 수 있는 자원입니다.

 

// 프로세스가 필요한 자원양을 needs에 담음.
for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        need[i][j] = maxRequires.get(i).get(j) - allocations.get(i).get(j);
    }
}

• 프로세스가 필요로 하는 자원양을 needs에 담아주었습니다.
• 필요로 하는 자원양은 최대 필요로 하는 자원량에서 이미 할당받아 가지고 있는 자원의 양만큼 빼주면 되겠습니다.

프로세스	Need ( A, B, C )
P0	( 7, 4, 3 )
P1	( 1, 2, 2 )
P2	( 6, 0, 0 )
P3	( 0, 1, 1 )
P4	( 4, 3, 1)

 

이제 은행원 알고리즘을 사용하여 교착상태를 회피해 볼건데요. 은행원 알고리즘 구조를 먼저 살펴봅시다.

 

은행원 알고리즘 Flow

1. 0번 프로세스~ n-1번 프로세스에 대하여 순서대로 프로세스가 요구하는 자원량(need)이 available한 자원량보다 큰 경우 해당 프로세스는 pass하여 대기.
2. 프로세스가 요구하는 자원량 need가 현재 할당 가능한 자원량보다 작은 경우 자원을 할당할 수 있으니 자원을 할당.
3. 프로세스 정상수행 및 종료.
4. 이 후 할당 가능한 자원량(available)에 정상수행 후 종료된 프로세스의 자원량을 더해줍니다.
5. 1~4번 과정을 모든 프로세스에 대해 n(최악의 경우를 고려하여)번 반복하여 모든 finish가 true가 되면 안정상태에 이름.

 

위 과정을 구현한 것이 아래의 코드입니다.

for (int k = 0; k < n; k++) {
    for (int processNum = 0; processNum < n; processNum++) {
        if (finish[processNum] == false) {
            boolean flag = false;
            for (int j = 0; j < m; j++) {
                if (need[processNum][j] > available.get(j)) {
                    flag = true;
                    break;
                }
            }
            if (flag == false) {
                ans.add(processNum);
                // 자원 헌납
                available.a += allocations.get(processNum).get(0);
                available.b += allocations.get(processNum).get(1);
                available.c += allocations.get(processNum).get(2);

                finish[processNum] = true;
            }
        }
    }
}

 

프로세스가 모두 마친 경우 안정상태에 이르기 때문에 데드락을 회피했다고 볼 수 있습니다. 모든 프로세스에 대해 iter하여 finish가 true인지 검사해주고 모두 true라면 안정상태가 됩니다.

boolean isAllSafe = true;
for (int i = 0; i < n; i++) {
    if (finish[i] == false) {
        isAllSafe = false;
        break;
    }
}

 

모든 프로세스가 안정상태라면 안정상태에 도달하게 된 프로세스의 순서를 알 수 있겠습니다. 아래 코드에서 안정상태에 도달하게 된 프로세스의 순서를 담은 리스트를 출력합니다.

if (isAllSafe) {
    System.out.println("-- 안정상태 순서 --");
    for (int i = 0; i < n; i++) {
        System.out.println("Process" + i + " " + ans.get(i));
    }
    System.out.println();
    return;
}

System.out.println("불안정 상태");

 

실제 결과

 

이렇게 데드락 회피기법인 은행원 알고리즘을 코드로 구현해보았습니다.

 

은행원 알고리즘은 프로세스가 시스템에 들어갈 때 필요한 최대 자원 수를 예측해야 하는데 사실 이 최대필요량(maxRequires)를 예측하기가 쉽지 않고 해당 알고리즘에 대한 자원소모량이 증가하게 되며, 프로그램 수 또한 고정되어있지 않고 항상 변할 수 있기 때문에 은행원 알고리즘은 사실상 활용하기가 어렵다는 치명적인 단점이 존재합니다. 

 

<참고 자료>

Deadlock(교착 상태)의 개념과 발생 원인