記憶管理とは？実記憶・仮想記憶・ページング・LRUを基礎から理解しよう

はじめに

プログラムを実行するとき、そのプログラムやデータは基本的に**主記憶（メモリ）**へ読み込まれます。

しかし、メモリの容量には限りがあります。

そこでOSは、

どのプログラムに、メモリのどの領域を、どれくらい割り当てるか

を管理しています。

これが記憶管理です。

今回は、

実記憶管理
   ↓
仮想記憶管理
   ↓
ページング
   ↓
ページ置換
   ↓
ページフォール
   ↓
スラッシング

という流れで見ていきましょう。

---

1. 実記憶管理

**実記憶（Real Memory）**とは、コンピュータに実際に搭載されている主記憶のことです。

つまり、一般的にいう物理メモリです。

実記憶管理では、

限られた実記憶を、複数のプログラムへどのように割り当てるか

を管理します。

---

2. 実アドレス空間の割り当て

プログラムを実記憶へ配置する方法には、いくつかの考え方があります。

固定区画方式

あらかじめ主記憶を一定の区画に分割しておき、それぞれにプログラムを配置する方式です。

主記憶

┌──────────┐
│ OS       │
├──────────┤
│ 区画1    │ ← プログラムA
├──────────┤
│ 区画2    │ ← プログラムB
├──────────┤
│ 区画3    │
└──────────┘

仕組みは単純ですが、プログラムが区画より小さい場合、余った領域が無駄になります。

このように、割り当てた領域の内部に使用されない領域が生じることを内部断片化と呼びます。

可変区画方式

プログラムの大きさに応じて必要な分だけ記憶領域を割り当てる方式です。

┌──────────┐
│ OS       │
├──────────┤
│ A        │
├─────┐    │
│ B   │    │
├──────────┤
│ 空き     │
└──────────┘

効率よく利用できますが、プログラムの配置と解放を繰り返すと、小さな空き領域がバラバラに発生することがあります。

これを外部断片化と呼びます。

---

3. 記憶域管理アルゴリズム

可変区画方式などでは、空いている記憶領域のどこへプログラムを配置するか決める必要があります。

代表的な方式が、

• First Fit
• Best Fit
• Worst Fit

です。

First Fit

先頭から空き領域を探して、

最初に見つかった十分な大きさの領域

へ配置します。

Best Fit

利用可能な空き領域の中から、

要求された容量に最も近い、小さな領域

へ配置します。

Worst Fit

利用可能な空き領域の中から、

最も大きな空き領域

へ配置します。

整理すると、

方式	選択する領域
First Fit	最初に見つかった十分な領域
Best Fit	入る領域の中で最も小さい領域
Worst Fit	最も大きい領域

です。

---

4. オーバレイ方式

昔のコンピュータでは、実行したいプログラム全体が主記憶に入りきらないことがありました。

そこで利用される考え方が**オーバレイ方式（Overlay）**です。

プログラムを複数の部分に分割し、必要な部分だけを主記憶へ読み込んで実行する方式

です。

例えば、

大きなプログラム

A
B
C
D

をすべて同時に読み込むのではなく、

必要なとき

Aを読み込む
 ↓
Bに入れ替える
 ↓
Cに入れ替える

というように利用します。

限られた主記憶でも、大きなプログラムを実行できるようにする考え方です。

---

5. スワッピング

**スワッピング（Swapping）**とは、

実行中のプログラムやプロセスを、主記憶と補助記憶の間で入れ替える仕組み

です。

主記憶が不足すると、

主記憶
  ↓
一時的に補助記憶へ退避

し、必要になったら、

補助記憶
  ↓
主記憶へ戻す

という処理を行います。

主記憶から補助記憶へ退避することをスワップアウト、補助記憶から主記憶へ戻すことをスワップインと呼びます。

---

6. 仮想記憶管理

実記憶だけを使う場合、実行できるプログラムの大きさは物理的なメモリ容量に強く制限されます。

そこで利用されるのが、

仮想記憶（Virtual Memory）

です。

仮想記憶では、

補助記憶を利用することで、実際の主記憶より大きなアドレス空間をプログラムから利用できるようにする

ことができます。

例えば、

プログラムから見える空間
┌────────────────┐
│     仮想記憶空間        │
└────────────────┘
           ↓
   必要な部分だけ
           ↓
┌────────────────┐
│       実記憶           │
└────────────────┘

というイメージです。

プログラム側は、実際にどの物理メモリへ配置されているのかを強く意識せずに動作できます。

---

7. ページング方式

仮想記憶を実現する代表的な方式が、

ページング方式（Paging）

です。

ページング方式では、仮想記憶空間を一定サイズの、

ページ（Page）

に分割します。

一方、実記憶も同じ大きさの、

ページフレーム

に分割します。

仮想記憶             実記憶

ページ0 ───────→ フレーム2
ページ1 ───────→ フレーム0
ページ2 ───────→ フレーム5
ページ3 ───────→ フレーム1

ページとページフレームを対応付けることで、仮想記憶上では連続しているデータを、実記憶上では離れた場所へ配置できます。

---

8. アドレス変換

CPUがプログラムを実行するときに扱うのは、基本的に仮想アドレスです。

これを実際の主記憶上の物理アドレスへ変換する必要があります。

仮想アドレス
    ↓
ページ番号 + ページ内変位
    ↓
ページテーブル
    ↓
ページフレーム番号 + ページ内変位
    ↓
物理アドレス

この対応関係を管理するのがページテーブルです。

例えば、

仮想ページ2
    ↓
ページテーブル
    ↓
物理フレーム5

という対応が登録されていれば、仮想ページ2へのアクセスを物理フレーム5へ変換できます。

---

9. ページインとページアウト

すべてのページが常に実記憶に置かれているわけではありません。

必要になったページが実記憶に存在しない場合、そのページを補助記憶から読み込みます。

これを、

ページイン（Page In）

と呼びます。

逆に、実記憶からページを追い出して補助記憶側へ移すことを、

ページアウト（Page Out）

と呼びます。

補助記憶
   │
   │ ページイン
   ↓
実記憶
   │
   │ ページアウト
   ↓
補助記憶

---

10. ページフォールト

CPUが必要としたページが実記憶上に存在しない場合、

ページフォールト（Page Fault）

が発生します。

するとOSは、

必要なページがない
      ↓
ページフォールト
      ↓
補助記憶から探す
      ↓
ページイン
      ↓
実記憶へ配置
      ↓
処理を再開

という処理を行います。

補助記憶へのアクセスは主記憶へのアクセスより非常に時間がかかるため、ページフォールトが多すぎると性能が低下します。

---

11. 実記憶がいっぱいだったら？

ページインしたくても、すべてのページフレームが使用中の場合があります。

この場合、

現在実記憶にあるページのどれかを追い出す

必要があります。

このとき、

どのページを追い出すのか

を決めるのがページ置換アルゴリズムです。

代表的な方式として、

• FIFO
• LRU

があります。

---

12. FIFO

**FIFO（First In First Out）**は、

最も古く実記憶へ入ったページから追い出す方式

です。

例えば実記憶に、

入った順番

1 → 2 → 3

というページが存在するとします。

ここでページ4が必要になった場合、

1 → 2 → 3
↑
最も古い

ため、ページ1を追い出します。

結果、

2 → 3 → 4

となります。

🍯 FIFOは**「いつ入った？」を見る方式**です。

---

13. LRU

**LRU（Least Recently Used）**は、

最も長い間使用されていないページを追い出す方式

です。

FIFOとの違いが重要です。

FIFO
→ 最も昔に「入った」ページ

LRU
→ 最も昔に「使った」ページ

と覚えましょう。

---

14. LRUによるページ置き換えの例

ページフレームが3個あり、次の順番でページへアクセスするとします。

1 → 2 → 3 → 1 → 4

最初は空です。

① ページ1

[1][ ][ ]

ページフォールトが発生します。

② ページ2

[1][2][ ]

ページフォールトです。

③ ページ3

[1][2][3]

これで3つのフレームが埋まりました。

④ ページ1

[1][2][3]

ページ1はすでに実記憶にあるため、ページフォールトは発生しません。

ただし、

ページ1が最近使用された

という情報は更新されます。

この時点で、最も長く使われていないページはページ2です。

⑤ ページ4

ページ4は実記憶にありません。

そこでLRUでは、

[1][2][3]
    ↑
最も長く使われていない

ページ2を追い出します。

結果、

[1][4][3]

となります。

これがLRUの基本的な考え方です。

---

15. FIFOならどうなる？

同じ、

1 → 2 → 3 → 1 → 4

をFIFOで考えてみましょう。

最初に、

[1][2][3]

が読み込まれます。

その後ページ1を使用しても、

ページ1が最初に入ったという事実は変わりません。

そのためページ4が必要になると、

[1][2][3]
 ↑
最も古く入った

ページ1を追い出します。

結果、

[4][2][3]

となります。

したがって、

FIFO → 入った順番を見る
LRU  → 最後に使った時点を見る

という違いがあります。

---

16. 割り当て主記憶容量とページフォールト

プログラムへ割り当てるページフレームが少ないと、

必要なページ
   ↓
実記憶にない
   ↓
ページフォールト

が発生しやすくなります。

一方、利用できるページフレームが増えれば、多くのページを実記憶へ保持できます。

一般的には、

割り当てられる主記憶容量が十分であれば、ページフォールトを減らしやすくなる

と考えられます。

ただし、ページ置換方式やプログラムのアクセスパターンによっても結果は変化します。

---

17. スラッシング

主記憶が不足してページフォールトが大量に発生すると、

ページフォールト
      ↓
ページイン
      ↓
別ページをページアウト
      ↓
すぐにそのページが必要
      ↓
またページフォールト
      ↓
ページイン……

という状態になることがあります。

このように、

ページの入れ替え処理ばかりが発生し、本来の処理がほとんど進まなくなる状態

を、

スラッシング（Thrashing）

と呼びます。

CPUで本来の処理
████████████████

↓ スラッシング

本来の処理
██

ページ入替え
██████████████

というイメージです。

---

18. ワーキングセット

スラッシングを考えるうえで重要なのが、

ワーキングセット（Working Set）

です。

ワーキングセットとは、

ある一定期間にプログラムが頻繁に使用しているページの集合

です。

プログラムは通常、すべてのページを均等に利用するわけではありません。

例えば、

全ページ

1 2 3 4 5 6 7 8 9 10

現在よく使うページ

3 4 5 6

なら、

{3, 4, 5, 6}

が現在のワーキングセットだと考えられます。

---

19. ワーキングセットとスラッシング

ワーキングセットに必要なページを十分に実記憶へ置ければ、

必要なページ
↓
実記憶にある
↓
そのまま処理

となり、ページフォールトを抑えられます。

反対に、ワーキングセットを保持できないほど実記憶が不足すると、

必要なページを追い出す
      ↓
すぐにまた必要になる
      ↓
ページフォールト
      ↓
別のページを追い出す
      ↓
……

となり、スラッシングが発生しやすくなります。

そのため、

プログラムが現在必要としているページ群を実記憶上に確保する

ことが重要です。

---

20. 記憶管理の全体像

ここまでの内容を整理すると、

記憶管理
│
├─ 実記憶管理
│   ├─ 固定区画方式
│   ├─ 可変区画方式
│   ├─ First Fit
│   ├─ Best Fit
│   ├─ Worst Fit
│   ├─ オーバレイ
│   └─ スワッピング
│
└─ 仮想記憶管理
    │
    └─ ページング
        ├─ ページテーブル
        ├─ アドレス変換
        ├─ ページイン
        ├─ ページアウト
        └─ ページフォールト
             ↓
        ページ置換
        ├─ FIFO
        └─ LRU
             ↓
        多発すると
             ↓
        スラッシング
             ↑
        ワーキングセットが重要

という関係になります。

---

まとめ

この記事で覚えること

• 記憶管理は主記憶を効率よく利用するためのOSの機能
• 固定区画方式では内部断片化が発生することがある
• 可変区画方式では外部断片化が発生することがある
• First Fit・Best Fit・Worst Fitは空き領域の選び方が異なる
• オーバレイ方式は必要なプログラム部分だけを主記憶へ読み込む
• スワッピングは主記憶と補助記憶の間でプログラムなどを入れ替える
• 仮想記憶では実記憶より大きなアドレス空間を扱える
• ページングでは仮想記憶をページ、実記憶をページフレームに分割する
• ページテーブルによって仮想アドレスから物理アドレスへ変換する
• 必要なページが実記憶にないとページフォールトが発生する
• FIFOは最も古く入ったページを置換する
• LRUは最も長く使われていないページを置換する
• ページフォールトが大量に発生するとスラッシングにつながる
• ワーキングセットは一定期間に頻繁に利用されるページの集合

🍯 はちみつメモ

仮想記憶は「必要なページだけ実記憶に置く」と考えると分かりやすい。必要なページがなければページフォールト。実記憶がいっぱいならページを置換し、FIFOは「入った順」、LRUは「使った順」を見る。ページ交換ばかりになるとスラッシング！