n개의 프로세스와 각기 다른 크기의 m개 메모리 블록이 주어졌을 때, First Fit(최초 적합) 메모리 관리 알고리즘을 이용해 각 프로세스에 적합한 메모리 블록을 찾아 할당하는 것이 이 프로그램의 목표입니다.
First Fit 메모리 관리 알고리즘이란?
운영체제는 프로세스에 메모리 블록을 할당할 때 여러 가지 메모리 분할 알고리즘을 사용합니다.
- First Fit Algorithm (최초 적합)
- Next Fit Algorithm (다음 적합)
- Best Fit Algorithm (최적 적합)
- Worst Fit Algorithm (최악 적합)
- Quick Fit Algorithm (퀵 적합)
First Fit 알고리즘은 이 가운데 가장 단순한 메모리 할당 기법입니다. 포인터가 메모리 내 모든 빈 블록을 추적하다가 새 프로세스의 할당 요청을 받으면, 메모리의 처음부터 차례대로 블록을 검색합니다. 그리고 프로세스 크기보다 크거나 같은 첫 번째 빈 블록을 발견하는 즉시 그 블록을 프로세스에 할당합니다. 이때 블록은 두 개의 파티션으로 나뉘는데, 하나는 남은 빈 공간(홀, hole)이 되고 다른 하나에는 프로세스가 저장됩니다.
장점: 조건에 맞는 첫 번째 블록을 찾자마자 바로 할당하기 때문에 다른 알고리즘에 비해 할당 속도가 가장 빠릅니다.
단점: 블록 뒤쪽에 잘 쓰이지 않는 작은 빈 공간(단편화)이 계속 남아 메모리가 낭비될 수 있으며, 이로 인해 다른 프로세스에 필요한 메모리가 부족해질 수 있습니다.
예제 입력과 출력
입력 -: block_size[] = {300, 50, 200, 350, 70}
process_size[] = {200, 47, 212, 426, 10}
출력 -:
Process No. Process Size Block no.
1 200 1
2 47 1
3 212 4
4 426 Not Allocated
5 10 1실행 결과를 보면 3번 프로세스(212)는 앞선 두 블록에 더 이상 공간이 없어 4번 블록(350)에 할당되었고, 4번 프로세스(426)는 어떤 블록으로도 수용할 수 없어 할당되지 않았습니다.
프로그램의 접근 방식
- 블록과 프로세스 정보를 배열로 입력받습니다.
- 모든 메모리 블록을 '비어 있음' 상태로 초기화합니다.
- (프로세스 크기) ≤ (메모리 블록 크기)라면 해당 프로세스를 그 블록에 할당합니다.
- 조건을 만족하지 않으면 만족하는 블록을 찾을 때까지 다음 블록을 계속 탐색합니다.
알고리즘
시작
Step 1-> 최초 적합 메모리 블록을 계산하는 함수 선언
void First_Fit(int block_size[], int total_blocks, int process_size[], int total_process)
int allocation[total_process] 선언
memset(allocation, -1, sizeof(allocation)) 호출
반복문 i = 0; i < total_process; i++
반복문 j = 0; j < total_blocks; j++
IF block_size[j] >= process_size[i]
allocation[i] = j
block_size[j] -= process_size[i]
End
End
End
반복문 i = 0; i < total_process; i++
IF allocation[i] != -1
allocation[i] + 1 출력
Else
"Not Allocated" 출력
End
End
Step 2-> main() 함수 안에서
블록 배열 선언: int block_size[] = {300, 50, 200, 350, 70}
프로세스 배열 선언: int process_size[] = {200, 47, 212, 426, 10}
전체 블록 수 계산: int total_blocks = sizeof(block_size) / sizeof(block_size[0])
전체 프로세스 수 계산: int total_process = sizeof(process_size) / sizeof(process_size[0])
First_Fit(block_size, total_blocks, process_size, total_process) 호출
종료C++ 구현 예제
#include<bits/stdc++.h>
using namespace std;
// First Fit 알고리즘에 따라 블록에 메모리를 할당하는 함수
void First_Fit(int block_size[], int total_blocks, int process_size[], int total_process) {
int allocation[total_process];
memset(allocation, -1, sizeof(allocation));
// 이 반복문은 각 프로세스를 순서대로 살펴보며 최초로 적합한 블록을 할당합니다
for (int i = 0; i < total_process; i++) {
for (int j = 0; j < total_blocks; j++) {
if (block_size[j] >= process_size[i]) {
allocation[i] = j;
block_size[j] -= process_size[i];
break;
}
}
}
cout << "\nProcess No.\tProcess Size\tBlock no.\n";
for (int i = 0; i < total_process; i++) {
cout << " " << i+1 << "\t\t" << process_size[i] << "\t\t";
if (allocation[i] != -1)
cout << allocation[i] + 1;
else
cout << "Not Allocated";
cout << endl;
}
}
int main() {
// 블록 크기를 저장할 배열 생성
int block_size[] = {300, 50, 200, 350, 70};
// 프로세스 크기를 저장할 배열 생성
int process_size[] = {200, 47, 212, 426, 10};
// 전체 블록 수를 담는 변수
int total_blocks = sizeof(block_size) / sizeof(block_size[0]);
// 전체 프로세스 수를 담는 변수
int total_process = sizeof(process_size) / sizeof(process_size[0]);
// First_Fit 함수 호출
First_Fit(block_size, total_blocks, process_size, total_process);
return 0;
}실행 결과
Process No. Process Size Block no. 1 200 1 2 47 1 3 212 4 4 426 Not Allocated 5 10 1