【C++】メモリ管理におけるベストフィット（最適適合）アルゴリズムの実装プログラム

ブロックサイズとプロセスサイズを格納した2つの配列が与えられたとき、メモリ管理における「ベストフィット（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-> 関数 void bestfit(int bsize[], int m, int psize[], int n)
    int alloc[n] を宣言
    memset(alloc, -1, sizeof(alloc)) を呼び出す
    繰り返し For i=0; i= psize[i] ならば
                もし bestIdx == -1 ならば
                    bestIdx = j とする
                そうでなく bsize[bestIdx] > bsize[j] ならば
                    bestIdx = j とする
        もし bestIdx != -1 ならば
            alloc[i] = bestIdx とする
            bsize[bestIdx] -= psize[i] とする
    繰り返し For i=0; i 関数 int main()
    bsize[] = {100, 500, 200, 300, 400} を宣言・初期化
    psize[] = {112, 518, 110, 526} を宣言・初期化
    m = sizeof(bsize)/sizeof(bsize[0]) とする
    n = sizeof(psize)/sizeof(psize[0]) とする
    bestfit(bsize, m, psize, n) を呼び出す
Stop

C++による実装例

#include <iostream>
#include <memory>
using namespace std;

// ベストフィットアルゴリズムに従ってメモリをブロックへ割り当てる
void bestfit(int bsize[], int m, int psize[], int n) {
    // 各プロセスに割り当てられたブロック番号を格納する配列
    int alloc[n];
    // 初期状態では、どのプロセスにもブロックを割り当てない
    memset(alloc, -1, sizeof(alloc));
    // 各プロセスを取り上げ、サイズに応じた適切なブロックを探して割り当てる
    for (int i = 0; i < n; 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;
            }
        }
        // 現在のプロセスに割り当てられるブロックが見つかった場合
        if (bestIdx != -1) {
            // ブロックjをプロセスp[i]に割り当てる
            alloc[i] = bestIdx;
            // このブロックの残りメモリを減らす
            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;
    }
}

// ドライバーコード
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

出力の解説と補足

この実行結果から、プロセス1（サイズ112）は要求サイズに最も近いブロック3（200）へ、プロセス3（サイズ110）はブロック4（300）へ割り当てられていることがわかります。一方、プロセス2（518）とプロセス4（526）は、どの空きブロックのサイズよりも大きいため「Not Allocated（未割り当て）」となっています。

計算量は、プロセス数をn、ブロック数をmとすると O(n × m) です。また、類似の手法には「ファーストフィット（最初に見つかった空きブロックへ割り当てる）」や「ワーストフィット（最大の空きブロックへ割り当てる）」があり、断片化の発生傾向などがそれぞれ異なります。用途に応じて使い分けることで、メモリ利用効率をさらに高めることができます。