교착 상태 회피

교착 상태 회피는 방법 중 하나는 자원이 어떻게 요청될지에 대한 정보를 제공하도록 요구하는 것이다.
각 스레드의 요청과 방출에 대한 순서를 파악한다면 우리는 각 요청에 대해서 가능한 미래의 교착 상태를 피할 수 있다(스레드 대기를 통해). 이러한 동작을 위해 현재 가용자원, 각 스레드에 할당된 자원, 앞으로 요청할 자원과 방출할 자원을 알고 있어야 한다.

아래는 교착 상태 회피에 대한 알고리즘을 설명하겠다.

안전 상태

시스템 상태가 안전하다는 말은 시스템에 어떤 순서로든 스레드들이 요청하는 모든 자원을 교착 상태를 야기시키지 않고 차례로 모두 할당할 수 있음을 말한다. 즉, 시스템이 안전 순서를 찾을 수 있다면 시스템은 안전하다고 말한다. 만약 찾을 수 없다면 불안전하다고 말한다.

예를 들기 위해 총 시스템에는 12개의 자원이 있고 스레드 T0, T1, T2가 있다고 가정하자.
각 스레드의 최대 소요량은 T0 = 10, T1 = 4, T2= 9이다.

시간 / 이름	T0	T1	T2	남은 자원
0	5	2	2	3
1	5	4	2	1
2	5	완료	2	5
3	10	완료	2	0
4	완료	완료	2	10
5	완료	완료	9	3
6	완료	완료	완료	12

위 표와 같은 형태로 모두 할당할 수 있는 순서를 찾게 되면 현재 상태는 안전 상태라고 할 수 있다.

하지만 시스템은 안전상태에 있다가도 불안전 상태로 변경될 수 있다. 예를 들어 아래와 같은 경우이다.

시간 / 이름	T0	T1	T2	남은 자원
0	5	2	2	3
1	5	2	3	2
2	5	4	3	0
3	5	완료	3	4

1초 이후 시스템에 남은 자원은 2개이고 이 자원을 이용해서 처리할 수 있는 스레드는 T1하나만 존재하게 된다. 이후 T1을 완료후 자원을 반납하여도 어떠한 스레드도 최대 자원을 할당할 수 없게 된다. 이때 교착상태가 발생하게 된다.

회피 알고리즘의 주 목적은 시스템이 안전 상태를 떠나지 않도록 하는것이다. 스레드들이 자원을 요청하면 시스템은 자원을 즉시 할당할지 대기해야할지 결정하여 안전상태를 유지하도록 한다.

스레드가 요청한 자원보다 시스템에서 더 많은 자원을 가지고 있다 하더라고 프로세스가 대기해야할 상황이 발생할 수 있다. 따라서 회피 방법을 사용한 자원의 이용률은 낮아질수 밖에 없다.

자원 할당 그래프 알고리즘

시스템이 자원 유형 마다 하나의 인스턴스만 갖고있다면 이전 글에서 설명한 자원 할당 그래프에서 예약 간선이라는 개념을 추가하여 해결할 수 있다. 예약 간선은 점선으로 나타내며 T1-> R1 예약 간선의 의미는 T1이 미래에 R1을 요청할것이라는 의미이다. 이 간선은 자원을 요청하게 되면 요청 간선으로 바뀌며 자원을 방출할때는 R1->T1의 할당 간선이 T1->R1 예약 간선으로 변경된다.

중요한점은 시스템에서 어떤 자원이 요청되어야하는지 미리 알고 모든 예약 간선을 표시 해놔야한다. 아래는 자원 할당 그래프의 예제이다.

이후에 스레드 T1이 R1을 요청한다고 가정했을때, 요청 간선 T1->R1이 할당간선 R1->T1으로 변경되어도 자원 할당 그래프에 사이클을 형성하지 않을때만 요청을 허용할 수 있다. 만약 사이클이 없다면 자원을 할당해도 시스템은 안전 상태가 된다. 사이클이 존재 한다면, 할당은 시스템을 불안전 상태로 만들게 된다. 이럴때는 T1은 자신의 요청이 충족될 때까지(사이클이 생기지 않을때까지) 반드기 대기해야한다. 아래는 불안전 상태의 자원할당 그래프이다.

은행원 알고리즘

시스템에서는 스레드가 시작할 때 스레드가 가지고 있어야 할 자원의 최대 개수를 자원 종류마다 미리 알려야 한다. 이 숫자가 자원의 총 보유 수를 넘어서면 안된다. 스레드가 자원들을 요청하면 시스템은 계속 안전 상태에 머무르게 되는지 여부를 판단해야 한다. 계속 안전하다면 그 요청을 들어주고 안전하지 않다면 이 스레드는 대기하게 된다.
(은행원 알고리즘은 앞의 자원 할당 그래프 알고리즘보다는 효율성이 떨어진다. 자원유형마다 개수를 확인 해야함으로 시간복잡도가 늘어난다.)

구현

알고리즘 구현을 위해 몇가지 자료구조가 필요하다. n은 스레드 수이고, m은 자원의 종류 수라고 하자. <= 연산은 해당 원소가 모두 작거나 같고, 두 집합이 같지 않아야 한다. (원소가 같은 것이 아닌 요청하는 두 집합이 같지 않아야함)

자료구조

• Available : 종류별로 가용한 자원의 개수를 나타내는 벡터, 크기는 m.
  Available[j] = k라면 현재 Rj를 k개 사용할 수 있다는 뜻.

• Max : 각 스레드가 최대로 필요로 하는 자원의 개수. 크기는 n*m.
  Max[i][j]=k라면 스레드 Ti가 Rj를 최대 k개 까지 요청할 수 있다는 뜻.

• Allocation : 각 스레드에 현재 할당된 자원의 개수. 크기는 n*m.
  Allocation[i][j]=k라면 스레드 Ti가 Rj를 현재 k개 사용중이다는 뜻.

• Need : 각 스레드가 향후 요청할 수 있는 자원의 개수. 크기는 n*m.
  Need[i][j] = k라면 Ti가 향후 Rj k개 까지 더 요청할 수 있다는 뜻.
  Need[i][j] = Max[i][j] - Allocation[i][j]

안전성 알고리즘

시스템이 안전한지 확인하는 알고리즘.

1. Work와 Finish는 크기가 m과 n인 벡터.
   Work = Available로 초기화, i = 0,1,...,n-1에 대해서 Finish[i] = false로 초기화.

2. 아래 조건을 만족하는 i값을 찾는다.
   a. Finish[i] == false
   b. Need[i] <= Work
   c. 두 조건을 만족하는 i값을 찾지 못하면 4번으로 이동

3. Work = Work + Allocation[i]
   Finish[i] = true;
   2번으로 이동

4. 모든 i값에 대해 Finish[i] == true이면 이 시스템은 안전 상태에 있다.

간단하게 설명하겠다.

1. 끝나지 않은 스레드 중 필요 자원들의 수가 시스템에서 가용한 자원들 수보다 적거나 같은 스레드를 찾는다.

2. 찾으면 스레드를 끝내고 현재 스레드에 할당된 모든 자원을 반환한다. 이 과정을 해당 스레드를 못 찾을때까지 반복한다.

3. 못 찾을때 마지막으로 모든 스레드들이 완료 됐는지 확인한다.

시간 복잡도는 m*n^2만큼 발생한다.

자원 요청 알고리즘

자원 요청을 들어줄 수 있는지 확인하는 알고리즘.
Request[i]는 스레드 Ti의 요청 벡터. Request[i][j] == k라면 Ti가 Rj를 4개 까지 요청한다는 뜻.

1. 만약 Request[i] <= Need[i] 이면 2번으로 간다.
   아니면 시스템에 있는 개수보다 더많이 요청했으므로 오류로 처리
   

2. 만약 Request[i] <= Available이면 3번으로 간다.
   아니면 요청한 자원이 당장은 없으므로 대기한다.

3. 마치 시스템이 Ti에게 자원을 할당해준 것처럼 시스템 상태 정보를 아래처럼 변경한다.
   Available = Available - Request[i]
   Allocation[i] = Allocation[i] + Request[i]
   Need[i] = Need[i] - Request[i]

만약 상태가 변경된 이후에도 안전하다면 Ti에 변경된 정보대로 자원을 할당한다. 안전하지 않다면, 자원 할당 상태를 원상태로 복원하고 Request[i]가 만족할때 까지 대기한다.

예시

시스템에는 다섯 개의 프로세스 T0부터 T4까지 있고, A, B, C 세가지 종류의 자원이 있다고 가정한다. A는 10개, B는 5개 C는 7개 있다고 하자.

	Allocation	Max	Available
	A B C	A B C	A B C
T0	0 1 0	7 5 3	3 3 2
T1	2 0 0	3 2 2
T2	3 0 2	9 0 2
T3	2 1 1	2 2 2
T4	0 0 2	4 3 3

Need 값은 (Max-Allocation)값으로 얻을 수 있다.

	Allocation
	A B C
T0	7 4 3
T1	1 2 2
T2	6 0 0
T3	0 1 1
T4	4 3 1

위 시스템은 안전하다. <T1, T3, T4, T2, T0> 순서로 안전성 기준을 만족 시킨다. 이제 T1이 A자원 한개와 C자원 두개를 추가로 요청한다고 하자. Request[1] = (1,0,2).

1. Request[1] <= Available 를 확인한다. (1,0,2) <= (3,3,2)인지 여부를 검사한다. 이조건이 만족되므로 상태 정보를 변경한다.

2. 변경 된 상태가 안전한지 확인한다. 안전성 알고리즘을 통해 <T1, T3, T4, T0, T2>가 만족함을 알 수 있다.

3. T1의 요청을 들어준다.

	Allocation	Need	Available
	A B C	A B C	A B C
T0	0 1 0	7 4 3	2 3 0
T1	3 0 2	0 2 0
T2	3 0 2	6 0 0
T3	2 1 1	0 1 1
T4	0 0 2	4 3 1

이후 T4가 (3,3,0) 요청을 하면 자원이 부족하기에 들어줄 수 없다.
T0가 (0,2,0) 요청을 하면 자원은 충분하지만 상태가 불안전 상태가 되므로 들어줄 수 없다.

코드

public class BankerAlgorithm {

    public int numOfThreads = 5;
    public int numOfResources = 3;

    public int[] Available = {3, 3, 2};
    public int[][] Max = {{7, 5, 3}, {3, 2, 2}, {9, 0, 2}, {2, 2, 2}, {4, 3, 3}};
    public int[][] Allocation = {{0, 1, 0}, {2, 0, 0}, {3, 0, 2}, {2, 1, 1}, {0, 0, 2}};
    public int[][] Need = {{7, 4, 3}, {1, 2, 2}, {6, 0, 0}, {0, 1, 1}, {4, 3, 1}};

    public boolean lessThan(int[] lhs, int[] rhs) {
        for (int i = 0; i < lhs.length; ++i) {
            if (lhs[i] > rhs[i])
                return false;
        }

        return true;
    }

    public void sum(int[] lhs, int[] rhs) {
        for (int i = 0; i < lhs.length; ++i) {
            lhs[i] += rhs[i];
        }
    }

    public void minus(int[] lhs, int[] rhs) {
        for (int i = 0; i < lhs.length; ++i) {
            lhs[i] -= rhs[i];
        }
    }

    public boolean isSafety() {
        // 현재 가용한 자원의 개수로 초기화
        int[] work = new int[numOfResources];
        System.arraycopy(Available, 0, work, 0, work.length);

        boolean[] finish = new boolean[numOfThreads];
        Arrays.fill(finish, false);

        for (int i = 0; i < numOfThreads; ++i) {
            for (int j = 0; j < numOfThreads; ++j) {
                if (!finish[j] && lessThan(Need[j], work)) {
                    sum(work, Allocation[j]);
                    finish[j] = true;
                }
            }
        }

        for (boolean b : finish) {
            if (!b) return false;
        }

        return true;
    }

    public boolean request(int id, int[] request) {
        if (!lessThan(request, Need[id])){
            System.out.println("너 이만큼 필요 없어 ㅎㅎ");
            return false;
        }


        if (!lessThan(request, Available)){
            System.out.println("요청한 자원이 당장 없다 다음에 가져가 ㅠ");
            return false;
        }

        minus(Available, request);
        sum(Allocation[id], request);
        minus(Need[id], request);

        if (isSafety()) {
            return true;
        } else {
            sum(Need[id], request);
            minus(Allocation[id], request);
            sum(Available, request);

            System.out.println("불안전해지잖아 ㅡㅡ");
            return false;
        }
    }
}


class BankerAlgorithmTest {
    @Test
    @DisplayName("뱅커 알고리즘 테스트")
    public void test1() {
        BankerAlgorithm bankerAlgorithm = new BankerAlgorithm();

        request(bankerAlgorithm, 1, new int[]{1, 0, 2});
        request(bankerAlgorithm, 4, new int[]{3, 3, 0});
        request(bankerAlgorithm, 0, new int[]{3, 3, 3});
        request(bankerAlgorithm, 1, new int[]{20, 20, 20});
        request(bankerAlgorithm, 0, new int[]{0, 2, 0});
    }

    private void request(BankerAlgorithm bankerAlgorithm, int id, int[] val) {
        System.out.println(bankerAlgorithm.request(id, val) ? "요청 들어줄게 ^^" : "안돼!");
        System.out.println();
    }
}