ページング方式

ページング方式 (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がない）。また、ページ単位以下の小さなメモリを要求されてもページ単位でしか割り当てられないというフラグメンテーション（内部断片化）問題もある。

プリページング

スワップ・プリフェッチとも呼ばれる技法で、（参照の局所性を利用して）近い将来参照されると予測したページを事前にロードしておく。プロセスが経験するページフォールト回数を減らす試みである。例えば、ある参照でページフォールトが発生したとき、連続する数ページにもすぐに参照するだろうと予測してまとめてロードしておく、といった戦略がある。また、ある大きなプログラムが終了して多くのメモリを解放したとき、ページアウトされていた他のプログラムがメモリを必要とするだろうと予測して、事前にページインしておくといった戦略もある。

フリーページのキュー

フリーページのキューは、ページフォールト時に使用可能なページフレームのリストである。一部のオペレーティングシステムはページの再利用をサポートしている。すなわち、かつて奪われたが他に再割当てされていないページに対してページフォールトが発生した場合、ページイン処理をせずにフリーとなっている当該ページフレームをそのまま再利用するものである。

ページの事前解放

一部のオペレーティングシステムは、定期的に最近使われていないページを探し、それらをフリーページのキューに追加し、当該ページが更新されていらた（ダーティな場合）、ページアウト処理を行っておく。すると、ページフォールト時に空のページフレームがないということがなく、ページアウトを行う必要がなくなる。

事前クリーニング

UNIXでは、sync を使って定期的に全ダーティページを書き戻してクリーンな状態にする。Windowsでは、"modified page writer" というスレッドが同じことを行っている。
事前クリーニングにより、プログラムの起動や新たなファイルのオープンが高速化される。

ページカラーリング

キャッシュメモリでのスラッシングを防ぐ、あるいは積極的にキャッシュヒット率を向上させようとする物理ページ管理手法をページカラーリングと呼ぶ。ページカラーリングはまた、仮想インデックスキャッシュのエイリアス問題への回避策としても使われた。
キャッシュは年々巨大化しているが、ページサイズは4Kバイトが一般的でこれはページング方式が一般化してから変わっていない。物理アドレスをインデックスとするキャッシュでは、物理ページと仮想ページのマッピングによってはキャッシュ上で現に使用中のページの対応する位置が衝突してしまい、巨大なキャッシュを生かしきれない事態が発生することがある。例えば、キャッシュサイズが16Kバイトでページサイズが4Kバイトであれば、ページはそのアドレスによってキャッシュ上で4種類の位置に対応することが考えられる。この場合、ページのカラー（色）が4種類存在すると称する。
物理インデックスキャッシュでは同時にアクセスする物理ページ群のカラーがばらばらであればスラッシングが発生せず、キャッシュヒット率が向上する。ページカラーリングの実装上の問題は、仮想ページと物理ページのマッピングは一度なされると変更されることがなく、マッピング時点でどのようなメモリアクセスパターンとなるかを予測できない点にある。一般的には仮想ページのカラーと物理ページのカラーが一致するようにマッピングを行う。こうすることで、仮想空間上連続な領域へのアクセスでスラッシングが発生するのを防ぐ。
ただし、そのような実装をした場合に新たな問題が発生する。実行ファイルのテキストとデータの領域は仮想空間上きりのよいアドレスに配置されることが多い。そして、そのアドレスはキャッシュのカラーで言えば同じカラーとなる。従ってページカラーリングを行うシステムでは、カラーによって物理ページの使用率に偏りが発生することがある。するとシステム全体としては未使用メモリが十分であるにも関わらず、特定のカラーの空きページがないためにページ置換アルゴリズムが起動してしまい性能低下するといった問題が発生する。これに対処する方法は様々である。
仮想インデックスキャッシュでは、ある物理ページが複数のプロセスに共有されているとき、そのマッピング先の仮想ページのカラーが異なっていると困った状態となる。同じ物理ページでありながら、キャッシュ上の複数個所に内容が置かれてしまうのである。これをエイリアス問題とかシノニム問題と呼ぶ。この状態をハードウェアが検出せずに放置すると、一方のマッピング経由で更新した内容が他方のマッピング経由では観測できないという事態が発生する。もちろん、ほとんどのシステムではハードウェアが自動的にこの状態を検出して対処するが、その対処による性能低下もある(キャッシュミス時に他のカラーの位置をチェックしてエイリアスがあればそれらのキャッシュラインを全てフラッシュして無効化する)。一時期のシステムでは、この性能低下が無視できないレベルであったため、OSがなるべくエイリアス問題を発生させないようにすることで性能低下を防ぐ必要があった。その際に使用されたのがページカラーリングである。ちなみにR4000では二次キャッシュと一次キャッシュの間の矛盾状態をエイリアス検出に利用していたため、二次キャッシュのないシステムではエイリアス状態を検出することすらできなかった(検出した場合も対処はOS任せである)。最近のシステムではキャッシュの性能向上によってペナルティが無視できるレベルになっているため、エイリアス問題への対策としてページカラーリングを行う必要性は小さくなっている。

可変ページサイズ

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

共有

マルチタスクまたはマルチユーザー環境では、複数のユーザーが同じプログラムを実行するということがよくある。そのプログラムのコピーを各ユーザー用に作成するのはメモリの無駄使いとなる。解決策としては、それらページ群をプロセス間で共有すればよい。
共有する場合、あるプロセスがデータを更新した際に別のプログラムがその更新されたデータにアクセスしないよう注意深く制御しなければならない。これをコピーオンライトと呼ぶ。

用語

歴史的には、「ページング」という用語は可変長のセグメントではなく固定長のページによるメモリ管理を指すこともあり、仮想記憶や二次記憶装置への転送などといった技法を含まないこともある。しかし近年ではそのような用法は稀である。
最近の一部システムでは、「ページング」と同時に「スワッピング」という用語を使っている。歴史的には「スワッピング」はプログラム全体を二次記憶に転送（あるいは二次記憶から主記憶に転送）することを意味する。
1960年代にセグメント方式とページング方式の仮想記憶の概念が登場すると、「スワッピング」という用語はセグメント単位およびページ単位の二次記憶と主記憶間の転送を意味するようになった。今日の仮想記憶はほとんどがページング方式となったため、「スワッピング」は「ページング」とほぼ同義に使われることもある。また、スワップファイルとの間のページインとページアウトのみを「スワッピング」と称することもある。

32ビットハードウェアでのアドレッシングの限界

ページングは、プロセスが使用するアドレス範囲（仮想アドレス空間または論理アドレス空間）をコンピュータに実際に搭載されている物理メモリ（物理アドレス空間）とは異なる大きさにする手段でもある。

仮想アドレス空間より主記憶が小さい場合

多くのシステムでは、プロセスの仮想アドレス空間は利用可能な主記憶よりもずっと大きい。
そのようなシステムでは、プロセスが利用可能な主記憶容量は、実装している主記憶容量より少ない。実装可能な主記憶容量はCPUと主記憶を接続するアドレスバスのビット数で制限されており、例えば、MC68000やi386SXは内部的には32ビットの仮想アドレスを使用していたが、アドレスバスは24ビットぶんのピンしかなく、物理的に接続可能な主記憶容量は16MBに制限されていた。
たとえ物理アドレスのビット数が仮想アドレスのビット数と同じかそれ以上であっても、実際に実装可能な物理主記憶容量はそれより小さいことが多い。それはたとえばコスト的な問題のためだったり、I/O用にアドレス空間がハード的に予約されていたりするためである。

仮想アドレス空間と主記憶が同じサイズの場合

32ビットのコンピュータでPAEなどを使わなければ、最大主記憶容量は4GBまでだが、その限界ぎりぎりまでRAMを搭載したシステムも珍しくない。IBM System/370 はXAモードでもアドレッシング可能な範囲は2GBまでだった。
ページングおよびスワップスペースはこの4GBの限界を超えて使うことができ、そのためにメモリアドレスではなくディスク上の位置でアドレス指定される。
リニアなアドレス空間の32ビットマシンでは、プログラムの仮想アドレス空間は4GBまでに制限されておりが、複数のプログラムでグループを形成すればその制限を越えることも可能である。個々の仮想アドレス空間の総和は、ページテーブルがサポートするプロセスID（または仮想空間ID）のビット数で制限される。
セグメントレジスタ（例えば、System/370のESAモードにおけるアクセスレジスタ）のあるマシンでは、アドレス空間の大きさはOSによってのみ制限され、マッピング用テーブルのサイズだけが問題となる。