3日目の今日は，仮想記憶です。
まだメインメモリが高価だった頃，プログラムを分割してハードディスクに置いておき，実際に動かすプログラムだけメモリに読み込むようにして，少ないメモリでも大きなプログラムを動かす工夫をしていました。
キャッシュと同じで，プログラムには局所性がありますから，実際に動いていないプログラムを置いておくために高価なメモリを用意するのは不経済ですから，これを自動的に行ってくれる仕組みを考えました。
これが仮想記憶です。
仮想記憶を使うと，実際に用意されているメモリは小さくても，使っていないメモリのデータはハードディスクに待避しておき，必要に応じてハードディスクから読み出してメモリの中身を自動的に入れ替えてくれます。プログラムを書く人はメモリのサイズを気にしなくてもよくなります。
必要なのは，ハードディスクから読み出したメモリのデータが持つアドレスに，実際に存在しているメモリのアドレスを変換してあげる仕組みです。
マルチタスクの場合にはこの機能はとても重要で，複数のプログラムを実行させるとき，同じアドレスには同時にプログラムを置くことが出来ませんから，ずらさないといけなくなりますけども，それをプログラムを書く人がいちいち考えていたらきりがありません。
そこで，アドレスは常にゼロから始まるものと考えてプログラムを作り，実体の存在するアドレスに変換する仕組みを使って，CPUに実行をさせるようにします。それぞれのタスクは，自分が使っているメモリを他のプログラムが使うとは思っていませんから，他のプログラムが存在する実アドレスをアクセス出来ないように，メモリの保護を行うことも必要です。
実際に存在するメモリのアドレスを物理アドレス，CPUから見えているアドレスを仮想アドレスといいます。CPUから見えているアドレス，つまりプログラムを書く人にとっての先頭アドレスは常にゼロです。
しかし，実際にプログラムが置かれているアドレスはゼロではなく，別のどこかです。毎回その場所は変わるだろうし，もしかしたらメモリにさえ存在せずハードディスクに追い出されているかも知れません。
この仕組みは，普段我々はほとんど意識しませんが，少ないメモリを有効に利用するため，またマルチタスクを利用するためには必須であり，非常に大切な仕組みなのです。
----
問題:コンピュータの仮想記憶における次の説明のうち，最も不適切なものを選べ。
(1)仮想記憶方式とは，実アドレス空間よりも大きな仮想アドレス空間を作る方法である。
(2)仮想記憶方式を用いると，実装されている実記憶容量を気にせずに大きなプログラムを処理させることが出来る。
(3)仮想記憶方式を使えば，メインメモリの容量を小さくしてもCPUの性能の低下を防ぐ事が出来る。
(4)仮想記憶のページングアルゴリズムであるLRU方式は，プログラムの局所性が高いときはページイン，ページアウトを減らすことが出来る。
(5)マルチタスクのOSでは，通常，仮想空間を複数持った多重仮想アドレス空間方式を実装している。
----
回答:
(1)はその通りで，実アドレスよりも大きな仮想アドレス空間を作ることが可能な技術。よって正しい。
(2)は実際に搭載されている実メモリよりも大きなアドレス空間をプログラムに使うことができるので，容量という点では気にしないでよい。よって正しい。
(3)メインメモリの容量を小さくすることで，OSはハードディスクとのページの入れ替えを頻繁に行う必要が生じ，大きく処理速度の低下を招いてしまう。よって正しくない。
(4)LRU方式はアクセスの履歴を用いて，頻度の少ないものからページアウトさせる方式なので，プログラムの局所性が高い場合にはアクセス頻度も上がるため，ページイン，ページアウトを減らすことが出来る。よって正しい。
(5)マルチタスクOSでは，それぞれのタスクが固有の仮想アドレスで動作している。これを多重仮想アドレス空間方式という。よって正しい。
ゆえに，正解は(3)となる。
----
さて，仮想記憶を実現するには，ハードディスクとメモリとの入れ替えを行う最小単位を決めて，これで入れ替えていく必要があります。プログラムやデータには局所性がありますので，あまり小さくしても意味がありませんし入れ替えばかりが発生してしまいますし，大きすぎると入れ替えは発生しにくくなりますが，そもそも入れ替えにくくなってしまいますので，仮想記憶のうまみが生かせません。
また，入れ替える単位は機能や制限で分類を作らず，すべてが同一のものであると自由度が高いです。そこで現在は数kbyte単位で物理メモリを分割してこれをページと名付け，ページ単位でハードディスクとの入れ替えを行うような仕組みが主流となっています。この方式を，ページング方式といいます。
現在主流のx86でもページング方式の仮想記憶がサポートされていますが，ページの大きさは4kByteです。4kbyteということは12ビットですので，全部で32ビットあるアドレスのうち下位の12ビットはページ内のアドレスを示し，上位の20ビットはページの通し番号を示すことになります。20ビットで表現出来るページ数は1Mページですので，1ページあたり4kByteということは，トータルで4Gbyteですね。まあ，32ビットのアドレスなのですから，当たり前のことです。
ところで，仮想記憶というのは，ちょっと見方を変えるとキャッシュメモリとそっくりです。キャッシュメモリとメインメモリの関係は，そのままメインメモリとハードディスクの関係に相当します。
先に言葉の話になりますが，キャッシュのラインに取り込まれるデータをブロックといいました。ページング方式の仮想記憶ではこれはページに相当します。キャッシュメモリに一度に取り込むデータの大きさをブロックサイズといいますが，仮想記憶ではこれをページサイズといいます。
また，キャッシュにデータが入っていないことをミスといいましたが，仮想記憶ではこれをページフォールトといいます。そして，キャッシュにおけるタグは，仮想記憶では仮想ページ番号というのです。
ということは，仮想アドレスを物理アドレスに変換する仕組みは，キャッシュメモリのそれとほとんど同じになるということです。
では，具体的な仕組みを見ていきましょう。
まず最初は，ページテーブルという仕組みです。
x86を例に取ると，仮想アドレスの上位の20ビットはページ番号といいます。また，下位12ビットはページ内のアドレスで，これをページ内オフセットといいます。
キャッシュメモリと同じように参照するアドレスのページを総当たりで比較してもいいのですが，現実的にページ数は100万個を超えますので，これを全て比較していては大変です。だからといってダイレクトマップや2ウェイセットアソシアティブなどでは有限の物理メモリを生かし切れないばかりか，ハードディスクとのスワップが多発して現実的な速度で動いてくれません。
そこで，仕組みとしてはキャッシュにおけるフルアソシアティブ方式と同じにして，どの物理アドレスにも仮想アドレスを割り当てられるようにした上で，比較を行わずに済むようアドレスの変換表を作って，これを参照するようにします。また，メモリの内容が書き換わった場合に，いちいちハードディスクの内容を更新していては時間がかかって仕方がありませんので，キャッシュにおけるライトバック方式を用いて，メモリからハードディスクに追い出されるときに内容を更新します。
この変換表と，ページ変換表，あるいはページ変換テーブルといいます。
ページ変換テーブルは，ページ番号の順番にずらーっと列んでいて，そのページ番号が今どの物理アドレスに格納されているかを記録してあります。そして仮想アドレスの上位20ビットをインデックスとしてこの表を参照し，書かれている値を読み出します。これが物理アドレスになるわけです。
この時読み出される項目をページ変換テーブルエントリ，略してPTEといいます。
ただし，重要な事があります。仮想アドレスは，基本的にタスクごとに固有の値を持っています。先程書いたように，ソフト屋さんは自分のプログラムは全部ゼロ番地から書かれていると考えているわけで，3つタスクが走っていたら，それぞれのタスクは固有の仮想アドレス空間で動作しています。
ということは，3つのタスクで同じ仮想アドレスを持つことはごく当たり前のことです。3つのタスクが同じ仮想アドレスをもち，その仮想アドレスでページ変換テーブルを参照しても，同じ物理アドレスしか手に入りません。これでは何のために変換しているのか分かりません。
そこで，タスクごとにページ変換テーブルのベースアドレス（ページ変換テーブルの物理アドレスの先頭です）を変えてやります。タスク1のベースアドレスは0x4000から，タスク2が0x10000となっていると，それぞれここをゼロページ目にして，仮想アドレスの上位20ビットが示すページ番号を参照していくのです。
さて，PTEはそれぞれに対応する物理アドレスが書かれているわけですから，1つあたり32ビットの大きさが必要になりますね。実際は下位12ビットのオフセットは仮想アドレスと物理アドレスで共通ですから記録する必要はないのですが，キャッシュのタグと同じで他の情報も書いておきたいので，やはり32ビットくらいは必要になります。
思い出して頂きたいのですが，ページの数は100万個を超えますので，ページ変換テーブルだけで4MByte，下手をすると8Myteにもなってしまいます。従ってCPUに持たせるわけにはいかず，メインメモリに置かれることになります。
CPUには，メインメモリのどこにページ変換テーブルが置かれているかを書いておくレジスタが用意されているので，任意のアドレスに置くことが可能です。
さて，先程ページ変換テーブルが少なくとも4MByteにもなってしまうと書きました。今は数GByteのメインメモリを搭載できるのですが，それでもただのテーブルに4MByteというのはもったいないですし，組み込み用途などで少ないメモリしか搭載しない場合，物理メモリの大半をページ変換テーブルが占めるというバカバカしいことが起こってしまいかねません。
そこで，こんな対策をします。
まず，100万個を越えるPTEですが，その全てが公平に参照されるわけではなく，しょっちゅう参照されるところとほとんど参照されない部分が出てきます。例えば，1つのタスクに注目すると，そのタスクはまさか32ビットのアドレス空間を全部使っているわけではなく，そのうちのごく一部を使っているに過ぎません。
ですから，仮想アドレスから物理アドレスへの変換を行うときでも，ある限られた仮想アドレスの範囲だけが参照されるはずです。
こうして，よく参照されるものをメインメモリに残し，あまり参照されないものをハードディスクに逃がしてやります。
例えば，20ビットあったページ番号を，上位の12ビットと下位の8ビットに分けます。まず上位12ビットをインデックスとして1つ目の変換テーブルを参照し，2つ目のテーブルを参照するために，2つ目のテーブルのベースアドレスを手に入れます。
このベースアドレスと，先程の下位8ビットを合計して，2つ目の変換テーブルを参照して，ページ番号を手に入れます。
ここで，1つ目のテーブルは12ビットですので4096個のエントリがあります。2つ目のテーブルは8ビットですので256個のエントリがあります。ということは，2つ目のテーブルは1枚ごとに256ページの物理ページ番号が書かれていて，その表は全部で4096枚存在しているわけです。
そして，1つ目のテーブルは必ずメインメモリに残しておき，2つ目のテーブルは使っているテーブルだけメインメモリに残します。面倒なのでどの表もエントリの大きさは32ビットとしますと，1つ目のテーブルは16kByte，2つ目のテーブルは1枚あたり1kByteということになり，同時にメインメモリに置かれるテーブルはわずか17kByteと大幅に小さくなります。
こうして，ページ変換テーブルを複数階層に分割する仕組みを，マルチレベルページングと言います。もちろんメインメモリが許せば，2つ目のテーブルも1つだけにせず，よく使うものを複数メインメモリに置けば高速に処理が出来ますし，最近の64ビットアドレスを持つCPUでは2階層でも膨大な数になりますから，3階層や4階層に分けることをします。
ところが，ページ変換テーブルはメインメモリに置かれます。仮想アドレスを使って実行しているプログラムが，物理アドレスのどこにあるのかを知るのにいちいちメインメモリをアクセスするのでは，速度がなかなか上がりません。そこでCPU内部に，ページ変換テーブルのうち，よく使うものをコピーしておくメモリを少しだけ確保しておくことで，ここに残っているエントリであれば高速にアドレス変換を行う事が出来るようにしました。
この，ページ変換テーブルの一部をコピーするCPU内蔵の小さなメモリを，TLBといいます。TLBはTranslation Look-aside Bufferの略で，ページ変換テーブルを横目でちらちら見ながら（look-aside)作ったバッファという意味です。
ここでお気づきの方もいると思いますが，実はこのTLBは，キャッシュメモリそのものです。CPUはアドレスを参照するのに，まずTLBを見に行きます。TLBにエントリがあれば，そこから参照した物理アドレスを参照します。もしエントリがなければ，メインメモリにあるページ変換テーブルを参照し，TLBに登録するわけです。
TLBは一種のキャッシュですので，その読み出しの方法は，キャッシュと全く同じで，フルアソシアティブ方式，ダイレクトマップ方式，そしてnウェイセットアソシアティブ方式の3つがあり，その仕組みも同一です。
そして，TLBの入れ替えについても同じで，LRU方式，ランダム方式があります。どういうわけか，ラウンドロビン方式については用いられていないようです。
さて，ちょっと思い出してもらいたいのですが，仮想アドレスはタスクごとに固有でした。ところがTLBはタスクの固有情報であるページ変換テーブルのベースアドレスを持っていませんから，タスクが変わるとその内容も入れ替える必要が出てきます。
理想的には，TLBもタスクごとに別々に用意して，タスクが切り替わるごとにTLBも切り替えられればいいのですが，高価な高速メモリですからそんなに用意できませんし，そもそもタスクの数がいくつになるかわからないので，現実的には不可能です。
そこで，多くのCPUはタスクの切り替えが起こると，TLBの中身をクリアしてしまいます。しかしこれでは，せっかくのTLBがしょっちゅう無効になり，あまり効果が期待できません。CPUによっては，TLBにタスクの識別番号を一緒に入れておくことで，TLBのクリアを行わないようにしているものもあります。
TLBを命令用とデータ用に分ける例もあります。CPUにとって命令だろうがデータだろうが，メモリへのアクセスが発生することは同じです。命令の実行にはデータへのアクセスが必要な場合が多いことを考えると，実は命令とデータでアドレスの変換が同時に発生することが考えられます。
しかし，TLBは1つしかありませんから，どちらかを待たせて順番に処理する事になりますが，こうするとパイプラインが乱れてしまい，速度の低下が起きます。
そういうことなら命令とデータで別にTLBを持てば同時の変換ができますから，パイプラインは乱れません。キャッシュをメモリを命令とデータに分けるハーバードアーキテクチャというのがありますが，いわばこれのTLB版ということでしょう。
ところが，データは別にして，命令は順番に処理されますから極めて局所的で，それで大きなTLBを持つ事はもったいないという考え方もあります。そこで命令用のTLBについては4エントリ程度の超小型サイズTLBを持たせることがあります。これをマイクロTLBと呼んでいます。
本来のTLBはデータと命令を共通に持つごく普通のものですが，これをキャッシュする形でマイクロTLBを命令用に持ちます。こうすると命令とデータで2つTLBを持つのに比べて，TLBの更新のための回路が1つで済み，かつマイクロTLBだけで済んでしまう場合には消費電力も小さくすることが出来ます。なかなか合理的な方法ですね。
次にページフォールトについてです。
仮想アドレスを物理アドレスに変換した結果，そのページがメインメモリに存在せず，ハードディスクに追いやられていた場合に発生するのが，ページフォールトです。ページフォールトが起きると，メインメモリのどこかのページをハードディスクに追い出して，必要なページを取り込んできます。ハードディスクに追い出すことをページアウト，ハードディスクから取り込むことをページインといい，両方を総称してページスワップといいます。
ページフォールトをもう少し具体的に見てみます。TLB，そしてページ変換テーブルを参照し，仮想アドレスを物理アドレスに変換し，結果その物理ページがハードディスクに追い出されていることがわかると，例外が発生し，OSがその事実を知ることになります。
OSはページフォールトの発生を知り，ハードディスクとメインメモリのページを入れ替えます。あくまでこれはOSの仕事です。なかには，TLBに仮想アドレスが入っていないとすぐに例外をだして，TLBの更新さえOSに任せようとするCPUもあります。どこまでハードでやるのかソフトでやるのかは，その設計思想によるところも大きいわけです。
さて，OSはページアウトとページインを行わなければなりませんが，どのページを捨てるのかは，キャッシュの時と同じく重要な問題です。よく使うページを捨ててしまってはスワップが頻発するでしょうし，かといって真面目に統計を取るような事をしていたら，その処理が重くて大変です。なにせメモリ空間はキャッシュに比べて広大です。
そこで，ページ変換テーブルのエントリ（PTE）に，少し情報を持たせておきます。PTEに必要な情報は，言うまでもなくそのページが存在する物理アドレスですが，これにアクセスがあったことを示すフラグ，ライトがあったことを示すフラグ，メモリに存在することを示すフラグ，そしてそのページへのアクセス制限を示すフラグなどです。
このうち，アクセスがあったことを示すフラグを，OSは定期的にチェックしてゼロにし，TLBのエントリを無効化しておきます（なぜ無効化するかというと，TLBにエントリがあったらPTEまでアクセスが及ばないからです）。そして，アクセスがあると1を書き込むのです。このフラグがOSによってチェックされたときに1になっている場合の数を数えておくと，数が多いほどその仮想アドレスへのアクセスが発生している頻度が高いとわかります。
こうすると，擬似的にではありますが，LRU方式がかのうになり，頻度の高いページを捨てることが避けられます。
もっとも，これはOSの仕事です。OSによっては，ランダムに捨てるものもあるでしょうし，ラウンドロビンで捨てるものもあると思いますが，これはもうプロセッサと言うよりOSの問題です。
キャッシュと同じという事は，書き戻しの仕組みも似たような考え方をするということです。メインメモリから捨てられてハードディスクに追いやられるページがあったとして，このページの内容が書き換わっていないなら，すでにメインメモリとハードディスクで内容が一致しているわけですから，ハードディスクに書き戻す必要などありません。
ということは先程のPTEのフラグに，メインメモリが書き換えられてハードディスクと不一致が起こっていることを示すものを用意しておけば，必要なものだけハードディスクに書き戻してやればよいことになります。これはつまり，キャッシュにおけるライトバックと同じ事です。
もう1つ，PTEのフラグには，アクセス制限を行うものを用意してありました。CPUには実行レベルという考え方で，命令の実行やレジスタへのアクセスに制限を設けてあります。全てのリソースにアクセスせねばならないOSは最も上位のレベルでなければなりませんが，ユーザーアプリケーションなどは最低のレベルで動作させ，システム全体の信頼性を低下させるようなアクセスがあったら，例外を発生させてシステムダウンを防ぎます。
このレベルに準じて，アクセス可能なページかどうかをフラグにしてあれば，実行モードによってアクセス出来るアドレスと出来ないアドレスを自動的に制御できることになります。これがメモリ保護という仕組みです。
例えばx86のPTEでは，U/SというビットとR/Wというビットが存在します。U/Sがセットされている仮想ページには，ユーザーモード（レベル3）ではアクセスが出来ませんし，R/Wがセットされている仮想ページには，ユーザーモード（レベル3）に書き込むことが出来ません。
さて，キャッシュと同じという割には，随分と長い話になってしまったのですが，パイプラインとキャッシュ，そしてメモリ管理の3つはコンピュータ技術の中でも特に基礎的な事項であり，普段意識しないように作られているが故に知らなくても構わない上，それなりにややこしい話なので，頑張って勉強しようという人は以前よりも少なくなっているように思います。
Z80にCP/Mだったころは，こうした技術は大型の汎用機かスーパーミニコンという，雲の上のシステムで使われていた最先端技術だったわけで，コンピュータが好きでたまらない人はこうした最先端技術を強い憧れを動機とし，競って勉強したものと思います。
しかし，今や数万円のネットブックにも，この3つの技術は当たり前のように使われていて，すでに珍しい物でも憧れの対象でもなくなりました。
それでも，コンピュータは生まれ落ちたその時から，ひたすら高速であることを目指して突き進んでおり，その唯一とも言える目標のために，あらゆる工夫が試されてきました。
ある工夫が新しい問題を引き起こし，それがまた別の工夫で回避される，そうした工夫の連鎖が，1つの歴史として積み重なっていることが，コンピュータ工学の醍醐味ではないかと私は思います。
それは，こんな基礎的な事項にも，たくさん含まれているのです。
最後に，ちょっと面白そうな問題をもう1つ。
----
問題:仮想記憶のOSで，あるプロセスが参照しているページ番号の順序が，
3,5,2,0,2,5,4,3,0,3,5
であるとする。実ページの数を4とするとき，ページ置き換えのアルゴリズムにLRUアルゴリズムを用いたとき，ページフォールトの回数はいくつか。なお，ページ割り当ての初期状態として，すべてのページは未割り当てとする。
回答:
ページ参照の順に，実メモリの様子を見ていく。
3 3,X,X,X ページフォールト1回目
5 3,5,X,X ページフォールト2回目
2 3,5,2,X ページフォールト3回目
0 3,5,2,0 ページフォールト4回目
2 3,5,2,0 ページフォールトなし
5 3,5,2,0 ページフォールトなし
4 4,5,2,0 ページフォールト5回目
3 4,5,2,3 ページフォールト6回目
0 4,5,0,3 ページフォールト7回目
3 4,5,0,3 ページフォールトなし
5 4,5,0,3 ページフォールトなし
よって，ページフォールトの回数は7回。
---
ここで，もし実ページが1つ増えて，5になったらどうなるでしょうか。
3 3,X,X,X,X ページフォールト1回目
5 3,5,X,X,X ページフォールト2回目
2 3,5,2,X,X ページフォールト3回目
0 3,5,2,0,X ページフォールト4回目
2 3,5,2,0,X ページフォールトなし
5 3,5,2,0,X ページフォールトなし
4 3,5,2,0,4 ページフォールト5回目
3 3,5,2,0,4 ページフォールトなし
0 3,5,2,0,4 ページフォールトなし
3 3,5,2,0,4 ページフォールトなし
5 3,5,2,0,4 ページフォールトなし
実ページが5になったということは，実は全てのページが収まってしまうので，ページアウトは発生しません。ということで，5回のページフォールト，つまり5ページ全てが割り当てられるまでのページフォールトで済みます。
逆に，実ページが1つ減って，3になってしまったらどうなるでしょう。
3 3,X,X ページフォールト1回目
5 3,5,X ページフォールト2回目
2 3,5,2 ページフォールト3回目
0 0,5,2 ページフォールト4回目
2 0,5,2 ページフォールトなし
5 0,5,2 ページフォールトなし
4 4,5,2 ページフォールト5回目
3 4,5,3 ページフォールト6回目
0 4,0,3 ページフォールト7回目
3 4,0,3 ページフォールトなし
5 5,0,3 ページフォールト8回目
1回増えただけですね。結構激しく入れ替えがあったように思いますが，この程度のならそんなに差がなさそうだという気もします。とはいえ，実メモリが5の時に比べて，ページフォールトの起きている回数は1.6倍になっていますから，ハードディスクへのアクセスの遅さを考えると，数倍の速度低下になっていることは間違いないでしょう。
WindowsでもMacでもそうですが，メモリをたくさん積むと快適になるというのは，このあたりの話からも容易に想像出来ます。
