Cho hai mảng chứa kích thước khối và kích thước tiến 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 Best Fit là gì?
Best Fit là thuật toán quản lý bộ nhớ; nó xử lý việc cấp phát phân vùng trống nhỏ nhất đáp ứng yêu cầu của tiến trình đang yêu cầu. Trong thuật toán này, chúng ta tìm kiếm toàn bộ khối bộ nhớ và kiểm tra khối nhỏ nhất và phù hợp nhất cho tiến trình, sau đó tìm khối gần nhất có thể dùng để đáp ứng tiến trình đầy đủ.
Vì vậy, chúng ta sẽ lấy kích thước khối và kích thước tiến trình, rồi trả về đầu ra của tiến trình và khối nào được cấp phát cho tiến 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 giải quyết bài toán trên:
- Nhập kích thước tiến trình và khối.
- Ban đầu đặt tất cả các khối bộ nhớ là trống.
- Lấy từng tiến trình và tìm kích thước khối nhỏ nhất có thể cấp phát, nghĩa là nhỏ nhất trong số các khối lớn hơn kích thước tiến trình.
- Nếu tìm thấy thì cấp phát cho tiến trình hiện tại, nếu không thì bỏ qua tiến trình đó và kiểm tra tiến 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ụ mã nguồn
#include <iostream> #include <memory> using namespace std; // Cấp phát bộ nhớ cho các khối theo thuật toán Best fit void bestfit(int bsize[], int m, int psize[], int n) { // Lưu ID khối được cấp phát cho một tiến trình int alloc[n]; // Ban đầu không khối nào được gán cho tiến trình nào memset(alloc, -1, sizeof(alloc)); // Duyệt từng tiến trình và tìm khối phù hợp // theo kích thước và gán cho nó for (int i=0; i<n; i++) { // Tìm khối best fit cho tiến trình hiện tạ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; } } // Nếu tìm thấy khối cho tiến trình hiện tại if (bestIdx != -1) { // cấp phát khối j cho tiến trình p[i] alloc[i] = bestIdx; // Giảm bộ nhớ khả dụng trong khối này. 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 ; } Kết quả
Process No. Process Size Block no. 1 112 3 2 518 Not Allocated 3 110 4 4 526 Not Allocated