Banker's Algorithm 구현

1. Banker's Algorithm의 등장배경

• Program에서 자원 할당 시 Deadlock 상태의 발생을 피하고자 safety or unsafety 상태인지를 확인하는 알고리즘이 필요하다.

2. 소스 코드

#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;

typedef struct inform {
	int* allocation; // 할당된 자원
	int* max; // 최대 필요 자원
	int* need; // 필요 자원
}inform;

int p_num; // 프로세스 개수
int rtype_num; // 리소스 타입 개수
inform* process; // 프로세스 배열
int* available; // 이용 가능한 리소스 저장 배열 
int* total; //전체 자원 저장
int* order; // 프로세스 실행 순서

void Input();
void Output();
void Bankers();
void Exec(int idx);

int main(void) {
	Input(); // 입력
	Output(); // 초기 정보 출력

	// 프로세스 진행순서 입력
	while (1) {
		cout << endl << endl << "프로세스 진행 순서 입력: ";
		bool flag = true;
		for (int i = 0; i < p_num; i++) {
			cin >> order[i];
		}

		// 예외처리 5 - 범위 이외의 프로세스 번호 입력 or 중복된 번호 입력
		for (int i = 0; i < p_num; i++) {
			if (order[i] < 0 || order[i] >= p_num) {
				flag = false;
				break;
			}
		}
			
		if (!flag)cout << "프로세스 번호 입력이 잘못되었습니다! 다시입력하세요!" << endl;
		else break;
	}

	// banker's 알고리즘 진행
	Bankers();

	// 메모리 해제
	delete[] available;
	delete[] total;
	delete[] order;
	for (int i = 0; i < p_num; i++) {
		delete[] process[i].allocation;
		delete[] process[i].max;
		delete[] process[i].need;
	}
	delete[] process;

	system("pause");
	return 0;
}

void Input() {

	// Process, Resource Type 개수 입력받기
	while (1) {
		cout << "프로세스 개수 입력: ";
		cin >> p_num;
		cout << "리소스 타입 개수 입력: ";
		cin >> rtype_num;
		// 예외처리1 - 음수값 입력
		if (p_num > -1 && rtype_num > -1)
			break;
		cout << "음수값 입력! 다시입력하세요!" << endl;
	}

	// Process, available 배열 동적할당
	available = new int[rtype_num];
	total = new int[rtype_num];
	process = new inform[p_num];
	order = new int[p_num];
	for (int i = 0; i < p_num; i++) {
		process[i].allocation = new int[rtype_num];
		process[i].max = new int[rtype_num];
		process[i].need = new int[rtype_num];
	}

	// Resource Type별 개수 입력
	cout << endl << "===== Resource Type별 자원의 개수 입력 =====" << endl;
	for (int i = 0; i < rtype_num; i++) {
		// 예외처리2 - 음수값 입력
		while (1) {
			printf("resource %c: ", 65 + i);
			cin >> total[i];
			if (total[i] > -1)
				break;
			cout << "음수값 입력! 다시 입력하세요!" << endl;
		}
		available[i] = total[i]; // available에 total값 복사해둠
	}

	// Process별 Allocation입력
	cout << endl << "===== Process별 Allocation 정보 입력 =====" << endl;
	for (int i = 0; i < p_num; i++) {
		while (1) {
			bool flag = true;
			cout << "process[" << i << "] allocation 입력: ";
			for (int j = 0; j < rtype_num; j++) {
				cin >> process[i].allocation[j];
				available[j] -= process[i].allocation[j]; // available 값 계산 (전체자원 개수 - 할당된 자원 수)
				// 예외처리3 - 자원 초과할당 or 음수값 입력
				if (available[j] < 0 || process[i].allocation[j] < 0) flag = false;
			}
			if (!flag) {
				cout << "음수값이 입력되었거나 자원이 초과할당되었습니다! 다시입력하세요!" << endl;
				for (int k = 0; k < rtype_num; k++)
					available[k] += process[i].allocation[k];
			}
			else break;
		}
	}
	
	// Process별 Max 입력
	cout << endl << "===== Process별 Max의 정보 입력 =====" << endl;
	for (int i = 0; i < p_num; i++) {
		while (1) {
			bool flag = true;
			cout << "process[" << i << "] Max  입력: ";
			for (int j = 0; j < rtype_num; j++) {
				cin >> process[i].max[j];
				process[i].need[j] = process[i].max[j] - process[i].allocation[j]; // need 값 계산(max-allocation)
			}
			// 예외처리4 - 음수값 입력 
			for (int j = 0; j < rtype_num; j++) {
				if (process[i].max[j] < 0) {
					flag = false;
					break;
				}
			}
			if (!flag) cout << "음수값 입력! 다시 입력하세요!" << endl;
			else break;
		}
	}
}

void Output() {
	cout << endl << endl << "=============== 초기 정보 출력 ===============" << endl;
	printf(" -------------------------------------------------------------------------------------------------------------\n");
	printf("%s %s %s %s %s \n", " Process |", "      Allocation       |", "          Max          |", "         Need          |", "       Available       ");
	printf(" -------------------------------------------------------------------------------------------------------------");
	
	int blank;
	for (int i = 0; i < p_num; i++) {
		if (i != 0) 
			printf("\n -------------------------------------------------------------------------------------------------------------");
		
		printf("\n %s%d%s", " P[", i, "]   ");
		// allocation, max, need, available 출력
		for (int a = 0; a < 3; a++) {
			printf("| ");
			blank = 0;
			int value;
			for (int j = 0; j < rtype_num; j++) {
				switch (a) {
				case 0: value = process[i].allocation[j]; break;
				case 1: value = process[i].max[j]; break;
				case 2: value = process[i].need[j]; break;
				}
				printf("%d ", value);
				if (value > 10)
					blank += 3;
				else
					blank += 2;
			}

			// 남은 공백 출력
			blank = 23 - blank;
			for (int i = 0; i < blank; i++)
				printf(" ");
		}
		printf("| ");

		// 첫번째 줄에는 available 도 출력
		if (i == 0)
			for (int j = 0; j < rtype_num; j++)
				printf("%d ", available[j]);
	}
	printf("\n -------------------------------------------------------------------------------------------------------------");
}

void Bankers() {
	int i, j;
	bool flag;

	cout << endl << "초기 Available :  ";
	for (int i = 0; i < rtype_num; i++)
		cout << available[i] << "  ";
	cout << endl;

	for (i = 0; i < p_num; i++) {
		// 현재 프로세스 진행 가능한지 검사
		flag = true;
		for (j = 0; j < rtype_num; j++) {
			if (process[order[i]].need[j] > available[j]) {
				flag = false;
				break;
			}
		}
		// 진행 가능하면 프로세스 처리
		if (flag) 
			Exec(order[i]);
		// 불가능하면 종료
		else { 
			cout << endl << "P[" << order[i] << "]에서 부터 진행 불가능!";
			cout << endl << endl << "Unsafe State!" << endl;
			return; 
		}
	}
	cout << endl << "Safe State!" << endl;
	return;
}

// idx 프로세스를 실행
void Exec(int idx) {
	for (int i = 0; i < rtype_num; i++) {
		// 현재 실행한 프로세스에 할당된 자원 release
		available[i] += process[idx].allocation[i]; 
		process[idx].allocation[i] = 0;
	}
	cout << "P[" << idx << "] 처리후    :  ";
	for (int i = 0; i < rtype_num; i++)
		cout << available[i] << "  ";
	cout << endl;
}

 

3. 결과 화면

Safe State

 

Unsafe State

 

 

4. 첨부 파일 (실행파일, 소스코드, 보고서)

Banker's Algorithm.zip

0.37MB