Microsoft PowerPoint mm

(1)

システムプログラム概論

Memory management 1/2

2005/4/26 門林雄基（インターネット工学講座）奈良先端科学技術大学院大学

今日の講義のポイント

z問題は何か？

zmemory hierarchy (メモリ階層)

zこの複雑な技術を、単純なプログラミングで使

いこなせるようにできないか

zmemory management in operating system

今日の講義のポイント

zthe development of memory management concepts

z monoprogramming without swap & paging

z→ multiprogramming with fixed partitions z→ virtual memory

zvirtual memory (仮想記憶)

zPaging, page table, segmentation

(2)

メモリ階層 (memory hierarchy)

zメモリ技術: アクセス速度、容量、価格のトレードオフ $0.0006/MB 250GB 13ms Disk $0.1/MB 1GB 60ns Main memory On chip 2MB 4.7ns On-chip cache On chip 512bytes 0.13ns Register cost Size Latency

メモリ階層

On-chip cache register Off-chip cache Main memory disk CPU

メモリ管理の目標

z 複数のプロセスがメモリという資源を競合して使用するのでこれをうまく調停する z メモリ技術を組み合わせ、非常に高速かつ大容量のアドレス空間をユーザプログラムに提供する (virtual memory) z アドレス空間を分離し、他のプロセスのバグ等の悪影響を受けないようにする (protection, software fault isolation)

z cache, swap, paging, segmentation 等のメモリ管理技術

(3)

メモリ管理とは

z メモリ管理とはマルチプログラミングにおける資源割り当て問題の一種 z contention (競合) z複数のプロセスがメモリという限られた資源を奪い合う z=> これだけではうまくいかない。 z arbitration (調停) z限られたメモリ上に複数のプログラムを共存させるために、メモリの割り当てを管理する必要がある。 z=> memory management (メモリ管理) z 資源に対する競合と調停は OS の基本的な機能

Part 1: memory management without hardware support

zハードウェアの機構を用いないメモリ管理

Monoprogramming (or uni-)

z一度にひとつのプログラムだけを実行 zアドレス固定、境界チェックなし z最も原始的なメモリ管理 zメモリ上に他のプロセスが存在しない => protection なし zMOS p. 191

(4)

スワップ

z一つのプロセス全体をディスクに退避 zswap out, swap in (MOS p. 197) zメモリサイズの制限を受けないが、 I/O オーバーヘッドが問題

可変区画 (variable partition) 割付け

zメモリセグメントのリストを維持 (H/P, start, length) zメモリの連続した空き領域 (hole) を探す

zfirst fit: 充分な大きさのholeを検出するまでリストを走査

znext fit: 前回終了したところから検索を開始

zbest fit: 該当するholeの中で最も小さいものを採用

(5)

可変区画割付け

H, 0K, 64K P, 64K, 96K H, 160K, 16K P, 176K, 16K 64K 96K 16K 16K メモリ空間の計算機内におけるリスト表現

可変区画 (variable partition) 割付け

zbest fit は first fit, next fit よりメモリの無駄が多い。

zfirst fit は平均的に大きなholeを作り出す。 zプロセスが要するメモリ容量が既知でない場合は

どうするのか？

zbrute-force approach: memory compaction zbetter approach: virtual memory

Interlude

z 実社会で技術革新を起こすためには、コンピュータアーキテクチャ、OSに対する深い理解が必要

z 例：Network Appliance NetCache products

z~500Mbps Webキャッシュ z~1Gbps Real/WMT ストリーミング zAppliance approach

z単一のアドレス空間 zメモリ保護の必要もない → 高速

(6)

Part 2: memory management with

hardware support

zハードウェアの機構を用いたメモリ管理

仮想記憶が誕生した背景

z参照の局所性 (locality of reference) zプロセスは実行中に全メモリ空間の一部しか必要としない zプロセスの実行に必要な一部だけをメモリに置き、残りはディスクなどに置けば良い。 z実メモリと、論理的なアドレス空間の分離

仮想記憶 (virtual memory) と実記憶

(physical memory)

z仮想アドレス、仮想アドレス空間 (virtual address space) z実アドレス、実アドレス空間

(physical address space)

zAddress translation: 仮想アドレスから実アドレスへのマッピング

zMemory Management Unit (MMU)

(7)

Address translation

CPU 実記憶 MMU 仮想アドレス _{実アドレス} アドレス変換なし

Base and bounds

z仮想アドレス + base = 実アドレス zbounds を超えるメモリアクセスは違反 z実メモリにおいて、可変区画割付けが必要仮想アドレス実アドレス + Bounds (境界) Base (基底) > エラー

ページング(1)

zページサイズを単位とした address translation z(仮想ページ番号、オフセット) --> (物理ページ番号、オフセット) z(MOS p. 202～) zページテーブルを実メモリ上に維持 zページテーブル・レジスタ、テーブルサイズ・レジスタ

(8)

ページング(2)

VPN offset Page table register Table size register

CPU Virtual address

Page table

PFN P D Page table entry PPN offset

Physical address

ページング(3)

zメモリ管理が非常に単純になる -- ビットマップを用いたメモリ管理 z連続領域を探す必要がない z仮想アドレスを sparse に使う場合、ページテーブル長が爆発

セグメンテーション(1)

zbase and bounds の拡張。

コード、データ、スタック毎に base, bounds z(MOS p. 249～) zsegment descriptor (セグメント記述子) に以下の情報が含まれる: zセグメント・ポインタ、セグメント・サイズ、保護ビット zセグメントテーブルを CPU 内部に維持

(9)

セグメンテーション(2)

Seg# offset

Segment pointer Segment size Protection Segment descriptor Virtual address code data const stack base offset Physical address Segment table CPU

Multi-level translation:

ページング + セグメンテーション

z今日のプロセッサアーキテクチャではこれが主流。 z仮想アドレス = (segment#, page#, offset)

Seg# VPN offset Segment table Page table offset PPN

Multi-level page tables

zこの方式をとるプロセッサもある zMOS p. 207～ (独習)

zセグメントを用いた方式と比較したときの得失は? → MOS p. 252

(10)

メモリアクセスの高速化技法

zaddress translationのオーバーヘッド zセグメントテーブル参照 => ページテーブル参照 => メモリアクセス

zTranslation Look-aside Buffer (TLB)

z変換早見表 -- メインメモリへのアクセスなしに

アドレス変換

TLB

Translation look-aside buffer

CPU 実記憶 MMU 仮想アドレス実アドレスアドレス変換なし TLB

TLB types

zDirect mapped TLB zN-way set associative TLB zFully associative TLB (略)

(11)

Direct mapped TLB

VPN VPN PFN h(VPN) Same?

Use this TLB entry

Use MMU yes no

N-way set associative TLB

VPN VPN PFN h1(VPN) Same? VPN PFN h2(VPN) Same? N banks

TLB secrets

zテーブルサイズ vs ハッシュ衝突 (TLB キャッシュミス) のトレードオフ z小さなテーブルでも 90% のアドレス変換を高速化できる。 zQ. コンテクストスイッチすると TLB は作り直しか？

(12)

まとめ

z メモリ管理は OS における資源管理メカニズムのうち最も興味深いもの z OS がプロセッサのアドレス変換機構を活用することで、さまざまな機能が実現される： z広大なアドレス空間 zメモリ階層を活かした、費用対効果の高いシステム zソフトウェア障害の検出と隔離 zプロセス間のセキュリティ zプロセス間のメモリ共有次回

レポート課題1

zQ. プロセッサのメモリアーキテクチャについて調べ、仮想アドレスから実アドレスへの変換プロセスの様子を絵と文章で説明せよ。 z学籍番号 % 4 == 0 の学生： MIPS z学籍番号 % 4 == 1 の学生： IA-64 z学籍番号 % 4 == 2 の学生： ARM z学籍番号 % 4 == 3 の学生： PowerPC

資料へのポインタ

z MIPS z http://www.mips.com/publications/

z "MIPS R4000 Microprocessor User's Manual" 等 z IA-64

z Sunil Saxena, "IA-64 Architecture"

z Jerry Huck et al., "Introducing the IA-64 Architecture" 等 z ARM

z Http://www.arm.com/documentation/

z Intel, "Memory Management on the StrongARM SA-110" 等 z PowerPC

z http://www-03.ibm.com/chips/products/powerpc/