|
次のページ
前のページ
目次へ
4. メモリ管理
メモリ管理サブシステムは、オペレーティングシステムの最も重要な部分 のひとつである。コンピュータの黎明期以来、システム上にある物理メモリだけでは 足りない状況がずっと続いてきた。この限界を克服するために様々な戦略が立てられ たが、それらのうちで最も成功したのが、仮想メモリ(virtual memory)である。 仮想メモリとは、システムに実際以上のメモリがあるかのように見せる仕組みであり、 メモリ争奪関係にあるプロセス間で、必要に応じてそれらを協調して使用することに より実現されている。
仮想メモリは、コンピュータのメモリを大きく見せること以外にも様々な機能を 提供している。メモリ管理サブシステムが提供する機能には、次のようなものがあ る。
4.1 仮想メモリの抽象モデル
図表(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 ページがアクセスされたことを記すために使用される。
4.2 キャッシュ上記の理論モデルを使ってシステムを実装した場合、確かに機能はするであろうが、 それほど効率のよいものにはならない。オペレーティングシステムとプロセッサの 設計者はどちらもシステムからよりよいパフォーマンスを引き出そうと懸命に努力 しているからである。より速いプロセッサやメモリを製造するといったことを別に すると、処理速度を上げる最良の方法は、頻繁に使用する情報やデータのキャッシュ を維持管理することである。Linux では、キャッシュに関するいくつかのメモリ管理 機構が利用されている。
ハードウェアキャッシュやその他のキャッシュを使う場合の欠点は、手順を簡略化 するために、これまで以上の時間とメモリ空間を使ってそうしたキャッシュを維持し なければならないということであり、もしキャッシュが壊れると、システムがクラッ シュするということである。
4.3 Linux のページテーブル
図表(3.3) 3 つのレベルのページテーブル
Linux では、3 つのレベルのページテーブルの存在が前提になっている。アクセス される個々のページテーブルには、次の段階のページテーブルにおけるページ フレーム番号が含まれている。図表(3.3)では、仮想アドレスがいくつかのフィールド に分割されている様子が示されている。図中の仮想アドレスの個々のフィールドが 提供するのは、特定のページテーブルへのオフセットである。プロセッサは、 仮想アドレスを物理アドレスに変換するため、まず個々のレベルのフィールドの 内容を取得して、その内容を当該レベルのページテーブルを含む物理ページ上での オフセットへと変換し、それによって次のレベルのページテーブルのページフレーム 番号を読み取る。この処理を三度繰り返すと、その仮想アドレスを含んだ物理ページ のページフレーム番号が分かる。仮想アドレスの最後のフィールドは、バイト オフセット(byte offset)となっていて、それを使用して当該物理ページ内で必要な データを見つけ出す。
Linux を実行するプラットフォームが提供しなければならないのが、変換マクロ
である。これは、カーネルが特定のプロセスのためにページテーブルを走査すること
を可能にするものである。そうすることで、カーネルはページテーブルエントリの
フォーマットや、その仕組みを知る必要がなくなる。
4.4 ページの割り当てとページの解放システム内の物理メモリに対する需要は大きい。たとえば、イメージがメモリに ロードされるとき、オペレーティングシステムは、それに物理ページを割り当てる。 イメージが実行を終了し取り除かれたら、そのページは解放される。物理メモリは他 にも、ページテーブル自体のようなカーネル固有のデータ構造を保持する用途に使用 される。ページ割り当てと解放に使用されるメカニズムとデータ構造は、仮想メモリ サブシステムの効率を維持する上でおそらく最も重要なものである。
システム内のすべての物理ページは
count これは、そのページのユーザ数のカウンターである。ページが複数のプロセ スで共有されている時、このカウントは 1 より多くなる。 age このフィールドは、ページの 寿命(age)を記述するもので、そのページが破棄 やスワップの候補であるかを判断するのに使われる。 map_nr これは、mem_map_t が記述する物理ページのフレーム番号である。
図表(3.4)では、
ページの割り当て
Linux は、相棒アルゴリズム
(
Buddy algorithm)
(脚注 2)
を使用することで、ページブロックを効率的に割り当てたり解放したりしている。
割り当てアルゴリズムは、まず要求されたサイズのページブロックを探す。それは、
図表(3.4) free_area のデータ構造
たとえば、図表(3.4)では、2 つのページから成るブロックが要求された場合、
(ページフレーム番号 4 から始まっている) 4 つのページから成る最初のブロック
が、2 つのページから成るふたつのブロックに分割される。ページフレーム番号 4
から始まる最初のブロックは、割り当てられたページとして呼び出したプロセスに
戻され、ページフレーム番号 6 から始まる二番目のブロックは、
ページの解放
ページブロックの割り付けは、大きな空ページを小さく分割するので、
断片化したメモリ(framgment memory)を生じやすい。
ページブロックが解放されると、同じサイズの近接ブロックもしくは相棒(buddy) ブロックが空かどうかチェックされる。もしそうなら、新しく解放されたページ ブロックと結合して、一段階大きいサイズの新しい空ブロックを作成する。ふたつの ページブロックが結合されてより大きな空のページブロックが形成されるたびに、 ページ解放コードは、そのブロックをさらに大きなものにしようとする。このように して、空のページブロックは、メモリの使用方法として許される限り大きなブロックに なっていく。
たとえば、
図表(3.4)では、ページフレーム番号 1 が
解放されると、すでに解放されていたページフレーム番号 0 と結合される。そして、
2 つのページから成る空ブロックとして
4.5 メモリマッピングイメージが実行されるとき、その実行イメージの内容は、プロセスの仮想アドレス 空間に置かれなければならない。このことは、実行イメージで使用するためにリンク された共有ライブラリの場合でも同じである。実行ファイルは実際に物理 メモリに置かれるわけではなく、プロセスの仮想メモリにリンクされるだけである。 そして、実行中のアプリケーションからそのプログラムの一部が参照されると、実行 イメージ内のその部分のイメージがメモリの中に置かれる。あるイメージを、プロセ スの仮想アドレス空間にリンクさせるこの仕組みは、メモリマッピング (memory mapping)と呼ばれる。
図表3.5 仮想メモリのエリア
すべてのプロセス仮想メモリは、
実行イメージがプロセス仮想アドレスにマップされるとき、
4.6 デマンドページング実行イメージがいったんメモリにマップされてプロセス仮想メモリに入ると、
イメージの実行開始が可能となる。しかし、そのイメージの最初の部分だけしか物理
メモリに入っていないので、すぐに物理メモリ内にない仮想メモリ領域へとアクセス
がある。プロセスが、有効なページテーブルエントリを持たない仮想アドレスに
アクセスしたとき、プロセッサは Linux にページフォルトの発生を報告する。
Linux は、ページフォルトが起こったメモリ領域を示している
次に、Linux は、その仮想メモリ領域のアクセス権限に違反して起こったページ フォルトのタイプをチェックする。プロセスが、たとえば読み出ししか許されない領域 に書き込みをしようとした場合のように、無効な方法でメモリにアクセスしている 場合、そのプロセスにはメモリエラー(memory error)のシグナルも送られる。
Linux がページフォルトが正当なものと判断した場合、ページフォルトに対処しな
ければならない。
フォルトページのページテーブルエントリが無効だが空でない場合、そのページ フォルトは、現在スワップファイルに保存されているページのものである。Alpha AXP のページテーブルエントリの場合、有効ビットは設定されていないが PFN フィールドに 0 でない値が設定されている エントリがある。その場合、PFN フィールドには、 スワップのどこに(そしてどのスワップファイルに)当該ページが保存されているのか に関する情報が記されている。スワップファイル内のページを操作する方法は、 この章の後の部分で紹介される。
汎用的な Linux の nopege 操作ルーチンは、メモリにマップされた実行イメージに
対して使用されるものなので、その nopage 操作ルーチンは、ページキャッシュを
利用して、必要なイメージページを物理メモリに持ってくる。
方法はどうあれ、必要なページが物理メモリに置かれた場合は、 プロセスページテーブルはアップデートされる。それらのエントリをアップデート するためにはハードウェア固有の処理が必要になるかもしれない。特に、プロセッサ がアドレス操作バッファ(Translation Look-aside Buffer, TLB)を利用している場合は そうである。これでようやくページフォルトは処理されたので、フォルトは解除さ れ、プロセスは、仮想メモリアクセスでフォルトを起こした命令の時点から再 スタートされる。
4.7 Linux のページキャッシュ
図表3.6 Linux のページキャッシュ
Linux のページキャッシュの役割は、ディスク上のファイルへのアクセス速度を
上げることである。メモリにマップされたファイルはページ単位で読み出され、それら
のページはページキャッシュに保存される。図表(3.6)では、ページキャッシュが
Linux 内のファイルはそれぞれ VFS inode データ構造で識別される(詳細は、 「ファイルシステム」の章で述べる)。VFS inode は システム上ユニークであり、特定の単一のファイルに関する完全な識別子となる。 ページテーブルへのインデックスは、ファイルの VFS inode とそのファイルへの オフセットから導き出される。
メモリにマップされたファイルからページが読み出されるとき、たとえばデマンド
ページングでページがメモリに戻されるときなどには、ページはページキャッシュか
ら読み出される。
ページがキャッシュ内にある場合は、そのキャッシュ内のページを表す
要求がなくても、Linux の側でファイル内の次のページを読み出しておくことも 可能である。この単一ページの先読みは、もしプロセスがファイル内のページに連続 してアクセスしている場合は、そのプロセスのために次のページをメモリ内に待機さ せることを意味する。
イメージが読み出されて実行されていくと、ページキャッシュはだんだんと大きく なる。必要のなくなったページ、たとえばどのプロセスからもアクセスされなくなった イメージは、キャッシュから削除される。 メモリの使用量が増えると、物理ページが不足してくることがある。その場合、 Linux はページキャッシュのサイズを小さくする。
4.8 スワップアウトとページの破棄物理メモリが少なくなると、Linux のメモリ管理サブシステムは、物理ページを
解放するよう努力しなければならない。このタスクは、カーネルスワップデーモン
(kernel swap daemon)(
カーネルスワップデーモン(
システムの空ページの数が
充分な空ページが出来たら、スワップデーモンは、タイマーが切れるまで再び休憩
に入る。カーネルスワップデーモンがページを解放した理由が、システム内の空ページ
の数が
ページキャッシュとバッファキャッシュのサイズの縮小ページキャッシュとバッファキャッシュに保存されているページは、解放して
カーネルスワップデーモンは、これらのキャッシュを縮小しようとするたびに、
個々のページを調査する際は、そのページがページキャッシュかバッファキャッシュ
にキャッシュされているかどうか確認される。
注意すべきなのは、この時点では共有ページは破棄されないこと、および同時に両方の
キャッシュに入っているページは存在しないことである。
当該ページがどちらのキャッシュにも入っていない場合、
ページがバッファキャッシュにキャッシュされるのは(あるいは、バッファがページ
キャッシュにキャッシュされるのは)、バッファの割り付けと解放とをより効率的に
行うためである。メモリ縮小コードは調査が終わったページのバッファから、解放しよ
うとする。
この作業によって充分なページが解放されたら、カーネルスワップデーモンは、 次の定期的呼び出しまで休憩する。解放されたページはどのプロセスの仮想メモリ の一部にもなっていなかったので(それらはキャッシュされたページであったので)、 どのページテーブルもアップデートされる必要がない。キャッシュされたページが 充分に解放されない場合、スワップデーモンは共有ページのいくつかをスワップアウト しようとする。
System V 共有メモリページのスワップアウトSystem V 共有メモリとは、プロセス間通信のメカニズムであり、ふたつ以上の
プロセスがお互いに情報を交換するために仮想メモリを共有することを許す仕組み
である。この方法でどのようにプロセスがメモリを共有するかについては、
「プロセス間通信の仕組み」の章で詳細に
解説する。今のところ、System V 共有メモリのそれぞれのエリアは、
カーネルスワップデーモンは、System V 共有メモリページをスワップアウトする
時にもクロックアルゴリズムを使用する。それが実行される際はいつも、どの共有仮想
メモリエリアのどのページを最後にスワップアウトしたか、カーネルスワップデーモン
は覚えている。それを実現するために、スワップデーモンはふたつのインデックスを
使用する。ひとつは、
System V共有メモリの仮想ページに対する物理ページフレーム番号は、該当する仮想
メモリエリアを共有するすべてのプロセスのページテーブル内に含まれているので、
カーネルスワップデーモンはこれらすべてのページテーブルを書き換えて、該当ページ
はもはやメモリ内にはなく、スワップファイルに保存されているということを示さな
ければならない。共有ページはひとつずつスワップアウトされるので、カーネル
スワップデーモンは、個々の共有プロセスのページテーブル内のページテーブル
エントリを探す。(これは、個々の
共有プロセスのページテーブルが完全に書き換えられてページカウントがゼロに
なると、共有ページをスワップファイルに書き出すことが可能になる。その System
V 共有メモリエリアに対するページテーブルエントリのなかで、
スワップアウトされたか破棄されたページスワップデーモンはシステム内のプロセスを順番に調べて、スワップすべき有力
候補がいないかどうかを探す。
実行イメージの内容の多くはそのイメージのファイルからメモリ内に置かれている ので、その内容の再読み出しは簡単に実行できる。たとえば、あるイメージの実行命令 は、そのイメージによって修正されることはないので、それがスワップファイルに書き 込まれることは決してない。それらのページは単に破棄されるだけである。プロセス から再度参照される時は、実行イメージからメモリ内に戻せばいいからである。
スワップすべきプロセスが見つかったら、スワップデーモンはそのプロセスの仮想
メモリ領域を走査して共有されたりロック(lock)されたりしていないエリアを探す。
Linux
は、選択したプロセスのスワップ可能なすべてのページをスワップするわけではない。
むしろ、ごく少数のページだけを削除する。メモリ内でロックされている場合、ページ
はスワップも破棄もできない。
Linux のスワップアルゴリズムは、ページエイジング(page aging)を使っている。
ページの寿命が尽きたら(age=0)、スワップデーモンはさらにその処理を進める。
修正されているページ(dirty page)は、スワップアウトすることができる。Linux は、
PTE 内のアーキテクチャに固有のビットを使ってそれを区別する。
(
図表(3.2) 参照)
しかし、dirty page がすべてスワップファイルに書き出される必要はない。
あらゆるプロセスの仮想メモリ領域は、それ自身に必要なスワップ操作が指定されて
いるかもしれず(それは、
スワップアウトされたページのページテーブルエントリは、無効とマークされた
エントリによって置き換えられるが、そのエントリには、ページのスワップファイル
内の位置に関する情報が含まれている。その情報は、スワップファイル内のどこに
ページが保存されているかを表すオフセット値と、どのスワップファイルが使用され
たかを示す指示子から成る。
どのようなスワップメソッドが使用された場合でも、もとの物理ページは解放され、
スワップ可能なプロセスのページが、充分な数だけスワップアウトされるか 破棄された場合、スワップデーモンは再度スリープする。次に起きるときは、システ ム内の次のプロセスを対象として考慮する。この方法によって、スワップデーモンは システムがバランスを取り戻すまで、プロセスの物理ページを少しずつ解放してい く。この方法は、プロセス全体をスワップアウトするよりもずっと公平である。
4.9 スワップキャッシュページをスワップファイルに移す際、Linux は必要がなければページを書き 込まない。あるページがスワップファイルと物理メモリの両方に存在するときがある。 そのようなことが起こるのは、スワップされてメモリから削除されていたページが プロセスに再度アクセスされたことでメモリに戻った場合である。メモリにある ページが書き込みを受けていない限り、スワップファイルにあるページのコピーは 有効なままである。
Linux はそのようなページを監視するためにスワップキャッシュを使う。スワップ キャッシュはページテーブルエントリのリストであり、エントリはシステム上の物理 ページごとに存在する。これは、スワップアウトしたページのページテーブル エントリであり、そのページがどのスワップファイルに保存されているかということ と、そのスワップファイル内での位置とが記されているものである。スワップキャッ シュエントリがゼロでない場合、それは、そのページがスワップファイル内にあり、 しかもそれが変更されていないということを表している。ページの中味がその後で (書き込みをされて)変更された場合、そのエントリはスワップキャッシュから削除 される。
Linux が物理ページをスワップファイルにスワップアウトする必要がある場合、 スワップキャッシュをまず調べる。スワップキャッシュにそのページ用の有効な エントリがあるなら、そのページをスワップファイルに書き出す必要はない。 なぜなら、メモリ内のそのページは、スワップファイルから最後に読み出されて以来 変更されていないからである。
スワップキャッシュのエントリはスワップアウトされたページに関するページテー ブルのエントリである。それらは無効とマークされているが、どのスワップファイル のどこでそのページが見つかるかを Linux に知らせる情報を含んでいる。
4.10 スワップのページイン書き込みをされてスワップファイルに保存されたページが再度必要となることが
ある。たとえば、アプリケーションが仮想メモリのある領域に書き込みをしたいのだ
が、その内容が物理ページからスワップアウトされていた場合などである。物理メモリ
上にない仮想メモリのページにアクセスがあった場合、ページフォルトが起こる。
ページフォルトとは、プロセッサがオペレーティングシステムにシグナルを送って、
仮想アドレスを物理アドレスに変換できないことを伝えることである。この場合、
原因は、仮想メモリの該当ページの情報を記しているページテーブルのエントリが、
ページがスワップアウトされる際に無効とマークされるからである。プロセッサは
その仮想アドレスを物理アドレスに変換できないので、制御をオペレーティングシス
テムに手渡して、仮想アドレスがフォルトを起こしたこととそのフォルトの理由とを
伝える。この情報のフォーマットとプロセッサがオペレーティングシステムに制御を
渡す方法とは、プロセッサ固有のものである。
プロセッサ固有のページフォルト処理コードは、まず必要な
プロセッサ固有の動作を適切に処理し、フォルトが起きた仮想アドレスが有効な
仮想メモリ領域にあることが分かった場合、その後のページフォルト処理は、Linux
が稼働するどのプロセッサにも汎用的で適用可能なものとなる。
この時点で、Linux は、フォルトが起こった仮想アドレスを知っており、該当
ページがどこにスワップアウトされているかに関する情報を含むページテーブル
エントリを持っている。
ページフォルトを発生させたアクセスが書き込みアクセスでない場合、ページは スワップキャッシュにそのまま残され、そのページテーブルエントリも書き込み可能 とはマークされない。その後、そのページへの書き込みアクセスが発生すると、その 時点で別なページフォルトが生じ、該当するページ dirty とマークされ、そのエント リはスワップキャッシュから削除される。 そのページが書き込みされずに、再度スワップアウトされ る必要が生じた場合、そのページは既にスワップファイルに存在するので、Linux は ページをあらためてスワップファイルに書き込みせずに済ませることができる。
ページがスワップファイルから取ってこられるきっかけを作ったアクセスが書き込み 操作であった場合、そのページはスワップキャッシュから削除され、そのページテー ブルエントリは、dirty かつ書き込み可能であるとマークされる。
(脚注1)紛らわしいことに、この構造体は、ページ構造体とも呼ばれている。
次のページ 前のページ 目次へ |
[ |