รับสองอาร์เรย์ที่มีขนาดบล็อกและขนาดกระบวนการ งานคือการพิมพ์ผลลัพธ์ตามอัลกอริธึม Best Fit ในการจัดการหน่วยความจำ
อัลกอริทึมแบบพอดีที่ดีที่สุดคืออะไร
Best Fit คืออัลกอริธึมการจัดการหน่วยความจำ มันเกี่ยวข้องกับการจัดสรรพาร์ติชั่นว่างที่เล็กที่สุดซึ่งตรงตามข้อกำหนดของกระบวนการที่ร้องขอ ในอัลกอริธึมนี้ เราจะมองหาบล็อกหน่วยความจำทั้งหมด และตรวจสอบบล็อกที่เล็กที่สุดและเหมาะสมที่สุดสำหรับกระบวนการ จากนั้นมองหาบล็อกที่ใกล้เคียงในทันที ซึ่งสามารถใช้เพื่อทำให้กระบวนการสมบูรณ์ได้
ดังนั้น เราจะใช้ขนาดบล็อกและขนาดกระบวนการ และส่งคืนผลลัพธ์ของกระบวนการ และบล็อกใดที่จะจัดสรรให้กับกระบวนการ
ตัวอย่าง
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 วิธีการจะใช้ในการแก้ปัญหาข้างต้น -
- รับอินพุตของขนาดบล็อกโฆษณาของกระบวนการ
- เริ่มตั้งค่าบล็อคหน่วยความจำทั้งหมดให้ว่าง
- ใช้แต่ละกระบวนการและค้นหาขนาดบล็อกขั้นต่ำที่สามารถจัดสรรให้กับบล็อกได้ หมายถึงขั้นต่ำของบล็อกทั้งหมดซึ่งมากกว่าขนาดกระบวนการ
- หากพบแล้ว ให้จัดสรรให้กับกระบวนการปัจจุบัน มิฉะนั้น ให้ออกจากกระบวนการนั้นและตรวจสอบกระบวนการต่อไป
อัลกอริทึม
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 ตัวอย่าง
#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 ;
} ผลลัพธ์
Process No. Process Size Block no. 1 112 3 2 518 Not Allocated 3 110 4 4 526 Not Allocated
