Mirage:

Mirage: A Coherent
Distributed Shared
Memory Design
増山隆米澤研究室
[email protected]
参考文献
Brett D. Fleish et al, A Coherent
Distributed Shared Memory Design
Proceedings of the 12th ACM Symposium
on Operating Systems Principles. 1989

Mirageとは?
分散共有メモリ (DSM) システム
 Coherentなシステムを提供する
 Unix System V IPC互換

 分散OS

Locusのkernel内に実装
人工的なテストプログラムしか動いていない
Unix System V

Paged segmentation
 segment単位で共有
 共有するsegmentはプロセスの仮想アドレス空
間にAttachして使用
 生成時にアクセス制限可能
segment
page
page
page
page
Coherence
writeは逐次処理
 readはbatch処理
 readがwriteを追い越さない
 writable-copyを持つsiteは一つ

Coherence: Special Sites

Library site
 Segmentを担当
 リクエストをキューに受け付ける、処理する
 適切なClock
siteと通信
Mirageではsegmentを生成したsiteが担当

Clock site
 最新のpageを持つ
 Writerがいればそのsiteが担当
 copyを持つsiteへinvalidateメッセージを送る
 最新のページを送る
ページフォールトの処理
Invalidationの処理
invalidationの処理

Library site
 invalidateリクエストを受け付ける
 Clock

siteにinvalidateメッセージを送る
Clock site
 copyをもつsiteたちのpageをinvalidate

該当するpageをunmapさせ、pageを破棄させる
 新たにpageを要求したsiteにpageを渡す
invalidation時の最適化

readerがwriterになる場合、コピーは送らな
い
 通信料を減らす

write権限がreaderのリクエストによって奪わ
れたとき、writerはread権限を保持する
 局所性
 writerはすぐに同じpageをよむだろう
Coherence: Window time (Δ)
 siteに割り込みなしでpageを割り当てる時間

Δ時間が過ぎるまではinvalidationを受け付けない
 性能を調整するためのパラメータ
動作
Current
Incoming
(Clock site) (Request)
Clock
Check
Invalidation
Readers
Readers
No
No
Readers
Writer
Yes
Yes
(opt 1)
Writer
Reader
Yes
Writer
Writer
Yes
No
(opt 2)
Yes
実装: ページテーブル
standard System Vで
は共有されるsegment
はシステム空間の一部
であり、swapされない
(常にvalid)
⇒ Mirageがinvalidビッ
トをたてる
 page tableの使われて
いないビットを使用して
右表の情報を管理する

reader
mask
writer
readerのリ
スト
writer site
window
Δの値
ticks
Install time ページを
持ってきた
時刻
実装: ページフォールト処理の処理

フォールトがreadかwriteかを区別できなけれ
ばならない
 区別できるアーキテクチャはいくつかある

VAXはOK
実装: invalidationの処理
ネットワーク越しのinvalidationはネットワーク
サーバープロセスが行う (Mirage自前)
 invalidateするページをmapするすべてのプ
ロセスのページテーブルエントリに対して
invalidation をしなければならない

実装: consistency control design

masterの変更をいつ伝えるか?
 active
methods
更新があったらすぐに伝える
 実装困難、コスト大
 意味のない更新があり得る

 lazy
methods ←こちらを採用
プロセス再開前に
 実装は楽 masterをコピー(例変更ありなしに関わらず)
 プロセス再開のコスト大


共有するsegmentサイズに比例
性能評価: worst case
同じページの異なる
変数を異なるsiteに
ある2プロセスが
読み書きする

write
x
y
wait and read
P1
write
P2
性能評価: worst case
性能評価: worst case
性能評価: worst case

Δ<=6 でyield()を使うとthroughputが高い
 無駄に長い時間ページを持たない
 ほかのプロセスにCPUを譲る

一つのsiteがlibraryとuserを兼ねている
 context
switchのオーバーヘッド
 もし第三のsiteがlibraryをやると
○context switch不要
×Network遅延が発生
性能評価: Δを調整
同じpageにある
別の変数をそれぞれ
デクリメント
 局所性あり
 実際のアプリケ
ーションをシミュレート
x

decrement
y
y
decrement x
P1
P2
性能評価: Δを調整
性能: Δを調整

Δ <= 600 … contention side
 pageのやりとりが激しい
 Δに敏感

Δ > 600 … retention side
 pageを必要以上に保持する
 contention
sideと比べるとΔに鈍感
まとめ

プログラムに性能が左右される
 yeildで待つ
or busy wait
invalidationのオーバーヘッドが大
 Δの調整が必要

 プログラムの局所性にあわせるとよい

Download Report