Memory allocator
todo：为每个CPU实现一个物理内存分配器，每个分配器有自己的锁，从而减少锁竞争
you must use a dedicated unloaded machine with multiple cores，可以用你自己的笔记本
要求使用细粒度的锁来进行内存分配，而非一个锁保护 kmem 或 bcache
- a free list per CPU, each list with its own lock.
Allocations and frees on different CPUs can run in parallel
Your job is to implement per-CPU freelists, and stealing when a CPU’s free list is empty.
you should call initlock for each of your locks, and pass a name that starts with “kmem”
思路与结果
每个CPU维护一个freelist，与其锁。初始时全部把物理页给第一个CPU（可优化，例如均分），本CPU物理页不够了就调用 kborrow，从其他CPU偷一个物理页，此过程中需要获取锁
- 另外获取cpuid时需要注意防止被中断
优化后：
偷取策略还是可以优化：
- 比如在 kborrow 中，不总是从第一个CPU开始获取锁，可以从其下一个CPU获取锁
- 又或者维护一个堆，空闲页最多的CPU放到堆顶，每次从这个CPU的freelist获取页
- 又或者每次偷取页时，偷取一堆页，而不是一个一个偷；这可能需要计数每个CPU现有的页数，每次获取一半或者四分之也的页数
另外局部性应该也可以优化？但是意义似乎不是很大，这里的调用频率不算太高
Buffer cache
todo：与上面的差不多，但是这里是为 buf cache 实现分配器，和CPU无相关性，目的地都是使用细粒度的锁，从而减少锁竞争
最初的思路
- 每个buffer一个锁，包括 head
- 获取指定块时，先查看缓存：
- 获取 head、head->next 的信息锁，初始化当前buffer指针为head->next
- 查看当前buffer块号是否匹配，不匹配则释放上一个锁，获取下一个锁，当前buffer指针指向 LRU list中的下一个buffer；匹配则释放锁然后返回
- …循环
- 缓存中没有，则按照上面的思路找一个空闲的buffer
这个思路有问题，万一你找着找着前面的结构变了怎么办？以及获取锁的顺序怎么规定？如何避免可能的复杂死锁情景？
最终的思路
不同于上一个实验（可以为每个CPU维护其固定的分配器），buffer cache 是与进程直接交互的，并不局限于特定的CPU
还是要从固定的池中分配buffer出来，可以考虑hash，将blockno映射到某个池中，每个池分配buffer的算法与原始的bcache一样
- blockno从1到上千，池号从0到某个质数-1，考虑取模
- 每个池都是LRU分配
在池中buffer不够时，需要从其他池借buffer…借buffer的算法？
- 每个池需要维护一个当前buffer数量，以确定拿多少
每次偷一半？进程可能频繁交互，线性搜索的时间有点长；又或者直接维护一个ref=0的list
- 每次偷一半的版本我debug了半天没调试出来
也可以每次偷一个
结果：tot=0
