メモリ管理と仮想記憶

共有資源としてのメモリ

OSの役割は資源の抽象化にある。メモリを単純に割り当ててしまうと
断片化が生じることになる。また、プロセスが暴走し、他のプロセスの
メモリ領域を書き換えてしまうことがないようにしなくてはならない。
望ましいメモリ管理では次の事柄が要求される。

• 断片化が起こりにくい
• メモリ保護の機能がある
• 物理メモリを越えるメモリを利用できる

メモリの抽象化

OSはメモリ空間を抽象化し、各プロセスがひとつのメモリ空間を独占しているかのような錯覚を得られるようにする。

仮想アドレスと仮想アドレス空間

プロセスが独占して使用することができるアドレス空間を仮想アドレス空間と呼ぶ。一般にC言語などのプログラム言語で「アドレス」と呼んでるのはこの仮想アドレスに当たる。同じアドレスであってもプロセスが異なれば全く別のメモリ領域を指すことになる。よってこれによってメモリ保護が実現できる。

仮想アドレスと物理アドレス

仮想アドレスから物理アドレスへと変換することをアドレス変換と呼ぶ。そのためのハードウエアとしてMMUが存在する。MMUには仮想アドレスと物理アドレスの対応を記したテーブルが存在する。
MMUの動作は次のとうりである。

• プロセスがメモリ参照しようとすると仮想アドレス空間識別子と仮想アドレスのペアがMMUに送られる。
• MMUでは仮想アドレスがページテーブルに存在するかどうかを調べる
• 存在すればその物理アドレスを出力する
• 存在しなければページフォールトの例外を出力する

ページテーブルの実現方法

ページテーブルはどのように実現されているのだろうか
アドレス空間上の連続したひとまとめの領域のことをページと呼ぶ。
仮想アドレス空間上のページを仮想ページ、物理アドレス空間上のページを物理ページと呼ぶ。ページの大きさは4キロバイト／8キロバイトであることが多い。ページの大きさが4キロバイトとした場合の仮想アドレスから物理アドレスへの変換は次の手順で行われる。

• 32bit Addressの上位20bitが仮想ページ番号
• 4キロバイトページがあるのでoffsetは12bit必要
• MMUは仮想ページ番号をキーとして仮想ページを参照し、offsetだけ進めて対応する物理アドレスを得られる。

TLB

いちいちMMUはページテーブルを参照していたのではメモリアクセスが
頻発し、性能低下を引き起こす。そのためにページテーブルにはTLBと呼ばれる特殊なハードウエアが搭載されており、過去の参照アドレスを保存しておけるようになっている。

多段ページテーブル

ページテーブルはメモリ上に置くにはまだ大きい。これを小さくする
ために多段ページテーブルが用いられる。例えばアドレスの上位10bit
で一段目のページエントリを参照する。そこに2段目のページテーブルのアドレスが入っており、次の10bitで2段目のページエントリを参照する。といった具合である。

断片化

ページの大きさを大きくするとページ内に未使用の領域が発生することになる。これを内部断片化と呼ぶ

ページの保護

例えばプログラム領域は実行可能、書き込み不可などプロセスの各領域について属性を設定できたほうが良い。ページテーブルに各仮想領域についてどの操作が許可されるかが記録されている。例えば、読み出しが許可されていないページに対して読み出しを要求した場合、MMUは次のように動作する。

• ページテーブルを参照し、不在であればページフォールト例外を発生させる。
• 不在でなければ要求された操作(読み込み)が許可されているかどうか確認する。
• 許可されてなければメモリ保護違反などの例外を発生させる。
• 許可されていれば仮想アドレスを物理アドレスに変換する。

仮想記憶

仮想記憶とはメモリ量という制約を取り除くための機構である。
これにより物理的に搭載されているメモリ量を越えたメモリをプロセスに提供できる。物理メモリに入りきらないメモリは二次記憶上のスワップ領域と呼ばれる部分に退避される。スワップ領域からページを読み出すことを「ページイン」書き出すことを「ページアウト」と呼ぶ。
仮想記憶の主な動作は次である。

• 物理メモリに入りきらない領域はスワップ領域に書き出し、マッピング不在としておく。
• メモリ参照を行ったときに参照されたページがマッピング不在でなければその物理メモリを参照する。
• マッピング不在であれば、仮想ページがスワップ領域にあるか確認する。なければセグメントエラーを出す。
• スワップ領域に存在すればそれを読み出す。

アドレス空間記述表

OSによって管理されるどの仮想ページがどこに書き出されているか
といった情報。ページフォールトのたびにOSが参照する。MMUとの違いに注意する。

ページ置換アルゴリズム

通常プロセスが起動した段階では全くページが割り当てられていない。
ページフォールトが発生してはじめて割り当てられる。これをデマンドページングと呼ぶ。ページインする際に物理ページに空きがない場合はページアウトを行う必要がある。このページアウトするページを選ぶアルゴリズムがページング置換アルゴリズムである。

LRU

代表的なページ置換アルゴリズムとしてLRUがある。これは最近もっとも長く使われていないページをページアウトするアルゴリズムである。
LRUを厳密に実現するためにはページを参照した時刻を記録し、比較する必要あるが、それではあまりに手間がかかる。近似的な実現法として参照bitと汚れbitを用いる方法がる。ページが参照された場合にこの参照bitをたて、書き込まれた場合に汚れbitを立てる。これによりOSは定期的にこれらのbitをクリアして、ページアクセスを行う際にはこれらのbitが立っていないページをページアウトすることで近似的にLRUが実現できる。