2015.6.9 コンピュータアーキテクチャII 講義ノート (キャッシュと仮想記憶) キャッシュ 1 1.1 ここで学ぶこと パイプライン制御のところで，各ステージの実行に必要な時間がバランスしないと，性能が発揮 できないことを述べた．そして，各ステージは，実行時間がほぼ同じ（レジスタの読み書きはそれ ぞれ半分の時間でできるとしたが）として話を進めた． 実際のコンピュータでは，メモリは記憶容量の大きい DRAM（ダイナミック RAM）を使うの が普通である．ところが DRAM は，読み書きに時間がかかり，パイプラインステージに DRAM を使ったのでは，ステージの実行時間がバランスしない．そこで，読み書き時間の短い SRAM（ス タティック RAM）を使って，実行時間をバランスさせる．ところが，SRAM は記憶容量を大きく とれない． パイプラインステージでは SRAM を使わないと間に合わないし，SRAM では，プログラムや データを格納するのに十分な容量をとれない．この矛盾する要求を解決する方法はないだろうか？ それがキャッシュメモリの考え方である．具体的には，パイプラインステージには SRAM を使い， パイプラインステージの外に DRAM で構成した大容量メモリを置く．後者を主記憶（メインメモ リ）と呼ぼう．プログラムやデータは初めに主記憶に格納しておく．プログラムの実行に際しては， プログラムやデータの一部を SRAM にコピーして，パイプライン処理によりプログラムの実行を する．SRAM に入ってないプログラム（やデータ）の部分の実行が必要になったら，プログラム の実行を一時中断して，必要な部分のプログラム（やデータ）を DRAM から SRAM にコピーす る．そして実行を継続する．このようにすることによって，プログラムの高速実行が期待できる． （実際にそうであることは，以降で述べる． ） ここでは，キャッシュメモリの各種構成法，それらの利点欠点を学ぶ． 1.2 容量と速度の両立 容量の大きいメモリ (DRAM, Dynamic RAM) は遅い．速いメモリ (SRAM, Static RAM) は容 量が小さい．(RAM は Random Access Memory の頭字．) その理由は， 容量 DRAM はトランジスタ 1 個（とコンデンサ 1 個）で 1 ビットのメモリが作れる1 のに対し， SRAM はトランジスタ 4 個で 1 ビットのメモリが構成される2 ．したがって，同じ面積に構 成できるメモリビット数は DRAM のほうが約 4 倍大きい． 速度 DRAM のコンデンサは，何もしないで放っておけば放電してしまい，記憶した情報が喪失 する．そのため，定期的にリフレッシュという操作を行って，記憶した情報の維持をする3 ． DRAM のアドレスは，2 段階に分けて与えるように回路が構成される． （詳細は，教科書の付 録 C を見てください． ）その制御に時間がかかり，その結果メモリアクセス時間が大きくなる． 1 コンデンサが記憶素子として働く．コンデンサに充電された状態と放電された状態を 1 と 0 に対応つける． 2 フリップフロップを構成する． 3 これが Dynamic RAM と呼ばれる理由．これに対しフリップフロップで構成される SRAM は，ほおって置いても記 憶が消失することはないからスタティックとよばれる． （もちろん，電気が供給されているという前提です． ） 1 そのため，DRAM は遅く，SRAM は速い．なお，最近は，SDRAM (Synchronous DRAM) や DDR SDRAM (Double Data Rate SDRAM) と呼ばれる DRAM が出てきており4 ，メモ リアクセス時間の改善がなされている． （詳細は付録 C や Wikipedia を参照してください） ということである．なお，このノートの 1.8 節に SRAM と DRAM のメモリセルの構造を書いて おきましたので，参考にしてください． また，値段も DRAM は安く，SRAM は高い．これらを，表にまとめておく． （）内は典型的な値 である． DRAM SRAM 容量 大きい (256M∼1G bit) 小さい (32∼64M bit) 速度 遅い (50∼70 ns) 速い (0.5∼5 ns) バイトあたりの値段 安い 高い 容量が大きくて速度の速いメモリを作りたい．この相矛盾する要求を実現する方法はないだろう か？正攻法でやったのでは，それは難しい．そういうメモリ IC を作ろうとしても，それはできな い． （論理的に矛盾しているから． ）それでは，見かけ上そのような動作をするメモリを構成するこ とはできないだろうか？ そこで登場するのが，20-80 法則である．つまり，プログラムの実行時間の 80%は，プログラム の 20%の部分で消費される，という法則である．局所性の法則ともいう．この法則は，プログラム の実行においては，空間的な局所性があることを示している． これはまた，今使われたデータが次に使われる確率が高いという時間的局所性につながる． このことを利用すると，次のようなメモリ構成法が発想される． （図 1 参照． ） 小さな容量の高速メモリと大きな容量の低速メモリを用意する．メモリを一定の大きさのブロッ クに区切っておく．プログラムを低速メモリに入れておく．今実行しようとする命令が属するブ ロックを高速メモリにコピーする．そして，高速メモリの下でプログラムを実行する．いまコピー したブロック以外のブロックに属す命令の実行が必要になったら，その命令の属するブロックを高 速メモリにコピーする．そして実行を続ける．これを続ける．もし，高速メモリがコピーされたブ ロックで一杯になっていたら，どれか適切なブロックを低速メモリに戻して，必要なブロックを高 速メモリにコピーする．このようにすれば，ブロックをコピーするというオーバーヘッドはあるけ れど，それを除けばあたかも高速メモリ上でプログラムが実行されているように見えるであろう． 20-80 法則を考えれば，すでにコピーされたブロックの中で実行が継続される確率が高い．そうす プロセッサ 小容量高速メモリ 大容量低速メモリ 図 1: 記憶階層の概念 4 さらに，DDR2 SDRAM, DDR3 SDRAM などが出ている． 2 プロセッサ 命令メモリ データメモリ 大容量メモリ(主記憶) 図 2: パイプライン構成における記憶階層 ると，ブロックをコピーするオーバーヘッドは相対的に小さくなる． （100 回メモリアクセスするう ち 98 回は高速メモリに入っているというくらいになる． ） これが，キャッシュメモリの発想である．キャッシュ(cache) とは隠すのに安全な場所という意味 であり，低速メモリの背後に隠された安全なメモリということである．このようなメモリシステム の構成をメモリの階層構成という． パイプライン構成との関係でいうと，命令メモリやデータメモリは，高速メモリでなければなら ない．一方で，大容量メモリも必要である．図 2 に構成概念図を示す．図 1 と対比しながら見てほ しい．パイプライン処理の話の中では，大容量メモリを省略して話をしてきたが，実際には図 2 の ように大容量メモリがある．これは通常，主記憶とよばれる． さて，現在のコンピュータシステムの記憶階層は，どうなっているだろうか？キャッシュメモリ は，１次キャッシュと２次キャッシュの２階層で構成されるのが普通である．それに主記憶，さら に，外部記憶（ハードディスク）の４階層構成が普通であろう． 教科書の図 5.3 に記憶階層の構造が示されている．横軸が容量，縦軸が速度と見ればよい． 以下の説明をする前に，用語について説明しておく． • ヒット：CPU がアクセスするデータあるいは命令がキャッシュにある場合ヒットという．キャッ シュが階層化されている場合はそれぞれの階層に対してヒットという言葉を使う．以下同様． • ミス：ヒットしなかった場合をミスという． • ヒット率：アクセスしたデータあるいは命令がヒットした割合をヒット率という． • ミス率：1 − ヒット率 である． • ヒット時間：キャッシュメモリへのアクセス時間である． • ミス・ペナルティ：ミスを起こした場合，下位の記憶階層からミスを起こした記憶階層にブ ロックをコピーするのに要する時間である． 3 1.3 キャッシュの基礎 ここまでは，概要を話したが，ここからはキャッシュを具体的に構成していく．そして，構成す る際の問題点などについても考えていく．すぐに問題になるのが，ブロックをコピーする場所をど う選択するか（キャッシュのどの位置にコピーするかという問題），である．なお，以下では，簡 単のため，キャッシュは１階層としておく． 1.3.1 ダイレクトマップ方式 簡単のためブロックの大きさを 1 語 4 バイトとしよう． （よくある大きさは 1 ブロック 8 語 32 バ イトである． ）また，キャッシュの大きさを 8 語 32 バイトとしよう． （よくあるキャッシュの大きさ は，32KB である． ）さらに，主記憶を 32 語 128 バイトとしよう． （よくある主記憶の大きさは 1GB である． ）ブロックをコピーの単位とする．ブロックを単位としてキャッシュと主記憶をアドレス付 けすると，キャッシュは 0 から 7 まで，メモリは 0 から 31 まで番号をつけることができる． もっとも簡単な割り当て方法は，主記憶の下位ビットの値（上の簡単な例では，下位 3 ビットの 値）と同じ番号のキャッシュ上のブロック番号に割り当てる方式である．これをダイレクトマップ 方式 (direct map) という．教科書の図 5.5 に概念図が示されている．この方式を実現するには，い くつか考慮すべき点がある．まず，明らかに，主記憶上の複数のブロックが同一キャッシュブロッ クに割り当てられるので，キャッシュ上のブロックに入っているデータは主記憶上のどのブロック が入っているのかという情報を持たなければならない．また，キャッシュ上のブロックは，有効な ブロックかどうかという情報も持たなければならない5 ．したがって，キャッシュメモリは，デー タを格納するメモリのほかに，タグフィールドとよばれるメモリと有効ビットと呼ばれるメモリを 持つ．それを図 3 に示す．但し，図 3 は，ブロックサイズ 4 バイト，キャッシュサイズ 4KB，メモ リサイズ 4GB とした図である6 ．図 3 からわかるように，タグフィールドには，アドレスの上位 ビットの値が入る．タグフィールドの内容と，インデックスを合わせて，主記憶のブロック番号が 特定できる． （もちろん，有効ビットが 1 のとき． ） キャッシュメモリのアクセス例を図 3 にしたがって説明する．しばらくは読み出しアクセスだけ を考える．書き込みアクセスには特有の問題があるので後で詳しく述べる．まず，アドレスのイン デックスフィールド（この例では，右から 2 つ目の 10 ビットのフィールド）の値をアドレスとし てキャッシュがアクセスされる．そのアドレスにある有効ビットが有効ならタグフィールドがアド レスのタグフィールドと比較される．それが一致すれば，今アクセスしようとしているデータは キャッシュにある．すなわち，ヒットである．そうでなければ，ミスである． 4 章でやった命令メモリやデータメモリをこのようなキャッシュメモリにすれば，クロックサイ クル時間を小さくすることができる．また，パイプライン構成でも命令メモリとデータメモリを キャッシュメモリにすることによりパイプラインステージの実行時間を短縮できる．じつは，パイ プライン構成では，ALU やレジスタの速度と見合うようにデータメモリや命令メモリを構成しな いとパイプラインの効果が発揮できない．だから，パイプライン構成では，キャッシュは必須なの である． 次に，ミスしたときどうすればよいか，という問題を考える．ミスしたときは，ブロックを入れ 替えなければならない．ダイレクトマップ方式では入れ替えるブロックは一意に決まる．動作と 5 このほかにも必要な情報があるが，簡単のためここでは省略する． 6 ここで，メモリサイズ 4GB と言ったが，これは論理空間の大きさ（32 ビットアドレス空間）である．物理メモリは これより小さいことが多いが，最近は 4GB の物理メモリを持つものも多い．また，最近のプロセッサは，32 ビットより 大きい論理アドレス空間を持つものが多い． 4 アドレス インデックス 20 10 2 120627 512 00 有効 1 データ 32 タグ 20 キャッシュメモリ キャッシュメモリ 0 1 512 1 1234567890 120627 1022 1023 = データ ヒット 図 3: キャッシュメモリの構成概要 しては，あたらしいブロックをキャッシュにコピーし，有効ビットおよびタグフィールドを適切に セットすればよい． （今は，読み出しアクセスだけを考えている． ） 教科書の 4 章でやったシングルサイクルの構成では，ミスが発生したら，キャッシュを入れ替え るように制御回路を構成しておけばよい．一方，パイプライン構成の時はどうするか？パイプライ ンをストールして入れ替えをする．まず，キャッシュミスの例外が発生し，制御が OS に移る．命 令メモリのミスが発生した場合，OS は以下の処理をする．なお，以下の手順では，ブロックは，1 語 4 バイトとし，メモリのアクセスは語単位としている． 1. ミスが発生したメモリアドレス (PC-4) を主記憶に送る． 2. 主記憶からデータを読み出す．読み出しには，通常，何クロックサイクルかかかる． 3. 読み出したデータを命令メモリに書く． （ダイレクトマップ方式の場合，書き込むブロックは 一意に決まる． ） 4. キャッシュの有効ビットやタグフィールドに適切なデータを書く7 ． 5. ミスを起こしたアドレスを PC にセットする．再開． ミスを起こした命令メモリアドレスが再度読み出されるが，今度は，ヒットする8 ．ブロックの大 7 このようなことができるように回路が作られている． 8 ミスを起こした時，パイプライン上を実行中の命令はどうなるか？という疑問が湧くだろう．これらは，ミス発生時に OS によって適切に保存され，再開時に適切な場所に戻される．どうやったら，そんなことができるか？興味を持ったら調 べてみよう． 5 きさが 1 語より大きい場合は，上の手順で，2 と 3 のステップを必要回数繰り返した後，4 へ進む． このノートの 1.3.2 節も参照のこと． データメモリについても基本的には同様の手順になる． さて，書き込みアクセスの場合はどうなるだろうか？ （キャッシュは主記憶のコピーだから）キャッ シュと主記憶のデータは同じものでないといけないという考え方がある．これを一貫性 (consistency) という．一貫性を維持するという考え方で書き込みを行うときは，キャッシュと主記憶双方にデー タを書き込む．この方式をライトスルー (write-through) 方式という．書き込み時にミスを起こし た場合は，まず，ブロックを主記憶からキャッシュへコピーする．その後で，キャッシュ，主記憶双 方に書き込みを行う．この方式は，主記憶にもアクセスするので，書き込み操作に時間がかかると いう欠点を持つ．これに対する解決策の１つは，ライトバッファ(write buffer) を用意することで ある．ライトバッファは主記憶に対する書き込み待ちのデータを一時蓄えておく場所である．プロ セッサは，キャッシュとライトバッファにデータを書きこんだら処理を継続できる．主記憶への書 き込みが完了するとライトバッファは解放される．ライトバッファが 1 語分しかない場合，主記憶 書き込み中に次の書き込みが発生したら，パイプラインはストールする．複数語のライトバッファ を用意することで，幾分性能を改善できる．なぜなら，書き込みが続いた場合，ライトバッファの 容量分だけはストールが避けられるからである．主記憶アクセス時間より短い時間間隔で書き込み が発生する場合は，いくらバッファを用意してもストールは避けられない． 一貫性を放棄すればライトバック方式 (write-back) という別の方法がある．これは，書き込みは キャッシュだけに行い，主記憶への書き換えは，該当するキャッシュブロックが置き換えられる時 に行うという方式である．この意味するところは，書き込みにより，キャッシュと主記憶の間に一 貫性がなくなるが，キャッシュミスを起こした時，キャッシュにあったブロックを主記憶に書き戻 して，主記憶を正しいデータに更新しようということである． 1.3.2 ブロックサイズが１語より大きい場合 ブロックサイズが 1 語より大きい場合の構成例が，教科書の図 5.9 に示されている．この例では， 1 ブロックが 16 語で構成され，キャッシュは 256 ブロックからなる．1 語ブロックの時とのちがい は，ミス時の動作が異なることである．動作を説明する． • 読み出しヒット：入れ替え動作はない． • 読み出しミス：ライトスルー方式の場合は，ブロックを置き換えればよい．ライトバック方 式の場合は，ブロック単位で入れ替える． （書き込みのあったキャッシュブロックをメモリに 書き戻して，新しいブロックをキャッシュに書き込む． ） • 書き込みヒット：書き込みを行う． （ライトスルーの場合は，キャッシュとメモリに書き込む． ライトバックの場合は，キャッシュに書き込む． ） • 書き込みミス： – ライトスルー方式：ブロックをキャッシュにコピーする．その後にキャッシュとメモリ に書き込みを行う． – ライトバック方式：ブロックの入れ替えを行う．その後キャッシュに書き込む． ミス率とブロックサイズの関係が教科書の図 5.8 に示されている．図から，ブロックの大きさに は最適点があることがわかる．なお，右側の数字は，キャッシュの大きさである． 6 1.4 1.4.1 キャッシュの性能の測定と改善 性能の測定 プログラムの実行時間は，CPU の実行サイクル数とメモリ待ち時間の和である．キャッシュメ モリのアクセス時間（ヒット時）は，CPU 実行サイクル時間に含める． CPU 時間=(CPU 実行クロック数+メモリ・ストール・クロック数) ×クロック・サイクル時間 メモリ・ストール・クロック数を正確に出すのは難しい．メモリ・ストール・クロック数が増え る主な原因はキャッシュミスである．メモリ・ストールは，読み出しミスと書き込みミスに伴って 発生する．読み出しミスによるストール・クロック数は， 読み出しストール・クロック数＝プログラムあたりの読み出し件数×読み出しミス率×読み出し ミス・ペナルティ で与えられる．一方，書き込みミスによるストール・クロック数は，書き込み方式ごとに検討を 要する． ライトバッファつきのライトスルー方式の場合はライトバッファが一杯の場合と書き込みミスを 起こした場合にストールが発生する9 ．よって，下記の式で与えられる． 書き込みストール・クロック数＝プログラムあたりの書き込み件数×書き込みミス率×書き込み ミス・ペナルティ ＋ ライトバッファ・ストール ライトバッファ・ストール時間は，具体的な式で与えるのは困難であり，シミュレーションなど で求めることになる．ライトバッファの設計が適切な場合，ライトバッファ・ストールはわずかで ある． ライトバック方式の場合は，書き込みミスに伴うペナルティが発生する．ただし，ライトスルー 方式の場合とはペナルティのコストが異なる．具体的には，ライトスルー方式では，書き込みミス をしたブロックをキャッシュにロードする時間がミスペナルティであり，その後そのブロックに書 き込むための時間は，ライトバッファストール時間として計算される．一方，ライトバック方式は， キャッシュが一杯の場合，LRU（後述）で選択したブロックを（それが更新されている場合）メイ ンメモリに書き戻し，書き込みミスを起こしたブロックをキャッシュにロードする時間がミスペナ ルティとなる． ライトスルー方式の場合，ライトバッファストールが無視できる環境では，読み出しミスと書き 込みミスのペナルティは同じであるので次式が得られる． メモリ・ストール・クロック数=プログラム当たりのメモリアクセス件数×ミス率×ミス・ペナ ルティ キャッシュミスは，プログラムの振る舞いに大きく依存するので，テストベンチマークなどを用 いて，シミュレーションによりミス率やメモリアクセス数などを測定して，上記の式に当てはめる ことになる． 教科書の例題を１つやってみよう． （キャッシュの性能の計算） 9 ライトバッファがない場合は，書き込みの度にストールが発生する．つまり，書き込みストール・クロック数の式のラ イトバッファ・ストールの項の値が大きくなる． 7 もう一つ，第 3 版に出ていた例題（クロック周波数を挙げたときのキャッシュの性能）をやって みる．まず，例題を示す． [例題] キャッシュ性能の計算の例題において，クロック周波数を 2 倍にすることによって，コン ピュータの性能を向上させたとする．主記憶の速度は変わらないので，キャッシュミスを処理する 絶対時間はもとのままとする．クロック周波数を挙げたコンピュータの速度はどのくらい速くなる か．ただし，ミス率は上記の例題と同じとする． [解答例] 前の例題におけるクロックサイクル時間を Tclock とする．前の例題では，実行時間は A A = 5.44I × Tclock だった．この例題マシンでは，B = 8.88I × Tclock × 12 となる．よって，B = 1.23 となる． （導出は授業でやります． ） つまり，クロックを 2 倍にしても，速度は 1.23 倍の向上にとどまる，ということである．キャッ シュミスの影響が相対的に大きくなる． （当たり前ではあるが． ． ． ） 上の例題からわかるように，マシンの高速化につれて，キャッシュミスのペナルティの比重が増 大する．すなわち，主記憶のメモリの速度の向上率と CPU の速度の向上率は同じではなく，CPU の速度の向上率のほうが大きいので，ミスペナルティのクロックサイクル数が増加する． また，CPI を改善することも，ミスペナルティの比重を大きくすることにつながる． （ここで， CPI は clock per instruction の意味で，命令あたりのクロック数，すなわち，１命令実行するのに 必要な平均クロック数のことである． ）たとえば，1 番目の例題で，CPI を 1 として計算するとど うなるか？ したがって，CPI の改善やクロックサイクル時間の短縮を行う場合は，キャッシュの性能がシス テム性能に大きな影響を及ぼすことになる． （すなわち，ミス率を小さくすることが重要となる． ） ただし，キャッシュ容量を大きくすればよいかというと，必ずしもそうではない．確かに，ミス 率は下がるだろうが，キャッシュアクセス時間が長くなるので，クロックサイクル時間を短くする ことが難しくなるからである． このノートの 1.3.1 節で，キャッシュの構成方式として，ダイレクトマップ方式を示したが，キャッ シュミス率という観点からはこの方式は必ずしも柔軟性が高いとはいえない．以下では，キャッシュ に関していくつかの構成方式を述べる． 1.5 セットアソシアティブ方式 ダイレクトマップ方式は，メモリブロックのキャッシュ上の割り当て先 (ブロック) が一意に決 まっていた．このことは，回路を作る上で構成が簡単であるというメリットはあるが，割り当て先 が一意という意味で柔軟性に欠ける．割り当て先が複数あれば，柔軟性が増し，キャッシュミスの 低減が期待できる．究極の割り当て法は，キャッシュ上空いているところならどこに割り当てても よいという方法である．この方法をフルアソシアティブ方式 (fully associative) という．この方法 は柔軟性が非常に高いので，理想的な方法である．しかしながら，空いているブロックをどのよう に見つければよいか，あるいは，どのように管理すればよいか，という問題がついて回る．これは 難しい問題で，現段階では効率の良い方法は見つかっていない．そのため，フルアソシアティブ方 式は現在のところ実現されてはいない． そこで，ダイレクトマップ方式とフルアソシアティブ方式の中間の方式が考えられる．いわゆる いいとこどり方式である．これをセットアソシアティブ方式 (set associative) という． 8 1.5.1 セットアソシアティブ方式 キャッシュ上のメモリブロックをグループ化する．主記憶上のブロックは，キャッシュ上の一つ のグループに割り当てられる．グループ内では，どのブロックに割り当ててもよい．これが，セッ トアソシアティブ方式である．グループ内のブロック数が n である場合，n ウェイセットアソシア ティブキャッシュという．教科書の図 5.14 を参照．セットアソシアティブの名前は，グループをブ ロックの集合（英語でセット）と考えて，グループ内はフルアソシアティブで割り当てるというと ころからきている． セットアソシアティブキャッシュでは，セット内では任意の（キャッシュ）ブロックに割り当て ることができるので，その分，割り当てに柔軟性がある．すなわち，キャッシュミスの低減が期待 できる． そうすると，問題は，一つのセットに割り当てるメモリブロックをどう決めるかである．図 4 が 一例である．4-way セットアソシアティブ構成であり，1 ブロックは 4 バイトで構成されいる．イ ンデックスが同じグループが一つのセットである．ブロックごとにデータのほかに有効ビットとタ グフィールドがある．アドレスが与えられると，インデックスのフィールを用いてセットがアクセ スされる．セット内の各タグフィールドが読みだされ，アドレスの上位ビット（この例では上位 22 ビット）と比較される．一致するものがあれば，さらに有効ビットがチェックされ，ヒットした か否かがわかる．ヒットの場合，マルチプレクサを通じて有効なデータが出力される． （ヒットし なかった場合は，ミス例外が発生する． ）なお，図 4 において，4:1 マルチプレクサの制御入力は， ヒットしたブロックのデータが選択出力されるように構成されているものとする． 図からわかるように，主記憶のブロックとセットの対応は，インデックスフィールドの値で決ま る．図の例では，インデックス 71 のセットは，まだ一杯ではないので，インデックス 71 を持つ新 たなブロックがアクセスされた場合は，キャッシュミスを起こして，有効ビットが 0 のブロックに コピーが行われる．複数の空きがある場合は，どれかを適当に選んで，そこにコピーする．それで は，一杯の場合はどうなるであろうか？ アクセスしたセットが一杯だった場合，ブロックの入れ替えを行わなければならない．さて，ど のブロックを追い出したらよいものか？最近アクセスされなかったブロックは，これからもアク セスされることは少ないだろうという考えがある．この考えに従って，最近もっとも使われなかっ たブロックを追い出すというアルゴリズム —LRU(Least Recently Used) という— が提案されて いる．このアルゴリズムの実現は，2 ウェイセットアソシアティブの場合は簡単である．それは， フリップフロップ (FF) で実現できるからである．具体的には，セットごとに FF を用意しておく． セット内には 2 つのブロックしかないので，一方のブロックがアクセスされたら FF をリセットし， 他方のブロックがアクセスされたら FF をセットする．このようにしておけば，最近もっともアク セスされなかったブロックは，FF の値に対応しないほうのブロックである． ウェイ数が大きくなると LRU を実現するのは難しい．4 ウェイのときどう実現したらよいか考 えてみてください． （ハードウェアで実現すること，高速に判断できないといけない，等を考える と，実現が難しい． ）このような場合は，ランダムに選択するという方法がよく採用される． 1.6 キャッシュの動作例 キャッシュの動作を実例で見てみよう．教科書の p.445 の例題は，各自で読んでもらうことにし て，ここでは，この例題にならって 8 ブロック構成のキャッシュを仮定して，その上で，次の実際 9 アドレス 22 0627 インデッ 有効 タグ データ 32 1 22 クス 有効 タグ データ 32 1 22 キャッシュ メモリ 8 2 71 00 有効 タグ データ 32 1 22 有効 タグ データ 32 1 22 0 1 71 1 0627 10345678 1 0727 12045678 0 0637 12305678 1 1627 12340678 255 = = = = ヒット 4:1 MUX データ 図 4: 4-way セットアソシアティブキャッシュの構成例 のプログラム（階乗計算）を実行してみよう．ただし，キャッシュは命令キャッシュとし，データ キャッシュはここでは考えないものとする．また，プログラムは n=2 として実行する． adr 0x0100 blk 0 0x0104 0x0108 1 2 sw sw 0x010C 0x0110 0x0114 3 4 5 slt $t0, $a0, 1 beq $t0, $zero, L1 add $v0, $zero, 1 0x0118 0x011C 6 7 add $sp, $sp, 8 jr $ra 0x0120 0x0124 0x0128 8 9 10 0x012C 0x0130 11 12 lw $ra, 4($sp) add $sp, $sp, 8 0x0134 0x0138 13 14 mul $v0, $a0, $v0 jr $ra fact: sub $sp, $sp, 8 L1: $ra, 4($sp) $a0, 0($sp) sub $a0, $a0, 1 jal fact lw $a0, 0($sp) 答えは，1.9 節にあります． 10 1.7 キャッシュに関する補足事項 キャッシュのハードウェア量の算出 教科書の p.450 の例題を見てみましょう．キャッシュを構成するのに必要なハードウェア量がわ かります． マルチレベルキャッシュ マルチレベルキャッシュは，ほとんどのプロセッサで採用されている．その理由は，１次キャッ シュとメインメモリの速度差が開きすぎた現在では，２次キャッシュを用いないと，ミスペナルティ が大きくなり，性能低下をきたすからである．そのことを，教科書の p.451 の例題で見てみよう． 連想記憶とは 今までに話したセットアソシアティブキャッシュやフルアソシアティブキャッシュのアソシアティ ブという言葉は連想という意味である．連想記憶 (associative memory) とは，アドレスではなく て内容でアクセスできるメモリという意味である．つまり，キーワードとそれに対応するデータが メモリに記憶されていて，キーワードを与えるとデータが出力されるメモリである．ここで述べた キャッシュでは，タグがキーワードに相当する． 1.8 補足：メモリの構成 メモリセルの基本部分の構成は図 5 のようになる． SRAMのメモリセル構成 DRAMのメモリセル構成 図 5: メモリセルの中心部分の構成：SRAM と DRAM 図 5 を見ると解るように、SRAM は 1 つのセルを構成するのに 4 つ (またはそれ以上) のトラン ジスタが必要となり、配線数も多いため、「消費電力が大きい」「実装密度を上げにくい (大容量化 が難しい)」といった問題はあるが、トランジスタによるスイッチ回路で全てを構成するため高速 動作が可能である。したがって、パソコンのメモリモジュールのように大容量を要求されるものに は不向きであるが、プログラムを ROM に持ち、RAM を作業メモリとして使用するような一般の 電子機器や、高速性が要求されるキャッシュメモリとして利用される。 また SRAM は、 「リード (読み出し)」 「ライト (書き込み)」のやりとりが非常にシンプルである。 書き込むデータ (1or0) をデータ線に出力し、ワード線に電圧 (Vcc) を与えてやると、トランジス タ (Tr1) のソースとドレインが導通し、データが図の P 点に出力される。P 点に出力されたデー 11 タはフリップフロップ回路により保持される。リード時はデータ線を開放して (電位が無い状態) 再びワード線に電圧を与えてやると、Tr1 のソースとドレインが導通し、保持されている P 点の データがデータ線に出力される。 （MYCOM ジャーナルより) 上記の説明では，フリップフロップの片方の出力しか使用しないように見えるが，実際には，両 方の出力を利用する． （一方は 1，他方は 0 が出力される． ）両方を使うことによって動作の確実性 が増す． 1.9 例題の答え （間違いがあったら指摘してください． ） 主記憶のブロックのアクセス順は，0,1,2,3,4,8,9,0,1,2,3,4,8,9,0,1,2,3,4,5,6,7,10,11,12,13,14,10,11,12,13,14 となる． （32 ステップ） まず，これが正しいことを確認してください． １）8 ブロック構成のフルアソシアティブキャッシュの動作 以下の表示は () 内にキャッシュにあるブロックを左から右に向かって古い順に示し，m/h はミス ／ヒットを表す．(アクセス終了後のキャッシュの状態を示す．) 実行ステップ毎に結果を示す．置 き換えは LRU． 12 主記憶 キャッシュ ヒット ブロック ブロック /ミス 0 () (0) m 1 2 3 (0,1) (0,1,2) (0,1,2,3) m m m 4 8 (0,1,2,3,4) (0,1,2,3,4,8) m m 9 0 1 (0,1,2,3,4,8,9) (1,2,3,4,8,9,0) (2,3,4,8,9,0,1) m h h 2 3 (3,4,8,9,0,1,2) (4,8,9,0,1,2,3) h h 備考 初期状態 0 がもっとも最近アクセスされたブロック 以下 19 番目のブロックアクセスまでヒットが続く． 5 6 (8,9,0,1,2,3,4,5) (9,0,1,2,3,4,5,6) m m 7 10 11 (0,1,2,3,4,5,6,7) (1,2,3,4,5,6,7,10) (2,3,4,5,6,7,10,11) m m m 12 13 14 (3,4,5,6,7,10,11,12) (4,5,6,7,10,11,12,13) (5,6,7,10,11,12,13,14) m m m 10 11 (5,6,7,11,12,13,14,10) (5,6,7,12,13,14,10,11) h h 12 13 14 (5,6,7,13,14,10,11,12) (5,6,7,14,10,11,12,13) (5,6,7,10,11,12,13,14) h h h キャッシュのブロックが一杯になった LRU でブロック 8 が置き換え ブロック 10 ヒット ミスが 15 回，ヒットが 17 回． 13 ２）2 ウエイセットアソシアティブキャッシュの動作 以下では ((),(),(),()) でキャッシュの内容を表示する．内側の括弧はセット内のブロックをあら わす．セット内では現在あるブロックを古い順に示す．m/h はミス／ヒットを表す．実行ステップ 毎に結果を示す． 主記憶 キャッシュ ヒット ブロック ブロック /ミス 0 ((),(),(),()) ((0),(),(),()) m 1 2 ((0),(1),(),()) ((0),(1),(2),()) m m 3 4 8 ((0),(1),(2),(3)) ((0,4),(1),(2),(3)) ((4,8),(1),(2),(3)) m m m 9 0 ((4,8),(1,9),(2),(3)) ((8,0),(1,9),(2),(3)) m m 1 2 3 ((8,0),(9,1),(2),(3)) ((8,0),(9,1),(2),(3)) ((8,0),(9,1),(2),(3)) h h h 4 8 ((0,4),(9,1),(2),(3)) ((4,8),(9,1),(2),(3)) m m 9 0 1 ((4,8),(1,9),(2),(3)) ((8,0),(1,9),(2),(3)) ((8,0),(9,1),(2),(3)) h m h 2 3 4 ((8,0),(9,1),(2),(3)) ((8,0),(9,1),(2),(3)) ((0,4),(9,1),(2),(3)) h h m 5 6 ((0,4),(1,5),(2),(3)) ((0,4),(1,5),(2,6),(3)) m m 7 10 11 ((0,4),(1,5),(2,6),(3,7)) ((0,4),(1,5),(6,10),(3,7)) ((0,4),(1,5),(6,10),(7,11)) m m m 12 13 ((4,12),(1,5),(6,10),(7,11)) ((4,12),(5,13),(6,10),(7,11)) m m 14 10 11 ((4,12),(5,13),(10,14),(7,11)) ((4,12),(5,13),(14,10),(7,11)) ((4,12),(5,13),(14,10),(7,11)) m h h 12 13 ((4,12),(5,13),(14,10),(7,11)) ((4,12),(5,13),(14,10),(7,11)) h h 14 ((4,12),(5,13),(14,10),(7,11)) h ミスが 20 回，ヒットが 12 回． 14 備考 初期状態 初めてヒット ３）ダイレクトマップキャッシュの動作 (,,,,,,,) でダイレクトマップのキャッシュブロックを表す．m/h はミスとヒットをあらわす． 主記憶 キャッシュ ヒット ブロック ブロック /ミス 0 (,,,,,,,) (0,,,,,,,) m 1 2 3 (0,1,,,,,,) (0,1,2,,,,,) (0,1,2,3,,,,) m m m 4 8 (0,1,2,3,4,,,) (8,1,2,3,4,,,) m m 9 0 1 (8,9,2,3,4,,,) (0,9,2,3,4,,,) (0,1,2,3,4,,,) m m m 2 3 (0,1,2,3,4,,,) (0,1,2,3,4,,,) h h 4 8 9 (0,1,2,3,4,,,) (8,1,2,3,4,,,) (8,9,2,3,4,,,) h m m 0 1 (0,9,2,3,4,,,) (0,1,2,3,4,,,) m m 2 3 4 (0,1,2,3,4,,,) (0,1,2,3,4,,,) (0,1,2,3,4,,,) h h h 5 6 (0,1,2,3,4,5,,) (0,1,2,3,4,5,6,) m m 7 10 11 (0,1,2,3,4,5,6,7) (0,1,10,3,4,5,6,7) (0,1,10,11,4,5,6,7) m m m 12 13 (0,1,10,11,12,5,6,7) (0,1,10,11,12,13,6,7) m m 14 10 11 (0,1,10,11,12,13,14,7) (0,1,10,11,12,13,14,7) (0,1,10,11,12,13,14,7) m h h 12 13 (0,1,10,11,12,13,14,7) (0,1,10,11,12,13,14,7) h h 14 (0,1,10,11,12,13,14,7) h 備考 初期状態 となる．ミスが 21 回．ヒットが 11 回． 15 初めてヒット 仮想記憶 2 2.1 ここで学ぶこと プロセッサがアクセス可能なアドレス空間10 と実装されている物理メモリの大きさには，ギャッ プがあるのが普通である．たとえば，よく使われている最近のプロセッサは 36 ビットのアドレス を指定できる．これは，64GB のアドレス空間である．それに対して，実際に実装されているメモ リは 4GB とか 8GB といったところである．そのような状況で，たとえば 32GB の大きさのプロ グラム11 を実行したいとき，どんなことをしなければならないだろうか？プロセッサは，64GB の アドレス空間を持つから，このプログラムの実行は可能である．しかし，このプログラム（全体） を主記憶上にロードすることはできない．プログラム全体が主記憶上にないと実行できないような 制約があると，8GB の主記憶のコンピュータでは，このプログラムは実行できない．また，別の 問題として，マルチタスク12 環境下では，複数のプログラムが時分割13 で実行される．このような 場合，主記憶を複数のタスク間で共有しなければならないが，どのようにすれば共有することがで きるか？こういった問題に対する一つの解が仮想記憶方式である． ここでは，仮想記憶方式の概念，構成方法，構成上の問題の解法などについて学ぶ． 2.2 仮想記憶とは 仮想記憶 (virtual memory) とは，主記憶と２次記憶との間のキャッシュ技法ということができ る．その目的は，１）複数プログラム間でメモリを効率よく共有すること，２）物理的な主記憶容 量を超える大きさのプログラムの実行を可能にすること，である． １つのプログラムをコンパイルすると，コンパイラは 0 番地から始まるアドレス空間にプログラ ムの実行コード（機械語）を生成する．このアドレス空間を仮想アドレス空間という．このアドレ ス空間は論理的なものであり，実体がないので仮想アドレス空間という． 一方，主記憶は物理的なメモリ素子で構成されており，このメモリ装置は，0 番地からアドレス がつけられている．たとえば，8GB の主記憶の場合，0 番地から 8G 番地までメモリの実体がある． このようにメモリ装置の（実体がある部分の）アドレス空間を物理アドレス空間という14 ． 上記のコンパイルされたプログラムを実行することを考えよう．プログラムは，2 次記憶に記憶 されているものとする．そうすると，2 次記憶からプログラムを主記憶にロードして，プログラム を実行しなければならない．ここで，検討すべき問題が発生する．それは，１）主記憶のどこにプ ログラムをロードするのか，２）プログラムサイズが主記憶の容量より大きい場合どうなるのか， ３）今の機械は複数のプログラム（たとえば，OS とユーザプログラム）が同時に動いているが， その場合，それらのプログラムが物理アドレス空間をどのように使うのか，といった問題である． これらの問題を解決するのが仮想記憶方式である．それは，一言で言えば，仮想アドレスと物 理アドレスの間の対応表を動的に管理する方式である．まず，アドレス空間 (仮想，物理とも）を ページと呼ばれる単位に分割しておく．ページのサイズは両者で等しい．ページはキャッシュメモ 10 メモリ空間とも言う．プロセッサが指定可能なメモリ番地の全体である． 11 配列を使うプログラムを書くと，このくらいの規模のプログラムにはすぐになってしまう． 12 複数のプログラムが走っている状況．プログラムの実行単位をタスクという．一つのウインドウが一つのタスクと考え ればよい． 13 複数のタスクが，自分に割り当てられた時間実行し，次々に実行するタスクを切り替えて処理をする手法．典型的な 割り当て時間は 10 ミリ秒．この結果，人の目には，複数のタスクが同時に走っているように見える． 14 物理メモリは必ずしも連続する番地に割り振られるとは限らない．例えば，8GB の物理メモリがある場合，4GB を 0 番地から始まる番地（メモリ空間の頭の 4GB）に，4GB を 0xF00000000 から始まる番地（36 ビットメモリ空間のお尻 の 8GB）に割り当てるという割り当て方もある．この場合，物理アドレス空間は 2 つに分かれる． 16 仮想アドレス 物理アドレス ページ0 ページ0 ページk ページm ページn 2次記憶：ハードディスク 図 6: 仮想アドレスと物理アドレスの対応 (概念図) リでいうところのブロックである．このページを単位として，仮想アドレス空間のページが物理ア ドレス空間のどのページに割り当てられているかを示す表を用意しておく．図 6 に概念図を示す． 図 6 の仮想アドレスの箱が対応表である．物理アドレスの箱は，物理メモリ空間を表す．対応表 は，仮想アドレスのページ k が物理メモリ空間のどこに格納されているかを示している．もちろ ん，主記憶にいまだ割り当てられてない（ロードされてない）ページも存在する．それは，2 次記 憶にある．図の網掛け部分がそれを表している．さらに，仮想アドレスを物理アドレスに変換する 高速なハードウェアを用意しておく．そうすると，プログラムの実行は，仮想アドレス空間のアド レスに基づいて行えばよい．すなわち，仮想アドレスが物理アドレスに（高速に）変換され，主記 憶（物理メモリ）から命令やデータが読み出される． （実際には，キャッシュメモリがついているか ら，キャッシュから読み出される．そのやり方は，すでに述べた通り． ） 2.3 仮想記憶の実現法 前節までで，おおまかな動作を理解していただけたかと思う．これから，詳細を説明していくが， その前に用語を定義しておく． ページが物理メモリ空間にロードされてない場合，そのページをアクセスするとページフォール トが発生したという．仮想アドレスから物理アドレスへの変換をアドレスマッピングあるいはアド レス変換という．ページには番号がついていて，仮想アドレス空間では仮想ページ番号，物理アド レス空間では物理ページ番号とよぶ．またページ内の位置を示すのにページ内オフセットという言 葉を使う． 図 7 に示すように，仮想アドレスは，仮想ページ番号とページ内オフセットに分割され，また， 物理アドレスは，物理ページ番号とページ内オフセットに分割される． アドレス変換は，図 7 に示されるように，仮想ページ番号が物理ページ番号に変換されるのであ り，ページ内オフセットは変換されない．このようにアドレス空間をページに分けかつアドレス変 換機構を導入することにより，物理メモリ空間よりずっと大きなアドレス空間を実現することが可 能になる．すなわち，物理メモリの大きさを超えるプログラムを実行することが可能になる15 ． さて，ページが主記憶上にない場合，すなわちページフォールトが発生した場合，はどうすれば よいであろうか．図 6 の仮想アドレス空間の網掛けしたページがアクセスされた場合である．こ 15 言うまでもなく，仮想アドレス空間を超える大きさのプログラムの実行はできない． 17 仮想アドレス 12 24 ページ内オフセット 仮想ページ番号 変換 20 12 物理ページ番号 ページ内オフセット 物理アドレス 図 7: 仮想アドレスと物理アドレスの対応（数値は一例） の場合，2 次記憶から該当するページを物理メモリの適切な場所にロードし，アドレス変換表を更 新しなければならない．図 6 の例だと，物理メモリに空きがあるから，そこにロードすればよい． 物理メモリが一杯の場合は，ページの置き換えが必要になる．2 次記憶から主記憶へのロードは， CPU クロックにして何百万クロックもかかる（ハードディスクへのアクセス時間は数十ミリ秒か かる）．このハンディキャップを考慮した仮想記憶の設計，すなわち，ページフォールトの発生が できる限り少なくなるような設計，が重要である．そのための要点は， • ページの大きさ．一般に大きいほうがよい．ただし，大きすぎても問題である．現在の典型 的サイズは，4KB∼16KB．今後は，32KB∼64KB． • ページの物理メモリへの配置方法． • ページフォールトの処理機構．ソフトかハードか． • 書き込みに対する処理．ライトスルーはだめ．ライトバック． である．以下で，これらについて検討していく． 2.4 2.4.1 アドレス変換の機構 ページの配置と検索 はじめに，変換速度や物理メモリの大きさを考慮しないで，変換の機構を述べる．図 8 にその 概念図が示されている．基本的考え方は仮想ページ番号の数に等しい大きさのページ表を用意する のである．ページ表は，仮想ページがどの物理ページに格納されているかを示す表である．この ページ表は主記憶に置く．ページ表のベースアドレスはページ表レジスタが持っている．したがっ て，その値に仮想ページ番号を加えてメインメモリをアクセスすれば物理ページ番号が得られる． ページ表には，そのページがメインメモリにあるかどうかを示す有効ビットがある．ページ表の 1 エントリの大きさは，物理ページ番号および有効ビットや後述のダーティビットなど種々の情報が 格納できる大きさで，現在の典型的な値は 4 バイトである．そうすると，図 8 の例の場合，ページ 表の大きさは，最大で 64MB に達する． ページ表は，タスクごとに用意する．すべてのタスクがフルサイズのページ表を必要とするわけ ではないが，マルチタスク環境では，ページ表の容量は，最悪の場合，膨大なものになる．ページ 表の管理方法については後述する． 18 仮想アドレス 12 24 ページ内オフセット 仮想ページ番号 ページ表レジスタ 有効 物理ページ番号 + ページ表 20 12 物理ページ番号 ページ内オフセット 0ならページフォールト 1なら物理ページ番号 物理アドレス 図 8: ページ表の導入 2.4.2 ページフォールト 有効ビットが 1 であれば，メインメモリ上に該当ページがある．そうでない場合は，2 次記憶か ら主記憶へ該当ページをコピーしなければならない．仮想ページが 2 次記憶のどの位置にあるか は，OS が管理している．したがって，ここでは，その位置はわかっているものとする．そして， ページ表の有効ビットが 0 のところはディスク上の位置情報が入っているものとしよう．そうす ると次に考える問題は，仮想ページを物理メモリのどのページに置けばよいかということである． 物理メモリに空きがある場合は，適当なところに置けばよい．物理メモリに空きがない場合は，ど れかのページを追い出して，空いた後にページをロードする．追い出すページの選択は LRU 法を 用いる．たとえば，物理メモリが 5 ページ分あって，10,12,9,7,11,10 という順でページを参照して 次にページ 8 を参照した場合，ページフォールトが発生する．一方，この時点での LRU ページは 12 である．よって，物理メモリ中のページ 12 をページ 8 で置き換える． LRU 法を厳密に実現しようとするとコストがかかりすぎる．そこで，簡易法が用いられる．そ の方法は，物理ページ毎に参照ビットを用意しておき，ページがアクセスされる毎に対応する参照 ビットをセットする．OS 側では一定時間ごとに全参照ビットをクリアする．ページフォールトが 発生したら，参照ビットの立ってない適当なページを置き換え対象とする．こうすることにより， 近似的な LRU が実現できる． 2.4.3 ページ表の大きさについて 一つのプロセス（タスクと同義）は，図 9 のようにアドレス空間を使う． （これは，命令セットの ところでもやった． ）図において，スタックの領域とヒープの領域は，動的に管理される．プログ ラムの実行には，現在使用している領域をカバーするページ表があればよい．逆に言えば，ページ 表の大きさは，動的に変化するので，その特徴を生かしたページ表の管理が可能，ということであ る．また，多くのプログラムでは，必要なページ表はそんなには大きくはない，ということも事実 である．このような特性を考慮したページ表の管理法を述べる． ページ表の大きさが動的に変化するということは，最初は，小さなページ表の領域を用意してお き，それを超えるページ表が必要になったら，そのときに追加の領域を確保するのが効率的であ る．その方法として，境界レジスタを利用する方法がある． 19 アドレス 上位 メモリ空間 スタック領域 下に伸びる ～ ～ 上に伸びる ～ ～ ヒープ領域 静的データ アドレス 下位 プログラム 図 9: メモリ空間の割り当て • 今仮に図 9 において，スタックの領域を使わない場合を考えよう．この場合，動的な部分は ヒープの領域だけである．仮想ページをアクセスするとき，境界レジスタと比較し，境界レ ジスタの値より大きかったら，一定量のページ表領域を追加確保し，境界レジスタの値を更 新する．このようにすれば，ページ表領域の使用量を適切に制限することができる． 実際の環境では，次のような管理を行う． • ページ表を 2 つに分割して用意する．一つは，アドレス低位の領域用に使用し，もう一つは， アドレス高位の領域用に使用する．それぞれの領域は，上記の手法で管理する． そのほかの方法としては，次のようなものがある． • ハッシング技法を使う． • マルチレベルのページ表を使う． • ページ表を仮想アドレス空間に置く． 2.4.4 書き込みはどうなるか 書き込みについては，ライトスルーはコストがかかりすぎる．ライトバック方式が採用される． ライトバック方式はコピーバック方式とも言われる． 2.5 アドレス変換の高速化：TLB ページ表が主記憶にあるということは，必要なデータを得るまでに 2 回の主記憶アクセスが必 要である． （ページ表をアクセスして物理メモリアドレスを得ること，および，物理メモリアドレ スで必要なデータをアクセスすること． ）ページ表をキャッシュのような構成にすれば，大概の場 合，主記憶アクセスは 1 回で済む．この特別なアドレス変換キャッシュをアドレス変換バッファ (Translation-Lookaside Buffer)TLB という．TLB を含めたアドレス変換機構は図 10 のようにな る（仮想アドレス 36 ビット，物理アドレス 32 ビット）．図 10 において TLB の有効ビットとペー ジ表の有効ビットは意味がちがう．ページ表の有効ビットはそのページがメインメモリ上にあるこ 20 仮想ページ番号 TLB 有効 タグ 物理ページ 1 1 1 0 1 ページ表 有効 物理ページ 物理メモリ ページ0 ページ0 ページm ページn 2次記憶：ハードディスク 図 10: アドレス変換バッファ(TLB) TLB 容量 表 1: TLB 諸元 16 ∼ 512 エントリ ブロックサイズ 4 ∼ 8 バイト ヒット時間 0.5 ∼ 1 クロックサイクル ミスペナルティ 10 ∼ 100 クロックサイクル ミス率 0.01 ∼ 1 % とを意味し，TLB の有効ビットは当該エントリの物理ページアドレスが有効であることを示して いる．TLB はページ表の物理メモリへの対応付けだけを記憶するキャッシュである．TLB のタグ フィールドには仮想ページ番号が入る．TLB はフルアソシアティブ方式をとる場合が多い．フル アソシアティブとは，TLB 全体が 1 つのセットであるセットアソシアティブ方式である．別の言 葉で言えば，TLB のエントリ全体のタグフィールドが 1 度で比較できる方式である． 動作を具体的に示すと，仮想アドレスがアクセスされるたびに，TLB の中で仮想ページを検索 する．そこでヒットすれば，物理ページ番号を使用してアドレスを生成し，対応する参照ビット （これは LRU のための情報を保持するビットである．2.4.2 節を見よ． ）をセットする．書き込みの 場合はダーティビットもセットする． TLB 検索がミスの場合，ページ表を読み出し，その有効ビットを見て単なる TLB ミスかページ フォールトかを調べる．単なる TLB ミスならページ表から該当ページの物理アドレス情報を TLB に持ってくる． （置き換えは LRU など． ）ページフォールトなら，2 次記憶から主記憶に該当ページ を持ってくる．そしてページ表，TBL も更新する． （置き換えは，LRU など． ）その後，その仮想 アドレスから実行を再開する． 表 1 に TLB の諸元を示す．表 1 で，容量が 16 くらいならフルアソシアティブ，512 にもなると セットアソシアティブ方式が採られる．ブロックサイズは TLB の置き換えの単位である． （なお， LRU はコストが高いのでランダム選択方式が多い． ） さて，実際のマシンでは，TLB で物理アドレスに変換したあと，主記憶を直接アクセスするの ではなく，キャッシュメモリをアクセスする．したがって，仮想記憶，TLB，キャッシュ，主記憶 は一体の構成となる．その例を見てみよう．図 11 にそれを示す．今までの知識を総合すれば，こ 21 仮想アドレス 35 12 11 仮想ページ番号 有効 ダーティ 0 ページ内オフセット 24 物理ページ番号 タグ TLB ヒット 12 TLB 20 タグ部分は連想メモリ 16 有効 タグ 物理ページ番号 ページ内オフセット 物理アドレス バイト 物理アドレスタグ キャッシュインデックス オフセット 14 2 データ キャッシュ キャッシュ ヒット 32 データ = 図 11: TLB，キャッシュの一体構成 の図を理解するのは容易である．図 11 は TLB にヒットし，キャッシュにヒットした場合（最短時 間アクセス）の流れを示している． 最短時間アクセスから外れた場合，すなわち，ミスが発生した場合，を含めたメモリアクセスの 処理をフローチャートの形で図 12 に示す．ライトバック方式をとっている場合，キャッシュの読 み出しと書き込みでミスをした後の処理で，キャッシュが一杯の場合は，ブロックの入れ替え処理 を行う．また，ライトスルー方式の場合，キャッシュへの書き込みが成功した後，主記憶への書き 込みを合わせて行う． TLB ミスやページフォールトが発生した場合，具体的にどういう処理をしなければならないか？ まず，TLB ヒットの場合は，主記憶中に該当仮想ページがある． （TLB ヒットして該当仮想ページ が主記憶中にない場合があるだろうか？これは，該当仮想ページが置き換えになったときは，TLB の当該エントリを無効にすることによって，回避することができる．したがって，TLB ヒットの 場合は，必ず主記憶中に該当する仮想ページがあるようにできる． ）したがって，TLB から得られ る物理アドレスを使ってメモリアクセスすればよい．次に，TLB ミスについて考える．図 12 で TLB ミス例外処理のことである．TLB ミスが起きた場合，主記憶にあるページ表を引く．その 有効ビットが立っていれば，TLB エントリに一連の情報をセットすればよい．そうでない場合は， ページフォールトであるから，該当ページを主記憶にロードし，主記憶のページ表の更新と TLB の更新を行う．これらは例外処理として行われ，処理終了後，制御が TLB ミスを起こしたプロセ スに戻る．TLB ミスを起こしたプロセスは，ミスを起こした番地から処理を再開する． メモリアクセス１つとってもこんなにいろんなことをやっているんだということと，最短時間 アクセスのパスは 100 回中 99 回通る16 から高速化ができるんだということをしっかり理解してほ 16 その根拠は，20-80 ルール，あるいは時間的，空間的局所性．20-80 というのは，いつも 20-80 ということではない． あるときは，10-90 かもしれないし，5-95 かもしれない． 22 仮想アドレス TLBアクセス no TLBミス 例外処理 Hit? yes 物理アドレス no Cache read Load block to cache no yes Hit? yes Write? no Write allowed? yes Cache write 書込保護 例外処理 Load block to cache 読出しデータ no yes Hit? 書込み， TLBのダーティビットセット 図 12: TLB, キャッシュアクセスフロー しい． 2.6 例外処理時の注意事項 仮想記憶の流れからは外れるが，ここで例外処理時の注意事項について述べておく． それは，マルチサイクル方式やパイプライン方式のところで示したように，MIPS では例外を起 こした番地を記憶しておくレジスタ EPC が 1 つしかないことである．このことは，例外処理中に 別の例外処理が起きると，EPC の上書きが起きるということを意味している．例外処理中に例外 処理が発生することはありうることなので，そのようなことが起きても正しく動作できるようにし ておく必要がある．そのためには，例外処理プログラムの中で必要な情報をスタック上に退避して おき，例外処理終了時にそれを戻して例外処理を終了するということをソフトウェア的に行う．そ して，退避を行っている間は，例外が発生してもそれを受け付けないようなハードウェア的な処置 が必要である．そのためには例外マスクフラグを用意する．このフラグがオフの時，例外は受け付 けられると同時にこのフラグがオンになる．これはハードウェアで行う．そして，退避が終了した らこのフラグをオフにする．これはソフトウェアで行う．また，例外処理の終了時の回復処理期間 中も例外マスクフラグをオンにして，例外を受け付けないようにする必要がある． 2.7 仮想記憶による保護 ワークステーションでは，複数のプログラムが走っている．A さんのプログラム，B さんのプ ログラム，OS のプログラムなどなど．これらは厳密に排他的に動かなければならない．そうでな いと，他人のプログラムを破壊したり，書き換えたりしてしまうことになりかねない．それぞれの プログラムは，個別の仮想アドレス空間を持つ．いずれの仮想空間も 0 番地から始まる．したがっ て，物理アドレス空間への割付にあたっては，誰の仮想空間かを区別できるようにしておかない といけない．つまり，ページ表には，誰の仮想空間であるかという情報が含まれている．問題は， ページ表を誰が管理するか，ということである．これをユーザが書き換えることができてはめちゃ くちゃになってしまう． 23 プログラムとそのプログラムが動くのに必要な環境（プログラムカウンタの値や，レジスタの値 など）を合わせたものをプロセスという．実は，仮想空間はプロセス毎に与えられる．したがって， ページ表も，プロセス毎にある．OS はコンピュータを管理するいろいろな仕事をしている．大雑 把に言えば，その仕事の１つ１つがプロセスになっているといってよい．仮想空間を管理するプロ セスが OS にはある．ページ表はこのプロセスが管理する．ユーザのプロセスからページ表へのア クセスは禁止される．これによって，仮想空間の独立性が保たれ，記憶の保護ができるのである． 具体的にハードウェアでサポートするには，次のようにする．ユーザモードと OS のモードを区 別するフラグを用意しておく．OS のモードはいわゆる特権モードであり，システムのすべての資 源を操作することができる．ユーザは特権モードにはなれない．ユーザがシステム資源を操作した い場合は，OS に操作を依頼することになる（システムコール）．OS はユーザからの依頼を受け て，それが受理可能であれば，該当する処理を行い，制御をユーザに戻す． ページ表は，OS の管理下に置く．ページ表の操作は，OS のみに許される．ユーザモードで走行 中にページフォールトが発生すると，ページフォールト例外が発生し，これに伴ってシステムコー ルが行われ，OS がページ表の更新（とページの入れ替えやロードなど）を行う．その後，制御が ユーザに戻る．このようにすることによって，安全にページ表を管理することができる． プロセス間で情報を共有したいことがままある．これは複数のプロセスから共通にアクセスでき る空間を作るということである．その基本的な考え方は，共有したい仮想アドレス空間を同じ物理 アドレスに割り付ければよいのである．たとえば，プロセス A と B との間でメモリを共有したい 場合，各プロセスは他のプロセスの存在を知っていることが前提である．ユーザが自身のプログラ ムの中で複数のプロセスを生成するような場合は，これは可能である．プロセス A は自身のある 領域をプロセス B と共有したいと OS に要求する17 ．同様に，プロセス B も自身のある領域をプ ロセス A と共有したいと OS に要求する．OS は要求に基づき，それぞれの指定された領域を同じ 物理アドレスに割り付ける．これにより，プロセス間でデータのやり取りが可能になる18 ． 17 メモリ共有のための関数が OS 側で用意されている． 18 もちろん，各プロセスはどのような情報を共有するのか，データ構造を含めて把握していることが前提としてある． 24
© Copyright 2024 ExpyDoc
