システムプログラム概論 Memory management 2/2 25/5/6 門林雄基 ( インターネット工学講座 ) 奈良先端科学技術大学院大学 前回 Memory hierarchy Contention and arbitration for memory Virtual memory: software + hardware solution Address translation Physical address to virtual address Paging, segmentation Page table, segment descriptor... In the real world (MIPS, IA-64 etc.) 今日の講義のポイント Page replacement Page faults Page replacement algorithms Caching modified data Working set
今日の講義のポイント Virtual memory and performance Observe virtual memory in action Virtual memory and security Segmentation faults Privileged mode Sharing data between processes Page table entry ハードウェアが更新 Referenced Modified OS が更新 Present/absent Protection Caching disabled Page frame number (MOS p. 2) Page fault 仮想ページ番号 (n) に対応する物理ページなし present bit = プロセス (A) が仮想ページ内のメモリへアクセス page fault Page fault 発生時 当該プロセスを一時中断しOSの仮想記憶モジュールを実行 : 該当ページ (n) をディスクから復帰 (page in) present bit = 当該プロセス (A) の処理を続行 2
Page replacement 物理ページ数には限りがある 使っていない仮想ページをディスクへ退避 (page out) Present bit = どのページを選んで退避させるか? さまざまなアルゴリズムが考えられた NRU, FIFO, second chance, LRU... NRU page replacement algorithm MOS 4.4.2 (p. 26) FIFO page replacement algorithm MOS 4.4.3 (p. 27) 3
Second chance MOS 4.4.4 (p. 27) LRU page replacement algorithm MOS 4.4.6 (p. 28) やってみよう MOS p. 266 Q.29 A computer has four page frames. The time of loading, time of last access, and the R and M bits for each page are as shown below: Page Loaded Last ref R M 26 28 23 265 2 4 27 3 285 Which pages will NRU / FIFO / LRU / second chance replace? 4
Caching modified data 一般的な用語 ( メモリ階層で使われる ) Write-through: ただちに書き戻す Write-back: キャッシュから追い出されるまで書き戻さない Reliability / performance trade-offs ページアウトでは write-back 方式を採用 Working set w(k, t) (MOS p. 223) k most recent memory references at time t Thrashing ( スラッシング ) ワーキングセット サイズがキャッシュサイズを超えると起きる Virtual memory and performance 仮想記憶の功罪 プログラミングは単純に メモリ容量を気にする必要が無い マルチプログラミングが単純に ディスクさえあれば動き続ける スラッシングしていても... 本当はメモリが足りないのに メモリ不足をどうやって判定するか? 5
Virtual memory and performance: the case of BSD UNIX vmstat で全体のメモリ使用状況を把握 $ vmstat procs memory page disks faults cpu r b w avm fre flt re pi po fr sr ad md in sy cs us sy id 2 4758 844 82 6 696 95 3 96 47236 844 6 5 223 53 47236 844 5 3 86 44 99 47236 844 5 76 44 47236 844 5 7 254 49 99 ps で各プロセスのメモリ使用状況を把握 $ ps axotsiz,rss,vsz PID TSIZ RSS VSZ TT STAT TIME COMMAND?? DLs :. (swapper) 248 36 544?? ILs :. /sbin/init -- 284 324 636 738?? R :. /usr/xr6/bin/xfree86 : 38 56 836 9752 p S :.7 xemacs (xemacs-2..4) Virtual memory and security 仮想記憶で取り扱うセキュリティ プロセス内のメモリアクセス違反の検出 (detection of memory access violations) Segmentation fault 他のプロセスとのアドレス空間の分離 (separation of address spaces) 特権レベルでのアドレス空間の生成 (address space creation at privileged level) プロセス間のアドレス空間の共有 (sharing memory among multiple address spaces) Segmentation fault プログラムのバグ等で 許可された範囲を超えてメモリアクセスを行った場合 セグメント記述子に記載されたサイズを超えてメモリアクセス (memory access beyond allowable limit as indicated in segment descriptor) セグメント記述子に記載された権限を越えてメモリアクセス segmentation fault 6
Segmentation fault Virtual address Seg# offset base offset Physical address code data const stack Segment table CPU Segment pointer Segment size Protection Segment descriptor 特権レベルでのアドレス空間の生成 アドレス空間の操作は OS のカーネル ( プロセッサの特権レベル ) でのみ許可される 下記の情報を OS カーネルが設定する Page table register Table size register Page table Segment descriptor Segment table (MOS p. 26) Seg# Segment table VPN Page table offset PFN offset アドレス空間の分離 Text Data Const Stack s virtual address space 実記憶 s virtual address space Text Data Const Stack 7
アドレス空間の共有 Text Data Const Stack s virtual address space 実記憶 s virtual address space Text Data Const Stack まとめ メモリ管理のソフトウェア的側面について学んだ Page fault, page replacement Page replacement algorithms メモリ管理と性能 Working set VM statistics メモリ管理とセキュリティ Segmentation fault Address space management 8