艦長日誌・私的記録 DS9

　コンピュータ基礎の基礎，今日が一応の最終回という事で，仮想マシンについてとりあげます。

　コンピュータのハードウェアにはCPU，メモリ，I/Oがあって，その上でソフトウェアは動いています。では，そのソフトウェアでCPUやメモリ，I/Oを記述し，ハードウェア上で仮想的に別のハードウェアを作り出して，その上で別のソフトウェアを動かすと，どんなメリットがあるでしょうか。

　かつて，大型の汎用機は，新機種に置き換わるときに，お客さんが使っているソフトウェアが使えなくなることが大問題でした。今のようにパッケージソフトなどなく，お客さんが自分の都合で作ったソフトばかりなわけですから，新機種がいかに魅力的であっても，苦労して作ったソフトが走ってくれなければ困ります。

　しかし，互換性の問題は，いつの時代も技術的な進歩の妨げになるものです。そこでコンピュータメーカーは，新機種上で旧機種を仮想的に作り出し，過去のソフトウェアはここで動かすことで，ユーザーの不安を取り除くことにしました。

　このように，過去の資産の継承という目的で登場したのが，仮想マシンという技術です。歴史的には随分と昔からある技術ですが，最近特に注目を集めているのは，高性能化するコンピュータを有効に利用するため1台のコンピュータを仮想的に複数台にし，台数を減らしてコストを削減したり，資産継承ではなく異なるOSを走らせて各々得意とするアプリケーションを走らせるなど，もう少し積極的な目的で使われる事が増えたからです。

　仮想マシンには，大きくわけて2つの方法があります。

　1つは，エミュレータに代表される方式で，ホストOS型と呼ばれるものです。その名の通り，実ハードウェア上にまず1つのOSが走っており，このOSの上で仮想マシンを実現するソフトウェアを走らせます。このOSをホストOSを言いますが，仮想マシンもこのホストOSの機能を使って作られます。

　もう1つは仮想マシンモニタ型というものです。ハードウェアとOSの間に，ハードウェアを仮想マシンモニタというソフトウェアを1段挟みます。仮想マシンモニタはハードウェアを仮想化するもので，ここから上位レイヤーに対して，仮想化されたハードウェアを提供します。この上で複数のOSが走るわけですが，すべて別々の仮想マシンで動いているわけです。

　ホストOS方式は実装は楽ですし，仮想マシンがあたかもホストOSのアプリケーションのように見えるのでわかりやすく，またホストOSは仮想化されたハードウェアで動いているわけではないので，仮想マシンによって生まれる制約がありません。

　その代わり，ホストOSの提供するサービスによって実装されている仮想マシンは，競合するリソースや演算パワーを割り振るオーバーヘッドの影響が大きく，速度的にも信頼性の点でも今一歩です。

　これに対して，仮想マシンモニタ型の仮想マシンは，なにせハードウェアが直接見えず，あるのは複数の仮想マシンです。面倒なリソースの配分はこの仮想マシンモニタが行ってくれますし，それぞれの仮想マシンで動くOSはどれも対等な扱いです。それに，仮想マシンモニタがあるおかげでオーバーヘッドも小さく済みます。

　とはいえ，この仮想マシンモニタもソフトウェアなわけで，出来るだけ軽く作るのが望ましいです。そのために，ハードウェアの支援，とりわけCPUに仮想マシンモニタを支援するような機構を入れ込むことが，近年のCPUでは当たり前になっています。

　では，x86で仮想マシンを実現するのに，問題となっていることを見ていきます。

　まず，x86には，実行レベルという概念があります。リング0からリング3までの4段階があり，実行レベルが上がれば上がるほど，アクセス出来るリソースに制約が多くなってきます。OSやBIOSは最低レベルで動いて全てにアクセス出来ないといけませんが，アプリケーションが最上位で動いてくれると，万が一ソフトが暴走してもOSに動作を妨げたり，マシン全体に影響を与えるような動きを防いでくれます。

　この，レベルによってアクセス出来る範囲を変え，信頼性を高める技術をリングプロテクションと呼んでいますが，高度なOSを実装するには必須の機能の1つです。

　x86の場合，OSは全てのリソースにアクセス可能なリング0で実装されてきました。リング1や2はOSの一部が使い，最上位で最も制約の多いリング3はアプリケーションが使う事になっています。もしアプリケーションがOSの動きを妨げるようなレジスタを書き換えようとしたら，例外が発生して保護するようになっているわけですね。

　仮想マシンを実現する仮想マシンモニタを実装するには，OSよりも下位のリングで動かす必要がありますが，仮想マシンモニタをリング0で動かしてしまうと，OSはリング1や2で動かすことになってしまいます。
　
　しかし，OSは全てのリソースにアクセスしようとしますから，リング1や2でリング0でなければアクセス出来ないリソースをアクセスしてしまうと，例外が発生してしまいます。

　仮想マシンモニタは，この例外を受けると，その命令をエミュレートしてOSの代わりにレベル0でアクセスを代行し，結果をOSに渡してあげます。しかし，想像が付くようにこの方法はいちいち例外を監視し，命令のエミュレートを行うために，オーバーヘッドが大きくて速度が上がりません。

　別の問題もあります。

　x86はその名の通り，8086に端を発する歴史あるプロセッサです。互換性を維持してここまで来た驚異のプロセッサですが，これも簡単なことではなく，無理な建て増しを繰り返して，矛盾をギリギリの所で回避して成し遂げた産物です。

　例えばpopfという命令ですが，なんとリングレベルによって異なる動作をする命令だったりします。ということは，仮想マシンモニタの上で動いているOSが，リング0で動いているつもりで実行したpopf命令が，実はリング1や2で別の動作をすることが起きてしまうのです。

　この場合，悪いことに例外も発生してくれませんから，仮想マシンモニタはpopf命令がこないかどうか，常に監視する必要が生じるのです。これはさすがに足を引っ張りそうですね。

　ここ数年で用意されたx86の仮想マシン支援機能では，この問題を効果的に解決しています。まず，リング0からリング3まのリングをもう1つ用意し，それぞれVMXrootとVMXnon-rootと呼ぶようにしました。そして仮想マシンモニタをVMXrootで動作させ，OSをVMXnon-rootで動作させるのです。

　VMXnon-rootで動作するOSが，もし特権命令を実行したら，即座に処理をVMXrootに切り替え，仮想マシンモニタに制御を移します。VMXnon-rootのリング0では，リソースにアクセス出来ない代わりに，VMXrootで走っている仮想マシンモニタが動いてくれるわけですね。

　こうすると，例外によって処理を代行することもなく，またpopfをいちいち監視することもなく，オーバーヘッドを大幅に削減できることがおわかり頂けると思います。

　これに加えて，それぞれの独立した仮想マシンは，各々のコンテキストを保存しておかなければいけないのですが，その保存領域を専用に用意してあり，仮想マシンの切り替え時にはこれらの待避と復帰が自動で行われるようになっていて，これも大幅にオーバーヘッドを削減することに貢献しています。

　さらに，I/Oについても仮想マシンの支援の仕組みが考えられています。I/OとOSを繋ぐのはデバイスドライバですが，I/Oも仮想マシンモニタで管理されると，従来のデバイスドライバは当然使えません。またI/Oのエミュレータが仮想マシンモニタから提供されるようなものですので，非常に遅くなります。

　そこで，DMAのアドレスをハードウェアでリマップする機能を持たせてあります。こうすると，実際のI/Oデバイスのアドレスを直接仮想マシンに提供出来るようになるため，従来のデバイスドライバがそのまま利用出来るようになるばかりか，高速にアクセスが可能になってくれます。

　ただし，仮想マシンモニタが行ってくれていた排他制御はできなくなってしまいますので，ここはハードウェアによる排他制御が可能になるよう，PCIeの仕様が拡張されているので，これを用いることになっているそうです。

　さて，長々とコンピュータの基礎的な事項についてまとめを行って来ました。最終的には仮想マシンの支援機構までやってきましたが，ふと気が付くのは，従来は出来るだけハードウェアの規模を小さくして，その中で最大限の処理能力を出そうと言う目的で新しい技術が開発されてきたところが，最近では使う事の出来るトランジスタの数が膨大になり，処理能力を上げるためにどうやって回路規模を大きくするかを考えると言った，アプローチの違いがあるように感じます。

　例えばキャッシュメモリをたくさん積むことや，4コア，6コアという多数のコアを実装するマルチコアプロセッサなどは，その例だと思います。見方によってはインスタントで安易な高速化の方法が利用出来るようになるほど，トランジスタがふんだんに利用出来るようになったということでしょうか。

　しかし，喜んでばかりもいられません。微細化によってトランジスタの数が増えても，その微細化は消費電力の増大と発熱の問題を助長します。いつの時代も，こうしてバランスを取りながら，知恵と工夫でコンピュータの性能は上がり続けるのだと思うと，私などはワクワクしてしまいます。

　今後，どういう流れになっていくのでしょうか。特にマルチプロセッサの次に来るのは，いったいどういう技術でしょうか。楽しみです。

　さて，今日はマルチプロセッサとマルチスレッドについてです。

　CPUは1980年代のRISCから1990年代のスーパースカラ，そして2000年代に入りマルチプロセッサに，その進化の方向が移ってきました。RISCはパイプラインとコンパイラ技術によって高速化をしようという試みでしたが，次にやってきたスーパースカラはソフトはそのまま変えずに，出来るだけハードウェアで並列な命令実行を行うものでした。CPU設計者が無茶な意地を張っていた時代です。

　そしてスーパースカラに限界が見えて，マルチプロセッサの時代になりますが，これはマルチプロセッサを前提にしたソフトウェアを作らなければ全く高速にはならず，その点でハードウェア設計者が再びソフトウェア設計者に頭を下げた，と言っていいかも知れません。

----

問題:
　ある問題について，その実行時間の95%は完全に並列処理が可能で，Nプロセッサを利用することによりN倍性能が向上する。しかし，残りの5%は全く並列処理を行うことが出来ない。この問題を10台のプロセッサを用いて並列処理を行った場合，1台で実行するのに比べて何倍高速に実行することが可能か？

----

　まず最初に，マルチプロセッサとアムダールの法則についてです。

　仕組みや構造はちょっと置いておいて，2つのプロセッサを用いると，処理時間は1/2になりそうなものです。とはいえ，人間でも同じですが，二人が手分けして仕事をしても，なかには手分けできない仕事もあります。こういうものはどちらかが処理するかありません。

　System360の設計者で，後に富士通と一緒にSystem360互換機をビジネスにするジーン・アムダールは，プロセッサの数と同時実行不可能な命令の割合から，最終的な処理速度がどれくらい高速化されるかを公式にしました。これがアムダールの法則です。

　プロセッサの数をNとし，同時に実行出来ない命令の処理時間の割合をFとします。

　まず，Fが0，つまり全ての命令が同時に実行出来るという状態を考えると，プロセッサの数が1の時に比べて，1/Nの時間で処理が終わります。

　逆に，Fが1，つまり全ての命令が同時に実行出来ないという状態を考えると，プロセッサの数であるNに全く関係なく，1つのプロセッサで処理せねばなりませんから，プロセッサの数が1のと同じ処理時間，つまり1倍となります。

　では，Fが0.5，つまり半分は同時に実行出来る場合はどうなるかです。Nに関係なく，絶対にかかってしまう処理時間は0.5です。残りの0.5は1/Nになりますね。もしプロセッサが2つだったら，0.5+0.5*1/2で，0.75です。プロセッサが1つの時に比べて0.75の時間で処理が終わるということになります。

　さて，一般化しましょう。プロセッサが1つ時に比べて，どのくらいの処理時間がかかるのかは，

　F + ((1-F) / N)

　ですね。何倍高速，と言う言い方にするには，これの逆数をとればよいです。

　では，この式を使って早速問題を解いてみましょう。

---
回答:
　全体の処理時間を1とすると，同時に実行出来ない時間は0.05，同時に実行出来る時間は0.95である。プロセッサの数が10であるから，プロセッサが1台の時の処理時間を1とすると，このシステムでは，

　0.05 + 0.95*1/10 = 0.145

　の時間で済むことになる。よって1/0.145=6.90倍高速に実行が可能である。
----

　アムダールの法則によると，プロセッサを10台も使い，しかも命令の並列性を95%まで高めても，7倍弱までしか速度が上がらないのです。なんだか割が合いませんが，プロセッサの数を2つに減らし，しかも命令の並列性が80%まで悪化していると，1.67倍にしかなりません。プロセッサの数を増やすことも大事ですが，実際には命令の並列性を高めることがもっと大切なのです。

　マルチプロセッサには，大きく分けて対象型と非対称型があります。例えば汎用CPUとDSPの組み合わせのように，プログラムを分け，それぞれのプロセッサの役割も決められているようなシステムは非対称型と言われますが，何せいろいろな方法がありますのできちんとした定義は難しいです。

　一方の対象型は，プログラムも役割も同一です。また共有しているメモリへのアクセスについても時間的空間的に平等です。その共有メモリについて，全てのメモリを同じアドレスで複数のプロセッサにアクセスが可能になっているものを集中共有メモリ方式といい，プロセッサごとにローカルメモリを持つものを分散共有メモリ方式と言います。

　言うまでもなく，同じメモリに全てのCPUがアクセス可能というのはプログラムを書くのが楽ですし，わかりやすいですからほとんどがこの方式といってもよいと思いますが，何分メモリが1つ，バスも1つですから，あるCPUがアクセスをしていたら，他のCPUは待たされてしまいます。処理速度がバスのせいで上がらないというわけです。おのずとCPUの数は制限を受けてしまいます。

　一方の分散共有メモリ方式は，命令の局所性をあてにして，バスを使わず自分だけのメモリをガンガンアクセス出来る仕組みですので，プロセッサの数はいくらでも増やすことが出来ます。

　しかし，他のCPUのローカルメモリにアクセスに行くには時間がかかってしまう傾向があります。これではマルチプロセッサでの高速処理が，メモリのアクセスでふっとんでしまいかねません。

　それぞれに一長一短がありますので，システムの規模やコストによって使い分けられています。

　ここでは，対象型の集中共有メモリ方式を例に考えていきます。

　バスとメモリを共有しているのですが，CPUごとにキャッシュメモリを置いてやると，バスやメモリへのアクセスが激減します。しかもキャッシュメモリはソフトウェアにはほとんど影響を与えません。これでマルチプロセッサは万々歳といいたいところなのですが，大きな問題があります。

　キャッシュというのは，メインメモリの一部を高速なメモリに蓄えておくものでした。メインメモリとキャッシュの内容が食い違うことが起こるので，これをどうやって解消するかという問題が，キャッシュでは重要なテーマの1つだったことを思い出して下さい。

　これがマルチプロセッサになると，さらに深刻です。なぜなら，自分の手元にあるキャッシュのアドレスを，他のプロセッサが変更しているかもしれず，その場合自分に変更の覚えがなくても，自分の手元のキャッシュの内容がメインメモリと食い違っていることがあるわけです。

　こうなるともうキャッシュの内容を信用できなくなってしまいます。さすがにまずいので，何らかの対策を取って，それぞれのCPUが持っているキャッシュの内容の一致をしなければなりません。これをキャッシュのコヒーレンシを保証するといいます。

　手段としてはいくつかありますが，ここではMESIプロトコルについて考えてみましょう。

　MESIプロトコルとは，

Modified
Exclusive
Shared
Invalid

　の頭文字を取ったものです。この4つはキャッシュメモリの状態を示すステートで，キャッシュのタグに書き込まれています。これらを持つステートマシンを考えます。4つのステートの状態を以下に示します。

M
　キャッシュメモリとメインメモリは不一致で，他のキャッシュメモリにはキャッシュされていない。

E
　キャッシュメモリとメインメモリは一致しており，他のキャッシュメモリにはキャッシュされていない。

S
キャッシュメモリとメインメモリは一致しており，しかも他のキャッシュメモリにもキャッシュされている。

I
　キャッシュメモリの内容が無効であることを示す。

　基本的には，Sのステートになるように制御がかかります。この制御を行うのが，メインメモリとキャッシュメモリの間に入る，スヌープコントローラです。スヌープとはのぞき見という意味だそうです。

　さて，2つのCPUが同じアドレスのデータをリードした場合を考えます。最初に1つ目のCPUがリードを行うと，1つ目のステートはIからEに遷移します。続いて2つ目のCPUのアクセスが起こると，1つ目のステートはEからSに遷移し，2つ目のステートはIからSになります。2つともSになっていますので，全てのデータが一致していますね。コヒーレンシは保たれています。

　ここでCPU1が書き込みを行ったとします。キャッシュの内容がメインメモリと不一致になりましたので，ステートはMに遷移します。同時に2つ目のステートはSからIになり，キャッシュを無効とします。無効になったのですから，1つ目のキャッシュの内容は2つ目のキャッシュにはキャッシュされていないことになり，Mで矛盾は生じません。

　そしてここでスヌープコントローラの出番です。スヌープコントローラは2つのキャッシュのステートがSになるように動きます。ここでは，1つ目のキャッシュの内容をメインメモリに書き出します。そしてそのデータを2つ目のキャッシュにも書きます。

　このことで2つのキャッシュとメインメモリの3つが全て一致しましたので，1つ目のキャッシュはMからSへ，2つ目のキャッシュのステートはIからSに遷移します。こうして，出来るだけSになるようにして，コヒーレンシを維持するのです。

　対象型のマルチプロセッサにおいては，CPUがいつアクセスを行ってそのデータが有効でなくてはなりません。しかしデータの保存場所がメインメモリだけではなく，それぞれのCPUのそばにも存在しているので，基本的には全てのデータが一致していないと，マルチプロセッサシステムとしては成り立ちません。

　さてさて，ここまででCPUの数は複数に出来ました。しかし前述の通り，複数の命令が同時に実行出来るようにしないと，CPUが同時に動いてはくれません。

　ぱっと思いつくのは，メモリ空間さえも独立しているプロセスを単位として，CPUに割り付けて同時実行することです。しかし，あくまでそのプロセスは1つのCPUで動いていますから，そのプロセスが重いときには，他の手の空いているCPUは手伝ってあげられません。

　かといってOSにはプロセスの中身を見て分割する機能まではありませんから，1つのプロセスを複数のCPUに割り当てることは不可能です。

　そこで，各プロセスの中に「ここは同時に動かしますよ」という印を付けることにします。

　こうして，同じプロセスの内で同時に動くのがスレッドです。同じプロセスですからそれぞれのスレッドは同じメモリ空間で動いています。

　実は，プロセスが情報の共有を行おうとすると，プロセス間通信などを行う事になりますが，これは結構オーバーヘッドも大きく，効率的とはいえません。しかしスレッドはメモリ空間が同じですから，グローバル変数で共有出来るので，とても高速で効率がよいのです。

　そして，わざわざ明示してくれた「同時に動かしますよ」と書かれたスレッドを，複数のCPUに割り当てるのです。どうですか，メモリは共有でグローバル変数で情報のやりとりが出来，同時実行可能とわざわざソフト屋が書いてくれているのです。

　ソフト屋さんとしては，これまで1つのプロセスを書いているつもりで済んでいたのが，どれとどれを同時に実行するかを考えて，スレッドという形で分割しないといけないことになりました。

　プロセスを分割してスレッドにする方法は，大きく分けて2つあります。1つはフォークジョインモデルで，文字通りソフト屋さんが同時実行可能な部分でスレッドと生成し，ソフト屋さんが設定した同期ポイントによってメインのスレッドと同期します。

　POSIXの場合，スレッドの生成はpthread_createで行います。こうして複数のスレッドが生成され，それぞれが同時実行される時に，CPUが複数あればスレッドをCPUに割り当てることで，処理能力を向上させることが出来るわけです。そして各スレッドの結果は，設定された同期ポイントで同期されます。

　しかし，いかにスレッドが軽いとはいえ，スレッドの生成や同期にはそれなりの時間も手間もかかります。スレッドに分割して複数CPUに割り当てて高速化出来ても，これらのオーバーヘッドで食いつぶしてしまうようだと意味がありませんから，スレッドとして同時実行される時間が十分に長い場合ことが条件です。

　もう1つはスレッドプールモデルと呼ばれます。これは複数のスレッドが定期的に実行されることが先に分かっている場合に有効な方法で，これら複数のスレッドをひとまとめにしたスレッドのプールを作成します。

　そして，このプールに情報を入力することで，複数のスレッドが動作して処理されていくのです。スレッドの生成をいちいち行いませんし，同期も頻繁に行いません。それにあらかじめスレッドをひとまとめにしておく関係で，各スレッドの対称性が高い，つまり似たような単位に区切って置けるということで，処理の効率が随分よくなります。

　ということで，例えばWEBブラウザでGoogle Chromeなどは1つのタブを1つのスレッドで処理しています。ですからCPUが増えれば増える程，同時に処理されるタブの数が増えるので，タブをたくさん立ち上げても処理速度が落ちません。また，タブの1つがエラーを出してこけても，スレッドという単位で独立していますから，そのタブが落ちて終わるだけです。（もちろんスレッドで共有されたメモリが壊されてしまえばプロセス，つまりアプリケーションが丸ごと落ちることもあります）

　しかし，CPUが1つしかない時には，スレッドの生成や同期に時間がかかってしまうので，そうした処理を行わない他のブラウザの方が軽くなることになります。そう考えると，マルチコアが当たり前になった昨今のパソコンを使い切るのが，Google Chromeということになりますね。

　そして，CPUの進化がマルチコアと言う方向に進んでいる現在，ソフトを書く上でもどことどこを同時に実行出来るか考え，それをスレッドという単位でまとめることがとても重要な技術になってきます。こうして半導体の進歩とソフトウェアの進歩は歩調を合わせることになり，コンピュータ全体の処理能力が高まっていくことになりました。どちらか一方だけではだめ，そんな時代が来たことを改めて感じます。

　コンピュータ基礎の基礎，今回は浮動小数点演算です。

　一般に，我々がコンピュータを扱うときには，整数で表現が可能な演算が中心です。しかし，コンピュータが計算機である以上，小数点を扱う演算も日常的に起こります。

　Z80のように乗除算さえ持たないCPUを搭載した昔のパソコンでも，浮動小数点演算が出来た事を考えると，整数しか扱えないCPUも，プログラム次第で浮動小数点が扱えることになりますが，このように2進数で浮動小数点演算を行う場合には，その扱い方，つまりフォーマットが非常に重要です。

　かつては，この各社でバラバラだったフォーマットも，IEEE754という国際標準によって統一されており，データフォーマットの違いによるデータ互換のなさなど，不便な点が解消されてきました。

　まず，最初に，2進数で小数点の付いた数をどうやって表現するかです。

　思い出して欲しいのは，2進数というのは2になると桁が上がる数でした。一桁増えるごとに2倍になるのが2進数です。これはいいですね。

　10進法では，桁が増えるごとに10倍になるわけですが，では小数点から以下の桁はどうだったかというと，小数第一位が1/10，小数第二位が1/100と，桁が小さくなるごとに1/10ごとになっていきます。

　2進数でも同じ事で，小数第一位は1/2で0.5，小数第二位は1/4で0.25となっていきます。小数点以下が01なら0.25，10なら0.5，11なら0.75となるわけですね。

　では具体的に，小数点の付いた数を2進数で表現してみましょう。14.75を2進数で表現すると，まず小数点から上である14は1110です。次に小数点以下ですが，0.75から0.5を引き算すると0.25ですので，小数第一位と小数第二位の両方のビットが立ちます。

　よって，14.75は，2進数では1110.11となります。簡単ですね。

　浮動小数点というのは，小数点が動く表現方法です。先程の14.75は，1.475x10の-1乗，というわけですが，このうち1.475を仮数，10を基数，そして-1を指数といいます。これも基本ですね。

　問題はここから先です。この1110.11という0と1の列びを，どうやってメモリに格納するのかです。例えば小数点から上の1110の部分を何ビットで格納すればいいでしょうか。8ビット？10ビット？各社でバラバラだと，そのデータに互換性が出てこないのも頷けます。

　そこで1985年に制定された標準形式がIEEE754です。もう少し見ていきましょう。IEEE754のフォーマットは，以下のようになっています。

(1)基数は2で，基数はデータに含めない。
　基数というのは何の2乗とか3乗かを示す数字でした。IEEE754は2進数を扱うフォーマットですから，基数は2です。わかりきったことなのでいちいちこれをフォーマットには入れません，と言う意味です。

(2)仮数は1以上，2未満に揃える。これを正規化という。
　先程の14.75も，浮動小数点で表現すると1.475x10の-1乗となりました。このことで仮数部は10未満になります。IEEE754でも同じ事で，仮数部を1以上未満で扱う事にします。

(3)0の表現は，指数と仮数の全ビットをゼロにする。
　仮数部を0にすれば絶対にゼロなのですが，IEEE754では仮数部が0で指数部が最大になっているものを∞の表現に割り当てます。ゆえに全ビットゼロとしなければなりません。

(4)仮数も指数も2進数で表現する。
　これもまああたり前の話です。14は1110ですし，0.75は0.11です。

(5)MSBが符号ビットで，0が正，1が負を示す。
　当然正の数も負の数も扱いますので，符号ビットを考えておかねばなりません。MSB，つまり最上位のビットに符号の役割を与えます。

(6)単精度は32ビットで，符号1ビット，指数部8ビット，仮数部23ビットである。0から22ビットまでが仮数部，23から30ビットが指数部，31ビットが符号ビットである。
　IEEE754には単精度と倍精度の2つがありますが，このうち単精度は指数部を8ビット，仮数部を23ビットとしてあります。

(7)単精度の場合は，指数部は実際の指数に127を足し，仮数部は整数部分の1を省略する。
　正規化してあるので，仮数部は必ず1以上2未満になりますから，整数部分の1をわざわざ記述する必要がありません。また，指数部に足される127という数値をバイアス値と言います。バイアスを加えるのは，指数部が負の数を取ることがあるからです。

(8)倍精度は64ビットで，符号1ビット，指数部11ビット，仮数部が52ビットである。0から51ビットが仮数部，52から62ビットが指数部，63ビットが符号ビットである。

(9)倍精度の場合，指数部は実際の指数に1023を足し，仮数部は整数部分の1を省略する。

　ルールとしてはこんな感じです。

　では，2.5を単精度で表現してみましょう。

　まず，2.5を2進数で書きます。2は2進数で10，0.5は2進数で0.1ですから，10.1となります。

　これを正規化します。10.1x2^0ですから，これをシフトし，1.01x2^1とします。ここで，仮数部が1.01，指数部が1，そして基数が2となります。

　仮数部は整数部分を省略しますから，01となります。なお，基数2も省略します。また符号ビットは正ですので0です。

　仮数部は1になりますが，これにバイアス値である0x7fを足し，0x80とします。

　これらから，以下のようになります。

0 10000000 01000000000000000000000

　それでは次に0.1を倍精度で表現してみましょう。

　実はこの0.1をに2進数で正確に表現するのが不可能なのです。

　0.1ですから，0.5よりも，0.25よりも，0.125よりも小さいです。この段階で0.000まで確定です。

0.1-2^(-1)=-0.4　　0.0
0.1-2^(-2)=-0.15　　0.00
0.1-2^(-3)=-0.025　　0.000

　さらにもうヒトケタ小さくしますと，0.0625です。ここでようやく1になり，0.0001です。しかし余りが0.0375でます。

0.1-2^(-4)=0.0375　　0.0001

　余りである0.0375を使って以後計算します。

0.0375-2^(-5)=0.00625　　0.00011
0.00625-2^(-6)=-0.009375　　0.000110
0.00625-2^(-7)=-0.0015625　　0.0001100
0.00625-2^(-8)=-0.00234375　　0.00011001
0.00234375-2^(-9)=0.000390625　　0.000110011
0.000390625-2^(-10)=-0.0005859375　　0.0001100110
0.000390625-2^(-11)=-0.00009765625　　0.00011001100
0.000390625-2^(-12)=0.000146484375　　0.000110011001

　というわけで，ちゃんと証明したわけではありませんが，どうやら00110011・・・手な具合に循環していそうです。これでは永遠に割り切れることはないでしょう。つまり，0.1は2進数でちゃんと表現出来ないということになるのです。

　それはそれとして，先に進みましょう。0.0001100110011・・・を正規化します。1.100110011・・・x2^-4となります。よって仮数部は1.100110011・・・，指数部は-4です。

　指数部は倍精度の時には0x3ffをバイアスとして足します。すると指数部は0x3fbです。そう，指数部が負の数を取ることがあるから，バイアスを足すのでしたね。

　よって，64ビットで表現される倍精度フォーマットでは，以下のようになります。

0 01111111011 1001100110011001100110011001100110011001100110011001・・・

　一見するとこれいいように思いますが，実は循環する数字がそのままカットされているので，決まった範囲に数値が収まるように，丸めを行います。言ってみれば，3.14159・・・とせず，3.14と小数第2位までで表現するのと同じ事です。

　IEEE754では，4つの丸めが定義されています。

・最近接偶数丸め（RN）
　最も近くの表現できる値へ丸めます。基本的には0捨1入としますが，ちょうど中間の場合には，偶数になるよう，つまり仮数部の一番低位の数字が0になるようにします。誤差の蓄積もなく，もっともおすすめの方法です。

・0方向丸め（RZ）
　常に0に近い方に丸めます。いわゆる切り捨てです。

・+∞への丸め（RP）
　正の無限大に近い方に丸めます。

・-∞への丸め（RM）
　負の無限大に近い方に丸めます。

　さて，先程の数字ですが，標準では最近接偶数丸めを使います。入りきらなかった最初の数字は1ですので，これは0に丸めます。つまり，110011は，1000000に丸めます。よって，0.1は倍精度では，

0 01111111011 1001100110011001100110011001100110011001100110011010

　となります。

　この丸めによって，実は，10進数で0.0000000000000000055511151231257827021181583404541015625もの誤差を含んでいることになるわけですが，これがデジタルコンピュータの本質的な問題であるという事です。

　さて，続いてスーパースカラプロセッサについてです。

　パイプライン，キャッシュ，そして仮想記憶と，コンピュータについて重要な基礎的技術についてはこの3日で勉強してきました。今回のスーパースカラや次のマルチプロセッサについては，必ずしも全てのコンピュータに入っているわけではなく，一般化したかどうかには意見が分かれるところがあると思います。

　しかし，技術的には完成の域に達しており，後は使うか使わないかだけの問題になっています。その点では基礎的な技術と言ってもよいかも知れません。

　パイプラインとキャッシュを使えば，1サイクルごとに1命令を実行出来るという，かなり理想的なところまで可能になることがわかりました。といいますか，RISCプロセッサというのは，命令を単純にして1命令を小さく作って，それをパイプラインに流して1サイクルで1命令を実行出来るようにしたプロセッサでした。

　しかし，1サイクルで1命令が実現してしまったわけですから，ここから先の高速化は今の構成では不可能です。だって，1サイクルで1命令以上を処理するには，処理する装置を1つから複数に増やさねばならない訳ですから。

　こうして，複数の命令を実行出来るようにパイプラインを複数に増やしたプロセッサを，スーパースカラプロセッサといいます。

　パイプラインが1本のプロセッサは同時に1命令しか実行出来ませんが，これはスカラプロセッサと呼ばれています。これを越えるものとして，複数命令が同時に実行出来る複数パイプラインのプロセッサを，スーパースカラプロセッサといいます。

　例えば，パイプラインが2本になれば，同時に実行出来る命令は2になりますから，単純に倍になりそうです。しかし残念な事に，順番にやってくる命令が，いつも同時に実行可能とは限りません。

　例えば，1つ目の命令の結果を2つ目の命令で使う場合など，どうしても順番に処理しないといけなくなります。

　実はスーパースカラプロセッサのキモというのは，命令の並列性を調べ，同時に実行出来そうな命令を並べるという技術に集約されます。

　そんな並列性は，コンパイル時に並べ替えておけばいいだろうという方，とても鋭いです。まさにその通りで，スーパースカラプロセッサは，シングルパイプラインのプロセッサとプログラムの互換性を持ちますが，コンパイルし直した方が高速に動作することは良くあることです。

　しかし，遅くとも古いソフトがコンパイル無しでもそこそこ高速に動くということはとても重要なことであり，いわば並列性を調べて並べ替えを行う仕組みをハードウェアで実装したのがスーパースカラプロセッサであり，コンパイラでやってしまったのがVLIWといってよいと思います。

　当然，スーパースカラプロセッサは巨大になり，複雑になりました。同時に実行出来る命令が1つから2つになれば2倍になっても，4個から5個に増えてもたった25%しか速くなりません。その上，パイプラインが増えるほど同時に実行出来る組み合わせは厳しくなり，回路規模は増大しクロックも上がらず，しかも結果として遊んでいるパイプラインが出てきてしまうこともあり得ます。

　こうして，一世を風靡したスーパースカラプロセッサは限界を迎え，現在は完成した技術として利用されているのです。

　では，スーパースカラプロセッサについて，もう少し詳しく見ていきましょう。パイプラインを複数並べて命令が同時に実行出来るということは，どのめいれいが同時に実行出来るかを判断し，必要に応じて命令の並べ替えを行うことが必要になります。前述のように，スーパースカラプロセッサというのは，これが最重要技術です。

　命令の順番を入れ替えて良い場合は，同時実行を行うことの出来るような組み合わせを作る事が出来ます。命令を順に実行することをインオーダ，命令の順を入れ替えることをアウトオブオーダといいます。

　しかし，命令が順番通りに実行されないと予期しない結果を招くことがあります。以下にその問題として3つのハザードを示します。

(1)リード・アフター・ライトハザード(RAW)
　読み出して利用したいレジスタの値が，先行の命令によって書かれたものであって欲しい場合に発生する問題です。書くのは先行の命令，読むのは後続の命令です。先行命令が書いた結果を後続命令が読んで利用するというのはよくあることですが，順番が変わってしまうと結果が出る前に読まなくてはいけませんから，これはどうにも回避不可能な問題で，命令の入れ替えは出来ません。

(2)ライト・アフター・ライトハザード(WAW)
　同じレジスタに2回の書き込みがあった場合，2回目の書き込みが残っていないといけないというものです。順番が入れ替わって1回目が後に書かれてしまうと，2回目の結果が上書きされますので，消えてしまいます。

(3)ライト・アフター・リードハザード(WAR)
　読み出して利用したいレジスタの値が，後続の命令によって変更される前のものであって欲しい場合に発生する問題です。書くのは後続の命令，読むのは先行の命令で，RAWハザードとは逆になります。順番が入れ替わると，先行の命令が使う値が後続の命令によって変わってしまう可能性があるわけです。

　このうち，(1)は命令の順番が変わってしまうと回避不可能，(2)と(3)については，レジスタリネーミングを使って回避が可能です。

　そのレジスタリネーミングというのは，レジスタの名前を付け替えることです。実際にはレジスタの数を増やして実現しますが，プログラムを書く人から見てレジスタが増えたわけではないので，リネーミングといいます。

　レジスタリネーミングを使うと，(2)は同じレジスタにせず異なるレジスタに書き込むようにし，命令の順番通りに結果を使うようにすれば回避できます。

　(3)についても同様で，リネームして異なるレジスタを相手にして動いてもらい，最終的に命令の順番通りに読み出せば，結果が出るまでの途中の順番が入れ替わっても問題はありません。

　こうして，レジスタリネーミングを用いれば，(1)のRAWハザードだけを考慮すれば，(2)と(3)は解決出来たことになります。つまり，レジスタを2つ用意して結果をどちらも潰さず残しておき，利用するときに書き込み前の値が欲しければ古い方を，書き込み後の値が欲しければ新しい方を読み出して使うという仕組みです。

　こうして，順番を入れ替えて実行することがある程度出来るようになりました。ここで，命令の実行が完了する時刻に注目すると，命令によって時間のかかるものとかからないものがあるわけですから，当然終わる時刻が同時とは限りません。そこで，命令の処理が開始された状態を発行，処理が終わった状態を完了と決めて，それぞれインオーダとアウトオブオーダと組み合わせます。すると，

　インオーダ発行
　インオーダ完了
　アウトオブオーダ発行
　アウトオブオーダ完了

　の4つの組み合わせが出来ます。

・インオーダ発行

　これはもっとも単純で，命令キューに入っている連続する命令が同時実行可能かどうかを判断するだけです。もし命令に依存性があり，同時実行出来ない場合には，1命令のみを発行します。

・アウトオブオーダ発行

　アウトオブオーダ発行の場合は，命令の順番が入れ替わって発行されるわけですから，命令キューに入っている命令の全てで依存性が調べられます。冷静に考えると，命令キューに入っている命令のオペランドを，互いに使っていないかどうかをざっと調べるだけでよいことになります。もし依存性が全ての命令であった場合は1命令のみを発行します。

・アウトオブオーダ完了

　スーパースカラプロセッサとしては最も完璧なものになりますが，命令を完了する順番さえも入れ替わっていてよい，ということですので，もうなんでもありです。しかし，命令の完了順番が違ってくると，ライト・アフター・ライトハザードが発生してしまいます。

　これはレジスタリネーミングで回避できるとしても，実は例外や割り込みのを考えるた場合，順番が入れ替わってしまうと優先順位が変わってしまうことと同じになり，大変まずいですから，実はこのアウトオブオーダ完了という仕組みは一般的には使用されません。

・インオーダ完了

　これは結果の出る順番を入れ替えないわけですから，早く終わった命令が遅い命令を待ってあげればいいだけのことです。先に出た結果をROB（ReOrder Buffer）と呼ばれるバッファに取り込んでおき，結果の順番を守るわけです。これだと，アウトオブオーダ完了で問題となった例外や割り込みの問題は発生しません。

　ということで，スーパースカラプロセッサには，現実的には，インオーダ発行でインオーダ完了のインオーダ型と，アウトオブオーダ発行でインオーダ完了のアウトオブオーダ型の2種類しかない，ということになります。

　スーパースカラプロセッサの場合，シングルパイプラインのプロセッサに比べて，時間的な前後関係が問題になることがわかります。従って，単にパイプラインを乱さないようにしていれば良かった話が，依存関係を崩さないという絶対に守らなければならないことを考慮しなくてはならず，大変難しくなります。

　例えば，遅延分岐で済ませていた分岐のペナルティも，スーパースカラでは分岐予測と投機実行を組み合わせるのが普通です。

　分岐予測には3つの種類があり，分岐しないと決め打ちする単純予測，プログラムの走っている向きに逆行する場合はループの終端だから分岐すると決め打ちし，順行する場合は分岐しないと決め打ちする静的な分岐予測，分岐回数と分岐先の履歴から次の分岐を予測する動的な分岐予測があり，後者の方がヒット率が高いと言われています。動的な分岐予測には様々な方法があり，現在では90%を越えるようなヒット率を実現している例もあります。

　投機実行は，その分岐予測の結果が出る前に命令をとりあえず実行してしまうのですが，当然外れることもあるわけで，その場合はやり直しになります。しかし，どうせ分岐先が決まるまで待ち時間が出てしまうわけですから，その間にとりあえず命令を実行しても，無駄にはなっていません。

　スーパースカラプロセッサは，確かに複雑さと性能向上のバランスが限界に達して，これ以上大きな進歩はないと思いますが，なにも闇雲にパイプラインの数を増やすことをしなくても，時間のかかる浮動小数点演算と整数演算を並列に同時実行するだけでもそのメリットは大変に大きく，コンパイラによる命令の並べ替えと併用し，今後のプロセッサに必須な技術になっていくと思います。

　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でもそうですが，メモリをたくさん積むと快適になるというのは，このあたりの話からも容易に想像出来ます。