UNIX 6th code reading - ディスクキャッシュの効率化

はじめに

前回のエントリでバッファの状態遷移図を描きました。

それに関連して、ブロックバッファはディスクキャッシュとして効率化が図られているということをまとめます。

ディスクキャッシュの効率を高めるには

B_DONEフラグが立っているとき、そのバッファはキャッシュとして働きディスクへのアクセスを行いません。

B_DONEは読み出し・書き込みが行われるとセットされます。読み出しを行うと、そのバッファには最新のデータが格納されます。書き込みを行うと、そのバッファにはデバイス内と同じデータ、もしくはデバイスより新しいデータが入っている状態になります。(書き込みを行っている最中はB_DONEが外れますが、そのときはB_BUSYなので他プロセスは使えません。書き込みが終わればB_DONEフラグが立つので、キャッシュとしての機能を考えるときは無視します)

ではB_DONEが外れるのはいつか。それはgetblk( )でav-listから再割り当てが行われるときです。

なので、よく使うブロック(バッファ)の再割り当て頻度が減ると、それだけキャッシュとしての効率が高まります。

v6ではav-listがLRUになっていることで、これを実現しているようです。

av-listはLRU

av-listはLRUであるということを絵で説明してみます。

av-listの先頭バッファが再割り当てされます。(getblk( )参照)

使用するバッファ(B_BUSY)はav-listから取り除かれます。(notavail( )参照)

av-listに戻すバッファ(B_BUSYがリセット)は、av-listの最後尾につけられます。(brelse( )参照)

つまり、よく使われるバッファはav-listの後方でうろうろすることになるので、あまり再割り当てされません。使わないバッファほどav-listの先頭に出てきます。

LRUを実現するためにリンク構造を取っている？

av-listはリンク構造を取っているため、av-listから取り出すとき、av-listに戻すとき、それぞれCレベルで数命令で済みます。

もしproc[ ]などと同じように、単なる配列の構成になっていたら、取り出しのときに最悪の場合全要素シフトする必要があります。もしくは各バッファが最後に使用された時間をそれぞれ保持し、全探査して最も使用されていないバッファを探し出す必要があります。

高速動作のためにリンク構成にしたのではないかと思います。

(simulationでリンク構成と単純な配列構成の差異を見ると楽しそうです)

終わりに

バッファの状態遷移図を眺めていたところ、キャッシュの効率化が図られていることに気づいたのでまとめてみました。

次回こそ本当にファイルシステムに入ります。