【幕張読書会】Unixカーネルの設計 3(バッファキャッシュ)
- 3. 前回の復習(2) プロセスの状態遷移 ● 実行中(ユーザモード) ● 実行中(カーネルモード) ● 休眠状態 ● 実行可能状態 本書のカーネルはカーネルモード実行中はコンテ キストスイッチしない。割り込みはかかるが必要に 応じて禁止することも。いずれもカーネル空間の データ破壊を防ぐため
- 4. バッファキャッシュ概要 ● ブロックデバイスの内容をメモリに保持 ● データをブロック単位で管理 ● ヘッダ部とデータ部。ヘッダ重要 ● ハッシュと双方向リンクリストで管理 ● LRU(Least Recently Used)
- 5. 意識しておくこと ● ディスクに対してメモリは圧倒的に高速 ● 非同期書込してよければそうしたい(高効率) ● ディスクとバッファキャッシュの整合性 ● ディスクへの非同期書き込み完了は割り込みコ ンテキストで処理される(随所で割り込まれ、 バッファが操作される)
- 6. バッファヘッダ ● デバイス番号(簡単のため以後省略) ● ブロック番号 ● データ部へのポインタ ● バッファ状態変数(ロック中、要遅延書込等) ● ハッシュ用リストポインタ*2(prev,next) ● 自由リスト用ポインタ*2
- 8. ハッシュ(1) ● デバイス番号、ブロック番号をキーとした高速な アクセス用 ● ブロック番号 mod ハッシュサイズ でリストヘッド (番兵)を特定 m1 m6 m0 m2 15 6 7 44 92 41 14 2 29 13 35 58 20 42 72 … … … … 16 ブロック92にアクセスした い場合は 92 mod 7 = 1 な ので、このリストを探す
- 9. ハッシュ(2) ● リスト内は線形検索。順序なし ● ふたつ以上のバッファが同じブロック内容を保 持することはできない(整合性のため) ● (補足)リストの最後は番兵にループ m1 m6 m0 m2 15 6 7 44 92 41 14 2 29 13 35 58 20 42 72 … … … … 16 このリストをたどって (線形 検索して)92に到達。存在 しなければキャッシュミス。
- 10. 自由リスト(1) ● {再,新規}割当て可能なバッファのリスト ● System起動時、全バッファはここに繋がる ● 一度有効なデータ(ブロック)を保持するとハッ シュにもつながれる(下図) m1 m6 m0 FL m2 15 6 7 44 92 41 14 2 29 13 35 58 20 42 72 … … … … 16
- 12. 自由リスト(3) ● ハッシュを検索してヒットした場合は自由リスト の途中からとりだされる ● {新規,再}割り当ての際、先頭から取り出す ● つまり古いバッファから再利用 → LRU! m1 m6 m0 FL m2 15 6 7 44 92 41 14 2 29 13 35 58 20 42 72 … … … … 16 キャッシュヒットの場合は 途中からはずす キャッシュミスした場合は自由 リストの先頭を取り出して目的 のブロックに再割当て
- 16. インターフェース ● getblk バッファを割り当てて取得(←重要) ● brelse バッファを自由リストに戻す ● bread ブロック読み込み ● breada ブロック先読み ● bwrite ブロック書き込み
- 17. getblk (1) ● ブロックをキーとして呼び出される ● 戻り値は当該ブロックに対応するバッファ ● まずハッシュを検索 ● ロックされてなければそれをreturn ● されてる場合は解除を待ってやり直し ● ハッシュ内に見つからなければ、自由リストから の取り出しへ
- 18. getblk (2) ● 自由リストの先頭を取り出す ● 遅延書き込みフラグが立ってなければそれを return ● 立っていたら書き込み依頼してやりなおし それでは擬似コードをどうぞ
- 19. Case1: ハッシュから取り出し ● ハッシュ内にバッファを見つけ、ロックされてな かったケース m1 m6 m0 FL m2 15 6 7 44 92 41 14 2 29 13 35 58 20 42 72 … … … … 16 ブロック番号72を取り出すとす る。 まず 72 mod 7 ≡ 2 なので m2 リストを探す ブロック72のバッ ファが見つかっ た！
- 20. Case1: ハッシュから取り出し ● バッファをロックして ● 自由リストから取り除いて ● 該当バッファをreturn m1 m6 m0 FL m2 15 6 7 44 92 41 14 2 29 13 35 58 20 42 72 … … … … 16 ロック(状態変数に使用中のフ ラグをたてる)して 自由リストから取り除く
- 21. Case2:自由リストから再利用 ● ハッシュ内にバッファが見つからず、自由リスト から再利用するケース m1 m6 m0 FL m2 15 6 7 44 92 41 14 2 29 13 35 58 20 42 72 … … … … 16 ブロック番号8を取り出すとす る。 まず 8 mod 7 ≡ 1 なので m1 リストを探す リストを一周して もブロック8の バッファは見つ からなかった
- 24. Case2:自由リストから再利用 ● 遅延書き込みフラグが立っていないことを確認 (立ってたらCase3) ● ハッシュから取り除く m1 m6 m0 FL m2 15 8 7 44 92 41 14 2 29 13 35 58 20 42 72 … … … … 16 遅延書き込みフラグなし 6 → 8用のバッファにする
- 25. Case2:自由リストから再利用 ● ハッシュの新しい位置に挿入 ● バッファをreturn m1 m6 m0 FL m2 15 8 7 44 92 41 14 2 29 13 35 58 20 42 72 … … … … 16 8は m1 リストにあるべきなの で、ここにつなぐ
- 27. Case3:遅延書き込み ● とりだした6のバッファには遅延書き込みフラグ が立っていた＝再利用できない ● ディスクへの書き込みを依頼してハッシュを探す ところからやり直し m1 m6 m0 FL m2 15 6 7 44 92 41 14 2 29 13 35 58 20 42 72 … … … … 16 遅延書き込みフラグ ON＝再利 用不可。 ディスクへ書き込み依頼
- 31. Case3:遅延書き込み(ポイント) ● ディスクの書き込みは遅いので完了を同期的に 待つより別のバッファを探したほうが速い ● それに、スリープしてしまうと目覚めたときに別 のプロセスコンテキストによりバッファがロックさ れている可能性があり、書き込まれたバッファを そのまま使えない ● → 結局while文をやりなおすしかない
- 33. Case4:自由リストが空 ● このケースも目覚めたらwhile文やりなおし ● このプロセスコンテキストが目覚める前に、一緒 に目覚めた別のコンテキストが実行可能状態に なり、バッファを同じブロックに割り当てる可能 性に対応するため ● 言い換えると、目覚めた後ハッシュを確認せず に自由リストを使うと二重割り当てしてしまうか ら
- 35. Case5: ハッシュから取り出し ● 要求ありのフラグをバッファに立てて、アンロッ クを待ってスリープ ● 目覚めた後はwhile文をやり直し ● 理由はCase3,4と同様 m1 m6 m0 FL m2 15 6 7 44 92 41 14 2 29 13 35 58 20 42 72 … … … … 16 要求あり
- 36. インターフェース ● getblk バッファを割り当てて取得 ● brelse バッファを自由リストに戻す ● bread ブロック読み込み ● breada ブロック先読み ● bwrite ブロック書き込み
- 37. brelse (1) ● ロックされたバッファを引数に呼び出される ● 戻り値はなし ● 自由リストのバッファ追加まちのプロセスを起こ す ● 引数バッファのアンロックまちのプロセスを起こ す
- 38. brelse (2) ● 割り込みを禁止して ● 有効なデータが入っていて、古くないバッファは 自由リストの最後に ● そうでない(IOエラーや遅延書き込み後)バッファ は自由リストの先頭につなぐ ● 割り込み禁止を解除してバッファをアンロック
- 39. インターフェース ● getblk バッファを割り当てて取得 ● brelse バッファを自由リストに戻す ● bread ブロック読み込み ● breada ブロック先読み ● bwrite ブロック書き込み
- 40. bread ● ブロック番号を引数にして、データを読み込んだ バッファを返す ● バッファの取得にはgetblk()を使用 ● バッファに有効なデータが乗っていればそのま まもどし、乗ってなければディスクから読み込ん で戻す ● シーケンシャルに読み込む場合は次のブロック をバッファに載せたい→breada
- 41. インターフェース ● getblk バッファを割り当てて取得 ● brelse バッファを自由リストに戻す ● bread ブロック読み込み ● breada ブロック先読み ● bwrite ブロック書き込み
- 42. breada ● ブロック番号を引数にして、データを読み込んだ バッファを返す(breadと同じ) ● ただし、引数のブロック番号の次のブロックにも 非同期で読み込みをディスクに依頼する ● 详细は拟似コードで
- 43. インターフェース ● getblk バッファを割り当てて取得 ● brelse バッファを自由リストに戻す ● bread ブロック読み込み ● breada ブロック先読み ● bwrite ブロック書き込み
- 44. bwrite ● バッファを引数にして、そのバッファのデータを ディスクに書き込む ● 同期書き込みの場合はバッファのアンロック brelse()まで実施 ● 遅延書き込みの場合は「内容が古いフラグ」を たてて、割り込みコンテキストからbrelse()でア ンロックされた場合に自由リストの先頭に追加さ れるようにする
- 45. まとめ&感想 ● バッファキャッシュは最近アクセスしたものを キャッシュに載せておく(LRU) ● 自由リストの順番が「長く使ってない順」そのも の ● ハッシュと二重リンクリストの性質をうまく使って いる ● コンテキストスイッチと割り込み怖い