TT Lab
はじめる
学ぶ 学習パス コース

オペレーティングシステム

ページング — アドレスを翻訳して得た自由

TT Labで続きを見る

一言でいうと

仮想アドレスを固定サイズのページ単位で物理フレームに対応づけると、外部断片化がなくなり、プロセスごとに独立したアドレス空間を与えられます。

なぜ必要なのか

初期の方式は、プロセスごとに連続したメモリの塊をまるごと与えるものでした。この方式はすぐに外部断片化にぶつかります。空き領域の合計は十分なのに、連続した断片がなくて新しいプロセスを載せられない状況です。圧縮(compaction)で詰めて集めることもできますが、その間システムが止まります。

ページングの洞察は単純です。連続していなければならないという要求をなくそうというものです。アドレス空間を固定サイズ(通常4KB)のページに切り分け、物理メモリも同じサイズのフレームに切り分けます。ページをどのフレームにでも入れ、どこに入れたかだけを表に書いておきます。

どう動くのか

仮想アドレスは2つの部分に分かれます。上位ビットがページ番号、下位ビットがオフセットです。ページサイズが4KBなら、オフセットは12ビットです。アドレス変換は、ページ番号をページテーブルで探してフレーム番号に置き換え、オフセットはそのまま付けることです。オフセットには手を触れないので、ページ内の相対位置は保たれます。

ここからすぐに性能の問題が生まれます。ページテーブルはメモリにあるので、メモリアクセス1回のためにメモリを2回読むことになります。この問題をなくすキャッシュがTLB(Translation Lookaside Buffer)です。最近の変換結果を保持しておき、ヒットすれば追加のメモリアクセスなしで、すぐに物理アドレスが得られます。

実効アクセス時間は、次のように計算します。TLBアクセスが20ns、メモリアクセスが100ns、TLBヒット率が80パーセントなら、

ヒット率を98パーセントに上げると、122nsになります。ヒット率の数パーセントが全体の性能を左右するという事実が、ここで見えてきます。

64ビットのアドレス空間ではページテーブル自体が巨大になるので、多段ページテーブルを使います。アドレスを複数の断片に分けて表を木のように階層化し、実際に使われる枝だけを作ります。x86-64は通常4段階です。段階が増えるほどTLBミスのコストが大きくなるため、大きなメモリを使うワークロードでは、ページサイズを大きくするヒュージページ(huge page)が効果を発揮します。2MBページを使うと、同じメモリを512分の1のTLBエントリで覆えます。

現場での姿

データベースやJVMのように、大きなヒープをランダムに走査するプログラムでヒュージページがよく話題になる理由が、TLBです。ただしLinuxの透過的ヒュージページ(THP)は、デフラグメンテーションの遅延のせいで、かえってデータベースでテールレイテンシを生むという報告が多く、PostgreSQLやRedisのドキュメントが、alwaysではなくmadviseか無効化を勧める場合があります。優れた機能でも、ワークロードのアクセスパターンによって結論が分かれるという好例です。

続くクイズで確認すること

アドレスがどう分かれるのか、TLBヒット率が実効アクセス時間をどう変えるのかを計算できるか確認します。