仮想メモリ

実装: foundations/virtmem/ / 実行: go test ./foundations/virtmem/

各プロセスは自分だけの連続メモリを持つかに振る舞える。だが物理メモリは1つで、多数のプロセスが分け合う。この錯覚を作るのが仮想メモリだ。仮想アドレスをMMUが物理へ変換する。上位のページ番号と下位のオフセットに分け、ページテーブルでフレームを引く。未割り当てのページに触るとページフォルトが起き、そこで初めてフレームを渡す。アドレス変換・デマンドページング・TLB・隔離を実装する。

この章で作るもの

メモリアロケータで、1 枚の連続したメモリを切り分ける話をした。だが、そもそもプログラムが見ている「連続したメモリ」自体が作り物だ。あなたのプログラムは 0 番地から始まる広大なアドレス空間を、自分が独占しているかのように使える。だが実際には、物理メモリは 1 つしかなく、何十ものプロセスがそれを分け合っている。しかも各プロセスは互いのメモリを覗けない。この「みんなが自分専用の連続メモリを持っている」という錯覚を成立させているのが仮想メモリだ。

仕組みの中心はアドレス変換にある。プログラムが触るのは仮想アドレスで、これは実在しない。CPU の中の MMU(Memory Management Unit)が、アクセスのたびに仮想アドレスを本物の物理アドレスへ変換する。変換はページ単位で行う。仮想アドレスを、上位のページ番号と下位のページ内オフセットに分ける。ページ番号を、ページテーブルという対応表で物理フレーム番号に引き、オフセットはそのまま付ける。プロセスごとに別のページテーブルを持たせれば、同じ仮想アドレスでも別の物理フレームを指すので、互いに干渉しない(隔離)。まだ物理メモリを割り当てていないページに触ると、ページフォルトが起きて、そこで初めてフレームを渡す(デマンドページング)。この章では、この変換の仕組みを実装する。

仮想アドレス 0x0140
 ┌─ページ番号 1─┬─オフセット 0x40─┐
 │              │                 │
 ▼ ページテーブル                  │
 ページ1 → フレーム N              │(オフセットはそのまま)
 └──────────┬───────────────────┘
            ▼
物理アドレス = フレームN << bits | 0x40

プロセスA: 仮想0x40 → フレーム0    別テーブル
プロセスB: 仮想0x40 → フレーム1  → 同じ仮想でも別の物理(隔離)

アドレス変換。仮想アドレスをページ番号とオフセットに分け、ページテーブルでフレームを引く。プロセスごとに別のテーブルなので同じ仮想アドレスが別の物理を指す

順に見ていく。

アドレス変換: 仮想アドレスをページ番号+オフセットに分け、ページテーブルでフレームを引く。オフセットは変わらない
デマンドページングと TLB: 未割り当てページはフォルトで初めて割り当てる。変換は TLB という小さなキャッシュで速くする
プロセス隔離: プロセスごとに別のページテーブル。同じ仮想アドレスが別の物理フレームを指すので、互いに干渉しない

① アドレス変換: ページ番号とオフセット

まず変換の土台を作る。仮想アドレスを 2 つに割る。ページサイズが 256(= 2^8)なら、下位 8 ビットがページ内オフセット、それより上がページ番号だ:


var (
	// ErrSegfault はアドレス空間に含まれない(未マップの)ページに触ったとき。
	ErrSegfault = errors.New("virtmem: segmentation fault")
	// ErrOOM は割り当てる物理フレームが尽きたとき。
	ErrOOM = errors.New("virtmem: out of physical frames")
)

// FrameAllocator は物理フレームを配る(全プロセスで共有する物理メモリの管理役)。
type FrameAllocator struct {
	next uint
	max  uint
}

// NewFrameAllocator は max フレームぶんの物理メモリを作る。
func NewFrameAllocator(max uint) *FrameAllocator { return &FrameAllocator{max: max} }

func (fa *FrameAllocator) alloc() (uint, bool) {
	if fa.next >= fa.max {
		return 0, false
	}
	f := fa.next
	fa.next++
	return f, true
}

// MMU は 1 プロセスぶんのアドレス変換器(ページテーブル + TLB)。
type MMU struct {
	pageSize uint
	pageBits uint // log2(pageSize)。オフセットのビット幅
	fa       *FrameAllocator

	valid map[uint]bool // このページはアドレス空間に含まれるか
	frame map[uint]uint // ページ番号 → 物理フレーム(常駐しているページ)
	tlb   map[uint]uint // ページ番号 → フレーム(直近の変換キャッシュ)

	Hits, Misses, Faults int // 観測用
}

// New は pageSize(2 の冪)のページを使う MMU を作る。fa は物理フレームの供給元。
func New(pageSize uint, fa *FrameAllocator) *MMU {
	return &MMU{
		pageSize: pageSize,
		pageBits: uint(bits.TrailingZeros(pageSize)),
		fa:       fa,
		valid:    map[uint]bool{},
		frame:    map[uint]uint{},
		tlb:      map[uint]uint{},
	}
}

// Map は [vpageStart, vpageStart+count) のページをアドレス空間に加える。
// この時点では物理フレームは割り当てない(触れられて初めて割り当てる)。
func (m *MMU) Map(vpageStart, count uint) {
	for i := uint(0); i < count; i++ {
		m.valid[vpageStart+i] = true
	}
}

ページを固定サイズにするのが肝で、これでアドレスの下位ビットがそのままオフセットになる。ビットシフトとマスクだけで、ページ番号とオフセットに一瞬で分けられる。Map は、どのページがそのプロセスのアドレス空間に含まれるかを登録する。ただしこの時点では物理フレームは割り当てない。実際に触られて初めて割り当てる。物理フレームを配る FrameAllocator は全プロセスで共有する。1 つしかない物理メモリを分け合う様子を、この共有が表している。

② 変換とページフォルト、TLB

変換の本体だ。仮想アドレスを受け取り、ページ番号を引いて物理アドレスを組み立てる。手順は 3 段。まず TLB(直近の変換のキャッシュ)を引き、当たれば即返す。外れたらページテーブルを引く。まだ物理フレームが無ければ、ページフォルトを起こしてフレームを割り当てる:


// Translate は仮想アドレスを物理アドレスに変換する。
// 手順: TLB を引く → なければページテーブル → 未常駐ならページフォルトで割り当て。
func (m *MMU) Translate(vaddr uint) (uint, error) {
	vpage := vaddr >> m.pageBits       // 上位 = ページ番号
	offset := vaddr & (m.pageSize - 1) // 下位 = ページ内オフセット

	// 1. TLB(直近の対応のキャッシュ)を引く。当たれば一発。
	if f, ok := m.tlb[vpage]; ok {
		m.Hits++
		return f<<m.pageBits | offset, nil
	}
	m.Misses++

	// 2. アドレス空間に含まれないページ = segfault。
	if !m.valid[vpage] {
		return 0, ErrSegfault
	}

	// 3. ページテーブルを引く。まだ物理フレームが無ければページフォルト。
	f, resident := m.frame[vpage]
	if !resident {
		m.Faults++
		var ok bool
		f, ok = m.fa.alloc() // ここで初めて物理フレームを割り当てる(デマンドページング)
		if !ok {
			return 0, ErrOOM
		}
		m.frame[vpage] = f
	}

	m.tlb[vpage] = f // 次回のために TLB に載せる
	return f<<m.pageBits | offset, nil
}

// FlushTLB は TLB を空にする(文脈切替時などに実際に行われる)。
func (m *MMU) FlushTLB() { m.tlb = map[uint]uint{} }

// FrameOf は vpage に割り当てられた物理フレームを返す(観測用。未常駐なら false)。
func (m *MMU) FrameOf(vpage uint) (uint, bool) {
	f, ok := m.frame[vpage]
	return f, ok
}

デマンドページングがここにある。Map で登録しただけのページは、まだ物理メモリを持たない。初めてアクセスされたときに Faults が上がり、FrameAllocator からフレームを 1 枚もらって割り当てる。使わないページには物理メモリを一切使わない。だから、確保した以上のメモリをプログラムに見せられる(実際に触ったぶんだけ物理を消費する)。アドレス空間に無いページ(Map していない)に触れば segfault(不正アクセスとしてプロセスを止める)、物理フレームが尽きれば OOM(メモリ切れ)だ。テストで、初回アクセスでフォルトが 1 回起き 2 回目はフォルトしないこと、未マップアクセスが segfault になることを固定した。

TLB(Translation Lookaside Buffer)も要だ。ページテーブルを引くのは、実物では複数回のメモリアクセスを伴い遅い。同じページには連続してアクセスすることが多い(プログラムの局所性)ので、直近の「ページ番号→フレーム」を小さなキャッシュに覚えておけば、大半の変換が一発で済む。テストで、同じページの再アクセスが TLB ヒットになり、FlushTLB すると再びミスすることを固定した。プロセスを切り替えるとページテーブルが変わるので、TLB は流す必要がある。

③ プロセス隔離: 同じ番地が別の場所を指す

仮想メモリの最大の恩恵が隔離だ。2 つのプロセスが、まったく同じ仮想アドレス(たとえば 0x40)に書き込んでも、互いのデータを壊さない。なぜなら、プロセスごとに別のページテーブルを持つからだ。

上の設計で、MMU は 1 プロセスぶんのページテーブルと TLB を持ち、物理フレームを配る FrameAllocator だけを共有する。プロセス A が仮想 0x40 に触るとフレーム 0 が割り当てられ、プロセス B が同じ仮想 0x40 に触ると、別のフレーム 1 が割り当てられる。同じ仮想アドレスなのに、変換の先が違う。テストで、2 プロセスが同じ仮想アドレスを使っても、異なる物理アドレス・異なるフレームを指すことを固定した。この隔離があるから、あるプロセスのバグが別のプロセスを巻き込まず、悪意あるプログラムも他人のメモリを直接は読めない。仮想メモリは、性能(デマンドページング)より前に、まず安全(隔離)のための仕組みだ。

動かす

下のデモは、2 つのプロセスが仮想アドレスにアクセスする様子を見る。アドレスがページ番号とオフセットに分かれ、ページテーブルで物理フレームに変換され、初回はページフォルトが起き、同じページの再アクセスは TLB ヒットになる。そして同じ仮想アドレスが、プロセスごとに別の物理を指す隔離を確かめてほしい。

デモ仮想メモリ(アドレス変換)物理フレーム 0/8 使用

アクセスボタンを押すと、仮想アドレスが物理アドレスに変換される様子が出る

プロセスA のページテーブルfault 0 / hit 0

ページ0→(未割当)

ページ1→(未割当)

ページ2→(未割当)

ページ3→(未割当)

プロセスB のページテーブルfault 0 / hit 0

ページ0→(未割当)

ページ1→(未割当)

ページ2→(未割当)

ページ3→(未割当)

仮想アドレスを上位のページ番号と下位のオフセットに分け、プロセスごとのページテーブルでフレームを引く。未割当ページへの初回アクセスはページフォルトで、そこで初めて物理フレームを渡す(デマンドページング)。同じページの再アクセスは TLB ヒットで一発。注目は隔離で、プロセスAとBが同じ仮想 0x0040 に触っても、別々のテーブルなので別のフレーム(別の物理)を指す。だから互いのメモリを壊さない。

設計の観点

隔離が第一の目的: 仮想メモリはまず、プロセスを互いから守るためにある。同じ仮想アドレスが別の物理を指すことで、干渉も覗き見も防ぐ。性能はその次
多段ページテーブル: 64bit のアドレス空間を単段の表で持つと巨大すぎる。実物は多段(x86-64 は 4 段)にして、使う部分だけ表を作る(疎な表現)
TLB が性能を左右する: 変換は全メモリアクセスで起きるので、TLB ミスは重い。局所性を壊すアクセス(巨大な配列を飛び飛びに)は TLB ミスを増やし、遅くなる
デマンドページングと over-commit: 触るまで物理を割り当てないので、物理より多くの仮想メモリを約束できる。全員が一斉に触ると足りなくなり、OOM killer やスワップが動く
スワップ: 物理が足りないとき、使っていないページをディスクへ退避し、フレームを空ける。ページフォルトでディスクから戻す。物理より大きなメモリの錯覚を支えるが、遅い(スラッシング)

対照と実例

概念	役割
ページ番号 + オフセット	仮想アドレスの分割。変換の単位
ページテーブル	ページ番号 → 物理フレーム。プロセスごと
ページフォルト	未割り当てページへのアクセス。割り当ての契機
TLB	変換のキャッシュ。局所性で大半を一発に
フレーム	物理メモリのページ単位。全プロセスで共有

裏どり:

x86-64 のページング: 4 段(または 5 段)のページテーブルと 4KB ページ。CR3 レジスタが現在のページテーブルを指す
TLB とコンテキストスイッチ: プロセス切替で TLB を流すコストを避けるため、ASID(アドレス空間 ID)でエントリを区別する仕組みがある
mmap / デマンドページング: ファイルやゼロ埋めページを仮想空間に写像し、触られたときに物理を割り当てる。この章のフォルト機構の応用
Meltdown / Spectre: 仮想メモリの隔離を投機実行の副作用で破った攻撃。隔離の重要さと難しさを示した

簡略化したこと

単段ページテーブル: 実物は多段で疎に表す。ここは 1 段のマップ
TLB は無限: 実物は固定サイズで追い出しがある。ここは全部覚える
スワップなし: フレーム枯渇でディスクへ退避せず OOM にする
保護ビットなし: 読み書き実行の権限やダーティビットは扱わない

参考資料

OSTEP: Paging — ページングとアドレス変換の定番教材
OSTEP: TLBs — TLB の仕組みと性能
What Every Programmer Should Know About Memory (Drepper) — 仮想メモリと TLB の実務的影響
実装: foundations/virtmem

仮想メモリ ​

この章で作るもの ​

① アドレス変換: ページ番号とオフセット ​

② 変換とページフォルト、TLB ​

③ プロセス隔離: 同じ番地が別の場所を指す ​

動かす ​

設計の観点 ​

対照と実例 ​

簡略化したこと ​

参考資料 ​