10-vm1.ppt

オペレーティングシステム

~ 仮想記憶

(1) ~

山田 浩史 hiroshiy @ cc.tuat.ac.jp 2015/06/19

OS の目的

•  裸のコンピュータを

抽象化

(

abstraction

)し、

より

使いやすく安全な

コンピュータとして見せること

–  OS はハードウェアを制御し、アプリケーションの 効率的な動作や容易な開発を支援する –  OS がないと･･･ •  メモリをアプリケーション自身が管理しなければならない •  他のアプリケーションが使っているメモリを容易に壊してしまう –  OS-アプリケーション間は CPU のモードで隔離されている オペレーティングシステム アプリケーション

Word Chrome Thunder _bird Database

CPU メモリ I/O デバイス _{(ディスク等)} 本日の

AGENDA

•  OS のメモリ管理法

–  素朴な実装

–  メモリ管理の要件

–  仮想記憶

–  ページ

–  ページテーブル

メモリも共有資源

•  複数のプロセスが同時にメモリを使用する

–  プログラムを実行するにはメモリを使う •  Text 領域，データ領域，スタック領域 –  例: ユーザA は emacs と gcc， ユーザ B は firefox と emacs を動作させると･･･ 0 番地 1024 M (物理メモリ量) A’s Thunderbird B’s chrome A’s iTunes

アドレス B’s iTunes ⇒ OS が適切にメモリを管理する必要がある –  各プロセスが自由にメモリを使ってはダメ •  他のプロセスが使っている領域があるから –  メモリの取得･解放は OS にお願いする •  システムコールを発行する 例: Linux では brk() というシステムコールが用意されている

素朴なメモリ管理

•  空いているメモリを linked list として管理 –  空き領域の先頭に •  空き領域の大きさ(byte) •  次の領域へのポインタ を格納しておく 使用中 使用中 8192 4096 1024

8192 byte の空 4096 byte の空 1024 byte の空

free memory

•  メモリ割り当て要求が来ると，空き領域からメモリを

割り当てる

どう割り当てるか？

•  First-Fit

–  Linked list を辿り，最初に遭遇した n byte 以上の領域から割り当てる –  メモリ割り当てを最速に

•  Best-Fit

–  Linked list を辿り，n byte 以上の最小の 領域から割り当てる

–  メモリ割り当て後に残る領域を最小に

•  Worst-Fit

–  Linked list を辿り，最大の領域から割り当てる –  メモリ割り当て後に残る領域を最大に

素朴なメモリ管理の問題点

(1/2)

•  メモリの確保･解放が繰り返されると，

断片化

(fragmentation)が起こりやすい

–  断片化: 小さい空き領域がたくさんできてしまうこと

•  何がまずい?

–  空き領域があるにもかかわらずメモリを 確保できなくなってしまう 断片化したメモリ領域 この大きさの連続したメモリ領域を割り当てたい！ 十分な空領域があるにもかかわらず，メモリ割当を行うことができない

素朴なメモリ管理の問題点

(2/2)

•  プロセス間のメモリ保護が実現できない

–  メモリ保護: あるプロセスが他のプロセスのメモリを 参照･変更できないようにすること

•  メモリ保護がないと･･･

–  プログラムのミスで他のプロセスのメモリを 破壊することがある •  1 つのプロセスの不具合がシステム全体に伝播 –  悪意のあるユーザが他人のプロセスのメモリを覗ける •  ウェブブラウザに入力したパスワードやクレジットカード番号 が見れる read write process 5 process 3 process 10

仮想記憶

(OS によるメモリの抽象化)

•

 

仮想記憶(Virtual memory)

–  各プロセスに専用の仮想アドレス空間 (Virtual address space) を提供する

–  各プロセスがメモリを占有しているように見える emacs (process 3) 0番地 4Gbyte firefox (process 5) 0番地 4Gbyte gcc (process 10) 0番地 4Gbyte OS による物理メモリの仮想化 物理メモリ 0 番地 512M (物理メモリ量)

仮想アドレス

(論理アドレス)

•  ある仮想アドレス空間内で有効なアドレス

•  プログラム/プロセスが使うアドレス

–  普段「アドレス」と言っているものは仮想アドレス –  コンパイラも仮想アドレスで object code を 生成すればよい int main() { int x, *p; printf(“%p\n”, &x); *p = 1000; printf(“%d\n”, *p); return 0; } 変数 x の仮想アドレス 仮想アドレス 1000 番地の 内容を参照

仮想アドレス空間

•  プロセスごとに用意された仮想的なアドレス空間

–  仮想アドレス空間の大きさはハードウェアと OS で決まる

•  互いに分離している

–  プロセス A の 9000 番地とプロセス B の 9000 番地は別物 –  他のプロセス内の仮想アドレスを指定する方法はない •  プロセス A が参照できるメモリはプロセス A の仮想アドレスのみ

⇒

プロセス間のメモリ保護が達成されている

0番地 4Gbyte 0番地 4Gbyte process A process B a F 9000 9000

物理アドレス

•  物理メモリを参照するためのアドレス

–  物理メモリの空間を物理アドレス空間と呼ぶ

•  メモリ参照のためのハードウェアが使用

–  プロセスが使用するのは仮想アドレスのみ

CPU メモリ rd 30000 物理アドレス

仮想アドレスと物理アドレス

•  仮想アドレス空間を物理アドレス空間にマップする

–  各プロセスの仮想アドレスを物理アドレスに対応づける

•  仮想アドレスを物理アドレスに変換する必要がある

0番地 _emacs 4Gbyte 0番地 _firefox 4Gbyte

0 番地 _{(物理メモリ量)} 512M OS による物理メモリの仮想化

アドレス変換の実現

•  CPU がメモリ参照を行うときは

–  仮想アドレスを物理アドレスに変換する –  物理アドレスを使って物理メモリを参照

•  どーやって変換するの?

–  CPU に内蔵された MMU というハードウェアが変換する –  なぜハードウェア？ •  メモリ参照のたびに変換が必要 •  ソフトウェアでは遅すぎ

•  仮想アドレスと物理アドレスの対応付けは?

–  OS が管理する •  OS が仮想アドレス空間ごとに仮想アドレスと 物理アドレスの対応表を用意すればよい_{(アドレス対応表)} –  仮想アドレス空間が違えば同じ仮想アドレスでも 別の物理アドレスに対応している

MMU (Memory Management Unit)

•  日本語ではメモリ管理ユニット

–  仮想アドレスから物理アドレスの変換をする

–  CPU 内部に組み込まれたハードウェア

MMU アドレス対応表 MMU は アドレス対応表を 見ながら， アドレス変換をする アドレス対応表は OS が用意する． 仮想アドレス空間ごとに ひとつずつ用意する． アドレス対応表には， 仮想アドレスと 物理アドレスの 対応が記述されている． メモリ上に置いておく．

アドレス対応表の実現

•  各仮想アドレスごとに対応する

物理アドレスを記憶する必要がある

•  これは可能?

–  100 プロセス，32 bit の仮想アドレス空間だと

すると･･･

•  仮想アドレス 1 つにつき 32 bit = 4 byte の情報 •  全体では，4 x 232 _{x 100 = 1600 GB の情報}

⇒

非現実的

–  アドレス対応表だけでメモリを食いつぶしたら

本末転倒

ページ

(Page)

•  ある連続したアドレスの範囲

–  典型的には 4 KB，8 KB の大きさ •  経験的に決められている値

•  仮想アドレス空間をページ単位で区切る

–  仮想ページ •  仮想アドレス空間内のページ –  仮想ページ番号 •  0 から順につけられた仮想ページの番号

•  物理アドレス空間も同様

–  物理ページ，物理ページ番号 –  物理ページのことをページフレーム ともいう 0x0000 0x1000 0x2000 0x9000 0xa000 0xf000 0xb000

ページテーブル

(Page table)

•  アドレス対応表のページバージョン

–  仮想ページ番号を物理ページ番号に対応づける

•  ページテーブルを MMU にセットする

–  仮想アドレス空間ごとに用意する

0 1 0 仮想アドレス 1 物理アドレス 仮想アドレス空間 物理アドレス空間 仮想ページ 0 番の 上から 3500 バイト目 _{上から 3500 バイト目} 物理ページ 1 番の 仮想ページ0 番が物理 ページ1番に 対応するとす ると・・・ ページテーブルによるアドレス変換

アドレス変換

•  仮想ページ番号をキーとして対応づける

例

: 32 bit 仮想アドレス空間，4 KB ページ

–  保護属性や Mapping 不在の取り扱いは 次回解説する ページ内オフセット 仮想ページ番号 20 bit 12 bit 物理ページ番号 保護属性 その他の属性 Mapping不在 (対応する物理ページなし) 0 1

ページテーブルによるアドレス変換

0 a 1  b 2  c 3  d 4  e 5  f 6 g 7 h 8 i 9 j 10 k 11 l 4 3 1 0 1 2 仮想アドレス空間 ページテーブル 0 12 e f g h 8 物理アドレス空間 16 a b c 4 i j k l •  対応付けを管理するためのテーブル –  <仮想アドレス空間，仮想アドレス番号>を キーとして<物理ページ番号，属性>を 値とする表 –  OS によってメモリ内で管理されている

ページテーブルの

naive な実装

•  ページテーブルを naive に実装すると

–  100 個のプロセス，32 bit の仮想アドレス空間，

4 KB ページとすると･･･

•  ページテーブルの大きさ = 4 x 232 _{x 100 = 400 MB} –  まだ大きすぎる –  最近は 64 bit マシンが普通 ⇒ ページテーブルの大きさを小さくする工夫が必要

多段のページテーブル

•  多段の表を使って実現する

–  仮想アドレス空間は結構スカスカ •  4 GB のうち，多くとも数 MB のみ使用 ⇒ 無駄なエントリを作成しない •  必要なエントリのみを作成するという考え方 a1 a2 10 bit 10 bit offset 12 bit a1 a2

まとめ

•  OS によるメモリ管理法の基礎

–  素朴な実装

–  メモリ管理の要件

–  仮想記憶

–  ページ

–  ページテーブル