恐竜本8章です。今回は主記憶のメモリ配置の管理に関する話です。IPA試験でよく出てくるけど適当に解答を丸暗記してすっ飛ばしがちな話題となります。
基本的なハードウェアの性質
CPUが直接触れる記憶装置としてはレジスタとメインメモリが存在している。レジスタへのアクセスは1CPUサイクルででき高速なのに対し、メインメモリへのアクセスは何サイクルも必要としストールという待ち状態となる。メインメモリほど遅くはないがレジスタほどサイズが小さくもない中間的なメモリとしてキャッシュメモリが用いられる。
OSは多数のプロセスを動かさなければならないので、お互いの動作によってメモリが撹乱されないようにする必要がある。最もシンプルなメモリ保護の方法として、それぞれのプロセスが使って良いメモリ領域をbase registerとlimit registerで指定するというものがある。あるプロセスのメモリ領域の始まりのアドレスがbase registerに入り、メモリ領域のサイズがlimit registerに入る。これらのレジスタの値がおかしくなると当然システムが不安定となるので、base registerとlimit registerをいじる命令はカーネルモードでしか実行できない。プロセスがアクセスしているメモリ領域はCPUがハードウェア的にチェックしており、アクセス違反をするとOSに通知され、処理される。
プログラム内では関数呼び出しなどで、現在実行位置から関数が存在する物理アドレスまでのジャンプを行わなければならない。また、変数のポインタを扱うときは変数が格納されている物理アドレスの位置が必要となる。プログラム内のオブジェクトの物理アドレスを解決することをbindという。コンパイル時にそのプログラムが物理メモリのどこに置かれるかわかっている場合は、これらのアドレスを絶対値で埋め込むことができる(absolute codeを生成する)。物理アドレスがコンパイル時には分からないがプログラムがメモリにロードされるときにわかる場合は、コンパイラは再配置可能な形でプログラムにアドレスを埋め込む(relocatable codeを生成する)。また、プログラムが実行されるまでどのアドレスに何が置かれるかわからない場合、プログラムの場所が実行時に変わる場合もある。この場合bindは実行時まで行われない。ほとんどのOSは実行時までbindしない。
CPUが生成するアドレスを論理アドレス（仮想アドレス）という。これは実際の主記憶上の物理的なアドレスとは一致しない、0から始まる連続的なアドレスである。すなわち、つながった大きなバイト配列のようなものである。一方、実際の主記憶上のアドレスを物理アドレスという。論理アドレスと物理アドレスの変換を行うのがmemory-management unit(MMU)というハードウェアである。
ここまでの議論ではプログラムが全部メインメモリ上に読み込まれる前提だったが、必ずしもそれが成り立たない場合もある。プログラムが動的にロードされる場合は、プログラムの一部だけが読み込まれる。
また、ライブラリを実行時に動的にリンクすることもある。プログラムの動的ロードとの違いは、リンクが実行時に行われ、複数のプログラムで同じメモリ領域に置かれたライブラリコードを利用するという点である。
スワッピング
全プロセスをメモリ上に載せられないときは一時的にバッキングストアと呼ばれる二次的な記憶域にプロセスを追い出す。これをスワッピングという。プロセスの優先度付きスケジューリングと合わせて使われるとき、より優先度の高いプロセスによって低いプロセスがメモリから追い出されることをロールアウト、優先度の高いプロセスが終了して低いプロセスがメモリに復帰することをロールインという。
バッキングストアはアクセスが遅く、スワッピングが起こると非常にコンテキストスイッチに時間がかかる。また、プロセスがI/O待ちだと、I/Oの結果がメモリに読み込まれるため、スワップしてしまうと別プロセスが今や保持しているメモリ領域にスワップアウトしたプロセスのI/O結果が読み込まれることになる。対処法としては、I/O待ちのプロセスをスワップアウトしないか、I/O結果をOS所有のバッファに入れるかとなる。
連続的なメモリ割り当て
ページングの必要性を見るためメモリをプロセスごとに連続的に割り当てる場合を考える。シンプルな方法として、パーティションと呼ばれる固定長の区切りをメモリ上に入れて、各パーティションにプロセスを一つずつ入れるものがある。この方法はIBM OS/360で採用されていた。プロセスが終了すると占めていた領域を解放して別プロセスが使えるようになる。
可変パーティションの方法では、メモリ領域の分割サイズは可変で、どの領域がどんなサイズであるかOSがテーブルを作って管理する。メモリの空き領域をホールと呼ぶ。ホールが複数存在している状態でプロセスをメモリにロードする必要があるとする。このとき、どのホールを割り当てるか選択の余地がある。割り当て方としては、
- 最初に見つかった十分なサイズを持つホールに入れる(first-fit)
- 必要なサイズ以上を持ち、かつ最小のホールに入れる(best-fit)
- 最大のホールに入れる(worst-fit)
の3種類がある。シミュレーションによると、first-fitとbest-fitは検索時間やストレージ利用率に大きな差が出ないが、worst-fitは他2つより劣る事がわかっている。
どの割当方法をとるにしても、セグメンテーションという現象に悩まされることになる。セグメンテーションは、メモリが専有されたり解放されたりを繰り返すことで小さなホールがメモリ状で散在する状態になることである。ホールが小さすぎてなんのプロセスも入り込めないので、実質使用不可となる。プロセスとプロセスの間に空いた隙間をexternal fragmentationという。統計的にはN個のメモリブロックが割り当てられているとき、0.5N個相当のメモリがフラグメンテーションによって使えなくなる事が多い。これを50%ルールという。
また、割り当てるメモリサイズを厳密にプロセスが要求するサイズにすると、例えば18484バイト使ったプロセスのあと18482バイト使うプロセスが読み込まれたら、2バイトをわざわざ空き領域としてマークしておく必要がある。これを記憶するメモリ領域のほうが空き領域より多くなって無駄が多い。対応方法として、割り当てるメモリサイズを一定サイズのメモリブロックの倍数にすることが考えられる。これをやると、割り当てられたメモリブロックをプロセスが全部使い切らないことによるinternal fragmentationが起こる。
external fragmentationへの対処方法は、プロセスの位置を整理して歯抜けになったメモリを寄せ集めるコンパクションを行うことである。しかしこれはオーバーヘッドが大きい。
ページング
ページングは物理アドレスを必ずしも連続的にしないことでexternal fragmentationの問題を解決する。まず、論理メモリと物理メモリを一定サイズで区切る。論理メモリの1区切りをページ、物理メモリの1区切りをフレームという。論理メモリ上で区切られた区画にはインデックスが振られ、これをページ番号という。論理メモリ上のアドレスはページ番号と、そのページの中での相対的な位置であるページオフセットで指定できる。この各ページと物理メモリ上のフレームはページテーブルという表で紐付けられている。また、OSはどのフレームが割り当て済みなのかを管理するためフレームテーブルというデータも持っている。ページに対応するフレームの番号は必ずしも物理メモリ上で連続している必要は無い。これによって物理メモリ上の隙間はページテーブルで結びつければプロセスが利用することができ、external fragmentationが起こらなくなる。一方でフレームサイズが固定なのでinternal fragmentationは防げない。internal framgmentationを緩和するためにはページサイズとフレームサイズを小さくすればいいが、ページテーブルのサイズ増大を招き、オーバーヘッドが増える。
ページングはハードウェアサポートを受けることができる。ページング専用のレジスタを持つCPUもある。ページテーブルのサイズが大きいとレジスタに納めるのが不可能になるため、page-table base register(PTBR)というページテーブルへのポインタを入れるためのレジスタを用意することがある。この場合、ページテーブルと実際にアクセスしたい場所の2回メモリにアクセスすることになる。これによる速度低下を防ぐため、ページテーブルの一部を保持するキャッシュである、translation look-aside buffer(TLB)というハードウェアが存在する。このハードウェアにページ番号を問い合わせると登録されたエントリ全部を同時に確認し、キャッシュがヒットすればメインメモリ上のページテーブルにアクセスせずアドレスの解決ができる。キャッシュミスの場合はメインメモリに取りに行くことになる。TLBの内容は古いものから順にメモリに追い出す、least recently used方式で更新されていくが、特定データが追い出されないようにするwired downを使うこともできる。また、TLBではプロセスごとにアクセスできる領域を分離するためaddress-space identifiers(ASID)という付加的なデータを持たせることもある。これがない場合、コンテキストスイッチ時にTLBの中身をメモリに退避させたあと消す必要がある。TLBのヒット率を使ってメモリアクセス速度の期待値（実行メモリアクセス速度）が計算される。
プロセスがアクセスできないページテーブルのエントリを表すため、valid-invalidビットをページテーブルに付加する場合がある。invalidフラグがたったエントリにアクセスするとアクセス違反としてOSに通知される。この仕組はページに対応するフレームがメモリ上に存在しない場合に起こる1。
ページテーブルを使えば、複数のプロセスで同一の物理メモリを同時に参照することが可能となる。プログラムが再入可能であれば、つまり自分自身を書き換えなければ同じプログラムコードを複数のプロセスから参照でき、メモリを節約できる。
ページテーブルの構造
ページ数が非常に多くなると一個のページテーブルを配列として持っておくにはサイズが大きすぎる。そのような場合にはページテーブル自体を分割して物理メモリ上の隙間に差し込んでメモリを有効活用する必要がある。そのような方法を取るとページテーブルへのポインタを取りまとめるテーブルが必要となり、テーブルが階層構造をなす。論理アドレスの部分のうち、第一段階のテーブル上のインデックスを指定する部分をouter page、第二段階のテーブル上のインデックスを指定する部分をinner pageという。論理アドレスが64bitともなるとテーブル階層を増やさないとやはりテーブルサイズが大きくなりすぎる。UltraSPARCという64bit CPUは7階層のテーブルを持っていた。これだとメモリへのアクセス数が多すぎてパフォーマンス上厳しい。
ページ数が大きくなりすぎる場合、ハッシュテーブルを使用する。論理アドレスをハッシュ関数に通すと、テーブル上の位置が得られる。テーブルには連結リストの先頭ノードが格納されており、各ノードの値には論理アドレスと物理アドレスのペアが入っている。これは、ハッシュの衝突があっても良いようにするためである。この連結リストを頭から見ていくことで、所望の物理アドレスを得ることができる。また、これの亜種として、clustered page tablesというものがある。連結リストが保持するのは1個のページ・フレーム対応ではなく複数のページの対応となる。
別の実装として、逆引きページテーブルというものがある。この方式ではフレーム番号とそのフレームを所有するプロセスのIDが格納されている。テーブルはフレーム番号でソートされているのに、テーブルの参照はページ番号で行われるので、参照が遅い。この問題に対応するためハッシュテーブルを使用する。また、この方法だと共有メモリを実装するのが難しい。なぜなら、1個の物理アドレスに1個しか論理アドレスを対応させられないからである。これに対処するためには、共有メモリの物理アドレスに対応させる論理アドレスをどんなプロセスでも一意にする。
セグメンテーション
メモリは一個のバイト配列で、プログラム内の関数はその配列の特定範囲を占めていて、スタックはこのへんで、…などと意識することは普段はあまりない。これらの関数やらスタックといった構成要素をセグメントと呼び、そのセグメントに番号を振ってセグメントごとにメモリ領域を割り当てる方法をセグメンテーションという。セグメンテーションは、各セグメントに割り当てられたメモリの始まり(segment base)とメモリのサイズ(segment limit)を保持するセグメントテーブルを利用して行われる。Pentiumなどではページングとセグメンテーションを併用している。
コメント