メモリ管理サブシステムは、オペレーティングシステムの最も重要な部分 のひとつである。コンピュータの黎明期以来、システム上にある物理メモリだけでは 足りない状況がずっと続いてきた。この限界を克服するために様々な戦略が立てられ たが、それらのうちで最も成功したのが、仮想メモリ(virtual memory)である。 仮想メモリとは、システムに実際以上のメモリがあるかのように見せる仕組みであり、 メモリ争奪関係にあるプロセス間で、必要に応じてそれらを協調して使用することに より実現されている。
仮想メモリは、コンピュータのメモリを大きく見せること以外にも様々な機能を 提供している。メモリ管理サブシステムが提供する機能には、次のようなものがあ る。
オペレーティングシステムは、システム上に実際以上のメモリがあるかのように 振る舞う。仮想メモリはシステム上の物理メモリより、何倍も大容量にできる。
システム上のプロセスは、各々が独自の仮想アドレス空間を持っている。これらの 仮想アドレス空間は、お互いに完全に独立しているので、あるアプリケーションを実行 しているプロセスは、他のプロセスに影響を与え得ない。 さらに、メモリエリアはハードウェア上の仮想メモリ機構によって、書き込みから保護 されている。 これによって、コードやデータを、出来の悪いアプリケーションによる上書きから 保護している。
メモリマッピング(memory mapping)は、イメージやデータファイルをプロセスの アドレス空間にマップ(map)するために使用される。メモリマッピングにおいて、 ファイルの内容は、プロセスの仮想アドレス空間に直接リンクされる。
メモリ管理サブシステムによって、システム上で実行されている個々のプロセスは、 システムの物理メモリ上に公正な持ち分を所持することができる。
仮想メモリはプロセスが個別の(仮想)アドレス空間を持つようにしているが、
複数のプロセスでメモリを共有(share)しなければならない場合もある。たとえば、bash のコマンドシェルを実行しているプロセスがシステム上に複数存在するこ
とがある。その場合、物理メモリ内に複数の bash のコピーが存在して、
個々のプロセスが個別の仮想アドレス空間を持つよりも、ひとつだけのコピーが存在
し、bash を実行するすべてのプロセスでその仮想アドレス空間を共有する
ほうが効率がよい。動的ライブラリ(dynamic library)は、複数のプロセス間で実行
コードを共有するもうひとつの典型例である。
共有メモリ(shared memory)は、プロセス間通信(Inter Process Communication, IPC)のメカニズムでも使用される。それは、ふたつ以上のプロセスが、それらすべて に共通のメモリを経由して、情報を交換する仕組みである。Linux は、Unix System V の共有メモリ IPC をサポートしている。
図表(3.1) 仮想アドレスから物理アドレスへのマッピングに関する抽象モデル
Linux が仮想メモリをサポートする方法を考える前に、煩瑣な詳細を省いた抽象 モデルを検討することは有益である。
プロセッサがプログラムを実行するとき、プロセッサはメモリから命令を読み出し て、デコード(decode)する。命令をデコードする際、プロセッサは、ある地点の メモリの内容を読み出したり(fetch)、書き込んだり(store)することが必要になる場合 もある。そして、プロセッサはその命令を実行し、プログラムの次の命令に移る。 このように、プロセッサはいつもメモリにアクセスしながら、命令を読み出したり、 あるいは、データを読み書きしたりしている。
仮想メモリシステムでは、それらに使用されるアドレスはすべて仮想アドレスで あり、物理アドレスではない。それらの仮想アドレスはプロセッサによって物理 アドレスに変換されるのだが、その変換は、オペレーティングシステムが管理する 変換テーブルに保持された情報を基にして行われる。
この変換を容易にするため、仮想メモリと物理メモリは、ページ(page)と呼ばれる 扱い易い単位に分割されている。それらのページはすべて同じサイズである。ページ のサイズは必ずしも同一である必要はないのだが、同一サイズでない場合、システム による管理が非常に困難なものになるためにそうされている。Alpha AXP システム上 の Linux では、8 k バイトのページを使用し、Intel x86 システムでは、4 k バイト のページが使用されている。ページそれぞれには、他と重複しない数値のページ フレーム番号(Page Frame Number, PFN)が割り振られている。
このようにページ分割されたシステムの場合、仮想アドレスは、オフセット(offset) と仮想ページフレーム番号(PFN)のふたつの部分から構成される。ページサイズが 4 k バイトならば、仮想アドレスの bit 11 から 0 にオフセットが含まれていて、 bit 12 以降が仮想ページフレーム番号となっている。 プロセッサは仮想アドレスに出会うたびに、オフセット番号と仮想ページフレーム 番号を抽出する。プロセッサは、仮想ページフレーム番号を物理ページフレーム番号 に変換し、その上で、該当する物理ページの正しいオフセット番号の位置にアクセス する。その変換のために、プロセッサはページテーブル(page table)を使用する。
図表(3.1)は、プロセス X とプロセス Y というふた つのプロセスの仮想アドレス空間を示すもので、どちらもプロセス自身のページテー ブルを持っている。それらのページテーブルは、プロセスの仮想ページをメモリの物理 ページにマップするものである。この図表では、プロセス X の仮想ページフレーム番 号 0 が物理ページフレーム番号 1 にマップされ、プロセス Y の仮想ページフレーム 番号 1 が物理ページフレーム番号 4 にマップされている。理論的には、ページテーブ ル内のそれぞれのエントリーには、次の情報が含まれている。
ページテーブルのエントリが有効かどうかを示す。
そのエントリが記述している物理ページフレーム番号。
そのページが利用される方法を記述している。書き込み可能か、 実行コードを含むかといったことに関係する情報。
ページテーブルにアクセスする場合、仮想ページフレーム番号が(ページテーブル への)オフセットとして使用される。仮想ページフレーム番号の 5 は、ページテーブ ルの 6 番目の要素に該当する。(0 が最初の要素に該当するためである。)
仮想アドレスを物理アドレスに変換する場合、プロセッサはまず仮想アドレスページ フレーム番号とその仮想ページ内のオフセット値を探さなければならない。ページサ イズを 2 の n 乗とすることで、マスク操作(masking)とシフト操作(shifting)により それは簡単に実行できる。もう一度 図表(3.1)を見てほ しい。ページサイズが 0x2000 バイト(十進数なら 8192)で、プロセス Y の仮想アド レス空間でのアドレスが 0x2194 だとすると、プロセッサがそのアドレスを変換した 結果は、オフセット値 0x194 を持つ仮想ページ番号 1 となる。
プロセッサは、仮想ページフレーム番号をプロセスのページテーブルへの インデックスとして使用することで、そのページテーブルエントリを知る。もしその オフセット位置にあるページテーブルエントリが有効(valid)ならば、プロセッサはその エントリから物理ページフレーム番号を取得する。エントリが無効なら、プロセスは 物理メモリ上に存在しない仮想メモリ領域にアクセスしたことになる。その場合、 プロセッサはアドレスを解決できないので、オペレーティングシステムに制御を渡す ことで、問題の解決を依頼する。
現在のプロセスが有効な変換先のない仮想アドレスにアクセスしようとしたことを プロセッサがオペレーティングシステムに伝える方法は、プロセッサの種類によって 異なる。しかしプロセッサの伝達方法がどのようなものであれ、その現象 はページフォルト(page fault)と呼ばれていて、オペレーティングシステムには、 フォルトとなった仮想アドレスとフォルトが生じた原因とが通知される。
ページテーブルのエントリが有効であった場合、プロセッサは、物理ページフレーム 番号を取得し、それにページサイズを掛け算して、物理メモリ内のページのベース アドレス(base address)を取得する。最後に、プロセッサは、(そのベースアドレス を起点に)取得すべき命令やデータまでのオフセットを、そのベースアドレスに加える (ことで、完全な物理アドレスを得る)。
上記の例を再び取り上げると、プロセス Y の仮想ページフレーム番号 1 は、 物理ページフレーム番号 4 にマップされる。その物理ページフレームは、アドレス 0x8000(4 x 0x2000)を起点(ベースアドレス)としている。そのアドレスに 0x194 バイトのオフセット値を加えると、最後に 0x8194 という物理アドレスが得られる。
仮想アドレスから物理アドレスへのマッピングにこうした方法を使用することで、 仮想メモリからシステムの物理メモリへのマッピングが、その番号と無関係に可能と なる。たとえば、 図表(3.1)において、プロセス X の 仮想ページフレーム番号 0 は、 物理ページフレーム番号 1 にマップされるが、仮想ページフレーム番号 7 は、仮想 ページフレーム 0 より大きな番号であるにも関わらず、物理ページフレーム 0 に マップされる。このことは、仮想メモリ機構が興味深い副産物を持つことを意味す る。すなわち、仮想メモリのページは、物理メモリ内で特定の順番通りに並んでいる 必要がないということである。
仮想メモリに比べて物理メモリは非常に量が少ないので、オペレーティングシステム は物理メモリを効率的に使うよう気を配らなければならない。物理メモリを節約す るひとつの方法は、実行中のプログラムが現在使用している仮想ページだけをロード することである。たとえば、データベースプログラムがデータベースに問い合わせを 実行したとする。その場合、データベース全体がメモリにロードされる 必要はなく、調べる必要のあるデータレコードだけがロードされればよい。データ ベースへの問い合わせが検索である場合、新規レコード追加の処理をするデータ ベースプログラムのコードをロードしても意味がない。アクセスされた仮想ページだけ をメモリにロードするというこのテクニックは、デマンドページング(demand paging) と呼ばれる。
プロセスが物理メモリ上にない仮想アドレスにアクセスしようとした場合、プロ セッサは、参照された仮想ページのページテーブルエントリを見つけることができな い。たとえば、 図表(3.1) では、プロセス X の ページテーブルには、仮想フレーム番号 2 のエントリがないので、プロセス X が 仮想ページフレーム番号 2 の中にあるアドレスを読もうとしても、プロセッサは、 そのアドレスを物理メモリ上のアドレスに変換できない。この時点で、プロセッサは、 ページフォルトが発生したことをオペレーティングシステムに通知する。
フォルトとなった仮想アドレスが無効なものである場合、それはプロセスが存在 しない仮想アドレスにアクセスしようとしたことを意味する。おそらく、アプリ ケーションに不具合が起こって、たとえばメモリ内のランダムなアドレスへ書き込み をしようとしたのかもしれない。この場合、オペレーティングシステムはその プロセスを終了させて、暴走したそのプロセスからシステム内の他のプロセスを 保護する。
しかし、フォルトとなった仮想アドレスが有効なものであり、参照されたページは そのときメモリ内になかっただけである場合、オペレーティングシステムは、ディスク 上のイメージから適切なページをメモリ内に持ってこなければならない。ディスク アクセスは、相対的に時間の掛かる処理なので、プロセスは、ページが来るまでの間 待っている必要がある。その際に実行可能なプロセスがあれば、オペレーティ ングシステムはそのいくつかを選んで実行する。そして、取ってきたページを空いた 物理ページフレームに書き込んで、仮想ページフレーム番号用のエントリーを プロセスのページテーブルに追加する。それによって、プロセスはメモリフォルトが 発生した命令があった場所から再び実行される。今度は、仮想メモリへのアクセスに 成功し、プロセッサも仮想アドレスから物理アドレスへの変換ができるので、 プロセスの実行は継続する。
Linux は、デマンドページングを使用して、実行イメージをプロセスの仮想メモリ にロードする。コマンドが実行される際はいつも、そのコマンドを含むファイルが オープンされ、ファイルの内容がプロセスの仮想メモリにマップされる。その処理は、 そのプロセスのメモリマップを記述しているデータ構造体を修正することにより 行われるので、メモリマッピング(memory mapping)と呼ばれる。しかし、実際に物理 メモリに置かれるのはイメージの最初の部分だけであり、残りはディスクに保存され たままとなる。 したがって、イメージが実行されるとページフォルトが起こり、Linux は、プロセスの メモリマップを利用して、イメージのどの部分をメモリに持ってくれば実行が完遂でき るのかを判断する。
あるプロセスが仮想ページを物理メモリに持ってこなければならないのだが、利用 可能な物理メモリの空きがない場合、オペレーティングシステムは、別のページを物 理メモリから取り除くことでそのページのための空間を確保しなければならない。
物理メモリから取り除くべきページがイメージやデータファイルのコピーであり、 上書きされてはいない場合、そのページは保存する必要はない。破棄しておいて、プロ セスが再度そのページを必要としたときに、該当するイメージやデータファイルから メモリ内に戻せばそれでよい。
しかし、ページが変更されている場合には、オペレーティングシステムは、その ページを維持して、後でそのページにアクセスできるようにしなければならない。 この種のページは、ダーティページ(dirty page)と呼ばれ、メモリから削除されると きにスワップファイルと呼ばれる特別なファイルに保存される。スワップファイルへ のアクセスには、プロセッサとメモリとの間のスピードと比べて非常に長い時間が掛 かるので、オペレーティングシステムは、ページをディスクに書き込む必要がある場合 でも、再使用に備えて出来るだけそれをメモリに保持する必要がある。
破棄やスワップするページを決めるために使用されるアルゴリズム(スワップ アルゴリズム)の効率が悪い場合、スラッシング(thrashing)と呼ばれる状態に陥る。 その場合、ページは間断なくディスクに書き込まれたり読み出されたりするので、 オペレーティングシステムはそれに時間を取られて本来の仕事が出来なくなる。 たとえば、もし物理ページフレーム番号 1 ( 図表(3.1)) が定期的にアクセスされるなら、 そのページはハードディスクにスワップされるべきではない。プロセスが現在使用し ているページセットは、ワーキングセット(working set)と呼ばれる。効率の良い スワップスキームとは、すべてのプロセスが自分のワーキングセットを物理メモリに 持つよう手配するスキームである。
Linux は、最も使用頻度の少ない(最長時間未使用(Least Recently Used, LRU)) ページの寿命を縮める(エイジング(aging))というテクニックを使って、システム から削除すべきページを公平に選択している。このスキームでは、システム内のすべ てのページが寿命(age)を持っていて、それがページアクセスされると、変更される 仕組みになっているいる。 ページへのアクセスが多ければ、そのページの寿命は長くなる。アクセスが少な ければ寿命が縮み、必要性が薄れる。寿命が尽きたページは、スワッピングの有力な 候補となる。
仮想メモリ機構は、複数のプロセスでのメモリの共有を実現しやすくする。メモリ へのアクセスはすべてページテーブル経由で行われ、プロセスはそれぞれ自分の独立 したページテーブルを持っている。ふたつのプロセスがメモリ内の物理ページを共有す るには、その物理ページのフレーム番号が、両者のページテーブル内のエントリに 存在する必要がある。
図表 3.1 では、ふたつのプロセスが物理ページフレーム番号 4 を共有している 様子が示されている。プロセス X にとって、これは仮想ページフレーム番号 4 であ り、プロセス Y にとって、これは仮想ページ番号 6 である。これはページ共有の 興味深い点を示している。共有された物理ページは、それを共有するプロセスにとって 仮想メモリの同じ位置に存在しなくてもよいということである。
オペレーティングシステム自体が仮想メモリ内で実行されるというのはほとんど ナンセンスである。オペレーティングシステムが自分のページテーブルを管理しなけ ればならないとしたら、悪夢のような状況になるだろう。大部分の汎用プロセッサ は、仮想アドレスモードと同時に物理アドレスモードという概念をサポートしてい る。物理アドレスモードでは、ページテーブルは不要であり、プロセッサはこのモー ドのときはアドレス変換をしようとしない。Linux カーネルは、この物理アドレス モードで実行されるようにリンクされている。
Alpha AXP プロセッサは、特に物理アドレスモードというのは持っていない。 そのかわり、メモリ空間をいくつかのエリアに分割していて、そのうちのふたつを 物理的にマッピングされたアドレス空間として使用する。このカーネルアドレス空間 は、KSEG アドレス空間と呼ばれていて、0xfffffx0000000000 以上のすべてのアドレス を包含している。KSEG 領域にリンクされているコード(カーネルコードと定義される コード)を実行したり、その領域のデータにアクセスしたりするためには、そのコード はカーネルモードで実行される必要がある。Alpha 上の Linux カーネルは、 アドレス 0xfffffc0000310000 から実行されるようにリンクされている。
ページテーブルのエントリには、アクセス制御情報も含まれている。プロセッサは、 プロセスの仮想アドレスを物理アドレスにマップするためにいつもページテーブルを 使用するので、そこに含まれたアクセス制御情報を利用して、プロセスが許されていな い方法でメモリにアクセスしていないかどうかを簡単にチェックできる。
メモリの特定のエリアへのアクセスを制限すべき理由は数多くある。実行コードを 含むようなメモリは、通常読み出し専用である。オペレーティングシステムは、プロ セスがそのような実行コードの位置にデータを上書きするのを許すべきではない。 反対に、データを含むページは上書きされてもよいわけであり、そのメモリの内容を 実行しようとする命令があった場合、失敗させなければならない。 大部分のプロセッサには、実行に関してカーネルモードとユーザモードという少なく ともふたつのモードがある。カーネルコードをユーザが勝手に実行できないようにする ためであり、プロセッサがカーネルモードで動いているとき以外は、カーネルのデータ 構造へのアクセスを許さないようにするためである。
図表(3.2) Alpha AXP のページテーブルエントリ(PTE)
アクセス制御情報は、PTE に保持されており、それはプロセッサに固有のものであ る。図表(3.2)は、Alpha AXP の PTE を表している。そのビットフィールドは、次の ような意味を持つ。
V 「有効(Valid)」。これが設定されると、PTE が有効となる。
FOE 「実行フォールト(Fault On Execute)」。このページ内で命令が実行されようとし
た際は、プロセッサがページフォルトを報告し、制御をオペレーティングシステム
に渡す。
FOW 「書き込みフォールト(Fault on Write)」。上記と同様だが、このページへ書き込
もうとした場合のページフォルトである。
FOR 「読み込みフォールト(Fault On Read)」。上記と同様だが、このページの読み込も
うとした場合のページフォルトである。
ASM 「アドレス空間合致(Address Space Match)」。これが使用されるのは、オペレー
ティングシステムが変換テープルから数個のエントリだけを削除したいときである。
KRE カーネルモードで実行されているコードは、このページを読むことができる。
URE ユーザモードで実行されているコードは、このページを読むことができる。
GH Granularity hint(粒度ヒント). ひとつのブロック全体を分割せずに単一の変換
バッファにマッピングするときに利用される。
KWE カーネルモードで実行されているコードはこのページに書き込み可能。
UWE ユーザモードで実行されているコードは、このページに書き込み可能。
PFN(page frame number)
V ビットが設定された PTE では、このフィールドには、当該 PTE への物理フレー
ム番号(ページフレーム番号)が書かれている。V ビットが設定されていおらず、こ
のフィールドがゼロでない場合、スワップファイル内でのページの場所に関する情
報が書かれている。
次のふたつのビットは、Linux で定義され、使用されているものである。
_PAGE_DIRTY
これが設定された場合、このページはスワップに書き出される必要がある。
_PAGE_ACCESSED
ページがアクセスされたことを記すために使用される。
上記の理論モデルを使ってシステムを実装した場合、確かに機能はするであろうが、 それほど効率のよいものにはならない。オペレーティングシステムとプロセッサの 設計者はどちらもシステムからよりよいパフォーマンスを引き出そうと懸命に努力 しているからである。より速いプロセッサやメモリを製造するといったことを別に すると、処理速度を上げる最良の方法は、頻繁に使用する情報やデータのキャッシュ を維持管理することである。Linux では、キャッシュに関するいくつかのメモリ管理 機構が利用されている。
バッファキャッシュ(buffer cache)には、ブロックデバイスドライバが使用する
データバッファが含まれている。
[see:
fs/buffer.c]
これらのバッファは固定サイズ(たとえば、512 バイト)で、ブロックデバイスから
読み出されたか、そこに書き込まれた情報のブロックが入っている。ブ
ロックデバイスとは、データアクセスの際に、固定サイズのブロック単位でのみ読み
書きできるデバイスを指す。すべてのハードディスクはブロックデバイスである。
バッファキャッシュは、デバイス識別子と必要なブロック番号とでインデックス付け されていて、データブロックをすばやく見つけだすために使用されるものである。 ブロックデバイスは、バッファキャッシュを経由しなければアクセスできない。 データがバッファキャッシュに見つかれば、たとえばハードディスクのような物理 ブロックデバイスから読み出す必要がなくなるので、アクセスがずっと高速になる。
ページキャッシュ(page cache)は、ディスク上のイメージやデータへのアクセスを
高速化するために使用される。
[see:
mm/filemap.c]
これは、ページ単位でファイルの論理的な内容をキャッシュし、ファイル名と
そのファイル内のオフセットを使ってアクセスされる。ページがディスクからメモリ
に読み出されると、それらはページキャッシュにキャッシュされる。
変更された(あるいは、dirty な)ページだけが、スワップファイルに保存される。
[see: swap.h,
mm/swap_state.c,
mm/swapfile.c]
当該ページがスワップファイルに書き込まれてから変更されていない場合は、再度
スワップアウトされたとしても、同じページがすでにスワップファイル内にあるわけ
だから、スワップファイルに書き込む必要はない。そのページは単に破棄される。
システムがスワップを頻繁に使用する場合、これによって時間の掛かる不必要な
ディスク操作を大幅に省略できる。
ハードウェアキャッシュ(hardware cache)の実装として一般的なのが、プロセッサ 内のハードウェアキャッシュである、ページテーブルエントリのキャッシュである。 この場合、プロセッサはいつも直接ページテーブルを読み出すのではなく、変換が 必要であったときにそのページ変換をキャッシュしておく。プロセッサ内には、 アドレス変換バッファ(Translation Look-aside Buffer, TLB)があり、そこには、 システム上の複数のプロセスに関するページテーブルエントリのコピーがキャッシュ されている。
仮想アドレスへの参照が行われるとき、プロセッサは合致する TLB エントリを 探そうとする。それが見つかれば、仮想アドレスを直接物理アドレスに変換して、 データに対して適切な処理を実行する。プロセッサが合致する TLB エントリを見つけ 出せない場合は、オペレーティングシステムに助けを求める。すなわち、プロセッサ は、オペレーティングシステムに対して、TLB 失敗(TLB miss)が起こったことをシグ ナルで伝える。システム固有のメカニズムを使用して、その例外(exception)をオペ レーティングシステムの例外処理コードに渡す。オペレーティングシステムは、その シグナルを受けて、アドレスマッピングのための新しい TLB エントリを生成する。 例外がクリアされると、プロセッサは再度仮想アドレスの変換を試みる。今回は、 TLB 内に必要なアドレスに関する有効なエントリがあるので、問題なく変換される。
ハードウェアキャッシュやその他のキャッシュを使う場合の欠点は、手順を簡略化 するために、これまで以上の時間とメモリ空間を使ってそうしたキャッシュを維持し なければならないということであり、もしキャッシュが壊れると、システムがクラッ シュするということである。
図表(3.3) 3 つのレベルのページテーブル
Linux では、3 つのレベルのページテーブルの存在が前提になっている。アクセス される個々のページテーブルには、次の段階のページテーブルにおけるページ フレーム番号が含まれている。図表(3.3)では、仮想アドレスがいくつかのフィールド に分割されている様子が示されている。図中の仮想アドレスの個々のフィールドが 提供するのは、特定のページテーブルへのオフセットである。プロセッサは、 仮想アドレスを物理アドレスに変換するため、まず個々のレベルのフィールドの 内容を取得して、その内容を当該レベルのページテーブルを含む物理ページ上での オフセットへと変換し、それによって次のレベルのページテーブルのページフレーム 番号を読み取る。この処理を三度繰り返すと、その仮想アドレスを含んだ物理ページ のページフレーム番号が分かる。仮想アドレスの最後のフィールドは、バイト オフセット(byte offset)となっていて、それを使用して当該物理ページ内で必要な データを見つけ出す。
Linux を実行するプラットフォームが提供しなければならないのが、変換マクロ
である。これは、カーネルが特定のプロセスのためにページテーブルを走査すること
を可能にするものである。そうすることで、カーネルはページテーブルエントリの
フォーマットや、その仕組みを知る必要がなくなる。
[see:
include/asm/pgtable.h]
この方法は非常に成功しているので、Linux は、ページテーブル操作のコードとして
Alpha プロセッサにも Intel x86 プロセッサにも同じものを使用している。ただ、
Alpha プロセッサは、3 つのレベルのページテーブルを持つが、Intel x86 は、
2 つのレベルのページテーブルを持つという違いがある。
システム内の物理メモリに対する需要は大きい。たとえば、イメージがメモリに ロードされるとき、オペレーティングシステムは、それに物理ページを割り当てる。 イメージが実行を終了し取り除かれたら、そのページは解放される。物理メモリは他 にも、ページテーブル自体のようなカーネル固有のデータ構造を保持する用途に使用 される。ページ割り当てと解放に使用されるメカニズムとデータ構造は、仮想メモリ サブシステムの効率を維持する上でおそらく最も重要なものである。
システム内のすべての物理ページは
mem_map というデータ構造に
よって記述されている。それは、
mem_map_t
構造体(
脚注 1 )の
リストであり、それらは起動時に初期化される。
[see:
include/linux/mm.h]
個々の mem_map_t は、システム内の単一の物理ページを記述する。(メモリ
管理に関する限り)その構造体の重要なフィールドには、次のようなものがある。
count これは、そのページのユーザ数のカウンターである。ページが複数のプロセ
スで共有されている時、このカウントは 1 より多くなる。
age このフィールドは、ページの 寿命(age)を記述するもので、そのページが破棄
やスワップの候補であるかを判断するのに使われる。
map_nr これは、mem_map_t が記述する物理ページのフレーム番号である。
free_area という配列も、ページ割り当
てのコードにより、ページの検索と解放のために使用される。すべてのバッファ管理
スキームはこのメカニズムによってサポートされており、そのコードに関する限り、
プロセッサの物理ページングメカニズムとページサイズとの間には、関連性がない。
free_area の個々の要素は、ブロック単位
のページに関する情報を含んでいる。
すなわち、配列の最初の要素はひとつのページ、次が 2 つのページから成るブロック、
さらに次が 4 つのページから成るブロックというふうに 2 の n 乗でブロックのページ
数が増える。
構造体の要素
list はキューの先頭として
使用され、
mem_map 配列内の
page データ構造体へのポインタとなっている。
(訳注: list は、v2.0.12 以降は、next と prev による
二重連結リストになっています。)
空のページブロックはこのキューに並べられる。
map は個々のサイズのページグループの割り当て状態を管理してい
るビットマップ(bitmap)に対するポインタである。bitmap の N ビット目は、ページの
N 番目のブロックが空である場合にセットされる。
図表(3.4)では、free_area 構造体が示
されている。
要素 0 はひとつの空ページ(ページフレーム番号 0 )を持っており、要素 2 は 4
つのページから成る 2 つの空ブロックを持っている。最初の空ブロックは、ページ
フレーム番号 4 から始まり、次の空ブロックはページフレーム番号 56 から始まって
いる。
Linux は、相棒アルゴリズム
(
Buddy algorithm)
(脚注 2)
を使用することで、ページブロックを効率的に割り当てたり解放したりしている。
[see: __get_free_page(), in
mm/linux/page_alloc.c]
ページ割り当てのコードは、ひとつもしくは複数のページから成るブロックを割り当
てようとする。ページの割り当ては、大きさとして 2 の n 乗のブロック単位となって
いる。すなわち、ひとつのブロックに 1 つのページ、2 つのページ、4 つのページ等が
割り当てられる。システム内に要求(nr_free_pages >
min_free_pages)に応えられるだけの空き空間があれば、割り当て
コードは、要求されたサイズのページ数でブロックを作成するために
free_area を調べる。
free_area のそれぞれの要素は、該当するサイズのブロックに関するマップ
を持っていて、割り当て済みもしくは空いているページブロックが参照できるように
なっている。たとえば、配列の要素 2 が持つメモリマップでは、4 つのページから成る
それぞれのブロックのどれが割り当て済みであり、どれが空なのかが記録されている。
割り当てアルゴリズムは、まず要求されたサイズのページブロックを探す。それは、
free_area データ構造体のキューにある、
list 要素上から、空のページの連続を調
べる。もし要求されたサイズのページブロックでは空きがない場合、
次のサイズ(これは要求されたサイズの 2 倍である)のブロックがないか調査する。
この過程は、free_area のすべてが調べられるか、ページブロックが見つかる
かするまで続けられる。見つかったページブロックが当初の要求よりも大きい場合、
適切なサイズになるまで分割される。ブロックは 2 の n 乗のページから成り立つの
で、この分割プロセスは半分に割るだけの簡単なものである。空ブロックは適当な
キュー上に並べられ、割り当てられるページブロックが、呼び出しをしたプロセスに
返される。
図表(3.4) free_area のデータ構造
たとえば、図表(3.4)では、2 つのページから成るブロックが要求された場合、
(ページフレーム番号 4 から始まっている) 4 つのページから成る最初のブロック
が、2 つのページから成るふたつのブロックに分割される。ページフレーム番号 4
から始まる最初のブロックは、割り当てられたページとして呼び出したプロセスに
戻され、ページフレーム番号 6 から始まる二番目のブロックは、
free_area 配列の要素 1 上にある 2 つのページから
成る空ブロックとしてキュー上に置かれる。
ページブロックの割り付けは、大きな空ページを小さく分割するので、
断片化したメモリ(framgment memory)を生じやすい。
[see: free_pages(), in
mm/page_alloc.c]
ページを解放するコード(page deallocation code)は、
可能なときはいつでも、空のページをより大きなブロックに連結する。実際、
ブロックをまとめてより大きなブロックを簡単に作れることを考えると、
この(2 の n 乗という)ページブロックサイズには重要な意味がある。
ページブロックが解放されると、同じサイズの近接ブロックもしくは相棒(buddy) ブロックが空かどうかチェックされる。もしそうなら、新しく解放されたページ ブロックと結合して、一段階大きいサイズの新しい空ブロックを作成する。ふたつの ページブロックが結合されてより大きな空のページブロックが形成されるたびに、 ページ解放コードは、そのブロックをさらに大きなものにしようとする。このように して、空のページブロックは、メモリの使用方法として許される限り大きなブロックに なっていく。
たとえば、
図表(3.4)では、ページフレーム番号 1 が
解放されると、すでに解放されていたページフレーム番号 0 と結合される。そして、
2 つのページから成る空ブロックとして
free_area の要素 1 上のキューに置かれる。
イメージが実行されるとき、その実行イメージの内容は、プロセスの仮想アドレス 空間に置かれなければならない。このことは、実行イメージで使用するためにリンク された共有ライブラリの場合でも同じである。実行ファイルは実際に物理 メモリに置かれるわけではなく、プロセスの仮想メモリにリンクされるだけである。 そして、実行中のアプリケーションからそのプログラムの一部が参照されると、実行 イメージ内のその部分のイメージがメモリの中に置かれる。あるイメージを、プロセ スの仮想アドレス空間にリンクさせるこの仕組みは、メモリマッピング (memory mapping)と呼ばれる。
図表3.5 仮想メモリのエリア
すべてのプロセス仮想メモリは、
mm_structデータ構造体で表現される。これには、現在実行中のイメージ(たとえば、
bash)に関する情報が含まれると同時に、
いくつかの
vm_area_struct データ
構造体へのポインタも含まれる。
vm_area_struct データ構造体には、その仮想メモリ領域の始点と終点、
そのメモリへのプロセスのアクセス権、およびそのメモリに対する一連の操作ルーチン
が含まれている。これらの操作ルーチンは、Linux がこの仮想メモリの領域を操作する
際に使わなければならない一連のルーチンである。たとえば、仮想メモリ操作のひと
つに訂正処理があり、それはプロセスが仮想メモリにアクセスしようとしたが、
(ページフォルトによって)その仮想メモリが実際には物理メモリ上にないことが分
かった時になされる。この操作は、
nopage 操作である。
nopage 操作が利用されるのは、Linux のデマンドページングにより実行
イメージのページが物理メモリ内にページを割り当てられるときである。
実行イメージがプロセス仮想アドレスにマップされるとき、
vm_area_struct データ構造が一組生成される。
vm_area_struct データ構造体はそれぞれ実行イメージの一部を表している。
実行コード、初期化されたデータ(変数)、初期化されないデータ等につき、ひとつづつ
の構造体が生成される。Linux はいつくかの標準的な仮想メモリ操作をサポートしてい
るので、vm_area_struct データ構造体が生成されると、仮想メモリ操作の
適切なセットがそれらと結びつけられる。
実行イメージがいったんメモリにマップされてプロセス仮想メモリに入ると、
イメージの実行開始が可能となる。しかし、そのイメージの最初の部分だけしか物理
メモリに入っていないので、すぐに物理メモリ内にない仮想メモリ領域へとアクセス
がある。プロセスが、有効なページテーブルエントリを持たない仮想アドレスに
アクセスしたとき、プロセッサは Linux にページフォルトの発生を報告する。
[see: handle_mm_fault, in
mm/memory.c]
ページフォルトは、そのページフォルトが発生した仮想アドレスと、発生の原因と
なったメモリアクセスのタイプとの情報を含んでいる。
Linux は、ページフォルトが起こったメモリ領域を示している
vm_area_struct 構造体を探す。
vm_area_struct データ構造での検索はページフォルト
処理の効率を決定する上で非常に重要なので、それらは、AVL(Adelson-Velskii and
Landis)木構造にリンクされている。もし、フォルトが起こった仮想アドレスに
関する vm_area_struct データ構造体が存在しない場合、このプロセスは、
無効な仮想アドレスにアクセスしたことになる。Linux は、そのプロセスに SIGSEGV
シグナルを送り、もしそのプロセスが当該シグナルを処理しない場合は、そのプロセス
を終了させる。
次に、Linux は、その仮想メモリ領域のアクセス権限に違反して起こったページ フォルトのタイプをチェックする。プロセスが、たとえば読み出ししか許されない領域 に書き込みをしようとした場合のように、無効な方法でメモリにアクセスしている 場合、そのプロセスにはメモリエラー(memory error)のシグナルも送られる。
Linux がページフォルトが正当なものと判断した場合、ページフォルトに対処しな
ければならない。
[see: do_no_page(), in
mm/memory.c]
Linux は、スワップファイル内のページとディスクの他の場所にある実行イメージの
一部とを区別しなければならない。それをするためには、フォルトが起こった仮想アド
レスのページテーブルエントリが使用される。
フォルトページのページテーブルエントリが無効だが空でない場合、そのページ フォルトは、現在スワップファイルに保存されているページのものである。Alpha AXP のページテーブルエントリの場合、有効ビットは設定されていないが PFN フィールドに 0 でない値が設定されている エントリがある。その場合、PFN フィールドには、 スワップのどこに(そしてどのスワップファイルに)当該ページが保存されているのか に関する情報が記されている。スワップファイル内のページを操作する方法は、 この章の後の部分で紹介される。
vm_area_struct データ構造体のすべ
てが、仮想メモリ操作のセットを持っているわけではなく、nopage 操作すらもっていな
い場合もある。これは、デフォルトでは Linux が、アクセスの問題を解決するために、
新しい物理ページを割り付け、そのための有効なページテーブルエントリを作成するよ
うになっているからである。(vm_area_struct に)この仮想メモリ領域に
対する nopage 操作が存在する場合、Linux はそのルーチンを使用する。
汎用的な Linux の nopege 操作ルーチンは、メモリにマップされた実行イメージに
対して使用されるものなので、その nopage 操作ルーチンは、ページキャッシュを
利用して、必要なイメージページを物理メモリに持ってくる。
[see: filemap_nopage(), in
mm/filemap.c]
方法はどうあれ、必要なページが物理メモリに置かれた場合は、 プロセスページテーブルはアップデートされる。それらのエントリをアップデート するためにはハードウェア固有の処理が必要になるかもしれない。特に、プロセッサ がアドレス操作バッファ(Translation Look-aside Buffer, TLB)を利用している場合は そうである。これでようやくページフォルトは処理されたので、フォルトは解除さ れ、プロセスは、仮想メモリアクセスでフォルトを起こした命令の時点から再 スタートされる。
図表3.6 Linux のページキャッシュ
Linux のページキャッシュの役割は、ディスク上のファイルへのアクセス速度を
上げることである。メモリにマップされたファイルはページ単位で読み出され、それら
のページはページキャッシュに保存される。図表(3.6)では、ページキャッシュが
page_hash_table から構成されており、それ
が
mem_map_t データ構造へのポインタの配列
となっていることが示されている。
[see:
include/linux/pagemap.h]
Linux 内のファイルはそれぞれ VFS inode データ構造で識別される(詳細は、 「ファイルシステム」の章で述べる)。VFS inode は システム上ユニークであり、特定の単一のファイルに関する完全な識別子となる。 ページテーブルへのインデックスは、ファイルの VFS inode とそのファイルへの オフセットから導き出される。
メモリにマップされたファイルからページが読み出されるとき、たとえばデマンド
ページングでページがメモリに戻されるときなどには、ページはページキャッシュか
ら読み出される。
ページがキャッシュ内にある場合は、そのキャッシュ内のページを表す
mem_map_t データ構造体へのポインタが、ページフォ
ルト処理コードに返される。
そうでない場合は、ページは、そのイメージを保存しているファイルシステムから
メモリ内へと取り出さる必要がある。その場合、Linux は物理ページを割り付けて、
ディスク上のファイルからそのページを読み出す。
要求がなくても、Linux の側でファイル内の次のページを読み出しておくことも 可能である。この単一ページの先読みは、もしプロセスがファイル内のページに連続 してアクセスしている場合は、そのプロセスのために次のページをメモリ内に待機さ せることを意味する。
イメージが読み出されて実行されていくと、ページキャッシュはだんだんと大きく なる。必要のなくなったページ、たとえばどのプロセスからもアクセスされなくなった イメージは、キャッシュから削除される。 メモリの使用量が増えると、物理ページが不足してくることがある。その場合、 Linux はページキャッシュのサイズを小さくする。
物理メモリが少なくなると、Linux のメモリ管理サブシステムは、物理ページを
解放するよう努力しなければならない。このタスクは、カーネルスワップデーモン
(kernel swap daemon)(kswapd)の仕事である。
カーネルスワップデーモンは、カーネルスレッド(kernel thread)という特別な
プロセスである。
カーネルスレッドは仮想メモリを持たず、そのかわり物理アドレス空間内において
カーネルモードで実行される。このカーネルスワップデーモンは、その役割が
単にページをシステムのスワップファイルに書き出すだけでないことからすると、
やや命名に難があるといえる。その役割は、システム内で充分な空ページを
確保して、メモリ管理システムの操作効率を維持することである。
カーネルスワップデーモン(kswapd)は、起動時にカーネル初期化プロセ
スにより起動され、カーネルスワップタイマーが定期的に時間切れになるのを待って
いる。
[see: kswapd(), in
mm/vmscan.c]
タイマーが時間切れになると、スワップデーモンはシステムの空ページの数が減りす
ぎていないかどうかを確認する。kswapdは、
free_pages_high と
free_pages_low のふたつの変数を使ってページを解放するかどうかを判断
する。
システム内の空ページの数が free_pages_high よりも多い限り、カーネル
スワップデーモンは何もしない。タイマーが切れるまで再び休憩する。このチェックに
際して、カーネルスワップデーモンは、スワップファイルに現在書き出されている
ページ数を考慮に入れる。カーネルスワップデーモンは、その数を、nr_async_pages に保持している。この数は、スワップファイルに書き出される
ためにページがキューに入れられたときに増加し、スワップデバイスへの書き込みが
完了したときに減少する。free_pages_high と free_page_low と
は、システム起動時にセットされ、システム内の物理ページの数と関連付けられる。
システム内の空ページの数が free_page_high 以下になるか、free_pages_low 以下にまで落ち込んでしまった場合には、カーネルスワップ
デーモンは、3 つの方法を使ってシステムで使用されている物理ページの数を減ら
そうとする。
システムの空ページの数が free_pages_low 以下になっている場合、
カーネルスワップデーモンは、次の実行時までに 6 つのページを解放する。でなけれ
ば、3 つのページを解放する。上記の方法は、充分なページが解放されるまで順番に
繰り返される。カーネルスワップデーモンは、物理メモリを解放するとき最後に
使った方法を覚えている。実行の際はいつも、前回の最後に成功した方法を使用して
ページを解放しようとし始める。
充分な空ページが出来たら、スワップデーモンは、タイマーが切れるまで再び休憩
に入る。カーネルスワップデーモンがページを解放した理由が、システム内の空ページ
の数が free_pages_low を下回ったからであった場合は、その休憩時間は、
通常の半分に短縮される。空ページの数が free_pages_low の数を超えて
しまえば、カーネルスワップデーモンは通常のタイマー間隔での休憩に戻る。
ページキャッシュとバッファキャッシュに保存されているページは、解放して
free_area 配列に入れるべき有力な候補者である。
ページキャッシュには、メモリにマップされたファイルのページが含まれているので、
メモリを満杯にしている不要なページが含まれている場合がある。同様に、バッファ
キャッシュには、物理デバイスに対する読み書きの結果としてのバッファが含まれてい
るので、ここにも必要のないバッファが含まれている場合がある。
システム内の物理ページが不足し始めると、これらのキャッシュからページを削除する
ことは相対的に容易になる。ページをメモリからスワップアウトさせる場合と異なり、
それらは、物理デバイスへの書き込みを必要としないからである。キャッシュから不要
なページをいくつか破棄したとしても、物理デバイスやメモリにマップされたファイル
へのアクセスが遅くなる以外には、目立った有害な副作用はない。しかし、もしそれら
のキャッシュからページをすべて破棄したとしたら、全プロセスが等しく悪影響を受
ける。
カーネルスワップデーモンは、これらのキャッシュを縮小しようとするたびに、
page の配列
mem_map 内のページ
ブロックを調べて、物理メモリから削除できるものがないかどうかを確認する。
[see: shrink_mmap(), in
mm/filemap.c]
カーネルスワップデーモンが熱心にスワップ処理をしている場合、すなわちシステム
の空ページの数が危険なほど低下している場合には、より大きなサイズのページ
ブロックが調査される。ページブロックの調査は循環的な方法でなされる。すなわち、
メモリマップを縮小しようとするたびごとに違うサイズのページブロックが調査され
る。この方法は、時計の分針に似ていることからクロックアルゴリズム
(clock algorithm)と呼ばれ、page の配列
mem_map 全体が、一度に数ページ単位で調査される。
個々のページを調査する際は、そのページがページキャッシュかバッファキャッシュ
にキャッシュされているかどうか確認される。
注意すべきなのは、この時点では共有ページは破棄されないこと、および同時に両方の
キャッシュに入っているページは存在しないことである。
当該ページがどちらのキャッシュにも入っていない場合、page の配列 mem_map の次のページが調査される。
ページがバッファキャッシュにキャッシュされるのは(あるいは、バッファがページ
キャッシュにキャッシュされるのは)、バッファの割り付けと解放とをより効率的に
行うためである。メモリ縮小コードは調査が終わったページのバッファから、解放しよ
うとする。
[see: try_to_free_buffer, in
fs/buffer.c]
それらすべてのバッファが解放されると、それらを含むページも解放される。調査
されたページが Linux のページキャッシュに入っている場合、それはページ
キャッシュから削除され解放される。
この作業によって充分なページが解放されたら、カーネルスワップデーモンは、 次の定期的呼び出しまで休憩する。解放されたページはどのプロセスの仮想メモリ の一部にもなっていなかったので(それらはキャッシュされたページであったので)、 どのページテーブルもアップデートされる必要がない。キャッシュされたページが 充分に解放されない場合、スワップデーモンは共有ページのいくつかをスワップアウト しようとする。
System V 共有メモリとは、プロセス間通信のメカニズムであり、ふたつ以上の
プロセスがお互いに情報を交換するために仮想メモリを共有することを許す仕組み
である。この方法でどのようにプロセスがメモリを共有するかについては、
「プロセス間通信の仕組み」の章で詳細に
解説する。今のところ、System V 共有メモリのそれぞれのエリアは、
shmid_ds データ構造体により記述されているとだけ
述べておく。
これには、
vm_area_struct データ構造体
のリストへのポインタが含まれている。その個々の vm_area_struct データ
構造体は、仮想メモリの当該領域を共有するプロセスのものであり、それぞれのプロセ
スの仮想メモリのどこに System V 共有メモリの領域があるのかを記述するものであ
る。System V 共有メモリのための vm_area_struct データ構造体はそれぞ
れ、
vm_next_shared と vm_prev_shared ポインタを使ってお互いにリンクされている。
個々の shmid_ds データ構造体には、ページテーブルエントリのリストが含ま
れていて、それぞれ共有仮想ページがマップされている物理ページを記述している。
カーネルスワップデーモンは、System V 共有メモリページをスワップアウトする
時にもクロックアルゴリズムを使用する。それが実行される際はいつも、どの共有仮想
メモリエリアのどのページを最後にスワップアウトしたか、カーネルスワップデーモン
は覚えている。それを実現するために、スワップデーモンはふたつのインデックスを
使用する。ひとつは、
shmid_ds データ構造体
のセットへのインデックスであり、もうひとつは、System V 共有メモリの該当エリア
に関するページテーブルエントリのリストへのインデックスである。それによって、
System V 共有メモリに対して公正な負担が課されるようになっている。
System V共有メモリの仮想ページに対する物理ページフレーム番号は、該当する仮想
メモリエリアを共有するすべてのプロセスのページテーブル内に含まれているので、
カーネルスワップデーモンはこれらすべてのページテーブルを書き換えて、該当ページ
はもはやメモリ内にはなく、スワップファイルに保存されているということを示さな
ければならない。共有ページはひとつずつスワップアウトされるので、カーネル
スワップデーモンは、個々の共有プロセスのページテーブル内のページテーブル
エントリを探す。(これは、個々の
vm_area_struct データ構造体のポインタを追跡することにより実行され
る。)
もし、その System V 共有メモリエリアに対するプロセスのページエントリーテーブル
が有効ならば、スワップデーモンは、それを無効だがスワップアウトされたページ
テーブルエントリである旨に書き換えて、その(共有)ページのユーザ数カウントを
ひとつ減少させる。スワップアウトされた System V 共有ページのテーブルエントリの
フォーマットには、
shmid_ds データ構造体の
セットへのインデックスと その System V 共有メモリエリアに対するページテーブル
エントリへのインデックスとが含まれる。
共有プロセスのページテーブルが完全に書き換えられてページカウントがゼロに
なると、共有ページをスワップファイルに書き出すことが可能になる。その System
V 共有メモリエリアに対するページテーブルエントリのなかで、shmid_ds
データ構造体によって指示されたリスト内に存在するものは、スワップアウトされた
ページテーブルのエントリ(swapped out page table entry)によって置き換えられ
る。スワップアウトされたページテーブルのエントリは無効だが、スワップファイルを
オープンするためのセットへのインデックスと、そのファイル内でスワップ
アウトされたページを探すためのオフセットとが含まれている。この情報が使用され
るのは、そのページが物理メモリ内に再度戻されるときである。
スワップデーモンはシステム内のプロセスを順番に調べて、スワップすべき有力
候補がいないかどうかを探す。
[see: swap_out(), in
mm/vmscan.c]
候補者とは、スワップ可能で(不可能なプロセスもあ
る)、メモリ内からスワップか破棄することが可能なひとつ以上のページを持っている
プロセスである。ページが物理メモリからスワップアウトされてシステムのスワップ
ファイルに入れられるのは、ページ内のデータがスワップ以外の方法では元に戻せな
い場合だけである。
実行イメージの内容の多くはそのイメージのファイルからメモリ内に置かれている ので、その内容の再読み出しは簡単に実行できる。たとえば、あるイメージの実行命令 は、そのイメージによって修正されることはないので、それがスワップファイルに書き 込まれることは決してない。それらのページは単に破棄されるだけである。プロセス から再度参照される時は、実行イメージからメモリ内に戻せばいいからである。
スワップすべきプロセスが見つかったら、スワップデーモンはそのプロセスの仮想
メモリ領域を走査して共有されたりロック(lock)されたりしていないエリアを探す。
Linux
は、選択したプロセスのスワップ可能なすべてのページをスワップするわけではない。
むしろ、ごく少数のページだけを削除する。メモリ内でロックされている場合、ページ
はスワップも破棄もできない。
(原注: この操作は、当該プロセスの
mm_struct 上でキューイングされた vm_area_struct 構造体のリストにある
mv_next ポインタを順に検査することで実行される。)
Linux のスワップアルゴリズムは、ページエイジング(page aging)を使っている。
[see: swap_out_vma(), in
mm/vmscan.c]
ページはそれぞれ(
mem_map_t 構造体の中に)
カウンタを持っていて、それによってカーネルスワップデーモンにページがスワップ
されるべきかどうかを伝えている。
ページが使用されなかったりアクセスによって若返らない場合に、ページは歳を取る。
スワップデーモンは高齢のページだけをスワップアウトさせる。ページを最初に
割り付けるときのデフォルトの操作では、最初に 3 の寿命を与える。
アクセスがあるたびに、年齢は 3 から最大 20 まで上がる。カーネルスワップ
デーモンが実行されると、そのたびにページを加齢し、その年限をひとつずつ引いて
いく。こうしたデフォルトの操作は変更可能であり、それゆえ、設定値(と、その他の
スワップに関係した情報)は、
swap_control データ構造体に保存されている。
ページの寿命が尽きたら(age=0)、スワップデーモンはさらにその処理を進める。
修正されているページ(dirty page)は、スワップアウトすることができる。Linux は、
PTE 内のアーキテクチャに固有のビットを使ってそれを区別する。
(
図表(3.2) 参照)
しかし、dirty page がすべてスワップファイルに書き出される必要はない。
あらゆるプロセスの仮想メモリ領域は、それ自身に必要なスワップ操作が指定されて
いるかもしれず(それは、
vm_area_struct 内の vm_ops ポインタ
で示される)、そこでの方法が利用されるからである。そうでない場合、スワップ
デーモンは、ページをスワップファイルに割り付け、スワップデバイスに書き出す。
スワップアウトされたページのページテーブルエントリは、無効とマークされた
エントリによって置き換えられるが、そのエントリには、ページのスワップファイル
内の位置に関する情報が含まれている。その情報は、スワップファイル内のどこに
ページが保存されているかを表すオフセット値と、どのスワップファイルが使用され
たかを示す指示子から成る。
どのようなスワップメソッドが使用された場合でも、もとの物理ページは解放され、
free_area の中に入れられる。内容の変更
されていない(あるいは、修正されていない(not dirty))ページは、破棄されて、
再利用のために free_area に入れられる。
スワップ可能なプロセスのページが、充分な数だけスワップアウトされるか 破棄された場合、スワップデーモンは再度スリープする。次に起きるときは、システ ム内の次のプロセスを対象として考慮する。この方法によって、スワップデーモンは システムがバランスを取り戻すまで、プロセスの物理ページを少しずつ解放してい く。この方法は、プロセス全体をスワップアウトするよりもずっと公平である。
ページをスワップファイルに移す際、Linux は必要がなければページを書き 込まない。あるページがスワップファイルと物理メモリの両方に存在するときがある。 そのようなことが起こるのは、スワップされてメモリから削除されていたページが プロセスに再度アクセスされたことでメモリに戻った場合である。メモリにある ページが書き込みを受けていない限り、スワップファイルにあるページのコピーは 有効なままである。
Linux はそのようなページを監視するためにスワップキャッシュを使う。スワップ キャッシュはページテーブルエントリのリストであり、エントリはシステム上の物理 ページごとに存在する。これは、スワップアウトしたページのページテーブル エントリであり、そのページがどのスワップファイルに保存されているかということ と、そのスワップファイル内での位置とが記されているものである。スワップキャッ シュエントリがゼロでない場合、それは、そのページがスワップファイル内にあり、 しかもそれが変更されていないということを表している。ページの中味がその後で (書き込みをされて)変更された場合、そのエントリはスワップキャッシュから削除 される。
Linux が物理ページをスワップファイルにスワップアウトする必要がある場合、 スワップキャッシュをまず調べる。スワップキャッシュにそのページ用の有効な エントリがあるなら、そのページをスワップファイルに書き出す必要はない。 なぜなら、メモリ内のそのページは、スワップファイルから最後に読み出されて以来 変更されていないからである。
スワップキャッシュのエントリはスワップアウトされたページに関するページテー ブルのエントリである。それらは無効とマークされているが、どのスワップファイル のどこでそのページが見つかるかを Linux に知らせる情報を含んでいる。
書き込みをされてスワップファイルに保存されたページが再度必要となることが
ある。たとえば、アプリケーションが仮想メモリのある領域に書き込みをしたいのだ
が、その内容が物理ページからスワップアウトされていた場合などである。物理メモリ
上にない仮想メモリのページにアクセスがあった場合、ページフォルトが起こる。
ページフォルトとは、プロセッサがオペレーティングシステムにシグナルを送って、
仮想アドレスを物理アドレスに変換できないことを伝えることである。この場合、
原因は、仮想メモリの該当ページの情報を記しているページテーブルのエントリが、
ページがスワップアウトされる際に無効とマークされるからである。プロセッサは
その仮想アドレスを物理アドレスに変換できないので、制御をオペレーティングシス
テムに手渡して、仮想アドレスがフォルトを起こしたこととそのフォルトの理由とを
伝える。この情報のフォーマットとプロセッサがオペレーティングシステムに制御を
渡す方法とは、プロセッサ固有のものである。
[see: do_page_fault(), in
arch/i386/mm/fault.c]
プロセッサ固有のページフォルト処理コードは、まず必要な
vm_struct データ構造を探さなければならない。
vm_area_structは、仮想メモリのエリアを記述したものであり、そのフォルト
が起きた仮想メモリアドレスを含んでいるからである。
フォルト処理コードは、それらの構造体を検索し、フォルトを起こした仮想アドレスを
含むものを見つけだす。これらは、決して長時間掛かってはいけない(time critical)
コードや処理であるので、vm_area_struct 構造体は、検索時間が最短になる
ように並べられている。
プロセッサ固有の動作を適切に処理し、フォルトが起きた仮想アドレスが有効な
仮想メモリ領域にあることが分かった場合、その後のページフォルト処理は、Linux
が稼働するどのプロセッサにも汎用的で適用可能なものとなる。
[see: do_no_page(), in
mm/memory.c]
汎用のページフォルト処理コードは、フォルトを起こした仮想アドレスのページ
テーブルエントリを探す。探し出したページテーブルエントリがスワップアウトされた
ページのものであった場合、Linux はページを物理メモリに戻さなければならない。
スワップアウトされたページに対するページテーブルのエントリはプロセッサ固有の
ものだが、すべてのプロセッサはそれらのページを無効とマークしてあり、そのページ
テーブルエントリにはスワップファイル内で該当ページを見つける際に必要な情報が
書き込まれている。Linux はこの情報を使って、そのページを物理メモリに呼び戻す。
[see: do_swap_page(), in
mm/memory.c]
この時点で、Linux は、フォルトが起こった仮想アドレスを知っており、該当
ページがどこにスワップアウトされているかに関する情報を含むページテーブル
エントリを持っている。
vm_area_struct
構造体にはある
ルーチンへのポインタが含ま
れている場合があり、そのルーチンは、その vm_area_struct 構造体
で記述している仮想メモリ領域の任意のページを物理メモリへと戻す処理をする。
これは、スワップイン(swapin)操作と呼ばれる。
[see: shm_swap_in(), in
ipc/shm.c]
その仮想メモリエリアにスワップイン処理ルーチンが存在する場合、Linux はその
ルーチンを使用する。これは実際、スワップアウトされた System V 共有メモリ
ページが処理される方法でもある。スワップアウトされた System V 共有ページの
フォーマットは通常のスワップアウトされたページのフォーマットとは少し異なるの
で、それには特別な処理方法が必要とされるからである。しかし、そうした
スワップイン処理ルーチンが存在しない場合もあるので、その際には、Linux は、
そのページが特別な処理を必要としない通常のページであると推定する。
[see: swap_in(), in
mm/page_alloc.c]
そして、空の物理ページを割り当て、スワップファイルからスワップアウトされた
ページを読み出す。ページがスワップファイルのどこに(およびどのスワップファイル
に)あるかを示す情報は、無効とマークされたそのページテーブルエントリから取得
される。
ページフォルトを発生させたアクセスが書き込みアクセスでない場合、ページは スワップキャッシュにそのまま残され、そのページテーブルエントリも書き込み可能 とはマークされない。その後、そのページへの書き込みアクセスが発生すると、その 時点で別なページフォルトが生じ、該当するページ dirty とマークされ、そのエント リはスワップキャッシュから削除される。 そのページが書き込みされずに、再度スワップアウトされ る必要が生じた場合、そのページは既にスワップファイルに存在するので、Linux は ページをあらためてスワップファイルに書き込みせずに済ませることができる。
ページがスワップファイルから取ってこられるきっかけを作ったアクセスが書き込み 操作であった場合、そのページはスワップキャッシュから削除され、そのページテー ブルエントリは、dirty かつ書き込み可能であるとマークされる。
(脚注1)紛らわしいことに、この構造体は、ページ構造体とも呼ばれている。
(脚注2)ここに参考文献を置くこと。