恐竜本9章後半です。フリーなフレームの割当方法とスラッシングの話などに関して述べられています。
フレームの割当
空きフレームの割当は比較的にシンプルに考えることができる。すなわち、OSは空き領域のリストを保持しておき、プロセスがページフォルトしたとき空き領域のリストから適当な領域を選択してそこにページインする。空き領域が枯渇している場合にはページ置換アルゴリズムでvictimを選んでデータを読み込む。この方法にはいろいろなバリエーションがあり、例えば常に空きフレームを3つだけ持っておいて、ページフォルトが起きた場合にはそこから一つ選んで割り当てる。ページフォルトの読み込み処理が行われている間に、割当分を補充するために置換アルゴリズムを使ってvictimを選ぶようなパターンもある。
空きフレーム割当の方法は様々であるが、２つの制約を守らなければならない。1つ目は、割り当てるフレーム数は物理的に存在するフレーム数を超えられないこと、2つ目はプロセスに割り当てるフレーム数には下限が存在することである。第二の制約は、プロセスがメモリ上に置いておけるデータが減るとページフォルト回数が増大し、パフォーマンスが非常に低下してしまうことを避けるためのものである。フレーム数の下限はコンピュータのアーキテクチャで決定される。
制約を守ってもプロセスに割り当てるフレーム数を決める方法には依然として自由度が残る。その中でどのように割り当てるかは設計思想次第となる。equal allocationでは使用可能なフレームをプロセス数で割り、1プロセスあたりに割り当てるフレーム数を決める。proportional allocationでは、それぞれのプロセスが使用する仮想メモリのサイズで重み付けしてプロセスにメモリを割り当てる。いずれにしてもプロセス数が増えると1プロセスあたりのフレーム数は当然減少する。また、各プロセスの優先度を考慮しない議論になっていることに注意が必要である。
Global/Local replacement
フレームの割り当て方として重要な考え方が、global replacementとlocal replacementである。global replacementでは空きフレームが足りないときあるプロセスがページフォルトしたとすると、別プロセスを含めてページ置換アルゴリズムが走る。local replacementでは自プロセスのページを置換する。global replacementでは他のプロセスの実行状況によってあるプロセスのページフォルト率が変動し、自プロセスのページフォルト率を制御できない。一方で、local replacementではあるプロセスがあまり使っていないフレームを持っていても別プロセスに解放しない。この性質から、システム全体のスループットとしてはglobal replacementのほうが良くなり、より広く用いられている。
Non-Uniform Memory Access
複数のシステムボードとCPUからなるコンピュータではCPUのメモリへのアクセス速度が、CPUとメモリの物理的な位置関係で異なるnon-uniform memory access(NUMA)という現象が起こる。プロセスにフレームを割り当てる際には、プロセスが実行されるCPUと割り当てるメモリの位置関係を考慮しないとパフォーマンス低下につながる。これに対し、Solarisではlgroupというグルーピングを行い、CPUとそれに近接したメモリを管理している。Solarisではlgroup内で全てのスレッドを実行しメモリも割り当てるように試みることでNUMAの問題に対処している。
スラッシング
プロセスが増えてくると、実行状態となったとき「必要とする」ページがページ置換アルゴリズムによってメモリ上に存在せず、ページフォルトが起こる確率が増大する。プロセスの実行順が回ってきたときページフォルトが非常に大量に発生し、ページフォルト処理にほとんどの時間を費やす状態となることをスラッシングという。ページフォルト処理の待ち時間が多くなり、CPU使用率が低下するので、賢くないOSはプロセス数に余裕があると判断し、プロセスを増やそうとする。
スラッシングへの対応としては、local replacementを採用するというものが考えられる。別プロセスからフレームを奪わないのでシステム全体に及ぶスラッシングが緩和される。しかし、local replacementを使ってもあるプロセスが恒常的にメモリ不足となっているとき、そのプロセス単体ではスラッシングが起きており、ページングデバイスへのキューには常にそのプロセスが並んでいることになる。その影響によって結局スラッシングしていないプロセスも実行アクセス速度が低下することになる。
スラッシングの防止にはlocality modelを利用したアルゴリズムが有効である。以下でlocality modelに関して述べる。
Working-Set Model
プロセスは特定メモリ領域にアクセスする傾向があり、その性質をlocalityと呼ぶ。Localityを測定する方法として、working setというものがある。working setは参照されたページ番号を時系列順に記録する。次に、過去Δ（単位は秒、回など）以内のユニークなページ番号数を計算する。同じメモリ領域にばかりアクセスしているとユニークなページ番号は少なくなるので、実効的に必要なメモリとしては小さくなる。このユニークな番号がworking setである。working setを全プロセスで合計したとき、使用可能なフレーム数を超えたらスラッシングが起こっているとわかる。この方法を使えば、スラッシングが起こっているとき、OSは何らかのプロセスを停止し、スワップアウトする。
working set modelの欠点としてはworking setの移動窓を維持するコストである。メモリを参照するたびに移動窓を動かすのはそれなりにオーバーヘッドがある。代わりとして、一定回数メモリを参照したら、reference bitをチェックし、そのタイミングで統計を取るという方法がある。「一定回数」を小さくするほど検出の感度は上がるがオーバーヘッドは大きい。
ページフォルト頻度
working setを観測するのではなく、ページフォルト頻度を観測するアプローチもある。スラッシングはページフォルト頻度が非常に高くなる現象であるから、ページフォルト率を一定に保つようにフレームを割り当てる。
メモリマップトファイル
ファイル上にアドレス空間を割り当て、物理メモリではなくファイル上のアドレス空間を仮想メモリから参照できるようにする技術をメモリマップトファイルと呼ぶ。マッピングが行われたあとは、プログラムから初めて参照が行われるときに通常のページフォルト同様ファイルからの読み込みが起こり、実メモリにコピーされる。なお、書き込み時はすぐにファイルに反映されるとは限らない。
メモリマップトファイルは複数プロセスから同時に同一ファイルに対して使うことができる。これを共有メモリのように使うことができる。また、copy-on-writeが実装され、プロセスが書き込みを行ったときに初めてデータがコピーされるようにすることもある。
カーネルのメモリ割り当て
カーネルのメモリ割当ではページング機構を使っていない。これは、
- カーネルが使うデータサイズがページサイズよりはるかに小さいことがあり、無駄をなくすため
- ハードウェアとのやり取りで、受け渡すデータのメモリが連続していることが必要な場合があるため
である。代わりにバディーシステムという方法とスラブアロケーションという方法のいずれかが使用される。
バディーシステムではメモリを2の累乗単位で管理する。メモリ割り当て要求があったら、要求量より大きい最小の2の累乗を計算し、割当メモリ量とする。次に、空き領域を半分ずつ分割していき、メモリを割り当てる。メモリを解放するときは隣接するメモリ領域と結合して2の累乗のサイズを維持する。この方法は高速だが要求量より大きなメモリを割り当て、フラグメンテーションの問題が存在する。
スラブアロケーションでは、キャッシュと呼ばれる静的領域を確保しておく。スラブは1個以上の連続した物理メモリ領域からなり、キャッシュは複数のスラブから構成される。キャッシュにはカーネルが作成するオブジェクトが格納されている。各オブジェクトはusedとfreeの2種類の状態を持っている。カーネルがメモリを要求するときはキャッシュからfreeなオブジェクトが割り当てられ、当該オブジェクトをused状態にする。解放する場合はその逆となる。スラブはfull,empty,partialの3状態を持っており、オブジェクトが割り当たるときはまずpartialから割り当たる。この方法では必要とするメモリ領域がちょうど割当たるのでフラグメンテーションが起こらない。また、高速である。LinuxやSolarisではこちらを採用している。
その他考慮事項
プロセスが最初に実行されるときに必要なページが全部ディスク上にあると大量のページフォルトが発生し時間がかかる。そのため、prepagingと呼ばれる、ある程度のページを最初に読み込む機能が実装されることがある。プロセスが停止されてスワップアウトされる場合、working setを保存しておいて再開時はworking setのページを読み込むことでprepagingを行う。prepagingは使わないページを読み込むおそれがあり、その場合無駄なページを読み込むオーバーヘッドにより、単純にページフォルトでページを読み込むより遅くなる。
ページサイズは新規のコンピュータアーキテクチャが出てきたときに検討すべき事項となる。ページサイズが小さいとinternal fragmentationを防げ、1ページあたりのページイン・アウトの時間も短縮できる。またlocalityの現れ方がより細かいメモリ単位となるのでメモリ割り当て量が適正値に近づく。しかしながら、ページテーブルのサイズは増大してしまう。
TLBのヒット率も重要なファクターである。TLBのアクセス速度は大きいのでできる限りTLBにヒットするようページサイズを設計したい。似たようなメトリックとしてはTLB reachがある。これは、TLBに存在するページテーブルのエントリーからアクセスできるメモリ範囲を表す。計算は単純にTLBのエントリー数×ページサイズで求められる。TLB reachはTLBに格納できるエントリー数を増やすか、ページサイズを増やすかすると増大できる。前者はハードウェア価格の問題が、後者はフラグメンテーションの問題が伴う。
逆ページテーブルを使う場合、ページフォルト判定をどうやって行うのかという問題がある。その場合結局別にページテーブルを用意することとなる。ただし、逆ページテーブルの良さ（ページ管理情報のメモリ領域節約）がなくなるかどうかは別の話である。例えば通常のページテーブルが必要になるのはプログラムがページフォルトしたときだけなので、すぐ通常のページテーブルを用意できる必要はない。そのため、通常のページテーブル自体をページアウトさせておくという戦略が考えられる。
プログラムの構造もページングを考慮して最適化することができる。例えば、ページサイズが128WORDのコンピュータで128×128のshort型二次元配列にくまなくループでアクセスすることを考える。列を固定して行を回すプログラムだと、別の行にアクセスするたびに別ページにアクセスすることになる。メモリが128WORDしか割当たっていないなら128×128回ページフォルトが起こる。一方行を固定して列を回すプログラムなら128回のページフォルトで済む。データ構造としても、ハッシュテーブルはlocalityが低いがstackはlocalityが高いので、ページフォルト頻度が低くなる。当然プログラムの動作速度はページフォルトだけに影響されるのではないことには注意が必要である。
コンパイラやローダーもページングに影響を及ぼす。お互いに頻繁に呼び合うルーチンを同じページに配置したり、ルーチンがページ境界をまたがないようにすることでlocalityを高められる。また、コードとデータを分け、reentrantなコードを生成することも重要である。プログラミング言語の選択も重要で、CやC++ではポインタをよく使うので、localityが低下する傾向がある。また、オブジェクト指向言語もlocalityが低下しやすいという研究がある。
I/Oインターロック
global replacementを採用しているとき、I/Oのバッファとして指定したページがページアウトされてしまい、別プロセスによって使用されることが考えられる。I/Oは別のプロセッサが行っているのでページングの都合を加味せず、I/Oが終わったら読込結果を書き込んで中身を破壊してしまう。対応としてはシステムメモリをI/Oのバッファとして使うという方法がある。これだとまずシステムメモリにデータが読み込まれたあとでユーザーメモリにコピーされなければならないので受け入れがたいオーバーヘッドを生む。別の方法としては、バッファに指定されたページはlock bitを立てて保護するという方法もある。
lock bitは他にも低優先度のプロセスが読み込んだページを保護する目的でも使われる。低優先度のプロセスは実行順が回ってくるのが遅く、次に回ってくる間に全ページがページアウトされてしまう可能性がある。OS設計者がページが1回も参照されないままページアウトするのは望ましくないと考えた場合はlock bitで保護するよう実装される。
コメント