교착 상태(deadlock)와 은행원 알고리즘

교착 상태란?

두 개 이상의 프로세스나 스레드가 서로 상대방의 작업이 끝나기를 무한정 기다리며, 결국 아무것도 완료되지 않는 상태.

 

 

 

교착 상태의 원인 (조건)

1. 상호배제(Mutual Exclusion):  자원은 한번에 하나의 프로세스만 사용 가능
2. 점유대기(Hold and Wait): 최소 하나의 자원을 점유하고 있으며, 추가 자원을 요청하여 대기중인 프로세스가 존재
3. 비선점(Non-preemptive): 자원을 강제로 뺏을 수 없음
4. 환형 대기(Circular Wait): 대기하고 있는 프로세스들 간의 순환적인 고리가 형성됨.

4가지 조건이 모두 충족되어도 교착상태는 발생하지 않을 수 있다. 그러나 4가지 조건이 모두 충족되어야 “교착상태가 일어날 수” 있다.

 

 

 

 

교착 상태 해결 방법

 

• 교착상태 예방(Prevention):
  • 교착상태 발생 조건 중 하나를 미리 제거하여 교착상태가 발생하지 않도록 함.
  • 예를 들어, 점유 대기 조건을 제거하기 위해 프로세스가 자원을 요청하기 전에 모든 자원을 할당받도록 하기.
• 교착상태 회피(Avoidance):
  • 자원 할당 시 교착상태가 발생하지 않도록 하는 알고리즘을 사용.
  • 대표적인 알고리즘 은행원 알고리즘(Banker's Algorithm)
• 교착상태 탐지(Detection):
  • 시스템이 교착상태에 빠졌는지 탐지하는 알고리즘을 사용하고, 교착상태를 해결하기 위한 조치를 취하기.
  • 자원 할당 그래프(Resource Allocation Graph)를 사용하여 탐지할 수 있음.
• 교착상태 회복(Recovery):
  • 교착상태를 탐지한 후, 교착상태를 해결하기 위한 방법을 적용.
  • 예를 들어, 교착상태에 빠진 프로세스를 강제로 종료하거나 자원을 강제로 회수하기.

- 현대 운영체제는 어떻게 해결할까?

교착상태는 매우 드물게 일어나기 때문에 이를 처리하는 비용이 더 커서 교착 상태가 발생하면 이를 탐지하고 사용자가 작업을 종료하게 함.

 

 

 

 

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

은행원 알고리즘이란? 

Dijkstra가 제안한 교착상태 회피 알고리즘으로, 은행가가 여러 고객에게 자원을 빌려주되, 항상 자원이 충분히 남아서 모든 고객이 자신이 최대 필요량을 충족할 수 있도록 하는 원리에 기반한다.

현재 할당한 자원의 양을 기준으로 안정/불안정 상태로 나누고 안정 상태로 가도록 자원을 할당하는 알고리즘이다.

안정상태 : 교착상태를 일으키지 않는 상태. 프로세스의 최대 자원 요구량을 운영체제가 충족시킬 수 있는 상태.
불안정상태 : 안정상태로 가는 순서열이 존재하지 않는 상태

 

 

 

주요 데이터 구조

1. Available:
   • 현재 사용 가능한 각 자원 유형의 수를 나타내는 벡터.
   • Available[j]는 자원 유형 j의 사용 가능한 인스턴스 수.
2. Max:
   • 각 프로세스가 필요로 하는 최대 자원 수를 나타내는 행렬.
   • Max[i][j]는 프로세스 i가 자원 유형 j에서 필요로 하는 최대 인스턴스 수.
3. Allocation:
   • 각 프로세스에 현재 할당된 자원의 수를 나타내는 행렬.
   • Allocation[i][j]는 프로세스 i에 할당된 자원 유형 j의 인스턴스 수.
4. Need:
   • 각 프로세스가 앞으로 필요로 하는 자원의 수를 나타내는 행렬.
   • Need[i][j] = Max[i][j] - Allocation[i][j]로 계산.

 

은행원 알고리즘 동작과 예제

request[i] 는 프로세스 i가 요청한 자원.

1. request[i] <= need[i] 가 아니면  오류
2. request[i] <= available[i] 가 아니면 대기
3. 이후, available[i] += request[i] 이고, need[i] -= request[i] 이다. (자원 할당을 가정)
4. 이러한 과정을 모든 프로세스에 대해 반복한 뒤 모든 finish[i]가 True라면 안정상태가 됨.
5. 안정상태이면 자원을 할당하고, 그렇지 않으면 요청을 보류함. (available[i], need[i] 값 롤백 필요)

 

 

Java 예제 코드

프로세스 P0, P1, P2, P3, P4에 대해

Allocation, Max, Need, Available 값이 위의 표와 같을 때

안정상태가 되는 순서는 다음과 같다

P1 → P3 → P4 → P0 → P2

 

 

public class BankersAlgorithm {

    // 프로세스 수와 자원 수를 저장하는 변수
    private int numberOfProcesses;
    private int numberOfResources;

    // 사용 가능한 자원의 수를 저장하는 배열
    private int[] available;

    // 각 프로세스가 필요로 하는 최대 자원의 수를 저장하는 행렬
    private int[][] max;

    // 각 프로세스에 현재 할당된 자원의 수를 저장하는 행렬
    private int[][] allocation;

    // 각 프로세스가 추가로 필요로 하는 자원의 수를 저장하는 행렬
    private int[][] need;

    // 생성자: 프로세스 수, 자원 수, 사용 가능한 자원, 최대 자원 요구량, 할당된 자원을 초기화
    public BankersAlgorithm(int numberOfProcesses, int numberOfResources, int[] available, int[][] max, int[][] allocation) {
        this.numberOfProcesses = numberOfProcesses;
        this.numberOfResources = numberOfResources;
        this.available = available;
        this.max = max;
        this.allocation = allocation;
        this.need = new int[numberOfProcesses][numberOfResources];
        calculateNeed();
    }

    // need 행렬을 계산하는 메서드
    private void calculateNeed() {
        for (int i = 0; i < numberOfProcesses; i++) {
            for (int j = 0; j < numberOfResources; j++) {
                // need[i][j] = max[i][j] - allocation[i][j]
                need[i][j] = max[i][j] - allocation[i][j];
            }
        }
    }

    // 시스템이 안전한 상태인지 검사하는 메서드
    public boolean isSafe() {
        // 현재 사용 가능한 자원을 나타내는 work 배열 초기화
        int[] work = new int[numberOfResources];
        boolean[] finish = new boolean[numberOfProcesses];
        System.arraycopy(available, 0, work, 0, numberOfResources);

        // 모든 프로세스를 완료하지 않은 상태로 초기화
        for (int i = 0; i < numberOfProcesses; i++) {
            finish[i] = false;
        }

        // 모든 프로세스를 검사
        for (int i = 0; i < numberOfProcesses; i++) {
            for (int j = 0; j < numberOfProcesses; j++) {
                // 프로세스 j가 완료되지 않았고, 요청한 자원을 모두 충족할 수 있는 경우
                if (!finish[j] && canProceed(j, work)) {
                    // work 배열에 할당된 자원을 반영
                    for (int k = 0; k < numberOfResources; k++) {
                        work[k] += allocation[j][k];
                    }
                    finish[j] = true; // 프로세스 j가 완료됨을 표시
                    i = -1; // 루프를 다시 시작하여 모든 프로세스를 재검사
                }
            }
        }

        // 모든 프로세스가 완료되었는지 검사
        for (boolean f : finish) {
            if (!f) return false;
        }
        return true;
    }

    // 프로세스가 요청한 자원을 충족할 수 있는지 검사하는 메서드
    private boolean canProceed(int process, int[] work) {
        for (int i = 0; i < numberOfResources; i++) {
            // 필요 자원보다 work 자원이 부족하면 false 반환
            if (need[process][i] > work[i]) return false;
        }
        return true;
    }

    // 프로세스가 자원을 요청할 때 호출되는 메서드
    public boolean requestResources(int process, int[] request) {
        // 요청한 자원이 need를 초과하지 않는지 검사
        for (int i = 0; i < numberOfResources; i++) {
            if (request[i] > need[process][i]) {
                System.out.println("Error: process has exceeded its maximum claim.");
                return false;
            }
            // 요청한 자원이 available보다 적거나 같은지 검사
            if (request[i] > available[i]) {
                System.out.println("Error: resources are not available.");
                return false;
            }
        }

        // 자원을 할당하는 가정 하에 시스템이 안전한 상태인지 검사
        for (int i = 0; i < numberOfResources; i++) {
            available[i] -= request[i];
            allocation[process][i] += request[i];
            need[process][i] -= request[i];
        }

        // 시스템이 안전한 상태인지 검사
        if (isSafe()) {
            return true;
        } else {
            // 시스템이 안전하지 않으면 자원 할당을 롤백
            for (int i = 0; i < numberOfResources; i++) {
                available[i] += request[i];
                allocation[process][i] -= request[i];
                need[process][i] += request[i];
            }
            return false;
        }
    }

    public static void main(String[] args) {
        int numberOfProcesses = 5; // 프로세스 수
        int numberOfResources = 3; // 자원 수

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

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

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

        BankersAlgorithm ba = new BankersAlgorithm(numberOfProcesses, numberOfResources, available, max, allocation);

        int[] request1 = {0, 2, 0}; // 프로세스 1의 자원 요청
        System.out.println("Request 1: " + ba.requestResources(1, request1));

        int[] request2 = {1, 0, 2}; // 프로세스 4의 자원 요청
        System.out.println("Request 2: " + ba.requestResources(4, request2));

        int[] request3 = {3, 3, 0}; // 프로세스 0의 자원 요청
        System.out.println("Request 3: " + ba.requestResources(0, request3));
    }
}

 

 

은행원 알고리즘의 단점

프로세스가 시스템에 들어갈 때 필요한 최대 자원 수를 예측해야 하는데 이를 예측하기가 쉽지 않음.

해당 알고리즘에 대한 자원소모량이 증가하게 되며 프로그램의 수는 고정되어있지 않고 항상 변하기 때문에 쓰기가 어려움.