n개의 프로세스와 m개의 메모리 블록 크기가 주어지면 첫 번째 적합 메모리 관리 알고리즘을 사용하여 해당 프로세스에 가장 적합한 메모리 블록을 찾는 작업입니다.
First Fit 메모리 관리 알고리즘이란 무엇입니까?
운영 체제에서 다음과 같은 프로세스에 메모리 블록을 할당하는 데 사용하는 여러 메모리 분할 알고리즘이 있습니다.
- 첫 번째 맞춤 알고리즘
- 다음 맞춤 알고리즘
- 최적 맞춤 알고리즘
- 최악 맞춤 알고리즘
- 빠른 맞춤 알고리즘
First Fit Algorithm은 메모리 블록을 모든 프로세스에 할당하는 가장 간단한 기술입니다. 이 알고리즘에서 포인터는 메모리의 모든 여유 블록을 추적하고 메모리 블록을 다음 프로세스에 할당하라는 요청을 수락합니다. 그 포인터가 프로세스에 대해 가장 큰 첫 번째 여유 블록을 검색하기 시작한 후 해당 메모리 블록을 다음 프로세스에 할당합니다. 여기에서 두 개의 파티션이 만들어집니다. 하나는 구멍을 위한 것이고 다른 하나는 프로세스를 저장할 것입니다.
장점 First Fit Algorithm을 사용하는 비율은 새로운 프로세스에 가장 큰 First Fit 알고리즘을 할당하므로 다가오는 프로세스에 가장 빠른 메모리 할당입니다.
단점 First Fit Algorithm을 사용하는 것은 다른 프로세스에 대한 메모리 부족으로 이어지는 메모리 낭비입니다.
예시
Input-: block_size[] = {300, 50, 200, 350, 70}
process_size[] = {200, 47, 212, 426, 10}
Output-:
Process No. Process Size Block no.
1 200 1
2 47 1
3 212 4
4 426 Not Allocated
5 10 1 다음 프로그램에서 사용되는 접근 방식은 다음과 같습니다. -
- 블록과 프로세스를 배열로 입력
- 모든 메모리 블록을 해제로 설정
- (프로세스의 크기) <=(메모리 블록의 크기)인지 확인한 후 프로세스를 메모리 블록에 할당
- 그렇지 않으면 (프로세스 크기) <=(메모리 블록 크기)가 참이 아닐 때까지 다른 블록을 계속 탐색합니다.
알고리즘
Start
Step 1-> declare function to calculate the best fit memory block
void First_Fit(int block_size[], int total_blocks, int process_size[], int total_process)
Declare int allocation[total_process]
Call function memset(allocation, -1, sizeof(allocation))
Loop For i = 0 and i < total_process and i++
Loop for j = 0 and j < total_blocks and j++
IF block_size[j] >= process_size[i]
Set allocation[i] = j
Set block_size[j] -= process_size[i]
End
End
End
Loop For i = 0 and i < total_process and i++
IF allocation[i] != -1
Set allocation[i] + 1
End
Else
Print Not Allocated
End
End
Step 2-> In main()
Declare an array for blocks as int block_size[] = {300, 50, 200, 350, 70}
Declare an array for processes int process_size[] = {200, 47, 212, 426, 10}
Calculate total blocks int total_blocks = sizeof(block_size) / sizeof(block_size[0]
Calculate total processes int total_process = sizeof(process_size) / sizeof(process_size[0])
Call First_Fit(block_size, total_blocks, process_size, total_process)
Stop 예시
#include<bits/stdc++.h>
using namespace std;
// Function to allocate memory to
// blocks as per First fit algorithm
void First_Fit(int block_size[], int total_blocks, int process_size[], int total_process) {
int allocation[total_process];
memset(allocation, -1, sizeof(allocation));
//this for loop wll pick eact process and allocate a first fit block to it
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() {
//create array to store block sizes
int block_size[] = {300, 50, 200, 350, 70};
//create array to store process sizes
int process_size[] = {200, 47, 212, 426, 10};
//variable total_blocks that contain total number of blocks
int total_blocks = sizeof(block_size) / sizeof(block_size[0]);
//variable total_process that contain total number of blocks
int total_process = sizeof(process_size) / sizeof(process_size[0]);
//calling the function 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