定义哈希表的结构体，bcache.lock为表级锁，而hashtable[i].lock为桶级锁：
#define NBUCKET 13 #define NBUF (NBUCKET * 3) struct { struct spinlock lock; struct buf buf[NBUF]; } bcache; struct bucket { struct spinlock lock; struct buf head; }hashtable[NBUCKET]; int hash(uint dev, uint blockno) { return blockno % NBUCKET; }在binit函数中对哈希表进行初始化，将bcache.buf[NBUF]中的块平均分配给每个桶，记得设置b->blockno使块的hash与桶相对应，后面需要根据块来查找对应的桶。
void binit(void) { struct buf *b; initlock(&bcache.lock, "bcache"); for(b = bcache.buf; b < bcache.buf+NBUF; b++){ initsleeplock(&b->lock, "buffer"); } b = bcache.buf; for (int i = 0; i < NBUCKET; i++) { initlock(&hashtable[i].lock, "bcache_bucket"); for (int j = 0; j < NBUF / NBUCKET; j++) { b->blockno = i; // hash(b) should equal to i b->next = hashtable[i].head.next; hashtable[i].head.next = b; b++; } } }之后就是重点bget函数，首先在对应的桶当中查找当前块是否被缓存，如果被缓存就直接返回；如果没有被缓存的话，就需要查找一个块并将其逐出替换。我这里使用的策略是先在当前桶当中查找，当前桶没有查找到再去全局数组中查找，这样的话如果当前桶中有空闲块就可以避免全局锁。
在全局数组中查找时，要先加上表级锁，当找到一个块之后，就可以根据块的信息查找到对应的桶，之后再对该桶加锁，将块从桶的链表上取下来，释放锁，最后再加到当前桶的链表上去。
这里有个小问题就是全局数组中找到一个块之后，到对该桶加上锁之间有一个窗口，可能就在这个窗口里面这个块就被那个桶对应的本地查找阶段用掉了。因此，需要在加上锁之后判断是否被用了，如果被用了就要重新查找。
static struct buf* bget(uint dev, uint blockno) { // printf("dev: %d blockno: %d Status: ", dev, blockno); struct buf *b; int idx = hash(dev, blockno); struct bucket* bucket = hashtable + idx; acquire(&bucket->lock); // Is the block already cached? for(b = bucket->head.next; b != 0; b = b->next){ if(b->dev == dev && b->blockno == blockno){ b->refcnt++; release(&bucket->lock); acquiresleep(&b->lock); // printf("Cached %p\n", b); return b; } } // Not cached. // First try to find in current bucket. int min_time = 0x8fffffff; struct buf* replace_buf = 0; for(b = bucket->head.next; b != 0; b = b->next){ if(b->refcnt == 0 && b->timestamp < min_time) { replace_buf = b; min_time = b->timestamp; } } if(replace_buf) { // printf("Local %d %p\n", idx, replace_buf); goto find; } // Try to find in other bucket. acquire(&bcache.lock); refind: for(b = bcache.buf; b < bcache.buf + NBUF; b++) { if(b->refcnt == 0 && b->timestamp < min_time) { replace_buf = b; min_time = b->timestamp; } } if (replace_buf) { // remove from old bucket int ridx = hash(replace_buf->dev, replace_buf->blockno); acquire(&hashtable[ridx].lock); if(replace_buf->refcnt != 0) // be used in another bucket's local find between finded and acquire { release(&hashtable[ridx].lock); goto refind; } struct buf *pre = &hashtable[ridx].head; struct buf *p = hashtable[ridx].head.next; while (p != replace_buf) { pre = pre->next; p = p->next; } pre->next = p->next; release(&hashtable[ridx].lock); // add to current bucket replace_buf->next = hashtable[idx].head.next; hashtable[idx].head.next = replace_buf; release(&bcache.lock); // printf("Global %d -> %d %p\n", ridx, idx, replace_buf); goto find; } else { panic("bget: no buffers"); } find: replace_buf->dev = dev; replace_buf->blockno = blockno; replace_buf->valid = 0; replace_buf->refcnt = 1; release(&bucket->lock); acquiresleep(&replace_buf->lock); return replace_buf; }最后将bpin和bunpin的锁替换为桶级锁就行了：
void bpin(struct buf *b) { int idx = hash(b->dev, b->blockno); acquire(&hashtable[idx].lock); b->refcnt++; release(&hashtable[idx].lock); } void bunpin(struct buf *b) { int idx = hash(b->dev, b->blockno); acquire(&hashtable[idx].lock); b->refcnt--; release(&hashtable[idx].lock); }实验结果如下：
start test0 test0 results: --- lock kmem/bcache stats ... lock: bcache_bucket: #fetch-and-add 0 #acquire() 4244 lock: bcache_bucket: #fetch-and-add 0 #acquire() 2246 lock: bcache_bucket: #fetch-and-add 0 #acquire() 4402 lock: bcache_bucket: #fetch-and-add 0 #acquire() 4458 lock: bcache_bucket: #fetch-and-add 0 #acquire() 6450 lock: bcache_bucket: #fetch-and-add 0 #acquire() 6312 lock: bcache_bucket: #fetch-and-add 0 #acquire() 6624 lock: bcache_bucket: #fetch-and-add 0 #acquire() 6634 lock: bcache_bucket: #fetch-and-add 0 #acquire() 12706 lock: bcache_bucket: #fetch-and-add 0 #acquire() 6208 lock: bcache_bucket: #fetch-and-add 0 #acquire() 4360 lock: bcache_bucket: #fetch-and-add 0 #acquire() 4246 lock: bcache_bucket: #fetch-and-add 0 #acquire() 2236 --- top 5 contended locks: lock: proc: #fetch-and-add 269741 #acquire() 4551132 lock: proc: #fetch-and-add 236112 #acquire() 4551131 lock: proc: #fetch-and-add 186278 #acquire() 4551151 lock: proc: #fetch-and-add 167286 #acquire() 4551164 lock: proc: #fetch-and-add 151922 #acquire() 4551132 tot= 0 test0: OK start test1 test1 OK