Cho hai mảng chứa kích thước khối và kích thước quy trình; nhiệm vụ là in kết quả theo thuật toán Best Fit trong quản lý bộ nhớ.
Thuật toán phù hợp nhất là gì?
Best Fit là một thuật toán quản lý bộ nhớ; nó giải quyết việc phân bổ phân vùng miễn phí nhỏ nhất đáp ứng yêu cầu của quy trình yêu cầu. Trong thuật toán này, chúng tôi tìm kiếm toàn bộ khối bộ nhớ và kiểm tra khối nhỏ nhất và thích hợp nhất cho quá trình, sau đó tìm khối gần ngay lập tức có thể được sử dụng để thực hiện quá trình đầy đủ.
Vì vậy, chúng tôi sẽ lấy kích thước khối và kích thước quy trình và trả về kết quả đầu ra của quy trình và khối nào sẽ được phân bổ cho một quy trình.
Ví dụ
Input: bsize[] = {100, 500, 200, 300, 400}
psize[] = {112, 518, 110, 526}
Output:
Process No. Process Size Block no.
1 112 3
2 518 Not Allocated
3 110 4
4 526 Not Allocated Phương pháp tiếp cận sẽ được sử dụng để giải quyết vấn đề trên -
- Nhận đầu vào của kích thước khối quảng cáo trong quy trình.
- Ban đầu, hãy đặt tất cả các khối bộ nhớ là trống.
- Thực hiện từng quy trình và tìm kích thước khối tối thiểu có thể được phân bổ cho một khối nghĩa là kích thước tối thiểu của toàn bộ khối lớn hơn kích thước quy trình.
- Nếu được tìm thấy thì hãy phân bổ nó cho quy trình hiện tại, còn lại hãy rời quy trình đó và kiểm tra quy trình tiếp theo.
Thuật toán
Start
Step 1-> In function void bestfit(int bsize[], int m, int psize[], int n)
Declare int alloc[n]
Call function memset(alloc, -1, sizeof(alloc))
Loop For i=0 and i<n and i++
Declare and Initialize bestIdx = -1
Loop For j=0 and j<m and j++
If bsize[j] >= psize[i] then,
If bestIdx == -1 then,
Set bestIdx = j
Else If bsize[bestIdx] > bsize[j] then,
Set bestIdx = j
If bestIdx != -1 then,
Set alloc[i] = bestIdx
Set bsize[bestIdx] -= psize[i]
Loop For i = 0 and i < n and i++
Print i+1, psize[i]
If alloc[i] != -1
Print alloc[i] + 1
Else
Print "Not Allocated"
Print newline
Step 2->In function int main()
Declare and initialize bsize[] = {100, 500, 200, 300, 400}
Declare and initialize psize[] = {112, 518, 110, 526}
Set m = sizeof(bsize)/sizeof(bsize[0])
Set n = sizeof(psize)/sizeof(psize[0])
Call function bestfit(bsize, m, psize, n)
Stop Ví dụ
#include <iostream>
#include <memory>
using namespace std;
// To allocate the memory to blocks as per Best fit
// algorithm
void bestfit(int bsize[], int m, int psize[], int n) {
// To store block id of the block allocated to a
// process
int alloc[n];
// Initially no block is assigned to any process
memset(alloc, -1, sizeof(alloc));
// pick each process and find suitable blocks
// according to its size ad assign to it
for (int i=0; i<n; i++) {
// Find the best fit block for current process
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 we could find a block for current process
if (bestIdx != -1) {
// allocate block j to p[i] process
alloc[i] = bestIdx;
// Reduce available memory in this block.
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;
}
}
// Driver code
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 ;
} Đầu ra
Process No. Process Size Block no. 1 112 3 2 518 Not Allocated 3 110 4 4 526 Not Allocated