Operating System Lecture No.8
Menu
Memory Management
コンピュータにはメモりが付き物である。このメモリは、どのように使われているのだろうか? メモリは、- malloc()
- free()
この状況は最悪、メモリの有効利用度(Memory Utilization)を50%程度にまでさげてしまうことが知られている。
問題8.1
malloc/ free を繰り返して、 fragmentation を実際に見てみる。Paging と アドレス変換
メモリは、OS下の複数のプロセス、ユーザから要求されている。この時に、個々のプロセスでは、あたかも自分一人がCPUとmemoryを専用している下のように見えた方が良い。これは仮想プロセッサと呼ばれるものであった。仮想プロセッサのメモリと実際のメモリを結びつけるには、アドレス変換(Address Translation)という技術を用いる。
この時に、flagmentation を防ぐために、実際のメモリ(Physical memory)は、前もって細分化されて、それの不連続(non-contiguous)な集合が、プロセスのメモリ(Virtual Memory)上での連続なメモリに対応するようになっている。
論理メモり空間(Logical Address) を物理メモり空間(Physical Address)に変換するメカニズムがアドレス変換である。これにより、メモリの割り当て、返却によるメモリ使用の細分化(fragmentation)を防ぐことができるだけでなく、複数のプロセスに対して、一つの物理メモリを、あたかも自分の固有のアドレス空間(Memory Spcace)であるかのように割り当てることができる。変換の単位は、frame (or page ) と呼ばれる。普通は、512byte - 4096byte 程度である。32bit CPU の場合、メモリのアドレスは、0x00000000 から0xffffffff の16進数で表すことができる。Page size ごとに frame 番号が振られていて、メモリのアドレスは、frame 番号と、frame の中のoffset で表される。例えば、Page size = 0x10000 ならば、0x80000500 のアドレスのframe番号は 0x8000 で、offset は 0x0500 となる。(0x80000500 = 0x8000 x page size + offset )
アドレス変換用のメモリ
ただし、この表も、64bit/32bit のメモリ空間に対しては、かなり大きくなってしまう。
Multi level page-table scheme
ただし、このテーブルが全部必要なわけではない。論理アドレス4Gのプロセスでも実際に使われるのは1M程度なのが普通である。そこで、この変換を2重3重にしてテーブルそのものを必要な部分だけ割り当てるようにする。また、この多重変換により、ページテーブル自身を仮想記憶上に置くことができるので、変換テーブルが大きくなっても実メモリを圧迫しなくなる。
問題8.2
GUI によるPage table のデモTLB
この変換はhardware にとっても重いので、このpage entry をcache するという技術が使われる。これを、TLB (Traslation lookup buffer) という。最近では、プロセスごとにTLBを持つTagged TLBという機能も使われている。
TLB が有効な間はアドレスを計算する必要はないので、TLB を入れ換える必要が出たときに(TLB miss)計算すれば良い。アドレス変換自体は、ハードウェアでサポートする必要はなく、ソフトウェアで行っても良い。
Segmentation
もし、CPUが16bitデータしか扱う能力がない時に、32bitアドレスを扱いたい時にはどうすればよいだろうか? 80x86 architecture などでは、segmentation という技術が使われている。これは、CPUから出力されるアドレスをCPUのアドレスレジスタだけでなく、Segment Register との組で表すものである。通常は単なるshift + 加算で処理が行われる。Paging を行う場合は、Segment RegisterにはPage Entry Table そのものを使っても良い。この場合は、Segment Register の数値にはさまざまな意味が与えられる。
仮想記憶 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 という。
問題8.3 Perfomance of Demand Paging
平均Page fault 処理時間
Page Replacement
page-replacement する時に、どのpageを書きだせば良いのだろうか? これを決めるアルゴリズムはいくつか知られている。- FIFO
- Optimal
- LRU (Counters, Stack)
Unix では、pageout あるいは、swapper と呼ばれるプロセスが、使われていないメモリをディスクに追い出している。
Page Replacement
Unix では、pageout あるいは、swapper と呼ばれるプロセスが、使われていないメモリをディスクに追い出している。
仮想記憶の制御
リアルタイム処理などでは、プログラムやデータが仮想記憶に追い出されてしまうと、致命的な処理時間の遅延が生じる。そこで、メモリの特定領域を実メモリに固定する方法が使われる。これは、メモリのpin down (ピン止め)と呼ばれる。 mlock/munlock によりpin downすることが可能である。
mlock, munlock - lock (unlock) physical pages in memory
#include <sys/types.h>
#include <sys/mman.h>
int
mlock(void *addr, size_t len);
int
munlock(void *addr, size_t len);
int
mprotect(void *addr, size_t len, int prot);
DESCRIPTION
The mprotect() system call changes the specified pages to have protection prot. Not all
implementations will guarantee protection on a page basis but Mac OS X's current implementa-
tion does.
問題8.3と mlock を組み合わせて見ると良い。
問題8.4 Perfomance of Demand Paging
mlock
mmap
仮想記憶はメモリとSwap領域を接続する。つまり、メモリとディスク上のファイルに対応があることになる。メモリをアクセスすることとファイルにアクセスすることは、ここでは同一になる。
Unixでは、mmap ( memory map )というシステムコールによって、 仮想記憶を制御することができる。この機構は、共有メモリを実現したり、ファイルとメモリの対応を実現したりすることができる。
kernel thread を使うのと process 間でメモリを共有するとでは、ほぼ同じ効果を得ることができる。
メモリに書き込みがない場合には、そのSwap領域は書きだす必要がない。mmap の場合は、書き込みを行った時にはメモリの内容をファイルに書きだすことになる。これをcopy-on-writeという。
特に zero 初期化した page はすべてのプロセスで同一のpageを使うことができる。書き込みが起きる時に初めて新しいページを用意する。
madvise
共有メモリのアクセスパターンをシステムに教える。
問題8.5 mmap によるコピー
mmap したファイルを write することにより、memory copy を減らすことができる。(今は、あまり使われない)
memory management の失敗
OS が管理するメモリは paging されているが、ユーザプロセスではそうはいかない。malloc/free ではミスが多い。pool を併用して、まとめて解放することが多い。
Garbage collection のある言語( Java, Perl, Ruby, Python) などでは、object の参照がなくなると自動的に free される。
GC でも fragmentation は起きる。GC で memory を OS に返すことは一般的には期待できない。
free 忘れ、あるいは link の放置により malloc/free では、もちろん、GC 環境下でも、放置される memory が出てしまう。
これを memory leak という。
逆に pointer が残っている部分を free あるいは GC が回収してしまう場合がある。これを dangling pointerという。
dangling pointer が stack を指していたりすると、security flow になる場合がある。
これらの memory management の失敗を調べるツールがある。
＊ valgrind
＊ VisualVM
＊ Xcode の Leaks