ページテーブルとTLB
仮想アドレスをページ番号と位置に分け、ページ表とTLBの対応から物理位置を求めます。
説明
プログラムが使う仮想アドレスは、そのままメモリ装置の位置を表すとは限りません。ページ方式では一定サイズの範囲ごとに物理フレームへ対応付け、ページ内の位置は保ったまま変換します。TLBはその対応を一時的に保存するキャッシュです。
ページサイズ4 KiBのモデルで、16進アドレスのどの部分がページ番号になるかを計算します。続いてTLBのヒット、対応の変更、別プロセスの同じ仮想アドレスを扱い、最後に二段階のページ表の索引を求めます。
1ページ番号とページ内位置
仮想アドレス0x12345を4096で割った商と余りを求めます。4 KiBは4096バイトで、下位12ビットがページ内の位置です。
page_size = 4096; va = 0x12345サイズと仮想アドレス; vpn, offset = divmod(va,page_size)商と余り; print(hex(vpn),hex(offset))ページ番号と位置; print(format(offset,'012b'))下位12ビット仮想ページ番号は0x12、位置は0x345です。下位12ビット001101000101は変換後も同じ値を使います。仮想ページ0x12の先頭は0x12000で、その先頭から0x345バイト目にあります。
2物理フレームへ対応付ける
ページ表で仮想ページ0x12を物理フレーム0xabへ対応させます。フレーム番号にページサイズを掛け、位置を足します。
page_table = {0x12:0xab,0x13:0x41}ページとフレームの対応; pa = page_table[vpn]*page_size+offset物理アドレス; print(hex(pa))変換結果; print(hex(pa%page_size))変わらない位置物理アドレスは0xab345です。末尾0x345は変わりません。仮想空間で連続する0x12・0x13の二ページも、物理側では0xab・0x41へ離して置けます。
3境界をまたぐアクセス
0x12ffeから4バイト読む場合を1バイトずつ変換します。途中で仮想ページが変わるため、二つのページ表項目を使います。
for address in range(0x12ffe,0x13002):4バイトの仮想位置
page, pos = divmod(address,page_size)ページと位置; print(hex(address),hex(page_table[page]*page_size+pos))各バイトの変換前半は0xabffe・0xabfff、後半は0x41000・0x41001です。仮想側では連続した4バイトでも、物理側では二つの離れた範囲になります。境界の後半ページにも読取り可能な対応が必要です。
4TLBに対応を保存
TLBを空から始め、同じページを続けて参照します。初回だけページ表を引き、得たフレーム番号を保存します。
tlb = {}空の変換キャッシュ
次のアクセス列ではページ表参照が必要だったかを表示します。TLBはデータ本体を保存するキャッシュではなく、ページの変換情報を保存します。
5TLBヒットとミス
同じページ内の0x12000・0x12004と、別ページ0x13000を変換します。ページ表の対応はすべてメモリにある条件です。
for address in (0x12000,0x12004,0x13000):参照するアドレス列
page,pos = divmod(address,page_size); hit = page in tlbTLBを検索
if not hit: tlb[page] = page_table[page]ミス時にページ表から登録
print(hex(address),'hit' if hit else 'miss',hex(tlb[page]*page_size+pos))検索結果と物理位置最初はミス、次はヒット、別ページはミスです。この二つのミスはページ表を参照して解決でき、ページ内容をディスクから読む処理は発生していません。TLBミスとページフォルトを同じ出来事として数えないようにします。
6ページ表変更後の古い対応
0x12の物理フレームを0xcdへ変更します。TLBに古い0xabが残っている状態を表示してから、該当項目を削除し、更新した表を使います。
page_table[0x12] = 0xcdページ表を変更; print(hex(tlb[0x12]*page_size))残る古い対応; del tlb[0x12]古い項目を無効化; tlb[0x12] = page_table[0x12]表から再取得; print(hex(tlb[0x12]*page_size))新しい対応古い対応は0xab000、新しい対応は0xcd000です。ページ表だけ書き換えても、CPUが保持する変換が自動的に同期するとは限りません。OSはCPUの規則に従ってTLBの無効化を行い、複数CPUが使う対応なら他CPUへの反映も扱います。
7別プロセスの同じ仮想アドレス
ASIDはアドレス空間の識別に使われます。ここではASID1と2の同じページ番号0x12を別のTLB項目として保存します。
tagged = {(1,0x12):0xcd,(2,0x12):0x33}空間番号とページ番号の組; print([hex(tagged[(asid,0x12)]*page_size+0x345) for asid in (1,2)])二つの空間で変換同じ0x12345でも0xcd345と0x33345へ変換されます。ページ番号だけをキーにすると取り違えるため、識別タグや切替時の無効化が必要です。タグの名称や利用方法はCPUによって異なります。
8二段階のページ表の索引
32ビットの仮想アドレスを上位10ビット、次の10ビット、下位12ビットへ分ける構成を考えます。0x12345678から各索引を取り出します。
address = 0x1234567832ビットの入力; outer = (address>>22)&0x3ff上段の10ビット; inner = (address>>12)&0x3ff下段の10ビット; pos = address&0xfffページ内12ビット; print(outer,inner,hex(pos))索引と位置; print(hex((outer<<22)|(inner<<12)|pos))元の値へ結合索引は72と837、位置は0x678です。上段72の項目が下段の表を指し、その表の837番目からフレームを得ます。逆に三つを結合すると元のアドレスに戻ります。ページ表の段数や索引幅は採用するアドレス方式で変わります。
まとめ
ページ変換ではページ番号をフレーム番号へ置き換え、ページ内の位置は保ちます。
TLBミスは変換情報がない状態であり、ディスク読込みを伴うページフォルトとは別です。
ページ表の変更やプロセスの切替では、古い変換や別空間の変換を使わない仕組みが必要です。
操作履歴と解説を振り返れます。
Python 3
page_size = 4096; va = 0x12345; vpn, offset = divmod(va,page_size); print(hex(vpn),hex(offset)); print(format(offset,'012b'))0x12 0x345 001101000101
page_table = {0x12:0xab,0x13:0x41}; pa = page_table[vpn]*page_size+offset; print(hex(pa)); print(hex(pa%page_size))0xab345 0x345
for address in range(0x12ffe,0x13002):
page, pos = divmod(address,page_size); print(hex(address),hex(page_table[page]*page_size+pos))0x12ffe 0xabffe 0x12fff 0xabfff 0x13000 0x41000 0x13001 0x41001
tlb = {}
for address in (0x12000,0x12004,0x13000):
page,pos = divmod(address,page_size); hit = page in tlb
if not hit: tlb[page] = page_table[page]
print(hex(address),'hit' if hit else 'miss',hex(tlb[page]*page_size+pos))0x12000 miss 0xab000 0x12004 hit 0xab004 0x13000 miss 0x41000
page_table[0x12] = 0xcd; print(hex(tlb[0x12]*page_size)); del tlb[0x12]; tlb[0x12] = page_table[0x12]; print(hex(tlb[0x12]*page_size))0xab000 0xcd000
tagged = {(1,0x12):0xcd,(2,0x12):0x33}; print([hex(tagged[(asid,0x12)]*page_size+0x345) for asid in (1,2)])['0xcd345', '0x33345']
address = 0x12345678; outer = (address>>22)&0x3ff; inner = (address>>12)&0x3ff; pos = address&0xfff; print(outer,inner,hex(pos)); print(hex((outer<<22)|(inner<<12)|pos))72 837 0x678 0x12345678
演習完了