Banker’s Algorithm

Operating System Concepts (9th Edition)에 등장하는 Deadlock Avoidance를 위한 Banker’s Algorithm(Safety Algorithm) 이다.
코드는 다음과 같다.

#define TRUE 1
#define FALSE 0
#define PROCESS_NUM 5
#define RESOURCE_TYPE 4
#define GRANTED 1
#define NOT_GRANTED 0
typedef struct {
    int available[RESOURCE_TYPE];
    int max[PROCESS_NUM][RESOURCE_TYPE];
    int allocation[PROCESS_NUM][RESOURCE_TYPE];
    int need[PROCESS_NUM][RESOURCE_TYPE];
    int work[RESOURCE_TYPE];
    int finish[PROCESS_NUM];
    int request[PROCESS_NUM][RESOURCE_TYPE];
    int total_request[PROCESS_NUM];
    int request_flag[PROCESS_NUM];
    int system_flag;
} Banker;

int safetyAlgorithm(Banker *b) {
    int i, j;
    int chk_work;
    int chk_process = 0;

    for (i = 0; i < RESOURCE_TYPE; i++) {
        b->work[i] = b->available[i];
    }

    for (i = 0; i < PROCESS_NUM; i++) {
        b->finish[i] = FALSE;
    }

    for (i = 0; i < (PROCESS_NUM * PROCESS_NUM); i++) {
        chk_work = 0;
        for (j = 0; j < RESOURCE_TYPE; j++) {
            if ((b->finish[i % PROCESS_NUM] == FALSE) && (b->need[i % PROCESS_NUM][j] <= b->work[j]))
                chk_work++;
        }
        if (chk_work == RESOURCE_TYPE) {
            for (j = 0; j < RESOURCE_TYPE; j++) {
                b->work[j] += b->allocation[i % PROCESS_NUM][j];
            }
            b->finish[i % PROCESS_NUM] = TRUE;
        }
    }

    for (i = 0; i < PROCESS_NUM; i++) {
        if (b->finish[i] == TRUE) {
            chk_process++;
        }
    }

    if (chk_process == PROCESS_NUM) {
        return TRUE;
    } else {
        return FALSE;
    }
}

int ralloc(Banker *b, int i) {
    int j;
    int req_flag, avail_flag;
    int safe_state;
    req_flag = FALSE;
    avail_flag = FALSE;

    for (j = 0; j < RESOURCE_TYPE; j++) {
        if (b->request[i][j] <= b->need[i][j]) {
            req_flag = TRUE;
        } else {
            req_flag = FALSE;
        }
    }

    if (req_flag == TRUE) {
        for (j = 0; j < RESOURCE_TYPE; j++) {
            if (b->request[i][j] <= b->available[j]) {
                avail_flag = TRUE;
            } else {
                avail_flag = FALSE;
            }
        }
    } else {
        b->request_flag[i] = NOT_GRANTED;
        return FALSE;
    }

    if (avail_flag == TRUE) {
        for (j = 0; j < RESOURCE_TYPE; j++) {
            b->available[j] -= b->request[i][j];
            b->allocation[i][j] += b->request[i][j];
            b->need[i][j] -= b->request[i][j];
        }

        safe_state = safetyAlgorithm(b);
        if (safe_state == TRUE) {
            b->request_flag[i] = GRANTED;
            b->system_flag = TRUE;
            return TRUE;
        } else {
            b->request_flag[i] = NOT_GRANTED;
            b->system_flag = TRUE;
            for (j = 0; j < RESOURCE_TYPE; j++) {
                b->available[j] += b->request[i][j];
                b->allocation[i][j] -= b->request[i][j];
                b->need[i][j] += b->request[i][j];
            }
            return FALSE;
        }
    } else {
        b->request_flag[i] = NOT_GRANTED;
        b->system_flag = TRUE;
        return FALSE;
    }
}

메인함수에서의 호출은 다음과 같다.
ralloc(p, i);
메인함수에서 ralloc함수를 호출한다.
(물론 그 전에 각자의 방법으로 resource들을 가지고 있어야 한다.
구조체에 request 2차원 배열을 통해 프로세스별 request를 기록하는 방식을 사용했다.)
그러면 ralloc 함수에서 조건 검사를 모두 통과하게 되면, 임시적으로 request를 할당을 한다.
그런 다음, safetyAlgorithm을 호출하여, 이 request를 받아서 grant를 해 주어도 되는지를 판단하는 로직이다.
safety algorithm은 Process의 수를 n, Resource의 수를 m이라 할 때, loop를 n^2 * m 만큼 수행하게 된다.  (이것이 핵심.)
따라서 safety algorithm의 time complexity는 O(n^2*m) 이 된다.
여기에서 n의 제곱만큼을 수행하지 않고, n 만큼 수행하게 되는 경우에 원하는 결과값이 절대 나오지 않는다.
safety algorithm을 수행하고 결과값이 true로 return 될 경우에는 임시적으로 할당한 것을 그대로 grant해준다.
만약 false가 return 될 경우에는 임시적으로 할당한 request를 모두 지워주어야만 한다.

댓글 남기기