[發(fā)明專利]閃存區(qū)塊選取方法及數(shù)據(jù)儲存裝置

有效

• 申請?zhí)枺?/td>: 201110112932.1
• 申請日: 2011-04-25
• 公開（公告）號: CN102760489A
• 公開（公告）日: 2012-10-31
• 發(fā)明（設(shè)計）人: 喬夢麟
• 申請（專利權(quán)）人: 慧榮科技股份有限公司
• 主分類號: G11C16/02
• 分類號: G11C16/02
• 代理公司: 上海專利商標事務(wù)所有限公司 31100
• 代理人: 陳亮

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

本發(fā)明是有關(guān)于閃存，特別是有關(guān)于閃存區(qū)塊選取。

背景技術(shù)

閃存包括多個區(qū)塊(block)，每一區(qū)塊包含用以儲存數(shù)據(jù)的多個頁(page)。當控制器欲將數(shù)據(jù)儲存至閃存，必須自閃存的多個區(qū)塊選擇其中之一區(qū)塊，以供儲存數(shù)據(jù)。為了管理閃存中區(qū)塊的數(shù)據(jù)儲存，控制器有時亦必須自閃存的多個區(qū)塊選擇其中之一，以刪除被選擇區(qū)塊所儲存的數(shù)據(jù)。被選擇的區(qū)塊稱之為「犧牲區(qū)塊」(victim?block)。因此，控制器經(jīng)常必須自閃存的多個區(qū)塊選擇一犧牲區(qū)塊，以供數(shù)據(jù)刪除或數(shù)據(jù)儲存。

一般來說，當控制器選擇犧牲區(qū)塊時，并非盲目的進行選擇，而是依據(jù)閃存中各區(qū)塊的分數(shù)(score)高低而進行選擇?？刂破骺赡軙孪葘﹂W存中的所有區(qū)塊進行評分，再依據(jù)分數(shù)高低選擇犧牲區(qū)塊。例如，若分數(shù)愈高的區(qū)塊愈適合成為犧牲區(qū)塊，則控制器選擇對應(yīng)于分數(shù)的最大值的區(qū)塊作為犧牲區(qū)塊；而若分數(shù)愈低的區(qū)塊愈適合成為犧牲區(qū)塊，則控制器選擇對應(yīng)于分數(shù)的最小值的區(qū)塊作為犧牲區(qū)塊。因此，當控制器選擇犧牲區(qū)塊時，必須事先由閃存的所有區(qū)塊的分數(shù)中找出分數(shù)的極值(extreme?value)。

尋找極值并不是件容易的事。首先，控制器必須維護一分數(shù)數(shù)據(jù)串，此分數(shù)數(shù)據(jù)串記載閃存中所有的區(qū)塊的分數(shù)。接著，控制器必須在相當短的時間內(nèi)依據(jù)分數(shù)數(shù)據(jù)找到分數(shù)極大值。舉例來說，依據(jù)閃存的規(guī)格，當主機發(fā)送一寫入命令至控制器，自控制器接到寫入命令開始起算，控制器至多僅能花費200ms將數(shù)據(jù)寫入。因此，控制器搜尋分數(shù)極值的時間無法超過200ms。

控制器找到分數(shù)極大值所需花費的時間與分數(shù)數(shù)據(jù)串的數(shù)據(jù)結(jié)構(gòu)有關(guān)。舉例來說，圖1A為以串行方式儲存閃存區(qū)塊的分數(shù)數(shù)據(jù)的示意圖。X個區(qū)塊的分數(shù)S₁～S_X依序儲存為數(shù)據(jù)儲存單元101～10X，而控制器必須逐一搜尋數(shù)據(jù)儲存單元101～10X，才能找到分數(shù)S₁～S_X中的極值。因此，對以串行方式儲存的分數(shù)數(shù)據(jù)搜尋極值所需的時間最長。

圖1B為以二元樹方式儲存閃存區(qū)塊的分數(shù)數(shù)據(jù)的示意圖。二元樹的一節(jié)點分生為左方子樹(left?subtree)與右方子樹(right?subtree)，其中左方子樹的節(jié)點資料值均小于根節(jié)點的數(shù)據(jù)值，而右方子樹的節(jié)點數(shù)據(jù)值均大于根節(jié)點的數(shù)據(jù)值。因此，二元樹中儲存的數(shù)據(jù)極值便是二元樹的右下方節(jié)點。例如，圖1B中的二元樹120所儲存的分數(shù)數(shù)據(jù)S₁～S₁₂中的極大值是節(jié)點128儲存的分數(shù)S₆。雖然以二元樹的數(shù)據(jù)結(jié)構(gòu)儲存數(shù)據(jù)易于尋找極值，但當新數(shù)據(jù)欲存入二元樹時需耗費大量時間。例如當欲將分數(shù)S₁₂存入二元樹120時，需逐次與節(jié)點121、123、125、127、130進行分數(shù)大小的比較，耗費許多時間。當二元樹中儲存的數(shù)據(jù)愈多時，維護二元樹的數(shù)據(jù)必須耗費過多的時間，不利于控制器的數(shù)據(jù)存取。

因此，需要一種數(shù)據(jù)結(jié)構(gòu)，可以讓控制器于短時間內(nèi)記錄閃存區(qū)塊的分數(shù)，又可讓控制器于短時間內(nèi)搜尋出閃存區(qū)塊分數(shù)的極值。

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

有鑒于此，本發(fā)明的目的在于提供一種閃存區(qū)塊選取方法，以解決習(xí)知技術(shù)存在的問題。首先，將一閃存的多個區(qū)塊分為多個區(qū)塊群，其中每一區(qū)塊群包括一第一數(shù)目的區(qū)塊。接著，將這些區(qū)塊群分為多個區(qū)塊大群，其中每一區(qū)塊大群包括一第二數(shù)目的區(qū)塊群。接著，于一評分記錄表中記錄該閃存的這些區(qū)塊對應(yīng)的分數(shù)(score)。接著，于一極值記錄表中記錄每一這些區(qū)塊群所包含的區(qū)塊對應(yīng)的分數(shù)的一第一極值(extreme?value)、每一這些區(qū)塊大群所包含的區(qū)塊對應(yīng)的分數(shù)的一第二極值、以及該閃存的所有這些區(qū)塊對應(yīng)的分數(shù)的一總極值。當這些區(qū)塊中的一目標區(qū)塊對應(yīng)的分數(shù)有修改時，將該修改后分數(shù)與該極值記錄表中對應(yīng)于該目標區(qū)塊的該第一極值、該第二極值、以及該總極值比較，以決定是否將該第一極值、該第二極值、以及該總極值置換為該修改后分數(shù)。最后，依據(jù)該極值記錄表中記錄的該總極值自該閃存的這些區(qū)塊決定一犧牲區(qū)塊(victim?block)以供運用。