オペレーティングシステム ~ 仮想記憶 (1) ~ 山田浩史 hiroshiy @ cc.tuat.ac.jp 2015/06/19 OS の目的 裸のコンピュータを抽象化 (abstraction) し より使いやすく安全なコンピュータとして見せること OS はハードウェアを制御し アプリケーションの効率的な動作や容易な開発を支援する OS がないと メモリをアプリケーション自身が管理しなければならない 他のアプリケーションが使っているメモリを容易に壊してしまう OS- アプリケーション間は CPU のモードで隔離されている 本日の話題 Word Thunder Chrome bird アプリケーションオペレーティングシステム Database CPU メモリ I/O デバイス ( ディスク等 ) 1
AGENDA OS のメモリ管理法 素朴な実装 メモリ管理の要件 仮想記憶 ページ ページテーブル メモリも共有資源 複数のプロセスが同時にメモリを使用する プログラムを実行するにはメモリを使う Text 領域, データ領域, スタック領域 例 : ユーザ A は emacs と gcc, ユーザ B は firefox と emacs を動作させると アドレス 0 番地 1024 M ( 物理メモリ量 ) A s Thunderbird B s chrome B s itunes A s itunes OS が適切にメモリを管理する必要がある 各プロセスが自由にメモリを使ってはダメ 他のプロセスが使っている領域があるから メモリの取得 解放は OS にお願いする システムコールを発行する例 : Linux では brk() というシステムコールが用意されている 2
素朴なメモリ管理 空いているメモリを linked list として管理 空き領域の先頭に 空き領域の大きさ (byte) 次の領域へのポインタを格納しておく 8192 byte の空 4096 byte の空 1024 byte の空 8192 使用中 4096 使用中 1024 free memory メモリ割り当て要求が来ると, 空き領域からメモリを割り当てる どう割り当てるか? First-Fit Linked list を辿り, 最初に遭遇した n byte 以上の領域から割り当てる メモリ割り当てを最速に Best-Fit Linked list を辿り,n byte 以上の最小の領域から割り当てる メモリ割り当て後に残る領域を最小に Worst-Fit Linked list を辿り, 最大の領域から割り当てる メモリ割り当て後に残る領域を最大に 3
素朴なメモリ管理の問題点 (1/2) メモリの確保 解放が繰り返されると, 断片化 (fragmentation) が起こりやすい 断片化 : 小さい空き領域がたくさんできてしまうこと 何がまずい? 空き領域があるにもかかわらずメモリを確保できなくなってしまう 断片化したメモリ領域 この大きさの連続したメモリ領域を割り当てたい! 十分な空領域があるにもかかわらず, メモリ割当を行うことができない 素朴なメモリ管理の問題点 (2/2) プロセス間のメモリ保護が実現できない メモリ保護 : あるプロセスが他のプロセスのメモリを参照 変更できないようにすること read process 3 process 10 process 5 write メモリ保護がないと プログラムのミスで他のプロセスのメモリを破壊することがある 1 つのプロセスの不具合がシステム全体に伝播 悪意のあるユーザが他人のプロセスのメモリを覗ける ウェブブラウザに入力したパスワードやクレジットカード番号が見れる 4
仮想記憶 (OS によるメモリの抽象化 ) 仮想記憶 (Virtual memory) 各プロセスに専用の仮想アドレス空間 (Virtual address space) を提供する 各プロセスがメモリを占有しているように見える 0 番地 4Gbyte emacs (process 3) 0 番地 4Gbyte gcc (process 10) 0 番地 4Gbyte firefox (process 5) OS による物理メモリの仮想化 0 番地 512M 物理メモリ ( 物理メモリ量 ) 仮想アドレス ( 論理アドレス ) ある仮想アドレス空間内で有効なアドレス プログラム / プロセスが使うアドレス 普段 アドレス と言っているものは仮想アドレス コンパイラも仮想アドレスで object code を生成すればよい int main() { int x, *p; printf( %p\n, &x); 変数 x の仮想アドレス } *p = 1000; printf( %d\n, *p); return 0; 仮想アドレス 1000 番地の内容を参照 5
仮想アドレス空間 プロセスごとに用意された仮想的なアドレス空間 仮想アドレス空間の大きさはハードウェアと OS で決まる 互いに分離している プロセス A の 9000 番地とプロセス B の 9000 番地は別物 他のプロセス内の仮想アドレスを指定する方法はない プロセス A が参照できるメモリはプロセス A の仮想アドレスのみ プロセス間のメモリ保護が達成されている 0 番地 9000 4Gbyte 0 番地 9000 4Gbyte a F process A process B 物理アドレス 物理メモリを参照するためのアドレス 物理メモリの空間を物理アドレス空間と呼ぶ メモリ参照のためのハードウェアが使用 プロセスが使用するのは仮想アドレスのみ CPU 物理アドレス rd 30000 メモリ 6
仮想アドレスと物理アドレス 仮想アドレス空間を物理アドレス空間にマップする 各プロセスの仮想アドレスを物理アドレスに対応づける 仮想アドレスを物理アドレスに変換する必要がある 0 番地 emacs 4Gbyte 0 番地 firefox 4Gbyte OS による物理メモリの仮想化 0 番地 512M ( 物理メモリ量 ) アドレス変換の実現 CPU がメモリ参照を行うときは 仮想アドレスを物理アドレスに変換する 物理アドレスを使って物理メモリを参照 どーやって変換するの? CPU に内蔵された MMU というハードウェアが変換する なぜハードウェア? メモリ参照のたびに変換が必要 ソフトウェアでは遅すぎ 仮想アドレスと物理アドレスの対応付けは? OS が管理する OS が仮想アドレス空間ごとに仮想アドレスと物理アドレスの対応表を用意すればよい ( アドレス対応表 ) 仮想アドレス空間が違えば同じ仮想アドレスでも別の物理アドレスに対応している 7
MMU (Memory Management Unit) 日本語ではメモリ管理ユニット 仮想アドレスから物理アドレスの変換をする CPU 内部に組み込まれたハードウェア MMU MMU はアドレス対応表を見ながら, アドレス変換をする アドレス対応表 アドレス対応表は OS が用意する. 仮想アドレス空間ごとにひとつずつ用意する. アドレス対応表には, 仮想アドレスと物理アドレスの対応が記述されている. メモリ上に置いておく. アドレス対応表の実現 各仮想アドレスごとに対応する物理アドレスを記憶する必要がある これは可能? 100 プロセス,32 bit の仮想アドレス空間だとすると 仮想アドレス 1 つにつき 32 bit = 4 byte の情報 全体では,4 x 2 32 x 100 = 1600 GB の情報 非現実的 アドレス対応表だけでメモリを食いつぶしたら本末転倒 8
ページ (Page) ある連続したアドレスの範囲 典型的には 4 KB,8 KB の大きさ 経験的に決められている値 仮想アドレス空間をページ単位で区切る 仮想ページ 仮想アドレス空間内のページ 仮想ページ番号 0 から順につけられた仮想ページの番号 物理アドレス空間も同様 物理ページ, 物理ページ番号 物理ページのことをページフレームともいう 0x0000 0x1000 0x2000 0x9000 0xa000 0xb000 0xf000 ページテーブル (Page table) アドレス対応表のページバージョン 仮想ページ番号を物理ページ番号に対応づける ページテーブルを MMU にセットする 仮想アドレス空間ごとに用意する ページテーブルによるアドレス変換 仮想アドレス 0 仮想ページ 0 番が物理ページ 1 番に対応するとすると 0 仮想ページ 0 番の上から 3500 バイト目 1 物理アドレス 1 物理ページ 1 番の上から 3500 バイト目 仮想アドレス空間 物理アドレス空間 9
アドレス変換 仮想ページ番号をキーとして対応づける 例 : 32 bit 仮想アドレス空間,4 KB ページ 保護属性や Mapping 不在の取り扱いは次回解説する 20 bit 12 bit 仮想ページ番号 ページ内オフセット 物理ページ番号 保護属性その他の属性 0 Mapping 不在 ( 対応する物理ページなし ) 1 ページテーブルによるアドレス変換 対応付けを管理するためのテーブル < 仮想アドレス空間, 仮想アドレス番号 > をキーとして < 物理ページ番号, 属性 > を値とする表 OS によってメモリ内で管理されている 0 a 1 b 2 c 3 d 4 e 5 f 6 g 7 h 8 i 9 j 10 k 11 l 仮想アドレス空間 0 1 2 4 3 1 ページテーブル 物理アドレス空間 0 4 i j k l 8 12 e f g h 16 a b c d 10
ページテーブルの naive な実装 ページテーブルを naive に実装すると 100 個のプロセス,32 bit の仮想アドレス空間, 4 KB ページとすると ページテーブルの大きさ = 4 x 2 32 x 100 = 400 MB まだ大きすぎる 最近は 64 bit マシンが普通 ページテーブルの大きさを小さくする工夫が必要 多段のページテーブル 多段の表を使って実現する 仮想アドレス空間は結構スカスカ 4 GB のうち, 多くとも数 MB のみ使用 無駄なエントリを作成しない 必要なエントリのみを作成するという考え方 10 bit 10 bit a 1 a 2 12 bit offset a 1 a 2 11
まとめ OS によるメモリ管理法の基礎 素朴な実装 メモリ管理の要件 仮想記憶 ページ ページテーブル 12