恐竜本9章の前半です。今回は仮想メモリの管理に関する話です。IPA試験の午前に出るやつですね1。
背景
OSの大きな役割の一つは複数のプログラムを同時に動かすことであるが、プログラムをすべてメモリに読み込んだり、静的に確保された配列を真面目に全部確保すると物理メモリに乗り切れない事がある。プログラム全体を読み込んだところで全部のルーチンを使うことはどうせないのだから2、部分的に必要な部分だけ読み込んでおくほうが同時に動かせるプログラムを増やせて嬉しい。仮想メモリはプログラムが使うメモリの一部を実際のメインメモリに乗せ、残りをbacking storeにおいておくことで、これを実現する。
Demand paging
プログラムが使うメモリ空間をページに分け、実メモリをフレームに分ける。実際にプログラムがあるページを参照するまでディスク上からデータを読み込まない（スワップインしない）ような仕組みをdemand pagingと呼び、それを行うものをlazy swapperと呼ぶ。ただし、プロセス全体がメモリとディスクを行き来するわけではないのでもはやswapperというのは適切ではなく、pagerと言うのがより名前として適切である。
demand pagingの実装には、ページテーブルのvalid-invalidフラグを使う。8章ではvalid-invalidフラグはプロセスがそのページへのアクセス権を持つか持たないかを表していたが、「そのページがメインメモリ上に存在するか否か」という意味を追加で持たせる。プロセスがinvalidなページにアクセスするとハードウェアが検知し、割り込みが発生し、OSに通知される。これはページフォルトと呼ばれる。アクセス権があるページの場合はbacking storeからページを空いているフレームに読み込み、ページテーブルを更新する（ページイン）。その後プロセスの実行を続行する。
極端にdemand pagingを行うと、プロセス開始時にはページを一つも読み込まず、全てのデータをページフォルトで読み込ませることもできる。これをpure demand pagingという。
プログラムが毎回メモリにアクセスするたびにページフォルトして実行が遅くなることが最悪ケースとして考えられるが、そのようなケースはあまり起こらない。というのは、多くのプログラムは参照の局所性という性質を持っており、同じページばかりを参照することが多いからである。
仮想メモリを実装する際に起こる問題として、ページフォルト後の再開がある。ある命令でページフォルトが起きたら、シンプルな場合はもとの位置から命令をもう一回実行すればよい。しかし、その命令があるメモリブロックを参照し、オーバーラップするメモリブロックにデータを書き込む場合に問題が起こる。途中までページフォルトなしで書き込んでいけたが、あるアドレスでページフォルトが起きた場合を考える。再度同じ命令を頭から実行すると、ページフォルト前とは状態が変わってしまっている。これへの対処として、一つは命令開始時に、書き込み元ブロックと書き込み先ブロックの先頭位置と末尾位置にアクセスするというものが考えられる。もしページフォルトが起こりうるなら何も書き込む前にページフォルトが起こるから、ページフォルト後命令を再開しても問題ない。もう一つの対処は、レジスタに書き込み先位置の値をバックアップしておいてページフォルトが起きたらバックアップした値を使うという方法もある。
Demand pagingの性能
Demand pagingの性能解析には実効アクセス速度を使う。具体的には以下のように解析する。普通のメモリアクセス時間は200 ns、ページフォルト時の処理時間は8 ms(ディスクへの信号レイテンシ3 ms、ヘッドのシーク5 ms、データ転送0.05 ms)程度なので、実効アクセス速度が通常のメモリアクセス速度の10%ダウンに抑えられるためには、ページフォルト確率は0.0000025未満とならなければならない。
Copy-on-Write
多くのOSでプロセスをフォークするときにはページテーブルはシンプルにコピーされる。こうすることでメモリコピーの時間を省くことができる。この場合子プロセスと親プロセスは最初は同じメモリを参照していることになる。子か親がページに書き込みを行ったタイミングでページがコピーされて、書き込み前のページを参照するプロセスと、書き込み後のページを参照するプロセスとに分かれる。この仕組をcopy-on-writeという。copy-on-writeを使う際には、空きページの位置を把握することが重要である。OSは空きページの場所を把握しており、プールとして持っている。copy-on-writeが起きたときやスタックやヒープが伸びるときにこのプールを使う。ページを割り当てる直前に中身が0で埋められ、前の中身が消去される。
fork()の亜種として、vfork()というものもある。これはcopy-on-demandをせずに子プロセスを作り出し、子プロセスが動いている間親は中断する関数である。そのため、子プロセスがページの中身を書き換えると親に影響が波及する。ページのコピーが一切生じないのでオーバーヘッドが少なく、UNIXのシェルで使われたりしている3。
ページ置換アルゴリズム
Demand-pagingを使ってプロセスを全部メモリに乗せなければ、プロセス全体を乗せていた頃には不可能だった個数のプロセスを同時に走らせる事ができる。この状況はメモリをover-allocatingしていると言われる。しかし、over-allocatingしている状況でプロセスが突然メモリに乗っていないデータを参照することがある。この場合、どこかのページをページアウトしてメインメモリに空きを作らないとプロセスの動作が不可能となる。ページフォルトのペナルティは大きいのでどういうページを追い出すかを考えるのが重要となる。
追い出すページが決まったとしたらあとの動作はシンプルである。まず、追い出されるページのvalid-invalidフラグをinvalidとし、メモリ上にデータが無いことを記録する。次に物理メモリからデータを読み込んでbacking storeに送る。最後に読み込みたいデータを今空いた物理メモリの領域に読み込んで、ページテーブルを更新する。
上記動作では2回ディスクへのアクセスが発生してオーバーヘッドが大きく、更に改良された方法として、modify bitを使う方法がある。最後にディスクからメインメモリにデータが読み込まれてから中身が変更されていない場合、メインメモリからデータを追い出すときにはわざわざディスクにコピーしなくても既に同じデータがディスクに存在している。modify bitはフレームの中身に書き込みが行われたかどうかを表すフラグである。これを使えば、modify bitがfalseのときディスクアクセスを半減できる。
ページ置換アルゴリズムの良し悪しを次に考える。ページ置換アルゴリズムの良し悪しの解析ではフレーム数（∝メインメモリのサイズ）、参照先ページのインデックスのシーケンス（reference string）を仮定して何回ページフォルトが起こるかを考える。良いアルゴリズムはページフォルト回数が少なくなる。
FIFOページ置き換え
一番シンプルなページ置換アルゴリズムはFIFO方式である。この方式では新規にメモリを空けなければならないとき最も古くにページインしたページをページアウトする。この方式はあまり性能が良くない。また、この方式を使うと、同じreference stringでも、メモリを拡張（フレーム数を増やす）するとページフォルトが増えて逆に性能が落ちるようなことがある。この現象はBelady’s anomalyと呼ばれる。
最適ページ置換
reference string全体を予め知っているとき、つまり将来のメモリアクセスパターンを全部知っている場合はページフォルト回数が最小となる最適なページ置換アルゴリズムが存在する。この方法では、ある時刻に置き換えるページは、次の参照までの時間が最も長いページにする。当然今後のメモリアクセスパターンを把握することはできないので、このアルゴリズムは別のページ置換アルゴリズムの性能を比較するときに使われる。
LRUページ置換
最終使用時刻が最も古いページを置き換えるアルゴリズムをLRU(least recently used)アルゴリズムという。最近アクセスしていないページは今後も長期間アクセスしないという仮定が成立てば最適ページ置換の近似となる。このアルゴリズムの問題点は、実装が難しいということである。ちゃんと実装するなら2種類の方法が考えられる。
- カウンター ページ参照ごとにあるカウンター変数をインクリメントし、各ページにカウンターを紐づけておく。最後の参照が最も古いページを見つけるのに最悪のケースではページテーブル全体の走査が必要となる。
- スタック 要素の抜き差しが自由にでき、ランダムアクセスができるようなスタックを実装し、あるページが参照されたらそのページをスタックから抜いて先頭に持っていく。スタックの底にあるページは常に最も古いページとなる。このようなスタックは単なる配列で実装すると、要素の抜き差しに要素数に比例した時間がかかるので双方向連結リストで実装することになる。そのため、ページテーブルをソフトウェア的に実装する場合にしか使えない。
このアルゴリズムではBelady’s anomalyが生じない。
ページ置換アルゴリズムをまともなスピードで動かすためにはハードウェアサポートが必要であるが、LRUを完全にサポートするハードウェアは殆どない。近似的にLRUを行うため、reference bitという仕組みを提供するハードは存在し、以下にそれを使った近似LRUの方法を述べる。
Additional-Reference-Bitsアルゴリズム
reference bitはページ参照時にハードウェアによってtrueが設定される。このアルゴリズムではreference bitの履歴を記録しておいてLRUを実現しようとする。まず、OSは1 byteの変数をページテーブルのエントリー全部に対して用意する。次に、プロセスを実行する。実行の前にOSはタイマーを設定してプロセスを回しているので、定期的にOSがプロセッサを握る。このとき、すべてのページテーブルのエントリーについて、reference bit記録変数を右に1bitシフトしたあと、先頭1bitに現在のreference bitを記録する。記録用変数を1つの値としてみたとき、最も小さい値を取っているエントリーが、最後にアクセスされた時刻が最も古いエントリーとなる。
履歴が8bit分しか記録されないので同じ値を持つページが複数出てくる。この場合、ページフォルトが起きたら同じ値を取っているページを全部ページアウトするか、同じ値を取っているページのなかでFIFO方式でページアウトするページを決めるかする。
履歴記録用変数は1byteである必要は無い。何bitで実装してもよく、極端な話0 bitにすることもできる。これは、履歴を記録せず、現在のreference bitのみで置換されるページを決めることを意味する。このようなアルゴリズムをSecond-Chanceアルゴリズムという。
Second-Chanceアルゴリズム
Second-Chanceアルゴリズムでは、ページを置き換えるときにreference bitを見る。reference bitが立っているページは一旦reference bitをクリアされ、次のエントリーを確認する。reference bitが立っていないページがあれば、それをページアウトする。もしすべてのエントリーのreference bitが立っている場合、ページテーブルの先頭に戻り、先頭のページをページアウトする。すなわち、すべてのページでreference bitが立っている場合の動作はFIFOと一致する。
Second-Chanceアルゴリズムの改良版として、modified bitも一緒に見るという方法もある。modified bitが立っていると、そのページを置き換えるときにはbacking storeに退避しなければならないので、できれば置き換えたくない。reference bitとmodified bitが両方falseであるものが一番置き換えに適しており、両方trueであるものが一番置き換えたくないページである。ページテーブルを走査して最も置き換えやすいページを置き換えるのが改良版second-chanceアルゴリズムである。
カウンターを使った置換アルゴリズム
- LFU(least frequently used)アルゴリズム 各ページに参照数カウンターをもたせ、一番参照数が低いページを置き換える。この場合、プロセス起動直後だけ頻繁に参照されるページがいつまでも置換対象にならない問題が生じる。これに対処するにはカウンターを定期的に右に1bitシフトすることで、時間的に値を減らしていくことが考えられる。
- MFU(most frequently used)アルゴリズム 参照数カウンターが一番大きいページを置き換える。参照数が小さいページはページインしたばかりであるので追い出すのには適さないという仮定を置いている。
これらの方法は結局あまり使われていない。
ページバッファリングアルゴリズム
予めフリーなフレームをプーリングしておくことで、ページフォルトへの応答速度を上げることができる。別の機会にvictimが書き出されたらフリーなフレームのプールに補充される。また、この方法の亜種としてmodified bitが立っているページのリストを持っておき、定期的にbacking storeに書き出しておく方法も取られる。
また、解放されたフレームにもともと何が入っていたかを把握しておいて、再度同じ内容を読み込もうとしたときそのフレームを割り当てる方法もある。こうすればI/Oをせずに済む。
アプリケーションによって適したページ置換アルゴリズムは異なる
データベースアプリケーションは自身がどうやってメモリアクセスするか、I/Oを行うか厳格に管理しているので、OSが提供する汎用のページバッファリングの他に自前のバッファリングをしていることがある。この場合OSのバッファリングも合わせて2倍のメモリを食うことになる。
別のケースでは、データウェアハウスはシーケンシャルなディスクアクセスを頻繁に行うことがある。この場合読み込み順でいうと古いページのほうが新しいページより頻繁にアクセスされることになる。この場合はMFUのほうがLRUより効率的になる。
このような場合に対処するため、ファイルシステム関係のサービスを経由せずディスクにアクセスできるraw diskという仕組みを用意しているOSもある。
- しっかり理解するより問題と答えを暗記するほうが時間効率が良いという…
- 「例としてアメリカの予算のバランスを取るルーチンは何年も使われていない」、という冗談が突然書かれていて一瞬戸惑いました
- 昔はforkがcopy-on-demandしていなかったのにfork後すぐexecするプログラムが多くて無駄が多かったのでvforkができたようです。forkがcopy-on-demandする今となっては使うべきではないみたいですね。
コメント