[發(fā)明專利]實時閃存轉(zhuǎn)換層使用的自適應(yīng)局部垃圾回收方法

有效

• 申請?zhí)枺?/td>: 201310339508.X
• 申請日: 2013-08-06
• 公開（公告）號: CN103365788A
• 公開（公告）日: 2013-10-23
• 發(fā)明（設(shè)計）人: 賈智平;申兆巖;李新;鞠雷;蔡曉軍
• 申請（專利權(quán)）人: 山東大學
• 主分類號: G06F12/06
• 分類號: G06F12/06;G06F3/06
• 代理公司: 濟南圣達知識產(chǎn)權(quán)代理有限公司 37221
• 代理人: 張勇

1.一種實時閃存轉(zhuǎn)換層使用的自適應(yīng)局部垃圾回收方法，其特征是，它采用的策略為：

A地址映射

閃存芯片采用混合式地址映射方式，即將每個邏輯頁地址分為一個邏輯塊地址和一個塊內(nèi)偏移量，對每個邏輯塊按需分配對應(yīng)的物理塊，并建立相應(yīng)的映射關(guān)系；

B讀寫操作

文件系統(tǒng)發(fā)出的寫操作由一個數(shù)據(jù)和邏輯頁地址組成，邏輯頁轉(zhuǎn)換成邏輯塊地址和塊內(nèi)偏移量；

當?shù)谝淮螌σ粋€邏輯塊進行寫時，此時為寫請求的最好情況，寫反應(yīng)時間為T_wrpg；然而，在最壞情況下，寫請求會觸發(fā)垃圾回收操作，寫請求之后會跟隨一個塊擦出操作，此時寫請求反應(yīng)時間為T_er+T_rdoob+T_wrpg；

經(jīng)過π次的寫操作后，物理塊被寫滿，如果此時要進行寫的邏輯塊所對應(yīng)的物理塊的個數(shù)已達到上限U_M或者閃存芯片中的空白塊數(shù)量達到下限E_gc，再分配新塊前垃圾回收將被觸發(fā)，否則直接進行新物理塊的分配；

文件系統(tǒng)發(fā)出的讀請求由邏輯頁地址組成，邏輯頁地址被轉(zhuǎn)化為一個邏輯塊地址和一個塊內(nèi)偏移量；通過映射關(guān)系找到要讀取的邏輯頁所對應(yīng)的物理頁，此時無論最好情況或是最快情況讀請求反映時間都是T_rdoob+T_rdpg；

C自適應(yīng)垃圾回收策略

當閃存芯片中的空白塊數(shù)量足夠時，采用分布式的局部垃圾回收算法，此時如果某個要寫的邏輯塊對應(yīng)的物理塊個數(shù)等于U_M時將觸發(fā)垃圾回收過程；另一方面，集中式的局部垃圾回收策略在閃存芯片中的空白塊數(shù)量小于E_gc時進行調(diào)用，在集中式的局部垃圾回收過程中每一個請求都將跟隨垃圾回收的一部分。

2.如權(quán)利要求1所述的實時閃存轉(zhuǎn)換層使用的自適應(yīng)局部垃圾回收方法，其特征是，所述地址映射中，對每一個邏輯塊M都存在M_i個物理塊與之相對應(yīng)，M_i按需進行分配，M_i存在上限U_M。每個邏輯塊在RAM中都存在一個映射項，映射項中存放著此M_i個物理塊的指針和它們塊內(nèi)有效頁的個數(shù)VP；對于每一個邏輯塊都存在一個頁級的映射表用來存放邏輯塊中的頁和它所對應(yīng)的物理塊中頁的映射關(guān)系；頁級映射表被分為N個頁映射子表，每個頁映射子表都被存放在最近分配的物理頁的OOB區(qū)；每個塊有π頁，每個頁的OOB區(qū)存放m個頁映射表項，0<m≤π，則存放這N個頁映射子表的物理頁的指針響應(yīng)的也被存放在RAM中。

3.如權(quán)利要求1或2所述的實時閃存轉(zhuǎn)換層使用的自適應(yīng)局部垃圾回收方法，其特征是，所述寫操作時，對一個邏輯塊的第一次寫請求會被寫入到此邏輯塊對應(yīng)的物理塊的首個空白頁中；一旦一個物理塊被分配給一個邏輯塊，無論后續(xù)的請求是寫操作還是更新操作，物理塊中的空白頁都會被順序的分配。

4.如權(quán)利要求2所述的實時閃存轉(zhuǎn)換層使用的自適應(yīng)局部垃圾回收方法，其特征是，所述寫操作時，當一個新的物理頁被分配后，首先需要更新此物理頁OOB中的頁映射子表中的信息，而后將數(shù)據(jù)寫入到此物理頁的數(shù)據(jù)域中，另外此物理頁的指針也應(yīng)該相對應(yīng)的存放在RAM中用來記錄映射表信息。

5.如權(quán)利要求2所述的實時閃存轉(zhuǎn)換層使用的自適應(yīng)局部垃圾回收方法，其特征是，所述寫操作時，對一個更新操作而言，首先需要利用RAM中存放頁映射子表的頁指針將舊的OOB信息獨取出來，而后更新此頁映射子表，而后再將此映射子表寫入到新分配的物理頁的OOB區(qū)中。