–
プロセスのサイズに従って割り当て
S m p s
a m
s S
p s
i i
i
i
i i
for allocation
frames of
number total
process of
size
5 137 64
10 127 10
64
1 2
a s s m
i
Global vs. Local Allocation
• Global replacement
– 各 プロセスは置き換えるページフレームを選ぶ際，すべて のページフレームから選択可能
•
あるプロセスが他のプロセスのフレームを取得可能
• Local replacement
–
それぞれのプロセスは置き換えるページフレームを選ぶ際，
決められたページフレームの集合からのみ選択可能
補足
• 複数プロセスにそれぞれ仮想アドレス空間
–
追い出しの対象
(=割付けの候補）は？
A0 10
A1 8
A2 4
A3 7
A4 3
A5 5
A6 6
B0 4
B1 5
B2 2
B3 3
B4 6
C0 12
大域ページ置換
global replacement
他のプロセスも含めて全 域から割り当て
局所ページ置換
local replacement
自分のプロセスの領域か
A0 A1 A2 A3 A7 A5 A6 B0 B1 B2 B3 B4 C0
A0 A1 A2 A3 A4 A5 A6 B0 B1 A7 B3 B4 C0
ページングの利点
• 外部断片化がなし
• 主記憶の大きさに依存しないアドレス空間
–
プロセス毎に独立
• 実際に使用するページのみを主記憶に配置
–
主記憶の利用効率の向上
–
主記憶容量を超える記憶領域
• マルチプログラミングの多重度増
➡CPU利用率の向上
参照の局所性
• locality of reference
• 短期的なページアクセスに多く見られる傾向
–
少数のページを集中的にアクセス
•
長期に渡るとそうでない場合も
• 少量の高速メモリでも処理を高速化
–
キャッシュ ー メモリ
–メモリ ー ２次記憶
– TLB
ー ページ表
)参照の局所性
1.0
1.0 0.5
0.5
ページフォルト率
各プロセスで主記憶に存 在するページの割合
ランダムなアクセス 局所的なアクセス
時間的局所性
• 最近アクセスされたページは近い将来にも アクセスされる確率が高
–
プログラムのループの部分
• コードは同じ部分を繰り返し参照
• 同じ制御変数を繰り返しアクセス
–
他にも関数の引数や局所変数
main() ...
printf() ...
k[ ]
空間的局所性
• 近くのページがアクセスされる確率が高
–
配列の要素
–
関数呼び出しのないプログラムコード
–
制御スタック（関数呼出し時に伸び縮み）
• 関連する変数の領域を近くに配置
–
空間的局所性に寄与
for (i=0; i < SIZE; i++) { printf(“.... %d”, k[i])
main() ...
printf() ...
k[ ]
Segmentation
• ユーザから見るとメモリ領域は、様々な意味のある塊
–
プログラム
–変数
–
スタック
• セグメントとはこのような塊
Logical View of Segmentation
1
3
2
4
1 4
2
3
user space physical memory space
Segmentation Architecture
•
論理アドレスはセグメント番号＋セグメント内オフセット
<segment-number, offset>
Segmentation with Paging
Intel ｘ 86
Working-Set Model
• working-set window
• WSSi (working set of Process Pi) = もっとも最近の時間内にアクセスされたページ群 – が小さすぎると，全体の網羅は不可能
– が大きすぎると，局所的には網羅が可能
– = プログラム全体を包含
• D = WSSi 要求されるフレームの合計
• if D > m Thrashing状態
– プロセスをサスペンド
参照回数
＝１０の場合
補足
• working set model
• ワーキングセット
–
プログラムが使用しているページの集合
–
主記憶にあればページフォルトは殆ど発生なし
• 効率よく実行するために主記憶に置きたい
• ワーキングセットモデル
–
各プロセスのワーキングセットを記録
–
プロセス実行前に対応するメモリ中への存在を確認
•
時刻
tにおける
W(t, w)の定義
– [t-w, t]の間にアクセスされるページ集合
– ここでの時間：他のプロセスが実行中の時間は含めず – W＝「ワーキングセットのウィンドウサイズ」
補足
•
ワーキングセットモデルでは，W(t, w) をワーキングセット とし，主記憶に
ウインドウサイズ w
t t-w
ワーキングセッ 遷移 ト2
遷移
補足
• プログラムの典型的な実行パターン：
–
ある部分をしばらく実行すると，次の部分移行
• ex) コンパイラのパス
–
ワーキングセットモデルでは，これを考慮する必要あり
ワーキング ワーキング 遷移
ページ数
Thrashing
• Thrashing
（スラッシング）
– プロセスが頻繁にページイン・アウトを繰り返すこと
•
マルチプログラミングの多重度を向上
– CPU利用率／スループットが向上
• プロセス単体の処理時間：増加
• システム全体の性能：向上
•
多重度を上げすぎるとページフォールトが多発
– CPU利用率の急激な減少
頻繁に使用するページ数＞ページフレーム総数
⇒ 新しいページのために，すぐ使うページがページアウト
Thrashing
• なぜページングはうまくいく ? Locality model
–
プロセスはある場所からほかの場所へ移動
–その場所は重複しているかも？
• Thrashing はなぜはっせいするのか ?
バッキングストア
• どこにある？
–
一般に
HDDの一部
• 固定領域・主記憶より大
• ファイル・主記憶より小 (部分的な待避)
主記憶
0
UNIX の仮想アドレス空間
•
多くの
UNIXは左のような 配置（
Linux, FreeBSD）
– 0〜3GBがユーザ プロセス空間
– exec直後のtext, dataバッキン グストアは実行ファイル自体 text
data
stack
0x0000000
0xC000000
bss
kernel text, data
text
data
header
symbol table
実行ファイル
（ディスク中）
ページテーブルは 10bit，10bitの2段
Copy-on-Write
• data
領域などは読み書き可能
– 実行可能ファイルをバッキングストアにして大丈夫？
– 書き換えちゃったら・・・？
– 同時に読み書きしたら・・・？
– 書き込みが行われた時にページを確保・コピー
text data read
read write
text data header
read-only read-only
text write data
text data header
read-only read-only
プログラムコードやライブラリの共有
• プログラムの部分は一般に書き換え不可なので 主記憶の一部を共有して，省メモリ化が可能
:
0
1
15
:
0
1
15
:
0
1
15
sbrk システムコール
• void *sbrk( 増分 )
–
データ領域（アドレス空間）を「増分」バイト増やすシス テムコール
• 主記憶を直ちに確保するわけではない
text データ
stack 決められた上限まで使用可
sbrk()等で明示的に拡張しない限り，「データ」
領域を超えてアクセスは不可能 sbrk(0)
malloc()/free()
ープログラムから見たメモリ管理ー
• sbrk
によってメモリを確保（
mmapを使うことも
…）
• free()
された領域の管理
…リスト等で空き領域管理
– free()された空き領域 → 足りるならそこから確保
• first-fit, best-fit等の方法で – 空き領域がなければsbrk
• OS
の機能（システムコール）を利用したライブラリ関数
– OSが提供するものと異なる実装を用いても○
• cf. K&Rの単純な実装例
– 割当て･解放，断片化，局所性等の性能は実装依存
mmap システムコール
•
任意のファイルを仮想アドレス空間にマップ
– ページフォルトで必要部分を（OSによって）読み込み
• void *mmap(void *start, size_t length,
int prot, int flags, int fd, off_t offset);
– start:このアドレスからマップ
• ページサイズの整数倍, 0ならmmapに任せる – length:マップする長さ
– prot:PROT_EXEC,PROT_READ,PROT_WRITE – flags:MAP_SHARED,MAP_PRIVATE（COW)
– fd:マップするファイル記述子
マップする位置について
text data
sbrk(0) bss
こういう部分にも マップが可能
この部分のPTEは用意 しなくてよい（cf. 多段 ページテーブル）
/* stdio.h, sys/mman.h, unistd.h, sys/types.h, sys/stat.h, fcntl.hをインクルード */
main() {
int fd; char *p;
/* getpagesize() のファイルをあらかじめ用意 */
fd = open("output", O_RDWR|O_CREAT, 0600);
if ((int)(p = mmap(0, getpagesize(),
PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0)) == -1) { perror("mmap");
exit(1);
}
printf("%c¥n", p[100]);
p[0] = 'a'; p[100] = 'b';
Windows の仮想アドレス空間
• x86 Windows
の標準で は
2GBのユーザ空間
•
起動時オプションで
3GBを指定可能
• XP, Server 2003
は
2GB〜
3GBの間で指定可能
0x00000000
0xC0000000
1GB system 3GB user space 2GB
user space
kernel, executive
process page table, hyper space
0xC0800000