6.S081 Lab8:Locks

locks lab大概是pagetable labs后面第二个折磨人的实验了,两个实验虽然细节不同,但目的都是重新实现一个并行效率更高,lock contention更少的机制,因此需要花了大量的时间去考虑并行的问题。

Problem 1:Memory allocator
重新实现物理内存分配器,总体的思想是为每个CPU核心维护一个free page list,这样各自的CPU就不需要在唯一个free page list相互等待,当当前CPU的free page list用完时,需要向另外一个CPU借。

Problem 2:Buffer cache
重新实现硬盘缓存buffer cache,原来的buffer cache是由一把大锁lock维护,并行效率低,多个CPU同时读取的时候会产生很多lock contention,因此需要对buffer cache进行优化,要求通过测试的lock contention不得超过500。
我采用的优化策略有
1.利用hash表的原理,设置多个bucket中,每个bucket维护一个锁和一个块环状列表,读取块时根据块号索引对应的bucket。
2.当cache miss的时候需要替换块,利用LRU可以提高替换的效率。因此在每次回收的时候将块转移到列表的最前面,同时每次寻找替换块时利用环状列表可以很轻松地进行反向遍历,从列表的最后端选取最少使用的替换的块。
3.因为cache一共维护有限个缓存块,替换块的有时候需要到将块从一个bucket转移到另外一个bucket,因此设置每次优先从自身的bucket开始寻找替换块,当从自身的bucket寻找到合适的替换块时,则可以省去转移步骤。

Problem 3:Dead lock
前两个实验最麻烦的地方在于思考新策略的锁放置问题,因为一旦锁的顺序设置不当就会出现死锁的问题。我找到一个思考方式是
1.将各种锁归类,即可能在同一个地方出现的锁归成一类,如bucket lock虽然有13个,但它们都可能出现在同一个位置,即归成一类,单个锁自成一类。
2.在归类后根据锁使用的顺序,将每一个闭环内的锁记录为一套锁方案,如下图记录为AB方案。

acquire(a);
acquire(b);
release(b);
release(a);

3.将方案都整理好后查看不同方案之间是否存在交叉,即AB存在的同时又存在BA,或者AA本身就是一种交叉,若出现交叉,需要考虑交叉的情况因为很可能会出现死锁。
这种比较简单但同时比较死板的思考方式有时候在找不到方向的时候可以帮忙排查,但还有一些其他复杂的情况需要根据实际的场景去设置。(可能需要去看看并行编程相关的书籍了)


暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇