[オペレーティングシステム] 10. 仮想メモリ：デマンドページングからスラッシングまで

仮想メモリの概念

仮想メモリ（Virtual Memory）は、プロセス全体が物理メモリにロードされていなくても実行を可能にする技術である。プログラマに実際の物理メモリよりもはるかに大きなアドレス空間を提供する。

[仮想メモリの動作]

仮想アドレス空間（プロセス視点）：       物理メモリ：
+-----------+ 0xFFFF...                +-----------+
|   スタック  |                          |   OS      |
|    |      |                          +-----------+
|    v      |                          | ページ A   | <-- 仮想ページ 0
|           |                          +-----------+
|           |                          | ページ C   | <-- 仮想ページ 5
|    ^      |                          +-----------+
|    |      |                          | ページ D   | <-- 仮想ページ 2
|   ヒープ   |                          +-----------+
+-----------+                          |   空き     |
|  データ    |                          +-----------+
+-----------+
|  コード    |                          ディスク（スワップ領域）：
+-----------+ 0x0000...                +-----------+
                                       | ページ B   | <-- 仮想ページ 1
4GB仮想空間のうち一部のみ               | ページ E   | <-- 仮想ページ 3
物理メモリにロードされている             +-----------+

仮想メモリの利点は以下の通りである。

プログラムが物理メモリより大きくなれる
各プロセスのアドレス空間が分離される
複数のプロセスがページを共有できる（共有ライブラリ、fork時のCOW）
プロセス生成が効率的

デマンドページング（Demand Paging）

プログラム開始時にすべてのページをメモリにロードする代わりに、実際に必要な時のみ（on demand）ページをロードする。

[デマンドページングの概念]

ページテーブル：
+-------+------+
| フレーム| 有効  |
+-------+------+
|   3   |  v   |  <- メモリにある
|   -   |  i   |  <- ディスクにある（まだロードされていない）
|   7   |  v   |  <- メモリにある
|   -   |  i   |  <- ディスクにある
+-------+------+

v = valid（メモリにある）
i = invalid（メモリにない、ディスクにある）

ページフォルト（Page Fault）

無効なページにアクセスするとページフォルトが発生する。

[ページフォルト処理過程]

1. CPUがページテーブルを参照
2. 有効ビットが i (invalid) -> トラップ発生
      |
      v
3. OSがページフォルトを確認
   - 不正な参照（アドレス範囲外）？ -> プロセス終了
   - 有効だがメモリにない？ -> 続行
      |
      v
4. 空きフレームを探す
      |
      v
5. ディスクからページを空きフレームに読み込む（I/O）
      |
      v
6. I/O完了時：
   - ページテーブル更新（フレーム番号、有効ビット = v）
   - プロセス再開（フォルトを起こした命令から）

デマンドページングの性能

[実効アクセス時間（EAT）]

p = ページフォルト確率
ma = メモリアクセス時間 (200ns)
ページフォルト処理時間 = 8ms (8,000,000ns)

EAT = (1 - p) * ma + p * ページフォルト時間
    = (1 - p) * 200 + p * 8,000,000

p = 0.001（1000回に1回フォルト）なら：
EAT = 0.999 * 200 + 0.001 * 8,000,000
    = 199.8 + 8,000
    = 8,199.8ns

性能低下40倍！

10%以内の性能低下のためには：
220 > 200 + 7,999,800 * p
p < 0.0000025
つまり400,000回アクセスに1回以下のページフォルトが必要

コピーオンライト（Copy-on-Write, COW）

fork()時に親のページを即座にコピーせず、2つのプロセスが同じページを共有する。どちらかがページを変更しようとした時のみ、そのページをコピーする。

[Copy-on-Write動作]

fork()直後：
親ページテーブル：              子ページテーブル：
ページ0 -> フレーム A (COW)   ページ0 -> フレーム A (COW)
ページ1 -> フレーム B (COW)   ページ1 -> フレーム B (COW)
ページ2 -> フレーム C (COW)   ページ2 -> フレーム C (COW)

子がページ1を変更すると：
親ページテーブル：              子ページテーブル：
ページ0 -> フレーム A (COW)   ページ0 -> フレーム A (COW)
ページ1 -> フレーム B         ページ1 -> フレーム D（コピー）
ページ2 -> フレーム C (COW)   ページ2 -> フレーム C (COW)

変更されたページのみコピー -> 不要なコピーを排除

// COWが適用されるfork + execパターン
#include <unistd.h>
#include <sys/wait.h>

int main() {
    pid_t pid = fork();
    // fork時点：親のページをCOWで共有

    if (pid == 0) {
        // exec()呼び出し時に子のアドレス空間が完全に置き換わる
        // COWのおかげでforkでの不要なページコピーなし
        execlp("ls", "ls", "-la", NULL);
    } else {
        wait(NULL);
    }

    return 0;
}

ページ置換（Page Replacement）

物理メモリが満杯の時に新しいページをロードするには、既存のページの1つをディスクに追い出す（置換する）必要がある。

[ページ置換過程]

1. ディスク上のページ位置を確認
2. 空きフレームを探す
   - 空きフレームがあれば使用
   - なければ置換アルゴリズムで犠牲ページを選択
     - 犠牲ページが変更されていれば（dirty bit）ディスクに書き込む
     - 変更されていなければそのまま上書き
3. 新しいページを空きフレームにロード
4. ページテーブルを更新
5. プロセスを再開

1. FIFOページ置換

最も早くロードされたページを最初に置換する。

[FIFO例] フレーム3個、参照列：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1

参照  7  0  1  2  0  3  0  4  2  3  0  3  2  1  2  0  1  7  0  1
     [7][ ][ ] -> フォルト
     [7][0][ ] -> フォルト
     [7][0][1] -> フォルト
     [2][0][1] -> フォルト (7置換)
     [2][0][1] -> ヒット
     [2][3][1] -> フォルト (0置換)
     [2][3][0] -> フォルト (1置換)
     [4][3][0] -> フォルト (2置換)
     [4][2][0] -> フォルト (3置換)
     [4][2][3] -> フォルト (0置換)
     [0][2][3] -> フォルト (4置換)
     [0][2][3] -> ヒット
     [0][2][3] -> ヒット
     [0][1][3] -> フォルト (2置換)
     [0][1][2] -> フォルト (3置換)
     [0][1][2] -> ヒット
     [0][1][2] -> ヒット
     [7][1][2] -> フォルト (0置換)
     [7][0][2] -> フォルト (1置換)
     [7][0][1] -> フォルト (2置換)

総ページフォルト：15

ベラディの異常（Belady's Anomaly）: FIFOではフレーム数を増やしてもページフォルトが増加する場合がある。

2. 最適ページ置換（OPT）

今後最も長く使われないページを置換する。理論的最適だが未来を知ることができないため実装不可能である。他のアルゴリズムの比較基準として使用する。

[OPT例] フレーム3個、参照列：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1

参照  7  0  1  2  0  3  0  4  2  3  0  3  2  1  2  0  1  7  0  1
     [7][ ][ ] -> フォルト
     [7][0][ ] -> フォルト
     [7][0][1] -> フォルト
     [2][0][1] -> フォルト (7：最も遅く使用される)
     [2][0][1] -> ヒット
     [2][0][3] -> フォルト (1：最も遅く使用される)
     [2][0][3] -> ヒット
     [2][4][3] -> フォルト (0はすぐ使うので別のものを置換)
     [2][4][3] -> ヒット
     [2][4][3] -> ヒット
     [2][0][3] -> フォルト
     [2][0][3] -> ヒット
     [2][0][3] -> ヒット
     [2][0][1] -> フォルト
     [2][0][1] -> ヒット
     [2][0][1] -> ヒット
     [2][0][1] -> ヒット
     [7][0][1] -> フォルト
     [7][0][1] -> ヒット
     [7][0][1] -> ヒット

総ページフォルト：9（最適）

3. LRUページ置換（Least Recently Used）

最も長い間使用されていないページを置換する。OPTの近似値で、過去の情報を未来の近似として使用する。

[LRU例] フレーム3個、参照列：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1

参照  7  0  1  2  0  3  0  4  2  3  0  3  2  1  2  0  1  7  0  1
     [7][ ][ ] -> フォルト
     [7][0][ ] -> フォルト
     [7][0][1] -> フォルト
     [2][0][1] -> フォルト (7：最も古く使用)
     [2][0][1] -> ヒット
     [2][0][3] -> フォルト (1：最も古く使用)
     [2][0][3] -> ヒット（0が最近使用）
     [4][0][3] -> フォルト (2：最も古く使用)
     [4][0][2] -> フォルト (3：最も古く使用)
     [4][3][2] -> フォルト (0：最も古く使用)
     [0][3][2] -> フォルト (4：最も古く使用)
     [0][3][2] -> ヒット
     [0][3][2] -> ヒット
     [1][3][2] -> フォルト (0：最も古く使用)
     [1][3][2] -> ヒット
     [1][0][2] -> フォルト (3：最も古く使用)
     [1][0][2] -> ヒット
     [1][0][7] -> フォルト (2：最も古く使用)
     [1][0][7] -> ヒット
     [1][0][7] -> ヒット

総ページフォルト：12

LRUの実装方法。

カウンタ方式: 各ページテーブルエントリにアクセス時間を記録。置換時に最も古いものを選択
スタック方式: ページアクセス時にスタックの最上位に移動。最下位がLRUページ

両方法ともハードウェアサポートが必要で、純粋なLRU実装はコストが高い。

4. クロックアルゴリズム（Second-Chance / Clock）

LRUの近似アルゴリズムで、参照ビット（reference bit）を使用する。

[クロックアルゴリズム]

フレームが円形キューを形成
各フレームに参照ビット(ref)がある

         ポインタ
           |
           v
    [A, ref=1] -> [B, ref=0] -> [C, ref=1] -> [D, ref=0]
         ^                                          |
         |                                          |
         +------------------------------------------+

置換が必要な時：
1. ポインタが指すフレームを確認
2. ref=0なら：このページを置換
3. ref=1なら：refを0にリセットし、ポインタを次に移動
4. 2-3を繰り返す

動作過程：
ポインタ -> [A, ref=1]：refを0に変更、次へ
ポインタ -> [B, ref=0]：このページを置換！

参照ビットはハードウェアがページアクセス時に自動的に1に設定

// クロックアルゴリズム実装（概念的）
#define NUM_FRAMES 64

struct frame {
    int page_number;
    int reference_bit;
    int dirty_bit;
};

struct frame frames[NUM_FRAMES];
int clock_hand = 0;

int clock_replace() {
    while (1) {
        if (frames[clock_hand].reference_bit == 0) {
            // 置換対象を発見
            int victim = clock_hand;
            clock_hand = (clock_hand + 1) % NUM_FRAMES;
            return victim;
        }

        // セカンドチャンス付与：参照ビットをリセット
        frames[clock_hand].reference_bit = 0;
        clock_hand = (clock_hand + 1) % NUM_FRAMES;
    }
}

アルゴリズム比較

[ページ置換アルゴリズム比較]

アルゴリズム  性能      ベラディ異常  実装コスト  備考
--------    ------    ----------  --------  ----
FIFO        低い      O           低い      最もシンプル
OPT         最適      X           不可能    理論的基準
LRU         良い      X           高い      ハードウェアサポート必要
クロック      良好      X           中程度    LRU近似、実用的

フレーム割り当て（Frame Allocation）

複数のプロセスが実行される時、各プロセスに何個のフレームを割り当てるか決定する必要がある。

割り当て戦略

[フレーム割り当て方式]

1. 均等割り当て：すべてのプロセスに同じ数のフレーム
   100フレーム、5プロセス -> 各20フレーム

2. 比例割り当て：プロセスサイズに比例して割り当て
   総フレーム = 62
   P1サイズ = 10ページ -> 10/137 * 62 = 4.5 -> 5フレーム
   P2サイズ = 127ページ -> 127/137 * 62 = 57.5 -> 57フレーム

グローバル置換 vs ローカル置換

グローバル置換（Global Replacement）: すべてのフレームから犠牲ページを選択。スループットは高いが予測不可能
ローカル置換（Local Replacement）: 該当プロセスのフレーム内でのみ置換。予測可能だが非効率な場合がある

スラッシング（Thrashing）

プロセスが実行よりもページ置換に多くの時間を費やす現象である。

[スラッシング発生過程]

1. プロセスにフレームが不足
2. ページフォルトが頻繁に発生
3. CPU利用率低下（I/O待ち）
4. OSが「CPUが遊んでいる」と判断
5. マルチプログラミング度を増加（プロセス追加）
6. 既存プロセスのフレームがさらに減少
7. さらに多くのページフォルト -> 悪循環！

CPU利用率
  ^
  |        /\
  |       /  \
  |      /    \
  |     /      \------> スラッシング！
  |    /
  |   /
  +--+---+---+---+----> マルチプログラミング度
     1   2   3   4

ワーキングセットモデル（Working-Set Model）

特定の時点でプロセスが活発に使用しているページの集合をワーキングセットと呼ぶ。

[ワーキングセットの概念]

参照列：... 2 6 1 5 7 7 7 7 5 1 6 2 3 4 1 2 3 4 4 4 3 ...
                                            |<-- ウィンドウサイズ (delta) -->|

時点 t1のワーキングセット(delta=10)：
WS(t1) = ページ 1, 2, 3, 4（ウィンドウ内のユニークページ）

ワーキングセットサイズ = 活発に使用中のページ数

[ワーキングセットベースのフレーム割り当て]

総必要フレーム D = すべてのプロセスのワーキングセットサイズの合計

if D > 利用可能フレーム数：
    スラッシング発生の可能性
    -> 一部プロセスを一時中断（swap out）

if D <= 利用可能フレーム数：
    各プロセスにワーキングセットサイズ分のフレームを割り当て
    -> スラッシングを防止

ページフォルト頻度（Page-Fault Frequency）

ワーキングセットより直接的な方法で、ページフォルト率を直接モニタリングする。

[PFFベースのフレーム調整]

ページフォルト率
  ^
  |
  |---- 上限線 ----  フォルト率がこれより上なら：フレームを追加割り当て
  |
  |
  |---- 下限線 ----  フォルト率がこれより下なら：フレームを回収
  |
  +--+---+---+---+----> 割り当てフレーム数

上限線超過：プロセスにフレームを追加割り当て
下限線未満：プロセスからフレームを回収
追加割り当てするフレームがない場合：プロセスを一時中断

メモリマップドファイル（Memory-Mapped Files）

ファイルI/Oをメモリアクセスとして処理する技法である。ファイルの一部または全体をプロセスの仮想アドレス空間にマッピングする。

#include <stdio.h>
#include <sys/mman.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>
#include <string.h>

int main() {
    // ファイルを開く
    int fd = open("data.txt", O_RDWR);
    struct stat sb;
    fstat(fd, &sb);

    // ファイルをメモリにマッピング
    char *mapped = mmap(NULL, sb.st_size,
                        PROT_READ | PROT_WRITE,
                        MAP_SHARED, fd, 0);

    if (mapped == MAP_FAILED) {
        perror("mmap失敗");
        return 1;
    }

    // ファイル内容をメモリのようにアクセス
    printf("ファイル内容：%.50s\n", mapped);

    // メモリに書き込むとファイルも変更される（MAP_SHARED）
    memcpy(mapped, "変更された内容", 21);

    // 変更をディスクに同期
    msync(mapped, sb.st_size, MS_SYNC);

    // マッピング解除
    munmap(mapped, sb.st_size);
    close(fd);

    return 0;
}

[メモリマップドファイルの動作]

プロセス仮想アドレス空間：       物理メモリ：          ディスク：
+------------------+          +-----------+        +-------+
|                  |          |           |        |       |
| mmap領域 ---------|--------->| ファイルページ|<------>| ファイル|
|                  |          |           |        |       |
+------------------+          +-----------+        +-------+

1. mmap()でファイルをアドレス空間にマッピング
2. 該当領域アクセス時にページフォルト -> ファイルからロード
3. メモリ書き込み時にdirtyページとしてマーク
4. 定期的にまたはmunmap時にディスクに書き込み

利点：
- read/writeシステムコールのオーバーヘッドなし
- 複数のプロセスが同じファイルを共有可能
- ページキャッシュを自動的に活用

プロセス間共有メモリとしてのmmap

// プロセス間共有メモリ（MAP_SHARED + MAP_ANONYMOUS）
#include <sys/mman.h>
#include <unistd.h>
#include <stdio.h>
#include <sys/wait.h>

int main() {
    // 匿名共有マッピングを作成
    int *shared = mmap(NULL, sizeof(int),
                       PROT_READ | PROT_WRITE,
                       MAP_SHARED | MAP_ANONYMOUS,
                       -1, 0);

    *shared = 0;

    pid_t pid = fork();

    if (pid == 0) {
        // 子プロセス
        *shared = 42;
        printf("子：shared = %d\n", *shared);
    } else {
        // 親プロセス
        wait(NULL);
        printf("親：shared = %d\n", *shared);
        // 出力：親：shared = 42
        munmap(shared, sizeof(int));
    }

    return 0;
}

まとめ

[仮想メモリ核心概念のまとめ]

+-------------------+--------------------+
| デマンドページング  | 必要な時のみロード   |
| COW               | fork時のコピー最小化 |
+-------------------+--------------------+
| FIFO              | シンプルだが性能が低い |
| OPT               | 理論的最適（実装不可） |
| LRU               | 実用的で性能が良い   |
| クロック           | LRU近似、広く使用    |
+-------------------+--------------------+
| スラッシング        | フレーム不足で       |
|                   | フォルト爆発する現象  |
| ワーキングセット    | 活発なページ集合を   |
|                   | 追跡してスラッシング防止|
+-------------------+--------------------+
| メモリマップドファイル| ファイルI/Oを       |
|                   | メモリアクセスで処理  |
+-------------------+--------------------+

仮想メモリは物理メモリの限界を克服し、プロセスに独立したアドレス空間を提供する核心技術である。デマンドページングで必要なページのみロードし、LRUやクロックアルゴリズムで効率的なページ置換を行い、ワーキングセットモデルでスラッシングを防止する。メモリマップドファイルは効率的なファイルI/Oとプロセス間通信を可能にする。