Operating System Lecture 12/18

次は、1/9 です。1/16 はお休みです。

問1

Pagesize 4096 byte の時、0x05543344 と 0xffeed013 に対応するアドレス変換テーブル(page entry table)の offset はいくつか? それぞれに対応するpage のアドレス変換テーブルの内容は、それぞれ0x1004と、0x5233 であった。それぞれのアドレスはどのように物理アドレスに変換されるか。

Segmentation

もし、CPUが16bitデータしか扱う能力がない時に、32bitアドレスを扱いたい時にはどうすればよいだろうか? 80x86 architecture などでは、segmentation という技術が使われている。これは、CPUから出力されるアドレスをCPUのアドレスレジスタだけでなく、Segment Register との組で表すものである。通常は単なるshift + 加算で処理が行われる。

Paging を行う場合は、Segment RegisterにはPage Entry Table そのものを使っても良い。この場合は、Segment Register の数値にはさまざまな意味が与えられる。

16it CPU 8086 では、Segment register は4つ(CS,DS,ES,SS)あり、アドレスを指示できるアドレスレジスタは6つである(BX,SI,DI,BP,SP,IP)。それぞれ16bit幅であり、Segment register は 4bit shiftされてアドレスレジスタに加算される。CS:IP で CS segemnet を使って、segment の中で IP のoffset を持つアドレスを指示することになる。

問2

8086 で表すことのできる最大のメモリ空間の大きさはいくつか? CS の内容は、0x1234, IP の内容は、0x0ffe であった。CS:IP で表される論理アドレスはいくつか?

(80186 という 8086 をちょっとだけ改良したCPU が、ワンダースワンというゲーム機で使われている)

問3

Segmentation に対して、一つのレジスタでアドレスを指示する方法をLinear address (線形アドレス)という。Paging をおこなうシステムにおいて、Segmentation と Linear address の優劣を比較して論ぜよ。(ヒント: アドレス空間が大きい時、小さい時を比較しよう。プログラムのしやすはどうか? システムプログラムはどちらが書きやすいか? 効率は? )

仮想記憶 Virtual Memory

メモリはいくらあっても足りないものだが、そのメモリはいつも使われているわけではない。一方、メモリと磁気ディスクのような大容量外部記憶を比較すると、常に外部記憶の方が安価である。そこで、paging されたメモリの一部を磁気ディスクに移すという方法が考えられる。これは、メモリ上にはないメモリ空間を作ることになる。これを仮想記憶(Virtual Memory)という。必要に応じて、ディスクの内容をメモリにコピーしたり、メモリの内容をディスクに書き出すことにより、仮想的にメモリを実現する。

もちろん、これをファイル操作などによりアプリケーションレベルで実現することもできる。これは、overlay などと呼ばれ、MSDOS 2.x, 3.x などでは良く使われていた。また、Intel 8086 のようなアドレス空間よりも大きなメモリを実装するシステムの場合、Window と呼ばれる部分に、他のメモリをマップすることも行われていた。これは、Extendene Memory Management (EMM) と呼ばれ、MSDOS のもっとも汚いAPIの一つとなった。このようなことをすると、OSで共通に実装するべき部分をアプリケーションで繰り返し実装する必要があり、しかも、この部分はかなり複雑なので、バグを呼びやすい。32bit CPUでは、将来的にこのようなWindowサポートが必要になる可能性はあるが、64bit CPUでは、その心配はないと思われる。64bit OSは既に実用レベルにあるが、広く広まるには、まだ数年は時間がかかると思われる。

ディスク上には、仮想メモリの内容をとって置く場所を確保する必要がある。これをSwap領域という。Swap 領域は、特別なDisk 領域を取る場合もあるし、普通のファイルとして実現する場合もある。ファイルシステム上の空き領域をSwapに用いる場合もある。さらに、Network を経由してSwapしてもよい。この場合も、NFS経由でSwapする方式と、直接、ネットワーク経由でディスクにアクセスする方法(remote disk)の2種類が存在する。

Page fault

技術的には、Page Entry Table に、そこが実際にメモリが割り当てられているかどうかを示すbitを付けるだけでよい。もし、CPUがメモリの割り当てられていないPage Entry Tableをアクセスすると、CPUは割り込みを発生する。これを page fault という。その割り込みにより、OS がそのPageを実際のメモリに割り当て、ディスクから内容を複写する。これをPage in, Swap in という。この時に、CPU は割り込みを起こした命令を正確に再実行する必要がある。メモリで使う確率が少ないものをディスクに追い出すことをSwap out またはPage outという。

実際のpage fault では、命令の再実行を正確に行う必要がある。これはCPUがサポートする必要がある。(意外に複雑なことになる)例えば、68000 は再実行を正確に行うことができず、68010という別なCPUを開発するはめになった。page fault の処理の最中に、もう一度 page fault が起こると、これは致命的なことになる。これを double page fault という。

Perfomance of Demand Paging

問4

平均page-falut処理時間が25m sec, memory access 100n sec の時に、page fault rate が、1% の時の effective access time を求めよ。page fault rate が、0.001% の時の effective access time を求めよ。性能低下を20%以下にするためには、page fault rate はいくらでなければならないか。

    effective access time = (1-p) x (memory access time) + p x (page fault time)

Page Replacement

page-replacement する時に、どのpageを書きだせば良いのだろうか? これを決めるアルゴリズムはいくつか知られている。

FIFO
Optimal
LRU (Counters, Stack)

Unix では、pageout あるいは、swapper と呼ばれるプロセスが、使われていないメモリをディスクに追い出している。

宿題

今日できなかった残りの問題を以下のサブジェクトでE-Mailで、kono@ie.u-ryukyu.ac.jp まで来週までに提出すること。

    Subject: Report on Operating System Lecture 12/18

課題

WWWに関する課題を1/9 までに行うこと。レポートはメールで

    Subject: Report Operating System Lecture 12/12

というように、課題を出した日付をサブジェクトに入れたメールで提出して下さい。