天天看點

Nand Flash管理算法介紹之垃圾回收類型介紹

本文簡簡單單講述FTL垃圾回收的幾種基本的類型:

1. Greedy Algorithm 貪婪算法,找有效頁數最少的塊進行回收。因為不考慮磨損均衡,是以可能會對某些塊進行多次擦除,導緻這些塊比其它塊要更早達到PECS,有隐患。但是在随機寫入的case下,貪婪算法看起來效果比較好,因為随機寫入導緻無效頁分布也是随機的。

2. Cost-Benefit Algorithm(CA) 此算法考慮到塊擦除的頻率,公式如下,根據下列公式計算出每個塊的權重值,選擇權重最大的塊進行回收。

Nand Flash管理算法介紹之垃圾回收類型介紹
Nand Flash管理算法介紹之垃圾回收類型介紹

age:此塊距離上次擦除的時間。 u:此塊有效頁比例 好處:既可以選擇有效頁數少的塊進行回收,也可以避免塊長時間沒有回收。 缺點:沒有考慮到塊的擦除次數,沒有很好均衡塊的擦除次數。

3. Cost-Age-Time Algorithm(CAT) CAT算法,在CA的基礎上,增加考慮了塊的擦除次數,每個塊的權重計算公式如下,FW選擇權重最小的塊進行回收。

Nand Flash管理算法介紹之垃圾回收類型介紹
Nand Flash管理算法介紹之垃圾回收類型介紹

age:此塊最後一次修改的時間。 u:此塊有效頁比例 CT:塊擦除次數。 好處:和CA相比,均衡了塊的擦除次數。還可以在回收的時候,把冷、熱資料寫到不同的塊上,進而達到更好的磨損均衡效果。

4. CICL Algorithm(不知道全稱) 綜合效果比較好的算法,綜合了回收效率和塊擦除次數。每個塊的權重計算公式如下,FW選擇權重最小的進行回收。

Nand Flash管理算法介紹之垃圾回收類型介紹
Nand Flash管理算法介紹之垃圾回收類型介紹

ui:塊i中有效頁的比率 εi:塊i擦除的次數 εmax:所有塊中最大擦除次數 λ:磨損均衡權重比例,取值範圍[0,1],是個浮動的值,取決于目前塊擦除最大、最小的內插補點。 當λ值較小,那麼優先以回收效率為先,反之,以磨損均衡為先。也就是說,在磨損均衡較好的情況下,λ取值較小,反之λ取值較大。