关于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