OS学習メモ13 (MINIX本4.3-4.3.2章)
本自体は既に一回読んだんですが、復習を兼ねてこの記事を書くためにわざわざ”The MINIX book Operating system implementation”を図書館から借りてきました。持ち歩くのが重いったらないです(笑)。
洋書で読んでるので、もしかしたら英語の解釈違いによる致命的な間違いがある可能性もあるので…違和感感じたら各自改めて調べてください…。
4.3仮想記憶
昔は、利用可能なメモリよりも大きいプログラムを実行しなければならないときにプログラムをオーバレイという小さい断片に分けて実行させる方法を取っていた。オーバレイのスワップイン/アウトはシステムが行うにしても、オーバレイへの分割はプログラマの仕事で、これがまた結構面倒くさいからこれもコンピュータにやらせようってことになって仮想記憶が登場する。
仮想記憶の基本的な考え方は、プログラム、データ、スタックなどを合わせたサイズが物理メモリ量を超えることにある。つまりOSは、その時点でプログラムが使ってる部分だけメモリに残しておいて残りはディスクに置けばいいのである。
4.3.1 ページング
例えば MOV $t0 1000 というアセンブラ命令があったとすると、CPUはメモリアドレス1000の内容をt0にコピーする。この時プログラムが指定するアドレスは仮想アドレスで、これはMMU（Memory Management Unit）によって物理アドレスに変換される。仮想アドレス空間はページという単位に分割され、物理メモリ内における対応する単位はページフレームと呼ばれる（ページとページフレームは同じサイズであることが多い）
明らかに、ページ数>ページフレーム数であるから全てのページを物理メモリにマップすることは不可能なので(だから仮想メモリがあるわけなんだし)、実際のハードウェアでは、物理メモリ上にページが存在するか否かを示すpresent/absent bit(在/不在ビット)が各エントリにある。もしプログラムがマップされていないページを使おうとすると、CPUはOSに対して割り込みを引き起こす（この割り込みはページフォルトと呼ばれている）。これが発生すると、OSはあまり使用されていないページフレームを選び、その内容をディスクに書き込んで、空いたところに該当ページを読み込んで、変換テーブルを書き換えて、割り込みを起こした命令を再度実行する。
4.3.2 ページテーブル
仮想アドレスは「ページ番号を表す部分」と「オフセットを表す部分」に分割される。例えば16bitのアドレスの場合、上位4bitをページ番号に割り当てて(この時2^4=16個のページを持てる)、下位12bitは指定されたページ内のオフセット(0-4095)にしたりする。ページテーブルの目的は”ページ→ページフレーム”の変換であるが...2つの大きな問題がある。「1.ページテーブルが極端に大きくなること」と「2.変換が高速に行われなくてはいけないこと」である。
１、32ビットの仮想アドレス幅を持っているとすると、ページサイズが4KBとして約100万ページ(2^32/4KB)あることになる。これがもし64ビットなら4.5*10^15に…考えたくない。
２、メモリが参照される度に”仮想→物理”の変換がなされるという点に問題がある。典型的な命令は命令ワードとメモリオペランドを持っているので、一命令あたり1か2回,場合によってはそれ以上のページテーブル参照が必要になる。
大きなエントリを持って高速なページ変換を実現するというのは、コンピュータ設計の大きな制約条件になる。超高性能を要求されるマシンには深刻な問題だし、ローエンドなものに関してもコスト/性能比が非常に大事という意味では見逃すことが出来ない項目。
そこで、現実のコンピュータで使われているハードウェアの解決法の例↓
多階層ページテーブル
巨大なページテーブルを常にメモリ上に持たなければいけないという問題を抱えているので、多くのコンピュータではこの多階層ページテーブルを採用している。
(名前からある程度想像できると思うが)この方式では、アドレス32bitをいくつかのまとまりに分けてページテーブルを階層構造にすることで不要な部分をメモリに配置しないようにしている。具体的には、32を10/10/12の3つのまとまりに分け、最初の10bitはページテーブルのインデックス※として利用（第一層）,次の10bitは4MBのページテーブル(第二層)に、残る12bitをオフセットとして利用する。
※ちなみに第一層の1024個のエントリのうち、エントリ0はプログラムテキストのページテーブルを指しており、エントリ1023はスタックのページテーブルを指している。
これなら、100万ページのアドレス空間であるにも関わらず必要なのは4つの小さなページテーブルだけで済む（第一層のテーブル、それに対応する第二層のテーブル、それに加えて第二層エントリ0,1023)
これはあくまで2階層ページテーブルシステムであり、3階層,4階層…と拡張可能である。階層を追加すればその分柔軟にはなるが複雑になる
ページテーブルエントリの構成
エントリのサイズはコンピュータによって異なるが32ビットが通常サイズになっていて、ページフレーム番号,在/不在ビット,保護ビット,更新ビット,参照ビット,キャッシュ禁止を指示するビットの内容を含んでいる
・（最初の2つは説明を省略）
・protection bits(保護ビット)は、どんなアクセスが許されるかを示していて、単純な形であれば1ビットで”読み書き可能/読み出しのみ”を表している。
・modified (更新ビット)はページの使用履歴を示している（次に出てくる参照ビットも）。ページが読み込まれたらハードウェアが自動的に更新ビットをセットし、OSがこのページフレームを再利用する時に使われる。つまり、もしもページが更新されていたらそのページはディスクに書き戻さなければならないし、そうでなければディスク内のコピーとページが同一なので直ちに破棄できる。このビットはページの状態を表しているのでdirty bitと呼ばれることもある。
・referenced bit(参照ビット)は、そのページに参照した時にセットされ、ページフォルト発生時の追放ページを選ぶ根拠になる。
・最後のビットはページにキャッシュ禁止の指示をしている。これはデバイスレジスタ上にマップされたページに対して重要な意味を持っている。OSがI/Oをポーリングで待っている時（I/Oからのワードを読み続けている時）、CPU上のキャッシュが溢れたからといって古いキャッシュ内容のコピーを書き戻してはいけないので、このビットを使ってキャッシュをオフと指定する（...なので分離したI/O空間を持つメモリマップドI/Oを使っていないマシンではこのビットは不要）
ちょっと疲れたので半端ですが今日はここまで。
次回は4.3.3 TLB（Translation Lookaaside Buffers）の説明から。
余談:
先日研究室が決まりました。AI関係なのでこういったOSの知識って殆ど使わないんですけど、なんか個人的に好きなのでこの分野は趣味として続けようと思ってます。今のモチベーションとして、MINIX(バージョンは最新の3ではなく1)のソースを読んでみたいなって思っています。理論だけじゃなくて、実際にどう実装されているのかまで追ってみたいです。Linuxとかと違って教育用のOSなので1万行くらいですし、学生じゃないとそんなことしてる時間無さそうなので...春休みにでも。
