[發(fā)明專利]一種基于FLASH區(qū)域地址映射機(jī)制的垃圾回收方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201811472073.5
• 申請(qǐng)日: 2018-12-04
• 公開（公告）號(hào): CN109376095B
• 公開（公告）日: 2023-06-13
• 發(fā)明（設(shè)計(jì)）人: 王冬;李運(yùn)喜;楊瓊;徐曉光
• 申請(qǐng)（專利權(quán)）人: 中國航空工業(yè)集團(tuán)公司西安航空計(jì)算技術(shù)研究所
• 主分類號(hào): G06F12/02
• 分類號(hào): G06F12/02
• 代理公司: 北京清大紫荊知識(shí)產(chǎn)權(quán)代理有限公司 11718
• 代理人: 婁華

本發(fā)明屬于計(jì)算機(jī)系統(tǒng)軟件專業(yè)技術(shù)領(lǐng)域，涉及一種基于FLASH區(qū)域地址映射機(jī)制的垃圾回收方法，該方法用于解決垃圾回收時(shí)間開銷過大，空間回收效果不明顯的問題。一種基于FLASH區(qū)域地址映射機(jī)制的垃圾回收方法包括以下3個(gè)關(guān)鍵方面：1.在文件系統(tǒng)初始化時(shí)構(gòu)建FLASH設(shè)備的區(qū)域地址映射與垃圾回收預(yù)留塊結(jié)構(gòu)；2.在文件系統(tǒng)運(yùn)行中執(zhí)行FLASH設(shè)備的垃圾回收空間壓縮；3.在文件系統(tǒng)運(yùn)行中執(zhí)行FLASH設(shè)備的垃圾回收空間收集。實(shí)施本發(fā)明設(shè)計(jì)的FLASH設(shè)備垃圾回收方法后，能夠在較小的時(shí)間開銷內(nèi)達(dá)到理想的空間回收效果。

技術(shù)領(lǐng)域

本發(fā)明屬于計(jì)算機(jī)系統(tǒng)軟件技術(shù)領(lǐng)域，具體提出一種基于FLASH區(qū)域地址映射機(jī)制的垃圾回收方法。

背景技術(shù)

FLASH設(shè)備先擦后寫的特性導(dǎo)致其使用異地更新機(jī)制，一個(gè)物理塊會(huì)同時(shí)存在有效頁、無效頁以及空閑頁。顯然，無效頁雖然存儲(chǔ)的數(shù)據(jù)已經(jīng)無效但仍占用區(qū)域的空間，而垃圾回收會(huì)對(duì)無效頁進(jìn)行整理與回收，重新增加空閑空間。通常垃圾回收會(huì)在文件寫操作空間不足時(shí)執(zhí)行，而且涉及數(shù)據(jù)頁的拷貝操作，耗時(shí)較長(zhǎng)。此外，單次垃圾回收新增的空閑空間較少，文件寫操作會(huì)反復(fù)出現(xiàn)空間不足從而頻繁執(zhí)行垃圾回收，急劇降低文件系統(tǒng)寫性能。如何能夠在較小的時(shí)間開銷內(nèi)達(dá)到理想的空間回收效果是需要重點(diǎn)研究的問題。因此提出一種基于FLASH區(qū)域地址映射機(jī)制的垃圾回收方法。

發(fā)明內(nèi)容

本發(fā)明的目的：

為了解決FLASH設(shè)備的垃圾回收時(shí)間開銷過大，空間回收效果不明顯的問題，結(jié)合區(qū)域地址映射機(jī)制與空間壓縮以提升垃圾回收效果，特提出本發(fā)明。

本發(fā)明的技術(shù)方案：

一種基于FLASH區(qū)域地址映射機(jī)制的垃圾回收方法，其特征在于，包括以下步驟：

步驟1、構(gòu)建FLASH設(shè)備的區(qū)域地址映射結(jié)構(gòu)：文件系統(tǒng)在初始化時(shí)，采用FLASH設(shè)備的區(qū)域地址映射機(jī)制將整個(gè)文件系統(tǒng)管理的邏輯地址范圍劃分為若干個(gè)組，每個(gè)組映射到FLASH設(shè)備一組特定數(shù)目的物理塊；

步驟2、構(gòu)建垃圾回收預(yù)留塊結(jié)構(gòu)：文件系統(tǒng)在初始化時(shí)，將部分FLASH空閑塊保留且不參與區(qū)域地址映射，這些塊在垃圾回收空間收集時(shí)被擦除，作為新產(chǎn)生的空閑塊以增加區(qū)域可用空間；

步驟3、文件系統(tǒng)在運(yùn)行中，執(zhí)行垃圾回收空間壓縮：

文件系統(tǒng)運(yùn)行中，在無文件讀寫等操作的空閑時(shí)間執(zhí)行區(qū)域的空間壓縮，選擇最近最后訪問的區(qū)域執(zhí)行空間壓縮，遍歷該區(qū)域包含的所有普通邏輯映射塊，分別找到包含無效頁最多的最臟塊與一個(gè)包含空閑頁的遷移塊。

如果該區(qū)域最臟塊不包含任何有效頁，則將該最臟塊的所有空閑頁均標(biāo)記為無效，使得該最臟塊包含的所有頁均為無效；如果該區(qū)域最臟塊包含有效頁，則將其包含的有效頁依次拷貝到遷移塊中，同步更新這些有效頁的區(qū)域地址映射信息。

步驟4：文件系統(tǒng)在運(yùn)行中，執(zhí)行垃圾回收空間收集：

文件系統(tǒng)運(yùn)行中，當(dāng)執(zhí)行文件寫操作時(shí)，根據(jù)區(qū)域地址映射機(jī)制，涉及的普通邏輯映射塊屬于某個(gè)區(qū)域。當(dāng)遍歷該區(qū)域所有普通邏輯映射塊均無法找到空閑頁時(shí)，則該區(qū)域空間已滿將執(zhí)行垃圾回收空間收集；

遍歷空間已滿的區(qū)域，找到包含無效頁最多的最臟塊：如果該最臟塊包含的所有頁均為無效頁，則將文件系統(tǒng)的垃圾回收預(yù)留塊擦除，并將其與最臟塊的邏輯地址進(jìn)行交換，重新在該區(qū)域執(zhí)行垃圾回收空間收集；如果該最臟塊包含有效頁，則將文件系統(tǒng)的垃圾回收預(yù)留塊擦除，將最臟塊包含的有效頁依次拷貝到空閑的垃圾回收預(yù)留塊，最后將其與最臟塊的邏輯地址進(jìn)行交換，垃圾回收空間收集執(zhí)行完畢。

所述的垃圾回收方法適用于嵌入式實(shí)時(shí)操作系統(tǒng)。

所述的FLASH設(shè)備類型為NOR型或NAND型。

所述的文件系統(tǒng)應(yīng)包括異常掉電的數(shù)據(jù)恢復(fù)方法。