C++で実装するFirst Fitアルゴリズム：メモリ管理の基本とサンプルコード

n個のプロセスとm個のメモリブロックが与えられたとき、First Fit（ファーストフィット）メモリ管理アルゴリズムを使って、各プロセスに適切なメモリブロックを割り当てる方法を解説します。

First Fitメモリ管理アルゴリズムとは？

オペレーティングシステムは、プロセスにメモリブロックを割り当てる際に、複数のメモリ分割アルゴリズムを使用しています。代表的なアルゴリズムは以下の通りです。

• First Fit アルゴリズム
• Next Fit アルゴリズム
• Best Fit アルゴリズム
• Worst Fit アルゴリズム
• Quick Fit アルゴリズム

First Fitアルゴリズムは、これらの中で最もシンプルなメモリ割り当て手法です。このアルゴリズムでは、ポインタがメモリ上のすべての空きブロックを追跡し、プロセスからのメモリ割り当て要求を受け付けます。その後、ポインタはメモリの先頭から順に検索を行い、プロセスを格納できる十分な大きさを持つ最初の空きブロックを見つけると、そこにプロセスを割り当てます。割り当て後、メモリブロックは「空き領域（ホール）」と「プロセスが使用する領域」の2つのパーティションに分割されます。

メリット： 先頭から順に検索し、最初に適合したブロックを即座に割り当てるため、他のアルゴリズムと比較して最も高速なメモリ割り当てが可能です。

デメリット： 小さなプロセスがメモリの先頭側に集中して割り当てられやすく、断片化が発生します。その結果、他のプロセスに利用できるメモリが不足する可能性があります。

実行例

入力：block_size[] = {300, 50, 200, 350, 70}
　　　process_size[] = {200, 47, 212, 426, 10}

出力：
Process No. Process Size Block no.
1           200          1
2           47           1
3           212          4
4           426          Not Allocated
5           10           1

この例では、プロセス4（サイズ426）はどのブロックよりも大きいため割り当てが失敗し、「Not Allocated」と表示されます。

プログラムのアプローチ

• メモリブロックとプロセスをそれぞれ配列に入力する
• すべてのメモリブロックを空き状態として初期化する
• （プロセスサイズ）≤（メモリブロックサイズ）が成立すれば、そのプロセスを該当ブロックに割り当てる
• 条件を満たさない場合は、条件を満たすブロックが見つかるまで残りのブロックを順番に走査する

アルゴリズム

開始
ステップ1→ First Fitでメモリブロックを割り当てる関数を宣言
　　void First_Fit(int block_size[], int total_blocks, int process_size[], int total_process)
　　int allocation[total_process] を宣言
　　memset(allocation, -1, sizeof(allocation)) を呼び出す
　　ループ For i = 0 かつ i < total_process かつ i++
　　　　ループ For j = 0 かつ j < total_blocks かつ j++
　　　　　　もし block_size[j] >= process_size[i] ならば
　　　　　　　　allocation[i] = j を設定
　　　　　　　　block_size[j] -= process_size[i] を設定
　　　　　　終了
　　　　終了
　　終了
　　ループ For i = 0 かつ i < total_process かつ i++
　　　　もし allocation[i] != -1 ならば
　　　　　　allocation[i] + 1 を表示
　　　　それ以外
　　　　　　「Not Allocated（未割り当て）」を表示
　　　　終了
　　終了
ステップ2→ main() 内で
　　ブロック用の配列を宣言 int block_size[] = {300, 50, 200, 350, 70}
　　プロセス用の配列を宣言 int process_size[] = {200, 47, 212, 426, 10}
　　ブロック総数を計算 int total_blocks = sizeof(block_size) / sizeof(block_size[0])
　　プロセス総数を計算 int total_process = sizeof(process_size) / sizeof(process_size[0])
　　First_Fit(block_size, total_blocks, process_size, total_process) を呼び出す
終了

C++での実装例

#include<bits/stdc++.h>
using namespace std;
// First Fitアルゴリズムに従って
// ブロックへメモリを割り当てる関数
void First_Fit(int block_size[], int total_blocks, int process_size[], int total_process) {
    int allocation[total_process];
    memset(allocation, -1, sizeof(allocation));
    // 各プロセスを取り出し、最初に適合するブロックを割り当てる
    for (int i = 0; i < total_process; i++) {
        for (int j = 0; j < total_blocks; j++) {
            if (block_size[j] >= process_size[i]) {
                allocation[i] = j;
                block_size[j] -= process_size[i];
                break;
            }
        }
    }
    cout << "\nProcess No.\tProcess Size\tBlock no.\n";
    for (int i = 0; i < total_process; i++) {
        cout << " " << i+1 << "\t\t" << process_size[i] << "\t\t";
        if (allocation[i] != -1)
            cout << allocation[i] + 1;
        else
            cout << "Not Allocated";
        cout << endl;
    }
}
int main() {
    // ブロックサイズを格納する配列を作成
    int block_size[] = {300, 50, 200, 350, 70};
    // プロセスサイズを格納する配列を作成
    int process_size[] = {200, 47, 212, 426, 10};
    // ブロックの総数を保持する変数
    int total_blocks = sizeof(block_size) / sizeof(block_size[0]);
    // プロセスの総数を保持する変数
    int total_process = sizeof(process_size) / sizeof(process_size[0]);
    // First_Fit関数を呼び出す
    First_Fit(block_size, total_blocks, process_size, total_process);
    return 0;
}

出力結果

Process No.     Process Size   Block no.
1               200            1
2               47             1
3               212            4
4               426            Not Allocated
5               10             1

このように、First Fitアルゴリズムは実装が非常に簡単で高速な一方、断片化によるメモリ効率の低下というトレードオフがあることを理解しておくことが重要です。実際のシステム設計では、Next FitやBest Fitなど、用途に応じた他のアルゴリズムとの使い分けも検討しましょう。