「ページング方式」の版間の差分
(36人の利用者による、間の48版が非表示) | |||
1行目: | 1行目: | ||
'''ページング方式'''('''Paging''')とは、[[コンピュータ]]の[[オペレーティングシステム]]において[[記憶装置]]をページと呼ばれる小さな単位に分割して割り当てを行うアルゴリズム群である。[[仮想記憶]]のベースとなる設計の一つ。 |
'''ページング方式''' ('''Paging''') とは、[[コンピュータ]]の[[オペレーティングシステム]]において[[記憶装置]]をページと呼ばれる小さな単位に分割して割り当てを行う[[アルゴリズム]]群である。[[仮想記憶]]のベースとなる設計の一つ。 |
||
物理メモリ空間および論理メモリ空間を、基本的に一定サイズのページと呼ばれる単位に分割して管理を行う。 |
[[主記憶装置|物理メモリ]]空間および[[仮想記憶|論理メモリ]]空間を、基本的に一定サイズのページと呼ばれる単位に分割して管理を行う。論理メモリから物理メモリ空間への対応づけは[[ページテーブル]]と呼ばれる構造体で実現され、この構造体は[[オペレーティングシステム]] ('''OS''') によって管理される。物理メモリ空間に対応づけられていない論理メモリを参照した時には[[ページフォールト|ページフォルト]]という[[例外処理|例外]]によってOS側の[[例外処理]][[ルーチン]]に制御が移行し、OS側の管理によって適宜対応したページを[[補助記憶装置|二次記憶]]等から読み込み、[[テーブル (情報)#プログラミング|テーブル]]を更新してその参照した命令の実行に戻る。 |
||
これを実現するハードウエアである[[メモリ管理ユニット]]('''MMU''')の中には[[トランスレーション・ルックアサイド・バッファ]](''Translation Lookaside Buffer'':'''TLB''')と呼ばれる一種のキャッシュがあり、ユニット内部ではこの対応表に基づいてアドレスの対応づけを行っている。このテーブルから参照出来なかったときをTLBミスと呼ぶ。このときの処理はMMUの設計によって異なり、MMU内にはTLBのみを持ちTLBミスが即例外を起こし、OSがページテーブルを引いてTLBに追加することによってTLBミスを解決する[[コンピュータ・アーキテクチャ|アーキテクチャ]]や、ページテーブル自体のフォーマットがOSが使えるビットを含めた形でMMUによって定義されていて、TLBミス時にMMU自身が与えられた物理アドレスにあるページテーブルを参照するアーキテクチャもある。 |
これを実現する[[ハードウエア]]である[[メモリ管理ユニット]] ('''MMU''') の中には[[トランスレーション・ルックアサイド・バッファ]] (''Translation Lookaside Buffer'':'''TLB''') と呼ばれる一種の[[キャッシュ (コンピュータシステム)|キャッシュ]]があり、[[ユニット (プログラミング)|ユニット]]内部ではこの対応表に基づいて[[メモリアドレス]]の対応づけを行っている。このテーブルから参照出来なかったときをTLBミスと呼ぶ。このときの処理はMMUの設計によって異なり、MMU内にはTLBのみを持ちTLBミスが即例外を起こし、OSがページテーブルを引いてTLBに追加することによってTLBミスを解決する[[コンピュータ・アーキテクチャ|アーキテクチャ]]や、ページテーブル自体の[[フォーマット]]がOSが使える[[ビット]]を含めた形でMMUによって定義されていて、TLBミス時にMMU自身が与えられた[[物理アドレス]]にあるページテーブルを参照するアーキテクチャもある。 |
||
== 利点 == |
== 利点 == |
||
他の[[動的メモリアロケーション]]に比較して、ページング方式ではプログラムに割り当てるメモリが連続である必要がなく、大きな[[フラグメンテーション]](外部断片化)がほとんど発生しないため、メモリを無駄にしない。 |
他の[[動的メモリアロケーション]]に比較して、ページング方式ではプログラムに割り当てるメモリが連続である必要がなく、大きな[[フラグメンテーション]](外部断片化)がほとんど発生しないため、メモリを無駄にしない<ref>{{Cite book| contribution = Virtual memory systems | title = Encyclopedia of computer science and technology | editor1-last = Belzer | editor1-first = Jack | editor2-last = Holzman | editor2-first = Albert G. | editor3-last = Kent | editor3-first = Allen | publisher = CRC Press | volume=14 | page = 32 | year = 1981 | isbn = 0-8247-2214-0 | postscript = <!--None--> }}</ref>。 |
||
プログラムは、ある時点でそのコードとデータを全て使用するわけではない |
プログラムは、ある時点でそのコードとデータを全て使用するわけではない([[参照の局所性]])。そのため、必要に応じてページをディスクに書き込んだり、ページの内容をディスクから読み込んだりすることで[[仮想記憶]]のコンセプトを実装できる。この点もページング方式が他のメモリアロケーション手法よりも優れている点である。 |
||
== 欠点 == |
== 欠点 == |
||
ページング方式の主な問題点は、それを実装するコードが相対的に複雑になる点であり、特に[[仮想記憶]]を実現しようとすると複雑化する。他には[[ |
ページング方式の主な問題点は、それを実装するコードが相対的に複雑になる点であり、特に[[仮想記憶]]を実現しようとすると複雑化する。他には[[MMU]]が必要になるという問題もあり、古くて小さい[[マイクロプロセッサ]]でページングを実装するのは困難である(例えば、[[x86]]シリーズでは、[[Intel 80386|i386]]以上でないとページングをサポートしたMMUがない)。また、ページ単位以下の小さなメモリを要求されてもページ単位でしか割り当てられないというフラグメンテーション(内部断片化)問題もある。 |
||
== 動作原理 == |
== 動作原理 == |
||
[[ |
[[ファイル:Paging Addr Ja.JPG|thumb|right|350px|ページング方式のアドレス変換の概念図]] |
||
ページング方式では、実際のメモリアクセスは[[ページテーブル]]を使用して[[メモリ管理ユニット]]がハードウェアレベルで制御する。前述の通り、物理メモリはページと呼ばれる小さなブロックに分割される。各ページにはページ番号が付与される。 |
ページング方式では、実際のメモリアクセスは[[ページテーブル]]を使用して[[メモリ管理ユニット]]がハードウェアレベルで制御する。前述の通り、物理メモリはページと呼ばれる小さなブロックに分割される。各ページにはページ番号が付与される。OSは未使用のページのリストを保持するか、メモリ使用要求があったときに毎回メモリを調べる(最近のOSでは前者の実装が一般的)。いずれにしても、プログラムがメモリを要求したとき、OSがそのプログラムに何ページかのメモリを割り当て、それをプログラム([[プロセス]])毎に割り当て中のページを管理するリストに入れておく(訳注:ページそのものはプログラムが使用するので、それをリストに入れるわけではなく、物理ページを管理するデータ構造を別途作成してリストに入れる)。具体例を以下に示す。 |
||
以下のような順番でページの割り当てが行われたときのページアロケーションリストをテーブルに示す。 |
以下のような順番でページの割り当てが行われたときのページアロケーションリストをテーブルに示す。 |
||
45行目: | 45行目: | ||
|} |
|} |
||
結果として、各プログラムのページテーブルには、以下のようなマッピングが格納される |
結果として、各プログラムのページテーブルには、以下のようなマッピングが格納される(「プログラムのページ番号 → OSのページ番号」)。 |
||
* プログラムA: 0 → 0、1 → 1、2 → 2 |
* プログラムA: 0 → 0、1 → 1、2 → 2 |
||
* プログラムB: 0 → 3、1 → 4、2 → 7 |
* プログラムB: 0 → 3、1 → 4、2 → 7 |
||
* プログラムD: 0 → 5、1 → 6 |
* プログラムD: 0 → 5、1 → 6 |
||
ここで、プログラムが自身に割り当てられたメモリにアクセスしようとしたときに何が起きるかを示す。プログラムA が "LOAD memory at 20FE" |
ここで、プログラムが自身に割り当てられたメモリにアクセスしようとしたときに何が起きるかを示す。プログラムA が "LOAD memory at 20FE"(20FE番地からロード)という命令を実行したとする。 |
||
20FE(16進数)を2進数表記すると(16ビットシステムでは) 0010000011111110 となる。ページサイズは4Kバイトとする。従って、20FE番地のメモリ参照要求を受けると MMU は以下のようにこのアドレスを見る。 |
|||
<pre> |
<pre> |
||
65行目: | 65行目: | ||
</pre> |
</pre> |
||
ページサイズが4096バイトなので、MMUはアドレスの先頭 |
ページサイズが4096バイトなので、MMUはアドレスの先頭([[最上位桁ビット]]群)4ビットをページ番号、残りの12ビットをページ内相対メモリアドレスとして扱う。ページサイズが2048バイトなら、[[メモリ管理ユニット|MMU]]は先頭5ビットをページ番号、残り11ビットをページ内相対メモリアドレスとして扱うだろう。つまり、ページサイズが小さければページ数が多くなる。 |
||
従って、このメモリアクセス要求がなされると、MMUはそのプログラムのページテーブルを参照してマッピングされているOSのページ番号を得る。この例の場合、プログラムAの2番目のページはOSの2番目のページにマップされている。次いで、OSページ番号に対応する物理マッピングを得る。2番目のOSページは物理メモリアドレス 1000:2000 に対応しており、プログラムが参照しようとしているアドレスのページ内相対アドレスは 00FE なので、MMU は物理アドレス 1000:20FE の位置のメモリにアクセスする。 |
従って、このメモリアクセス要求がなされると、MMUはそのプログラムのページテーブルを参照してマッピングされているOSのページ番号を得る。この例の場合、プログラムAの2番目のページはOSの2番目のページにマップされている。次いで、OSページ番号に対応する物理マッピングを得る。2番目のOSページは物理メモリアドレス 1000:2000 に対応しており、プログラムが参照しようとしているアドレスのページ内相対アドレスは 00FE なので、MMU は物理アドレス 1000:20FE の位置のメモリにアクセスする。 |
||
以上はあくまでも概略である。最近の[[コンピュータ・アーキテクチャ]]では様々な手段でページングを高速化している。例えば、i386 系アーキテクチャのプロセッサも他のプロセッサと同様に |
以上はあくまでも概略である。最近の[[コンピュータ・アーキテクチャ]]では様々な手段でページングを高速化している。例えば、i386 系アーキテクチャのプロセッサも他のプロセッサと同様にTLBと呼ばれる特殊なキャッシュを持っていて、過去にアクセスした仮想アドレスと物理アドレスのマッピングを保持する。従って一度ページテーブルを参照してマッピング情報を得たら、スワップアウトされたりTLBのエントリが他のマッピングに転用されるまで、時間のかかるページテーブル参照をせずにマッピング情報が得られる。 |
||
== ページングと仮想記憶 == |
== ページングと仮想記憶 == |
||
ページングの主たる機能は、プログラムがその時点で物理メモリ (RAM) のマッピングされていないページにアクセスしようとしたときに実行される。これを[[ページフォールト]]と呼ぶ。オペレーティングシステムはページフォールトによって制御を得て、プログラムからは見えない形で処理を行う。その流れは次のようになる。 |
|||
ページングが[[仮想記憶]]と共に使用されるとき、OSは使用されているページ全体について最近の使用状況を監視し、今後の使用を予測しなければならない。そしてOSが適当だと判断したとき(空きメモリが少なくなったと判断したとき)やプログラムがスワップアウトされたページにアクセスしようとしたとき、OSはページを選択してディスクにスワップアウトし、別のページの内容をメモリに持ってくる(詳しくは[[ページ置換アルゴリズム]]を参照されたい)。これによって物理的なメモリ容量以上のメモリを使用することができる。 |
|||
# [[補助記憶装置]]内での要求されたデータの位置を特定する。 |
|||
# RAM上の空のページフレームを取得。 |
|||
# 要求されたデータをそのページフレームにロードする。 |
|||
# [[ページテーブル]]を更新してそのページフレームをマッピングする。 |
|||
# 要求元プログラムに制御を戻し、ページフォールトを発生した命令を透過的に再実行させる。 |
|||
これを「ページイン」と呼ぶ。必要とされる全データを格納できるほどRAMがないという状態になるまで、空のページフレームを取得する処理はRAM上の使用中ページを奪う処理を伴わない。全ページフレームが使用中の場合、空のページフレームを得るには使用中のページフレームを選んで空にする処理が必要となる。選択したページフレーム内のデータが前回ロードされてから変更されている場合(いわゆる「ダーティ」状態)、二次記憶装置の対応する位置に書き戻さないと解放できない。これを「ページアウト」と呼ぶ。そうでない場合、選択したページフレームの内容は二次記憶装置の所定の位置にあるものと同じなので、書き戻す必要がない。そのように使用中のページを奪った場合、もともとそのページを使っていたプロセスがそのページにアクセスしようとした場合、同様に空のページフレームを取得して、ページインする必要がある。 |
|||
== デマンドページング == |
|||
アクセスしようとしたときに物理メモリをページに割り当てる方式を'''デマンドページング'''('''Demand Paging''')と呼ぶ。換言すれば、[[ページフォールト]]が発生したときに物理メモリを割り当てるのである。[[プロセス]]が実行を開始したとき物理メモリは割り当てられておらず、プロセスの[[ワーキングセット]]の大部分が物理メモリに置かれるまでページフォールトが発生し続けることになる。これは遅延ロード技法の一例である。 |
|||
効率的なページングシステムは、空にすべきページフレームとして、短期間では必要とされなさそうなページを選択しなければならない。そのための[[ページ置換アルゴリズム]]には様々なものがある。多くのオペレーティングシステムは [[Least Recently Used]] (LRU) アルゴリズムに類するものを使うか(LRUそのものは現行のハードウェアでの正確な実装は困難である)、[[ワーキングセット]]ベースのアルゴリズムを使っている。 |
|||
さらに応答性を向上させるため、ページングシステムはどのページがすぐに必要とされるかを予測する様々な戦略を活用する。プログラムが参照する前に先行的にページをロードするシステムもある。 |
|||
== ページ置換アルゴリズム == |
|||
{{Main|ページ置換アルゴリズム}} |
|||
=== デマンドページング === |
|||
アクセスしようとしたときに物理メモリをページに割り当てる方式を'''デマンドページング''' ('''Demand Paging''') と呼ぶ。換言すれば、[[ページフォールト]]が発生したときに物理メモリを割り当てる。[[プロセス]]が実行を開始したとき物理メモリは割り当てられておらず、プロセスの[[ワーキングセット]]の大部分が物理メモリに置かれるまでページフォールトが発生し続けることになる。これは遅延ロード技法の一例である。 |
|||
デマンドページングの利点: |
デマンドページングの利点: |
||
* アクセスされないページはロードされない。そのため、メモリ使用量が節約され、マルチプログラミング |
* アクセスされないページはロードされない。そのため、メモリ使用量が節約され、マルチプログラミング(マルチタスク)の度合いを向上させる。 |
||
* プログラム実行開始前のロードによる遅延がない。 |
* プログラム実行開始前のロードによる遅延がない。 |
||
* ページの読み込みが最小限なのでディスク負荷が少ない。 |
* ページの読み込みが最小限なのでディスク負荷が少ない。 |
||
89行目: | 102行目: | ||
* [[ページ置換アルゴリズム]]に関わるメモリ管理は複雑化しつつある。 |
* [[ページ置換アルゴリズム]]に関わるメモリ管理は複雑化しつつある。 |
||
[[Linux]]のような[[UNIX]]系システムでは、[[mmap|mmap()]]システムコールもデマンドページングによって実装されている。それは新たなプログラムを実行する際にも適用される。OSは[[実行ファイル]] |
[[Linux]]のような[[UNIX]]系システムでは、<tt>[[mmap|mmap()]]</tt> システムコールもデマンドページングによって実装されている。それは新たなプログラムを実行する際にも適用される。OSは[[実行ファイル]](とそれが依存するライブラリ群)をマッピングするが、そのときにファイルの中身を物理メモリ上に実際にロードすることはない。マッピングがリードオンリーで共有可能であれば、物理メモリに残っている内容をそのまま使って実行することもある。これを'''ページキャッシュ'''と呼ぶ。 |
||
使われていない物理ページには、スワップ領域以外のファイルに対応するページキャッシュと何とも対応していない完全な未使用ページがある。一般にページング方式では、新たに必要となったページがページキャッシュにあればそれを再利用し、なければ完全に未使用のページを使用する。使い終わったページは、その内容がスワップ領域以外に対応していればページキャッシュとしてそのまま内容が保持され、スワップ領域に対応していた匿名(Anonymous)ページは完全な未使用ページに戻される。もちろん、完全な未使用ページを使い切った上でさらにメモリを使用しなければならないときにはページキャッシュが他の用途に利用される。このようにして、現に使用中でない物理メモリを有効活用してなるべくディスクアクセスを減らすように工夫している。ちなみに、ページキャッシュとして存在する領域を<tt>mmap()</tt>でマッピングするとページキャッシュがそのまま使われるが、<tt>read()</tt>システムコールで読む場合にはユーザーバッファへのコピーが発生する。 |
使われていない物理ページには、スワップ領域以外のファイルに対応するページキャッシュと何とも対応していない完全な未使用ページがある。一般にページング方式では、新たに必要となったページがページキャッシュにあればそれを再利用し、なければ完全に未使用のページを使用する。使い終わったページは、その内容がスワップ領域以外に対応していればページキャッシュとしてそのまま内容が保持され、スワップ領域に対応していた匿名 (Anonymous) ページは完全な未使用ページに戻される。もちろん、完全な未使用ページを使い切った上でさらにメモリを使用しなければならないときにはページキャッシュが他の用途に利用される。このようにして、現に使用中でない物理メモリを有効活用してなるべくディスクアクセスを減らすように工夫している。ちなみに、ページキャッシュとして存在する領域を<tt>mmap()</tt> でマッピングするとページキャッシュがそのまま使われるが、<tt>read()</tt> システムコールで読む場合にはユーザーバッファへのコピーが発生する。 |
||
=== プリページング === |
|||
スワップ・プリフェッチとも呼ばれる技法で、([[参照の局所性]]を利用して)近い将来参照されると予測したページを事前にロードしておく。プロセスが経験するページフォールト回数を減らす試みである。例えば、ある参照でページフォールトが発生したとき、連続する数ページにもすぐに参照するだろうと予測してまとめてロードしておく、といった戦略がある。また、ある大きなプログラムが終了して多くのメモリを解放したとき、ページアウトされていた他のプログラムがメモリを必要とするだろうと予測して、事前にページインしておくといった戦略もある。 |
|||
=== フリーページのキュー === |
|||
フリーページのキューは、ページフォールト時に使用可能なページフレームのリストである。一部のオペレーティングシステム<ref group="注">例えば、 [[Multiple Virtual Storage|MVS]]</ref>はページの再利用をサポートしている。すなわち、かつて奪われたが他に再割当てされていないページに対してページフォールトが発生した場合、ページイン処理をせずにフリーとなっている当該ページフレームをそのまま再利用するものである。 |
|||
=== ページの事前解放 === |
|||
一部のオペレーティングシステムは、定期的に最近使われていないページを探し、それらをフリーページのキューに追加し、当該ページが更新されていたら(ダーティな場合)、ページアウト処理を行っておく。すると、ページフォールト時に空のページフレームがないということがなく、ページアウトを行う必要がなくなる。 |
|||
=== 事前クリーニング === |
|||
UNIXでは、{{仮リンク|sync (UNIX)|en|sync (Unix)|label=sync}} を使って定期的に全ダーティページを書き戻してクリーンな状態にする。Windowsでは、"modified page writer" というスレッドが同じことを行っている。 |
|||
事前クリーニングにより、プログラムの起動や新たなファイルのオープンが高速化される。 |
|||
== スラッシング == |
|||
{{Main|スラッシング}} |
|||
多くのプログラムは、ある程度動作すると[[参照の局所性]]によって命令フェッチでもデータアクセスでもページフォールトが発生しない安定状態になる。この安定状態で使用しているメモリ量は、そのプログラムが必要とする全メモリ量よりも少ないのが一般的である。この安定状態を[[ワーキングセット]]などと呼び、そのプログラムが最も頻繁にアクセスするメモリページ群を意味する。 |
|||
仮想記憶システムは、物理メモリの総ページ数に対してワーキングセットとして必要とされるページ数が小さいほど効率的であり、[[ページフォールト]]処理にかかる時間は性能の支配的要因ではなくなる。非常に巨大なデータ構造を必要とするプログラムはワーキングセットも巨大となる傾向にあり、ページフォールトがコンスタントに発生するためシステム性能が劇的に低下することがある。そのような状況を[[スラッシング]]という。 |
|||
スラッシングの興味深い特性として、ワーキングセットが大きくなってもページフォールト回数はある臨界点まではあまり増えない。その臨界点を越えるとページフォールト回数が劇的に増え、システム性能がそれに支配されるようになる。 |
|||
その種の極端な例として、[[IBM]]の [[System/360]] Model 67 と [[System/370]] で、データ転送命令の[[機械語]]がページ境界をまたぎ、データ転送元もページ境界をまたぎ、データ転送先もページ境界をまたいだ場合がある。そのとき、その命令を実行するには8ページがメモリ上になければならない。したがって、最大8回のページフォールトが連続的に発生する可能性があり、スラッシングが発生するといつまでたっても8ページが揃わないという状態になる。 |
|||
スラッシングを解決する手段として、次のような対策が考えられる。 |
|||
* RAMを増設する(長期的解決策) |
|||
* 同時に実行するプログラムの数を減らす。 |
|||
== ページカラーリング == |
== ページカラーリング == |
||
[[ |
[[ファイル:Page Coloring Ja.JPG|thumb|right|350px|ページカラーリングの概念図]] |
||
[[キャッシュメモリ]]での[[スラッシング]]を防ぐ、あるいは積極的にキャッシュヒット率を向上させようとする物理ページ管理手法を'''ページカラーリング'''と呼ぶ。ページカラーリングはまた、仮想インデックスキャッシュのエイリアス問題への回避策としても使われた。 |
[[キャッシュメモリ]]での[[スラッシング]]を防ぐ、あるいは積極的にキャッシュヒット率を向上させようとする物理ページ管理手法を'''ページカラーリング'''と呼ぶ。ページカラーリングはまた、仮想インデックスキャッシュのエイリアス問題への回避策としても使われた。 |
||
キャッシュは年々巨大化しているが、ページサイズは4Kバイトが一般的でこれはページング方式が一般化してから変わっていない。物理アドレスをインデックスとするキャッシュでは、物理ページと仮想ページのマッピングによってはキャッシュ上で現に使用中のページの対応する位置が衝突してしまい、巨大なキャッシュを生かしきれない事態が発生することがある。例えば、キャッシュサイズが16Kバイトでページサイズが4Kバイトであれば、ページはそのアドレスによってキャッシュ上で4種類の位置に対応することが考えられる。この場合、ページのカラー |
キャッシュは年々巨大化しているが、ページサイズは4Kバイトが一般的でこれはページング方式が一般化してから変わっていない。物理アドレスをインデックスとするキャッシュでは、物理ページと仮想ページのマッピングによってはキャッシュ上で現に使用中のページの対応する位置が衝突してしまい、巨大なキャッシュを生かしきれない事態が発生することがある。例えば、キャッシュサイズが16Kバイトでページサイズが4Kバイトであれば、ページはそのアドレスによってキャッシュ上で4種類の位置に対応することが考えられる。この場合、ページのカラー(色)が4種類存在すると称する。 |
||
物理インデックスキャッシュでは同時にアクセスする物理ページ群のカラーがばらばらであればスラッシングが発生せず、キャッシュヒット率が向上する。ページカラーリングの実装上の問題は、仮想ページと物理ページのマッピングは一度なされると変更されることがなく、マッピング時点でどのようなメモリアクセスパターンとなるかを予測できない点にある。一般的には仮想ページのカラーと物理ページのカラーが一致するようにマッピングを行う。こうすることで、仮想空間上連続な領域へのアクセスでスラッシングが発生するのを防ぐ。 |
物理インデックスキャッシュでは同時にアクセスする物理ページ群のカラーがばらばらであればスラッシングが発生せず、キャッシュヒット率が向上する。ページカラーリングの実装上の問題は、仮想ページと物理ページのマッピングは一度なされると変更されることがなく、マッピング時点でどのようなメモリアクセスパターンとなるかを予測できない点にある。一般的には仮想ページのカラーと物理ページのカラーが一致するようにマッピングを行う。こうすることで、仮想空間上連続な領域へのアクセスでスラッシングが発生するのを防ぐ。 |
||
ただし、そのような実装をした場合に新たな問題が発生する。実行ファイルのテキストとデータの領域は仮想空間上きりのよいアドレスに配置されることが多い。そして、そのアドレスはキャッシュのカラーで言えば同じカラーとなる。従ってページカラーリングを行うシステムでは、カラーによって物理ページの使用率に偏りが発生することがある。するとシステム全体としては未使用メモリが十分であるにも |
ただし、そのような実装をした場合に新たな問題が発生する。実行ファイルのテキストとデータの領域は仮想空間上きりのよいアドレスに配置されることが多い。そして、そのアドレスはキャッシュのカラーで言えば同じカラーとなる。従ってページカラーリングを行うシステムでは、カラーによって物理ページの使用率に偏りが発生することがある。するとシステム全体としては未使用メモリが十分であるにもかかわらず、特定のカラーの空きページがないために[[ページ置換アルゴリズム]]が起動してしまい性能低下するといった問題が発生する。これに対処する方法は様々である。 |
||
仮想インデックスキャッシュでは、ある物理ページが複数の[[プロセス]]に共有されているとき、そのマッピング先の仮想ページのカラーが異なっていると困った状態となる。同じ物理ページでありながら、キャッシュ上の複数個所に内容が置かれてしまうのである。これをエイリアス問題とかシノニム問題と呼ぶ。この状態をハードウェアが検出せずに放置すると、一方のマッピング経由で更新した内容が他方のマッピング経由では観測できないという事態が発生する。もちろん、ほとんどのシステムではハードウェアが自動的にこの状態を検出して対処するが、その対処による性能低下もある(キャッシュミス |
仮想インデックスキャッシュでは、ある物理ページが複数の[[プロセス]]に共有されているとき、そのマッピング先の仮想ページのカラーが異なっていると困った状態となる。同じ物理ページでありながら、キャッシュ上の複数個所に内容が置かれてしまうのである。これをエイリアス問題とかシノニム問題と呼ぶ。この状態をハードウェアが検出せずに放置すると、一方のマッピング経由で更新した内容が他方のマッピング経由では観測できないという事態が発生する。もちろん、ほとんどのシステムではハードウェアが自動的にこの状態を検出して対処するが、その対処による性能低下もある(キャッシュミス時に他のカラーの位置をチェックしてエイリアスがあればそれらのキャッシュラインを全てフラッシュして無効化する)。一時期のシステムでは、この性能低下が無視できないレベルであったため、OSがなるべくエイリアス問題を発生させないようにすることで性能低下を防ぐ必要があった。その際に使用されたのがページカラーリングである。ちなみに[[R4000]]では二次キャッシュと一次キャッシュの間の矛盾状態をエイリアス検出に利用していたため、二次キャッシュのないシステムではエイリアス状態を検出することすらできなかった(検出した場合も対処はOS任せである)。最近のシステムではキャッシュの性能向上によってペナルティが無視できるレベルになっているため、エイリアス問題への対策としてページカラーリングを行う必要性は小さくなっている。 |
||
==可変ページサイズ== |
== 可変ページサイズ == |
||
前述の通り、ページングとはメモリ空間を一定サイズのページに分けるのが基本であるが、TLBミスが多発すると実行効率が落ち、またTLB |
前述の通り、ページングとはメモリ空間を一定サイズのページに分けるのが基本であるが、TLBミスが多発すると実行効率が落ち、またTLBミスをソフトウエアで扱う時TLBフォールトハンドラをどう置くかという問題がある。このため、いくつかのMMUの設計では、最小ページサイズの倍数(多くは2の冪乗倍)サイズのページをサポートしている。OSのメモリ管理に可変ページサイズをサポートさせると、断片化等の関係で設計が複雑になるため、サポートされない事があるが(このサポートのことを'''スーパーページ'''と言う)、その場合でもOS自身を巨大なページに置く事によって実行効率を上げる事が出来るので、そのような設計になっている事が多い。また、後者の問題の解決の一つとしても使用される事がある(その場合は、あるページをTLBから追い出されない事を保証出来るようになっている)。また、OS用にアドレス変換されない領域を用意するMMUの設計も存在する。 |
||
== 共有 == |
|||
[[マルチタスク]]または[[マルチユーザー]]環境では、複数のユーザーが同じプログラムを実行するということがよくある。そのプログラムのコピーを各ユーザー用に作成するのはメモリの無駄遣いとなる。解決策としては、それらページ群をプロセス間で共有すればよい。 |
|||
共有する場合、あるプロセスが[[データ]]を更新した際に別のプログラムがその更新されたデータにアクセスしないよう注意深く制御しなければならない。これを[[コピーオンライト]]と呼ぶ。 |
|||
== 用語 == |
|||
歴史的には、「ページング」という用語は可変長の[[セグメント方式|セグメント]]ではなく固定長のページによる[[メモリ管理]]を指すこともあり、仮想記憶や二次記憶装置への転送などといった技法を含まないこともある<ref>{{Cite book| first = Harvey M. | last = Deitel | title = An Introduction to Operating Systems | publisher = Addison-Wesley | pages = 181, 187 | year = 1983 | isbn = 0-201-14473-5 | postscript = <!--None--> }}</ref><ref>{{Cite book| contribution = Operating systems | title = Encyclopedia of computer science and technology | editor1-last = Belzer | editor1-first = Jack | editor2-last = Holzman | editor2-first = Albert G. | editor3-last = Kent | editor3-first = Allen | publisher = CRC Press | volume=11 | page = 433 | year = 1981 | isbn = 0-8247-2261-2 | doi = 10.1002/ | postscript = <!--None--> }}</ref>。しかし近年ではそのような用法は稀である。 |
|||
最近の一部システムでは、「ページング」と同時に「スワッピング」という用語を使っている。歴史的には「スワッピング」はプログラム全体を二次記憶に転送(あるいは二次記憶から主記憶に転送)することを意味する<ref>{{Cite book| contribution = Operating systems | title = Encyclopedia of computer science and technology | editor1-last = Belzer | editor1-first = Jack | editor2-last = Holzman | editor2-first = Albert G. | editor3-last = Kent | editor3-first = Allen | publisher = CRC Press | volume=11 | page = 442 | year = 1981 | isbn = 0-8247-2261-2 | postscript = <!--None--> }}</ref><ref>{{Cite book| first = Harvey G. | last = Cragon | title = Memory Systems and Pipelined Processors | publisher = Jones and Bartlett Publishers | page = 109 | year = 1996 | url = https://books.google.co.jp/books?id=q2w3JSFD7l4C&redir_esc=y&hl=ja | isbn = 0-86720-474-5 | postscript = <!--None--> }}</ref>。 |
|||
1960年代にセグメント方式とページング方式の仮想記憶の概念が登場すると、「スワッピング」という用語はセグメント単位およびページ単位の二次記憶と主記憶間の転送を意味するようになった。今日の仮想記憶はほとんどがページング方式となったため、「スワッピング」は「ページング」とほぼ同義に使われることもある。また、スワップファイルとの間のページインとページアウトのみを「スワッピング」と称することもある。 |
|||
[[UNIX|Unix系OS]]にあっては、初期の仮想記憶技術としてカーネル内で長期間スリープ中のプロセスを対象に[[プロセス制御ブロック|PCB]]およびカーネルスタックを二次記憶へ追い出しており、これを「スワッピング」と呼んでいる。スワップされたプロセスは、PCBおよびカーネルスタックをメモリへ読み戻さなければ実行が再開できない。伝統的にスワッピングの処理はプロセスIDが0のプロセスが担当しており、このプロセスは<code>swapper</code>と呼ばれている。現在ではプロセスのアドレス空間全体がページングの対象となったためスワッピングの効果は小さくなったが、<code>swapper</code>の名称は多くのUnix系OSにて残っている。また、Unix系OSにて仮想記憶の二次記憶領域を「''スワップ''領域」「''スワップ''パーティション」などと呼ぶ由来ともなっている。 |
|||
== 性能 == |
|||
仮想記憶のバッキングストアは[[Random Access Memory|RAM]]に比べると何十倍も遅い。しかも機械的可動部分があるとさらに遅延が生じ、ハードディスクでは数ミリ秒単位の遅延になることもある。したがってスワッピング(ページアウト)は発生させないに越したことはない。OSによっては[[カーネル]]のそのあたりの動作に影響する設定が可能なものもある。 |
|||
* Linuxでは <code>/proc/sys/vm/[[swappiness]]</code> というパラメータがあり、値を大きく設定するほど積極的なページアウト(空きページフレームを作る)を行う。 |
|||
* Windowsでは <code>DisablePagingExecutive</code> というレジストリ設定があり、カーネルモードのコードやデータをページアウトの対象外とするか否かを指定できる。 |
|||
* メインフレームでは、シーク時間を除去すべくトラック毎にヘッドのある磁気ディスクや磁気ドラムをページングに使用し、回転レイテンシを削減すべく同一デバイスに複数の要求を同時に発行する技法を使っている<ref group="注">例えば、ブロックマルチプレクサチャネルの Rotational Position Sensing</ref>。 |
|||
* [[フラッシュメモリ]]は消去・書き込み回数が有限であり、一度に消去する範囲が大きく(例えば、Intel X25-M SSD<ref>{{Cite web |url= http://tytso.livejournal.com/60368.html |title=Aligning filesystems to an SSD’s erase block size |author= Ted Tso |date=2009-02-20 |accessdate=2010-10-28}}</ref> では128KiB)、ページサイズの何倍ということもある。したがって、フラッシュメモリをメモリ容量に余裕がない状況でスワップファイルに使用するとすぐに消耗するかもしれない。しかし、ハードディスクに比べて遅延が極めて小さく、RAMのように[[揮発性メモリ|揮発性]]でないという点は魅力的である。[[Windows ReadyBoost|ReadyBoost]] や [[ターボメモリー|Intel Turbo Memory]] といった方式はそういった利点を利用したものである。 |
|||
[[Unix系]]OSの多く(例えば、[[AIX]]、[[Linux]]、[[Solaris]])は複数のデバイスを並列にスワップスペースとして使用でき、性能を向上させることができる。 |
|||
== 32ビットハードウェアでのアドレッシングの限界 == |
|||
ページングは、プロセスが使用するアドレス範囲(仮想アドレス空間または論理アドレス空間)をコンピュータに実際に搭載されている物理メモリ(物理アドレス空間)とは異なる大きさにする手段でもある。 |
|||
=== 仮想アドレス空間より主記憶が小さい場合 === |
|||
多くのシステムでは、プロセスの仮想アドレス空間は利用可能な主記憶よりもずっと大きい<ref name="buzbee">Bill Buzbee. "[http://www.homebrewcpu.com/demand_paging.htm Magic-1 Minix Demand Paging Design]".</ref>。 |
|||
そのようなシステムでは、プロセスが利用可能な主記憶容量は、実装している主記憶容量より少ない。実装可能な主記憶容量はCPUと主記憶を接続する[[アドレスバス]]のビット数で制限されており、例えば、[[MC68000]]や[[Intel 80386|i386SX]]は内部的には32ビットの仮想アドレスを使用していたが、アドレスバスは24ビットぶんのピンしかなく、物理的に接続可能な主記憶容量は16MBに制限されていた。 |
|||
たとえ物理アドレスのビット数が仮想アドレスのビット数と同じかそれ以上であっても、実際に実装可能な物理主記憶容量はそれより小さいことが多い。それはたとえばコスト的な問題のためだったり、[[入出力|I/O]]用にアドレス空間がハード的に予約されていたりするためである。 |
|||
=== 仮想アドレス空間と主記憶が同じサイズの場合 === |
|||
32ビットのコンピュータで[[物理アドレス拡張|PAE]]などを使わなければ、最大主記憶容量は4GBまでだが、その限界ぎりぎりまでRAMを搭載したシステムも珍しくない。IBM [[System/370]] はXAモードでもアドレッシング可能な範囲は2GBまでだった。 |
|||
ページングおよびスワップスペースはこの4GBの限界を超えて使うことができ、そのためにメモリアドレスではなくディスク上の位置でアドレス指定される。 |
|||
リニアなアドレス空間の32ビットマシンでは、プログラムの仮想アドレス空間は4GBまでに制限されておりが、複数のプログラムでグループを形成すればその制限を越えることも可能である。個々の仮想アドレス空間の総和は、[[ページテーブル]]がサポートするプロセスID(または仮想空間ID)のビット数で制限される。 |
|||
セグメントレジスタ(例えば、[[System/370]]の[[ESA/390|ESA]]モードにおけるアクセスレジスタ<ref>{{Cite manual |author = IBM |title = IBM System/370 Extended Architecture Principles of Operation |id = SA22-7085-1 |version = Second Edition |date = January 1987 |separator = , }}</ref>)のあるマシンでは、アドレス空間の大きさはOSによってのみ制限され、マッピング用テーブルのサイズだけが問題となる。 |
|||
=== 仮想アドレス空間より主記憶が大きい場合 === |
|||
仮想アドレス空間より主記憶容量が大きいコンピュータも少数ながら存在する。例えば、Magic-1、[[PDP-11]]シリーズの一部機種、[[物理アドレス拡張]]付きの32ビットプロセッサなどである<ref name="buzbee" />。 |
|||
この場合、あるプロセスは仮想アドレス空間以上の主記憶を使うことができないため、仮想記憶の主たる利点が無効となる。したがってそのようなシステムでは、次のような別の利点を求めてページングを採用する。 |
|||
* 余分なメモリをよく使用するファイルやメタデータ(ディレクトリ情報など)のキャッシュ、すなわちページキャッシュとして使用する。 |
|||
* 複数の仮想アドレス空間をサポートし(一般に「プロセスID」をページテーブルに持たせる)、大きな主記憶容量をより多くのプロセスを動作させるのに使う。 |
|||
複数の仮想アドレス空間の総和は、[[ページテーブル]]がサポートするプロセスID(または仮想空間ID)のビット数、または使用可能な二次記憶装置の総量で制限される。 |
|||
== 脚注 == |
|||
=== 注釈 === |
|||
{{Reflist|group="注"}} |
|||
=== 出典 === |
|||
{{Reflist}} |
|||
== 関連項目 == |
== 関連項目 == |
||
* [[ |
* [[記憶装置]] |
||
** [[メモリ管理]]/[[メモリ保護機能]] |
|||
***[[仮想記憶]] |
|||
***[[セグメント方式]] |
|||
*** [[ページテーブル]] |
|||
*** [[ページ置換アルゴリズム]] |
|||
**[[キャッシュアルゴリズム]] |
|||
== 外部リンク == |
|||
* [http://it.toolbox.com/blogs/microsoft-infrastructure/moving-the-pagefilesys-to-another-partition-or-disk-35772 Windows Server - Moving Pagefile to another partition or disk] by David Nudelman |
|||
* [http://computer.howstuffworks.com/virtual-memory.htm How Virtual Memory Works] from HowStuffWorks.com (in fact explains only swapping concept, and not virtual memory concept) |
|||
* [http://www.faqs.org/docs/linux_admin/x1762.html Linux swap space management] (outdated, as the author admits) |
|||
* [http://www.techarp.com/showarticle.aspx?artno=143 Guide On Optimizing Virtual Memory Speed] (outdated, and contradicts section 1.4 of this wiki page, and (at least) references 8, 9, and 11.) |
|||
* [https://web.archive.org/web/20110720003417/http://people.msoe.edu/~durant/courses/cs384/papers0405/mccrawt.pdf Virtual Memory Page Replacement Algorithms] |
|||
* [http://support.microsoft.com/kb/308417/ Windows XP. How to manually change the size of the virtual memory paging file] |
|||
* [http://support.microsoft.com/?id=312362 Windows XP. Factors that may deplete the supply of paged pool memory] |
|||
* [http://www.acc.umu.se/~bosse/ SwapFs] driver that can be used to save the paging file of Windows on a swap partition of Linux. |
|||
{{オペレーティングシステム}} |
|||
{{DEFAULTSORT:へえしんくほうしき}} |
{{DEFAULTSORT:へえしんくほうしき}} |
||
[[ |
[[Category:メモリ管理]] |
||
[[fr:Mémoire virtuelle#Mémoire virtuelle paginée]] |
|||
[[cs:Stránkování]] |
|||
[[de:Paging]] |
|||
[[en:Paging]] |
|||
[[et:Lehekülgede saalimine]] |
|||
[[fr:Pagination (informatique)]] |
|||
[[it:Paging]] |
|||
[[pl:Stronicowanie pamięci]] |
|||
[[pt:Memória paginada]] |
|||
[[sk:Stránkovanie]] |
2023年8月15日 (火) 03:44時点における最新版
ページング方式 (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がない)。また、ページ単位以下の小さなメモリを要求されてもページ単位でしか割り当てられないというフラグメンテーション(内部断片化)問題もある。
動作原理
[編集]ページング方式では、実際のメモリアクセスはページテーブルを使用してメモリ管理ユニットがハードウェアレベルで制御する。前述の通り、物理メモリはページと呼ばれる小さなブロックに分割される。各ページにはページ番号が付与される。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そのものは現行のハードウェアでの正確な実装は困難である)、ワーキングセットベースのアルゴリズムを使っている。
さらに応答性を向上させるため、ページングシステムはどのページがすぐに必要とされるかを予測する様々な戦略を活用する。プログラムが参照する前に先行的にページをロードするシステムもある。
ページ置換アルゴリズム
[編集]デマンドページング
[編集]アクセスしようとしたときに物理メモリをページに割り当てる方式をデマンドページング (Demand Paging) と呼ぶ。換言すれば、ページフォールトが発生したときに物理メモリを割り当てる。プロセスが実行を開始したとき物理メモリは割り当てられておらず、プロセスのワーキングセットの大部分が物理メモリに置かれるまでページフォールトが発生し続けることになる。これは遅延ロード技法の一例である。
デマンドページングの利点:
- アクセスされないページはロードされない。そのため、メモリ使用量が節約され、マルチプログラミング(マルチタスク)の度合いを向上させる。
- プログラム実行開始前のロードによる遅延がない。
- ページの読み込みが最小限なのでディスク負荷が少ない。
- ページは更新されるまで複数のプログラムから共有され、コピーオンライトによってさらにリソースを節約できる。
- 実装メモリ量よりも巨大なプログラムを実行できる。オーバーレイという古い技術よりも優れている。
- 本来のページング方式が必要とする以上のハードウェア機構を必要としない。
欠点:
- プログラムが任意の仮想ページに初めてアクセスする際、遅延が発生する。そこでプリページングという技法で以前に動作したときに使用していたページを覚えておき、スケジューリングによって実行される際にそれらのページを予め物理メモリにロードしておいて性能向上を図ることもある。また、特にアクセスしていたページを覚えておかなくとも、プログラムカウンタとスタックポインタの指している仮想ページだけでも予めロードしておけばある程度の性能向上は図れる。
- ページ置換アルゴリズムに関わるメモリ管理は複雑化しつつある。
LinuxのようなUNIX系システムでは、mmap() システムコールもデマンドページングによって実装されている。それは新たなプログラムを実行する際にも適用される。OSは実行ファイル(とそれが依存するライブラリ群)をマッピングするが、そのときにファイルの中身を物理メモリ上に実際にロードすることはない。マッピングがリードオンリーで共有可能であれば、物理メモリに残っている内容をそのまま使って実行することもある。これをページキャッシュと呼ぶ。
使われていない物理ページには、スワップ領域以外のファイルに対応するページキャッシュと何とも対応していない完全な未使用ページがある。一般にページング方式では、新たに必要となったページがページキャッシュにあればそれを再利用し、なければ完全に未使用のページを使用する。使い終わったページは、その内容がスワップ領域以外に対応していればページキャッシュとしてそのまま内容が保持され、スワップ領域に対応していた匿名 (Anonymous) ページは完全な未使用ページに戻される。もちろん、完全な未使用ページを使い切った上でさらにメモリを使用しなければならないときにはページキャッシュが他の用途に利用される。このようにして、現に使用中でない物理メモリを有効活用してなるべくディスクアクセスを減らすように工夫している。ちなみに、ページキャッシュとして存在する領域をmmap() でマッピングするとページキャッシュがそのまま使われるが、read() システムコールで読む場合にはユーザーバッファへのコピーが発生する。
プリページング
[編集]スワップ・プリフェッチとも呼ばれる技法で、(参照の局所性を利用して)近い将来参照されると予測したページを事前にロードしておく。プロセスが経験するページフォールト回数を減らす試みである。例えば、ある参照でページフォールトが発生したとき、連続する数ページにもすぐに参照するだろうと予測してまとめてロードしておく、といった戦略がある。また、ある大きなプログラムが終了して多くのメモリを解放したとき、ページアウトされていた他のプログラムがメモリを必要とするだろうと予測して、事前にページインしておくといった戦略もある。
フリーページのキュー
[編集]フリーページのキューは、ページフォールト時に使用可能なページフレームのリストである。一部のオペレーティングシステム[注 1]はページの再利用をサポートしている。すなわち、かつて奪われたが他に再割当てされていないページに対してページフォールトが発生した場合、ページイン処理をせずにフリーとなっている当該ページフレームをそのまま再利用するものである。
ページの事前解放
[編集]一部のオペレーティングシステムは、定期的に最近使われていないページを探し、それらをフリーページのキューに追加し、当該ページが更新されていたら(ダーティな場合)、ページアウト処理を行っておく。すると、ページフォールト時に空のページフレームがないということがなく、ページアウトを行う必要がなくなる。
事前クリーニング
[編集]UNIXでは、sync を使って定期的に全ダーティページを書き戻してクリーンな状態にする。Windowsでは、"modified page writer" というスレッドが同じことを行っている。
事前クリーニングにより、プログラムの起動や新たなファイルのオープンが高速化される。
スラッシング
[編集]多くのプログラムは、ある程度動作すると参照の局所性によって命令フェッチでもデータアクセスでもページフォールトが発生しない安定状態になる。この安定状態で使用しているメモリ量は、そのプログラムが必要とする全メモリ量よりも少ないのが一般的である。この安定状態をワーキングセットなどと呼び、そのプログラムが最も頻繁にアクセスするメモリページ群を意味する。
仮想記憶システムは、物理メモリの総ページ数に対してワーキングセットとして必要とされるページ数が小さいほど効率的であり、ページフォールト処理にかかる時間は性能の支配的要因ではなくなる。非常に巨大なデータ構造を必要とするプログラムはワーキングセットも巨大となる傾向にあり、ページフォールトがコンスタントに発生するためシステム性能が劇的に低下することがある。そのような状況をスラッシングという。
スラッシングの興味深い特性として、ワーキングセットが大きくなってもページフォールト回数はある臨界点まではあまり増えない。その臨界点を越えるとページフォールト回数が劇的に増え、システム性能がそれに支配されるようになる。
その種の極端な例として、IBMの System/360 Model 67 と System/370 で、データ転送命令の機械語がページ境界をまたぎ、データ転送元もページ境界をまたぎ、データ転送先もページ境界をまたいだ場合がある。そのとき、その命令を実行するには8ページがメモリ上になければならない。したがって、最大8回のページフォールトが連続的に発生する可能性があり、スラッシングが発生するといつまでたっても8ページが揃わないという状態になる。
スラッシングを解決する手段として、次のような対策が考えられる。
- RAMを増設する(長期的解決策)
- 同時に実行するプログラムの数を減らす。
ページカラーリング
[編集]キャッシュメモリでのスラッシングを防ぐ、あるいは積極的にキャッシュヒット率を向上させようとする物理ページ管理手法をページカラーリングと呼ぶ。ページカラーリングはまた、仮想インデックスキャッシュのエイリアス問題への回避策としても使われた。
キャッシュは年々巨大化しているが、ページサイズは4Kバイトが一般的でこれはページング方式が一般化してから変わっていない。物理アドレスをインデックスとするキャッシュでは、物理ページと仮想ページのマッピングによってはキャッシュ上で現に使用中のページの対応する位置が衝突してしまい、巨大なキャッシュを生かしきれない事態が発生することがある。例えば、キャッシュサイズが16Kバイトでページサイズが4Kバイトであれば、ページはそのアドレスによってキャッシュ上で4種類の位置に対応することが考えられる。この場合、ページのカラー(色)が4種類存在すると称する。
物理インデックスキャッシュでは同時にアクセスする物理ページ群のカラーがばらばらであればスラッシングが発生せず、キャッシュヒット率が向上する。ページカラーリングの実装上の問題は、仮想ページと物理ページのマッピングは一度なされると変更されることがなく、マッピング時点でどのようなメモリアクセスパターンとなるかを予測できない点にある。一般的には仮想ページのカラーと物理ページのカラーが一致するようにマッピングを行う。こうすることで、仮想空間上連続な領域へのアクセスでスラッシングが発生するのを防ぐ。
ただし、そのような実装をした場合に新たな問題が発生する。実行ファイルのテキストとデータの領域は仮想空間上きりのよいアドレスに配置されることが多い。そして、そのアドレスはキャッシュのカラーで言えば同じカラーとなる。従ってページカラーリングを行うシステムでは、カラーによって物理ページの使用率に偏りが発生することがある。するとシステム全体としては未使用メモリが十分であるにもかかわらず、特定のカラーの空きページがないためにページ置換アルゴリズムが起動してしまい性能低下するといった問題が発生する。これに対処する方法は様々である。
仮想インデックスキャッシュでは、ある物理ページが複数のプロセスに共有されているとき、そのマッピング先の仮想ページのカラーが異なっていると困った状態となる。同じ物理ページでありながら、キャッシュ上の複数個所に内容が置かれてしまうのである。これをエイリアス問題とかシノニム問題と呼ぶ。この状態をハードウェアが検出せずに放置すると、一方のマッピング経由で更新した内容が他方のマッピング経由では観測できないという事態が発生する。もちろん、ほとんどのシステムではハードウェアが自動的にこの状態を検出して対処するが、その対処による性能低下もある(キャッシュミス時に他のカラーの位置をチェックしてエイリアスがあればそれらのキャッシュラインを全てフラッシュして無効化する)。一時期のシステムでは、この性能低下が無視できないレベルであったため、OSがなるべくエイリアス問題を発生させないようにすることで性能低下を防ぐ必要があった。その際に使用されたのがページカラーリングである。ちなみにR4000では二次キャッシュと一次キャッシュの間の矛盾状態をエイリアス検出に利用していたため、二次キャッシュのないシステムではエイリアス状態を検出することすらできなかった(検出した場合も対処はOS任せである)。最近のシステムではキャッシュの性能向上によってペナルティが無視できるレベルになっているため、エイリアス問題への対策としてページカラーリングを行う必要性は小さくなっている。
可変ページサイズ
[編集]前述の通り、ページングとはメモリ空間を一定サイズのページに分けるのが基本であるが、TLBミスが多発すると実行効率が落ち、またTLBミスをソフトウエアで扱う時TLBフォールトハンドラをどう置くかという問題がある。このため、いくつかのMMUの設計では、最小ページサイズの倍数(多くは2の冪乗倍)サイズのページをサポートしている。OSのメモリ管理に可変ページサイズをサポートさせると、断片化等の関係で設計が複雑になるため、サポートされない事があるが(このサポートのことをスーパーページと言う)、その場合でもOS自身を巨大なページに置く事によって実行効率を上げる事が出来るので、そのような設計になっている事が多い。また、後者の問題の解決の一つとしても使用される事がある(その場合は、あるページをTLBから追い出されない事を保証出来るようになっている)。また、OS用にアドレス変換されない領域を用意するMMUの設計も存在する。
共有
[編集]マルチタスクまたはマルチユーザー環境では、複数のユーザーが同じプログラムを実行するということがよくある。そのプログラムのコピーを各ユーザー用に作成するのはメモリの無駄遣いとなる。解決策としては、それらページ群をプロセス間で共有すればよい。
共有する場合、あるプロセスがデータを更新した際に別のプログラムがその更新されたデータにアクセスしないよう注意深く制御しなければならない。これをコピーオンライトと呼ぶ。
用語
[編集]歴史的には、「ページング」という用語は可変長のセグメントではなく固定長のページによるメモリ管理を指すこともあり、仮想記憶や二次記憶装置への転送などといった技法を含まないこともある[2][3]。しかし近年ではそのような用法は稀である。
最近の一部システムでは、「ページング」と同時に「スワッピング」という用語を使っている。歴史的には「スワッピング」はプログラム全体を二次記憶に転送(あるいは二次記憶から主記憶に転送)することを意味する[4][5]。
1960年代にセグメント方式とページング方式の仮想記憶の概念が登場すると、「スワッピング」という用語はセグメント単位およびページ単位の二次記憶と主記憶間の転送を意味するようになった。今日の仮想記憶はほとんどがページング方式となったため、「スワッピング」は「ページング」とほぼ同義に使われることもある。また、スワップファイルとの間のページインとページアウトのみを「スワッピング」と称することもある。
Unix系OSにあっては、初期の仮想記憶技術としてカーネル内で長期間スリープ中のプロセスを対象にPCBおよびカーネルスタックを二次記憶へ追い出しており、これを「スワッピング」と呼んでいる。スワップされたプロセスは、PCBおよびカーネルスタックをメモリへ読み戻さなければ実行が再開できない。伝統的にスワッピングの処理はプロセスIDが0のプロセスが担当しており、このプロセスはswapper
と呼ばれている。現在ではプロセスのアドレス空間全体がページングの対象となったためスワッピングの効果は小さくなったが、swapper
の名称は多くのUnix系OSにて残っている。また、Unix系OSにて仮想記憶の二次記憶領域を「スワップ領域」「スワップパーティション」などと呼ぶ由来ともなっている。
性能
[編集]仮想記憶のバッキングストアは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)のビット数、または使用可能な二次記憶装置の総量で制限される。
脚注
[編集]注釈
[編集]出典
[編集]- ^ Belzer, Jack; Holzman, Albert G.; Kent, Allen, eds (1981). “Virtual memory systems”. Encyclopedia of computer science and technology. 14. CRC Press. p. 32. ISBN 0-8247-2214-0
- ^ Deitel, Harvey M. (1983). An Introduction to Operating Systems. Addison-Wesley. pp. 181, 187. ISBN 0-201-14473-5
- ^ Belzer, Jack; Holzman, Albert G.; Kent, Allen, eds (1981). “Operating systems”. Encyclopedia of computer science and technology. 11. CRC Press. p. 433. doi:10.1002/. ISBN 0-8247-2261-2
- ^ Belzer, Jack; Holzman, Albert G.; Kent, Allen, eds (1981). “Operating systems”. Encyclopedia of computer science and technology. 11. CRC Press. p. 442. ISBN 0-8247-2261-2
- ^ Cragon, Harvey G. (1996). Memory Systems and Pipelined Processors. Jones and Bartlett Publishers. p. 109. ISBN 0-86720-474-5
- ^ Ted Tso (2009年2月20日). “Aligning filesystems to an SSD’s erase block size”. 2010年10月28日閲覧。
- ^ a b Bill Buzbee. "Magic-1 Minix Demand Paging Design".
- ^ IBM (January 1987), IBM System/370 Extended Architecture Principles of Operation (Second Edition ed.), SA22-7085-1
関連項目
[編集]外部リンク
[編集]- Windows Server - Moving Pagefile to another partition or disk by David Nudelman
- How Virtual Memory Works from HowStuffWorks.com (in fact explains only swapping concept, and not virtual memory concept)
- Linux swap space management (outdated, as the author admits)
- Guide On Optimizing Virtual Memory Speed (outdated, and contradicts section 1.4 of this wiki page, and (at least) references 8, 9, and 11.)
- Virtual Memory Page Replacement Algorithms
- Windows XP. How to manually change the size of the virtual memory paging file
- Windows XP. Factors that may deplete the supply of paged pool memory
- SwapFs driver that can be used to save the paging file of Windows on a swap partition of Linux.