建设部颁发的证书网站,网站数据分析报告,数字图书馆网站建设,高网站排名吗PreRead
第六章3.5节#xff1a;物理内存分配器8.1-8.3 文章目录 PreReadMemory allocatortaskshints思路 Buffer cachetaskhints思路实现 这次的lab#xff0c;本质上都是通过将锁的粒度减小来获得性能的提升 第一个task#xff0c;可以简单地按cpu划分#xff0c;因为本…
PreRead
第六章3.5节物理内存分配器8.1-8.3 文章目录 PreReadMemory allocatortaskshints思路 Buffer cachetaskhints思路实现 这次的lab本质上都是通过将锁的粒度减小来获得性能的提升 第一个task可以简单地按cpu划分因为本来就是空闲页面谁拥有都一样第二个task本质上也可以简单地按某种性质划分但是因为我们不只需要分配我们 还需要查找。如果随便分成若干部分那么查找起来就非常慢了。所以这也是为什么hints里提示我们用哈希表来划分 Memory allocator
tasks 你的任务是去实现per-cpu空闲链表并且在一个cpu的空闲链表空着的时候去偷另一个cpu的空闲链表 你的所有锁的名字都应该以kmem开头即在initlock中设置 你必须通过 kalloctestmake grade会提醒你它通过了 usertests可以先检查一下sbrkmuch
hints 你可以使用kernel/param.h中的NCPU常数 让freerange将所有的空闲内存都给正在运行的free range cpuid函数会返回当前的cpu号但是它必须在中断被关闭的时候使用 因此你需要使用push_off和pop_off 看一下snprintf学习怎么格式化字符
思路
首先我们需要以不同的cpu号去访问不同的freelist最方便的方法就是用一个数组如下所示。其中count是为了借空闲页面准备的。
struct {struct spinlock lock;struct run *freelist;int count;
} kmem[NCPU];然后我们应该在kinit中先初始化各种cpu对应的lock然后将所有空闲页面都放到运行kinit的cpu上。
这里有几个细节
首先我是希望kinit只被一个cpu执行这样才能保证freerange将所有页面都放到这个cpu上因此我需要使用push_off和pop_off将kinit包围起来对于b_lock这个锁也是为了借空闲页面准备的否则可能发生死锁
void kinit() {push_off();for (int i 0; i NCPU; i) {initlock(kmem[i].lock, kmem);kmem[i].count 0;}initlock(b_lock, borrow);freerange(end, (void *)PHYSTOP);pop_off();
}freerange函数不需要修改
在kfree函数中当我们准备将这个空闲页面加入到一个freelist时先关闭中断然后获取当前cpu号加入到对应的freelist还是比较简单的。
其中如果是freerange调用的kfree可能会有push_off的嵌套不过这没关系只要pop_off成对出现即可
void kfree(void *pa) {struct run *r;if (((uint64)pa % PGSIZE) ! 0 || (char *)pa end || (uint64)pa PHYSTOP)panic(kfree);// Fill with junk to catch dangling refs.memset(pa, 1, PGSIZE);r (struct run *)pa;push_off();int id cpuid();acquire(kmem[id].lock);r-next kmem[id].freelist;kmem[id].freelist r;kmem[id].count;release(kmem[id].lock);pop_off();
}kalloc函数如果当前cpu有空闲页面则正常操作否则的话需要去借页面。我这里采用的借的策略是遍历所有cpu如果某个cpu有空闲页面那我就借一半如果有3个那我就借2个
// Allocate one 4096-byte page of physical memory.
// Returns a pointer that the kernel can use.
// Returns 0 if the memory cannot be allocated.
void *
kalloc(void) {struct run *r;push_off();int id cpuid();acquire(kmem[id].lock);r kmem[id].freelist;if (r) {kmem[id].freelist r-next;kmem[id].count--;}release(kmem[id].lock);if (!r) {acquire(b_lock);r borrow(id);release(b_lock);}if (r)memset((char *)r, 5, PGSIZE); // fill with junkpop_off();return (void *)r;
}具体的borrow函数的实现如下
可以发现在进入borrow函数之前我就将当前cpu的freelist的锁给释放了。这是因为我进入borrow之后会去获取其他freelist的锁假如我是cpu a我在borrow里要获取cpu b的锁。而b此时也在运行borrow那它可能也在获取我的锁。如果我和b在进入borrow前都没有释放自己的锁那必然就死锁了
另外为什么在borrow之前要获得一个borrow的大锁呢这是因为如果我在borrow里如果找到了一个可以借的freelist那么我还是会获取两个锁这也是有可能造成问题的因为我们没有限制获取锁的顺序。为了避免可能的情况我是用这个大锁来保平安不过好像不会出现这种情况
void *borrow(int id) {for (int i 0; i NCPU; i) {acquire(kmem[i].lock);if (kmem[i].count ! 0) {int b_count (kmem[i].count 1) / 2;struct run *r kmem[i].freelist;struct run *temp r;for (int i 0; i b_count - 1; i) {temp temp-next;}kmem[i].freelist temp-next;kmem[i].count - b_count;acquire(kmem[id].lock);if (b_count ! 1) {temp-next kmem[id].freelist;kmem[id].freelist r-next;kmem[id].count b_count - 1;}release(kmem[id].lock);release(kmem[i].lock);return r;}release(kmem[i].lock);}return 0;
}Buffer cache
task
修改bget和brelse使得对磁盘块的查找和释放在lock上等待的时间越少越好通过bcachetest和usertests请给你的所有lock一个以bcache开头的名字在initlock中实现它这玩意比kalloc要难太多因为buffer是必须被所有cpu共享的不能每个cpu一份因此建议使用一个哈希表给哈希表的每个桶都设置一个锁以下情况发生冲突是没关系的因为测试不会有这些情况 两个进程访问同一个磁盘block两个进程同时miss然后需要找到一个没用过的block两个进程同时操作block但是它们恰好在你的hash策略中碰撞了那么你应该避免这种情况比如调大你的哈希表的size
hints
阅读xv6的8.1到8.3你可以使用固定长度的哈希表同时选择一个质数去做哈希比如13在哈希表中查找一个buffer和为这个buffer分配一个entry必须是原子性的删除所有缓存的链表bcache.head时间戳缓存使用它们上一次使用的时间trap.c中的ticks。有了这个改变之后brelse不需要获得bcache的lockbget可以基于时间戳选择最近最少使用的块在bget中使用顺序查找实现LRU是可以的你有时可能需要持有两个锁即bcache锁和每个bucket的锁保证你可以避免死锁当你替换某一块的内容时需要将buf从一个bucket移到另一个记得处理这两个bucket相同的情况否则就死锁了
思路
hints里其实就提供了一个思路用哈希表去存可用的buf。但是到底怎么实现呢我觉得这里的思路应该有很多这里提供一种。
首先我们通过blockno % prime为key构造一个哈希表其中prime可以取hints里的13 每一个哈希表的表槽都是一个buf链表一个表槽锁这个链表的结构可以按照原来的bcache里那个head来表槽锁就是保护这个表槽里的这个链表 然后我们在binit中先将所有的空闲buf都放到key0的链表中其实放到哪都可以平均放到每个表槽也行在bget的时候先根据blockno计算出key然后去对应的表槽里找是否这个block已经被取出来了 如果已经取出来了则直接返回buf指针这一个逻辑和原来的bget很像如果这个block还没有被取出来那么我们就去找一个引用数为0的buf将这个buf的内容换成我们这个block。这里又有两种情况因此我们需要遍历整个哈希表的表槽并遍历每个表槽的链表在链表上执行lru算法找到一个buf将这个buf修改为我们的内容然后移动到key对应的表槽 这个引用数为0的buf在我们这个表槽的链表里这个引用数为0的buf在别的表槽里 在brelse中就很简单只需要将refcnt减1就行了都不用将这个buf移动
思路就是这样不过有一个关键点没有涉及那就是锁该如何安排锁呢
首先锁肯定是要去保护一些东西的之前的bcache的那个大锁是因为保护的东西太多了所有buf都是被它保护着这就导致很慢了因为可能不同的cpu没有冲突但依然要等很久。
因此我们这里采用一种哈希表的方法使得锁管理的范围变小。对于某个key对应的表槽的那个锁它只需要管理blockno%primekey的block也就是说我们将原来的一个锁变成了prime个锁使得它们管理的范围缩小了prime倍。当然了这是对于那些存储了某些block的内容的buf而言的如果它存储了那么它肯定就在对应的表槽中。至于那些没有存储的或者说引用数为0的我们可以称为空闲buf它们按什么方式组织都行甚至可以专门搞一个空闲链表都可以。但是这里采用的方式比较偷懒也比较巧即没有存储的一开始就放在key0的表槽链表引用计数为0的直接不处理反正它们都可能在bget中被访问到
最后锁的作用呢我们这里有两个锁一个锁是表槽对应的锁一个是每个buf对应的锁它们分别保护了什么
表槽锁当然是保护了表槽里的那个链表也就是保护了链表的每个节点即一个个buf使得链表或者每个buf在被修改时只会有一个线程对它们进行修改而每个buf对应的锁它的作用是使得在某一刻它永远只会被一个线程所拥有不会同时被多个线程拥有。所以这个锁使用起来非常简单我们只需要在我们找到了一个正确的buf将它作为res在bget中返回之前调用这个buf的锁即可
实现
首先是整体的布局
这里的bcache最好不删因为这个变量默认就开辟了NBUF个struct buf省的我们自己申请空间创造了哈希表有prime个表槽每个表槽一个链表一个锁链表的结构和之前的一样一个head作为dummynode方便操作一些宏主要是方便省的后面输入一大串代码来获取锁和释放锁
#define prime 13struct {struct buf buf[NBUF];
} bcache;struct {struct spinlock lock;struct buf head;
} ht[prime];#define LOCK(i) (acquire(ht[i].lock));
#define UNLOCK(i) (release(ht[i].lock));binit函数
首先给每个表槽的锁给初始化然后初始化这个head将所有的buf都放到key0的表槽中
这个过程很像之前binit抄就完事了
void binit(void) {struct buf *b;char a[20];for (int i 0; i prime; i) {snprintf(a, sizeof(a), bcache_%d, i);initlock(ht[i].lock, a);ht[i].head.prev ht[i].head;ht[i].head.next ht[i].head;}// Create linked list of buffersfor (b bcache.buf; b bcache.buf NBUF; b) {initsleeplock(b-lock, buffer);insert_into_ht(b, 0);}
}可以发现这里用到了一个insert_into_ht的操作定义如下
可以从原来的brelse抄
void insert_into_ht(struct buf *b, int key) {b-next ht[key].head.next;b-prev ht[key].head;ht[key].head.next-prev b;ht[key].head.next b;
}void delete_from_ht(struct buf *b) {b-next-prev b-prev;b-prev-next b-next;
}brelse函数的实现也非常简单
释放这个buf的锁其实这个释放放在哪一行都没问题 因为它的refcnt还没减1就注定了它不会被别人给夺舍只要unlock不取消掉就没有人能够访问到它
void brelse(struct buf *b) {releasesleep(b-lock);int key b-blockno % prime;LOCK(key);b-refcnt - 1;UNLOCK(key);
}bpin和bunpin的实现也很简单
首先这两个函数肯定是在一个buf已经有了一个block并且refcnt不为0的情况下调用的我们只需要先获得对应表槽的锁即获得对这个buf的修改权然后修改就可以了
void bpin(struct buf *b) {int key b-blockno % prime;LOCK(key);b-refcnt;UNLOCK(key);
}void bunpin(struct buf *b) {int key b-blockno % prime;LOCK(key);b-refcnt--;UNLOCK(key);
}大头戏bget来了
首先通过search_in_ht尝试去找找这个block是不是已经被读入了某个buf里这种情况如果成功那就和之前bget前一部分逻辑一模一样如果失败了那么就需要通过search_in_other去整个哈希表中找一个空闲的buf这个操作一定会成功否则在xv6里就直接给它来一个panic原函数也是这么写的
static struct buf *
bget(uint dev, uint blockno) {struct buf *b;int key blockno % prime;// 尝试去对应的哈希表槽查找LOCK(key);b search_in_ht(dev, blockno, key);if (b) {UNLOCK(key);acquiresleep(b-lock);return b;}// 至此没有在对应的表槽找到遍历所有哈希表的表槽不过优先处理自己表槽的// 这里是带着key对应的锁去查找的b search_in_other(dev, blockno, key);// 这个b不可能为0否则直接panic了UNLOCK(key);acquiresleep(b-lock);return b;
}search_in_ht的实现如下所示就是遍历链表如果找到了更新属性然后返回。其中更新属性会用到update_time。
void update_time(struct buf *b) {acquire(tickslock);b-timestamp ticks;release(tickslock);
}struct buf *search_in_ht(uint dev, uint blockno, int key) {struct buf *b;for (b ht[key].head.next; b ! ht[key].head; b b-next) {if (b-dev dev b-blockno blockno) {b-refcnt;update_time(b);return b;}}return 0;
}而search_in_other就比较复杂 这里采取的遍历顺序是从自己这里开始遍历用一个cycle来控制遍历prime次之所以这样做是为了避免每次都是0开始遍历。这样操作相对来说会提高点性能不会出现前面的表槽没有空闲的后面的表槽全是空闲的 如果我们要进入的某个表槽不是自己那么就需要获取那个表槽的锁 这里是有可能死锁的 因为我们进入这个函数的时候是带着key对应的锁的现在又去请求i对应的锁假如某个cpu是带着i对应的锁进入这个函数正在请求key对应的锁岂不是就死锁了感觉是自带的评测没有检查出来这里还是有点问题的。不过懒得改了 接下来就是通过search_lru_free_in_ht去这个兄弟那里找一找有没有空闲的 struct buf *search_lru_free_in_ht(uint dev, uint blockno, int key) {struct buf *b;struct buf *lru_b 0;for (b ht[key].head.next; b ! ht[key].head; b b-next) {if (b-refcnt 0 (lru_b 0 || lru_b-timestamp b-timestamp)) {lru_b b;}}return lru_b;
}如果没有那么视情况释放锁然后continue 如果有的话 更新各种属性如果这个buf是别的表槽将这个buf挪到key对应的表槽最后视情况释放这个兄弟锁返回答案
struct buf *search_in_other(uint dev, uint blockno, int key) {struct buf *b;for (int i key, cycle 0; cycle prime; cycle, i (i 1) % prime) {// 如果不是自己则给这个兄弟上个锁if (i ! key) {LOCK(i);}// 在这个兄弟里去找一下b search_lru_free_in_ht(dev, blockno, i);// 这个兄弟里没有空闲页面if (!b) {if (i ! key) {UNLOCK(i);}continue;}// 在这个兄弟里找到了空闲页面// 先更新属性b-dev dev;b-blockno blockno;b-valid 0;b-refcnt 1;update_time(b);// 如果不是自己的哈希槽里的将这个页面放到自己哈希表槽中if (i ! key) {delete_from_ht(b);insert_into_ht(b, key);}// 释放哈希表的锁if (i ! key) {UNLOCK(i);}return b;}panic(no free buf);
}整体代码如下
// Buffer cache.
//
// The buffer cache is a linked list of buf structures holding
// cached copies of disk block contents. Caching disk blocks
// in memory reduces the number of disk reads and also provides
// a synchronization point for disk blocks used by multiple processes.
//
// Interface:
// * To get a buffer for a particular disk block, call bread.
// * After changing buffer data, call bwrite to write it to disk.
// * When done with the buffer, call brelse.
// * Do not use the buffer after calling brelse.
// * Only one process at a time can use a buffer,
// so do not keep them longer than necessary.#include types.h
#include param.h
#include spinlock.h
#include sleeplock.h
#include riscv.h
#include defs.h
#include fs.h
#include buf.h
#include x86_64-linux-gnu/sys/types.h#define prime 13struct {struct buf buf[NBUF];
} bcache;struct {struct spinlock lock;struct buf head;
} ht[prime];#define LOCK(i) (acquire(ht[i].lock));
#define UNLOCK(i) (release(ht[i].lock));void update_time(struct buf *b) {acquire(tickslock);b-timestamp ticks;release(tickslock);
}void insert_into_ht(struct buf *b, int key) {b-next ht[key].head.next;b-prev ht[key].head;ht[key].head.next-prev b;ht[key].head.next b;
}void delete_from_ht(struct buf *b) {b-next-prev b-prev;b-prev-next b-next;
}void binit(void) {struct buf *b;char a[20];for (int i 0; i prime; i) {snprintf(a, sizeof(a), bcache_%d, i);initlock(ht[i].lock, a);ht[i].head.prev ht[i].head;ht[i].head.next ht[i].head;}// Create linked list of buffersfor (b bcache.buf; b bcache.buf NBUF; b) {initsleeplock(b-lock, buffer);insert_into_ht(b, 0);}
}struct buf *search_in_ht(uint dev, uint blockno, int key) {struct buf *b;for (b ht[key].head.next; b ! ht[key].head; b b-next) {if (b-dev dev b-blockno blockno) {b-refcnt;update_time(b);return b;}}return 0;
}struct buf *search_lru_free_in_ht(uint dev, uint blockno, int key) {struct buf *b;struct buf *lru_b 0;for (b ht[key].head.next; b ! ht[key].head; b b-next) {if (b-refcnt 0 (lru_b 0 || lru_b-timestamp b-timestamp)) {lru_b b;}}return lru_b;
}struct buf *search_in_other(uint dev, uint blockno, int key) {struct buf *b;for (int i key, cycle 0; cycle prime; cycle, i (i 1) % prime) {// 如果不是自己则给这个兄弟上个锁if (i ! key) {LOCK(i);}// 在这个兄弟里去找一下b search_lru_free_in_ht(dev, blockno, i);// 这个兄弟里没有空闲页面if (!b) {if (i ! key) {UNLOCK(i);}continue;}// 在这个兄弟里找到了空闲页面// 先更新属性b-dev dev;b-blockno blockno;b-valid 0;b-refcnt 1;update_time(b);// 如果不是自己的哈希槽里的将这个页面放到自己哈希表槽中if (i ! key) {delete_from_ht(b);insert_into_ht(b, key);}// 释放哈希表的锁if (i ! key) {UNLOCK(i);}return b;}panic(no free buf);
}static struct buf *
bget(uint dev, uint blockno) {struct buf *b;int key blockno % prime;// 尝试去对应的哈希表槽查找LOCK(key);b search_in_ht(dev, blockno, key);if (b) {UNLOCK(key);acquiresleep(b-lock);return b;}// 至此没有在对应的表槽找到遍历所有哈希表的表槽不过优先处理自己表槽的// 这里是带着key对应的锁去查找的b search_in_other(dev, blockno, key);// 这个b不可能为0否则直接panic了UNLOCK(key);acquiresleep(b-lock);return b;
}// Return a locked buf with the contents of the indicated block.
struct buf *
bread(uint dev, uint blockno) {struct buf *b;b bget(dev, blockno);if (!b-valid) {virtio_disk_rw(b, 0);b-valid 1;}return b;
}// Write bs contents to disk. Must be locked.
void bwrite(struct buf *b) {if (!holdingsleep(b-lock))panic(bwrite);virtio_disk_rw(b, 1);
}// Release a locked buffer.
// Move to the head of the most-recently-used list.
void brelse(struct buf *b) {releasesleep(b-lock);int key b-blockno % prime;LOCK(key);b-refcnt - 1;UNLOCK(key);
}void bpin(struct buf *b) {int key b-blockno % prime;LOCK(key);b-refcnt;UNLOCK(key);
}void bunpin(struct buf *b) {int key b-blockno % prime;LOCK(key);b-refcnt--;UNLOCK(key);
}
