Operating System Lecture 6/25

## 先週の復習 -- 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 で
表される論理アドレスはいくつか?

### 問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)

## 仮想記憶の制御

仮想記憶はメモリとSwap領域を接続する。つまり、メモリとディスク上の
ファイルに対応があることになる。
メモリをアクセスすることと
ファイルにアクセスすることは、ここでは同一になる。

Unixでは、mmap ( memory map )というシステムコールによって、
仮想記憶を制御することができる。この機構は、共有メモリを
実現したり、ファイルとメモリの対応を実現したりすることが
できる。これらの機能は、Mach OS により最初に実現されて、
Sun OS そして、BSD/OS などにも使われるようになった。

メモリに書き込みがない場合には、そのSwap領域は
書きだす必要がない。mmap の場合は、
書き込みを行った時にはメモリ
の内容をファイルに書きだすことになる。
これをcopy-on-writeという。

リアルタイム処理などでは、プログラムやデータが仮想記憶に追い出されてし
まうと、致命的な処理時間の遅延が生じる。そこで、メモリの特定領域を実メ
モリに固定する方法が使われる。これは、メモリのpin down (ピン止め)と呼
ばれる。Sun OSやBSD/OS では、mlock/munlock によりpin downすることが可
能である。

### 問5 : 共有メモリを実現するmmap

### mmap_test.c は、共有
メモリを使用するmmapの例である。man mmap を参考にしながら、
このプログラムの動作を説明せよ。プログラムを変更し、リアルタ
イムで、共有された情報が変化することを確認せよ。

### 問6 : mmap によるコピー

### mmap_copy.c は、mmap を使ったファイルコピーである。
通常のread/write とどのように動作が異なるかを説明せよ。また、
実際に動作させて、cp との時間を測定してみよ。

time cp a b

などとすることにより、時間を測定することができる。一回目ののコピー
と二回目のコピーの時間差についても考察せよ。また、コピー先を削除
した場合はどうか? (時間差がはっきり分かるように、大きめのファイルを
コピーする必要がある。

### 問7 : mmap の改良

### このプログラムをfjに公開したところ、以下のようなコメントを
もらった。コメントにしたがってプログラムを改良し、時間を測定
して見よ。

In article <199809030356.MAA10105@srapc459.sra.co.jp>, Makoto Ishisone writes:
> mmap だけを使うのではなくて、mmap と write の組合せで使わないと意味が
> ないと思います。書き出しも mmap を使っちゃうと、せっかく read を使わな
> いことでメモリコピーを節約したのに、結局自分で memcpy することになっちゃ
> いますから。
>
> mmap+write だと、極端な話 /dev/null にコピーする場合、ほとんど何もしな
> いに等しいのですごく速くなります。それに意味があるかどうかは別として。
>
> 添削してみたバージョンをつけておきます。mmap+write に変えた以外に、
> ・open() の結果のチェックが間違っていたので修正
> ・mmap() の結果のチェックに MAP_FAILED を使うように修正
> ・exit() の値が逆 (正常終了なら 0、異常終了なら 1 にすべき)
> だったので修正
> ・その他エラーメッセージの表示方法を好みにあわせて変更
> してあります。FreeBSD で確かめましたが、BSD/OS だと修正が必要かも。
> -- ishisone@sra.co.jp
In article <snm4suo6psa.fsf@ludwig.spp.hpc.fujitsu.co.jp>, HASHIMOTO, Tsuyoshi writes:
> copy 元のファイルを mmap した領域を，単純に copy 先ファイルに write(2)
> （以下，この方法を (A) として言及）する方が，速いと思います．i.e.
> write(to,from_mmap,size);
> 正確なところは，profiler など（時刻表示 option つきの system call trace
> コマンドとかもあれば使えそう）で所要時間を測定したり，OS の system
> call の実装／仕様を確認しないと分かりませんが，BSD/OS は使っていないし，
> 実装も知らないので，他の UNIX のいくつかからの類推で考えて見た限りでは，
> > http://bw-www.ie.u-ryukyu.ac.jp/~kono/os/98-06-26/mmap_copy.c
> のコードは，例えば次のような原因で，read/write を使っている cp や前述
> の方法 (A) よりも，遅くなると思います．
>
> (1) mmap(2) + write(2) などの方が OS 内で disk I/O を最適化しやすそう．
> - OS からみて，memcpy(to_mmap,from_mmap,size) での pagefault のたび
> に通知されるより，system call で一度に教えてもらえる点でも有利かも．
>
> (2) ファイルの大きさによっては page out が起こりやすくなるかも知れない．
> - user 空間に copy 元と copy 先の２つの buffer があることになるので．
>
> (3) memcpy の CPU 時間消費で，実行優先度が下がってしまうかも知れない．
> - read(2) や write(2) の発行で sleep 状態になると実行優先度が上がる
> かも知れない．
>
> (4) msync(to_mmap,size) が disk に書き終るまで待つなら，書き込み処理は，
> write(2) + fsync(2) （ないし，O_SYNC 指定で open した場合の write(2)）
> 相当の動作をすると考えられるため，単なる write(2) より所要時間が大き
> くなるのでは．
> --
> 橋本　剛 (HASHIMOTO, Tsuyoshi)
> Replied: Thu, 03 Sep 1998 13:05:43 +0900
> Replied: Makoto Ishisone <ishisone@sra.co.jp>

## 宿題

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

Subject: Report on Operating System Lecture 6/25