- Authors
- Name
- Youngju Kim
- @fjvbn20031
背景
基本概念
CPUが直接アクセスできる記憶装置はレジスタとメインメモリだけである。ディスクのデータは必ずメモリにロードされてからCPUが処理できる。
メモリアクセスには時間がかかるため、CPUとメモリの間にキャッシュを置いて速度差を緩和する。
CPU <-> レジスタ (~1ns) <-> キャッシュ (~10ns) <-> メインメモリ (~100ns)
アドレスバインディング（Address Binding）
プログラムで使用するアドレスを実際のメモリアドレスに変換するプロセスである。バインディングの時点によって3つに分かれる。
[アドレスバインディングの時点]
1. コンパイル時バインディング
- プロセスがメモリのどこにロードされるかコンパイル時に決定
- 位置が変わると再コンパイルが必要
- 例：MS-DOSの.COMプログラム
2. ロード時バインディング
- プログラムをメモリにロードする時にアドレスを決定
- 再配置可能コード（relocatable code）を使用
- ロード後はアドレス変更不可
3. 実行時バインディング（現代のOS）
- 実行中にアドレスを動的に変換
- MMU（Memory Management Unit）ハードウェアが必要
- プロセスをメモリ内で移動可能
論理的アドレスと物理的アドレス
- 論理的アドレス（Logical Address）: CPUが生成するアドレス。仮想アドレスとも呼ぶ
- 物理的アドレス（Physical Address）: 実際のメモリハードウェアのアドレス
[MMUによるアドレス変換]
CPU --[論理アドレス: 346]--> MMU --[物理アドレス: 14346]--> メモリ
|
再配置レジスタ
(基準値: 14000)
物理アドレス = 論理アドレス + 再配置レジスタ値
346 + 14000 = 14346
ユーザープログラムは論理的アドレスのみを扱い、物理的アドレスを直接見ることはできない。
動的ロードと動的リンク
動的ロード: ルーチンが呼び出された時のみメモリにロードする。使用しないルーチンはメモリを占有しないため、メモリ利用率が向上する。
動的リンク: ライブラリを実行時にリンクする。
[静的リンク vs 動的リンク]
静的リンク：
プログラム A: [コード + libcコピー] -- 50MB
プログラム B: [コード + libcコピー] -- 50MB
総メモリ: 100MB
動的リンク（共有ライブラリ）：
プログラム A: [コード + libc参照] -- 10MB
プログラム B: [コード + libc参照] -- 10MB
libc.so: [共有ライブラリ] -- 40MB
総メモリ: 60MB
Linux: .soファイル（Shared Object）
Windows: .dllファイル（Dynamic-Link Library）
連続メモリ割り当て
最もシンプルなメモリ管理方式で、各プロセスを連続したメモリ領域に配置する。
メモリ保護
[ベースレジスタとリミットレジスタ]
ベース(base) リミット(limit)
| |
v v
+-------+=======================+-------+
| OS | プロセスPの領域 | その他 |
+-------+=======================+-------+
0 300040 420940
CPUが生成したアドレス addr に対して：
if (addr >= base && addr < base + limit)
アクセス許可 -> 物理メモリアクセス
else
トラップ発生 -> OSがエラー処理
メモリ割り当て戦略
空き領域（hole）リストからプロセスにメモリを割り当てる方法である。
[メモリ割り当ての例]
初期状態：
|---OS---|--P1--|-------空き-------|--P3--|---空き---|
割り当て戦略：
1. 最初適合（First Fit）：最初の十分な空き領域に割り当て
利点：高速
2. 最適適合（Best Fit）：最小の十分な空き領域に割り当て
利点：小さな残り領域を生成
欠点：全体探索が必要、非常に小さな断片を生成
3. 最悪適合（Worst Fit）：最大の空き領域に割り当て
利点：残り領域が大きく再利用可能
欠点：全体探索が必要
断片化（Fragmentation）
[外部断片化 vs 内部断片化]
外部断片化：
|P1| 空き |P2| 空き |P3| 空き |P4|
100KB 50KB 80KB
総空き領域：230KBなのに200KBのプロセスをロードできない！
（連続領域ではないため）
解決：圧縮（Compaction）- プロセスを一方に移動
|P1|P2|P3|P4|-----230KB空き-----|
内部断片化：
メモリを固定サイズブロックで割り当てる際
プロセスがブロックより小さいと内部に残り領域が発生
プロセスサイズ：18,462バイト
割り当てブロックサイズ：20,000バイト
内部断片化：1,538バイトの無駄
ページング（Paging）
ページングは論理的アドレス空間を非連続的に割り当てて外部断片化を完全に除去する技法である。
基本概念
- ページ（Page）: 論理的メモリを固定サイズブロックに分けたもの
- フレーム（Frame）: 物理的メモリを同じサイズのブロックに分けたもの
- ページテーブル（Page Table）: ページをフレームにマッピングするテーブル
[ページングアドレス変換]
論理アドレス = ページ番号(p) + ページオフセット(d)
例：ページサイズ 4KB (2^12)、論理アドレス 32ビット
上位 20ビット = ページ番号（最大 2^20 = 1Mページ）
下位 12ビット = オフセット（0 ~ 4095）
+--------+--------+
| p (20) | d (12) | 論理アドレス
+--------+--------+
|
v
[ページテーブル]
p -> f（フレーム番号）
|
v
+--------+--------+
| f (20) | d (12) | 物理アドレス
+--------+--------+
[ページングの例]
論理メモリ（4ページ）： 物理メモリ（8フレーム）：
+------+ +------+
|ページ0| ----+ | | フレーム0
+------+ | +------+
|ページ1| --+ | |ページ2| フレーム1
+------+ | | +------+
|ページ2| -+| | | | フレーム2
+------+ || | +------+
|ページ3| || +------------>|ページ0| フレーム3
+------+ || +------+
|+--------------->|ページ1| フレーム4
| +------+
+---------------->|ページ2| フレーム5 (X)
+------+
|ページ3| フレーム6
+------+
| | フレーム7
+------+
ページテーブル：
ページ0 -> フレーム3
ページ1 -> フレーム4
ページ2 -> フレーム1
ページ3 -> フレーム6
TLB（Translation Lookaside Buffer）
毎回ページテーブルをメモリから参照するとメモリアクセスが2倍になる。TLBはページテーブルのキャッシュ役割を果たす。
[TLBによるアドレス変換]
CPU --論理アドレス(p, d)--> TLB検索
|
+---------------+---------------+
| |
TLBヒット TLBミス
(高速、~1ns) (低速)
| |
フレーム f 取得 ページテーブル参照
| フレーム f 取得
| TLBに登録
| |
+---------------+---------------+
|
物理アドレス (f, d)で
メモリアクセス
実効アクセス時間（EAT）計算：
TLBヒット率 = 99%（一般的）
メモリアクセス時間 = 100ns
TLBアクセス時間 = 10ns
EAT = 0.99 * (10 + 100) + 0.01 * (10 + 100 + 100)
= 0.99 * 110 + 0.01 * 210
= 108.9 + 2.1
= 111ns
TLBなし：200ns（メモリ2回アクセス）
TLBあり：111ns（44.5%改善）
ページテーブル構造
プロセスのアドレス空間が大きい場合（例：64ビット）、ページテーブル自体が非常に大きくなる。
階層的ページテーブル（Multi-level Page Table）
[2段階ページテーブル]
32ビットアドレス、4KBページ：
+--------+--------+--------+
| p1(10) | p2(10) | d(12) |
+--------+--------+--------+
外部ページテーブル（1段階）
+---+
| 0 |---> 2段階テーブル A
+---+ +---+
| 1 |--+ | 0 |--> フレーム番号
+---+ | +---+
| 2 | | | 1 |--> フレーム番号
+---+ | +---+
| | ...|
| +---+
|
+-> 2段階テーブル B
+---+
| 0 |--> フレーム番号
+---+
| ...|
+---+
利点：使用していない領域の2段階テーブルは作成しない
-> メモリ節約
ハッシュページテーブル
[ハッシュページテーブル]
論理ページ番号 p をハッシュ関数に入力
-> ハッシュテーブルのスロットにマッピング
-> チェーン（連結リスト）で p を検索
-> 対応するフレーム番号を返す
64ビットアドレス空間のような非常に大きい場合に有用
逆ページテーブル（Inverted Page Table）
[逆ページテーブル]
通常ページテーブル：プロセスごとに1つ（論理 -> 物理）
逆ページテーブル：システムに1つ（物理フレーム -> プロセス、ページ）
物理メモリの各フレームに対して1つのエントリ：
フレーム 0: (PID=5, ページ=3)
フレーム 1: (PID=2, ページ=7)
フレーム 2: (空)
フレーム 3: (PID=5, ページ=0)
...
利点：物理メモリサイズに比例するテーブルサイズ
欠点：アドレス変換時にテーブル全体の検索が必要（ハッシュで解決）
スワッピング（Swapping）
プロセス全体または一部をディスクに退避してメモリを確保する技法である。
[標準スワッピング]
メインメモリ バッキングストア（ディスク）
+---------+ +---------+
| OS | | |
+---------+ | P2の |
| P1 | <-- swap in --- | イメージ |
+---------+ | |
| P3 | --- swap out --> | |
+---------+ +---------+
| 空き |
+---------+
現代のシステムではプロセス全体ではなく
ページ単位でスワッピング（ページスワッピング）
[ページ単位スワッピング]
プロセスの特定のページのみをディスクに移動：
- 長時間使用していないページをswap out
- 必要な時に再びswap in
- 仮想メモリの基盤技術
メモリ保護
ページング環境でのメモリ保護はページテーブルに保護ビットを追加して実装する。
[ページテーブルエントリの構造]
+-------+-----+-----+-----+-------+
| フレーム| 有効 | 読み | 書き | 実行 |
| 番号 | ビット| 可能 | 可能 | 可能 |
+-------+-----+-----+-----+-------+
有効ビット（Valid bit）：
1 = このページがプロセスの論理アドレス空間に属する
0 = 無効なページ（アクセス時にトラップ発生）
保護ビット：
読み取り専用ページへの書き込み試行 -> ハードウェアトラップ
コードページに対して実行のみ許可、書き込み不許可
// メモリ保護の例：mprotectシステムコール
#include <sys/mman.h>
#include <stdio.h>
#include <stdlib.h>
#include <signal.h>
void segfault_handler(int sig) {
printf("セグメンテーションフォルト発生！保護されたメモリへのアクセス試行\n");
exit(1);
}
int main() {
signal(SIGSEGV, segfault_handler);
// ページサイズ単位でメモリ割り当て
size_t page_size = getpagesize(); // 通常 4096
void *ptr = aligned_alloc(page_size, page_size);
// データ書き込み
*(int *)ptr = 42;
printf("値：%d\n", *(int *)ptr);
// メモリを読み取り専用に保護
mprotect(ptr, page_size, PROT_READ);
// 書き込み試行 -> セグメンテーションフォルト！
*(int *)ptr = 100;
free(ptr);
return 0;
}
まとめ
メインメモリ管理はプロセスに効率的で安全なメモリ空間を提供するための核心機能である。MMUが論理的アドレスを物理的アドレスに変換し、ページングが外部断片化を除去し、TLBがアドレス変換性能を保証する。階層的ページテーブルと逆ページテーブルは大容量アドレス空間を効率的に管理し、保護ビットによりプロセス間のメモリ分離を保証する。