블록 크기(block size)와 프로세스 크기(process size)를 담고 있는 두 개의 배열이 주어졌을 때, 메모리 관리의 최적 적합(Best Fit) 알고리즘에 따라 결과를 출력하는 것이 이 글의 목표입니다.
최적 적합(Best Fit) 알고리즘이란?
최적 적합 알고리즘은 메모리 관리 기법 중 하나로, 요청한 프로세스의 요구 사항을 충족할 수 있는 가장 작은 여유 파티션을 할당하는 방식입니다. 이 알고리즘에서는 전체 메모리 블록을 모두 살펴본 뒤, 프로세스에 가장 적합한 가장 작은 블록을 찾아 할당합니다.
즉, 블록 크기 배열과 프로세스 크기 배열을 입력으로 받아, 각 프로세스에 어떤 블록이 할당되었는지(또는 할당되지 않았는지) 그 결과를 출력하게 됩니다.
예시
입력: bsize[] = {100, 500, 200, 300, 400}
psize[] = {112, 518, 110, 526}
출력:
프로세스 번호 프로세스 크기 블록 번호
1 112 3
2 518 Not Allocated
3 110 4
4 526 Not Allocated문제 해결 접근 방식
- 프로세스 크기와 블록 크기를 입력받습니다.
- 처음에는 모든 메모리 블록을 여유(free) 상태로 설정합니다.
- 각 프로세스를 하나씩 확인하면서, 해당 프로세스보다 크거나 같은 블록들 중 크기가 가장 작은 블록(즉, 가장 적합한 블록)을 찾습니다.
- 적합한 블록을 찾으면 현재 프로세스에 할당하고, 찾지 못하면 해당 프로세스는 건너뛴 뒤 다음 프로세스를 확인합니다.
알고리즘
시작
단계 1 -> void bestfit(int bsize[], int m, int psize[], int n) 함수
int alloc[n] 선언
memset(alloc, -1, sizeof(alloc)) 호출
i = 0; i < n; i++ 반복
bestIdx = -1 로 선언 및 초기화
j = 0; j < m; j++ 반복
만약 bsize[j] >= psize[i] 라면,
만약 bestIdx == -1 이라면,
bestIdx = j
아니고 bsize[bestIdx] > bsize[j] 라면,
bestIdx = j
만약 bestIdx != -1 이라면,
alloc[i] = bestIdx
bsize[bestIdx] -= psize[i]
i = 0; i < n; i++ 반복
i+1 과 psize[i] 출력
만약 alloc[i] != -1 이면
alloc[i] + 1 출력
아니면
"Not Allocated" 출력
줄바꿈 출력
단계 2 -> int main() 함수
bsize[] = {100, 500, 200, 300, 400} 선언 및 초기화
psize[] = {112, 518, 110, 526} 선언 및 초기화
m = sizeof(bsize)/sizeof(bsize[0])
n = sizeof(psize)/sizeof(psize[0])
bestfit(bsize, m, psize, n) 호출
종료C++ 구현 코드
#include <iostream>
#include <memory>
using namespace std;
// 최적 적합(Best Fit) 알고리즘에 따라 블록에 메모리를 할당하는 함수
void bestfit(int bsize[], int m, int psize[], int n) {
// 프로세스에 할당된 블록의 ID를 저장하기 위한 배열
int alloc[n];
// 처음에는 어떤 블록도 프로세스에 할당되어 있지 않음
memset(alloc, -1, sizeof(alloc));
// 각 프로세스를 선택하고 크기에 맞는 블록을 찾아 할당
for (int i=0; i<n; i++) {
// 현재 프로세스에 대한 최적 블록 탐색
int bestIdx = -1;
for (int j=0; j<m; j++) {
if (bsize[j] >= psize[i]) {
if (bestIdx == -1)
bestIdx = j;
else if (bsize[bestIdx] > bsize[j])
bestIdx = j;
}
}
// 현재 프로세스에 적합한 블록을 찾은 경우
if (bestIdx != -1) {
// 블록 j를 프로세스 p[i]에 할당
alloc[i] = bestIdx;
// 해당 블록의 남은 메모리 크기 감소
bsize[bestIdx] -= psize[i];
}
}
cout << "\nProcess No.\tProcess Size\tBlock no.\n";
for (int i = 0; i < n; i++) {
cout << " " << i+1 << "\t\t\t\t" << psize[i] << "\t\t\t\t";
if (alloc[i] != -1)
cout << alloc[i] + 1;
else
cout << "Not Allocated";
cout << endl;
}
}
// 드라이버 코드
int main() {
int bsize[] = {100, 500, 200, 300, 400};
int psize[] = {112, 518, 110, 526};
int m = sizeof(bsize)/sizeof(bsize[0]);
int n = sizeof(psize)/sizeof(psize[0]);
bestfit(bsize, m, psize, n);
return 0 ;
}실행 결과
Process No. Process Size Block no. 1 112 3 2 518 Not Allocated 3 110 4 4 526 Not Allocated
위 실행 결과를 보면, 크기가 112인 프로세스는 300 크기의 블록(3번)에, 크기가 110인 프로세스는 200 크기의 블록(4번)에 할당된 것을 확인할 수 있습니다. 반면 518과 526 크기의 프로세스는 어떤 블록에도 들어갈 수 없어 할당되지 않았습니다. 이처럼 최적 적합 알고리즘은 요구 크기를 만족하는 블록 중 가장 작은 것을 선택함으로써 메모리 낭비를 최소화하려는 전략을 사용합니다.