先読み、遅延書き込みを行うための機能
「UNIXカーネルの設計」の３章 バッファキャッシュに構造やロジックが記載されています。
本日の内容を理解するのに役立ちます。お持ちの方は参照ください。
http://www.amazon.co.jp/UNIX%E3%82%AB%E3%83%BC%E3%83%8D%E3%83%AB%E3%81%AE%E8%A8%AD%E8%A8%88-Maurice-J-Bach/dp/4320025512
・遅延書き込み
ディスクIOを減らすために、書き込みの命令があってもすぐには書き込まずにメモリに保持しておいてまとめて書く。
⇒DBなどでも良くあります。
当時のUNIXのハードウエアは現在のマイコン並みの性能しかなかったので色々工夫したのだと思います。
⇒メインフレームの世界ではありえない。書き込み命令が来たらすぐ実行して終了させなければならない。
・先読み
ディスクから読み込んだ時に、次使いそうなデータも先に読んでおく。
参照するのは、buff.c、bio.c
です。
まずはバッファキャッシュの構造から
http://www.tamacom.com/tour/kernel/unix/S/52.html
21 struct buf
22 {
23 int b_flags; /* see defines below */
24 struct buf *b_forw; /* headed by d_tab of conf.c */
25 struct buf *b_back; /* " */
26 struct buf *av_forw; /* position on free list, */
27 struct buf *av_back; /* if not BUSY*/
28 dev_t b_dev; /* major+minor device name */
29 unsigned b_bcount; /* transfer count */
30 union {
31 caddr_t b_addr; /* low order core address */
32 int *b_words; /* words for clearing */
33 struct filsys *b_filsys; /* superblocks */
34 struct dinode *b_dino; /* ilist */
35 daddr_t *b_daddr; /* indirect block */
36 } b_un;
37 daddr_t b_blkno; /* block # on device */
38 char b_xmem; /* high order core address */
39 char b_error; /* returned after I/O */
40 unsigned int b_resid; /* words not transferred after error */
41 };
b_flagsは、そのバッファの状態を示すフラグです。後の関数で色々出てきます。
定義は
46 /*
47 * These flags are kept in b_flags.
48 */
49 #define B_WRITE 0 /* non-read pseudo-flag */
50 #define B_READ 01 /* read when I/O occurs */
51 #define B_DONE 02 /* transaction finished */
52 #define B_ERROR 04 /* transaction aborted */
53 #define B_BUSY 010 /* not on av_forw/back list */
54 #define B_PHYS 020 /* Physical IO potentially using UNIBUS map */
55 #define B_MAP 040 /* This block has the UNIBUS map allocated */
56 #define B_WANTED 0100 /* issue wakeup when BUSY goes off */
57 #define B_AGE 0200 /* delayed write for correct aging */
58 #define B_ASYNC 0400 /* don't wait for I/O completion */
59 #define B_DELWRI 01000 /* don't write till block leaves available list */
60 #define B_TAPE 02000 /* this is a magtape (no bdwrite) */
61 #define B_PBUSY 04000
62 #define B_PACK 010000
キャッシュバッファは双方向リストを２つ持っています。
b_forw:キャッシュの前方(forword)
b_back:キャッシュの後方(back)
av_forw:フリーリストの前方(forword)
av_back:フリーリストの後方(back)
28 dev_t b_dev; /* major+minor device name */
メジャー番号（８ビット）とマイナー番号（８ビット）を並べて１６ビットで格納しています。
メジャー番号がデバイスドライバの識別に使われ、マイナー番号がそのドライバが制御する個々の機器の識別に使われます。
そのため、256個の装置を識別できます。
37 daddr_t b_blkno; /* block # on device */
ブロックが識別した装置のどの位置にあるかを示しています。
つまり「b_devとb_blknoでどのデバイスのどのブロック番号か特定できる。」 ことになります。
ファイルの読み込み
１、ファイルのOpen
システムコール：openを呼び出します。
File Descriptor(FD)と呼ばれる小さな整数を返します。
http://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A1%E3%82%A4%E3%83%AB%E8%A8%98%E8%BF%B0%E5%AD%90
２、ファイルのRead
システムコールのreadを呼び出します
FDをFP(FilePointer)に変換します。
FPの定義は以下
http://www.tamacom.com/tour/kernel/unix/S/58.html#L8
FPからinodeへのポインタを取得します。
inodeへのポインタをパラメータとして、readiを呼び出します。
３、readi
http://www.tamacom.com/tour/kernel/unix/S/94.html#L19
bmap関数でbn（b_blkno）を取得
52 bn = bmap(ip, bn, B_READ);
inodeへのポインタからi_dev（b_dev）を取得
55 dev = ip->i_dev;
breadを呼び出します。
64 bp = bread(dev, bn);
●キャッシュのアルゴリズム
bread
http://www.tamacom.com/tour/kernel/unix/S/18.html#L56
１、キャッシュヒット（一番実行時間が短い）
パラメータとして受け取った、dev, blknoを引数として、バッファキャッシュの中を探します。
getblk
http://www.tamacom.com/tour/kernel/unix/S/18.html#L238
バッファの中に一致するものがあればそのバッファを、一致するものばなければ、一番古くて空いているバッファを返します。
受け取ったバッファの状態が「B_DONE」であれば、それを返します。
62 bp = getblk(dev, blkno);
63 if (bp->b_flags&B_DONE) {
64 #ifdef DISKMON
65 io_info.ncache++;
66 #endif
67 return(bp);
68 }
２、キャッシュヒットしたが誰かが使っている。
getblkで、そのバッファが欲しいという印を付けて、スリープして、待つ。
260 if (bp->b_flags&B_BUSY) {
261 bp->b_flags |= B_WANTED;
262 sleep((caddr_t)bp, PRIBIO+1);
263 goto loop;
264 }
他の誰かが処理が終わって、wakeupを呼ぶとsleepが解除される。
念のため、もう１回やってみてから、処理を続行する。
⇒若干原始的
３、キャッシュ上にない（ディスクを読む）
B_READをセットして、d_strategyに読み込みの依頼をして、iowaitで待ちます。
iowaitはスリープしているだけです。
d_strategyがデバイスドライバとの境目になります。
69 bp->b_flags |= B_READ;
70 bp->b_bcount = BSIZE;
71 (*bdevsw[major(dev)].d_strategy)(bp);
72 #ifdef DISKMON
73 io_info.nread++;
74 #endif
75 iowait(bp);
76 return(bp);
●先読み
breada aはaheadの略
http://www.tamacom.com/tour/kernel/unix/S/18.html#L84
基本はbreadと同じです。
パラメータが１個増えています。（先読み用のブロックを指定）
今回読みたいブロック、breadと同じです
94 bp->b_flags |= B_READ;
95 bp->b_bcount = BSIZE;
96 (*bdevsw[major(dev)].d_strategy)(bp);
先読みしたいブロック、B_ASYNCを設定します。これは非同期を設定しています。
107 rabp->b_flags |= B_READ|B_ASYNC;
108 rabp->b_bcount = BSIZE;
109 (*bdevsw[major(dev)].d_strategy)(rabp);
今回読みたいブロックだけ、待ちます。読み終わったらリターンします。
先読みしたブロックの読み込みは待ちません（非同期）
117 iowait(bp);
118 return(bp);
先読みしたいブロックは、今回読みたいブロック＋１を指定しているので、次のreadの時には、先読みしたいブロックが既に読み込み中かもしくは、読み込みが終わってバッファ上にあるという動作を期待しています。
●遅延書き込み
書き込みは後でゆっくり、印だけつけといてリターン
137 if ((flag&B_ASYNC) == 0) {
138 iowait(bp);
139 brelse(bp);
140 } else if (flag & B_DELWRI)
141 bp->b_flags |= B_AGE;
●バッファのLRU
よく使われるバッファはリンクの先へ付け替えます。
使われないバッファはリンクの後ろの方へ残ります。
●バッファサイズ
V7ではどれくらいbufの領域を用意するかということをカーネルのビルド時に固定的に決めていた。
不適切な値にするとパフォーマンスが出ないということがあった。
⇒以降のUNIXの発展でこれが動的になるように変更された。
0 件のコメント:
コメントを投稿