跟着兵哥捡垃圾 (2) — Greedy & Cost-Benefit算法

原创内容,转载请注明:  [http://www.ssdfans.com]  谢谢!


关于GC选取Block的策略算法,兵哥引用了好几种算法(作为轻度算法恐惧症患者,我第一反应其实是拒绝的)

 

Greedy算法

固件需要维护一张Block属性表,记录每个Block当前的Valid Page数量。假设每次GC处理8个Block,查表挑出Valid Page最少的8个Block进行GC,这样做的好处是复制Valid Page的开销最小。

 

Cost-Benefit算法

                             
u代表valid page在该Block中的比例,age代表该Block距离最近一次修改的时间。

1-u是对这个Block进行GC以后能够获得Free Page的数量

2u是对这个Block进行GC的开销,读取Valid Page(1个u)然后写入到新的Block(再1个u)

(1-u)/2u可以理解为投入产出比

固件需要维护的Block属性表里,需要记录每个Block最后一次被写入的时间,GC时选择更久没有被修改的Block(冷数据)

该策略就是选择投入产出比更高,未修改时间更长的Block进行GC,两者相乘数字更大的优先被GC

 

 


					つづく

 

参考文献:《A Flash-Memory Base File system》 by Atsuo Kawaguchi, Shingo Nishioka, and Hiroshi Motoda

分类目录 未分类.
扫一扫二维码或者微信搜索公众号ssdfans关注(添加朋友->点最下面的公众号->搜索ssdfans),可以经常看到SSD技术和产业的文章(SSD Fans只推送干货)。
ssdfans微信群介绍
技术讨论群 覆盖2000多位中国和世界华人圈SSD以及存储技术精英
固件、软件、测试群 固件、软件和测试技术讨论
异构计算群 讨论人工智能和GPU、FPGA、CPU异构计算
ASIC-FPGA群 芯片和FPGA硬件技术讨论群
闪存器件群 NAND、3D XPoint等固态存储介质技术讨论
企业级 企业级SSD、企业级存储
销售群 全国SSD供应商都在这里,砍砍价,会比某东便宜20%
工作求职群 存储行业换工作,发招聘,要关注各大公司招聘信息,赶快来
高管群 各大SSD相关存储公司高管和创始人、投资人

想加入这些群,请微信扫描下面二维码,或搜索nanoarchplus,加阿呆为微信好友,介绍你的昵称-单位-职务,注明群名,拉你进群。SSD业界需要什么帮助,也可以找阿呆聊。