ページング方式

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

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

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

利点

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

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

欠点

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

動作原理

ファイル:Paging Addr Ja.JPG

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

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

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

プログラムAが3ページのメモリを要求
プログラムCが2ページのメモリを要求
プログラムDが2ページのメモリを要求
プログラムCが終了し、2ページが解放される
プログラム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のエントリが他のマッピングに転用されるまで、時間のかかるページテーブル参照をせずにマッピング情報が得られる。

ページングと仮想記憶

ページングの主たる機能は、プログラムがその時点で物理メモリ (RAM) のマッピングされていないページにアクセスしようとしたときに実行される。これをページフォールトと呼ぶ。オペレーティングシステムはページフォールトによって制御を得て、プログラムからは見えない形で処理を行う。その流れは次のようになる。

補助記憶装置内での要求されたデータの位置を特定する。
RAM上の空のページフレームを取得。
要求されたデータをそのページフレームにロードする。
ページテーブルを更新してそのページフレームをマッピングする。
要求元プログラムに制御を戻し、ページフォールトを発生した命令を透過的に再実行させる。

これを「ページイン」と呼ぶ。必要とされる全データを格納できるほどRAMがないという状態になるまで、空のページフレームを取得する処理はRAM上の使用中ページを奪う処理を伴わない。全ページフレームが使用中の場合、空のページフレームを得るには使用中のページフレームを選んで空にする処理が必要となる。選択したページフレーム内のデータが前回ロードされてから変更されている場合（いわゆる「ダーティ」状態）、二次記憶装置の対応する位置に書き戻さないと解放できない。これを「ページアウト」と呼ぶ。そうでない場合、選択したページフレームの内容は二次記憶装置の所定の位置にあるものと同じなので、書き戻す必要がない。そのように使用中のページを奪った場合、もともとそのページを使っていたプロセスがそのページにアクセスしようとした場合、同様に空のページフレームを取得して、ページインする必要がある。

効率的なページングシステムは、空にすべきページフレームとして、短期間では必要とされなさそうなページを選択しなければならない。そのためのページ置換アルゴリズムには様々なものがある。多くのオペレーティングシステムは Least Recently Used (LRU) アルゴリズムに類するものを使うか（LRUそのものは現行のハードウェアでの正確な実装は困難である）、ワーキングセットベースのアルゴリズムを使っている。

さらに応答性を向上させるため、ページングシステムはどのページがすぐに必要とされるかを予測する様々な戦略を活用する。プログラムが参照する前に先行的にページをロードするシステムもある。

ページ置換アルゴリズム

テンプレート:Main

デマンドページング

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

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

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

欠点:

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

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

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

プリページング

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

フリーページのキュー

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

ページの事前解放

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

事前クリーニング

UNIXでは、テンプレート:仮リンクを使って定期的に全ダーティページを書き戻してクリーンな状態にする。Windowsでは、"modified page writer" というスレッドが同じことを行っている。

事前クリーニングにより、プログラムの起動や新たなファイルのオープンが高速化される。

スラッシング

テンプレート:Main 多くのプログラムは、ある程度動作すると参照の局所性によって命令フェッチでもデータアクセスでもページフォールトが発生しない安定状態になる。この安定状態で使用しているメモリ量は、そのプログラムが必要とする全メモリ量よりも少ないのが一般的である。この安定状態をワーキングセットなどと呼び、そのプログラムが最も頻繁にアクセスするメモリページ群を意味する。

仮想記憶システムは、物理メモリの総ページ数に対してワーキングセットとして必要とされるページ数が小さいほど効率的であり、ページフォールト処理にかかる時間は性能の支配的要因ではなくなる。非常に巨大なデータ構造を必要とするプログラムはワーキングセットも巨大となる傾向にあり、ページフォールトがコンスタントに発生するためシステム性能が劇的に低下することがある。そのような状況をスラッシングという。

スラッシングの興味深い特性として、ワーキングセットが大きくなってもページフォールト回数はある臨界点まではあまり増えない。その臨界点を越えるとページフォールト回数が劇的に増え、システム性能がそれに支配されるようになる。

その種の極端な例として、IBMの System/360 Model 67 と System/370 で、データ転送命令の機械語がページ境界をまたぎ、データ転送元もページ境界をまたぎ、データ転送先もページ境界をまたいだ場合がある。そのとき、その命令を実行するには8ページがメモリ上になければならない。したがって、最大8回のページフォールトが連続的に発生する可能性があり、スラッシングが発生するといつまでたっても8ページが揃わないという状態になる。

スラッシングを解決する手段として、次のような対策が考えられる。

RAMを増設する（長期的解決策）
同時に実行するプログラムの数を減らす。

ページカラーリング

ファイル:Page Coloring Ja.JPG

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

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

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

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

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

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

可変ページサイズ

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

共有

マルチタスクまたはマルチユーザー環境では、複数のユーザーが同じプログラムを実行するということがよくある。そのプログラムのコピーを各ユーザー用に作成するのはメモリの無駄使いとなる。解決策としては、それらページ群をプロセス間で共有すればよい。

共有する場合、あるプロセスがデータを更新した際に別のプログラムがその更新されたデータにアクセスしないよう注意深く制御しなければならない。これをコピーオンライトと呼ぶ。

用語

歴史的には、「ページング」という用語は可変長のセグメントではなく固定長のページによるメモリ管理を指すこともあり、仮想記憶や二次記憶装置への転送などといった技法を含まないこともある^[2]^[3]。しかし近年ではそのような用法は稀である。

最近の一部システムでは、「ページング」と同時に「スワッピング」という用語を使っている。歴史的には「スワッピング」はプログラム全体を二次記憶に転送（あるいは二次記憶から主記憶に転送）することを意味する^[4]^[5]。

1960年代にセグメント方式とページング方式の仮想記憶の概念が登場すると、「スワッピング」という用語はセグメント単位およびページ単位の二次記憶と主記憶間の転送を意味するようになった。今日の仮想記憶はほとんどがページング方式となったため、「スワッピング」は「ページング」とほぼ同義に使われることもある。また、スワップファイルとの間のページインとページアウトのみを「スワッピング」と称することもある。

性能

仮想記憶のバッキングストアはRAMに比べると何十倍も遅い。しかも機械的可動部分があるとさらに遅延が生じ、ハードディスクでは数ミリ秒単位の遅延になることもある。したがってスワッピング（ページアウト）は発生させないに越したことはない。OSによってはカーネルのそのあたりの動作に影響する設定が可能なものもある。

Linuxでは /proc/sys/vm/swappiness というパラメータがあり、値を大きく設定するほど積極的なページアウト（空きページフレームを作る）を行う。
Windowsでは DisablePagingExecutive というレジストリ設定があり、カーネルモードのコードやデータをページアウトの対象外とするか否かを指定できる。
メインフレームでは、シーク時間を除去すべくトラック毎にヘッドのある磁気ディスクや磁気ドラムをページングに使用し、回転レイテンシを削減すべく同一デバイスに複数の要求を同時に発行する技法を使っている^{[注 2]}。
フラッシュメモリは消去・書き込み回数が有限であり、一度に消去する範囲が大きく（例えば、Intel X25-M SSD^[6] では128KiB）、ページサイズの何倍ということもある。したがって、フラッシュメモリをメモリ容量に余裕がない状況でスワップファイルに使用するとすぐに消耗するかもしれない。しかし、ハードディスクに比べて遅延が極めて小さく、RAMのように揮発性でないという点は魅力的である。ReadyBoost や Intel Turbo Memory といった方式はそういった利点を利用したものである。

Unix系OSの多く（例えば、AIX、Linux、Solaris）は複数のデバイスを並列にスワップスペースとして使用でき、性能を向上させることができる。

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

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

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

多くのシステムでは、プロセスの仮想アドレス空間は利用可能な主記憶よりもずっと大きい^[7]。

そのようなシステムでは、プロセスが利用可能な主記憶容量は、実装している主記憶容量より少ない。実装可能な主記憶容量は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モードにおけるアクセスレジスタ^[8]）のあるマシンでは、アドレス空間の大きさはOSによってのみ制限され、マッピング用テーブルのサイズだけが問題となる。

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

仮想アドレス空間より主記憶容量が大きいコンピュータも少数ながら存在する。例えば、Magic-1、PDP-11シリーズの一部機種、物理アドレス拡張付きの32ビットプロセッサなどである^[7]。

この場合、あるプロセスは仮想アドレス空間以上の主記憶を使うことができないため、仮想記憶の主たる利点が無効となる。したがってそのようなシステムでは、次のような別の利点を求めてページングを採用する。

余分なメモリをよく使用するファイルやメタデータ（ディレクトリ情報など）のキャッシュ、すなわちページキャッシュとして使用する。
複数の仮想アドレス空間をサポートし（一般に「プロセスID」をページテーブルに持たせる）、大きな主記憶容量をより多くのプロセスを動作させるのに使う。

複数の仮想アドレス空間の総和は、ページテーブルがサポートするプロセスID（または仮想空間ID）のビット数、または使用可能な二次記憶装置の総量で制限される。

脚注

注釈

テンプレート:Reflist

出典