Linux2.4でのメモリ管理機構 - M.F Workshop

Linux2.2 on x86 での
メモリ管理機構
Dec 2001
安田泰勲
目次
• x86アーキテクチャにおけるメモリ管理
– セグメンテーションとページング
– アドレッシング
• Linux におけるメモリ管理
– Linuxのメモリ管理の用語
– アドレス空間モデルとデータ構造
– ページングの流れ
– ページング処理(demand paging, copy on write…)
– メモリ領域管理(buddy system, slab allocator)
x86アーキテクチャの
メモリ管理機構
• x86アーキテクチャでは二種類のメモリ管理
機構が利用可能
– セグメンテーション機構
• 複数のタスク(プロセス)が相互に干渉しないで同じプロ
セッサ上で実行できる様にコード、データ、スタックを
分離する機構(required)
– プロセス(=セグメント)毎に異なるリニアアドレス空間を
利用
– ページング機構
• 従来のデマンドページの仮想記憶システム(プログラムの
実行環境のページが必要に応じて物理メモリにマップさ
れる)を使用するための機構(optional)
– プロセス毎に同じリニアアドレス空間を利用
メモリアドレッシング
• x86アーキテクチャでのメモリアドレス
– Physical address(物理アドレス)
• プロセッサがアドレスバス上で指定できるアドレス空間。フラット(セ
グメント化されていない)であり、連続領域(0x0 -0xFFFFFFFFh)
4G(2^32)バイトの物理アドレス空間が利用可能。
– Linear address(リニアアドレス)
• 32bit で表現されるリニアアドレス空間内のページング機構でのアド
レス。物理アドレスと同様にフラットでセグメント化されていない。プ
ロセッサは論理アドレスをリニアアドレスに変換してからメモリにアク
セスする。
– Logical address(論理アドレス)
• 16bitのセグメントセレクタと32bitのオフセットで構成されるセグメント
グメント機構でのアドレス
論理アドレス
Segmentation Unit
リニアアドレス
物理アドレス
Paging Unit
セグメンテーションと
ページング
Segmentation
Paging
Logical address
Segment
selector
Segment
Descriptor
Global
Descriptor
Table
Linear address
Directory Table
offset
Linear
Address
Linear
Address
Space
Page
Directory
Entry
Page
Table
Entry
Page
Directory
Page
Table
CR3
offset
Physical
address
Page
x86用語
•
基本フラットモデル
– OS およびアプリケーションは連続したセグメント化されていないアドレス
空間を利用する。コードセグメントおよびデータセグメントが1つの同じリ
ニアアドレス空間にマップされる。
•
ページディレクトリ
– 4K バイトページに入っている 32bit の PDE(ページディレクトリエントリ)
の配列。1024 個までの PDE を保持可能。
•
ページテーブル
– 4K バイトページに入っている 32bit の PTE(ページテーブルエントリ)の
配列。1024 個までの PTE を保持可能。
•
ページ
– 4K バイト, 2M バイト, もしくは 4M バイトのフラットなアドレス空間。メモリ
はページ単位で扱う。
•
TLB (Translation Lookaside Buffer)
– PDE, PTE 用のオンチップのキャッシュ。
Linuxでのセグメンテーションと
ページングの利用
• Linuxではセグメント機構はほとんど利用せず、ペー
ジング機構を利用
– セグメント機構とページング機構を両方利用することは冗長
– 同じリニアアドレス空間を利用することによってメモリ管理
機構をシンプルにできる
– 他のアーキテクチャへの移植性を保つため
• RISCチップには限定的なセグメント機構しか持たない者
もある
1つの大きなセグメント内にプロセス毎に同じ
仮想アドレス空間というモデル
Linux でのメモリ管理の特徴
• 仮想アドレス空間のサポート
– 抽象化したメモリモデルを用いた広大な仮想アドレス空間が利
用可能にする
• デマンドページング／コピーオンライト
– フリーページを実際のアクセス時に仮想アドレス空間に割り当
てることによって使用効率／パフォーマンスを向上する技術
• スワッピング
– フリーページが足りない場合、使用中のページを一時的にス
ワップ領域に退避し、フリーページを確保することによって実
際の物理メモリより多くのメモリを利用可能にする
• 多様なキャッシュのサポート
– フリーページを多様なキャッシュに利用することによってパ
フォーマンスを向上する
Linuxで実装されている
キャッシュ
• バッファキャッシュ(buffer cache)
– ブロックデバイスから読み書きするデータ用のキャッシュ。全ての
ブロックデバイスはバッファキャッシュを経由してデータを取得す
る。ブロック単位で扱う。デバイス ID とブロック番号でアクセス。
• ページキャッシュ(page cache)
– ディスク上のイメージやデータを読み書きを高速化する(mmap し
たfileへのアクセス等)時に利用されるキャッシュ。ページ単位で
扱う。ファイル名とオフセットでアクセス。
• スワップキャッシュ(swap cache)
– スワップインされてから変更されていないページのページテーブ
ルエントリとフラグ(ページとスワップファイルの情報)のキャッシュ。
ページ単位で扱う。スワップファイルへの書出しを効率化するた
めに用いる。
メモリマップと
ページテーブル
• ページテーブル
– Linux では 64bitアドレス空間に対応できるように3 段のページ
テーブル(PGD, PMD,PTE)を持っている
• alpha は3段であるためそのまま利用
• x86 は 2 段であるため、PMD は何もしない仮想的なテーブルになっ
ている(メモリ上に存在しない)。x86 ではページテーブルはページン
グ対象外であり、物理メモリ上にマップされたカーネル空間に常に
存在する
• メモリマップ
– 物理メモリはPAGE_OFFSET(0xC0000000h)以降にマップ
– カーネルは全てのプロセスの仮想アドレス空間の
PAGE_OFFSET からストレートマップされる
• セグメントのプロテクション機能などの対象外
• 1GB以上の物理メモリを利用する場合にはPAGE_OFFSETをずらす
Linuxのメモリマップ(32bit)
プロセス毎の
仮想アドレス空間
0x00000000
text
text
text
data
data
data
bss
bss
bss
heap
heap
heap
0x40000000
ディスク
File
System
Swap
0xc0000000
kernel
stack
kernel
stack
stack
stack
*.so
*.so
*.so
mapped
mapped
mapped
vmalloc space
0xc0000000
stack
stack
stack
High mem
物理メモリ
0xffffffff
2レベルページング(x86)
Linear Address
31
22 21
Directory
12 11
Table
Page Table
Page
Directory
CR3
0
Offset
Page
3レベルページング(Linux)
Linear Address
Global Dir
Middle Dir
Table
Offset
Page
Page Global
Directory
CR3
Page Middle
Directory
Page Table
※x86 Linuxでは PMDはメモリ上に存在しない
(PGDからのアクセスはスルーしてPTにいく)
アドレス空間モデル
task_struct
mm_struct
mmap
pgd
vm_area_struct
vm_next
vm_file
vm_start
vm_end
vm_area_struct
vm_next
vm_file
vm_start
vm_end
NULL
NULL
mm
PTE
PGD
virtual address space
PTE
PMD
Page cache
File system
Physical memory
Swap cache
Swap device
アドレス空間を管理する
データ構造
• struct task_struct
– プロセスの情報を保持するデータ
• 伝統的UNIX でのu構造体を含むすべてのデータ
– プロセス毎に一つ
• struct mm_struct
– プロセスの仮想アドレス空間を管理するデータ
– プロセス毎に一つ
• task_struct からポイントされる
• struct vm_area_struct
– プロセスの仮想アドレス空間内のある連続領域を管理するデータ
– 仮想アドレス空間毎に複数存在し、それぞれの領域(vm_area_struct)
が線形リスト／AVL ツリーで連結されている
• 先頭のデータは mm_struct からポイントされる
アドレス空間の複製
• fork(2)時に複製
– init 以外はすべてこれを利用
• 複製処理の流れ(kernel/fork.c)
– 1) 新規に mm_struct{}を確保し、内容は親プロセスのものを
コピー(copy_ mm())
– 2) 親プロセスのもつメモリを全てコピーオンライトでマッ
プし直す(dup_mmap())
• PTEにおいて全てのページをReadOnly属性にする
– Read時: 問題無し
– Write時: Page Fault 発生。コピーオンライト処理を実施
アドレス空間の生成と解放
• execve(2)時に生成
• 生成処理の流れ(fs/exec.c)
– 1) 古いmm_struct の内容を破棄し、初期化する(exec_mmap())
– 2) プログラムをロードし、新しく生成したアドレス空間に
mmapする
• vm_area_struct は mmap処理内(do_mmap())で生成される
• それ以外の領域についてはデマンドページングで処理される
(ページは割り当てられない)
• exit(2)時に解放
• 解放処理の流れ(kernel/exit.c)
– 1) mm_struct の解放(exit_mm())
ページングの流れ
Page faultのハンドリング
YES
YES
Does the address
belong to the process
address space?
Does the access type
match the memory
region access right?
Legal access:
Allocate a new
Page frame
NO YES
Illegal access:
Send a SIGSEGV
signal
handle_mm_fault()
NO
Did the exception
occur in User Mode?
Kernel bug:
Kill the process
NO
Page fault
In interrupt or YES
kernel thread
NO
YES
Address in
Memory region
NO
Address could
Belong to user
Mode stack
YES
YES
Write access
NO
NO
YES
Region is
writable
YES
Copy on
write
NO
Page is present
Region is
readable or
executable
Demand
Paging
NO
Send
SIGSEGV
YES
YES
NO
Kernel process
And kernel
“Oops”
NO
In user mode
Address is a
wrong system
call parameter
“Fixup code”
(typically send
SIGSEGV)
NO
YES
ページングの流れ
ページ割り当て (1)
NO Is the PTE present? YES
Demand
paging
invoke
NO
do_no_page()
NO
Is the PTE empty?
Have a file already
mapped?
invoke
do_anonymous_page()
YES
NO
Write access?
Allocate a page & 0 clear
& Set PTE as writable
※3
invoke
do_swap_page()
YES
※2
invoke
vma->vm_ops->no_page()
※1
Mapped ZERO_PAGE
& Set PTE as ReadOnly
ページングの流れ
ページ割り当て(2)
Demand
paging
※1
NO
invoke
page_cache_read()
Allocate a page
& Set PTE &
load the file
Found the page
in page cache?
NO
load the file
YES
Is the cache valid?
NO
Allocate a page
& Set PTE &
load the file
YES
Is the page to be YES
shared?
Set PTE as
shared page
ページングの流れ
ページ割り当て(3)
※2
Demand
paging
NO
invoke
swap_in()
NO
Is read access
or shared?
Set PTE with
Writable&dirty
Is present
vm_ops->swapin?
YES
YES
Set PTE
YES
Is swap cache
present?
NO
Make a swap
cache
ページングの流れ
ページ割り当て(4)
※3
Set PTE & aging
NO
Do nothing
YES
Is write access?
NO
YES invoke
Is writable page?
do_wp_page()
Set PTE with
dirty flag
※4 Copy on write
ページングの流れ
ページ割り当て(5)
Copy on write
NO
Set PTE as writable
&dirty (copy no page)
※4
Does multiple
Processes refer
the page?
YES
Allocate a page &
Set PTE as writable &
Copy data from old page
デマンドページング
(Demand Paging)
• 仮想アドレス空間の生成時、実際にアクセスがあるまで物理
ページの割り当てを遅らせるメモリ割り当て手法
– メリット
• 仮想空間生成時のCPUのオーバヘッドが少ない
• 物理メモリの利用効率向上
– デメリット
• Page fault 時のCPUのオーバヘッドが重い
– 採用理由
• ローカリティの原理からpage faultはレアなイベントである
• プロセスは少ないアドレス空間のみ利用する
– Linuxでは仮想アドレス空間生成時にはPTE 作成するがペー
ジはNULLを指す
• 実際のアクセス時に page faultが発生
コピーオンライト
(Copy on Write)
• 仮想アドレス空間の複製時、実際に書き込みアクセスがあるまで
ページのコピーを遅らせるメモリ割り当て手法
– メリット
• 仮想空間複製時のCPUのオーバヘッドが少ない
• 物理メモリの利用効率向上
– デメリット
• Page fault 時のCPUのオーバヘッドが重い
– 採用理由
• 読み込みのみのページは永続的に共有可能
• 仮想空間複製直後に破棄されることが多い
– Linuxでは仮想アドレス空間複製時、当該空間にマップされて
いるページを全てReadOnlyで両方の空間からマップし直す
• 書き込み時に page fault が発生 -> Copy on Write 処理へ
スワップ処理
(Swapping)
• 空き物理ページが少なくなった時に、使用中の物理ページを二次記
憶に退避し、利用可能な物理ページを確保する技術
– メリット
• プロセスが実際に利用可能なアドレス空間を拡張できる
• プロセス実行時に割り当て可能な物理メモリを増やすことができる
– デメリット
• スワッピング処理のCPUのオーバヘッドが大きい
– 物理メモリが極端に少ない場合にスラッシングが発生し、システムの
応答性が極端に下がる
– 採用理由
• 大きな／多くのプロセスが動かせるメリットが大きい
– Linuxではプロセスレベルではなくページレベルのスワッピング
を実現
• CPUのページング機構を利用して実装
犠牲ページの決定
アルゴリズム
• 基本は LRU (Least Recently Used)ベース
– ただし厳密なLRUではない
• x86ではチップのサポートが不十分(アクセスビットのみ)
– Linux x86ではアクセスビットを利用したagingで実現
• 当該ページにアクセスすると、チップがページテーブルのアク
セスビットをたてる
• スワップ用のフリーページの検索時、アクセスビットが立って
いればビットは落とされる(その時はページは解放されない)
• スワップ用のフリーページの検索時、アクセスビットが立って
いなければ犠牲ページ候補となる
– 優先度毎にも最も利用物理ページ数が多いプロセスから犠牲
ページの決定を実施
スワップ処理の流れ
The page fault handler
must swap in a page
A page must be swapped
out
swap_out()
do_swap_page()
swap_out_process()
swap_in()
swap_out_vma()
swapin_readahead()
swap_out_pgd()
read_swap_cache_async()
swap_out_pmd()
try_to_swap_out()
rw_swap_page()
Low-level swapping function
brw_page()
Block device driver function
フリーページの取得処理
(1)
• do_try_to_free_pages()
– try_to_free_pages() -> do_try_to_free_pages()
– 物理ページ割り当て処理部や kswapd から呼ばれる
for (priority = 6;priority; priority--) {
while (shrink_mmap(priority,gfp_mask)) { /* ページキャッシュの解放 */
if (空きページが十分) return;
}
while (shm_swap(priority ,gfp_mask)) { /* 共有メモリの解放 */
if (空きページが十分) return;
}
while (swap_out(priority,gfp_mask)) { /* スワップアウトによる解放 */
if (空きページが十分) return;
}
shrink_dcache_memory();/* ディレクトリエントリの解放*/
}
フリーページの取得処理
(2)
• swap_out()
for (counter=nr_tasks/(priority+1);counter;counter--) {
int max_cnt=0;
struct task_struct *pbest;
for (init以外のすべてのプロセス) {
if (最近スワップアウトされていない &&
使用物理ページ数 > max_cnt) {
max_cnt = 使用物理ページ数;
pbest = 当該プロセス;
}
}
swap_out_process(pbest,gfp_mask);
}
フリーページの取得処理
(3)
• try_to_swap_out()
– swap_out_process() → … → try_to_swap_out()
if (有効なページがない || 予約／ロックされたページ) { return;}
if (最近アクセスがあった) {
PTE のアクセスビットをクリア; page 構造体の参照ビットをたてる; return;
}
if (スワップキャッシュ上にある) {
スワップキャッシュの参照数をあげる; PTE の設定; __free_page (); return;
}
if (書き込みされていない) {
PTE の設定; __free_page (); return;
}
if (独自swapout 関数がある) {
PTEクリア; swapout 関数を呼び出す; __free_page(); return;
}
空きスワップの検索; PTEの設定; ページの内容をメモリに書き出す; __free_page();
return;
kswapd
• 空きページを作る処理を行う、永続的に動作するカーネルスレッド
– 定期的(1回/秒)に起動あるいは物理ページ割り当て処理部から起
動される
• 空きページ判定の閾値は最大256*3ページ
– 最大物理メモリ量に関係
while (1) {
while (空きページが十分でない) {
if (do_try_to_free_pages(GFP_KSWAPD) {
if (スケジュール必要) {
schedule();
}
}
schedule_timeout(10*HZ);
}
}
メモリ領域管理機構
(1) Buddy system
• 空きページを複数種類のページ数*2のべき乗の単位で管理する
方式
– 領域の split, coalescing が簡単にできるため、要求されたメモ
リサイズにあわせて柔軟な割り当てが可能
• 要求サイズはページサイズ*2のべき乗に切り上げて割り当て
• 必要なサイズのエリアが足りない時は1つ上のサイズのリスト
からもらう(split)
• あるサイズのフリーなエリアの量が過剰な時は1つ上のサイズ
のリストに二個一化にして渡す(coalescing)
– External Fragmentation を解決する一つの方式
• ページ単位でのメモリフラグメンテーションを解決
– Linux x86では 2^0 から 2^9 ページサイズの10種類
メモリ領域管理機構
(1) Buddy system
Buddy system
10 kbytes の
メモリの要求
pager
2^2page*1 の
メモリの割り当て
Free area list
(n *page/block)
n= 2^0
1page
1page
…
n= 2^1
2page
2page
merge
n= 2^2
4page
4page
split
n= 2^3
…
8page
8page
メモリ領域管理機構
(2) Slab allocator
• カーネル内で利用するメモリをオブジェクト単位で扱い、再利
用に最適化したメモリ管理方式
– 再利用による管理オーバヘッドの低下
• ページ単位の管理よりも小さいメモリ領域も扱える
– ハードウェアキャッシュの効率向上
• キャッシュラインを乱さないようなメモリ割り当てを行える
– Internal Fragmentation を解決する一つの方式
• ページより小さいサイズのメモリフラグメントを解決
– e.g.) /etc/slabinfo 参照
• i-node cache, socket buffer, …
メモリ領域管理機構
(2) Slab allocator
Page-level allocator (buddy system)
back end
vnode
cache
active
vnodes
coloring area
N page
free active
proc
cache
active
procs
file
…
cache
Slab allocator
front end
active
files
unused
free active active
NULL
Slab data
Linked
list
メモリ領域管理機構
(2) Slab allocator
• Linux で使われている slab の種類
– カーネル内で利用される各structure用のブロック
• slabinfo,kmem_cache, tcp_tw_bucket, tcp_bind_bucket,
tcp_open_request, inet_peer_cache, ip_fib_hash, ip_dst_cache, arp_cache,
uhci_urb_priv, blkdev_requests, nfs_read_data, nfs_inode_cache,
nfs_write_data, nfs_page, journal_head, revoke_table, revoke_record,
dnotify, file, fasync, uid_cache, skbuff_head_cache, sock, sigqueue,
kiobuf, cdev_cache, bdev_cache, mnt_cache, inode_cache,
dentry_cache, filp, names_cache, buffer_head, mm_struct,
vm_area_struct, fs_cache, files_cache
– 2^{5,6,7,8,9,10,11,12,13,14,15,16,17}bytesのブロック
• 通常／DMA用
– ※ /proc/slabinfo で確認可能
参考文献
• Understanding Linux Kernel
– Daniel P. Bovet & Marco Cesati, O’reilly, 2001
• UNIX Internals: The New Frontiers
– Uresh Vahalia, Prentice Hall, 1996
• Intel Architecture Developers Manual Vol1,2,3
– Intel Corp., 1999
ブート時のメモリ管理
•
起動ステップ 1 (real mode)
– 4MB のアドレススペース用のページテーブルをコンパイル時に初期化
(pg0, arch/kernel/head.S で実施)
• 固定値(static な配列)
• 範囲[PAGE_OFFSET, PAGE_PFFSET+0x3fffff]
–
–
•
※ページングは使えない状態
※起動ステップ 2 に移行後は使用しない
起動ステップ 2 (protect mode)
– paging_init() ルーチンで初期化(swapper_pg_dir[], arch/mm/init.c)
• ページテーブルに PAGE_OFFSET 以降の仮想アドレスに対応する物理アド
レスを書き込む
• 0x0 をアンマップする(NULL Pointer access用の領域となる)
– ※Pentium 以降では 4MB ページテーブルも利用可能

Download Report