メモリ管理 - funini.com

メモリマップドファイル
オペレーティングシステム
今日の流れ (12/10)
 ディスクの話の残り
ディスクを高速に使う工夫
 メモリとディスクの簡単なまとめ
 メモリマップト・ファイル
(mmap)
http://funini.com/kei/mmap/
ディスクについて (前回の続き)
 ディスク
(ハードディスク, DVDなど)
電源を切っても消えない
物理的にはシリンダ・ブロックに分かれている
OSによって抽象化され，ファイル単位でデータ
を管理できる
 アクセスはメモリに比べて遅い
→高速化する工夫
http://funini.com/kei/mmap/
連続した領域への割り当て
 一度に読み出すのに都合の良いブロック
(例: 同じシリンダ(円周)内の全ブロック)に
ファイルの連続した領域を割り当てる
cf.
いわゆる「デフラグツール」
 先読みの効果を大きくする
OS上では
一つのファイル
ディスク上では
断片化している
“デフラグ”によって
連続領域に割り当て
fruit.txt
http://funini.com/kei/mmap/
ディスクスケジューリング
 アクセスすべきブロックを並び替えて，少な
いヘッドの動きで一度に読む
1,5,3,6というリクエストが来ても，1,3,5,6と
並べ替えて読み，ヘッドの動きを少なくする
元々のリクエスト: 赤(1) 黄(5) 緑(3) 青(6)
リクエスト処理順: 赤(1) 緑(3) 黄(5) 青(6)
654321
読み取りヘッド
http://funini.com/kei/mmap/
Agenda
 ディスクの話の残り
 メモリとディスクの簡単なまとめ
仮想メモリ
ディスクキャッシュ
 メモリマップド・ファイル
(mmap)
http://funini.com/kei/mmap/
OSによるデバイスの抽象化
デバイス
CPU
メモリ
OSの見せ方プロセス
スレッド
ディスク
論理メモリ空間ファイルシステム
変数
ファイル
実際のデバイス
メモリ
TCP/IP
ソケット
OSによる抽象化
プロセス
CPU
論理メモリ空間ファイルシステム
ディスク
ネットワーク
ネットワーク
char[256]
int
double
hello.c
fruit.txt
ソケットAPI
133.11.238.126
http://funini.com/kei/mmap/
メモリとディスク

OSは柔軟にメモリとディスクを組み合わせる


物理メモリ: 速い・高価・揮発性
→頻繁にアクセスするデータに適する
ディスク: 遅い・安価・不揮発性
→広大な空間を必要とするデータに適する
仮想メモリ:「メモリに見えて実はディスク」
 File Cache:「ディスクに見えて実はメモリ」

アドレス空間
物理メモリ
char[256]
int[8]
int
char[512]
物理メモリ上の
ファイルシステムファイルキャッシュ
hello.c
ディスク上の
スワップファイル
fruit.txt
ディスク
http://funini.com/kei/mmap/
仮想メモリ:ディスクを用いてメモリを拡張
 物理メモリより大きなアドレス空間を提供
頻繁にアクセスされるページは物理メモリ上
物理メモリ上に無い番地にアクセスすると，
ページフォルト(Page Fault)が発生して
ディスクからメモリにデータが読み込まれる
アドレス空間
メモリ上
A
B
Dにアクセス
C
D
E
アドレス空間
B
C
D
ディスク上
F
A
E
Page
Fault
F
ディスクから
メモリにDが
コピーされる
http://funini.com/kei/mmap/
File Cache:メモリを用いてディスクを高速化
 ファイルの一部をメモリ上にキャッシュ
 アクセスしたファイルをメモリ上にキャッシュ
 2回目からはキャッシュに対しアクセス
 2回目はメモリコピーと同じアクセス速度になる
ファイルを読み込み
f =open(hello.c);
アドレス空間
read(f, buf);
buf[256]
2回目のアクセスは高速
…
read(f, buf2);
アドレス空間
buf[256]
キャッシュが
読み書きされる
hello.c
hello.c
メモリに
キャッシュされる
hello.c
hello.c
時々
同期される
http://funini.com/kei/mmap/
Agenda
 ディスクの話の残り
 メモリとディスクの簡単なまとめ
 メモリマップド・ファイル(Mmap)
使い方
ファイルをメモリみたいにアクセス
共有マッピングでプロセス間でデータの共有
メモリ確保
(mallocの実体?)
仕組み
プライベートマッピングの最適化
mmapの利用価値
http://funini.com/kei/mmap/
ファイルAPI
 ファイルAPIはstream(流れ)志向
read()は前の読み出し位置を覚えている
 メモリはランダムアクセス志向
いつでも配列の任意の場所を読み書きできる
開く
読み込み
書き込み
メモリ
malloc(128)
int A[10];
i
A[3]
i = 10
A[10] = 128
ファイル
open()
read()
seek()
write()
seek()
ネットワーク
socket, connect
recv()
send()
http://funini.com/kei/mmap/
ファイルをランダムアクセスしたい場合
 例:大きな辞書ファイルを引く
 seek(),
read()を繰り返してもいいが面倒
 ファイルをメモリのように扱えると便利
→メモリマップドファイル (mmap)
f = open(dict.txt);
ファイルシステム read(f, buf);
/* do something */
read()
read()
seek(10);
dict.txt
read(f, buf);
seek(
/* do something */
)
seek(
)
seek(200);
read()
read(f, buf);
/* do something */
アドレス空間
A[0]
A[0];
/* do something */
A[10]
A[10];
/* do something */
A[200]
A[200];
/* do something */
http://funini.com/kei/mmap/
メモリマップドファイル
 基本:ファイルを明示的なread/writeではなく
「あたかもメモリの様に」読み書きするAPI
fd=open(“dict.txt”...);
A=mmap(.., fd, ..);
/* do something */
s = A[100];
ファイルシステム
論理アドレス空間
dict.txt
http://funini.com/kei/mmap/
メモリマップドファイル: Unix API
 fd
= open(file, access);
a’ = mmap(a, n, prot, share, fd, offset);
意味:
“fileのoffsetバイトから始まるnバイトを，
アドレス[a’, a’ + n)でaccess可能にする”
a  0  a’ = a (空いていれば)
a = 0  a’はOSが選ぶ
ファイルシステム
論理アドレス空間
a’
offset
a’+n
offset+n
http://funini.com/kei/mmap/
プライベート/共有マッピング
mmap(a, n, prot, share, fd, offset);
 パラメータshare
 複数のプロセスが同じファイルをmmapした場合の挙動
を指定
 share = MAP_PRIVATE
 プロセスごとに別のコピーを見る
 書き込み結果はファイルに反映されず，プロセス間で
も共有されない
 share = MAP_SHARED
 複数のプロセスが同じデータを見る
 書き込み結果はプロセス間で共有され，ファイルにも
反映される
http://funini.com/kei/mmap/
プライベートマッピング
 同じファイルをマップした際，複数のプロセ
スが独立した領域を持つ
プロセス
論理アドレス空間
dict.txt
dict.txt
プロセス
論理アドレス空間
dict.txt
2つのプロセスは
別々の物理メモリを見ている
(※後述するが，
実際には同じ場合もある)
http://funini.com/kei/mmap/
共有マッピング
 同じファイルをマップした際，複数のプロセ
スが共通の物理メモリを参照できる
書き込んだデータが共有される
プロセス1
論理アドレス空間
プロセス2
論理アドレス空間
2つのプロセスは
同じ物理メモリを見ている
dict.txt
dict.txt
http://funini.com/kei/mmap/
メモリマップドファイル: Windows API
h
= CreateFile(file, access, …);
m = CreateFileMapping(h, …);
a’ = MapViewOfFileEx(m, prot, offset1,
offset2, n, a);
 prot = FILE_MAP_COPYでMAP_PRIVATE
と似た効果を持つ
http://funini.com/kei/mmap/
mmap()によるメモリの割り当て
 brk
(Unix)やVirtualAlloc (Win32)に代わる
メモリ割り当て手段になっている
Unix:
特別なファイル/dev/zeroを
MAP_PRIVATEでmmapすると，特定のファイ
ルに結びついていないメモリ領域を得る
Win32: INVALID_HANDLE_VALUEを
CreateFileMappingに渡すと同様の効果
malloc()の中で使われている
http://funini.com/kei/mmap/
Agenda
 ディスクの話の残り
 メモリとディスクの簡単なまとめ
 メモリマップド・ファイル(Mmap)
使い方
仕組み
プライベートマッピングの最適化
mmapの利用価値
http://funini.com/kei/mmap/
メモリマップドファイルの仕組み(1)
 mmap/MapViewOfFile
etc.の実行時にファ
イルの中身をすべて読むわけではない
 mmapシステムコール内の動作:
アドレス空間記述表へ，新たにmmapされた
領域を記録する(だけ)
まだ物理メモリは割り当てない
dict.txt
?
dict.txt
http://funini.com/kei/mmap/
メモリマップドファイルの仕組み(2)
 mmapされたページが初めてアクセスされた
際に，ページフォルトが発生
 OSがファイルから内容を読み込む
 ページへの書き込み
 適当なタイミングで元のファイルに反映
アクセス
dict.txt
PageFault
を受けて
読み込み
dict.txt
Page
Fault
適宜書き込み
http://funini.com/kei/mmap/
メモリマップドファイルの仕組み(3)
 OSにとっては，メモリ管理(仮想記憶)機構
の自然な延長
メモリの退避場所としてスワップ領域の
代わりに通常のファイルを使うだけ
仮想メモリ
アドレス空間
メモリマップドファイル
アドレス空間
物理メモリ
dict.txt
char[256]
アクセス int
List
List
Page
Fault
List
ディスク上の
スワップファイル
SWAP
物理メモリ
アクセス
ディスク上の
ファイル
Page
Fault
dict.txt
http://funini.com/kei/mmap/
ページフォルト処理 (復習)
アドレス a へのアクセスで
ページフォルト発生
アドレス空間
記述表を参照
aは割り当て済み?
アドレス空間
記述表を参照
N
(OSの)保護違反
N
(OSの)保護違反
Y
保護属性OK?
Y
次のスライドでは
ここを詳しく説明
aを含む論理ページに対する
物理ページ割り当て
http://funini.com/kei/mmap/
物理ページ割り当て処理とその拡張
未使用な物理ページを見つける
ファイルマップ
された領域?
Y
N
初めてのアクセス?
N
対応するファイルから
ページ内容を読み込み
(ページイン)
2次記憶から
ページ内容を読み込み
(スワップ領域から
ページイン)
Y
割り当てたページを
0で埋める
スレッドを中断
ページイン終了後
スレッドを再開
http://funini.com/kei/mmap/
デモ: mmapとreadの性能挙動観察
 大きなファイルの全内容を次の二通りの方法
でアクセス
mallocとreadでファイル全体に相当する内容を
読み込んで、アクセス
mmapして配列のようにアクセス
両方の手法で2回ずつ読み込み
http://funini.com/kei/mmap/
Agenda
 ディスクの話の残り
 メモリとディスクの簡単なまとめ
 メモリマップド・ファイル(Mmap)
概要
仕組み
プライベートマッピングの最適化
読み出し専用マッピング
Copy-on-writeマッピング
mmapの利用価値
http://funini.com/kei/mmap/
プライベート/共有マッピングの違い
 共有:
全てのマッピングで物理メモリを共有
 プライベート: マッピングの数だけ物理メモリを消費
 プライベートマッピングは(そのままだと)共有マッピング
に比べて物理メモリの利用効率が悪い
共有マッピング
プロセスA
アドレス空間
プライベートマッピング
物理メモリ
file
プロセスA
アドレス空間
物理メモリ
プロセスB
アドレス空間
プロセスC
アドレス空間
file
プロセスB
アドレス空間
プロセスC
アドレス空間
http://funini.com/kei/mmap/
OSのプライベートマッピング最適化
 考え方:
可能な限り物理メモリを共有する
読み出し専用マッピング
明示的に「読み出し専用」としてマッピング
“Copy-on-write”マッピング
書き込みが起こったらはじめてコピーする
http://funini.com/kei/mmap/
読み出し専用マッピング
 利用者が読み出し専用であることを指定する
書き込みが起こらないので，プライベートマッ
ピング間で常に物理メモリを共有できる
 典型的使用場面
プログラム開始時にプログラムテキストを読み
出すために使われている
http://funini.com/kei/mmap/
Copy-on-write
 コピーを作らないといけない場面で，実際に
書き込みが起こるまでコピーをしない
mmap()でのプライベートマッピング
fork()でのメモリコピー
PHPやPythonでの値渡しの変数
http://funini.com/kei/mmap/
Copy-on-writeマッピング
 書き込み可でマップされた領域も，実際に書き込ま
れるまで物理メモリを共有しておく
 保護属性を「書き込み不可」にしておく
(ページテーブル，TLB上で)
 最初に書き込みが起きた時にCPU保護例外が発生
 ここでOSが新しい物理ページを割り当て，コピーを作る
書き込み発生前
プロセスA
アドレス空間
書き込み発生後
物理メモリ
file
物理メモリ
プロセスB
アドレス空間
file
コピー
プロセスA
アドレス空間
write
発生
プロセスB
アドレス空間
http://funini.com/kei/mmap/
応用: Copy-on-writeによる高速fork(1)
 fork
: アドレス空間のコピー
 pid = fork();
if (pid == 0) { /* child */
…;
execve(“/bin/ls”, …);
} else { /* parent */
…;
}
fork
exec
ls
http://funini.com/kei/mmap/
応用: Copy-on-writeによる高速fork(2)
 子プロセス生成=ページテーブル+アドレス
空間記述表のコピー(物理メモリのコピー)
生成直後は物理メモリを親子で共有
ただし「書き込み不可」に設定しておく
 書き込まれたページのみ，書き込まれた時点
でコピーを生成していく
 子プロセスがやがてexecveを実行すると，
子プロセスのマッピングは除去される
http://funini.com/kei/mmap/
Agenda
 ディスクの話の残り
 メモリとディスクの簡単なまとめ
 メモリマップド・ファイル(Mmap)
使い方
仕組み
プライベートマッピングの最適化
mmapの利用価値
http://funini.com/kei/mmap/
メモリマップドファイルの利用価値 (1)
 大きなファイルの一部だけをランダムアクセ
スする場合
実はプログラムコード(特にライブラリ)はメモリ
マップドファイルを利用して共有されている
printfやmallocが含まれるlibc.soなど
straceで観察してみよう
strace: Linuxでプロセスが
呼んだシステムコールを表示
$ strace <コマンド名>
execve("./a.out", ["./a.out"], [/* 27 vars */]) = 0
…
open("/lib/libc.so.6", O_RDONLY) = 3
…
mmap(NULL, 20466, PROT_READ,
MAP_PRIVATE, 3, 0) = 0x2af2c3b88000
http://funini.com/kei/mmap/
メモリマップドファイルの利用価値 (2)
 多数のプロセスが大きなファイルをアクセス
する場合
共有マッピング
: 常に物理ページが共有される
プライベートマッピング : 書き込まれるまで物
理ページが共有される
 malloc()したメモリにread()でデータを読み
込む場合よりもメモリの節約になる
さらに，メモリコピーが発生しない分高速
http://funini.com/kei/mmap/
read vs. mmap
 二つのプロセスA,
Bが同じファイルをread()
する場合と，mmap()する場合を比較
malloc & read()
buf = malloc(SIZE);
f = open(“dict.txt");
read(f, buf);
do_something(buf);
ファイル
キャッシュ
物理メモリ
プロセスA
アドレス空間
mmap()
f = open(“dict.txt");
buf = mmap(0, f, …);
do_something(buf);
ファイル
キャッシュ
物理メモリ
プロセスA
アドレス空間
コピー
file
コピー
プロセスB
アドレス空間
file
プロセスB
アドレス空間
http://funini.com/kei/mmap/

Download Report