TW201122812A

TW201122812A - Page based management of flash storage

Info

Publication number: TW201122812A
Application number: TW099129426A
Authority: TW
Inventors: Reinhard Kuehne
Original assignee: 248 Solidstate Inc
Priority date: 2009-09-03
Filing date: 2010-09-01
Publication date: 2011-07-01
Also published as: CN102012867A; US20110055458A1; CN104298610A; TWI474167B; TWI553475B; TWI551989B; TW201510723A; CN104298610B; US8688894B2; CN102012867B; TW201510722A

Description

201122812 六、發明說明：【發明所屬之技術領域】本發明有關於-種資料儲存系統及其管理方法一種用以管理非揮發性記憶體裝置的記憶體管理電路及^ 法、以及以頁面為基礎進行記憶管理的非揮發性記置（例如：快閃隨機存取記憶體；RAM)。心、【先前技術】件來一種資料儲存裝置，其使用半導體元 ===固態硬碟主要用以仿效-磁性硬碟或大一SATA標準作為傳輸介面，以在夕數的應用領域中可輕易取代—般硬碟機。再者，固鮮，碟也能採用其他介面規格，例如？ATA、USB、PGIexp^s ==通道之實體及信號介面（廳ix3 23(m994)，而固統可使用於—揮發性記憶體，例如：SRAM、DRAM， °非揮發性§己憶體，例如：快閃記憶。請參閱第la圖，為f用電腦系統之區塊示意圖，該電 ^統係制1態硬碟來取代—般硬碟進行長駐資料的彳：人如、圖所不’ 一中央處理器105執行-連串的儲存程體指t保存在暫存記憶體⑽）UG或長駐記憶從暫存記憶體⑴或長駐記憶體⑽巾提取ϋ =⑵.解碼指令資料、⑶執行指令、⑷ 口存⑽體110或長駐記憶體1〇〇中。提取或寫回的結 4 201122812 果資料可同時與一輸入/輸出裝置1〇5進行通信，例如：印表機、一顯示器或一網路裝置。中央處理器105、暫存記憶體11〇、長駐記憶體1〇〇及輸入/輸出裝置115連接一系統匯流排12〇。系統匯流排 120用以提供在中央處理器1〇5、暫存記憶體11〇、長駐記憶體100及輸入/輸出裝置115間所通信的必要資料，且進行資料規格化及資料變換。在長駐記憶體100的例子中，系統匯流排120所提供的通信規格可為SATA規格或其他上述所列出之其錢格。長駐記憶體⑽配置有複數個邏輯位址及設置有SATA規格介面，SATA規格介面進行提取及儲存的資料訊息及控制訊息亦可透過中央處理器1〇5處理資料及程式指令而獲得。免係由固態硬碟所構建的長駐記憶體1〇〇其具有一控制器125，該控制器係將該邏輯位址解碼成一實體位址及一控制訊息，以判斷是否從反及閘快閃陣列13〇中提取資料，或者，將資料儲存於反及閘快閃陣列13〇中。反及^ 快閃陣列130包括複數個非揮發性快閃隨機存取記 : 片，該記憶體晶片切分成複數個區塊，例如：i6G = 憶體晶片切分成8192區塊。再者’每一區塊進一步細分為複數個頁©’例如：單階層記憶n片中每個區塊包括有64個頁面或多階層記憶核心晶片中包括有128個頁面。一反及閘快閃記憶體晶片結構不允許係以位元組為基礎進订-位兀組的讀寫，只能讀寫—頁自（通常為卿。此外，-個已經寫人的頁面係不能覆寫，其只能對於已抹除 201122812 的頁面進行寫入的動作，並且每次抹除的最小單位為1個區塊、64個頁面或128個頁面。再者，不同單位尺寸的讀取（例如：1個頁面）及抹除（例如：64/128個頁面）會使得快閃隨機存取記憶體晶片不易管理，而且在寫入資料之前必須將舊區塊的資料進行複製及抹除，這意味著隨意寫入小量區塊資料其寫入速度將相當緩慢。一邏輯實體轉譯表位在快閃記憶體中’每當資料寫入時，邏輯實體轉譯表將進行轉變。凊參閱第1 b圖，為習用快閃儲存系統中長駐記憶體 (SSD) 100之邏輯位址之結構示意圖。如圖所示，一非揮發性快閃隨機存取記憶體裝置150，其切分成8192個區塊 (Block)155，各區塊155切分成64個頁面（page)i6〇，各頁面160切分成8個區段（Sector)165,各區段165切分成 512個位元組（bytes) 170。區段165通常定義為最小的單位’且在區段165上額外增加一 ECC錯誤更正位元167。母一頁面160將相等於4K Bytes(512 Bytesx8區段）。係以消費者為導向之快閃儲存卡對於價格非常敏感，因此，快閃儲存卡之控制器中通常只有一個最小數量之外 4單晶片元件’並不會額外增設外部隨機存取記憶體，且 !夬閃儲存卡之控制器内部所預設的隨機存取記憶體其容量非常有限。為了節省隨機存取記憶體之儲存空間，現今的控制器技術係採用區塊為導向進行記憶體管理，這意味著邏輯實體轉譯表的每一項目係為一區塊號碼…區塊位址包括有大量資料，例如：256kb或512kb，當資料連續地寫 6 201122812 入於隨機存取記憶料，其邏輯實㈣譯表會改變緩慢的。請參閱第1G ® ’為制快_存系财長駐記又隐體 (SSD)IOG讀取及寫人之操作示意圖。如圖所示，一位址訊號200輸入於-實體位址解碼器2〇5，以解碼出—實體位址一聊。實體位址❹23個位元來表示，較低位階的3個位元（0..2)用以才曰向頁面令之區# 9m . 又201，較高階級的6個位兀α.8)用以指向區塊中之頁面2G2，下一較高階級的 13個位兀（9..21)用以指向區塊2G3，而最高階級的位元 (22)用以指向晶片位置2〇4。在k例子中’非揮發性快閃隨機存取記憶體陣列裝置 235包括有至少兩個非揮發性快閃隨機存取記㈣鳩。實體位址解碼器m產生一實體位址⑽，= 體位址250用以辨別在記憶體晶片240/245中之區乂塊 242/247是進行讀取資料22〇或寫入資料22〇。 °° 一控制訊號21G用以提供編碼的控制指示，控制邏輯1215以產生—陣列控制訊號270,非揮發性快閃^存取記憶體陣列裝置235在根據陣列控制訊號⑽ 讀取貝料或寫人資料至記憶體晶片24()/245。資料2 以提供最新區段㈣222，其係從閃記憶艘陣列裝置235讀取或寫人至非揮發 :憶:陣裝置235。資請保存在一頁二= 到貝料220被-外部主機電路所讀取或寫入至發性快閃隨機存取記憶體陣列裝置235為止。資過-資料匯流謂傳輸於頁面緩衝器225與非揮發性： 201122812 閃隨機存取記憶體陣列裝置235間。就先前技術而言，SATA介面可對於一磁性硬碟或一光電硬碟進行區段讀取或寫入，為了相容於磁性硬碟或光電硬碟’固態硬碟操作於區段層級時也必須能夠與SATA介面進行通信。承上第1 c圖所示’ 一更新的的訊號區段具有一邏輯區塊位址（LBA)51200。區段201及頁面202所對應的較低階級位元（〇..8)其相同於邏輯及實體位址，並代表一區塊203内部之區段位置。高階級位元（9.. 22)的邏輯位址 2〇3/204係為進入邏輯實體轉譯表23〇之索引值。邏輯實體轉譯表230中有許多的項目232係為區塊。在每一項目 232中’最高階級位元用以指示記憶體晶片240/245進行 =貝料讀取、寫入或抹除，而項目232的低階級位元用以指不其中一個記憶體晶片240/245的實體區塊號碼。 s己憶體晶片240中區塊（1〇〇) 242用以取代記憶體晶片245中該抹除資料之區塊（2〇〇) 247，並且區塊（2〇〇) 247 係從外部電路接收新的區段資料222。再者，區塊（1〇〇) 242 中全部其他的區段亦可複製舊的區塊（1〇〇)242資料，該複製操作的動作亦可稱為區塊的重組。為了達成資料更新的目的，位址訊號2〇〇被實體位址解瑪器205所解碼’其最高階級位元（9. . 22)用以指向索引位址’以根據索引位址進入邏輯實體轉譯表23〇。區塊（1〇〇) 2 4 2的實體位址傳送至非揮發性快閃隨機存取記憶體陣列裝置235,此時，控制邏輯器215接收及解碼控制訊號21〇, 以及命令實體位址解碼器2〇5傳送所解碼出的實體位址 8 201122812 250,同時，控制邏輯器215傳送陣列控制訊號270至非揮發性快閃隨機存取記憶體陣列裝置235。記憶體晶片24〇讀取區塊（100)242中之資料並透過資料匯流排26〇傳送至頁面緩衝器225。控制邏輯器215指示頁面緩衝器225係將區塊（100)242資料以及區塊（2〇〇)247之區段位置 4296704資料合併成新資料22〇。然後，控制邏輯器215 決定區塊（100) 242資料寫回區塊（2〇〇)247中，且指示實體位址解碼器205更新邏輯實體轉譯表23〇的索引内容，以將實體區塊1〇〇更新為實體區塊8392(8192+200)。再者’區塊緩衝器224指示更新區塊及區段512〇〇内之新資料寫入至區塊（200)237中，然後，控制邏輯器215指示記憶體晶片（0)240抹除掉區塊中之資料。如上述，以區塊為基礎的管理，當整個區塊以新資料覆寫時，其連續的操作非常快速。但隨機的寫入作業將會依再結合區塊之數量而變慢。目前，高容量固態硬碟（SSD) 必須與便宜很多的機械式硬碟（HDD)做比較。為了提高競爭力，固態硬碟必須具有比機械式硬碟高出許多的讀寫速率，尤其是在隨機寫入方面。因此，相對於控制器的價格，兩速讀寫為更重要的問題。此類型的控制器通常具有一較大的外部隨機存取記憶體，藉以有效提高速率。對於新硬體架構之快閃隨機存取記憶體陣列裝置235，較佳的内部管理方法與電路才有利於效能的提升。 IEEE Transactions on Consumer Electronics 期子丨J 2002 年 5 月號 Vol·: 48 第 366-375 頁「Compact Flash 201122812 系統具空間效率之快閃轉譯層」描述__稱為㈣轉譯層 (Flash Translation Layer，FTL)之中間軟體層，用以於快閃記憶體中將主機系統之邏輯位址重新指向至實體位址。快閃轉譯層結合頁面寫入與區塊抹除位址轉換之粒度。較大粒度之位址轉換可降低維持轉換資訊之資源，較細粒度之位址轉換可提高小量寫入之管理效率。美國專利US 5, 404, 485提供-具有虛擬映射系統之快閃記憶體，可允許資料被連續寫人未寫人之實體位址。該虛擬記憶體地圖將快閃記憶體之實體位址關聯起來，以便於追蹤資料在記憶體中的位置。美國專利US 5, 963, 983提供-具有I作記憶之記憶體裝置，用以儲存邏輯實體位址轉換資訊。該半導體記憶裝置被定位為預設區段單元。該記憶裝置具有可抹寫之非揮發性記憶體資料儲存器。一連接至主機系統之介面可接收一存取要求。該揮發性工作記憶體儲存非揮發性記頁面位址表，用以轉換需求之邏輯區段位址至該非^發性實體記憶體空間之-實體區段位址。該揮發性記憶體尚儲存一第二表格，記錄各區塊之頁面之位址，用以轉換存取要求中之一邏輯頁面位址至該非揮發性記憶體之實體頁面位址。一第二存取控制裝置參考該第二表格以取得一邏輯區段位址所對應之實體頁面位址。美國專利US 6, 591，328提供一非揮發性記憶體，具有一儲存位址控制表，該表格包含有邏輯位址與實體位址。該邏輯實體位址控制表控制資料在非揮發性記憶體中離散 201122812 儲存之位址。該邏輯實體位址控制表由複數個區塊所組成，各區塊分別做為一資料刪除單元，另包含有具有固定長度之相鄰頁面’分別做為一讀寫單元。一運算域資料區塊包含有運算域識別資料，用以指示儲存於運算域資料區塊中之資料。該邏輯實體控制表區塊位於非揮發性記憶體中，包含有控制表識別資料，用以指示經排序之控制表資料。美國專利US 6, 598, 115提供一半導體儲存裝置，包含有複數個非揮發性快閃記憶體，並使用邏輯實體區段轉換。一控制器將區塊資料之邏輯區段數轉換為非揮發性半導體記憶體區域之實體區段數，其中該區塊資料為寫入資料。美國專利仍7,386,655提供—非揮發性記憶體之高速暫存區（scratch pad)與更新區塊之索引方法。更新資料係可依-預設條件選擇記錄於—更新區塊或—高速暫存區塊中。高速暫存區塊剌以緩衝最終要儲存於新資料。 ^ 美國專利US 7,386,655提供一可存取主機資料之快閃，憶體管理系統。該系統包含有記憶體之實體單元與虛擬早兀及各虛擬單元至-或多個#體單元之映射機制。美國專利申請案us 2〇〇6/〇〇69852提供一儲存於快閃用區段管理器。一快閃驅動器利用邏輯實體區段映射追縱儲存於一快閃記憶體之資料。該映射係以-資料結構儲存，並允許資料寫人快閃記憶媒體之 201122812 程序可伊迷:：由於無需先進行抹除程序’故寫入輯實體區段=!:。若發生電源中斷的悲劇，該邏快速重建知描快閃記憶媒體中之複製映射而【發明内容】取，發性隨機存之耗揮發性隨機存取_陣列裝置於H相上述目的’本發明提供—独頁面為基礎對 =快閃儲存系統進行讀取、寫入及區塊抹除之記憶體管㈣目理電路包括有—管理處理器及—頁面緩衝器，頁面緩衝器用以管理一快取及管理處理器與在快閃儲存系統卜非揮發性置進行通l帛以提供—控制訊號’以在非揮發性記憶體陣列裝置㈣於所選擇的頁面進行程式化、抹除及讀取動作。另，頁面緩衝器與非揮發性記憶體陣列裝置及管理處理器進饤通信’頁面緩衝器切分成複數個頁面區段，各頁面區段與快閃儲存系統之各頁面具有相等之尺寸，各頁面區段暫存頁面資料’並根據控制訊號以決定從非揮發性記憶體陣列裝置讀取頁面資料或傳送頁面資料至非揮發性記憶體陣列裝置。邏輯實體轉譯表，接收一需求的邏輯頁面 12 201122812 =址，轉換邏輯頁面位址為一實體頁面位址，與管理處理器進行通仏並將實體頁面位址傳送至管理處理器，以確認非揮發性記憶體陣列裝置中一需求頁面的一實體位置，再者I輯貫體轉潭表包括有一快取旗標表，其用以確認目前頁面緩衝器是否有需求的邏輯頁面位址。又，記憶體管理電路尚包括有一輸入/輸出轉接器，其連接在一外部端口、次區塊緩衝器及管理處理器間，用以 =收-邏輯位址、控制訊號及—被通信規格所編碼的區段 =’轉換邏輯位址、控制訊號及被通信規格所編碼的區貝料成非揮發性記憶體陣列裝置可接受的規格。 _又°己憶體管理電路尚包括有一實體位址解碼器，與輸入/輸出轉接器及邏輯實體轉譯表進行通信，從輸入/輸出轉接器接收邏輯位址，轉送邏輯位址至邏輯實體轉譯表，攸邏輯實體轉譯表接收實體位址，與管理處理器進行溝通’以確,忍—需求的邏輯次區塊資料存在於頁面緩衝器或非揮發性記憶體陣列裝置中。 —又’讀體管理電路尚包括有—頁面緩衝器快取表， f管理處理器進行通信’ f面緩制快取表包括有一實體人區塊號碼’其用以確認在非揮發性記憶體陣列裝置中之 -實體位置’實體位置與在頁面緩衝器中之—頁面位置相關聯肖取類型項目用以標示-快取類型且被實體位置所佔用’一狀態項目根據一有效狀態分類頁面之區段資料，快取形式包括有-讀取快取、—串流快取、—寫入快取及工閒列表’空閒列表用以表示一頁面緩衝器為抹除 13 201122812 及可使用狀態之列表。 .又’記憶體管理電路尚包括有一最近最少使用表，最近最少使用表包括有複數個連結指標，連結指標用以決定 -最近最少使用的頁面資料存於頁面緩衝器中。各快取形式U取I·夬取、串流快取、寫入快取及空閒列表）同樣包括有複數個連結指標，其連結指標用以決定最近最少使用表之貝料刀配到哪個快取。頁面緩衝器透過管理處理器執行一收回程序’最近最少使用表之頁面資料從頁面緩衝器中收回且寫入所指定的非揮發性記憶體陣列装置之頁面中，在頁面緩衝器中之頁面位置附加至頁面緩衝器快取表之空間列表内。又，記憶體管理電路尚包括有一無效次區塊表及一實體邏輯表，無效次區塊表用以指示非揮發性記憶_列裝 f中二選擇的頁面為有效的’而實體邏輯表用以映射非揮 I·生.己It體陣列裳置之實體位置至邏輯位置，實體邏輯表 ^不σ法的頁面號碼用以指示實體位置在實體邏輯表中為已抹除或無效的。 2 ’記憶體管理電路尚包括有—抹除總數表及一實體區塊連結表，抹除總數表對於非揮發性記憶體陣列裝置中區塊記錄一抹除總數’而實體區塊連結表包括有一包之連接列表，各指標指向非揮發性記憶體陣塊，再者’連接列表包括有-錫定指標’ 頁面發性記憶體陣列裝置中之各區塊定義出無效頁面號碼。虽管理處理器對於非揮發性記憶體陣列裝置執 201122812 行垃圾收集程序’錯定指標用以指出非揮發性記憶體陣列裝置之該區塊中具有該最大無效號碼頁面之區塊，進而允許具有最大無效號碼頁面之區塊選擇進行抹除的動作。又，5己憶體管理電路尚可執行一損耗平衡程序，在一損耗平衡程序中，一抹除區塊的抹除總數比較於一滑動視 _之抹除總數，若抹除區塊之抹除總數超過滑動視窗之抹除總數，選擇另一具有最低抹除總數之區塊，且具有最低抹除總數之區塊中全部有效的頁面複製至抹除區塊之低階級頁面巾’然I，具有最低抹除總數之區塊將進行抹除動作，而具有最低抹除總數之區塊成為一新的可寫入區塊，且其抹除總數將會增加。解瑪本以頁面為基礎的管理架構，用以對位址射 .....5至邏輯實體轉換表及區塊内的頁碼。若頁3 位於頁面或必須從非揮發性收回’邏輯實體轉換表包括」快取設】位=體陣列裝3 取記.==Γ器内’則由非揮發性快閃隨㈣段-被出。區段被指定為低順序的位址，區 S 。貝取或寫入頁面緩衝器。若頁面夠的空閒頁面時，將會進行收，並二= 回至少-最近被使用的頁面 f由頁岐衝器收揮發性快鳴存取記憶體陣列褒置的難在非緩衝器的頁面空間會被、致，則頁面曰破仔知，且頁面將會被從非揮發性快 15 201122812 閃隨機存取記憶體陣列裝置中取出。區段可被適當的被讀取或寫入。當頁面内之區塊為無效時，頁面緩衝器之無效區段將會是新的，並與非揮發性快閃隨機存取記憶體陣列裝置之舊的區段相配。頁面可被重新寫入非揮發性快閃隨機存取記憶體陣列裝置，且位於頁面緩衝器内的位置將會成為空閒頁面。頁面緩衝器内最新的空閒頁面會被指派至位址頁面，且頁面由非揮發性快閃隨機存取記憶體陣列裝置中被讀取，並由頁面緩衝器讀取區段，或將區段寫入頁面緩衝器。抹除區塊列表會被維持，且當不具有足夠的抹除區塊可允許非揮發性快閃隨機存取記憶體陣列裝置進行操作時，則會進行一垃圾收回的動作以抹除無效的區塊。當區塊被抹除之後，將會進行抹除數量及門檻的比對。若超過門檻，則具有最低抹除次數的區塊會被複製至較新的抹除區塊，而具有最低抹除次數的區塊會被抹除並成為一新的備用區塊。首先，請參閱第2圖，為本發明以頁面為基礎對於記憶體進行管理之一固態硬碟之資料儲存系統一較佳實施例之區塊示意圖。如圖所示，本發明固態硬碟之資料儲存系統300以頁面為基礎進行記憶體管理。非揮發性隨機存取記憶體陣列裝置375包括有複數個晶片376a. ..376η。各晶片376a. .. 376η切分成複數個區塊377a. .. 377η，各區塊377a. .. 377η切分成複數個頁面378a. .. 378η，而各頁面378a. .. 378η切分成複數個區段379a. .. 379η。本發明 16 201122812 實施例中，每一晶片具有8192個區塊，每一區塊具有64 個頁面，每一頁面具有8個區段。在一 128G位元之固態硬碟中，係採用8個16G非揮發性隨機存取記憶體陣列裝置 375，並具有64個晶片376a. .. 376η。一輸入/輸出轉接器305接收一位址訊號31〇、接收及傳送一資料訊號315及接收一控制訊號32〇，雖然，這些 δ孔號顯示為個別訊號，然，在“ΤΑ介面中實際上可以連續發送及接收這些訊號。輸入/輸出轉接器3〇5調節及格式化這些訊號，以產生一邏輯位址訊號325並傳送至實體位址解碼器345及管理處理器34〇。資料訊號33〇在調節及格式化後，將傳送於實體位址解碼器345及管理處理器34〇間。輸入/輸出轉接器305同時可調節及格式化控制碼 335，後續，以將控制碼335傳送至管理處理器。實體位址解碼器345解碼一邏輯位址訊號325，以產生一進入於邏輯實體位址轉譯表355之索引值。邏輯位址訊號325索引指向一實際實體位置，該實際實體位置使用於非揮發性隨機存取記憶料列裝置375的讀取或寫入程序。官理處理器340解碼一控制碼335，以產生必要的控制》η*唬控制實體位址解碼器345及頁面緩衝器35〇，以及產生一陣列控制訊號37〇並傳送至非揮發性隨機存取記憶體陣列裴置375 。，官理處理器34〇使用一實體邏輯位址表38〇、一頁面 =衝器快取表382、-無效頁面表384、—抹除總數表篇、員平句表387、-缺陷區塊表388及-實體區塊連結 17 201122812 表390,藉以管理非揮發性隨機存取記憶體陣列裝置375 及頁面緩衝器350間資料的一致性。實體邏輯位址表380透過一實體頁面號碼進行索引，實體邏輯位址表380對於邏輯實體位址轉譯表355執行一反函數，且管理處理器340執行一垃圾收回程序及一耗損平衡程序時將會使用到該實體邏輯位址表380，其細節容後討論。本發明中，將保留兩個較高位址數字 (Oxffffffff、Oxfffffffe)，以鑑別該實體頁面是不是與一邏輯頁面號碼相關聯，再者，數字（Oxffffffff)意味著該實體頁面進行抹除，而數字（Oxfffffffe)意味著該實體頁面為無效的，再者，實體頁面號碼並不會寫入邏輯頁面中。非揮發性隨機存取記憶體陣列裝置375低階格式化之後，將產生初始化的邏輯實體位址轉譯表355。若讀取一頁面，管理處理器340在頁面緩衝器350中產生 Oxffffffff數字，Oxffffffff數字為在非揮發性隨機存取記憶體陣列裝置375中一抹除頁面378a，378b，…，378η 之資料内容。有了這些特殊數字（如Oxf f f ff f f f、Oxf f f f f f fe)，除了恢復區塊内容之外，並不需要一無效的頁面表。當一區塊進行抹除時，在該實體邏輯位址表380中之區塊的全部頁面將具有一 Oxffffffff數字。為了在一區塊中判定出無效頁面的號碼，在該實體邏輯位址表380中，係將具有 Oxfffffffe數字之號碼頁面進行計數。實體邏輯位址表 380對於所有抹除區塊的全部頁面進行初始化，作動的寫 18 201122812 入區塊及缺陷區塊具有0xffffffff數字，而其餘頁面具有

Oxfffffffe數字。然後，邏輯實體位址轉譯表355在掃描之後’亦可擺放於實體邏輯位址表38Q中實體頁面位置。如第2圖所示，頁面緩衝器快取表382與頁面緩衝器 350具有相同的項目號碼。頁面緩衝器快取表3犯進一步切分成-快取頁面表及—最近最少使料結表。每個頁面緩衝器快取表382項目將對應至一頁面緩衝器35()並且描述各頁面緩衝器350之快取狀態。全部頁面緩衝器快取表 382之項目係連結四個快取：一讀取快取、一寫入快取、一串流快取及一最近最少使用次序之空閒列表，且各頁面緩衝器350分別指定於一對應的快取。再者，快取頁面項目鑑別所對應的頁面緩衝器35〇為髒掉的（dirty)、不髒或未使用過。假如-快取現存位元被設定於快取頁面表仍中’即可利用邏輯頁面號碼索引該快取頁面緩衝器快取表 382,反之，快取現存位元未設定於快取頁面表4託中，將無法透過邏輯頁面號碼得到頁面緩衝器35〇之位置。頁面緩衝器快取表382具有一可用以指向頁面快閃位置之項目。從頁面緩衝H 35〇收回頁面以及將收回頁面寫至頁面緩衝器350的另一位置之後’無效的頁面資訊也必須進行相對的設定。接著，從非揮發性隨機存取記憶體陣列裝置375之頁面位置進行資料讀取，以避免頁面緩衝器 350中並非全部區段皆為有效的情況下，而造成頁面資料回收不全。 19 201122812 經由頁面緩衝器350之實體頁面號碼429a，.··，429m 索引該快取頁面表425，快取頁面表425包括有複數個頁面378a，378b,…，378η之實體位址及索引位址，頁面 378a，378b，…，378η之實體位址資料係儲存在頁面緩衝器350中。一快取模式係指定頁面是否在四種快取形式（如一空閒列表、一讀取快取、一串流快取及一寫入快取）中採用其中一者。快取頁面表425尚包括一區段有效旗標428，其用以提供一頁面之區段無效性指示。承上，讀取快取包括複數個不髒（或稱為乾淨）的頁’ 面。當儲存在頁面緩衝器350及非揮發性隨機存取記憶體陣列裝置375中的資料是相同的，則快取内容可視為不髒，則存放於頁面緩衝器350的資料398必須寫回非揮發性隨機存取記憶體陣列裝置375中，並且從該讀取快取中收回頁面緩衝器350内所存放的資料365，從非揮發性隨機存取記憶體陣列裝置375中所讀取的頁面378a, 378b,…，378η資料365都必須通過讀取快取。串流快取包括有複數個髒掉（dirty)頁面，由於頁面緩衝器350相較於非揮發性隨機存取記憶體陣列裝置375之頁面378a, 378b，…，378η係具有較新的資訊，髒掉頁面必須寫回非揮發性隨機存取記憶體陣列裝置375進行收回。再者，從外部主機電路所接收的全部資料都必須通過串流快取。假如一頁面位置已經在讀取快取中，則原本存放於讀取快取中之頁面資料將進行刪除並移動至寫入快取中，或者，在串流快取中之一頁面若被觸動兩次讀取或寫 201122812 入指令’貞1ms面將會提升至寫人快取。頁面取包括複數個髒掉(dlrty)頁面，那些辦掉最'被觸動兩次，寫入快取有效地切分成兩個部分，再者’在本發明中，串流快取及寫入快取將可提供一效的收回策略。串流快取只有對於頁面寫入一次^而寫入最少寫入一次以上(例如:檔案分配表係經常 L:2、r免因為只寫入一次資料而令全部寫入快取 u夬取中之每一頁面將得到一個入快取，並且，原本存放於串流快取中之資料假若^ 保留於串流快取中’則這些資料將可容易被收回的。一#又I間列表提供一空間之頁面緩衝器㈣池。每寺 -項取/寫人指令從料主機電路制至非 ^ 取記憶體陣列裝置375之一頁面位置，然，在頁面== 讀取/寫入指令’此時將需要-新的快取項 ^快速反應’管理處理器340試圖保持該空閒的頁太低=350池之大小。假如空閒之頁面緩衝器350號碼 350低’收回程序將開始運行並產生新的”之頁面緩衝器 =取^取、寫人快取、串流快取及空間列表間之記憶 =大小亦可㈣地改變，例如：根據實際I作量或曰寫入快取之記憶區間亦可因此增加，而消耗 ;用原本讀取快取之記憶區間。 =近最少❹頁面連結表提供—連該連結項目機制允許-表格的财，以在^缓衝ίΐ 21 201122812 胃=最近存取的頁面。—頁面收回程序使用於該頁面===衝器35°中產生_間。寫入¥而次财圾收集私序及一損耗平衡程序用以 } 貝料至非揮發性隨機存取記憶體陣列裝置375 、及對於非揮發性隨機存取記憶體陣列裝i奶進 :非:：：:隨者收回程序之進行’以致頁面資料可寫入 f發性隨機存取記憶體陣列裝置375中，再者，若消耗太多抹除頁面或及已抹除區塊之數量太低該垃圾收集知序將會因此而進行觸發，垃圾收集程序將可產生新的抹除區塊。次外’該垃圾收集程序包括有兩個步驟程序··透複製所有有效的頁面並準備一欲抹除區塊’以及係將該欲抹除區塊進行抹除。在區塊抹除之後，一區塊抹除總數將S 4加，假如區塊抹除總數太高，該區塊將與另一具有較低抹除總數之區塊進行資料置換，在此，該具有較低抹除總數之區塊其資料係較少被進行抹除之動作。無效頁面表384對於一個區塊之每一頁面提供一個狀態位兀（如每一區塊具有64個頁面，因此每一區塊將會有 64個位元）。當無效頁面表384對於其中一區塊之一頁面給予邏輯（1)之狀態位元，則代表這頁面係為無效的。再者’無效頁面會被淘汰的，但也不會因此消失而不在使用，它將會被一新頁面所取代。無效頁面表384對於一恢復演算法是必須要的’在此，假如實體邏輯位址表38〇(最後電源斷電時寫入）無法在電源開啟狀態下進行讀取，它可透過再次讀取全部的頁面而重建出來。邏輯頁面號碼儲存在每 22 201122812 一頁面之增加區域中，該邏輯頁面號碼為—反向指標，若淘汰的頁面並未抹除仍處在可使用之狀態，反向指^將: 生不是唯-性的問題。無效頁面表384容易儲存於快閃記憶體中，其用以定義頁面的有效性，再者，無效頁面表3以主要作用只是便利於記憶體内部之其他目的可採用之表格，因此，在一恢復演算法之進行程序中，無效頁面表3以並不需要的，其可以省略。抹除總數表386使用在一耗損平衡程序中，用以監栌全部區塊之抹除總數。一滑動視窗之抹除總數為一最小抹除總數加上一區塊抹除總數之門檻值，而最小抹除總數為全部區塊中實際最低的抹除總數。 “ 在非揮發性隨機存取記憶體陣列裝置375中對於其中一區塊進行抹除動作之後，該損耗平衡程序將接著進行，以在抹除總數表38〇中對於該抹除區塊增加抹除總數。假如區塊進行抹除而成為最新的抹除區塊，其抹除總數仍足夠大的，係可將具有較小抹除總數之區塊中全部有效的頁面複製到此最新抹除區塊中，然後，在將較小抹除總數之區塊進行抹除。再者，較小抹除總數之區塊中無效的頁面將不會複製到該最新抹除區塊中，該較小抹除總數之區塊内的資料將複製至該最新抹除區塊之已抹除的對應頁面，而該最新抹除區塊並不會指定為寫入區塊且會記錄到耗損平衡表387中，以表明已抹除之頁面係存在於該最新抹除區塊中。缺陷區塊表388對於非揮發性隨機存取記憶體陣列裝 23 201122812 義置位元進行缺陷㈣，以定用。“中產生缺陷或者運用時成為缺陷而無法使實體區塊連結表390為一具有項目之雙連結里塊:咖性隨機存取記憶體陣列裝置375中每-區塊=目號碼係相等於一區塊中的頁者面’因此，_目號碼可為⑷。再 =體£塊連結表㈣進—步增加㈣點項目，盆卜巴表示已抹除的區塊’另，項_指示損耗平衡之程序。區塊項目指向錯點項目 == 效頁面的總數，點項目具有-可指回 ;數量而二二1田點項目可根據每一區塊中無效頁面之號到+丈頁目面f有多數個項目。再者’每次區塊額外得到無效頁面’將可在實體邏輯位址表38〇中相對設定一 =二本發明中’區塊亦可解開對於一特定錨點之連結， #彻二連結進人下—個更高㈣之連結。實體區塊連結 ΐ面=圾收集程序可以快速找到-具有最高無效 ==之區塊。本發明實際操作時，在區塊進行抹除而二閒區塊以&供非揮發性隨機存取記憶體陣列褒置 375進行頁面寫入之前，會盡量減少複製頁面的數量，以避免空閒區塊不足產生頁面複製失敗之情況發生。請參閱第3®，為本發明以頁面為基礎對^記憶體進行皆理之-固態硬碟之資料儲存系統又一實施例之區塊示音圖。如圖所示，除了第2圖中之實體位址解碼器挪合併二 24 201122812 管理處理器340當中之外，第3圖實施例之功能構造係與第2 圖完全相同。邏輯位址325、資料訊號330及控制碼335應用於管理處理器340。管理處理器340包括一管理處理控制器 342及一韌體記憶體344。管理處理控制器342為一電腦處理器’其執行一電腦程式程序，以進行非揮發性隨機存取記憶體陣列裝置375的管理❶韌體記憶體344為一電腦可讀取儲存媒體’其可用以保存一電腦程式碼，當該電腦程式碼運行時’將可執行上述之電腦程式程序以對於非揮發性隨機存取記憶體陣列裝置375進行記憶管理。動態隨機存取記憶體陣列裝置395提供儲存空間於頁面緩衝器350、邏輯實體轉譯表355、頁面緩衝器快取表382、無效頁面表384、抹除總數表386、損耗平衡表（wearievei tabie)387及缺陷區塊表388。管理處理控制器342產生所需之位址訊號396及控制時序訊號3 9 7 ’以儲存必要資料至動態隨機存取記憶體陣列裝置395，或從動態隨機存取記憶體陣列裝置395提取必要資料。該必要資料實際上係可為讀取或寫入到頁面緩衝器35〇之資料訊號、非揮發性隨機存取記憶體陣列裝置3 7 5之實體位址、或者是由實體邏輯轉譯表38〇、缺陷區塊表388、損耗平衡表387、以及390所得之轉譯表資訊（tabie information) ° 請參閱第4圖，為本發明固態硬碟讀取及寫人一實之操作示意圖’該固態硬碟以頁面為基礎進行記憶體管理。如圖所示，邏輯位址訊號325輪入於一實體位址解碼器 25 201122812 345。該實體位址使用23個位元來表示’較低位階的3個位元（0…2)用以指向頁面内之區段326’接下來的較高階級的 6個位元（3. . 8)用以指向區塊内的頁面327 ’下一較高階級 13個位元（9…21)用以指向區塊328，最高階級位元（22) 用以指向晶片位置329。管理處理器340接收控制碼335，以要求資料由非揮發性隨機存取記憶體陣列裝置375讀取或寫入。實體位址解碼器345將邏輯位址325的最高有效位元（3,…，22)傳送至邏輯實體轉譯表355，以用於邏輯實體轉譯表355内的索引值 357。位置356儲存頁面的實體位址（1〇〇)。假如邏輯實體轉譯表355的位置356指示資料儲存至快取記憶體 (cached)，該位置即包含頁面緩衝器35〇内的頁面位置。管理處理器340檢查該儲存至快取記憶體的快取頁面轉譯表 425以核對頁面位置之所有區段（sect〇r)為有效的。如果區段無效的，由非揮發性隨機存取記憶體陣列裝置375讀取至頁面位置之無效區段之資料以及儲存至快取相關頁面緩衝器快取轉譯表42G之有效位元都會設^為有效。如果邏輯實體轉譯表355的位置356指示顯示資料未儲存至快取記憶體，該位置即包括非揮發性隨機存取記憶體陣列裝置奶内的實際頁面位置。假如邏輯實體轉譯表355的位置356指示資料已儲存至 =記憶體’管理處理器34〇即指示頁面緩衝器35〇將資料 = 330傳达至第2圖中之輸入/輸出轉接器或由第2圖中之輸入/輸出轉接器3〇5傳送出。假如邏輯實體轉譯表咖 26 201122812 的位置356指示資料未儲存至快取記憶體，管理處理器340 會指示實體位址解碼器345從邏輯實體轉譯表355傳送位置 356的内谷，以作為傳送至非揮發性隨機存取記憶體陣列裝置375之實體位址訊號360。管理處理器34〇也傳送陣列控制訊號370到非揮發性隨機存取記憶體陣列裝置375。位置（頁面100)的頁面378i傳送到頁面緩衝器35〇。管理處理器34〇指示實體位址解碼器345將頁面位置寫入頁面緩衝器3°5〇内的邏輯實體轉譯表355之位置356。再者，管理處理器34〇另外會設定相關頁面缓衝器快取轉譯表42〇的有效位元。官理處理器340從實體位址解碼器345擷取區段位址 326並將區段位址326傳送至頁面緩衝器35〇。假如資料從非揮發性隨機存取記憶體陣列裝置375讀取，f面緩衝器即擷取區段位址326所指向的區段並且將其區段資料作為資料訊號330進行傳送。假如資料要寫入，管理處理器即指示頁面緩衝器350將新資料332寫入頁面位置。接著在收回（eviction)程序中，頁面會從頁面緩衝器 350中移除。管理處理器34〇在另一晶片376b内分派頁面位置378 j之新頁面位址，作為資料之頁面的新位置。管理處理器340指示實體位址解碼器345將新實體位址376j (頁面 100變為頁面524488)寫入位置356的邏輯實體轉譯表355，位置356由邏輯位址325的頁面位址部分（頁面327、區塊 328、以及晶片位置329)指向。資料頁面從頁面緩衝器350 寫入到378 j ( 324488或376b之頁面200 )。接著舊位置378i (第一晶片的位置10 0 )進行標記，以在垃圾收集（garbage 27 201122812 collection)程序中進行消除（容後詳細解釋）。請參閱第5圖，為本發明以頁面為基礎之記㈣管理之表格式意圖。在當前的科技中，非揮發性隨機存取記情體陣列裝置475可具有i6G記憶單元（咖，⑶i丄）或位元 (bits)^^^，,at^2G,iitM(bytes)^524 >288^^ 〇32〇或8，192個區塊〇31〇^〇。在本發明之一實施例中，每個非揮發性隨機存取記憶體陣列襄置475具有#位元組以及卜2、或4個儲存板（plane)的結構。每個儲存板的每個頁面合併於頁面緩衝器415的位置。例如，在具㈣位元組以及2儲存板構造的非揮發性隨機存取記憶體陣列裝置 475中’每個頁面緩衝器415内的位置416_位元組。本發明中之固態硬碟系統之結構的模擬顯示頁面緩衝器4工5加上所有其他表格的大小應該大致為非揮發性隨機存取記憶體陣列裝置375陣列之總共大小的〇. 1%。實際上，邏輯實體位址轉譯表4〇〇和實體邏輯位址轉譯表4仏是所有動離隨機存取記憶體最大的部份。因此，非揮發性隨機存取二憶體陣列裝置375之128G位元㈣列應該具有·位元的麵。對每個非揮發性隨機存取記憶體陣列裝置475來說將會有約512個頁面。對非揮發性隨機存取記憶體陣列裝置 475的整個陣列來說，這會轉換為具有約位元組大^ 頁面緩衝器415。 * k輯貫體位址轉澤表彻具有和固態硬碟之邏輯記憶空間一樣多的項目頁面（entry page)位置，，405i, ，405η。如第4圖所示，邏輯實體位址 28 201122812 轉譯表400透過頁面位址357進行索引。邏輯實體位址轉譯表400的每個項目位置4〇5a，…，4〇5i，…，4〇5〇包括非揮發性隨機存取記憶體陣列裝置475内的實體頁面位置478或頁面緩衝器415的快取位置。快取旗標（flag)41〇附加在每個項目位置4〇5a，...，405i，…，405η中。快取旗標41〇標 =出項目位置4〇5a，...，405i，…，405η是否位於頁面緩衝器415之實體位置或在非揮發性隨機存取記憶體陣列裝置 475 中。、頁面緩衝器415對資料頁面提供暫時的快速存取，該資料頁面儲存在非揮發性隨機存取記憶體陣列裝置475中。資料由外部主機電路讀取或寫入頁面緩衝器415。非揮發性隨機存取記憶體陣列裝置475並非由外部主機電路直接存取。非揮發性隨機存取記憶體陣列裝£ 4 7 5具有一關聯性之頁面緩衝器快取轉譯表420。頁面緩衝器快取轉譯表42〇包 ▲八有項目位置429a，..·，429ί，…，429η的快取頁面轉琿表425，其對應至頁面緩衝器415内的每個項目位置 416a，…’416ι’ .··’ 416η。快取頁面轉譯表425内的每個員目位置429a’ ."，429i，…，429η具有實體頁面位置 426快取模式旗標427、以及一區段有效旗標428。實體頁面位置426提供儲存於頁面緩衝器415内的頁面之非揮發性隨機存取記憶體陣列裝置475内之實體位置。〇快取模式旗標427指示頁面資料是否存放於頁面緩衝器415中’並絲取模式旗標奶為讀取快取、串流快取、寫入快取、或空閒列表之其中之—號碼。如前述，讀取快 29 201122812 取中的資料為從非揮發性隨撫擷取的資料，其保持^^取記憶體陣列裝置475所 475的…、揮發生隨機存取記憶體陣列裝置的頁面=相同。寫人快取中的資料是寫人w Γ1 ：: 6l，...，416n的外部資料，因此，在㈣程序乂不^貝科寫回非揮發性隨機存取記憶體陣列裝置475 :不再T揮發性隨機存取記憶體陣列裝議的頁面位 Γ記憶^包括在收回程序中必須寫回快閃 :=flash)之髒掉的頁面(dirt”·），因為快取 =内之頁面緩衝器相較於快取記憶體頁面係具空閒列表並非真的快取，而是頁面緩衝議内未伯據位置的列表，該空間列表可以握有從頁面緩衝器 415内所擷取之新頁面，或是新資料頁面從外部主機電路寫入至非揮發性卩通機存取記憶體陣列裝置475。 —區段有效旗號428利用-資料位元來指示每個頁面的每個區段是衫有效或無效。區段只在非揮發性隨機存取記憶體陣列裝倾5时效，並且如果需要，必須由非揮發性隨機存取記憶體陣列裝置475内擷取。區段有效旗號似内的位兀數量取決於每個頁面内存在的區段數量。如同前述在本實施例中，系統定義為每頁具有8個區段，或是每個區段有效旗號428有8個位元。在某些實施例中，頁面可以定義為具有8K位元組（512位元組χΐ6區段）或是每個區段有效旗號428具有16位元。在其他實施例中，區段和頁面亦可以相等’區段有效旗號428可以不需要的。另外，頁面緩衝器快取轉譯表420包括有一最近最少使 201122812 用連結表（least recently used chain table)430。最近最少使用連結表430具有複數個項目，各項目對應快取頁面轉譯表425的每個項目位置429a，…，429i，…，429η。最近最少使用連結表430具有連結佇列433/434。向前連結佇列433係由最年輕的項目到最舊的項目排序，相反的，向後連結佇列434由最舊的項目到最年輕的項目排序。另外，對每個連結佇列433/434來說最近最少使用連結表430具有4 個錨點項目（anchor entry)431a，431b, 431c，431d，432a， 432b，432c，432d。這允許最近最少使用連結表430有4個佇列（queue )’讀取快取、串流快取、寫入快取、以及空閒清單分別在連結仔列433/434中。每個連結件列433和434 的錨點項目 431a，431b，431c，431d，432a，432b，432c， 432d是每個連結佇列433/434的這4個佇列的起始點。最近最少使用連結表430根據老化順序（age)連接讀取快取、串流快取、以及寫入快取、彳宁列的所有項目。因為接續點 (successors)和前置點（predecessors)可立即獲得，這個雙重連接清單有效率地便利於連入/連出（chain in /chain out)程序。最近最少使用連結表430的時間順序機制使得每次當碰到頁面緩衝器415内的位置時’最近最少使用連結表4 3 〇内的項目移動到下一個向前清單（如果它還不在那裏）的起始處。所以每個越靠近向前清單的起始處的項目將掉回一個項目。同樣地’向前清單的最後項目位置和向後清單的起始相同’並且標記最舊的最近最少使用項目。 31 201122812 假如一輸入位址有一邏輯位址，該邏輯位址指向邏輯實體位址轉譯表400之位置405 i，且其内容會指向頁面位置 5。位置405i的快取旗標410從頁面緩衝器415的位置405i 而指示指向頁面位置5。位置5之頁面緩衝器快取轉譯表420 内的實體頁面位置426指向非揮發性隨機存取記憶體陣列裝置475内的實體頁面1000。在位置項目429i之頁面5的區 #又有效旗號428包括一數值（7)，數值（7)表示在位置4i6i 中，除3個最低階級區段外，其餘其他全部區段都是無效的。這3個最低階級區段儲存於非揮發性隨機存取記憶體陣列裝置475中之實體頁面1〇〇〇。在固態硬碟的讀取和寫入資料中，不在頁面緩衝器415 的頁面必須由快取模式旗標427從空閒列表中分配到一個頁面。如果頁面緩衝器415内的可用頁面數量低於門檻值，就會執行收回程序以移除最近最少使用頁面。最近最少使用頁面連結表430提供一種由頁面緩衝器415收回頁面的機制。如同前述’頁面緩衝位置416a，··.，416i, ·..，他的伯據者可以分為讀取快取、串流快取、寫入快取、以及空閒列表之其中之一。 416a,…，4l6i，串流快取以及寫入快取内所有的頁面緩衝位置 ’ 416n都是髒掉的（dirty)並且在某個記憶體陣列裝置

。貝面緩衝器415的位置是寫入快取或是串流快取因為/、是非揮發性隨機存取記憶體陣列裝置475 ^間3必㈣回非揮發性隨機存取記憶體陣列裝的成員。 32 201122812 的。非髒H 所以讀取快取頁面不被當做是辦掉用的=會立即列於空閒列表。在插回可直接使取二:則’髒掉的頁面必須寫回非揮發性隨機存取5己憶體陣列裝置475的頁面位置。到^執行另—指令（讀取或寫人）_，從串流快取所找面緩衝位置416a’…，4161，…，4i6n會晉升到寫快取。如果頁面緩衝位置仙，...，416i，...，他需 =寫入並且已經在讀取快取中發現，它也會晉升到寫入每個快取都有-個已經定義的門檻值或是標準填滿率，其可以根據工作量而動態改變。當空閒清單小於門播值之下時&回&序會啟動以在頁面緩衝器415内提供可用頁面。在執行兩個步驟的收回時，收回程序選擇頁面緩衝，置416a，…’ 416ι’…，416η，該兩個步驟包括利用計算到門檻值之實際填滿率的距離以選擇快取。由具有許多頁面緩衝位置416a，…，416i，…，416η的快取中找出其中最超過門檻值的快取，並且放開該頁面緩衝位置 416a，…，416i’ .··’ 416η。由頁面緩衝器415要回收的頁面緩衝位置416a，…，416i，…，416η由最近最少使用連結表430選擇以找到快取内最舊的頁面緩衝位置4wa，…， 416 i，…，416n。最近最少使用連結表430與頁面緩衝器快取轉譯表420 及頁面緩衝器415平行操作。老化的頁面緩衝位置416&，…， 416i，…，416η項目經由重新連結最近最少使用連結表43〇 33 201122812 内的項目而完成。例如’如果選擇讀取快取作為具有從其填滿率門檻值算起有最大距離的快取，向前連結件列似 (位置12)的向前錨點項目431a指向向前方向以到達頁面緩衝器415的最年輕項目（位置〇)。向後連結仔列434 (位置12)向後錨點項目432a指向向後方向到頁面緩衝器415 的最老項目（位置4)。對讀取快取來說連結仵列似觸是相反順序2, 4以及4, 2, G。每次參考每個老化的頁面緩衝位置416a，…，416i，…，416_，它㈣為最年輕的-個（將它解除連結（unchained)並且重新插入在最新的之前）。即，在參考頁面緩衝位置41讣（位置4)時，向前以及向後連結仔列433/434會重新排序，使得每個仔列具有指向位置4的431a，位置4依次指向位置〇,位置〇指向位置2。432a指向依次指向位置〇的位置2，位£〇指向位置 4。最近最少使用連結表43〇的每個項目皆由在連結佇列 433/43=移動其參相在㈣巾的—個位置而產生老化。如前述，要收回並且稱為鱗掉的的頁面緩衝位置 =6a，…，416i，…，41如必須具有區段，該區段已經複 '有頁面緩衝器415内的抹除頁面。非有效區段由非揮發性隨機存取記憶體陣列裝置475到頁面緩衝位置416&，…， 6ι’ ，416n。接著複製完整頁面至非揮發性隨機存取記憶體陣列裝置475中已抹除之頁面。邏輯實體位址轉譯表，调整反應非揮發性隨機存取記憶體陣列裝置仍内的新實體位置。非揮發性隨機存取記憶體陣列裝置内的先前頁面現在標記為無效，如同之後所述，該先前頁面包括頁 34 201122812 面緩衝位置416a,…，416i，···，416η内曾經為無效的區段。如果非揮發性隨機存取記憶體陣列裝置475之抹除頁面號碼低於一抹除頁面門檻值，便會觸發垃圾收集程序。請參閱第6圖，係本發明以頁面為基礎對於記憶體進行管理之垃圾收集中各表格之示意圖。為提高效能，非揮發性快閃隨機存取記憶體陣列裝置475在執行任何垃圾收集程序時，會同時選取一區塊進行抹除，以便於使用一快閃記憶體裝置之複製頁面命令。垃圾收集使用之區塊係由掃描實體區塊連結表450中的無效頁面錫點連結（i nva 1 i d page anchor chain) 455而得。實體區塊連結表450分為一向前連結佇列451及一向後連結佇列452。雙向連結表 (實體區塊連結表450中之向前連結佇列451與向後連結佇列452)可提供較佳的效能。因為前者與後者可立刻得知，故資料之擷取或插入很快。反之，使用簡單連結表則需從頭掃描以計算其前者。除了抹除總數表480需由抹除總數最低者開始之外，區塊連結並無方向性。垃圾收集使用之區塊，在搜尋無效頁面表435時會選用抹除總數最底之區塊。在垃圾收集的最後，該區塊將會被抹除。選取抹除總數最低的區塊可避免過度耗損。具有實體區塊連結表450之快閃隨機存取記憶體陣列裝置475，其向前連結佇列451與向後連結佇列452中之第一個項目（entry)分別對應於各快閃隨機存取記憶體陣列裝置475。實體區塊連結表450中，向前連結佇列451 與向後連結彳宁列452超出個別區塊項目（i nd i v i dua 1 b 1 ock 35 201122812 entry ，例如 453a，…，453i，…，453m ，及 454a，…，454i，^,45½)部份之項目即為無效頁面之錨點連結455。快閃隨機存取記憶體陣列裝置475之所有區塊皆包含於65個無效頁面錨點連結455(〇至64)之其中之一。掃描無效頁面錨點連結455係由無效頁面錨點連結64 456n與 457η開始至無效頁面錨連結〇 456a與457η結束。無效頁面錨連結〇 456a與457a指向個別區塊項目 453a’ …，453i，…453m 及 454a，…，454i，…，454m 中具有零 (〇)無效頁面者’各無效頁面錨點連結455分別表列具有一區塊列表’該區塊列表具有複數個無效頁面號碼，各無效頁面錨點連結455之個別位置用以表示各無效頁面號碼。例如，區塊100在個別區塊項目453i與454i中指向無效頁面錨點連結455之位置N+61 456i與457i，表示區塊100 具有61個無效頁面及3個有效頁面。每當快閃隨機存取記憶體陣列裝置475之一區塊增加 1個無效頁面時，無效頁面表435中代表該區塊位置438 之，效位元項目會被設定指示該頁面為無效。在區塊ι〇〇 =靶例中，區塊1〇〇對應的項目438中具有3個有效頁面，其餘61個頁面為無效。當增加丨無效頁面時，實體區塊連結表彻中代表該區塊之位置並未改變，而在無效頁面銷點連結455中之位置則改變至較高1級的位置。例如：區塊100 453i與454i從錨點連結61 456i與 57i中移除或解除連結，並插入或連結至錨點連結⑽』· 36 201122812 與457j中（假設錨點連結62 456j與457j原本為空）。空的連結係以向前連結與向後連結指向自己表示。管理處理器440執行垃圾收集程序時，搜尋無效頁面錨點連結455並選取具有最高數量無效頁面之區塊，藉以將重覆複製最小化。在本範例中，垃圾收集程序將複製區塊100中之有效頁面478a、478b及478c至快閃隨機存取記憶體陣列裝置475中之另一區塊。有效頁面478a、478b 及478c被寫入區塊200 477b中已抹除之頁面478e、478f 及478g中。被選定寫入之區塊200 477b依序允許被寫入之資料。先前被寫入之頁面478d將優先於有效頁面478a、 478b及478c被複製到已抹除之頁面478e、478f及478g 中。若區塊200 447b在複製有效頁面478a、478b及478c 的過程中被填滿，則將由已抹除頁面錨連結（錨連結64) 456m與457m中選取另一已抹除之區塊。當需要寫入新的區塊時，該已抹除頁面錨連結（錨連結64) 456m與457m 係經由搜尋最低抹除總數而得。當選定一區塊477a後，其所有有效頁面478a、478b 及478c將被複製到一第二區塊477b已抹除之頁面478e、 478f及478g。在複製區塊477a之有效頁面478a、478b 及478c前，有效頁面中為”髒”的頁面緩衝器，其所有區段需先複製。快閃隨機存取記憶體陣列裝置475中所有無效區段將最先被讀取。管理處理器440執行垃圾收集程序時，於複製後將所有有效頁面478a、478b及478c在無效頁面表435中設定 37 201122812 為無效。在邏輯貫體位址轉換表400中，邏輯頁面位置2 之快取旗標410項目表示該頁面位於實體頁面位置64〇〇 478a之:貝料已被複製到索引位置為〇之頁面缓衝器中。類似地，邏輯頁面位置5 405f之快取旗標41〇項目表示該頁面位於實體頁面位置64〇4 478b之資料未保留於頁面緩衝器415中。實體位置（6404) 4〇5f被改變到新的實體位置（12811)。類似地，具有索引位置〇 426之頁面緩衝器快取表420由實體位置（6400)改變到新的實體位置 (12810)。在實體邏輯位址轉譯表445中’實體頁面位置64〇〇 446a由邏輯頁面位置2改變到一個不合法的頁面指標。不合法的頁面指標有兩個，即兩個最高位址數字（f f f f f f f Oxfffffffe)。兩者皆表示無相關聯的邏輯頁面數字。位址數字Oxffffffff表示該頁面已被抹除，位址數字 Oxfffffffe表示該頁面為無效。其中，邏輯位置2被改變到不合法的頁面指標〇xfffffffe表示該頁面為無效。類似地，頁面位置6404 446e由邏輯位置5改變到不合法的頁面指標 Oxfffffffe。項目 6401 446b、6402 446c 及 6403 446d先前被設定為無效，故具有不合法的頁面指標

Oxfffffffe。頁面位置 12810 446f 及 12811 446g 分別由不合法的頁面指標〇Xffffffff (已抹除頁面）改變為邏輯頁面數子2及5。當區塊1〇〇中所有的頁面皆在無效頁面表435中顯示為無效，則區塊100 477a抹除完畢。當快閃隨機存取記憶體陣列裝置475之區塊1〇〇 438 38 201122812 被抹除，可易於達到耗損平衡。耗損平衡程序的模式，在於令第4圖所示之快閃隨機存取記憶體陣列裝置375均勻地損耗。請參閱第7圖，為本發明以頁面為基礎對於記憶體進行管理之耗損平衡中各表格之示意圖。在本實施例中，假設每區塊包含有64個頁面，則區塊100 477a之起始位置與頁面6400 478a之起始位置相同，而區塊200 447b之起始位置與頁面12800 478b之起始位置相同。在本發明的耗損平衡程序中，最新抹除的區塊200 477b在抹除總數表480中之對應位置482b將會增加。將位置482b之抹除總數值與一滑動視窗之抹除總數 (s 1 iding window)進行比較，若大於滑動視窗之抹除總數，則最新抹除之區塊接收來自具有最低抹除總數之區塊之資料。該滑動視窗之抹除總數由搜尋抹除總數表480所得最低抹除總數加上一區塊抹除總數之門檻值而得到。若有複數個區塊具有相同的抹除總數，則有效頁面最少的區塊將被指定為新的空閒區塊。若最新抹除之區塊200 482b 之抹除總數大於滑動視窗之抹除總數，則具有最低抹除總數之區塊100 482a將被轉移至最近抹除之區塊200 482b。其轉移係依序複製所有有效頁面478a、478b與487c至最近抹除區塊200 482b之頁面478j、478k與487k，並忽略所有無效頁面47811與478卜區塊100 48213之無效頁面47811 與478 i變成區塊末端之已抹除頁面478m，做為後續寫入之用。如前述，無效頁面之數目由無效頁面表435取得。 39 201122812 無效頁面表435以一 64位元字元標示每一區塊盔面，其中各位元分別顯示對應之頁面為有效437a”、” 437b 及437c或無效437d。一頁面從區塊100 477a複製至區塊200 477b時，邏輯實體位址轉譯表400必須更新。欲得知快閃隨機存取記憶體陣列裝置475中邏輯頁面與有效實體頁面478&、47肋及478c的關聯，則需存取實體邏輯位址轉譯表445。頁面 6400之索引446a顯示其關聯頁面為邏輯頁面2。頁面64〇〇之索引446e顯示其關聯頁面為邏輯頁面5。邏輯頁面2之索引405c及其快取旗標410顯示該頁面已被複製到第4圖所示之頁面緩衝器415。頁面緩衝器快取表42〇之項目426 中實體頁面位置由6400改變為12800。實體邏輯位址轉譯表445之項目446a由邏輯頁面2更新為不合法頁面指標 Oxfffffffe而表示為無效頁面◊索引4〇5f顯示該頁面未保留於頁面緩衝器415中，並由實體頁面位址64〇4改變為新的實體頁面位址12801。實體邏輯位址轉譯表445中邏輯頁面5之項目446e改變為不合法指標〇xfffffffe表示為無效。並將新頁面478j與47汕由已抹除頁面之不合法指標Oxffffffff分別更新為邏輯頁面2實體位址128〇〇 446f及邏輯頁面5實體位址12801 446g。有效頁面478c 亦適當地更新其實體頁面位址。複製之後，區塊1〇〇 477& 為已抹除，並成為新的空閒區塊，可寫入新頁面。具有空閒頁面之區塊200 482b被登記到耗損平衡表485中。若區塊100 477a中具有無效頁面，已抹除之區塊2〇〇 477b在 201122812 耗損平衡之複製程序中將不會被完 |又几王復蓋，而會刹餘都公面二耗損平衡表485用於暫時保留未被覆寫之頁面之位址。當一區塊被寫滿時， ^ 丄 a在取用新的已抹除區塊之刚檢查耗損平衡表485中是否纪挤1 士# ^ ^ ^ τ疋舍°己錄具有空閒已抹除頁面之區塊。而這些區塊中之空間ρ姑二間已抹除頁面將會優先被寫入利用。在抹除總數表480中，各區塊之抹除總數皆位於__最小抹除總數值與最小抹㈣數值加上—門餘之滑動視窗之中。該最小抹除總數值為快閃隨機存取記憶體陣列裝置 475中所有區塊貫際上之最低抹除總數。該抹除總數門播值’通常單階儲存單元（single level⑶⑴為4_，多階儲存單元（multiple level ce⑴為512。快閃隨機存取記憶體陣舰置475之抹除區塊連結係以各區塊之抹除總數排序。當區塊之抹除總數超過該滑動視窗抹除總數，耗損平衡程序將掃描抹除總數表以取得一具有最低抹除總數之區塊為取代區塊，並將兩區塊交換。若同時有多個區塊具有最低抹除總數，則選取具有最多無效頁面者。該最低抹除總數值於掃描抹除總數表480後，依據掃描結果更新。最低抹除總數值更新後，若仍有交換區塊之需求，則耗損平衡程序將再次被執行。滑動視窗之值亦需根據最低抹除總數之更新而重新計算。前述基於頁面管理快閃記憶體之讀取、寫入、區塊抹除等等作業模式可由一獨立設計之記憶體管理電路實施。此外’本發明之基於頁面之快閃記憶體管理亦可由微控制 41 201122812 器執行一管理程式實施。其中，該微控制器連接一儲存有管理程式或韌體之電腦可讀媒體，當微控制器執行該管理程式或韌體時，即可實施前述之快閃隨機存取記憶體陣列裝置之管理。管理快閃隨機存取記憶體陣列裝置之韌體為一多執行線程程式，可分為複數層或執行線程，分別執行收回程序、垃圾收集及耗損平衡等。各執行線程為平行執行，並分別由對應的門檻值觸發。當可用頁面緩衝器減少時，由一讀/ 寫命令觸發快取收回程序。”髒”頁面收回程序需進行頁面抹除，當已抹除區塊之數量太少時，頁面抹除動作將觸發垃圾收集程序。垃圾收集結束後，區塊為已抹除。而當區塊之抹除總數太高時，區塊之抹除動作將觸發耗損平衡程序。在本實施例中，該多線程程式用以管理快閃隨機存取記憶體陣列裝置，該多線程程式係由管理處理器（340於第 4圖或440於第6圖與第7圖）執行。該多線程程式包含有一閒置執行線程（id 1 e thread)，當收回執行線程、垃圾收集執行線程或耗損平衡執行線程之門檻值未達到時，則閒置執行線程將會被執行。該程式通常執行一迴圈，如下所示：

While (TRUE) {

WaitEvent (SomeEvent);

Handle SomeEvent; 42 201122812 其中，WaitEvent函式在對應之事件（event)未發生時 (即各執行線程之門檻值未達到），會令管理處理器34〇、 440執行之作業系統排程器（scheduler)切換（⑽丨忧乜）至其他的工作（task)。該閒置執行線程中包含有一睡眠命 π，*所有執行線程都在等待狀態時，可命令處理器進入睡眠狀態。 ° 請參閱第8圖，為本發明以頁面為基礎管理非揮發性隨機存取記憶體陣列裝置進行讀取資料的步驟流程圖。X最頂層只會看到頁面緩衝器快取，一讀取指令要求邏輯頁面位址之頁面緩衝器快取包含有頁面資料。開始進行讀取動作，如步驟500所示，主要對非揮發性快閃記憶體中一連串區段的被需求區段進行讀取，並對該需求區段的邏輯區 1又位址進行解碼的動作，如步驟505所示。ΑΤΑ標準之讀取及寫入的指令包括有一位址，且該位址指向一需求的邏輯區段號碼（SN)及一區段總數（SC)。讀取及寫入的指令起始於區段號碼，並處理區段數所指出之連續區段號碼。如第4圖所示，該邏輯位址可定義及界定出非揮發性隨機存取記憶體陣列裝置内之區段、頁碼、區塊及晶片的位置。邏輯頁面位址（如第4圖所示之327、328及329)指向需求的頁面，並對非揮發性隨機存取記憶體陣列裝置内的頁面進行項取，如步驟51 〇所示。邏輯頁面位址為邏輯實體位址轉譯表515的索引，邏輯實體位址轉譯表515包括有被讀取之需求資料頁面的實體位址項目516。快取旗標517標示出資料頁面是位於非揮發性隨機存 43 201122812 取s己憶體陣列梦署七+ 人· 頁面緩…戈頁面緩衝器内。若資料頁面不在内，則在非揮發性隨機存： 4的實際貫體位址將會在實體位址項目516中貝枓頁面為頁面緩衝器，進入：引，實體位址項目516中。藉由檢查快二3 =求的資科頁面是否位於頁面緩衝器快取，如=;；若頁面資料位於頁面緩衝器緩衝器快取555讀取百而“ 會從頁面中細分成之區段資料將^^ 550所7F。從頁面資料輪至Ή心付合傳輸協定之格式陸續分頁傳 =至外部主機電路，如步驟565所示！址的快取旗標517 只囬位機存取記憶體陣列裝。』未被從非揮發性隨出空閒列表是否未被已=空間列表快取檢查 ΐ二非揮發性隨機存取記憶體陣列裝置接收貝面貝枓，如步驟57 頁面緩衝器快取區係為空閒狀：:：列：未:佔用且沒有行=態則一收回步驟將會被執 575 m - 夕近最少使用緩衝器快取位置，如步驟程序已Γ赤若有足夠的空間頁面緩衝器之快取位置或收回步驟‘所示便===衝器位置接收頁面資料，如位址項心:::實::=5_ 取由:5=機存取記憶體陣列裝置讀取至頁面缓衝二： ;的5，如步驟590所+ π /、°頁面緩衝器位置由頁面缓衝器 44 201122812 快取表535的空閒列表中移除，並插入可為讀取快取項目之頁面緩衝器快取表535。邏輯實體位址轉譯表515可藉由設定快取旗標517的動作來進行調整，而在頁面緩衝^ 快取表535中最近最少使用連結表的頁面緩衝器位置的索引則會被設定並指派為頁面緩衝器位置’如步驟如。從頁面緩衝器快取555中讀取頁面，如步驟55〇。從頁面資料中細分成之區段資料將以符合傳輸協定之格式陸續分頁傳輸至送至外部主機電路，如步驟565所示。請參閱第9圖，本發明以頁面為基礎管理非閃記憶體寫入資料的步驟流程圖。寫入的指令需要頁面^ 衝之快取位置來接收資料頁面及相對的邏輯頁面位址。進仃寫入的動作，如步驟6〇〇所憶體中-串區段的被需求區段進行== 邏輯區段位址進行解碼的動作，如步寫驟6。== =::==定;:界:::?發性隨機存 =面位址(如第4圖所示之327，及3:=㊁求、頁面’並對非揮發性隨機麵記憶體陣㈣置内進= 買取’如步驟610所示。邏輯頁面位址為邏輯實體位址轉澤表515❺索引，邏輯實體位址轉譯表5括右讀取之需求資料頁面的實體位址項目516。有被快取旗標517標示出資料頁面是裝置或位於頁面緩衝器内。若== 頁面㈣.内’則在非揮發性隨機存取記憶體陣列裝置= 45 201122812 頁面的實際實體位址將位於實體位址項目516中。 =二:頁面為頁面緩衝器’進入資料頁面之頁面緩衝器之可，=玲在實體位址項目516中。藉由檢查快取旗標將二:二-而求的資料頁面是否位於頁面緩衝器快取，如步驟 b 1 b所示。料位於頁面緩衝器快取位置中，則頁面緩衝器快 =之快取模式項目537内之頁面緩衝器位置會被晉入百而:入决取，如步驟645所示，以使得頁面資料被寫 \面緩衝器快取咖，如步驟65〇所示。被從仙_轉#517指向的頁面#料尚未 ,^機存取記憶體陣列裝置中複製，則可由空取檢查出空閒列表是否未被佔用或是已有充分足體陣列；LI::裔位置可用以由非揮發性隨機存取記憶去^、接頁面資料’如步驟⑽所示。若空閒列表 ^用且沒有胃面緩衝的錄位置為回步驟將會被執行，以介山s, n J ^ 二出至>、一最近最少使用緩衝器快 a ^驟625所7F。若有足夠的空間頁面缓衝5|之快取位置或收回步驟p办屮体只四龙術态之接收百而-·α 几成’便可指派頁面緩衝器位置來主頁貝抖’如步驟630所示。可由邏輯實體位址轉譯 = 515中取出實體位址項目516並進行解碼咖頁面緩衝器快取表535之快取模式項g 537 _3頁5 二=器位置將會被晉升為串流快取，如步驟_所示。使侍頁面被寫入頁面緩衝器快取555，如步驟65〇所示。軔體的第二層為快取收回線程，如第8圖之步驟575 46 201122812 及第9圖之步驟.. 個通道，每個通道有δ :預::如，當固態硬碟系統具有8 逼有8個預備好的busy lines，並且右iu 個非揮發性隨機存 y nes尤、有64 線程，用以膝百°己隐體裝置。此外還包括有64個回收狀、兄下：：Γ立即由快取寫入快閃記憶體。在最佳的記憶體都具有一回收線程，但如此-來次二、、貝源（每一線程的堆疊式SRAM)。為了節省貝’、可使彳讀數個快閃日0日#制—個回個、4個或8個快閃晶片共用一個線程。 :^最大頁面使用門檻值時，收回線程便會開始作用。最大頁面使用門檻值為頁面緩衝器内之頁面資料之頁面位置的最大數量。當收回線程^成之後，頁面緩衝器快用的空閒頁面緩衝器的數量將會大於最大頁面緩衝器門檻值。最大頁面使用Η梭值及最小空閒頁面緩衝值必須是適當選擇的門檻及可能需要隨著各個時間之工作量來進行調整的Η檻。主要的目標是隨時都有可用之空閒頁面緩衝器之快取位置’以避免需要頁面緩衝器接收頁面資料時，軔體的頂層有延遲的情形。、 ^請參閱第l〇a圖及第l〇b圖，為本發明以頁面為基礎 f理頁面緩衝器之頁面收回之流程圖。頁面收回的線程如上所述，並可於快取頁面緩衝器之空閒頁面緩衝器之快取位置的數量過低時進行。如上所述，當有足夠之頁面緩衝器位置被指派至空閒列表快取，便不會進行頁面回收線程。回收的動作可釋放頁面緩衝器位置，若快閃記憶體髒的（串流快取或寫入快取）時，則可藉由將頁面資料内容寫 201122812 回其中。管理處理器340或44〇(如操作系統的時程表可控制回圖或第7圖所示）之表快取構件的數量大於最小起始’並可在空閒列動，如步驟谓所示。空閒列Hi緩衝器門摇值時起空閒頁面緩衝器門棰值進行比對。\1件的數篁可與最小童令旦士Μ旦 ^ 右二閒列表快取構件的到=閒㈣t空閒頁面緩衝器㈣值，肋到步驟700直 '的數量小於最小空閒頁面緩衝器門檀值為止。母一個Ί買取快取、宜拙合km , 寫入快取及串流快取的填充率都曰被计具出’如步驟71〇、近最少使用遠姓矣以楚e 及720。如上所述’在最 =用連、、、。表(如第5圖之43。)中包括有每一個讀取寫入快取及串流快取之最近被使用的順序。此外，面緩衝器快取被區分成複數個快取，且每—種型式的快 =都可以㈣進行調整。快取的回收是以基於偏離門植值的差異為鮮’且⑽值被建立於劃分頁面緩衝器快取，例如寫入快取佔頁面緩衝器快㈣5Q%:讀取快取佔頁面緩衝器快取的35%;而串流快取則佔頁面緩衝器快取的 ⑽。實際使料劃分的比例可能不同，因為緩衝器可能從 :個快取移到另-個，例如由讀取快取移往事流快取，或是由串流快取移往寫入快取等等。快取（如讀取快取、寫入快取及串流快取）具有最大填充率或與最小空閒頁面緩衝器門檻值的最小差距，或者是可預先由頁面緩衝器快取表535的快取模式數字來定義或選擇快取的大小，如步驟725所示。被回收之最新被使用的頁面快取緩衝位置則由最近最少使用連結表735所決 48 201122812 疋’如步驟7 3 0所示。如上所述，串流快取或寫入快取之緩衝器頁面快取為辦的。在選擇頁面緩衝器快取的最大填充率時，如步驟咖所示，主要是由被選取的頁面緩衝器快取位置是否辨的而决疋’如步驟740所示。若頁面緩衝器位置為辦的，則合由，面緩衝器快取表535中讀取區段有效旗標撕，以二斷f否將所有包括有效資料的區段被寫入非揮發性隨機存己隐體陣列裝置。所有的區段有效旗標皆會被測試，如步驟740所示，以判斷頁面緩衝器位置内的頁面資料是否效，如步驟75°所示。若所有頁面資料的區段都不可由頁面緩衝器快取表535中重新取得實體位 …ft行解碼，如步驟755所示。由非揮發性隨機存並；：I列裝置讀取有效頁面資料’如步驟760所示，二，士器快取内之有效資料與有效頁面資料重新組 σ ’如步驟765所示。 = :從頁面緩衝器位置被寫入非揮發性隨機存取口己憶體陣列裝置，如步驄則由1爭m 步驟770所不。收回頁面緩衝器位置亍及使用的快取中移出，如步驟775所 :取Π:項目則由被選取之快取中最近被使用的連結快取項目插入最：的動作，如步驟725所示。並將回收步驟7 8 〇所示。乂使用連結表的空閒列表連結中，如開始進行回㈣程序，如步驟7 頁面緩衝仿罢4 > 亚將更夕的位置進订回收，直到空閒頁面緩衝器位置的數 49 201122812 量大於最大空閒頁面緩衝門檻值。在發性隨機存取記恃體隍φ 頁面寫入非揮示，非揮發枓1½ M t /鄉770所 :=禪發11_存取記憶體陣列裝置中之 Β /衝串流快取或寫人快取收回各有效貝枓。且頁面不會由讀取快記憶體陣狀置㈣叫機存取快取之頁面内的盔效F <於項取刃…、政又。藉此所有被抹除面都可以被使用。二間抹除頁在軔體的第—層中，垃圾回收程序被區塊的抹除程序。以固^ 儿用以&裡 —/、、、以固態硬碟為例，包括有8個通道，日母個通道包括8個預借杯沾h ,. 頂備好的busy lines，並具有μ偏非揮發性隨機存取記情體梦晋。古夕、去〜加、有b4個非並可同時抹除各個輯。口收線程垃圾回收程序會紀錄那些頁面為無效或廢棄。主括有四種頁面的分級：有缺陷的頁面、被寫人的頁面、I 效的頁面及被抹除的頁面。藉由判斷區塊所具有；面的最高數量’可使得每—個垃圾回收㈣線程選擇1區塊。若有數個區塊具有相同號碼的無效頁面，則抹除次數的區塊將會被選取。凊參閱第11圖’為本發明以頁面為基礎管理之非揮發性快閃隨機存取記憶體陣列裝置之垃圾回收機制之流程圖。垃圾回收程序如以上所述，並於非揮發性隨機存ς記憶體陣列裝置内被抹除的頁面位置的數量過低時起動。當非揮發性隨機存取記憶體陣列裝置内有足夠之被抹除頁 201122812 面，則垃圾回收機制是一種無止境的空轉。管理處理器Mo 或4 4 0 (如第6圖或第7圖所示）之操作系統的時程表σ可控制垃圾回收程序的起始，並可在非揮發性隨機存取記憶^ 陣列裝置之被抹除頁面位置的數量小於被抹除頁面門檻值時起動，如步驟800所示。將非揮發性隨機存取記憶體陣列裝置之被抹除頁面位置的數量與一抹除頁面門檻值進行比對，如步驟805所示，當非揮發性隨機存取記憶體陣列裝置之被抹除頁面區的數量小於抹除頁面門檻值，其他線程開始且不斷地循環過程（如步驟8〇〇)，直到可使用之抹除頁面區的數量大於抹除頁面門檻值為止。若否，則垃圾回收動作則不會開始進行。當被抹除頁面位置的數量低於抹除頁面門檻值時，便可搜尋實體區塊連結表450,並找出具有最大無效頁面的區塊，如步驟810所示。區塊的選擇是位了藉由檢視實體區塊連結表450之無效頁面錨點連結456a..... 456η及 457a..... 457n找出垃圾收回。實體區塊連結表450被區分成向前連結佇列451及向後連結佇列452。之向前連結佇列451及向後連結佇列452的第一項目與非揮發性隨機存取記憶體陣列裝置之非揮發性隨機存取記憶體裝置的各個區塊相對應。向前連結佇列451及向後連結佇列452的項目疋無效頁面的錨點連結455，且向前連結佇列451及向後連結佇列452橫跨特定的區塊項目453a，…，453m及 454a，…’ 454m。非揮發性快閃記憶體的所有區塊為的個非揮發性隨機存取記憶體裝置（〇...64)之無效頁面錯點連結 51 201122812 陣列之其中一個。非揮發性隨機存取記憶體裝置之無效頁面錯點連結陣列將會被掃描’並由無效頁面的錨點連結64 456m及457m開始’並至無效頁面錨點連結〇 456a及457a 為止。無效頁面錨點連結〇 456a及457a指向各個具有零 (〇)無效頁面之區塊項目453a，...，456111 及…，454a，...454m，並可藉由無效頁面之區塊項目 453a，…，456m及…，454a，…45½來呈現無效頁面的錨點連接455，再者，各個無效頁面的錨點連接455具有一無效頁面數量之區塊列表。當被具有最大無效頁面的區塊被選定時，將會進一步判斷區塊内所有的頁面是否皆為無效，如步驟815所示。右不是所有胃面都是無效’則在當下寫入區塊内之被抹除頁面的實體位址將會由被抹除區塊被指派至有效頁面的邏輯位址’如步驟820所$。有效頁面資料則會由將被抹除的區塊複f至非揮發快閃記憶體之現行寫入區塊的頁面位置。要注意的是垃圾回收門檻可同時被多個非揮發性隨機存取記憶體裝置所執行。在無效頁面表435中設定抹除區塊的複製頁面為無效’並設定目前寫入區塊之新的複製為有效頁面資料，如步驟830所示。邏輯實體位址轉譯表4〇〇被更新並映射邏輯頁面號碼指向非揮發性隨機存取記憶體裝置内新的實體區的邏輯頁面。若邏輯頁面號碼位於快取頁面緩衝器’則決取頁面| 42G將會更新。當所有頁面在測試後皆為無 ’ 士 v驟815所示，則該區塊將會被抹除，如步驟gw 52 201122812 所示。所有被抹除區塊的頁面具有所有的邏輯頁面號碼，設置於實體邏輯位址轉譯表445内並設定為具有不合法位址碼(Oxffffffff)之抹除頁面’如步驟84〇所示。抹除總數表480會記錄增加的區塊抹除總數，如步驟845。在抹除-個區塊時，耗損平衡料將會執行，以確保所有的區塊具有大約相同的抹除總數，以使得各非揮發性隨機存取記憶體裝置的耗損㈣。則抹除頁面的總數再次盘抹除頁面門檻值比對，如步驟8〇5~示，且垃圾回收步驟將會重新開始或停止，如步驟840所示。耗損平衡程序的執行是為了使得非揮發性隨機存取記憶體陣列裝置的使用較為平均’並使得非揮發性隨機存取纪憶體陣列裝置各個部分的損壞時間較為相近。在垃圾回收程序中各個區塊的抹除後，抹除記數表之所有區塊的抹除總數將會被監看。非揮發性隨機存取記憶體陣列裝置的各個區塊的抹除總數位於滑動視窗内，滑動視窗之抹除她數是以最小區塊抹除總數加上抹除總㈣檻值為基礎。區塊的抹除總數大於滑動視窗之抹除總數，則一具有最：區塊抹除總數的區塊將複製到此超過滑動視窗之抹除總數之區塊中’然後’該具有最低抹除總數之區塊成為一新的可寫入區塊。耗損平衡程序具有_模式：動態耗鮮衡程序及^ 祕損平衡㈣。在㈣耗損平衡料下，#有大於1 了用_除區塊時’則會選擇最小抹除次數的區塊。仏〜耗抽平衡&序下，—部分的非揮發性隨機存取記憶體『 53 201122812 歹J裝置會被視為讀取資料（靜態資料），且該讀取資料往往是很少被讀取的。例如讀取資料可為節目、歌曲、電影等等。具有南抹除資料次數的區塊則會與低抹除次數的區塊交換這種父換可為高寫入區塊與低寫入區塊（靜態資料）的父換。本發明貫施例的方法及裝置可同時使用動態平均模損程序及靜態平均模損程序。明參閱第12a、12b及12c圖，係用以說明本發明以頁面為基礎管理非揮發性快閃隨機存取記憶體陣列裝置之一耗損平衡知序之步驟流程圖。在垃圾收集程序期間之一區塊被抹除之後，藉由收回（方塊9〇2)最新抹除區塊之抹除總數，以啟動損耗平衡程序（方塊9〇〇)。最新抹除區塊之抹除總數將存在於前述滑動視窗内，該滑動視窗之抹除總數之範圍亦可為其中一區塊之最低區塊抹除總數加上一抹除總數之門檻值。例如，對非揮發性多層次快閃隨機存取記憶體晶片而言，該抹除總數門檻值大約為512，但對非揮發性單層次快閃隨機存取記憶體晶片而言，該抹除總數門檻值大約為4096。相較於最新抹除區塊，存在於非揮發性快閃隨機存取記憶體陣列裝置内所有區塊中具有最大抹除總數之一區塊，將藉由檢索抹除總數表48〇而被發現。該抹除總數表 480也將被檢索以發現具有最小抹除總數之區塊，如步驟 904所示。滑動視窗之一抹除總數將被確定數量，如步驟 906所示’其為具有最小抹除總數之區塊的抹除總數再加上抹除總數門植值（最低抹除總數，其中N是為抹除總數 54 201122812 ^插值）。為了更好的損耗平衡，抹除總數表彻將被婦 :二：得所有非揮發性快閃隨機存取記憶體裝置之所有搞…、束除總數。如果完整的掃描將花#過多的時間，一的=概方法疋可隨意的啟動及檢索該抹除總數表彻矣，疋口P分（例如一半），或者是隨意經過該該抹除總數表〇的一部分。如果一種不充分的掃描定具有最小採除總數之區塊時，一種隨機函數(r: —⑽）將被援用而檢索出具有最小抹除總數的區塊。如果掃描至抹除總數表彻尾端，將從起端繼續開始掃描。〃最新抹除區塊的抹除總數將與滑動視窗之抹除總數進行比較，如步驟908所示。假如兩者抹除總數之差距不大於抹除總數門檻值時’該損耗平衡程序將被終止，如步驟 930所示。假如兩者抹除總數之差距是大於抹除總數門檻值時，具有最小抹除總數之區塊將被指定為最新可寫入區塊（new spare b 1 ock)。具有最小抹除總數之區塊的所有頁面將被測試以決定是否所有的頁面都是無效的，如步驟 910所示。假如並不是所有頁面無效的’則該具有最小抹除總數之區塊的有效頁面將被複製至最新抹除區塊，如步驟912所示，具有最小抹除總數之區塊的被複製頁面將被没疋成無效的，如步驟914所示，而存在於新抹除區塊之新的複製頁面則被設定成有效的，如步驟914所示，邏輯貫體位址轉澤表515也將被更新。如果快取旗標517传指示邏輯頁面是被快取的’則頁面緩衝器快取表535將被更新，以致使包含有最新抹除區塊的實體位置及快取位置之 55 201122812 頁面緩衝器位置538將被導入寫入快取（write cache)，而寫入快取則是儲存於頁面緩衝器快取表535的快取模式項目（cache mode entry)537内。該複製程序將一直被執行，直到所有頁面變成無效為止，而在這段時間内，具有最小抹除總數之區塊中的頁面的有效性也將一直被測試，如步驟910所示。無效頁面將不會被複製，且具有最小抹除總數之區塊的無效頁面將成為存在於該最新抹除區塊内的抹除頁面。值得注意的是，有效頁面將被持續的複製至最新替換區塊 (new replacement block)中。例如，如果該替換區塊具有三個無法被複製的無效頁面，則這最新抹除區塊的最後三個頁面也將不會被改變及保持抹除。當具有最小抹除總數之區塊的所有頁面都是無效後，它就會被抹除，如步驟916 所示。具有最小抹除總數之區塊的頁面將被設定成不合法位址碼（illegal address code)，如步驟918所示，以成為一儲存於實體邏輯位址轉譯表445的抹除頁面 (Oxffffffff)。抹除總數表480將增量，如步驟920所示，以成為一具有最小抹除總數之區塊。如果具有最新複製頁面之替換區塊具有抹除頁面，將登入於損耗平衡表485，如步驟922所示，被作為一當現行寫入區塊已滿時可被使用的可寫入抹除頁面，而損耗平衡程序也將在此時被終止，如步驟9 3 0所示。然而，在另一方面，如果替換區塊是持續被需要時，這個程序也會被重覆確定。 56 201122812 以頁面為基礎管理之一種非揮發性體陣列裝置的-些實施例中，這三個層:機存取· 集、及損耗平衡）當有需要時將可同時執行^、垃圾收收集程序將跑在讀取及寫人操作之前被執行^ ==内之頂層具有頁面緩衝器位置。本=頁頁 =:Γ僅可適用於前述幾個少數實施例而已：可期待適用於不限制頁面緩衝器位置。先前所描述實施例中，主要是揭露一種具有頁W 取、寫入及區塊層級抹除功能，並以頁面為基礎管理之^ 揮發性快閃隨機存取記㈣陣職置，它可提供—種很高執仃力之任意寫人功能。而在其他實施例中，主要是揭露一種以次區塊之使用來替代頁面…個次區塊將具有許= ，而-個區塊又包含有複數個次區塊。大量次區塊將思才曰所有内部表列之大小將被縮減，次區塊將重組總增加及垃圾收集總減少。具有大量次區塊將可提供持續性寫入及惡劣之任意寫入。又，在其他實施例中，於同一時間内將可使用不同之次區塊尺寸大小，藉此以達到可依據工作量而致使隨意及持續性之寫入有更完美的執行。實務上，在一次區塊内之頁面數量最好是2的次方數 (例如1、2、4、8、16、32)，而每一個區塊所能保證之頁面數量也是可被N整除，不帶有任何餘數。次區塊之被建構基本上有兩種方式：其中一種是一個次區塊（或是替代' 一特別頁面）是一實體區塊之部分，由於一個實體區塊將被 57 201122812 分割成多個次區塊，以致使具有2倍數之頁面。例如，如果一區塊包含有64個頁面，且具有16個次區塊，則一個次區塊將包括有4個實體頁面。區塊表將保持原有之數量’但頁面表（邏輯實體位址轉譯表4〇〇及實體邏輯位址表 455)則會只有四分之一大小。在這個實施例中，寫入一個次區塊就是持續性寫入連續的4個頁面。另外個方式是取組成超級區塊（s叩er-block)來當作是非揮發性快閃隨機存取記憶體陣列裝置所分割之區塊。例如，可從四個不同的非揮發性快閃隨機存取記憶體陣列裝置中各取一個區塊來組成一超級區塊。一個四頁面次區塊將具有四個實體頁面’而每—個實體頁面都是從不同的非揮發性快閃隨機存取記憶體陣列裝置中而來。如此將具有比較小的頁面表及比較小的區塊表，而快取管理也將依，超級區塊之數量而定，超級區塊之數量將是實體區塊數I的-小部分。在這個由四個不同的非揮發性快間隨，存取記憶體㈣裝置來組成四個區塊之實施例中，超級之數里將是實體區塊數量之四分之一。另外，每一個次區塊將可以被平行態樣寫人，因為—個次區塊之所有實，頁面將位於不同之晶片中，因此可提供以交錯的平行方式來進入非揮發性快閃隨機存取記憶體陣列裝置。、上所述者，僅為本發明之一較佳實施例而已，並非 ^限定本發明實施之範圍，即凡依本發财請專利範圍均庫：本：Γ Γ及精神所為之均等變化與修飾， Μ匕括於本發明之申請專利範圍内。 58 201122812 【圖式簡單說明】第la圖·為習用雷腦^ 第ib圖:為習用快閃财示意圖。邏輯位址之結構示意/存Μ巾絲記憶體⑽测之第lc圖.為習用快閃儲取及寫入之操作示意圖統中長駐記憶體（SSD)100讀第2圖.為本發明以百；& # 之太，系統一較佳實施例之區固態硬碟之資礎對於記憶體進行管理之― =圖.為本發明固態硬碟讀取及寫入—實施例之操作示第5圖·為本發明以百而先甘圖。面為基礎之記憶體管理之表格式意第6圖：本發明以頁面收集中各表格之示意圖^礎對於記憶體進行管理之垃圾第7圖.為本發明以頁面為損平衡中各表格之示意I 仏己Μ進仃官理之耗 =====㈣機她為基礎管理非揮發性㈣記憶體第l〇a、i〇b圖：為本之頁面收回之·®。頁面為基礎管理頁面緩衝器 59 201122812 第11圖：為本發明以頁面為基礎管理之非揮發性快閃隨機存取記憶體陣列裝置之垃圾回收機制之流程圖。第12a、12b、12c圖：為本發明以頁面為基礎管理非揮發性快閃隨機存取記憶體陣列裝置之一耗損平衡程序騍流程圖。乂 1〇〇 110 120 13〇 15〇 155 160 167 2〇〇 202 204 210 220 225 232 105 中央處理器 115 輸入/輸出裝置 125 控制器 165 區段 170 位元 201 區段 203 區塊 205 實體位址解碼器 215 控制邏輯器 222 區段資料 230 邏輯實體轉譯表主要元件符號說明】長駐記憶體暫存記憶體糸統匯流排反及閘快閃陣列非揮發性快閃隨機存取記憶體裝置非揮發性快閃隨機存取記憶體裝置頁面 ECC錯誤更正位元位址訊號頁面邏輯位址控制訊號資料頁面緩衝器項目 235 240 非揮發性快閃隨機非揮發性快閃隨機存取記憶體陣列裝置存取記憶體晶片 201122812 242 區塊 245 非揮發性快閃隨機存取記憶體晶片 247 區塊 250 實體位址 260 資料匯流排 270 陣列控制訊號 300 資料儲存系統 305 輸入/輸出轉接 310 位址訊號 315 資料訊號 320 控制訊號 325 邏輯位址訊號 326 區段 327 頁面 328 區塊 329 晶片位置 330 資料訊號 332 新資料 335 控制碼 340 管理處理器 342 管理處理控制器 344 韌體記憶體 345 實體位址解碼器 350 頁面緩衝器 355 邏輯實體轉譯表 356 位置 360 實體位址訊號 365 資料 370 陣列控制訊號 375 非揮發性隨機存取記憶體陣列裝置 376a-n 晶片 377a-n 區塊 378a-η 頁面 378i 頁面 378j 頁面 379a_n 區段 380 實體邏輯位址表 382 頁面緩衝器快取表 384 無效頁面表 386 抹除總數表 387 390 耗損平均表實體區塊連結表 388 缺陷區塊表 61 201122812 395 動態隨機存取記憶體陣列裝置 396 位址訊號 397 控制時序訊號 398 資料 400 邏輯實體位址轉譯表 405a_n 頁面位置 410 快取旗標 415 頁面緩衝器 416a-n [項目位置 420 頁面緩衝器快取轉譯表 425 快取頁面表 426 實體頁面位置 427 快取模式旗標 428 區段有效旗標 429a- n 項目位置 430 最近最少使用連結表 431a- d 向前錨點項目 432a- -d 向後錨點項目 433 向前連結佇列 434 向後連結仵列 435 無效頁面表 437a~d 頁面 438 區塊位置 440 管理處理器 445 實體邏輯位址轉譯表 446a- -g 實體頁面位置 450 實體區塊連結表 451 向前連結彳宁歹|J 452 向後連結仵列 453a- -m 區塊項目 454a- m 區塊項目 455 錨點連接 456a-m 描點連結 457a-n 錨點連結 475 快閃隨機存取記憶體陣列裝置 477a- b 區塊 478a- m 頁面 480 抹除總數表 482a-b 區塊 485 耗損平衡表 62 201122812 515 516 535 537 555 邏輯實體位址轉譯表實體位址項目 517 快取旗標頁面緩衝器快取表 536 區段有效旗標快取模式項目 538 頁面緩衝器位置頁面緩衝器快取 63

Claims

201122812 七、申請專利範圍： 1 · 一種資料儲存系統，其包括有：一非揮發性記憶體陣列裝置，包括有複數個次陣列，各次陣列包括有複數個區塊，各區塊包括複數個次區塊，各次區塊包括有複數個區段，各區段包括有複數個位址組之記憶單元；一官理處理器，與該非揮發性記憶體陣列裝置進行通信，用以提供一控制訊號，以在該非揮發性記憒陣列裝置中對於所選擇的該次區塊進行程式化:抹除及讀取動作；一次區塊緩衝器，與該非揮發性記憶體陣列裝置及該管理處理器進行通信，接收該控制訊號，該次區塊緩衝器切分成複數個次區塊片段以分別暫存該次區塊資料，並根據該控制訊號以決定從該非揮發性記憶體陣列裝置讀取該次區塊資料或傳送該次區塊資料至該非揮發性記憶體陣列農置；及一邏輯實體轉譯表，接收一需求的邏輯次區塊位址，轉換該邏輯次區塊位址為一實體次區塊位址，與該管理處理器進行通信並將該實體次區塊位址傳送至該管理處理器，以確認該非揮發性記憶體陣列裝置中一需求次區塊的一實體位置；其中’該邏輯貫體轉譯表包括有一快取旗標表，其用以確認目前該次區塊緩衝器是否有該需求的邏輯次區塊位址。 64 201122812 2 t申請專利範圍第1項所述之資料儲存系統，其中該 -人區塊為-頁面、—在非揮發性記憶體陣列裳置中單一區塊所組成的超級頁面或-經由多個頁面與—區塊所組成的超級頁面。 °° 如申请專利範圍第i項所述之資料儲存系統，尚包括有一輸入/輸出轉接器，其連接在-外部端Π、該次區塊緩衝ϋ及該管理處理器間，用以接收—邏輯位址、該控制訊號及—被通信規格所編碼的區段資料，並轉換該邏輯位址、該控制訊號及該被通信規格所編碼的區段資料成該非揮發性記憶體陣職的規格。 & 4 ·如中請專利範圍第3項所述之資料储存系統，尚包括有:實體位址解碼器，與該輸人/輸出轉接器及該邏輯貫體轉譯表進行通信，從該輸入/輸出轉接器接收該邏輯位址，轉送該邏輯位址至該邏輯實體轉譯表， ^亥邏輯實體轉譯表接收該實體位址，與該管理處理器進行溝通，以確認-需求的邏輯次區塊資料存在於 -該次區塊緩衝器或該非揮發性記憶體陣列裝置中。 )·如申請專利範圍第4項所述之資料儲存系統，尚包括有一次區塊缓衝器快取表，與該管理處理器進行通信，該次區塊緩衝器快取表包括有—實體：區塊號碼，其用以確認在該非揮發性記憶體陣列裝置中之一實體位置，該實體位置與在該次區塊緩衝器中之一次區塊位置相關聯，一快取類型項目用以標示一快取類 65 201122812 型，而一狀態項目根據一有效狀態分類該次區塊之區段資料，且該快取類型項目及該狀態項目佔用於該實體位置中。 6·如申請專利範圍第5項所述之資料儲存系統，其中該快取類型包括有一讀取快取、一串流快取、一寫入快取及一空閒列表。 7 .如申請專利範圍第5項所述之資料儲存系統，尚包括有一最近最少使用表，其包括有複數個連結指標，該連結指標用以決定一最近最少使用的次區塊資料存於該次區塊緩衝器中。 8·如申請專利範圍第7項所述之資料儲存系統，其中該次區塊緩衝器透過該管理處理器執行一收回程序，該最近最少使用的次區塊資料從該次區塊緩衝器中收回且寫入於該非揮發性記憶體陣列褒置中所指定的該次區塊，而該次區塊緩衝器中該次區塊位置並附加至該次區塊緩衝器快取表之該空間列表内。 9 ·如中請專利範㈣！項所述之f料儲存系統，尚包括有一無效次區塊表，其用以指示該非揮發性記憶體陣列裝置中所選擇的該區塊及其該次區塊為有效的。 10·如ί請專利範圍第1項所述之資料儲存系統，尚包括有-實體邏輯表用以映射該非揮發性記憶體陣列褒置之該實體位置至該邏輯位置，該實體邏輯表中之一不合法的次區塊號碼用以指示該實體位置於該實體邏輯表令已抹除或無效的。 66 201122812 .^申請專利範圍第i項所述之f料儲存系統，尚包括一抹除總數表，與該管理處理器進行通信，以對於 ^非揮發性記«陣縣置中各區塊記錄—抹除總数0 如申5月專利範圍第1項所述之資料儲存系統，尚包括 f 一與該㈣處理n進行通㈣實龍塊連結表，該 I體，塊連結表包括有—包含複數個指標之連接列二該連接列表包括有—财指標，其用以在該區塊中定義出該無效次區塊號碼。 ^申明專利範圍第11項所述之資料儲存系統，其中 j非揮發性記憶體陣職置透過該管理處理器執行 j垃圾收集程序，—㈣指標用以指出在該非揮發性，憶體陣列裝置中具有該最大無效號碼次區塊的該區鬼進而允許具有該最大無效號碼次區塊的該區塊選擇進行抹除的動作。 4 ★申叫專利範圍第丨3項所述之資料儲存系統，其中在y損耗平衡程序中，一抹除區塊的抹除總數比較於一最大總數，若該抹除區塊之抹除總數超過該最大總數’選擇另-具有最低抹除總數之區塊，且該具有最低抹除總數之區塊中全部有效的次區塊複製至該抹除區塊之低階級次區塊中，然後，該具有最低抹除總數之區塊將進行抹除動作，而該具有最低抹除總數之抹除區塊成為-新的可寫入區塊，且其抹除總數將會增加。 67 201122812 15 · -種財區塊為基礎對於—快_存“進行讀取、寫入及區塊抹除之記憶鮮理電路，其巾該記憶體管理電路包括有：〜 -管理處理n，與在該快_存系統巾之—非揮發性記憶體陣列裝置進行難，用以提供—控制訊號，以在該非揮發性記憶體陣列裝置中對於所選擇的該次區塊進行程式化、抹除及讀取動作；一次區塊緩衝器，與該非揮發性記憶體陣列裝置及該管理處理n進行通信’接㈣控制訊號，該次區塊緩衝器切分成複數個次區塊片段以分別暫存該次區塊資料，並根據該控制訊號以決定從該非揮發性記憶體陣列裝置讀取該次區塊資料或傳送該次區塊資料至該非揮發性記憶體陣列裝置；及一邏輯實體轉譯表，接收一需求的邏輯次區塊位址，轉換該邏輯次區塊位址為一實體次區塊位址，與該管理處理器進行通信並將該實體次區塊位址傳送至該官理處理器，以確認該非揮發性記憶體陣列裝置中之一需求次區塊的一實體位置；其中，該邏輯實體轉譯表包括有一快取旗標表，其用以確認目前該次區塊緩衝器是否有該需求的邏輯次區塊位址。 Μ ·如申請專利範圍第15項所述之資料儲存系統，其中 δ玄次區塊為一頁面、一在非揮發性記憶體陣列裝置中單一區塊所組成的超級頁面或一經由多個頁面與— 68 201122812 區塊所組成的超級頁面。 17 ·如申請專利範圍第15項喟所述之貝枓儲存系統，尚包輸入/輸出轉接器，其連接在一外部端口、該人塊緩衝裔及該管理處理器間’用以接收-邏輯位址、該控制訊號及一被通信規格所編碼的區段 f轉換該邏輯位址、該控制訊號及該被㈣規格所編馬的區段資料成該非揮發性記憶體陣列裝置可接無的規格。夂 18·如中請專利範圍第16項所述之資料儲存系統，尚包實體位址解碼器，與該輸入/輸出轉接器及該、輯貫體轉澤表進行通信，從該輸人/輸出轉接器接收邊邏輯位址’轉送該邏輯位址至該邏輯實體轉譯表，從該邏輯實體轉譯表接收該實體位址，與該管理處理器進行溝通，以確認一需求的邏輯次區塊資料存在於該次區塊緩衝器或該非揮發性記憶體陣列裝置中。 19·如中請專利範圍第18項所述之資料儲存系統，尚包括有-次區塊緩衝器快取表，與該管理處理器進行通信’該次區塊緩衝器快取表包括有一實體次區塊號碼，其用以確認在該非揮發性記憶體陣列裝置中之一貫體位置，該實體位置與在該次區塊緩衝器中之一次區塊位置相關聯，一快取類型項目用以標示一快取類型，而一狀態項目根據一有效狀態分類該次區塊之區段資料，且該快取類型項目及該狀態項目佔用於該實 69 201122812 體位置中。 20 ·如申請專利範圍第19項該快取類型包括有一讀取快取、系統，其中快取及一空閒列表。串机快取、一寫入 21 · 22 · 23 · 24 . 19項所述之資料儲存系統，尚包括有-最近衫❹表包括有 ^ 結指標用以決定一最近早小# 1固連、、、。才曰‘，该連該次區塊緩衝器中。使用的次區塊資料存於 2請專利範圍第21項所述之資料儲存系統，其中该次區塊緩衝器透過該管理處理器執行一收回程 =，該最近最少使用的次區塊資料從該次區塊緩衝器收回且寫入所才曰疋的該非揮發性記憶體陣列裝置之該次區塊中’而該次區塊緩衝器中之該次區塊位置並附加至該次區塊緩衝器快取表之該空閒列表内。如申凊專利㈣第16項所述之資料儲存线，尚包括有-無效:欠區塊表’其心指補非揮發性記憶體陣列裝置中所選擇的該區塊及其該次區塊為有效的。如申請專利範圍第16項所述之資料儲存系統，尚包括有一實體邏輯表用以映射該非揮發性記憶體陣列裝置之該實體位置至該邏輯位置，該實體邏輯表中之一不合法的次區塊號碼用以指示該實體位置在該實體邏輯表中已抹除或無效的。 25如申請專利範圍第16項所述之資料儲存系統，尚包括有一抹除總數表’與該管理處理器進行通信，以對 201122812 錄一抹於該非揮發性記憶體陣列裝置中之各區塊記除總數。 26·如中請專利範圍16項所述之資料儲存系統，尚包括與該管理處理||進行通信的實體區塊連結表，該實體區塊連結表包括有—包含複數個指標之連接列表丄該連接列表包括有一錯定指標，其用以在該區塊中定義出該無效次區塊號碼。 27 ·如申請專利範圍第25項所述之資料健存系統，其中 X非揮發性δ己憶體陣列裝置透過該管理處理器執行一垃圾收集程序，m標用以指出該非揮發性記憶體陣列裝置之該區塊中具有該最大無效號碼次區 4的《亥區塊，進而允許具有該最大無效號碼次區塊的該區塊選擇進行抹除的動作。 28 ·如中請專·㈣27項所述之資㈣存系統，其中在:知耗平衡程序中，一抹除區塊的抹除總數比較於 /月動視1¾之抹除總數，若該抹除區塊之抹除總數超過該滑動視窗之抹除總數，選擇另一具有最低抹除總數之區塊’且該具有最低抹除總數之區塊中全部有效的-人區塊複製至該抹除區塊之低階級次區塊中，然後’ 4具有最低抹除總數之區塊將進行抹除動作，而該具有最低抹除總數之區塊成為一新的可寫入區塊，且其抹除總數將會增加。 29.如中請專利範圍第27項所述之資料儲存系統，其中在-知耗平衡程序中，計算該滑動視窗之抹除總數， 71 201122812 该滑動視窗之抹除總數為該最低區塊抹除總數加上一區塊抹除總數之門檻值。 30· —種快閃儲存系統之管理方法，其中該快閃儲存系統為一非揮發性記憶體陣列裝置所組成，其方法之步驟包括有：對於該快閃儲存系統中一非揮發性記憶體陣列裝置進行一次區塊的讀取或寫入，其步驟包括： (a )解碼έ玄次區塊之一邏輯位址； (b) 從一邏輯實體轉譯表中存取該邏輯位址，以判定该次區塊是否存在於一次區塊緩衝器快取中； (c) 若該次區塊存在於該次區塊緩衝器快取中，對於該次區塊緩衝器快取進行該次區塊的讀取或寫入； (d) 若該次區塊不存在於該次區塊緩衝器快取中，判定該次區塊緩衝器快取是否具有一空閒次區塊； (e) 若該次區塊緩衝器快取具有該空閒次區塊，分配該邏輯位址，以對於該次區塊緩衝器快取之該空閒次區塊進行讀取或寫入，該次區塊從該非揮發性s己憶體陣列震置讀取至該分配的空閒次區塊並且讀取該分配的空閒次區塊，或者該次區塊寫入至該分配的空閒次區塊中； (f) 若該次區塊緩衝器快取沒有該空閒次區塊，從該次區塊緩衝器快取中收回一最近最少使用次區塊，以製作出一空間次區塊；及 72 201122812 (g)執订步驟（e) ’對於該分配的空閒次區塊進行該次區塊的讀取或寫入。 / 31 ·,申請專利範圍第3G項所述之管理方法，其中該次區塊為-頁面、一在非揮發性記憶體陣列裝置中單一區塊所組成的超級頁面或―經由多個頁面與1塊所組成的超級頁面。 32 ·如申請專利範圍第3〇項所述之管理方法，尚包括下列步驟：接收該邏輯位址’―控制訊號及-被通信規格所編碼的區段資料；及轉換該邏輯位址、該控制訊號及該被通信規格所編碼的區段資料成該非揮發性記憶體陣列裝置可接受的規格。 & 33·如申請專利範圍第32項所述之管理方法，尚包括有記錄一次區塊緩衝器快取表之步驟，該次區塊緩衝器快取表包括有一實體次區塊號碼，其用以確認在該非揮發性記憶體陣列裝置中之一實體位置，該實體位置與在該次區塊緩衝器中之一次區塊位置相關聯，—快取類型項目用以標示一快取類型，而一狀態項目根據一有效狀悲分類該次區塊之區段資料，且該快取類型項目及該狀態項目佔用於該實體位置中。 34 ·如申請專利範圍第33項所述之管理方法，其中該快取類型包括有一璜取快取、一串流快取、一寫入快取及一空閒列表。 73 201122812 35 .如申請專利範圍第33項所述之管理方法，其中從該次區塊緩衝器快取中收回該最近最少使用次區塊，以製作出一空閒次區塊，尚包括下列步驟：查δ旬一最近最少使用表，該最近最少使用表包括有複數個連結指標；及根據5玄連結指標以判定在該次區塊緩衝器中一最近最少使用的次區塊。 36. 如申請專利範圍第35項所述之管理方法，其中從該次區塊緩衝器快取中收回該最近最少使用次區塊，以製作出一空閒次區塊，尚包括下列步驟：該最近最少使用次區塊資料寫入於所指定的該非揮發性S己憶體陣列裝置之該次區塊中，而該次區塊緩衝器中之忒次區塊位置並附加至該次區塊緩衝器快取表之該空閒列表内。 37. 如申請專利範圍第36項所述之管理方法，其中該次區塊寫入至該次區塊緩衝器快取之該分配的空閒次區塊’尚包括有下列步驟：設定一次區塊位元，該次區塊位元寫入於一無效的次區塊表中，其用以指示該非揮發性記憶體陣列裝置中所選擇的該區塊及其該次區塊為有效的或無效的。 38 ·如申請專利範圍第35項所述之管理方法，其中從該次區塊緩衝器快取中收回該最近最少使用的次區塊之後，尚包括下列步驟： 74 201122812 執行一垃圾收集程序，以產生至少一空閒次區塊。 39 .如申請專利範圍第35項所述之管理方法，執行一垃圾收集程序，以產生至少一空閒次區塊之後，尚包括下列步驟：決定該非揮發性記憶體陣列裝置中一可抹除次區塊號碼是否低於一抹除次區塊門檻；搜索一包括有一連結列表之實體區塊連結表，該連結列表包括有複數個指標，其中一指標為一錨定指標’其用以在該區塊中定義出該無效次區塊的號碼’藉以找到一具有最大無效號碼次區塊；判斷具有該最大無效號碼次區塊之該區塊中是否全部的該次區塊皆為無效；右非全部該次區塊均為無效的，將該有效的次區塊複製至該非揮發性記憶體陣列裝置中其他區塊，以及在5亥無效次區塊表中設定無效的該次區塊；及田王。P該次區塊都為無效，具有最大無效號碼次區塊的該區塊將進行抹除。 4〇如申清專利範圍第39項所述之管理方法，其中該垃圾收回％序製作出該空閒次區塊後’尚包括下列步驟： °又定一不合法的次區塊號碼以指示該抹除區塊之該實體位置在該實體邏輯表中已被抹除，並且該實體邏輯表用以映射該非揮發性記憶體陣列裝置之該實體位置至該邏輯位置。 75 201122812 41 42 •如申請專利範，5項所述之管理方法，直中其中從該次區塊緩衝器快取中收回該最近最少使用的次區塊之後，尚包括下列步驟：對於該抹除區塊進行一損耗平衡程序。，如申請專利範㈣41項所述之管理方法，其中對於该抹除區塊進行—損耗平衡程序之後，尚包括下列步驟：決疋一抹除視窗之抹除總數，該抹除視窗之抹除總數為一區塊最低抹除總數之函數；判斷该抹除區塊之一區塊抹除總數是否超過該抹除視窗之抹除總數；右该抹除區塊之該區塊抹除總數超過該抹除視窗之抹除總數，搜尋一抹除總數表，以在各抹除區塊中判斷出一具有最低區塊抹除總數之區塊；選擇該具有最低區塊抹除總數之區塊；複製該具有最低區塊抹除總數之區塊中全部有效次區塊至該抹除區塊之低階級次區塊中；抹除該具有最低抹除總數之區塊，以成為一最新的抹除區塊；在該抹除總數表中對於該最新的抹除區塊增加其該抹除總數；及分配該最新的抹除區塊為一新的可寫入區塊。如申請專利範圍第42項所述之管理方法，其中決定該抹除視窗之抹除總數之步驟後，尚包括下列步驟： 76 43 - 201122812 44 =入一抹除計數Η檻值至該最低區塊抹除總數。一種用以保留電腦程式碼之資料儲存系統，其包括有 ^控制處理11，當該控制處理H進行運料，執行一電腦程式程序以對於—快閃儲存體進行管理，其中該電腦程式程序包括下列步驟：對於該資料儲存系統中—非揮發性記憶體陣列裝置進行-人區塊的讀取或寫入，其步驟包括： (a) 解碼該次區塊之一邏輯位址； (b) 從一邏輯實體轉譯表中存取該邏輯位址，以判定該次區塊是否存在於一次區塊緩衝器快取中； (c) 若該次區塊存在於該次區塊緩衝器快取中，對於該次區塊緩衝器快取進行該次區塊的讀取或寫入； (d) 若該次區塊不存在於該次區塊緩衝器快取中，判定該次區塊緩衝器快取是否具有一空閒次區塊； (e) 若該次區塊緩衝器快取具有該空閒次區塊，分配該邏輯位址，以對於該次區塊緩衝器快取之該空閒次區塊進行讀取或寫入，該次區塊從該非揮發性記憶體陣列裝置讀取至該分配的空閒次區塊並且讀取該分配的空閒次區塊，或者該次區塊寫入至該分配的空閒次區塊中； (f) 若該次區塊緩衝器快取沒有該空閒次區塊，從該次區塊緩衝器快取中收回一最近最少使用次區塊，以製作出一空閒次區塊；及 77 201122812 (g)執行步驟（e) ’對於該分配的空閒次區塊進行該次區塊的讀取或寫入。 45 46 47 - 48 - 如申請專利範圍第44項所述之資料儲存系統，其中 4 -人區塊為一頁面、一在非揮發性記憶體陣列裝置中單區塊所組成的超級頁面或一經由多個頁面與一區塊所組成的超級頁面。 ’如申請專利範圍第44項所述之資料儲存系統，其中该電腦程式程序尚包括下列步驟：接收該邏輯位址，一控制訊號及一被通信規格所編碼的區段資料；及轉換該邏輯位址、該控龍號及該被通信規格所編碼的區段資料成該非揮發性記憶體陣列裝置可接受的規格。 & 如申請專職H第46項所述之資料儲存系統，其中該電腦程式程序尚包括下列步驟：己錄_人區塊緩衝器快取表，該次區塊緩衝器快取表與該管理纽器進行通信，該次區塊緩衝器快= 包括有一實體次區塊號碼’其用以確認在該非揮發性記憶體陣列裝置中之—實體位置，該實體位置與在該次區塊緩衝器中之一次區塊位置相關聯，一快取類型項目用以標示—快取類型，而—狀態項目根據一有效狀態分類該次區塊之區段資料，且該快取類i項目及该狀態項目佔用於該實體位置中。如申請專利範圍第47項所述之資料儲存系統，其中 78 201122812 寫入 C型包括有一讀取快取、-串流快取、 49 跌取及一空閒列表。專利範圍第47項所述之資料儲存系統，其中塊” 3塊緩衝11快取中收回該最近最少使用次區 ::製作出-空閒次區塊，尚包括下列步驟： —數==使:表’該最近最少使用表包括有複 50 據錢結指標以判定在該次區塊緩衝器中最少使用的次區塊。二：：，利軏圍第45項所述之資料儲存系統，其中广人區塊緩衝器快取中收回該最近最少使用次區 ”以裝作出-空閒次區塊，尚包括下列步驟：少使用次區塊資料寫入於所指定的該非揮發性記憶體陣列Iw ^ 裝置之3亥-入區塊中，而該次區塊緩凼二本之°亥人區塊位置並附加至該次區塊緩衝器快取表之該空閒列表内。 51 請專利範圍第49項所述之資_存系統，呈中 =:寫=次區塊緩衝器快取之該分配的空間-人£塊，尚包括有下列步驟：設塊位元，該次區塊位元寫入於一無效的次 2 其用以指不該非揮發性記憶體陣列裝置 :所選擇的該區塊及其該次區塊為有效的或無效的。 52·如申請專利範圍苐51項所述之資料儲存系統，其中 79 201122812 從該次區塊緩衝器快取中收回該最近最少使用的次區塊之後’尚包括下列步驟：執行一垃圾收集程序，以產生至少一空閒次區塊。 53.如中請專利範圍第52項所述之資料儲存系統，執行垃圾收集程序’以產生至少一空閒次區塊之後，尚包括下列步驟：決定該非揮發性記憶體陣列裝置中-可抹除次區塊號碼是否低於一抹除次區塊門檻；搜索一包括有一連結列表之實體區塊連結表，該連結列表包括有複數個指標，其中一指標為一錨定指心’其用以在該區塊中定義出該無效次區塊的號碼’藉以找到一具有最大無效號碼次區塊；判斷具有該最大無效號碼次區塊之該區塊中是否全部的該次區塊皆為無效；若非全部該次區塊均為無效的，將該有效的次區塊複製至該非揮發性記憶體陣列裝置中其他區塊，以及在該無效次區塊表中設定無效的該次區塊；及當全部該次區塊都為無效，具有最大無效號碼次區塊的該區塊將進行抹除。 54 ·如申請專利範圍第53項所述之資料儲存系統，其中該垃圾收回程序製作出該空閒次區塊後，尚包括下列步驟：設定一不合法的次區塊號碼以指示該抹除區塊之該實體位置在該實體邏輯表中已被抹除，並且該實體 201122812 邏輯表用以映射該非揮發性記憶體陣列裝置之該實體位置至該邏輯位置。 55 ·如申請專利範圍第53項所述之資料儲存系統，其中從該次區塊緩衝器快取中收回該最近最少使用的次區塊之後’尚包括下列步驟：對於該抹除區塊進行一損耗平衡程序。 56 ·如申請專利範圍第55項所述之資料儲存系統，其中對於該抹除區塊進行一損耗平衡程序之後，尚包括下列步驟：决定一抹除視窗之抹除總數，該抹除視窗之抹除總數為一區塊最低抹除總數之函數；判斷该抹除區塊之一區塊抹除總數是否超過該抹除視窗之抹除總數；若該抹除區塊之該區塊抹除總數超過該抹除視窗之抹，總數’搜尋—抹除總數表，以在各抹除區塊中判斷出一具有最低區塊抹除總數之區塊；選擇该具有最低區塊抹除總數之區塊；複製該具有最低區塊抹除總數之區塊中全部有效次區塊至6亥抹除區塊之低階級次區塊中；抹^該具有最低抹除總數之區塊，以成為一最新的抹除區塊； =數r對於該最新的抹除區塊增加其該刀配違最新的抹除區塊為一新的可寫入區塊。 81 201122812 57 ·如申請專利範圍第56項所述之資料儲存系統，其中决定一抹除視窗之抹除總數之步驟後，尚包括下列步驟：加入一抹除計數門檻值至該最低區塊抹除總數。 58 . 一種用以快閃儲存系統之抹除區塊之損耗平衡方法，其中該快閃儲存系統包括有一非揮發性記憶體陣列裝置’該非揮發性記憶體陣列裝置包括有複數個次陣列，各次陣列包括有複數個區塊，其中該損耗平衡方法包括有：决定一抹除視窗之抹除總數，該抹除視窗之抹除總數為—區塊最低抹除總數之函數；判斷δ亥抹除區塊之一區塊抹除總數是否超過該抹除視窗之抹除總數；右该抹除區塊之該區塊抹除總數超過該抹除視窗之抹除總數，搜尋一抹除總數表’以在各抹除區塊中判斷出一具有最低區塊抹除總數之區塊；選擇該具有最低區塊抹除總數之區塊；複製該具有最低區塊抹除總數之區塊中全部有效次區塊至該抹除區塊之低階級次區塊中；抹除該具有最低抹除總數之區塊，以成為一最新的抹除區塊；在該抹除總數表中對於該最新的抹除區塊增加其該抹除總數；及为配該最新的抹除區塊為一新的可寫入區塊。 82 201122812 59 60 61 . •如申請料58韻狀管理方法，其中決定該抹除視窗之抹除總數之步職，尚包括下列步驟：抹除汁數門播值至該最低區塊抹除總數。 =申:月專利範圍帛58項所述之管理方法，其中該次區塊為一頁面、一在非揮發性記憶體陣列裝置中單一區塊所組成的超級頁面或—經由多個頁面與一區塊所組成的超級頁面。 -種用以⑽儲存系統之抹除區塊之損耗平衡設備，其中該資料儲存系統包括—非揮發性記憶體陣列裝置，該非揮發性記憶體陣列裝置包括有複數個次陣列，各次陣列包括有複數個區塊，該損耗平衡設備用以執行一損耗平衡方法，其中該損耗平衡方法包括有：用以決定一抹除視窗之抹除總數，該抹除視窗之抹除總數為一區塊最低抹除總數之函數；用以判斷該抹除區塊之一區塊抹除總數是否超過該抹除視窗之抹除總數；用以若該抹除區塊之該區塊抹除總數超過該抹除視窗之抹除總數，搜尋一抹除總數表，以在各抹除區塊中判斷出一具有最低區塊抹除總數之區塊；用以選擇該具有最低區塊抹除總數之區塊；用以複製該具有最低區塊抹除總數之區塊中全部有效次區塊至該抹除區塊之低階級次區塊中；用以抹除該具有最低抹除總數之區塊，以成為一最新 83 201122812 的抹除區塊；的抹除區塊增加用以在該抹除總數表中對於該最新其該抹除總數；及用：分配該最新的抹除區塊為一新的可寫入區塊。 62 ·如中請專利範圍第62項所述之資料儲存系统，其中用以決定該抹除視窗之抹除總數之步_，尚包括下列步驟：用以加入一抹除計數門檻值至該最低區塊抹除總數。 M·如申請專利範圍第63項所述之資料儲存系統，其中該次區塊為一頁面、一在非揮發性記憶體陣列裝置中單一區塊所組成的超級頁面或一經由多個頁面與一區塊所組成的超級頁面。 84