โปรแกรม C++ สำหรับอัลกอริทึม Best Fit ในการจัดการหน่วยความจำ

ภาพรวมของอัลกอริทึม 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= 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

ตัวอย่างโค้ด C++

#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 and 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