記憶管理

このページでは、実記憶の割当てとフラグメンテーション、仮想記憶とページング方式、LRU・FIFOなどのページ置換え、スラッシングがわかります。

• 一言で言うと：
  • 限られた主記憶（メモリ）を、たくさんのプログラムでどう分け合うか、足りない分をどうごまかすか（仮想記憶）という話。ページ置換えの数え上げ問題が頻出。

本物のメモリを分ける（実記憶管理）→ メモリを大きく見せる（仮想記憶管理）→ ページ単位で出し入れする（ページング方式）

覚え方の軸

• 「実記憶（本物のメモリ）」と「仮想記憶（ディスクを使って大きく見せる）」の2本立て
• すき間（フラグメンテーション）は「区画の中」か「区画の外」かで2種類：
  • 固定区画 → 内部フラグメンテーション、可変区画 → 外部フラグメンテーション → まとめる＝メモリコンパクション
• 空き領域の選び方は「最初・最小・最大」の3つ：
  • ファーストフィット（最初に見つけたもの）、ベストフィット（ぴったりに近い最小）、ワーストフィット（一番大きい）
• ページングは「表で変換 → なければ割込み → 読み込み → 満杯なら追い出す」の流れ：
  • ページテーブル（とTLB）→ ページフォールト → ページイン → ページ置換え（LRU・LFU・FIFO）
• 追い出し方の3つは「いつ使ったか・何回使ったか・いつ入ったか」：
  • LRU（最後に使ったのが一番昔）、LFU（使った回数が一番少ない）、FIFO（一番昔に入った）

実記憶管理：本物のメモリを分け合う

• 実アドレス空間：
  • 主記憶装置が作る記憶空間。プログラムを実行するには、必要な実アドレス空間を割り当てる
  • マルチプログラミングで、複数のプログラムにいかに効率よく割り当てるかが、システム全体の効率に大きく影響する
• 実アドレス空間の割当て方式

方式	やり方	問題点
単一連続割当て方式	OS以外の主記憶領域を、1つのプログラムだけに割り当てる	マルチプログラミングでは使えない
固定区画方式（パーティション方式）	主記憶を前もって固定長の区画（パーティション）に分け、プログラムに必要な大きさの区画を割り当てる	区画の中に余りが出る（内部フラグメンテーション）
可変区画方式（可変分割方式）	プログラムの大きさに合わせて割り当てる。固定区画方式より使用効率がよい	割当てと解放を繰り返すと、不連続な空きができる（外部フラグメンテーション）

• 補足：
  • 固定区画方式は、他の区画へのアクセスを禁止する記憶保護機構さえあれば、特別なハードウェアなしで実現でき、管理も簡単
• フラグメンテーション：
  • 断片化。一般に、単にフラグメンテーションといえば外部フラグメンテーションを指すことが多い
  • 例え：
    • 内部フラグメンテーションは「4人席に2人で座って2席余る」、外部フラグメンテーションは「空席は合計5席あるのに、全部バラバラで5人組が座れない」
• メモリコンパクション：
  • バラバラの未使用領域を、1つの連続領域にまとめる操作。合計では十分な空きがあっても、不連続だとプログラムを実行できないため
  • 動的再配置：
    • メモリコンパクションによって、実行中のプログラムが再配置されること
  • 補足：
    • 未使用領域をガーベジ（ゴミ）ととらえて、メモリコンパクションをガーベジコレクションと呼ぶこともあるが、厳密には両者は区別される
• 記憶域管理アルゴリズム（空き領域の管理方式）
  • リスト方式（最も代表的）：
    • 空き領域をリストで管理する。ヘッダ（リストの先頭要素を指すポインタ）を設け、空き領域のアドレス（記録位置）と大きさを持つ要素をチェーンでつなぐ。最後の要素はNULLを指す
  • ビットマップ方式：
    • ビットを固定長のメモリブロックに順に対応させる
  • メモリマップ方式：
    • 本質的にはリスト方式と同じだが、要素をテーブルで管理する
• 空き領域を割り当てるアルゴリズム★

アルゴリズム	選ぶ空き領域（必要量以上のもののうち）
最初適合（first-fit：ファーストフィット）	最初に見つかったもの
最適適合（best-fit：ベストフィット）	最小のもの
最悪適合（worst-fit：ワーストフィット）	最大のもの

• 例題：
  • 空き領域がリストの順に「200k、100k、160k、130k」バイトあるとき、120kバイトを割り当てる
  • ファーストフィット：
    • 先頭から見て最初に120k以上なのは 200k
  • ベストフィット：
    • 120k以上（200k、160k、130k）のうち最小の 130k（余りは10k）
  • ワーストフィット：
    • 120k以上のうち最大の 200k（余りは80k。大きな余りを残して再利用しやすくする考え方）
• 補足：
  • リスト要素の並べ方には、アドレス順（最初適合で使う）と大きさ順（最適適合で使う）がある
  • 最適適合では、空き領域の大きさをキーにした2分探索木を使うこともある
• オーバレイ方式：
  • プログラムを前もって、排他的に実行できる複数のセグメントに分けておき、実行時に必要なセグメントだけを主記憶に読み込む。読み込んだセグメントは、不要なセグメントの上に置かれる
  • 例：
    • A（3k、常駐）、B（4k）、C（6k）のモジュールで、BとCは同時に実行されない → 全部読むと 3＋4＋6＝13kバイト必要だが、オーバレイなら 3＋6（BとCの大きい方）＝9kバイトで実行できる
• セグメント：
  • プログラムを構成する関数やモジュールなどの論理的な単位
• スワッピング：
  • 長い時間実行待ちになっているプログラムを、実行状態のまま補助記憶のスワップ領域に退避（スワップアウト）して、別のプログラムを主記憶に読み込んで実行する。再開するときは、退避した状態を読み込む（スワップイン）
  • プログラム単位で丸ごと出し入れする（ページングはページ単位）
• スワップ（swap）：
  • 主記憶の容量不足を補うために確保された、ハードディスク上の領域。Linuxでは、通常、主記憶容量の約2倍をswapとして確保する

メモリプール

• メモリプール：
  • プログラムからの領域獲得要求にすばやく応えるため、ある程度の大きさの領域を前もって一括で確保した領域
  • プログラムの中で一括確保した領域、システムのメモリ管理機能で確保するもの、プログラム起動時にシステムが用意するヒープ領域も、メモリプールの一種
  • 動的な割当てと解放を繰り返せる。プログラムは必要な大きさを獲得し、不要になったら返却する
  • 通常、複数のメモリブロックでできている

管理方式	やり方	速さ	フラグメンテーション
可変長方式	要求量を満たす空きブロックを割り当て、余りを新しい空きブロックとして分割する	獲得・返却が遅く、一定しない	小さな余りが多くできて、フラグメンテーションの原因になる
固定長方式	要求量を満たす空きブロックをそのまま（必要なら複数をリンクして）割り当てる	獲得・返却が速く、一定	可変長方式のようなものは起きないが、ブロック内に内部フラグメンテーションが起きて使用効率が悪い

仮想記憶管理：ディスクを使ってメモリを大きく見せる

• 仮想記憶方式：
  • 磁気ディスクなどの補助記憶を使って、主記憶の物理的な容量よりはるかに大きなアドレス空間を提供する
  • 例え：
    • 机（主記憶）は狭いが、本棚（ディスク）に置いた本も「机の上にある」ように使える。必要なページだけ机に出す
• 仮想アドレス空間（論理アドレス空間）：
  • 仮想記憶方式で提供される、大きなアドレス空間
• 仮想アドレス（論理アドレス）→ 実アドレス（物理アドレス）：
  • プログラムで扱うアドレスは仮想アドレスなので、命令を実行するときに主記憶の実アドレスに変換する
• 動的アドレス変換（DAT：Dynamic Address Translator）：
  • プログラム実行時に、仮想アドレスを実アドレスに変換すること
• MMU（Memory Management Unit：メモリ管理ユニット）：
  • DATを実際に行うハードウェア装置
  • 主な機能：
    • 仮想アドレスを実アドレスに対応させる機能（仮想記憶管理）、メモリ保護機能、キャッシュ制御機能など
• 仮想記憶を実現する2つの方式（一般に、仮想記憶方式といえばページング方式を指す）

方式	分ける単位	特徴
ページング方式	ページ（固定長）	実行に必要なページだけを主記憶に読み込むので、主記憶の有効活用やフラグメンテーション問題の解決が期待できる
セグメンテーション方式	セグメント（論理的な単位。大きさは可変）	セグメント単位でアドレス変換する。ページングと組み合わせたものをセグメンテーションページング方式という

ページング方式：ページ単位で出し入れする

• ページテーブル：
  • 仮想アドレスと実アドレスを対応付ける（マッピングする）アドレス対応表
  • 仮想アドレスは「ページ番号」＋「ページ内変位（ページ内の相対アドレス）」でできている
  • ページテーブルには、各ページが置かれている主記憶上のアドレス（ページ枠先頭アドレス）と、ページフォールトビット（主記憶にない＝1、ある＝0）を記録する
  • MMUは命令を実行するたびにページテーブルを見て、ページが主記憶にあるかを判断し、実アドレスを計算する
  • 補足：
    • 動的にアドレスを変換するので、主記憶上にバラバラに置かれたプログラムを順序正しく実行できる
    • 記憶保護を簡単にするため、ページテーブルにアクセス権を設定する方式もある
• アドレス変換の例（1ページの大きさを100とする）：
  • ページテーブルが「ページ0 → 400、ページ1 → 200、ページ2 → 主記憶にない、ページ3 → 700」
  • 仮想アドレスが「ページ番号1、ページ内変位35」なら、ページ1の先頭アドレス200 ＋ 35 ＝ 実アドレス 235
  • ページ2を参照すると、ページフォールトビットが1なのでページフォールトが起きる
• TLB（Translation Look-aside Buffer）：
  • アドレス変換バッファ、連想レジスタともいう。MMU内部にある一種のキャッシュで、最近参照したページの変換履歴を記憶する
  • 主記憶のページテーブルを毎回見ると遅いので、TLBでアドレス変換を高速化する
• ページフォールト（ページ不在）：
  • 処理に必要なページが主記憶にない状態
  • 実際には、内部割込みであるページフォールト割込みが起きる（DATの過程で、ページフォールトビットが1のとき）→ そのページを主記憶に読み込む（ページイン）
• ページイン：
  • ページを主記憶に読み込むこと
• ページアウト：
  • ページを主記憶から追い出して、補助記憶に書き出すこと
• ページング：
  • ページインとページアウトのこと
• ページインのアルゴリズム
  • デマンドページング：
    • ページフォールトが起きたときに、そのページを読み込む。空きページ枠がなければ、ページ置換え（リプレースメント）アルゴリズムで決めた不要ページを追い出してから読み込む
  • プリページング：
    • 近い将来必要になるページを予測して、前もって読み込んでおく。ページフォールトの回数を減らせるが、予測が難しいので、実際はデマンドページングと併用する
• ページ置換えアルゴリズム★

アルゴリズム	追い出すページ	考え方
LRU（Least Recently Used）	最も長い間参照されていないページ	最近使ったページはまた使われやすい。効率がよいといわれる
LFU（Least Frequently Used）	参照された頻度が最も少ないページ	あまり使われないページは今後も使われにくい
FIFO（First In First Out）	最も長く存在する（最も早くページインした）ページ	プログラムは順に実行されるので、早く入ったページはもう使われにくい

• LRUやFIFOの基本的な考え方：
  • 「その時点以降、最も遠い将来まで参照されないページはどれか」を推測すること
• 最適（OPT）アルゴリズム：
  • 最も遠い将来まで参照されないページを本当に選ぶ方法。未来はわからないので実現できない。代わりにLRUやFIFOを使う
• 例題（ページ枠3つ、ページ参照順「1, 2, 3, 2, 1, 4, 1」）：
  • 最初の 1, 2, 3 は空き枠に入る（ページフォールト3回）。次の 2, 1 は主記憶にあるのでフォールトなし
  • 4 を参照（ページフォールト）：
    • FIFO：
      • 一番早く入った 1 を追い出す → {2, 3, 4}。次の 1 でまたフォールトが起き、一番早く入った2を追い出す → {3, 4, 1}。合計 5回
    • LRU：
      • 最後に使ったのが一番昔の 3 を追い出す → {1, 2, 4}。次の 1 は主記憶にある。合計 4回
  • ポイント：
    • 「入った順」と「最後に使った順」は違う。表に時刻を書いて1つずつ追うと間違えにくい
• 割当て主記憶容量とページフォールト
  • 一般に、割当て主記憶容量を増やすと、ページフォールト発生率は減る
  • ただしFIFOでは、割当てを増やすと逆にページフォールトが増えることがある（★頻出）
  • 例：
    • 参照順「1 2 3 4 1 2 5 1 2 3 4 5」で、ページ枠3なら9回、ページ枠4なら10回（1回増える）
  • この現象はBeladyの例外（ビレイディの異常）とも呼ばれる
• スラッシング★：
  • プログラムの多重度が高く、各プログラムへの割当て主記憶が小さかったり、置換え方法が適切でなかったりすると、ページングが多発する
  • ページングの実行優先度はプログラムより高いので、プログラムに回るCPU時間が減り、処理速度（レスポンス）が極端に悪くなって、システム全体のスループットが急激に下がる現象
  • グラフでは、多重度を上げるとスループットは上がっていくが、ある点を超えると急に落ちる
  • 例え：
    • 狭い机で本を何冊も同時に読もうとして、本棚との出し入ればかりで、肝心の読書が進まない
• 局所参照性：
  • 参照された場所の近くは続けて参照されやすく、離れた場所は参照されにくい、というプログラムの性質
  • ループによる反復実行のように、短い時間に近い場所を参照するプログラムは局所参照性が高い。分岐命令などで短い時間に広い範囲を参照するほど、局所参照性は低い
• ワーキングセット：
  • プログラムが各時点で局所参照しているページの集合。具体的には、過去T時間に参照されたページの集合
  • OSは前もって局所参照性を知ることができないので、実行時に把握して、ワーキングセットを主記憶に保存するように管理する
  • もとの概念：
    • 「プログラムを効率よく実行するために、主記憶内に存在させるべきページの集合」

混同しやすいペア

• 内部フラグメンテーション（区画の中の余り。固定区画・固定長）／外部フラグメンテーション（区画の外のバラバラな空き。可変区画・可変長）
• メモリコンパクション（空きを1つにまとめる）／ガーベジコレクション（ゴミ集め。厳密には別もの）
• ファーストフィット（最初に見つかったもの）／ベストフィット（最小）／ワーストフィット（最大）
• オーバレイ（同時に使わない部分を同じ場所に重ねる）／スワッピング（プログラム丸ごと出し入れ）／ページング（ページ単位で出し入れ）
• ページング方式（固定長のページ）／セグメンテーション方式（可変長のセグメント）
• 仮想アドレス（論理アドレス。プログラムが使う）／実アドレス（物理アドレス。主記憶の本物の番地）
• DAT（アドレス変換のこと）／MMU（変換するハードウェア）／TLB（変換結果のキャッシュ）
• デマンドページング（必要になってから読む）／プリページング（予測して先に読む）
• LRU（最後に使ったのが一番昔）／LFU（使った回数が一番少ない）／FIFO（一番早く入った）
• ページイン（主記憶に読み込む）／ページアウト（補助記憶に追い出す）
• スラッシング（ページングが多すぎてスループットが急落）／ワーキングセット（主記憶に置いておくべきページの集合）
• 可変長方式（遅い・断片化）／固定長方式（速い・ブロック内に余り）

---

← 05 ソフトウェアの目次に戻る