ページング方式

ページング方式 (Paging) とは、コンピュータのオペレーティングシステムにおいて記憶装置をページと呼ばれる小さな単位に分割して割り当てを行うアルゴリズム群である。仮想記憶のベースとなる設計の一つ。

物理メモリ空間および論理メモリ空間を、基本的に一定サイズのページと呼ばれる単位に分割して管理を行う。論理メモリから物理メモリ空間への対応づけはページテーブルと呼ばれる構造体で実現され、この構造体はオペレーティングシステム (OS) によって管理される。物理メモリ空間に対応づけられていない論理メモリを参照した時にはページフォルトという例外によってOS側の例外処理ルーチンに制御が移行し、OS側の管理によって適宜対応したページを二次記憶等から読み込み、テーブルを更新してその参照した命令の実行に戻る。

これを実現するハードウエアであるメモリ管理ユニット (MMU) の中にはトランスレーション・ルックアサイド・バッファ (Translation Lookaside Buffer:TLB) と呼ばれる一種のキャッシュがあり、ユニット内部ではこの対応表に基づいてアドレスの対応づけを行っている。このテーブルから参照出来なかったときをTLBミスと呼ぶ。このときの処理はMMUの設計によって異なり、MMU内にはTLBのみを持ちTLBミスが即例外を起こし、OSがページテーブルを引いてTLBに追加することによってTLBミスを解決するアーキテクチャや、ページテーブル自体のフォーマットがOSが使えるビットを含めた形でMMUによって定義されていて、TLBミス時にMMU自身が与えられた物理アドレスにあるページテーブルを参照するアーキテクチャもある。

利点

他の動的メモリアロケーションに比較して、ページング方式ではプログラムに割り当てるメモリが連続である必要がなく、大きなフラグメンテーション（外部断片化）がほとんど発生しないため、メモリを無駄にしない。

プログラムは、ある時点でそのコードとデータを全て使用するわけではない（参照の局所性）。そのため、必要に応じてページをディスクに書き込んだり、ページの内容をディスクから読み込んだりすることで仮想記憶のコンセプトを実装できる。この点もページング方式が他のメモリアロケーション手法よりも優れている点である。

欠点

ページング方式の主な問題点は、それを実装するコードが相対的に複雑になる点であり、特に仮想記憶を実現しようとすると複雑化する。他にはMMUが必要になるという問題もあり、古くて小さいマイクロプロセッサでページングを実装するのは困難である（例えば、x86シリーズでは、i386以上でないとページングをサポートしたMMUがない）。また、ページ単位以下の小さなメモリを要求されてもページ単位でしか割り当てられないというフラグメンテーション（内部断片化）問題もある。

動作原理

ページング方式のアドレス変換の概念図

ページング方式では、実際のメモリアクセスはページテーブルを使用してメモリ管理ユニットがハードウェアレベルで制御する。前述の通り、物理メモリはページと呼ばれる小さなブロックに分割される。各ページにはページ番号が付与される。OSは未使用のページのリストを保持するか、メモリ使用要求があったときに毎回メモリを調べる（最近のOSでは前者の実装が一般的）。いずれにしても、プログラムがメモリを要求したとき、OSがそのプログラムに何ページかのメモリを割り当て、それをプログラム（プロセス）毎に割り当て中のページを管理するリストに入れておく（訳注:ページそのものはプログラムが使用するので、それをリストに入れるわけではなく、物理ページを管理するデータ構造を別途作成してリストに入れる）。具体例を以下に示す。

以下のような順番でページの割り当てが行われたときのページアロケーションリストをテーブルに示す。

1. プログラムAが3ページのメモリを要求
2. プログラムCが2ページのメモリを要求
3. プログラムDが2ページのメモリを要求
4. プログラムCが終了し、2ページが解放される
5. プログラムBが3ページのメモリを要求し、先にCが解放した2ページを割り当て、さらに残りの1ページを割り当てる

ページ番号	ページ割り当て先	物理メモリアドレス
0	プログラム A.0	1000:0000
1	プログラム A.1	1000:1000
2	プログラム A.2	1000:2000
3	プログラム B.0	1000:3000
4	プログラム B.1	1000:4000
5	プログラム D.0	1000:5000
6	プログラム D.1	1000:6000
7	プログラム B.2	1000:7000

結果として、各プログラムのページテーブルには、以下のようなマッピングが格納される（「プログラムのページ番号 → OSのページ番号」）。

• プログラムA: 0 → 0、1 → 1、2 → 2
• プログラムB: 0 → 3、1 → 4、2 → 7
• プログラムD: 0 → 5、1 → 6

ここで、プログラムが自身に割り当てられたメモリにアクセスしようとしたときに何が起きるかを示す。プログラムA が "LOAD memory at 20FE"（20FE番地からロード）という命令を実行したとする。

20FE（16進数）を2進数表記すると（16ビットシステムでは） 0010000011111110 となる。ページサイズは4Kバイトとする。従って、20FE番地のメモリ参照要求を受けると MMU は以下のようにこのアドレスを見る。

0010000011111110         =   20FE
|__||__________|
 |       |
 |       v
 v       ページ内相対メモリアドレス (00FE)
ページ番号 (2)

ページサイズが4096バイトなので、MMUはアドレスの先頭（最上位桁ビット群）4ビットをページ番号、残りの12ビットをページ内相対メモリアドレスとして扱う。ページサイズが2048バイトなら、MMUは先頭5ビットをページ番号、残り11ビットをページ内相対メモリアドレスとして扱うだろう。つまり、ページサイズが小さければページ数が多くなる。

従って、このメモリアクセス要求がなされると、MMUはそのプログラムのページテーブルを参照してマッピングされているOSのページ番号を得る。この例の場合、プログラムAの2番目のページはOSの2番目のページにマップされている。次いで、OSページ番号に対応する物理マッピングを得る。2番目のOSページは物理メモリアドレス 1000:2000 に対応しており、プログラムが参照しようとしているアドレスのページ内相対アドレスは 00FE なので、MMU は物理アドレス 1000:20FE の位置のメモリにアクセスする。

以上はあくまでも概略である。最近のコンピュータ・アーキテクチャでは様々な手段でページングを高速化している。例えば、i386 系アーキテクチャのプロセッサも他のプロセッサと同様にTLBと呼ばれる特殊なキャッシュを持っていて、過去にアクセスした仮想アドレスと物理アドレスのマッピングを保持する。従って一度ページテーブルを参照してマッピング情報を得たら、スワップアウトされたりTLBのエントリが他のマッピングに転用されるまで、時間のかかるページテーブル参照をせずにマッピング情報が得られる。

ページングと仮想記憶

ページングが仮想記憶と共に使用されるとき、OSは使用されているページ全体について最近の使用状況を監視し、今後の使用を予測しなければならない。そしてOSが適当だと判断したとき（空きメモリが少なくなったと判断したとき）やプログラムがスワップアウトされたページにアクセスしようとしたとき、OSはページを選択してディスクにスワップアウトし、別のページの内容をメモリに持ってくる（詳しくはページ置換アルゴリズムを参照されたい）。これによって物理的なメモリ容量以上のメモリを使用することができる。

デマンドページング

アクセスしようとしたときに物理メモリをページに割り当てる方式をデマンドページング (Demand Paging) と呼ぶ。換言すれば、ページフォールトが発生したときに物理メモリを割り当てるのである。プロセスが実行を開始したとき物理メモリは割り当てられておらず、プロセスのワーキングセットの大部分が物理メモリに置かれるまでページフォールトが発生し続けることになる。これは遅延ロード技法の一例である。

デマンドページングの利点:

• アクセスされないページはロードされない。そのため、メモリ使用量が節約され、マルチプログラミング（マルチタスク）の度合いを向上させる。
• プログラム実行開始前のロードによる遅延がない。
• ページの読み込みが最小限なのでディスク負荷が少ない。
• ページは更新されるまで複数のプログラムから共有され、コピーオンライトによってさらにリソースを節約できる。
• 実装メモリ量よりも巨大なプログラムを実行できる。オーバーレイという古い技術よりも優れている。
• 本来のページング方式が必要とする以上のハードウェア機構を必要としない。

欠点:

• プログラムが任意の仮想ページに初めてアクセスする際、遅延が発生する。そこでプリページングという技法で以前に動作したときに使用していたページを覚えておき、スケジューリングによって実行される際にそれらのページを予め物理メモリにロードしておいて性能向上を図ることもある。また、特にアクセスしていたページを覚えておかなくとも、プログラムカウンタとスタックポインタの指している仮想ページだけでも予めロードしておけばある程度の性能向上は図れる。
• ページ置換アルゴリズムに関わるメモリ管理は複雑化しつつある。

LinuxのようなUNIX系システムでは、mmap() システムコールもデマンドページングによって実装されている。それは新たなプログラムを実行する際にも適用される。OSは実行ファイル（とそれが依存するライブラリ群）をマッピングするが、そのときにファイルの中身を物理メモリ上に実際にロードすることはない。マッピングがリードオンリーで共有可能であれば、物理メモリに残っている内容をそのまま使って実行することもある。これをページキャッシュと呼ぶ。

使われていない物理ページには、スワップ領域以外のファイルに対応するページキャッシュと何とも対応していない完全な未使用ページがある。一般にページング方式では、新たに必要となったページがページキャッシュにあればそれを再利用し、なければ完全に未使用のページを使用する。使い終わったページは、その内容がスワップ領域以外に対応していればページキャッシュとしてそのまま内容が保持され、スワップ領域に対応していた匿名 (Anonymous) ページは完全な未使用ページに戻される。もちろん、完全な未使用ページを使い切った上でさらにメモリを使用しなければならないときにはページキャッシュが他の用途に利用される。このようにして、現に使用中でない物理メモリを有効活用してなるべくディスクアクセスを減らすように工夫している。ちなみに、ページキャッシュとして存在する領域をmmap() でマッピングするとページキャッシュがそのまま使われるが、read() システムコールで読む場合にはユーザーバッファへのコピーが発生する。

ページカラーリング

ページカラーリングの概念図

キャッシュメモリでのスラッシングを防ぐ、あるいは積極的にキャッシュヒット率を向上させようとする物理ページ管理手法をページカラーリングと呼ぶ。ページカラーリングはまた、仮想インデックスキャッシュのエイリアス問題への回避策としても使われた。

キャッシュは年々巨大化しているが、ページサイズは4Kバイトが一般的でこれはページング方式が一般化してから変わっていない。物理アドレスをインデックスとするキャッシュでは、物理ページと仮想ページのマッピングによってはキャッシュ上で現に使用中のページの対応する位置が衝突してしまい、巨大なキャッシュを生かしきれない事態が発生することがある。例えば、キャッシュサイズが16Kバイトでページサイズが4Kバイトであれば、ページはそのアドレスによってキャッシュ上で4種類の位置に対応することが考えられる。この場合、ページのカラー（色）が4種類存在すると称する。

物理インデックスキャッシュでは同時にアクセスする物理ページ群のカラーがばらばらであればスラッシングが発生せず、キャッシュヒット率が向上する。ページカラーリングの実装上の問題は、仮想ページと物理ページのマッピングは一度なされると変更されることがなく、マッピング時点でどのようなメモリアクセスパターンとなるかを予測できない点にある。一般的には仮想ページのカラーと物理ページのカラーが一致するようにマッピングを行う。こうすることで、仮想空間上連続な領域へのアクセスでスラッシングが発生するのを防ぐ。

ただし、そのような実装をした場合に新たな問題が発生する。実行ファイルのテキストとデータの領域は仮想空間上きりのよいアドレスに配置されることが多い。そして、そのアドレスはキャッシュのカラーで言えば同じカラーとなる。従ってページカラーリングを行うシステムでは、カラーによって物理ページの使用率に偏りが発生することがある。するとシステム全体としては未使用メモリが十分であるにも関わらず、特定のカラーの空きページがないためにページ置換アルゴリズムが起動してしまい性能低下するといった問題が発生する。これに対処する方法は様々である。

仮想インデックスキャッシュでは、ある物理ページが複数のプロセスに共有されているとき、そのマッピング先の仮想ページのカラーが異なっていると困った状態となる。同じ物理ページでありながら、キャッシュ上の複数個所に内容が置かれてしまうのである。これをエイリアス問題とかシノニム問題と呼ぶ。この状態をハードウェアが検出せずに放置すると、一方のマッピング経由で更新した内容が他方のマッピング経由では観測できないという事態が発生する。もちろん、ほとんどのシステムではハードウェアが自動的にこの状態を検出して対処するが、その対処による性能低下もある(キャッシュミスヒット時に他のカラーの位置をチェックしてエイリアスがあればそれらのキャッシュラインを全てフラッシュして無効化する)。一時期のシステムでは、この性能低下が無視できないレベルであったため、OSがなるべくエイリアス問題を発生させないようにすることで性能低下を防ぐ必要があった。その際に使用されたのがページカラーリングである。ちなみにR4000では二次キャッシュと一次キャッシュの間の矛盾状態をエイリアス検出に利用していたため、二次キャッシュのないシステムではエイリアス状態を検出することすらできなかった(検出した場合も対処はOS任せである)。最近のシステムではキャッシュの性能向上によってペナルティが無視できるレベルになっているため、エイリアス問題への対策としてページカラーリングを行う必要性は小さくなっている。

可変ページサイズ

前述の通り、ページングとはメモリ空間を一定サイズのページに分けるのが基本であるが、TLBミスが多発すると実行効率が落ち、またTLBミスをソフトウエアで扱う時TLBフォールトハンドラをどう置くかという問題がある。このため、いくつかのMMUの設計では、最小ページサイズの倍数（多くは2の冪乗倍）サイズのページをサポートしている。OSのメモリ管理に可変ページサイズをサポートさせると、断片化等の関係で設計が複雑になるため、サポートされない事があるが(このサポートのことをスーパーページと言う)、その場合でもOS自身を巨大なページに置く事によって実行効率を上げる事が出来るので、そのような設計になっている事が多い。また、後者の問題の解決の一つとしても使用される事がある。（その場合は、あるページをTLBから追い出されない事を保証出来るようになっている。）また、OS用にアドレス変換されない領域を用意するMMUの設計も存在する。

関連項目

• メモリ保護機能
• キャッシュアルゴリズム