基本情報技術者 2009年 秋期 午前（科目A） 問18

要点まとめ

• 結論→ 固定長方式は内部断片化によりメモリ効率が劣る一方、獲得および返却は非常に高速で常に一定時間で処理できる方式です。
• 根拠→ 同一サイズのブロックをフリーリストで管理し、割当／解放はポップ／プッシュだけで済むため処理時間が決定的に短く$O(1)$に近い振る舞いを示します。
• 差がつくポイント→ リアルタイム性（遅延の確定性）を重視するか、メモリ効率（断片化の低減）を重視するかで方式選定が分かれ、場合により両者を組合せます。

正解の理由

よくある誤解

• 「高速＝効率的」と考えて固定長を無条件に採用すると、内部断片化でメモリを無駄遣いしてしまいます。
• 可変長方式が常に遅く不確定というわけではなく、アルゴリズム次第で性能改善や断片化抑制は可能です。

解法ステップ

1. 問題文で比較する観点を確認：「メモリ効率」と「獲得及び返却の処理速度（一定か不定か／速いか遅いか）」。
2. 固定長方式の特性を思い出す：同サイズブロック管理→フリーリスト→高速・定時間。
3. 固定長の弱点：内部断片化によるメモリ効率の低下。
4. 各選択肢の語句と対応させ、矛盾がないものを選ぶ（ウが一致）。
5. 選択肢を排除法で確認し、最終的に ウ を確定する。

選択肢別の誤答解説

• ア: 「メモリ効率が良く、獲得及び返却の処理速度は遅く一定である。」→ 固定長は処理速度は速いのに「遅い」としている点が誤り。
• イ: 「メモリ効率が良く、獲得及び返却の処理速度は遅く不定である。」→ 固定長は効率が良いわけではなく、速度も遅く不定ではないため複数の点で不適。
• ウ: 「メモリ効率が悪く、獲得及び返却の処理速度は速く一定である。」→ 正解。内部断片化で効率が落ち、操作はフリーリストで高速かつ決定的。
• エ: 「メモリ効率が悪く、獲得及び返却の処理速度は速く不定である。」→ 処理速度は速いが「不定（非決定的）」は固定長の特性と矛盾。

補足コラム

• 内部断片化と外部断片化：固定長は内部断片化（割り当てブロック内の未使用領域）が主な問題。可変長は外部断片化（空き領域が分散）に悩まされることが多いです。
• 実装例：固定長プールは複数のサイズクラス（階層）を用いることで断片化を抑えつつ高速性を保つ設計がよく使われます（スラブアロケータやスロットアロケータ）。
• リアルタイム用途：遅延の上限が必要なリアルタイムシステムでは、固定長の「処理時間の決定性」が非常に重要です。
• 簡単なフリーリスト割当の擬似コード（C）：

typedef struct Block { struct Block *next; } Block;
Block *free_list = NULL;

void *alloc_block() {
    if (!free_list) return NULL; // プール枯渇時のハンドリングが必要
    Block *b = free_list;
    free_list = free_list->next; // O(1)
    return b;
}

void free_block(void *p) {
    Block *b = (Block*)p;
    b->next = free_list;
    free_list = b; // O(1)
}

• 性能評価は単に平均時間ではなく最悪時間（ワーストケース）を見て選ぶことが重要です。固定長はワーストケースも短く予測可能です。

FAQ