Được đưa ra với số quy trình n và kích thước m của khối bộ nhớ và nhiệm vụ là tìm khối bộ nhớ phù hợp nhất cho quy trình tương ứng bằng cách sử dụng thuật toán quản lý bộ nhớ phù hợp đầu tiên.
Thuật toán quản lý bộ nhớ First Fit là gì?
Có nhiều thuật toán phân vùng bộ nhớ có sẵn được hệ điều hành sử dụng để phân bổ các khối bộ nhớ cho các quá trình như -
- Thuật toán First Fit
- Thuật toán Fit tiếp theo
- Thuật toán phù hợp nhất
- Thuật toán phù hợp tồi tệ nhất
- Thuật toán Quick Fit
Thuật toán First Fit là kỹ thuật đơn giản nhất để phân bổ khối bộ nhớ cho tất cả các quá trình. Trong thuật toán này, con trỏ theo dõi tất cả các khối trống trong bộ nhớ và chấp nhận yêu cầu cấp phát khối bộ nhớ cho tiến trình sắp tới. Sau khi con trỏ đó bắt đầu tìm kiếm khối trống đầu tiên lớn nhất cho tiến trình và cấp phát khối bộ nhớ đó cho tiến trình sắp tới. Trong đó, hai phân vùng được tạo ra, một phân vùng dành cho lỗ hổng và phân vùng sẽ lưu trữ các quy trình.
Lợi thế sử dụng Thuật toán First Fit là cấp phát bộ nhớ nhanh nhất cho các quy trình sắp tới vì nó phân bổ thuật toán phù hợp đầu tiên lớn nhất cho các quy trình mới.
Bất lợi khi sử dụng Thuật toán First Fit là sự lãng phí bộ nhớ sẽ dẫn đến việc thiếu bộ nhớ cho các quá trình khác.
Ví dụ
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 Phương pháp tiếp cận được sử dụng trong chương trình sau như sau -
- Nhập các khối và các quy trình trong một mảng
- Đặt tất cả các khối bộ nhớ thành trống
- Kiểm tra xem (kích thước của một quy trình) <=(kích thước của một khối bộ nhớ) sau đó cấp phát quy trình cho một khối bộ nhớ
- Khác tiếp tục duyệt qua các khối khác cho đến khi (kích thước của một quy trình) <=(kích thước của một khối bộ nhớ) không đúng.
Thuật toán
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 Ví dụ
#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 ;
} Đầu ra
Process No. Process Size Block no. 1 200 1 2 47 1 3 212 4 4 426 Not Allocated 5 10 1