TW200844740A - Use of a direct data file system with a continuous logical address space interface - Google Patents

Description

200844740 九、發明說明： 【發明所屬之技術領域】 本申請案大體上係㈣非揮發性記憶㈣統（諸如 再程式化半導體快閃記憶體）之操作以儲存資料且 之主機裝置轉移資料，且更特定言之，係關於資 案物件之管理。 心 【先前技術】 在較早代之商用快閃記憶體系統中，將記憶體單元之一 矩形陣列劃分為大量的單元群組，每一者儲存一標準磁碟 機磁區之資料量，亦即，512個位元組。每一群組中亦通 常包括額外量之資料（諸如，16個位元組）來儲存一誤差校 正碼(ECC) ’且可能包括與使用者資料及/或與其中儲存使 用者資料之記憶體單元群組有關的其他附加項資料。每一 此群組中之記憶體單元為可一起擦除之最小數目的記憶體 單元。亦即，擦除單位有效地為儲存一個資料區段及所包 括之任何附加項資料之記憶體單元的數目。在美國專利第 5,602,987號及第6,426,893號中描述此類型記憶體系統之實 例。需要在用資料再程式化記憶體單元之前擦除記憶體單 元為快閃記憶體之一特徵。 最通常以與諸如個人電腦、相機或其類似物之多種主機 可移除地連接之記憶卡或隨身碟的形式提供快閃記憶體系 統’但亦可在此等主機系統内嵌入快閃記憶體系統。當將 資料寫入至記憶體時，主機通常對記憶體系統之一連續虛 擬位址空間内的資料之區段、叢集或其他單位指派唯一邏 127921.doc 200844740 輯位址。如碟片作業系統（DOS)，主機將資料寫入至記憶 體系統之邏輯位址空間内的位址並自該等位址讀取資料。 記憶體系統内之控制器將自主機接收之邏輯位址轉譯為記 憶體陣列内之實體位址（其中實際上儲存了資料卜且接著 記錄此等位址轉譯。記憶體系統之資料儲存容量至少與可 • 在對於記憶體系統所界定之整個邏輯位址空間上定址的資 、料之量一樣大。 ' 在較後代之快閃記憶體系統中，將擦除單位的大小增大 • i足夠記憶體單元之區塊以儲存多個資料區段。即使與記 憶體系統連接之主機系統可以諸如區段之小的最小單位程 式化且讀取資料，亦將大量的區段儲存於快閃記憶體之單 個擦除單位中。當主機更新或替換資料之邏輯區段時，一 區塊内之資料的一些區段通常變得過時。因為必須在可覆 寫區塊中所儲存之任何資料之前擦除整個區塊，所以通常 將新資料或經更新資料儲存於已經擦除且具有用於資料之 • 乘]餘容量的另一區塊中匕過程使得原始區塊具有過時資 料，其佔據記憶體内之寶貴空間。但是若存在剩餘在該區 塊中之任何有效資料，則不能擦除該區塊。 r 因此，為了更好地利用記憶體之儲存容量，通常藉由將 冑效部分區塊量的資料複製至一已擦除區塊中來合併或收 集該等資料，以使得接著可擦除自其複製此等資料之區塊 且可重新使用其整個儲存容量。亦需要複製資料以便以一 區塊内之資料區段之邏輯位址的次序來群聚該等資料區 段，因為此增大了讀取資料並將經讀取資料轉移至主機的 127921.doc 200844740 速度。若此資料複製發生得太頻繁，則可降級記憶體系統 之操作效能。特定言之，此在記憶體之儲存容量稍大於可 經由系統之邏輯位址空間而藉由主機來定址的資料量（典 型情況）之情況下影響記憶體系統的操作。在此情況下， 在可執行主機程式化命令之前可要求資料合併或收集。接 '著增大程式化時間。 ‘ 在逐代之記憶體系統中，區塊之大小不斷增大以便增大 可儲存於給定半導體區域中之資料之位元的數目。儲存 • 256個資料區段或256個資料區段以上之區塊變得普通。另 外’不同陣列或子陣列之兩個、四個或四個以上區塊經常 邏輯上一起連結成元區塊以增大資料程式化及讀取時之並 行私度。與此等大容量操作單位一起到來的係有效地操作 此等大容量操作單位的挑戰。 【發明内容】 上文交叉引用之專利申請案描述將由一主機提供之資料 Φ 檔案物件直接儲存於快閃記憶體中之記憶體系統。此與大 多數當前商用系統不同，其中在該主機與該記憶體系統之 間的介面處存在一連續邏輯位址空間，如上文在先前技術 .中所描述。利用此"LBA介面"，個別資料檔案物件之資料 冑普遍地存在於大量記憶體單元區塊中。該記憶體系統未 將由該主機提供之該等檔案物件之資料（通常各自為多個 資料區段之叢集）與個別資料檔案物件相關聯。相反，該 主機僅對供應至該記憶體系統以進行儲存之資料指派當前 未對有效身料指派之在該LBA介面内之未用邏輯位址。該 12792I.doc 200844740 記憶體系統接著指派其各個記憶體單 體系統有效地操作但不瞭解該等叢华所屬=用使該記憶 案物件的方式儲存經接收資料。— = = ;等資料檔 權案物件之資料分段為在許多不同記=可為，將個別 之片段。 个丨』礼體早Μ塊中儲存

上文父又引用之專利申請案中之許多者中，另一 面，該記憶體“不經由LBA介面而自該主機直接接㈣ 2料檔案物件’使得該記憶體系統可以改良該記憶體系 效能之方式將個別播案之資料分配給其記憶體單元區 塊。舉例而言’因為該資料所屬於之該檔案未知，所以該 記憶體系統可限制儲存任一資料檔案之記憶體單元區塊的 數目。特定言之，該記憶體系統可約束儲存一檔案物件之 貧料的亦含有另一檔案物件之資料之記憶體單元區塊的數 目。因此，可控制檔案資料之分段。此最小化必須在一共 同區塊之外重定位以回收過時資料空間之有效檔案資料的 量’該過時資料空間在刪除或修改一儲存於該區塊中之第 二檔案的資料時已產生。此導致在該快閃記憶體系統之使 用壽命的顯著改良之效能及耐久性。 此改良之效能及耐久性亦可在將直接資料檔案管理系統 實施於該主機而並非該記憶體系統的情況下實現。一 lb A 介面仍可存在於該主機與該記憶體系統之間。但並非將叢 集中之檔案資料分配給此單個相連邏輯位址空間，而係將 檔案資料分配給對應於在該記憶體系統内之實體區塊的在 此空間内之邏輯位址的區塊。在主機内關於在該主機/記 127921.doc 200844740 體系統μ面之該邏輯位址空間内之相連位址的邏輯區塊 而替代進订在該快閃記憶體系統内關於實體記憶體單元區 塊貝加之在上文交叉引用之專利申請案中描述的該等檔案 資料管理技術。該記憶體系統可接著為一如當前商業上普 及之習知者，其具有一 LBA介面。在該主機内之該直接資 播案管理系統之操作可限制含有來自—個以上檔案之資 、料之邏輯區塊的數目，正如在該記憶體㈣中操作之該直 《資料檔案系統限制含有來自一個以上檔案之資料之實體 記憶體單元區塊的數目。在實體記憶體單元區塊中之個別 檔案物件之資料的分段類似地降低，但係藉由管理映射至 實體記憶體單元區塊中之該邏輯位址空間的區塊而實現。 因此，在該LBA介面處之邏輯區塊較佳映射至該記憶體 系統之具有相同資料儲存容量及其他相似性的實體區塊 中。特定言之，若該直接資料標案系統在該記憶體系統内 操作，則由该主機將該等邏輯區塊組態成似乎其直接資料 φ 4當案系統與該等實體區塊將表現之相同。該等實體記憶體 區塊之特徵（不通常供應至該主機之資訊）可由該記憶體系 統在其初始化時提供至該主機。該主機接著將該連續邏輯 • 位址空間組態成具有對應於該實體記憶體之彼等特徵之特 ‘徵的區塊中，且隨後將資料寫入至彼等邏輯區塊内之地 址0 作為-替代，該直接資料檔案系統可以與上文描述相同 之方式在具有越過記憶體系統之— LBA介面之連續位址空 間而界定之邏輯區塊的記憶體系统令操作，而並非在一主 127921.doc 200844740 機中實施。即使為該記憶體系統之部分，此直接資料槽案 操作仍不同於在上文交又引用之專利中請案中描述:實 例。並非在該記憶體系統之後端處以允許替換該lba介面 之該記憶體系統接收在播案中之資料的方式來操作（在以 上申請案中描述之實例），該直接資料標案系統可被添加 • 纟在：LBA介面之前的該記憶體系統且以似乎在其LBA介 、 的主機中之上文描述的相同方式操作。此記憶體系 、统可甚至經組態以提供該LBA介面及該檔案物件介面兩 者，該記憶體系統經由該檔案物件介面可與一主機通俨， 該主機具有該LBA介面或該檔案物件介面但並非該兩種類 型之介面。此特別便於在與許多類型之主機裝置可移除地 連接之記憶卡中使用。 作為另替代，一具有處理能力之可移除母卡可具備上 文描述之該直接資料檔案系統，以便將直接播案能:添加 至一不具有該直接檔案能力但具有一直接資料標案介面之 φ #與該主機連接時，該母卡接著操作以提供一在該 卡之一輸出處之LBA介面，一具有一 lba 卡可能可移除地與該卡連接。 仏羊°己匕、 . 本發明之額外態樣'優點及特徵包括於其例示性實例之 卩下描述中’該等例示性實例之描述應結合隨附圖式而理 解。 本文中所引用之所有專利、專利申請案、論文、書籍、 况明書、其他公開案、文件及事物兹出於所有目的皆全文 以此引用之方式併入本文中。在所併入公開案、文件或事 127921.doc 200844740 ㈣本文之間的術語之定義或使用中有任何不_ 致或衝大之情況下，以在本文件中之術語的定義或使用 準。 【實施方式】 决閃記憶艘系統之一般描述 务看圖1至圖6描述-種典型快閃記憶體系統。在該系統 中可H施本發明之多種態樣。圖1之主機系統丨將資料儲 存至&閃„己憶體2中且自快閃記憶體2擁取資料。儘管可在 主機内耿入快閃記憶體，但仍將記憶體2說明為經由機械 ^電連接器之配合零件3及4可移除地連接至主機之卡的更 曰及形式。當前存在許多不同之市售快閃記憶卡，實例為 緊山决(CF)、多媒體卡（MMC)、安全數位（sd)、迷你 仍、記憶棒、智慧媒體及。儘管此等卡中之 每:者根據其標準化規格而具有唯一機械及/或電介面， 仁7者中所包括之快閃記憶體系統為非常類似的。此等 • 卡皆可自本申請案之受讓人“Disk公司獲得。SanDisk亦 在其商標下提供一系列隨身碟，該等隨身碟為在小 封裝卞之手持式記憶體系統，其具有一用於藉由插入主機 - USB插座中而與主機連接的通料列匯流排⑽㈣ 頭。此等記憶卡及隨身碟中之每—者包括與主機介接且控 制該等記憶卡及隨身碟内之快閃記憶體之操作的控制器。 使用此等記憶卡及隨身碟之主機系統為許多且各種各樣 的。該等主機系統包括個人電腦(pc)、膝上型及其他攜帶 型“、蜂巢式電話、個人數位助理（pDA)、數位靜態相 I27921.doc •12· 200844740 機、數位電影相機及攜帶型音訊播放… 内建式插座，其用於一或多種類型之 、通常包括- 是-些要求將記憶卡插入其中之配接器）。〜或1^身碟（但 可將圖1之主機系統1視為具有 巧呵11¾主要部分 憶體2之範圍内），其由電路與軟 "及屺 八也^ 1 、、且口構成。該兩個部 厂:广 5及一與記憶體2介接之驅動程式部分 人在個人電腦中，例如，應用程式部分巧包括一用於執 仃子處理、圖形、控制或其他普

久應用软體之處理器。在 相機、蜂巢式電話或主要專用於執 也/ 丁早組之功能的其他 主機糸統中’應用程式部分$句枯姐从 1刀包括知作相機以獲得並儲存 圖像、操作蜂巢式電話以產生並接 軟體。 接收呼”及其類似操作的 圖1之記憶體系統2包括快閃記憶體7及電路8，該電路8 與卡所連接至之主機介接以來回傳遞資料，且控制記憶體 7。在貝料程式化及讀取期間，控制器8通常在由主機^吏 用之資料的邏輯位址與記憶體7之實體位址之間轉換。 參看圖2，描述可用作圖i之非揮發性記憶體2之典型快 閃記憶體系統的電路。系統控制器通常實施於單個積體電 路晶片11上，該積體電路晶片u在系統匯流排13上與一或 多個積體電路記憶體晶片並行連接，在圖2中展示單個此 記憶體晶片15。所說明之特定匯流排13包括獨立的一組用 於載運資料之導體17、——組用於記憶體位址之導體i 9及一 組用於控制及狀態信號之導體2丨。或者，單一組之導體可 在此三個功能之間為時間共用的。另外，可採用系統匯流 127921.doc -13- 200844740 排之其他組態，諸如，在2004年8月9曰申請之標題為 f,Ring Bus Structure and Itfs Use in Flash Memory Systems» 的美國專利申請案序號第10/915,039號（公開案第2〇〇6/ 0031593 A1號）中所描述之環狀匯流排。 典型控制器晶片11具有其自身内部匯流排23，該匯流排 23經由介面電路25與系統匯流排13介接。通常連接至匯流 排之主要功能為處理器27(諸如，微處理器或微控制器）、 含有用於初始化（”開機，，）系統之程式碼的唯讀記憶體 (ROM)29及主要用於緩衝在記憶體與主機之間轉移之資料 的隨機存取記憶體（RAM)3丨。對經過在記憶體與主機之間 的控制裔之貧料計算且檢查一誤差校正碼（ECC)之電路％ 亦可連接至匯流排23。亦可包括專用於編碼及解碼經過控 制器之資料的電路34。此編碼包括壓縮及安全性加密，但 幾乎任何類型之資料變換可以此方式執行。專用電路33及 34在被利用時執行原本可由在韌體控制下之處理器27執行 的特定演算法。控制器匯流排23經由電路35與主機系統介 接，^在記憶卡中含有圖2之系統的情況下係經由為連接 器4之部分的卡之外部接觸”而完成。時脈”與控制器“ 之其他組件中之每-者連接且由控制器11之其他組件中之 每一者利用。 憶體晶片15以及與系統匯流排13連接之任何其他晶片 通吊，3有4體單^之陣列，該陣列經組織為多個子陣列 或平面& 了簡單起見說明瞭兩個此等平面41及43，但可 替代地使用更多（諸如，四個或八個）此等平面。或者，可 127921.doc -14- 200844740 不將晶片15之記憶體單元陣列劃分為平面。然而，當如此 为時，每一平面具有其自身之行控制電路45及47，該等 行控制電路可彼此獨立地操作。電路45及47自系統匯流排 13之位址部分19接收其各別記憶體單元陣列的位址，且將 該專位址解碼以定址各別位元線及5 i中之特定一或多 者。回應於在位址匯流排19上接收之位址而經由列控制電 路55來定址字線53。源電壓控制電路57及59亦與各別平面 連接’ P型井電壓控制電路61及63同樣與各別平面連接。 右3己fe體晶片15具有記憶體單元之單個陣列，且若在系統 中存在兩個或兩個以上此等晶片，則可與在上述多平面晶 片内之平面或子陣列類似地操作每一晶片之陣列。 經由與系統匯流排13之資料部分17連接之各別資料輸入 /輸出電路65及67，將資料轉移至平面41及43内且將資料 轉移至平面41及43之外。經由藉由各別行控制電路45及47 連接至平面之線69及71，電路65及67將程式化資料提供至 記憶體單元中且自其各別平面之記憶體單元讀取資料。 儘管控制器11控制記憶體晶片15之操作以程式化資料、 讀取資料、擦除且注意各種内務處理事件，但每一記憶體 晶片亦含有一些控制電路，其執行來自控制器丨丨之命令以 執行此等功能。介面電路73連接至系統匯流排之控制及 狀態部分21。將來自控制器之命令提供至狀態機75，接著 該狀態機75提供對其他電路之特定控制以執行此等命令。 如圖2中所示，控制線77至8 1連接狀態機75與此等其他電 路。在線83上將來自狀態機75之狀態資訊傳遞至介面73， 127921.doc -15- 200844740 以在匯流排部分21上傳輸至控制器11。 儘管亦可替代地使用諸如”反或"(NOR)之其他架構，但 記憶體單元陣列41及43之，1反及"(NAND)架構當前較佳。 藉由參考美國專利第5,570,315號、第5,774,397號、第 6,046,935 號、第 6,373,746 號、第 6,456,528 號、第 6,522,580號、第6,771，536號及第6,781，877號及美國專利 申請公開案第2003/0147278號，可獲知作為記憶體系統之 部分的NAND快閃記憶體及其操作的實例。 由圖3之電路圖說明NAND陣列之一實例，其為圖2之記 憶體系統之記憶體單元陣列41的一部分。提供大量全局位 元線，在圖2中為解釋簡單起見展示僅四條此等線91至 94。若干串聯連接之記憶體單元串97至1〇4連接於此等位 兀線中之一者與參考電位之間。使用記憶體單元串99作為 代表’複數個電荷儲存記憶體單元107至110在串之任一末 端處與選擇電晶體111及112串聯連接。當使一串之選擇電 晶體導電時，該串連接於其位元線與參考電位之間。接著 同時程式化或讀取該串内之一個記憶體單元。 圖3之字線115至11 8個別地延伸越過若干記憶體單元之 串中之每一者中的一個記憶體單元之電荷儲存元件，且閘 極119及120控制串之每一末端處之選擇電晶體的狀態。使 得共用共同字線及控制閘極線115至12〇之記憶體單元串形 成一起擦除之記憶體單元之區塊123。單元之此區塊含有 最小數目之單元’該等單元可同時實體上擦除。每次程式 化一列記憶體單元，彼等沿字線115至118中之一者的記伊 127921.doc •16· 200844740 體單元。通堂，ϊν ,〇 ^ 喂卷’以一規定次序程式化N AND陣列之列，在 匕狀况下’以沿最接近於串之連接至接地或另一共同電位 4 x 八 子線118的列開始。接著在區塊123中沿字線117 矛王式化記怜_留 U體早70之列，如此等等。最後程式化沿字線 11 5之列。 第二區塊125為類似的，其記憶體單元之串與第一區塊 123 之串連接至相同全局位元線，但具有一不同組之字

線及控制閘極線。由列控制電路55將字線及控制極線驅 動至其適當操作電壓。若在系統中存在一個以上之平面或 車歹〗（諸如，圖2之平面丨及2),則一個記憶體架構使用在 其間延伸之共同字線。或者可存在共用共同字線之兩個以 ^平面或子陣列。在其他記憶體架構中，獨立地驅動個別 平面或子陣列之字線。 上文所參考之NAND專利及已公開之申請案中之若干 者中所描述’可操作記憶體系統以將電荷之兩個以上可偵 測位準儲存於每一電荷儲存元件或區域中，藉此以將資料 ，一個以上位元儲存於每—者中。如美國專利第6,925，_ 號中所描述’ δ£(憶體單元之電荷儲存元件最通常為導電浮 閘，但或者可為非導電介電質電荷捕獲材料。 圖4概念地說明快閃記憶體單元陣列7(圖”之組織，其 在下文之進—步描述中用作—實例。記憶體單元之四個平 面或子陣列13 1至134可處於單個積體記憶體單元晶片上、 兩個晶片上（平面中之兩者處於每一晶片上）或四個獨立晶 片上。特定配置對於下文之論述並不重要。當然，系統甲 _.d〇c ·ΐ7 200844740 可存在其他數目之平面（諸如小2、8、16或16個以上）。 將平面個別地劃分為在圖4中以矩形展示的記憶體單元之 區塊（諸如，區塊137、138、139及140)，該等區塊位於各 別平面131至134内。在每—平面中，可存在數打或數百個 區塊。如上述，記憶體單元之區塊為擦除之單位，其為可 -起實體上擦除的最小數目之記憶體單元。然而，為了增 大之並列性，以較大元區塊單位操作區塊。將來自每一平 面之-個區塊邏輯上連結在—起以形成—^區塊。將四個 區塊137至140展示成形成一個元區塊141。通常一起擦除 在一元區塊内之單元中之所有者。無需將用於形成-元區 塊之區塊約束在其各別平面中之相同相關位置，如在由區 塊145至148構成之第二元區塊143中所展示。儘管通常較 佳越過平面中之所有者延伸元區塊，但為了高系統效能， 可利用動態地形成在不同平面中之―個、兩個或三個區塊 中之任纟或所有者之元區塊的能力來操作記憶體系統。 此允許it區塊之大小更接近地與可用於在—程式化操作中 儲存之資料量匹配。 出於操作目的，接著將個別區塊劃分為記憶體單元之 頁，如圖5中所說明。將區塊131至134中之每一者之記憶 體單元（例如）各劃分為八個頁抑至”。或者，每一區塊内 可存在記憶體單元之16個、32個或32個以上頁。頁為一區 塊内之貝料程式化及讀取的單位，其含有同時經程式化資 料的^小量。纟圖3之顧漏架構中，一頁係由沿—區塊内 子線的。己f思體單元形成。然而’為了增大記憶體系統 127921.doc -18 - 200844740 操作並列性，可將兩個或兩個以上區塊内之此等頁邏輯上 連結為元頁。在圖5中說明—元頁151，其係由來自四個區 塊131至U4中之每一者之一個實體頁形成。元頁i5i(例如) 包括在四個區塊中之每一者中之頁p2，但元頁之頁無需必 須具有在區塊中之每一者内的相同相對位置。儘管較佳越 過所有四個平面來程式化且讀取最大量之:㈣，但為了高 系統效能，亦可操作記憶體系統以形成在不同平面之獨2 區塊中之-個、兩個或三個頁中之任一者或所有者之元 頁。此允許程式化及讀取操作與可便利地並列處理之資料 的量適應性地匹配，且減小元頁之部分保持未用資料程式 化的機會。 一由多個平面之實體頁形成之元頁（如圖5中所說明）含 有沿該等多個平面之字線列的記憶體單元。並非同時程式 1 匕一字線列中之所有單元，更通常將其在兩個或兩個以1 乂錯群組中交替地程式化，每一群組儲存資料之頁（在單 個區塊中）或貝料之疋頁（越過多個區塊卜藉由同時交替地 程式化記憶體單元，包括資料暫存器及感應放大器之周邊 電路之單位無需為每一位元線提供，而是在鄰近位元線之 間時間共用。此節約周邊電路所需要之基板空間的量且允 許用沿列增大之密度來封裝記憶體單元。其他方面，較佳 问時程式化沿-列之每_單元以最大化可自一給定記憶體 系統獲得之並列性。 _!看圖3/將資料同時程式化至沿-列之所有其他記憶 體早7L中係糟由沿NAND串之至少—末端提供兩列選擇電 127921.doc -19- 200844740 曰曰 一體(未圖不）而非所展示之單列來最便利地實現。接著， 一 之選擇電晶體回應於_控制信號而將區塊内 他串連接至其各別位元線， 有八 ^ ^ 踝且另一列之選擇電晶體回應於 另一控制信號而將插 ^、 之所有其他串連接至其各別位元 中。’將資料之兩個頁寫入至記憶體單元之每一列 :每：邏：頁中之資料量通常為資料之整數的一或多個 ^又&照f貝例’每一區段含有資料之512個位元組。圖6 展不頁或元頁之資料之兩個區段153及155的邏輯資料頁。 母Η又通常含有經儲存之使用者或系統資料的川個位 凡、且之口Ρ刀157，及用於與部分157中之資料或與實體頁 或其中儲存實體頁之區塊有關之附加項資料的另一數目之 位元組15 9。附加項杳相_ + μ - / θ 項貝枓之位兀組量通常為16個位元组， 從而使區段153及155中之每一者共有528個位元組。附加 項。Ρ刀159可含有在程式化期間自資料部分m計算出之 ECC、其邏輯位址、區塊經擦除及再程式化之次數的經歷 :數、-或多個控制旗標、操作電璧位準及/或相似内 容，加上自此附加項資料159計算出之Ecc。或者，附加 項資料159或其之-部分可儲存於其他區塊中之不同頁 中〇 隨著記憶體之並列性增大’元區塊之資料儲存容量增 大’且資料頁及元頁之大小亦因此增大。接著，資料頁可 含有資料之兩個以上區段。在一資料頁中有兩個區段且每 元頁有兩個資料頁的情況下H頁中存在四個區段。 127921.doc -20- 200844740 因此，每—元頁儲存資料之2048個位元組。此為高程度之 並列性’且可隨著列中之記憶體單元之數目的增大而甚至 進-步增大4於此原因’快閃記憶體之寬度正經延伸以 便增大一頁及一元頁中之資料量。 上文所識狀實體上較小之可再程式化非揮發性記憶卡 及隨身碟為市售的，其具有512百萬位元組(mb)、i十億位 元組（GB)、2 GB及4 GB之資料儲存容量，且可變得更 高。 用於處理檔案物件之技術 具有邏輯區塊（LBA)記憶體/主機介面之操作 在圖7A、圖8A及圖9A中之每一者中以不同形式說明在 主機與δ己憶體系統之間的共同邏輯介面。由主機對主機產 生之資料檔案分配一連續系統位址空間（L Β Α介面）中之邏 輯位址（通常以資料之多區段之叢集為單位卜接著，記憶 體系統看見此等邏輯位址並將其映射至實際地儲存資料之 記憶體單元之區塊的實體位址。 特別參看圖9 A，連續邏輯位址空間丨6丨之大小足以為可 儲存於記龍线巾之所#資料提供㈣。通Μ主機位 址空間劃分為資料之叢集的增量。在一給定主機系統中， 每-叢集可經設計以含有資料之若干區段，大約在植64 個區段之間為典型的…標準區段含有512個位元組之使 用者資料，加上視需要之若干位元組的附加項資料（通常 16個位元組），共528個位元組。 圖9Α說明在主機與（諸如）在記憶卡或隨身碟上得到之大 127921.doc -21 · 200844740 里己L體系、為之間的最常見介面。主機處理由主機所 之應用軟體或_式所產生或使用的資料槽

?案，:·意謂由主機針對一些應用或目的而認物 疋貝，的貝料群組。將_檔案物件之資料作為—單位而管 理子處理檔案之資料為一實例，且電腦辅助設計（CAD) 軟體之製圖檔案的資料為另一實例，其主要在諸如％、膝 上聖電月自及其類似物之一般電腦主機中得到。以州格式 ^文件的資料亦為此檔案。播案物件之資料可在執行應用 、肩門由主機產生，或在別處產生且接著被提供至主 機靜怨數位視訊相機產生用於儲存於記憶卡上之每一圖 像的貝料核案。蜂巢式電話利用來自内部記憶卡上之檔案 (諸如’電話號碼薄）的資料。屬儲存且使用若干不同播 案（諸如，地址檔案、行事曆檔案及其類似物）。在任何此 應用中，§己憶卡亦可含有操作主機之軟體。 在圖9A之實例中，將三個檔案1、2及3展示成已產生。 在主機系統上執行之應用程式將每一檔案產生為一有序組 之貝料且由唯一名稱或其他參考來識別該有序組之資料。 由主機對檔案1指派尚未分配給其他檔案之足夠可用的邏 輯位址空間。將檔案1展示成已被指派一相連區間之可用 邏輯仇址。亦為了特定目的共同地分配位址之區間（諸 用於主機操作軟體之特定區間），接著即使在主機對 貪料指派邏輯位址時尚未利用此等位址，該等區間亦避免 用於儲存資料。 當由主機稍後產生檔案2時，主機類似地指派在邏輯位 12792l.doc -22· 200844740 址空間161内之兩個不同區間的相連位址，如圖7中所示。 一檔案無需被指派相連邏輯位址，但可被指派在已分配給 其他檔案之位址區間之間的位址的分段。接著，此實例展 示對由主機產生之又一檔案3分配主機位址空間之其他部 分’該等其他部分先前並未分配給檔案1與2或其他資料。 主機藉由維持檔案分配表（FAT)來記錄記憶體邏輯位址 空間，在該檔案分配表中維持主機對各種主機檔案指派之 邏輯位址。FAT表通常儲存於非揮發性記憶體以及主機記 憶體中’且在儲存新檔案、刪除其他檔案、修改權案及其 類似操作時由主機頻繁地更新。舉例而言，當删除主機槽 案時，主機接著藉由更新FAT表來對先前分配給已刪除檔 案之邏輯位址解除分配以展示該等邏輯位址現在可用於配 合其他資料檔案使用。 主機並不關心記憶體系統控制器選擇來儲存檔案之實體 位置。典型主機僅瞭解其邏輯位址空間及已分配給其各種 檔案之邏輯位址。另一方面，記憶體系統經由典型LBa主 機/卡介面而僅瞭解邏輯位址空間之已寫入資料的部分但 不瞭解分配給特定主機檔案之邏輯位址，乃至主機檔案之 數目。記憶體系統控制器將由主機所提供用於資料之儲存 或擷取的邏輯位址轉換為儲存主機資料之快閃記憶體單元 車歹】内的唯一實體位址。區塊163表示此等邏輯至實體位 址轉換之工作表，其係由記憶體系統控制器來維持。 处記憶體系統控制器經程式化以將資料檔案以將系統之效 此維持於高位準之方式儲存於記憶體陣列165之區塊及元 127921.doc -23 - 200844740 區塊中。在此說明中使用四個平面或子陣列。越過由來自 平面中之每-者之區塊形成之整個元區塊，用系統允許之 取大程度的並列性較佳地程式化且讀取資料。通常將至少 -元區塊167分配為-保留區塊，其用於儲存操㈣體及 由圮憶體控制器所使用之資料。可分配另一元區塊⑽或 多個元區塊以用於儲存主機操作軟體、主機㈣表及其類 似物。大多數實體儲存空間保持用於儲存資料檔案。然 而’記憶體控制器不瞭解經接收資料如何已由主機分配於 其各種檔案物件中。記憶體控制器通常自與主機交互所瞭 解的所有知識係：由主機寫人至·特定邏輯位址之資料係儲 存於對應實體位址中’該實體位址係由控制器之邏輯至實 體位址表16 3來維持。 在典型記憶體系統中，提供儲存容量之少量額外區塊， 其少於儲存在位址空間161内之資料量所必須的量。可將 此等額外區塊巾之m作為賤區塊而提供，其用於 取代可能會在記憶體之壽命内變得有缺陷之其他區塊。通 常可為了各種原因改變個別元區塊内所含有之區塊的邏輯 刀組，原因包括用冗餘區塊取代對元區塊原始指派之有缺 陷區塊。通常將一或多個額外區塊（諸如，元區塊171)維持 於已擦除區塊集區中。當主機將資料寫入至記憶體系統 時，控制器將由主機所指派的邏輯位址轉換為在已擦除區 塊集區中之元區塊内的實體位址。接著擦除未用於儲存邏 輯位址空間161内之資料之其他元區塊並將該等元區塊指 疋為已擦除集區區塊以便在隨後之資料寫入操作期間使 127921.doc -24- 200844740 用0

當原始儲存之資料變得過時時，由新資料來頻繁地覆寫 :;特疋主機邏輯位址處之資料。作出回應，記憶體系 :制器將新:貝料寫人已擦除區塊中並接著改變用於彼等 ，輯位址之邏輯至實體位址表以識別彼等邏輯位址處之資 料所儲存至的新實體區塊。接著擦除含有在彼等邏輯位址 處之原始貝料的區塊並使該等區塊可用於儲存新資料。若 在寫入開始時’在來自擦除區塊集區之預擦除區塊中不存 在足夠的儲存容量，則此擦除經常必須在可完成當前資料 寫入操作之刖發生。此可不利地影響系統資料程式化速 度。記憶體控制器通常瞭解，僅當主機將新資料寫入至其 相同邏輯位址時 料過時。因此， 料0 ，才藉由主機而使一給定邏輯位址處之資 圮憶體之許多區塊可暫時儲存此無效資 在商用記憶體系統中利用之區塊及元區塊的大小不斷增 大，以便有效使用積體電路記憶體晶片之面積。此導致大 部分個別資料寫人儲存少於區塊之儲存容量（且在許 多狀況下甚至少於一區塊之儲存容量）的資料量。因為記 憶體系統控制器通常將新資料引導至已擦除集區元區塊， 此可導致70區塊之部分變得未填充。若新資料為儲存於另 -元區塊中之-些資料的更新，則亦以邏輯位址次序將來 自具有與新資料元頁之邏輯位址相連之邏輯位址之另一元 區塊的資料之剩餘有效元頁合意地複製至新元區塊中。舊 元區塊可保持其他有效資料元頁。此隨著時間的過去而導 127921.doc -25- 200844740 致使個別元區塊之特定元頁之資料過時且無效，且該資料 由寫入至不同元區塊之具有相同邏輯位址的新資料替換。 為在整個邏輯位址空間161上維持用於儲存資料之足夠 實體記憶體空間，週期性地將該資料壓縮或合併（垃圾收 集）以便回收添加至已擦除區塊之集區的區塊。亦需要將 資料之區段以與實際一般多之其邏輯位址相同的次序而維 持於元區塊内’因為此使得在相連邏輯位址中讀取資料更 有效。因此通常以此額外目的執行資料壓縮及垃圾收集。 美國專利第6,763,424號中描述了在接收部分區塊資料更新 且使用元區塊時管理一記憶體的一些態樣。 ^料壓縮通常涉及自元區塊讀取所有有效資料元頁並將 〇專有效資料元頁寫入至新區塊，在該過程中忽略具有無 效資料之元頁。亦較佳以匹配元頁中儲存之資料之邏輯位 址次序的實體位址次序來配置具有有效資料之元頁。在新 元區塊中所佔據之元頁的數目將少於在舊元區塊中所佔據 7元頁的數目’因為未將含有無效資料之元頁複製至新元 區鬼接著將舊區塊擦除且將其添加至已擦除區塊集區以 :用於儲存新資料。藉由合併所獲得之容量的額外元頁接 著可用以儲存其他資料。 、在垃圾收集期間，自兩個或兩個以上元區塊聚集具有相 連或接近相連邏輯位址之有效f料的元頁，並將該等元頁 重新寫a人至另-元區塊中（通常為已擦除區塊集區中之一 者）一田自原始的兩個或兩個以上元區塊複製所有有效資 料70頁時’可將該等有效資料元頁擦除以便將來使用。資 127921.doc •26· 200844740 料合併及垃圾收集之發生率隨著在不同區塊中儲存檔案之 分段的增大而增大。 資料合併及垃圾收集花費時間且可影響記憶體系統之效 能’特定而言，在資料合併或垃圾收集需要在可執行來自 主機之命令之前進行時。此等操作通常由記憶體系統控制 器排程以儘可能在背景中進行，但執行此等操作之需要可 導致控制器對主機提供忙狀態信號，直至完成此操作為 止。可延遲主機命令之執行的一實例為··在已擦除區塊集 區中不存在用於儲存主機想要寫入至記憶體中之所有資料 的足夠預擦除元區塊，且首先需要資料合併或垃圾收集以 清空有效資料（其可接著經擦除）之一或多個元區塊。因 此，注意力已關注於管理記憶體之控制以最小化此等中 斷。在以下美國專利申請案中描述了許多此等技術··在 2003年12月30曰申請之標題為"1^11纹§611^111:〇尸1^〇11-Volatile Memory Systems Having Large Erase Blocks"之序 號第l〇/749,83 1號（現為公開案第2005/0144358 A1號）；在 2003 年 12 月 30 曰申請之標題為"Non-Volatile Memory and Method with Block Management System"之序號第 10/750,155號（現為專利第7,139,864號）；在2004年8月13曰 申請之標題為 ”Non_Volatile Memory and Method with Memory Planes Alignment”之序號第 10/917,888號（現為公 開案第2005/0141313 A1號）；在2004年8月13日申請之標題 為 ’’Non-volatile Memory and Method with Non-Sequential Update Block Management” 之序號第 10/917,867號（現為公 127921.doc -27- 200844740 開案第2005/0141312 A1號）；在2004年8月13日申請之標題 為 ’’Non-Volatile Memory and Method with Phased Program Failure Handling"之序號第10/917,889號（現為公開案第 2005/0166087 A1號）；在2004年8月13日申請之標題為 "Non-Volatile Memory and Method with Control Data Management"之序號第10/917,725號（現為公開案第 2005/0144365 A1號）；在2004年12月16日申請之標題為 "Scratch Pad Block”之序號第11/016,285號（現為公開案第 2006/0161722 A1號）；在2005年7月27日申請之標題為 "Non-Volatile Memory and Method with Multi-Stream Update Tracking"之序號第11/192,220號（現為公開案第 2006/0155921 A1號）；在2005年7月27日申請之標題為 ’’Non-Volatile Memory and Method with Improved Indexing for Scratch Pad and Update Blocks"之序號第 11/192,386號 (現為公開案第2006/0155922 A1號）；及在2005年7月27曰 申請之標題為"Non-Volatile Memory and Method with Multi-Stream Up datingni 序號第 11/191，686 號（現為公開案 第 2006/0155920 A1號）。 有效控制具有非常多擦除區塊之記憶體陣列之操作的一 挑戰在於使在給定寫入操作期間儲存之資料區段的數目與 記憶體之區塊的容量及邊界匹配且對準。一種方法為將所 使用元區塊組態成利用少於最大數目之區塊來儲存來自主 機之新資料，視需要儲存少於填滿整個元區塊之量的一定 量資料。在2003年12月30曰申請之標題為"Adaptive 127921.doc • 28 - 200844740

Metablocks"之美國專利申請案序號第10/749,189號（現為公 開案第2005/0144357 A1號）中描述適應性元區塊之使用。 在2004年5月7曰申請之標題為"Data Boundary Management"之專利申請案序號第10/841,118號（現為公開 案第2005/0144363 A1)及在2004年12月16日申請之標題為 • "Data Run Programming”之序號第 11/016,271 號（現為公開 案第2005/0144367 A1)中描述在資料區塊之間的邊界與在 元區塊之間的實體邊界之配合。 # 記憶體控制器亦可使用來自FAT表（其由主機儲存於非揮 發性記憶體中）之資料，以便更有效地操作記憶體系統。 一種此使用在於瞭解資料何時藉由解除其邏輯位址分配而 由主機識別為過時。知道此允許記憶體控制器在通常由將 新資料寫入至彼等邏輯位址之主機瞭解含有此無效資料之 區塊之前排程含有此無效資料之區塊的擦除。此係在2004 年7月21日申請之標題為"Method and Apparatus for Maintaining Data in Non-Volatile Memory Systems”之美國 ® 專利申請案序號第10/897,049號中描述。其他技術包括監 控將新資料寫入至記憶體之主機模式以推斷給定寫入操作 ^ 為單個檔案還是邊界位於檔案之間的多個檔案。在2004年 12 月 23 曰申請之標題為 ’’FAT Analysis for Optimized Sequential Cluster Management” 之美國專利申請案第 ll/022,369號描述此類型之技術的使用。 為有效地操作記憶體系統，需要控制器盡其最大努力地 瞭解關於由主機對其個別檔案之資料指派的邏輯位址。資 127921.doc -29- 200844740 料檔案接著可由控制器儲存於單個元區塊或元區塊之群组 内，而並非在不瞭解檔案邊界時散布於大量元區塊中。結 果在於減小了資料合併及垃斑你隹 叹垃圾收集刼作之數目及複雜性。 結果，記憶體系統之效能改* 乂 犯改良。但在主機/記憶體介面包 括邏輯位址空間161(圖9A)睥，今忤鱗 、 J子δ己憶體控制器難以瞭解關 於主機資料檔案結構之許多内容，如上文所描述。 直接資料檔案操作

在圖7Β、_及_中展示之在主機與用於儲存大量 資料之記憶體系統之間的不同類型介面排除邏輯位址空間 之使用。而是主機藉由唯一檔案ID(或其他唯一參考）及檔 案内之資料之單位（諸如，位元組）的偏移位址來邏輯上定 址每一檔案。直接對記憶體系統控制器給出此等位址，該 呑己憶體糸統控制器接著保持關於其將每一主機檔案之資料 實體上儲存於何處之自身表。此係作為上文交叉引用之專 利申凊案之主要目標的操作。可利用如上文參看圖2至圖6 而描述之相同ό己憶體糸統來實施此檐案介面。在圖7B、圖 8Β及圖9Β之基於檔案之介面與圖7Α、圖8八及圖9Α之LBA 介面之間的主要區別為記憶體系統與主機系統通信且儲存 檔案資料之方式。 比較圖8Β之基於構案之介面與圖8Α之lbΑ介面，圖8A 之邏輯位址空間及主機維持之FAT表並未在圖8B*出現。 相反’精由槽案说碼及檐案内之貢料的偏移來將由主機所 產生之資料檔案識別至記憶體系統。記憶體系統接著直接 將檔案映射至記憶體單元陣列之實體區塊。 127921.doc •30- 200844740

當藉由直接資料檔案儲存技術將新資料檔案程式化至纪 憶體中時’將資料寫入記憶體單元之已擦除區塊中，以區 塊中之第-實體位置開始且按次序順序地進行以穿過區塊 之位置。α自主機接收之次序程式化資料，而不管標案内 之資料之偏料次彳。程式化繼續ϋ已將槽案之所有資 料寫入至記憶體中為止。若檔案中之資料量超出單個記憶 體區塊之容量，則接著當第一區塊變滿時，程式化在第二 已擦除區塊中繼續。以與第一記憶體區塊相同之方式、以 自第-位置開始之次序程式化第二記憶體區塊，直至儲存 了檔案之所有資料或第二區塊變滿為止。可用檔案之任何 剩餘資料程式化第三或額外區塊。用於儲存單個擋案之資 料的多個區塊或元區塊不需要實體上或邏輯上相連。為了 易於解釋’除非另有說明，否則希望本文中使用之術語 ”區塊’’指擦除之區塊單位或多區塊式，，元區塊"，此取決於 元區塊是否正用於一特定系統中。 參看圖9Β，將檔案i、檔案2及檔案3中之每一者之識別 及該等檔案中之資料的偏移直接傳遞至記憶體控制器。接 著由記憶體控制器功能173將邏輯位址資訊轉譯為記憶體 165之元區塊及元頁之實體位址。並未將檔案資料映射至 圖9 A之邏輯位址空間161。 快閃最優化檔案系統之原理 圖7C圖8C及圖9C以不同形式說明併入有圖7B、圖8B 及圖9B之直接為料檔案技術且具有包括在圖7a、圖及 圖9A中之類型的LBA介面的作業系統。圖7C之”快閃最優 127921.doc -31 - 200844740 化檔案系統，’以與圖7B之”直接檔案儲存後端系統，，實質上 相同之方式操作’除了將檔案之資料映射至在圖7C中之 LB A介面之連續位址空間内的邏輯區塊，而不是將檔案之 資料映射至在圖7B中之NAND快閃之實體記憶體單元區 塊。圖7C之LBA介面及’’LBA至實體後端系統”為與圖7a之 系統的共同之處。在圖7C之系統中，直接之檔案至區塊位 址分配在LBA介面之前發生，但藉由在lba介面之連續位 址空間内之邏輯區塊位址而不是NAND快閃記憶體之實體 區塊而工作。 在圖8C中，以一不同形式說明相同觀點。將由主機產生 之資料棺案分配給在儲存裝置之邏輯位址空間内的邏輯區 塊位址。邏輯位址空間之邏輯區塊接著由記憶體控制器以 習知方式映射至實體儲存媒體之區塊。在圖8C中說明此等 功能在主機與記憶體系統之間的兩個可能劃分。第一實施 例將檔案分配給在主機（在圖中識別為主機υ中之邏輯區塊 位址。接著，記憶體1為具有與主機之LBA介面連接之 LBA介面的習知記憶卡或其他裝置。或者，圖叱之主機2 將資料檔案識別及在檔案内之資料偏移與記憶體系統介 接。接著在記憶體2内執行將此等檔案分配給邏輯區塊位 址之直接資料檔案功能。 圖8C之記憶體2(最常見形式為記憶卡、隨身碟或其他較 小的攜帶型單元）可藉由提供與用於儲存裝置之邏輯位址 空間連接之外部連接而另外包括LBA介面。如另一替代， 可在包括微處理器之母卡中執行將檔案分配給邏輯=塊位 127921.doc -32- 200844740 址之功能。接著使母卡可移除地與主機2連接，且記憶體i 將可移除地與母卡連接。 在圖9C中，以一不同方式說明將檔案物件之資料映射至 邏輯位址空間之技術。功能173,接收個別檔案之資料，其 具有唯一檔案識別符之個別邏輯位址及在該檔案内之資料 的偏移位址。由功能173,將此等檔案位址轉換為連續邏輯 位址空間161之邏輯區塊内的位址。取決於由實體記憶體 利用之單位，將個別邏輯區塊之位址區間界定成具有記憶 體陣列165之區塊或元區塊之相同資料儲存容量。圖％之 功能173,實質上與圖9B之功能ι73相同，除了在圖9C中將 檔案映射至位址空間1 61内之邏輯區塊，而在圖9B中將檔 案直接映射至記憶體單元陣列i65。與圖9a中實質上相 同，接著在圖9C中由功能163將邏輯位址區塊轉譯為記憶 體陣列165。功能163可為習知快閃記憶體作業系統，諸 如’在别述美國專利第7,139,864號及先前列出之以下已公 開之專利申請案中所描述：2〇〇5/〇141313 A1、 2005/0141312 A1、2005/0166087 A1、2005/0144365 A1 及 2006/0161722 A1 〇 自圖9C應注意，位址空間ι61之個別邏輯區塊可含有來 自一個以上檔案之資料。又，可對個別檔案之資料指派在 一個以上邏輯區塊内之位址。舉例而言，對資料檔案2及3 中之每一者指派在兩個或兩個以上邏輯區塊内之位址。邏 輯區塊亦可含有兩個不同檔案之資料；圖9C之邏輯區塊2 為此之一實例。但較佳地，在可含有給定檔案之資料以及 127921.doc -33· 200844740 一些其他檔案之資料的邏輯區塊數目上有至少一極限。可 在不同環境下利用不同極限。在一特定實例中，以任一權 案可與另一檔案之資料共用不多於兩個邏輯區塊之方式將 槽案之資料分配給位址空間161之若干邏輯區塊。藉由約 束允許用檔案之資料僅部分填充之邏輯區塊數目，可在對 特疋枯案物件之資料指派邏輯區塊位址期間遵循此約束。 此約束使（例如）由於其他檔案之資料隨後變得過時而可

變得必要之資料重定位量保持為低。當此發生時，通常將 給疋檔案之有效資料自含有另一擋案之過時資料的區塊複 製至另一區塊中。藉由約束給定檔案與另一檔案之資料共 用之區塊數目，此等資料複製操作變得不頻繁。此改良記 憶體系統之效能。 參看圖ίο，以邏輯區塊及實體區塊說明檔案資料之分 配。出於說明目的而將實例實體記憶體單元區塊ΐ9ι劃分 為四個頁195至199,但實際系統之每個區塊通常含有更多 頁。每-頁儲存資料之多個區段。每次程式化資料之一 頁1常在區塊内以195至199之次序。若記憶體系統利用 兀區塊’則區塊191為元區塊且頁至州為元頁。 邏輯位址空間161之邏輯區塊193被映射至實體區塊⑻ 中。=輯區塊193以成具有與實體區塊191相同之資料 :存容量’且亦劃分為與實體區塊i9i數目相同之頁⑽至 之二=具有與實體頁195至199中之每-者相同 體纪情體：：…亦即’較佳使邏輯位址空間之粒度與實 頁或元頁之資料料容量相等。以與在實體區塊 127921.doc -34· 200844740 191中寫人資料之頁相同之順序對資料指派在邏輯區塊⑼ 内之邏輯頁。在邏輯區塊193之第一頁2〇1開始處寫入資料 使得在實體區塊191之第_頁195開始處開始寫入資料。 為維持此邏輯功能與實體功能之協調，進行檔案至邏輯 區塊轉譯之主機需要瞭解與該主機_起操作 體特徵。在使用元區塊之記憶體系統之一實例中，此等特 徵可由以下參數界定： 、 1·實體頁之大小，以實體頁所儲存之資料之區段的數目 計； 2·元頁之大小，以連結在一起以形成個別元頁之頁的數目 計； 3 ·每個元區塊之頁的數目；及 4.映射至實體元區塊之第一頁之最低邏輯位址。 利用此資訊，主機可組態其邏輯位址空間161之邏輯區 塊結構以用由圖10所說明之方式操作。若僅一種類型之記 憶體（諸如，嵌入主機之記憶體）待由特定主機使用，則僅 需維持主機之邏輯位址空間之一種組態。但更典型情況 為，具有不同實體特徵之攜帶型記憶體裝置與給定主機裝 置可移除地連接，實際上與許多不同主機裝置可移除地連 接。因此，在主機内提供使該主機之邏輯區塊組態適應於 =該主機連接之特定攜帶型記憶體裝置之實體區塊配置的 能力。為實現此，以資料可由主機讀取之方式在記憶體裝 置本身中儲存上文列出之記憶體參數的資料。記憶體系統 之控制器冑常改變任何特定邏輯區; 鬼將映射至之實體區 127921.doc •35· 200844740 塊’但主機並不瞭解此情況且此情況不影響主機對邏輯區 塊指派槽案資料之位址。 圖11說明記憶體裝置207，其在可由主機211經由内連匯 流排213存取之非揮發性儲存空間2〇9中含有此等參數資 料。存在可由主機讀取此等參數之許多方式。一實例為界 定一供應商特定命令，其係在初始化記憶體裝置2〇7期間 由主機211發給記憶體裝置。記憶體裝置2〇7接著操作以將 經儲存參數值返回至該主機。另一實例為，此等參數可包 括於記憶體裝置207回應於來自主機之現有標準命令而已 返回至主機211的現有欄位之未用部分中。此命令之一實 例為識別驅動（Identify Drive)命令。 例示性快閃最優化檔案系統 在此部分中提供將個別檔案映射至連續邏輯位址空間之 邏輯區塊之技術的實例實施的進一步細節。其之某些態樣 已參考實質上相同之以下功能而描述：圖7C之”快閃最優 化檔案系統”、圖8C之”將檔案分配給邏輯區塊位址"及圖 9C之槽案/偏移至邏輯位址轉換"I?]·。 在此部分中描述之用於將檔案映射至邏輯區塊位址之許 夕内谷利用在上文父叉引用之專利申請案中描述之將檔案 映射至實體記憶體單元區塊位址的相同技術。主要不同在 於，檔案映射係（諸如）由主機裝置越過LBA介面而進行， 而並非繞過L B A介面藉由直接將資料檔案映射至實體記憶 體區塊（如在先前交又引用之專利申請案中所描述）而進 吁可將先4申清案之實體記憶體區塊映射技術替代地應 127921.doc -36- 200844740 用於將資料檔案物件映射至LB A位址空間之邏輯區塊，本 文中描述其之一些實例。 在本文中對邏輯映射檔案物件之描述中，稱將資料”寫 入至”或’’程式化至”LBA介面之區塊。當然，與實體記憶體 區塊相反，此等邏輯區塊實際上並不儲存資料，所以此指 對特定邏輯區塊指定資料之位址。類似地，稱邏輯區塊在 未被分配給資料時為”已擦除”。”已擦除”邏輯區塊為不含 有倉料之位址的邏輯區塊，所以其完全可被指派資料之位 址。其他邏輯區塊可為”部分擦除”，此意謂該邏輯區塊之 一部分可用於接收資料之額外位址。 快閃最優化檔案系統之一般操作 田新資料檔案待程式化至記憶體中時，將資料寫入至以 在區塊中之第一位置開始之未佔據邏輯區塊中，且按次序 順序地進行以穿過區塊之位置。卩自主機接收之次序程式 化資料’而不管播案内之資料之偏移的次序。繼續程式化 :至已寫入檔案之所有資料為止。若檔案中之資料量超過 早，邏輯區塊之容量，則接著在第—區塊變滿時，程式化 在弟二空白(已擦除)區塊中繼續。以與第-邏輯區塊相同 式以自第叫立置開始之次序程式化第二邏輯區塊， 至分配了擋案之所有資料或第二區塊變滿為止。可用播 檔料程式化第三或額外區塊。用於儲存單: 备’、貝；。的多個邏輯區塊或元區塊無 解釋，怜韭易於 "區塊”二:::月， ”在錢體糸、统内擦除之實體區塊最小單位 127921.doc -37- 200844740 相同之容量的邏輯區塊或對應於通常一起擦除之多區塊式 實體元區塊的多區塊式邏輯，，元區塊”，此取決於元區塊是 否正用於一特定系統中。 圖12之表說明快閃最優化檔案系統之全面功能。個別邏 輯區塊可視為處於三種狀態中之一者中。此三種狀態為已 擦除區塊641、儲存有效檔案資料而無可回收容量之區塊 643及可含有一些有效檔案資料但亦具有來自未程式化（已 擦除）頁面及/或儲存於其中之過時（無效）資料之可回收容 里的區塊645。由功能647將資料寫入至已擦除邏輯區塊， 藉此導致寫入至在種類643或645中之區塊，此取決於所得 經程式化區塊是否保持任何可回收容量。當刪除檔案時， 如由功能649所指示，含有檔案之資料的區塊643轉換為具 有可回收容量之區塊645。在功能650中將資料自可回收區 塊複製至其他區塊之後，區塊645之未用儲存容量由功能 651回收，此導致使彼等區塊返回至可將新資料寫入至其 之已擦除區塊641的狀態。 參看圖13 A，其說明將資料檔案寫入至邏輯位址空間。 在此只例中，-貝料檔案丨8丨大於一個區塊或元區塊1之儲 存谷里，將該資料檔案i 8 i展示成在垂直實線之間延伸。 因此，亦將貧料檔案181之一部分184寫入至第二區塊US 中將此專邏輯區塊展示成具有相連位址但並非必需。將 來自檔案181之資料如同其為自主機接收之串流一樣寫入 直至已將檔案之所有資料寫入至邏輯位址空間為止。在圖 13A之實例中，資料181為檔案之初始資料。 127921.doc -38- 200844740

種用於《己隐體系統官理且記錄經儲存資料之較佳方法 為使用可變大小之資料群組。亦即，將檔案之資料储存為 複數個貧料群組，可將該等資料群組以-界定次序鏈接在 一起以形成完整檔案。當正寫入來自主機之資料流時，只 要在檔案資料之邏輯偏移位址中或在分配給資料之邏輯位 址工間中存在不連_性，即開始__新資料群組。此邏輯位 址空間不連續性之一實例為在檔案之資料填滿-個邏輯區 塊且開始寫入至另一區塊中時。此係在圖i3A中說明，其 中第-資料群組填滿第一區塊183，檔案之剩餘部分關乍 為第二資料群組儲存於第二區塊185中。第一資料群组可 由(F〇，D〇)來表示’丨中F〇為資料檔案開始處之邏輯偏 移，且D0為在邏輯區塊183内檔案開始處之位置。可將第 二資料群組表示為（F1,D1)，其中F1為儲存於第二區塊185 開始處之資料的檔案偏移’且〇1為第二區塊開始處之對應 邏輯位址。 經由主機記憶體介面而轉移之資料量可以資料之位元組 的數目、資料之區段的數目或用一些其他粒度來表達。當 經由當前邏輯位址介面與大容量記憶體系統進行通信時， 主機最經常用位元組粒度來界定其檔案之資料，但接著將 位元組分組為每一者512個位元組之區段或分組為每一者 多個區段之叢集。通常進行此動作以簡化記憶體系統之操 作。儘官本文中描述之基於檔案之主機記憶體介面可使用 賓料之些其他單位，但原始主機樓案位元組粒度通常較 佳。亦即’資料偏移、長度及其類似物較佳以位元組（資 127921.doc -39- 200844740 料之最小合理單位）而非藉由區段、叢集或其類似物來表 達。此允許用本文中描述之技術來更有效地使用快閃記情 體儲存器之容量。 “

接著將以在圖13A中說明之方式寫入至邏輯位址空間之 新檔案在檔案索引表（FIT)中表示為關於資料群組之以如下 次序的一連串索引項（F0，D0)、（F1，D1)。亦即，只要主機 系統想要存取特定檔案，則主機產生其檔案1〇或其他識 別，接著存取其FIT以識別構成該檔案之資料群組。為了 便於操作記憶體系、統，個別資料群組之長Mength>亦可 包括於其個別項中。 只要主機將圖13A之檔案維持於已打開狀態，則較佳地 亦維持寫入指標P以界定用於針對該檔案寫入自主機接收 之任何另外資料的邏輯位址。將用於檔案之任何新資料在 、輯區塊中之檔案的末端處寫入，而不管檔案内之新資料 的邏輯位置。記憶體系統允許多個檔案(諸如，…個此 等權案）同時保持打開，且針對該等檔案中之每一者維持 -寫入指標P。用於不同檔案之寫入指標指向不同邏輯區 =中之位置。若在關於打開權案之數目之系統限制已存在 ,機系統想要打開-新檔案，則首先關閉已打開檔案 中之一者且接著打開新檔案。 圖郎說明由主機將f料附加至圖13A之先前寫入但仍 =之標案的末端。將資料187展示成由主機系統添加至 耷之末鳊’亦在第二區塊185中在該檔案之資料的末端 _料187°«加資料成為資料群組孔叫之部 127921.(i〇( 200844740 分，因此該資料群組現含有更多資料，因為在現有資料群 組184與經附加資料189之間不存在檔案不連續性且不存在 邏輯位址不連續性。因此，仍將完整資料表示為在fit中 之—連串索引項（F0，D0)、（F1，D1)。亦將指標p之位址改變 為儲存經附加資料之末端的位址。 在圖13C中展示將資料191之區塊插入至圖13A之先前寫 入檔案中的一實例。儘管主機將資料191插入至檔案中， 但快閃最優化檔案系統在先前寫入檔案資料之末端處的位 置193處附加經插入資料。無需在將資料插入至打開檔案 中時以其邏輯次序重寫入檔案之資料，儘管此可稍後在主 機關閉檔案之後在背景中進行。由於將經插入資料完全儲 存在第二邏輯區塊185内，故其形成單個新群（F1，D3)。但 進行此插入導致將圖13A之前一資料群組（F〇，D〇)劃分為兩 個群組，一個在插入之前的群組（f〇,do)及一個在插入之 後的群組（F2，D1)。此因為，只要存在資料之檔案不連續 性（諸如’在插入之開始^處及在插入之末端^處出現之 不連續性）’則需要形成新資料群組。群組（F3，D2)係作為 第二區塊185開始之邏輯位址02的結果。即使群組（F1，D3) 及群組（F3，D2)儲存在同一邏輯區塊中，但仍將群組 (F1，D3)及群組（F3，D2)維持為獨立，因為在該等群組中儲 存之資料的檔案偏移存在不連續性。接著在FIT中由以如 下次序之資料群組索引項（F0，D0)、（F1，D3)、（F2，D1)、 (F3，D2)表示具有插入之原始檔案。自圖13A、圖13B及圖 13 C之實例應注意’可在並不使由邏輯區塊位址表示之任 127921.doc -41- 200844740 何資料變得過時的情況下宜 料。 以下寫入用於新或現有擋案之新資 作為在圖13C中說明之將咨 貝枓插入至現有檔案中的替 代，只要已插入資料，則可 旧管 重寫入。此獨立檔宰接=主機將檔案作為獨立檔案而 棕案接者可由記憶體系統作為新 理。接著由主機删除舊案而處 卜 』陈售祜案，且系統可藉由回收 舊檔案（其之資料現為過時、，二儲存 _說明另一實二時 =邏輯位址空間而回應。 、幻其中更新以在圖13Α中展示之士 式原始寫入之資料的特定 之方 展示成待更新。將=:斩將資料檔案之一部分- 之資料，η t 更新料197附加至先前寫入 資料 ？重寫入具有更新之整個檔案。先前寫入之 部分199現為過時。在更新之後，檔案在系統FIT 中係由以如下次序之資料群組索 (F2，D1)、（F3 〇2、矣+ 如 1 5〇3) Λ )(3，D2)表不。在圖nD中，再次將圖 ::群組⑽糊分為幾塊一個在經更新部分之:： 群組、經更新部分及—個在經更新部分之後的群組。= 之位址空間199,但此較佳稍後進行 存用於部分而進行。此回收通常導致儲 疋4田案之更少量之資料群组。 二進:序步:明::長度資料群組之使用’由叫 首先將原::宰：：檔案之―連串若干寫入操作。 ，、、4W寫入至連續位址空間之兩個邏輯 ;二一如圖14A中所示。接著由兩個資料群組界定檔 組在邏輯區塊之開始處開始，且在邏輯區塊邊 127921.doc -42- 200844740 界之後需要第二群組。圖14A之檔案接著由用於資料群組 之索引項的以下序列描述：（F0，D0)、（fi，D1)。 在圖14B中，主機使在圖14A中寫入之檔案資料更新。 緊接在前一群組（F1，D1)之後寫入經更新檔案資料ui，其 中經更新資料之前一版本變為過時。圖14 A之前一群組 (F0，D0)縮短為圖14B之經修改群組（F0，D0)，且前一群組 (F1，D1)縮短為群組（F4，D2)。因為經更新資料與邏輯區塊 之邊界重疊，因此在兩個群組（F2，D3)與（F3，D4)中寫入經 更新資料。在第三邏輯區塊中儲存一些資料。權案現由用 於資料群組之索引項的以下序列描述：（p〇，D〇)、 (F2，D3)、（F3，D4)、（F4，D2)。 在圖14C中’圖14B之檔案由使新檔案資料η之插入的主 機進一步修改。因為經插入資料與邏輯區塊之邊界重疊， 所以將新資料II作為圖14C之新群組（F5，D6)及（F6，D7)而寫 入至緊接在圖14B之前一群組（F4，D2)之後的邏輯區塊中。 使用弟四邏輯區塊。在圖14C中，因為新資料η之插入， 所以將圖14B之前一群組（F0，D0)分割為縮短群組（f〇，d〇)及 (F7，D5)。檔案現由用於資料群組之索引項的以下序列描 述：（F0，D0)、(F5，D6)、(F6，D7)、（F7，D5)、（F8，D3)、 (F9，D4)、（F10，D2)。 圖14D展示對圖14C之資料檔案的進一步修改：將新資 料W2附加至該檔案之末端。將新資料W2作為圖14D之新 群組（F11，D8)而緊接在圖14C之前一群組（fi〇，d2)之後寫 入。播案現由用於資料群組之索引項的以下序列描述： 127921.doc -43- 200844740 (F0，D0)、（F5，D6)、（F6，D7)、（F7，D5)、(F8，D3)、 (F9，D4)、（F10，D2)、（Fli，〇8)。 在圖14E中展示對打開檔案之第二更新，其中將經更新 檔案資料U2寫入至圖14D之檔案中。在圖14E中，經更新 資料U2緊接在圖14D之前一群組（F11，D8)之後寫入，其中 該資料之前一版本變為過時。圖14d之前一群組（F9，D4)縮 短為在圖14E中之經修改群組09，;〇4)，前一群組（Fl〇，D2) 變得完全過時，且前一群組（F11，D8)經縮短以形成新群組 (F14，D9)。在圖14E之新群組（Fi2，D10)及（F13，D11)中寫入 與邏輯區塊邊界重疊之經更新資料。現在，檔案需要第五 邏輯區塊。檔案現由用於資料群組之索引項的以下序列描 述··（F0，D0)、（F5，D6)、（F6，D7)、（F7，D5)、（F8，D3)、 (F9，D4)、（F12，D10)、（fi3，D11)、（F14 D9)。 在根據前文描述之檔案建立或修改之後’較佳以正確邏 輯-人序使每一檔案之資料的偏移維持連續。因此，舉例而 言，作為將資料插入至檔案中之操作的一部分，由主機提 供之、、:插人貝料的偏移與緊接在該插人之前的偏移連續， 且已在該插入之後的檔案中之資料增大經插入資料之量。 更新現有檔案最通常導致在現有檔案之給定位址區間内的 資料由相同量之經更新資料所替換，因此—般無需替換檔 案之其他資料之偏移。 :將如此儲存之資料之粒度或解析度維持為與主機之粒 ί或解析度相同。舉例而言’若主機應用用-位元組粒度 寫入播案資料’則在邏輯區塊中亦可用—位元組粒度來表 127921.doc -44 - 200844740 示檔案。接著在若+ 丄曰 之旦艿仞罢 4凡、、且中置測資料在個別資料群組内 αι 即，可在主機應用檔案内獨立地定址之資 料的相同偏移單# 貝 亦可在該檔案儲存於快閃記憶體中時在 δ亥檔案内獨立地定 ^ 之同… 接者’在FIT中將在-邏輯區塊内 -p、L、之貝料群組之間的任何邊界指定給最接近之位 :組或其他主機偏移單位。類似地，以主機偏移之單位界 疋在：邏輯區塊内之不同檔案之資料群組之間的邊界。

U#又在本文中結合大區塊記憶體使用，以表示盥 ECC相關聯之經儲存資料的單位。㈣，區段為在此❹ 权正碼由記憶體系統之控制器產生^用資料儲存時，傳遞 至快閃記憶體且自快閃記憶體傳遞之資料的最小單位。當 參考實體記憶體時，T用於表示在—區塊内之記憶體: 兀的早位。頁為程式化之最小單位。在邏輯區塊内之邏輯 頁’’為含有與實體頁相同之資料量的頁。術語"元頁”用於 表示具有一元區塊之完全並行性的頁。元頁為程式化之最 大單位。 自圖14B及圖14E應注意，經更新命令導致由檔案所占 之邏輯位址空間大於在檔案中之資料量。原因為留存用於 已由更新替換之資料的邏輯位址。因此，非常需要夢由、、宵 除過時之無效資料而將檔案之資料合併（垃圾收集）至較少 邏輯位址空間中。因此，更多邏輯位址空間變得可用於1 他資料。 亦可注意，除了圖14B及圖14E之檔案資料更新，圖uc 之資料插入亦導致檔案資料之位址失序。亦即，雖然幾乎 127921.doc -45· 200844740 始終在檔案内某處定位更新及插入，但更新及插入在其進 行時被添加至檔案之末端。此為圖14B、圖14c及圖之 實例的情況。因此，可能會需要越過邏輯位址空間對檔案 之資料重排序以匹配偏移在播案内之次序。因為順序地讀 取頁及區塊將給予以其偏移次序之檔案的資料，所以此接 • 著改良讀取經儲存資料之速度。此亦提供檔案之最大可能 • 之重組。但對檔案資料重排序以使讀取更有效對記憶體系 統之效能的重要性並不如檔案資料合併，檔案資料合併潛 籲在地釋放用於其他資料之位址的_或多個邏輯區塊。因 此，對檔案中之資料重排序一般並非由其自身進行（其中 優點不值添加之操作負擔），但可作為具有極少或不具有 添加之操作負擔之許多垃圾收集操作的一部分而進行。 因為已進行兩個資料更新U1及U2，所以圖14E之檔案包 括過時檔案群組（灰色部分）。結果，自圖14E顯而易見， 分配給檔案之邏輯位址空間量之實質上大於檔案之大小。 _ 因此，垃圾收集係合適的。圖15提供垃圾收集圖丨4e之資 料檔案之結果的說明。在垃圾收集之前，該檔案佔據位址 空間之接近五個邏輯區塊（圖14E)，而在垃圾收集之後， • 同一檔案在稍多於三個區塊（圖15)内。作為垃圾收集操作 • 之部分，將資料自其初始寫入至之邏輯區塊複製至其他已 擦除邏輯區塊中，且接著擦除原始區塊。若整個檔案經垃 圾收集，則可將其資料複製至新區塊中，該等新區塊具有 與在該檔案内之資料邏輯偏移次序相同之邏輯次序。舉例 而言，更新U1及U2以及插入II在垃圾收集之後（圖15)以與 127921.doc -46- 200844740 其在主機檔案中出現之相同次序儲存。 基於檔案之垃圾收集亦通常導致在合併之檔案内形成新 的且不同的資料群組。在圖15之情況τ，檔案係由用於新 資料群組之索引項的以下新序列描述：（f〇，di2)、 (F1’D13)、（F2，D14)、（F3，D15)。此比在圖 14E中展示之檔 案的情形下存在之資料群組的數目少得多。現在針對^ 中之每一者存在一個資料群組，已將檔案之資料複製至該 等區塊中。作為垃圾收集操作之部分，更新m以反映形 成檔案之新資料群組。 當在圖14E之狀態中時，回收固持檔案之資料的區塊係 對區塊個別地操作而並非對儲存同一檔案之資料的多個區 塊操作。舉例而言，若考慮在某給定時間對圖i4E之含有 位址空間之任何區塊之最少量有效資料的第二區塊〇〇2進 灯回收操作，則接著將其單個資料群組複製至另一已擦除 區塊。新區塊接著含有單個資料群組（F8，D16)，且該區塊 之剩餘部分為已擦除容量，可將新資料寫入至該已擦除容 量中。已自區塊（在圖14E中，資料儲存於該區塊中）回收 該已擦除容量。檔案接著由用於構成該檔案之資料群組之 索引項的以下序列描述：（F0，D0)、（F5，D6)、（F6，D7)、 (F7，D5)、（F8，D16)、（F9，D4)、（F12，D10)、（F13，D11)、 (F14，D9)。在圖14E中展示之其他區塊保持不變，直至其 個別地符合用於回收操作之標準為止。 檔案區塊管理 基於儲存於區塊中之檔案資料之結構來認識邏輯區塊之 127921.doc -47- 200844740 特定類型。接著注意具有在連續位址空間中之位址的每一 檔案處於若干狀態中之一者，每一檔案狀態係由儲存檔案 之賓料之區塊的數目及類型而界定。對一檔案而言，當有 資料待寫入時，該檔案當前狀態及自一狀態至另一狀態之 准許轉變較佳經控制以約束含有用於特定檔案之資料的區 塊數目’該特定權案亦含有一或多個其他槽案之資料。此 促進邏輯區塊之有效利用，且降低維持用於接受新資料或 經複製資料之足夠已擦除區塊所必需之稍後回收操作的頻 率〇 在此實例中認識之含有檔案資料之邏輯區塊的核心類型 如下： π檔案區塊”已完全程式化，且表示單個檔案之有效資 料。其亦可含有一些過時資料之位址。 π程式化區塊π已部分程式化，且表示僅單個擋案之有 效資料。一些已擦除容量仍留存在該區塊中。其亦可含 有一些過時資料之位址。 共同區塊”已部分程式化’且表示兩個或兩個以上播 案之有效資料。仍留存一些已擦除容量。其亦可含有一 些過時資料之位址。 ’’滿的共同區塊”已完全程式化，且表示兩個或兩個以 上構案之有效資料。其亦可表示一些過時資料。 另一類型之區塊為’’已擦除區塊"，其中在該區塊中不存 在負料位址’因此該區塊之全部谷量可用於接受資料。广1' LBA介面之邏輯位址空間變滿或幾乎充滿資料位址時，通 127921.doc -48- 200844740 常藉由連續地回收存在於正估用 队vpy、正汊用之邏輯區塊内之未用容量 來維持特定最小數目之已擦除區塊的集區。

'碎形區塊"為一集體術語’指程式化區塊、共同區塊或 滿的共同區塊。詩檔案之碎形區塊含有該檔案之有效資 料以及未經程式化之儲存容4、用力其他槽案之有效資 «該兩者。本文中描述之技術的主要目的為藉由管理經 指定以接收檔案之資料之仙區塊的類型來最小化在位址 空間中之碎形區塊的數目。此減少需要在邏輯位址空間中 執行垃圾收集及資料合併（區塊时操作）以維持特定最小 數目之已擦除邏輯區塊的情況。因為花費更少時間來内部 複製資料以回收在先前經程式化區塊中之未用容量的分 段，所以接著使可將資料寫入至記憶體中之速率增大。 亦在本文中使用額外術語以集中描述區塊之其他類型： ”部分區塊’’含有一 之有效資料之位址， 些未經程式化容量、一或多個檔案 且可表示一些過時資料。程式化區 塊及共同區塊為部分區塊之實例。 案區塊或 量，且表 ’’過時區塊”為含有一些過時資料之位址的檔 滿的共同區塊。過時區塊不具有任何已擦除容 示有效資料及無效資料兩者。 "無效區塊"不含有有效資料。無效區塊含有至少一些 過時資料之位址，且可含有已擦除容量但不表示任何有 效資料。 圖16A至圖16D說明使用上文定義之邏輯區塊之類型的 些實例。在圖16A中，檔案a之資料已填滿區塊661及 127921.doc -49- 200844740 663 ’且部分填充第三區塊665。在此實例之每一區塊中從 左至右地寫入資料，首先填充區塊661，接著填充區塊663 且隨後寫入至區塊665之一部分中。區塊665之剩餘部分為 可儲存額外資料之未經程式化之已擦除容量。藉由上文列 出之定義，區塊661及663為檔案區塊，且區塊665為程式 化區塊。在程式指標P處開始將任何新資料寫入至區塊665 中。指標P隨著將資料寫入至區塊而從左至右地移動，以

始終指向在區塊中之下一可用儲存位置。為保持未經程式 化之已擦除容量之個別區塊（無論當前是否為作用）保持該 指標，使得始終瞭解待寫入至區塊之任何其他資料的邏輯 位址。 圖⑽之實例包括為共同區塊之區塊669，㈣該區塊 699含有另一檔案b之資料以及當前檔案八之資料加上一些 未經程式化容量。在展示程式指標p處開始，在檔案A之末 端處將新資料寫入至區塊669中。區塊669為檔案A之作用 區塊。該區塊699亦可為用於檔❹之作用區塊，在此情況 下，可在程式指標P處寫入檔案A切案B之額外資料。或 者，一獨立區塊（未圖示）可為檔案]5之作用區塊。 可將檔案之資料直接寫入至已含有其他權案之資料之部 分區塊的已擦除容量中’而並非寫入至已擦除區塊中，以 便較佳此形式制未經程式化容量。此在待寫人小於一滿 =容量之已知量的權案資料時特別有用。搜尋現有部分 區塊以找到適合待寫入之已知資料量的適量已擦除容量。 貝料之頁（或在使用元區塊時之元 貝）的數目與在部分區塊 127921.doc -50- 200844740 中之未經程式化容量之頁的數目比較。當以此方式程式化 程式化區塊之未用已擦除空間，則該區塊轉換為共同區 塊。 在圖16C中’擋案A儲存於檔案區塊661、區塊671之一 部分及區塊673之一部分中。區塊671為滿的共同區塊，因 為該區塊671充滿兩個檔案A&B之資料。區塊673為類似 於圖16A之區塊665的程式化區塊。區塊673為檔案之作用 區塊，且指標P指向在區塊673内首先寫入額外資料處之未 用容量的位置。 在圖16D之實例中，將檔案A寫入至滿的共同區塊671之 一部分及共同區塊675中。區塊675含有第三檔案c之資 料。指標P指向作用區塊675之寫入額外資料處之未用部分 的第一位置。 儘管圖16A至圖16D之實例展示儲存於多個區塊中之檔 案A的資料以說明區塊之若干不同類型，但在許多情況 下，檔案可足夠小以儲存於更少數目之區塊（甚至單個區 塊）中。本文中描述之技術亦可應用於此等小檔案。又， 較大檔案可佔據三個以上區塊中之頁。 應注意，邏輯區塊665、669、671、673及675為碎形區 塊。需要最小化由任一檔案之資料佔據之碎形區塊的數 目，因為其存在增大需要回收在該等碎形區塊中之未用容 量之可能性且因此不利地影響系統效能。未用已擦除容量 存在於部分邏輯區塊665、669、673及675中，但除非已知 擋案之未寫入資料量且該已知量匹配此等區塊中之一者的 127921.doc -51 - 200844740 未用容量’否則將新資料自主機 有效率。最常見地，未知特定資來:b空間内並沒 因此不易於填充容量之此等位元。因:自主機的資料量， 作期間將資料自另一區塊移動1^需要在回收操 禾用二間内，以古由田 記憶體容量。區塊669、671及 乂有效使用 久〇 /：>含有一個 欠 料，其意謂，當刪除該等檔案中之一 备八貝 塊中之資料變得過時，則可能進行資料^儲存於共同區 資料之位址佔據之區塊容量。 r U回收由過時 因此，為降低資料回收操作花費之 索$ m t . 、 等間1，允許特定檔 案：貝科在任-時間健存於僅一個、兩個或某個 之碎形區塊中。在判定准許之碎形區塊數目時，權衡能夠 ^用^等碎形區塊之優點與具有料碎形區塊之不良影 曰。在本文中描述之特定實例中 1 彳田案之資料可儲在 於兩個或少於兩個碎形區塊中 — U 1一个夕於兩個。因此，指 疋新作用區塊以儲存於査夕咨粗 减仔犏案之貝枓的處理受約束。對每一檔 案指派一組准許檔幸妝能Φ ^ ^ ^ 田茶狀悲中之一者，其係由儲存檔案之資 料之區塊類型所界定。當需要指派將新作用區塊以接收特 定檔案之資料時，諸如當一現有區塊變為滿時，如此指定 之區塊類型取決於檔案之狀態，且在許多情況下亦取決於 其他因素。 、 吹在圖17之表中給出在一特定實施中根據含有用於構案之 資料之碎形區塊的組合之七個准許檔案狀態⑽至2〇的定 義。准許檔案狀態中之每一者允許在不超過兩個碎形區塊 中儲存檔案。對可儲存檔案之資料之檔案區塊的數目不存 127921.doc -52· 200844740 在約束。檔案之狀態為用於控制對將用作檔案之作用區塊 之區塊的選擇的特性。已選擇為回收區塊之區塊並不視為 碎形區塊’目為存在於該回收區塊中之用檔案的任何資料 並不有助於判定檔案之狀態，此係由於回收區塊為暫時 的在FIT中l控且記錄存在於裝置中之每一權案的狀態 以及播案資料索引資訊。只要發生任何狀態轉變，則更新 針對檔案記錄之狀態。 取決於檔案狀態轉變與程式化資料、與變過時之資料還 是與選定之回收區塊相關聯，將檔案狀態轉變再劃分為三 類。在圖18之狀態圖中說明由於掛起或完成之資料程式: 操作的檔案狀態中之准許轉變。由具有識別來自圖Η中之 表之數字的檔案狀態之圓來指示七個檔案狀態。 在圖1 8之狀態轉變上的標籤具有以下含義： A-將已擦除區塊作為檔案之作用區塊而分配； 已填充部分區塊； C-將部分區塊作為檔案之作用區塊而分配； D -將此檔案之部分區塊作為另一檔案之作用區塊而 配； E-對作為作用區塊而分配之已擦除區塊進行資料轉變；及 F-對作為作用區塊而分配之部分區塊進行資料轉變。 多數狀態轉變在分配一區塊或一區塊變為滿時自動發 生。然而，一些界定狀態轉變亦併入有特定資料自一個： 塊至另-區境之再定位。資料作為單個不間斷操作而再定 位’且狀態轉變視為僅在完成資料再定位之後發生。此等 127921.doc -53- 200844740 轉變被指定為"資料轉變"。參看圖18之狀態圖，圖19之表 提供准許狀態轉變之細節。 & 當待寫入之資料的長度已知時，可將部分區塊作為作用 區塊而分配。在此情況下，自裝置中之全體部分區塊選擇 "最適合"部分區塊。"最適合"定義為具有待寫入之已知量 資料可有效利用之適量已擦除容量的部分區塊。在—些： 況下，若不存在"最適合”部分區塊，則，•最大"部分區塊^ ?為替代而選擇。此為具有最高量之可用未用容量的部分 區塊。 圖2〇為說明由於資料變為過時之檔案狀態轉變的狀離 圖。特定檔案之此等狀態轉變在儲存於含有特㈣案之: 料之碎形區塊中的檔案之所有資料變為過時時發生 已變為過時之檔案無需為特定檔案。彳由四個事件中之任 一者使資料過時： 1 ·由主機删除一檔案； 2.由主機删除在檔案内之資料； 3·由主機更新先前對檔案寫入之資料；或 4·在回收操作期間重定位檔案之資料， 在圖20之狀態轉變上的標籤具有以下含義： G-在部分區塊中之此檔案的所有資料已變為過時； 在滿的、同區塊中之此檔案或所有其他 料已變為過時；及 ％茶之所有貝 I-在部分區塊中之所 ， 時。 /、他檔案之所有資料已變為過 127921.doc -54- 200844740 圖21之表提供由於在圖2 〇中說明之過時資料之權案狀態 轉變的細節。在此等環境中之任一者下使資料為過時導致 疋位有過時資料之區塊的類型改變，從而導致檔案之狀態 的所得改變。 當將一區塊選擇為回收區塊時，不再將該區塊視為檔案 之碎形區塊（槽案之資料存在於該區塊中）。此導致由圖22 之狀態圖說明之檔案狀態轉變。在圖22之狀態轉變上的標 織具有以下含義： 將部分區塊選擇為回收區塊；及 Κ-將滿的共同區塊選擇為回收區塊。 在圖23之表中給出由於回收區塊之選擇的檔案狀態轉變 的細節。 存在兩個替代機制以用於將檔案之資料與連續邏輯位址 空間之邏輯區塊對準。在實體記憶體單元區塊上操作之直 接資料檔案系統的情況下，如在上文交又引用之專利申請 案中所描述’新檔案之開始較佳對準已擦除記憶體單元區 塊之開始。此亦可在直接資料檔案系統以邏輯區塊操作時 進行，如圖24中所說明。說明儲存於邏輯區塊1至7中之三 個‘案A Β及C。當寫入此等檔案中之一者的所有資料 時，自圖24應注意，檔案之最後部分佔據部分區塊之_；部 分。 圖25之表提供用於判定作為作用區塊而分配以儲存檔案 之資料之邏輯區塊類型的標準。如所指示，此取決於檔案 之現有狀態（由圖17之表所定義）及待程式化之資料的主導 127921.doc -55- 200844740 狀况。即使當在此基礎上選擇/分配情況中乂一者時，必須 取决於可用性而自一可能性之有限集合進一步選擇區塊之 類型’如圖25之右手行所指示。舉例而言，對分配情況b

°邛刀區塊優先用於接收已知長度之資料。首先搜尋 二有洽足夠可用（已擦除）容量以儲存此已知量資料之部分 區塊。但若不存在該部分區塊，則判定是否存在具有最大 ^經程式化空間之部分區塊。否則，作為第三優先級，接 著扣定70全未分配（已擦除）區塊以接收資料，此將導致一 邛刀區塊，因為在此實例分配情況B中待寫入之資料的已 知量小於將填滿一滿區塊之量。 可刪除與在首次寫入一檔案（諸如，在圖Μ中之檔案A、 中之一者）時之狀態保持相同之該播案，而隨之無需 重疋位任何不相關檔案之資料。但若回收操作已合併檔案 之部分區塊之資料與另一檔案之資料，則可按需要來刪除 檔案以自僅一個區塊重定位另一檔案之資料。舉例而言， 右來自區塊2之檔案的資料A已與在區塊7中之檔案c的資 料口併，則接著，可隨後按需要來刪除擋案A或檔案◦以 自僅一個區塊7重定位資料。 區塊回收為與寫入檔案資料之處理交錯的處理，其中自 正、、二歷回收之區塊重定位有效資料，以便允許待擦除之區 塊（其所有容量指定為未分配）回收在該區塊中之未用容 置。可出於兩種原因中之一者選擇回收之區塊·· 1·區塊含有由於已刪除或更新檔案之過時資料；或 2·區塊為部分區塊，且含有未經程式化容量。 127921.doc -56- 200844740 分配：回收處理之時間比例較佳不變’使得可維持寫入新 檔案資料之速度不變。此難以達成，因為檔案寫入處理產 生必須由回收處理來處理之不可預測數目的部分區塊。 在圖24中展示之檔案至區塊之映射機制的優點在於，其 允許含有最新近寫入之檔案資料的部分區塊保持儘可能 長，直至該等部分區塊被選擇為用於回收操作之源區塊或 目的區塊為止。此增大關於檔案能夠在重定位其資料中之 任何資料或在共同區塊中之不相關檔案的資料之前被刪除 的木兄率jtb係因為該樯案之資料包含在專用於該標案之區 塊中。因為無需回收操作、無需複製資料之時間，且因此 記憶體系統更有效地操作。 圖24之映射機制的—缺點在於，通常對每—寫人之構案 產生-個部分區塊，且一般需要合併許多部分區塊之資料 以便回收其可用未經程式化（已擦除）容量。另彳，若記憶 體控制器以自動合併來自部分寫人區塊之資料以回收新的 已擦除區塊容量之方式管理實體記憶體，則可由圖Μ之映 射機制產生大量消耗時間之資料複製。因&，可能會需要 實施® 26之映射機制㈣代機制。此機制之主要特徵在於 新播案開始處之資料鄰接先前佔據部分區塊之不相關擋案 的貝料。當已寫入檔案之所有資料時，最後寫入資料最通 常佔據部分區塊之-部分，但僅為暫時地。在該部分區塊 中之未經程式化空間立即填充有經寫人以鄰接完成㈣之 新檔案的資料。 在圖7之表巾、、Ό出圖26之機制之針對為寫人資料分配作 127921.doc -57- 200844740 用區塊的實施。在圖25之表中的分配情況a在圖27之表中 由界定用於新檔案及現有檔案之獨立情況的分配情況Μ及 A2替代。 在圖26中，用於檔案之開始及檔案之末端之資料通常與 不相關樯案共用一區塊，且在刪除一標案時必須自兩個區 塊重定位資料。舉例而言，若删除檔案B，則自區塊2重定 位檔案A之資料，且自區塊3重定位檔案c之資料。此接著 使區塊2及區塊3能夠被擦除且添加至已擦除（未分配）區塊 的集區，可將其他資料稍後寫入至該等區塊中。 圖26之檔案至區塊映射機制之一優點在於，其消除經部 分程式化區塊之累積。因為在部分區塊中待寫入之新播案 的貢料開始鄰接不相目現有檀案之資料，戶斤以 寫入之權案資料的部分區塊無法保持長時間週期，且因此 置中存在非常少之部分區塊。此限制關於必須在回收 J間二併來自部分區塊之資料的機會，且允許建立不 持口收速率以使用於新檔案資料之不變寫入速度得以維 時：26之映射機制的—缺點在於’其增大關於在刪 除槽案時萬要重定位不相關檔案之資 於必須對每一機合 千幻曰大關 於在刪除檀案時增大資里。在圖26之機制中之關 24之播… 枓重定位的此缺點否定了超越圖 1之^於降低細收操作期間來 之合併的發㈣的優點。 < 塊之貝科 回收區塊容量 127921.doc -58- 200844740 =上文所描述，區塊f理之部分包括回收在區塊中之未 用谷里以儲存新資料。此在儲存於記憶體系統中之資料量 遂小於。己k體系統容量時並不特別重要，但較佳將記憶體 系充0又°十為仿佛其充滿資料般地操作。其意謂，可以回收 此未用谷里之方式處理僅含有過時資料之區塊及含有有效 貧=但亦具有_些過時f料及/或未寫人頁之其他區塊。 ^標為儘可能完全地利用記憶體系統之儲存容量，而同時 隶小化對系統之效能的不利影響。 ·』將在扣定用於回收操作之區塊(源區塊)中之有效資料複 製至具有用以儲存該有效資料之充分未分配(已擦除)容量 的或夕個區塊（目的區塊）中。根據上文描述之區塊管理 技術來‘擇目的區塊。將儲存於源區塊中之每一檔案的資 料禝製至基於檔案之狀態及其他因素(如上文所描述)而選 擇的區塊類型。在圖28A至圖勘中給出作為回收操作之 部分的在不同類型檔案之間複製資料的實例。 在圖28A中，作為實例說明對兩個部分區塊681及683之 回收操作。區塊681為程式化區塊，其中儲存檔案A之有效 資料’同時亦含有並未儲存資料之已擦除容量。取決於播 案A之狀態的—個可能回收操作為，將區塊之權案a的 資料複製至已包括不同檔案B之資料的另一部分區塊_的 可用已擦除容量中’因此使該部分區塊奶成為共同區 塊。接著在FIT中不再引用在區塊⑻中之資料群組，且將 該區塊記錄為過時。當儲存於區塊681中時，檔案A具有包 括程式化區塊之狀態(參看圖17)中之—者。可接著將資二 127921.doc •59- 200844740 移動至另-碎形區塊，而使檔㈣持寫人至最多兩個碎形 區塊中。在複製至區塊685之後，取決於儲存檔案之其他 資料之區塊類型’冑案A已轉變為包括儲存於共同區塊中 之檔案之資料的狀態（參看圖17)中之一者。 圖28A之區塊683為共同區塊，該區塊⑻係藉由將其播 案C及D之經儲存資料複製至含有播㈣之資料之程式化區 塊687的已擦除容量中而回收，該程式化區塊687接著變為 共同區塊。在區塊683中之檔案C&D之資料接著過時，如 該區塊自身。檔案(：及〇中之每一者的狀態並未改變，因 為資料已自一個共同區塊移動至另一共同區塊。然而，檔 案E之狀態已改變。或者，檔案C&D中之每一者之資料可 移動至彼此不同之區塊且無需必要地複製至共同區塊之可 用空間。檔案之狀態可接著可能地轉變至其他狀態。 在圖28B中說明對實例區塊689及691之回收操作。此等 區塊中之每一者為過時區塊，因為其充滿有效資料及過時 資料。區塊689為含有檔案ρ之資料的檔案區塊，該檔案ρ 之一部分為過時且剩餘部分為有效。舉例而言，此可在更 新播案F期間發生，其中將新資料寫入至在檔案末端處的 具有與檔案之現有資料相同之邏輯偏移的位址，且現有資 料接著變為過時。在此實例中，將構案F之資料複製至含 有檔案G之資料的程式化區塊693之已擦除容量中，從而導 致區塊693之類型改變為共同區塊。或者，可將檔案ρ之有 效資料寫入至已擦除區塊，此接著導致該區塊為程式化區 塊0 127921.doc 200844740 圖28B之區塊691為含有檔案H之無效資料及檔案τ之有效 資料的滿的共同區塊。在此實例中，將檔案j之有效資料 自區塊691複製至已擦除區塊695中。區塊的5接著變為程 式化區塊。或者，若可得到良好適合性，則可將檔案1 = 資料寫入至含有另一檔案之資料的部分區塊。目的區塊將 取決於檔案I在回收操作時之狀態。 由於在圖28Α及圖28Β中展示之回收操作之四個特定實 例中之每一者，儲存於兩個部分區塊中之資料組合為一 個，籍此使該兩個區塊中之另—者僅具有過時資料。該等 區塊接著為無效區塊。原始區塊681、683、689及691中^每 一者之整個空間接著藉由擦除區塊而回收，如圖28c中所 說明。已擦除區塊為回收無效區塊之結果。 圖28D展示儲存檔案j之資料之檔案區塊的7的實例。當 檔案J由主機刪除時，使在區塊697中且可能亦在其他區^ 中之檔案J的資料為過時。區塊697接著變為無效。回收無 效區塊為系統已擦除區塊集區提供已擦除區塊。 自記憶體刪除權案亦通常導致在一丨多個碎形區塊（諸 如，共同區塊或滿的共同區塊）中之檔案的資料變為過 時。因為另-檔案之剩餘有效資料小於區塊之儲存容量且 可為y i，所以該區塊接著經受回收操作。 由圖29之流程圖概括展示回收操_。取決於特定實施 例’為部分、過時及無效區塊維持一或多個清單，如由步 驟701所指示。根據一技術，在啟動記憶體系統時（諸如， 當貫先施加電源時）建立區塊之此清單。此清單可包括使 127921.doc -61 - 200844740

每次選擇一個回收區塊之區塊的其他資訊，諸如，在每一 區塊中之有效資料量及在每一區塊中之已擦除空間量。此 等量通常根據區塊之頁的數目或在使用元區塊時之元頁的 數^而I㈣。一較佳替代技術為在非揮發十生記憶體中維持 此等表’且只要-區塊狀態改變便在清單中添加或更新該 區塊之項。利用此技術，當初始化記憶體系統時，無需掃 描區塊及建立清單。作為將所#料、料及無效區塊保 持於清單上之替代，僅包括彼等具有低於—些設定臨限量 的少量有效資料之區塊，因為選擇回收區塊之一特徵在 於’該區塊具有極少或不具有需要複製之有效資料。在許 多回收操作中必須將資料自一個區塊複製至另一區塊，此 花費顯著量之時間’因此一般對彼等具有較 量之區塊執行此操作。 < 此等區塊之清單隨著寫人、更新、移動、刪除等而不斷 改變。導致區塊類型改變為部分、過時且無效且導致區塊 類型自部分、過時及無效改變的改變導致由圖29之步驟 701所維持之清單有所改變。有效資料量之改變個別地儲 存於此等區塊中’ i已擦除容量之量的改變亦記錄於區塊 清單中。 有效資料的源。下文描述可 。。在步驟703中’較佳自彼等在經更新清單上之區塊識別 早個回收區塊作為下—個以便進行回收。在部分或過時區 塊之情況下，其為待複製至稱為目的區塊之另—區塊中之 術 用於選擇源區塊之若干特定技 127921.doc -62- 200844740 考慮到需要回應主機之命令而執行之記憶體操作，圖29 之下一步驟705接著判定在當前時間執行回收操作是否合 適。若主機已發布閒置命令或指示將存在主機不會期望記 憶體系統執行特定操作之某個時間週期的類似命令，接著 系統可在前景中自由地進行負擔操作，其包括回收操作。 即使主機忙於將資料寫人至記憶體系統或自記憶體系統讀 取資料，回收操作（特定言之，其資料複製）仍可與資料寫 入及讀取操作交錯進行。在2005年10月25日申請之Alan 以⑽1^之美國專利申請案序號第11/259,423號及2005年12 月19日中請之Alan Bennett等人之序號第11/312,985號中描 述應用至實體記憶體單元區塊之此交錯。 若由圖29之步驟7G5狀可進行回收操作，則該處理取 決於經識別回收區塊是否含有有效資料，且若含有則是否 含有-個以上檔案之有效資料而不同。在部分區塊或過時 區塊之〖月況下’按定義該區塊含有有效資料，且在共同區 塊或滿的共同區jt免$ +軎π τ ^ , h况下該區塊含有兩個或兩個以上 標案之有效資料。由步驟7()7判定在回收區塊中是否存在 有效資料。若存在必須移動之有效資料，則在下一步驟 709中識別單個檔案之資料且識別目的區塊以接收該資 枓。目的區塊藉由上文參看圖17至圖19而描述之處理來識 別’以便維持檔案（有效資料屬於該檔案）之所有資料館存 於兩個或兩個u π #心p，，， __ 下碎形區塊中（在此實例中）。接著開始將 -個檔案之有效資料自源回收區塊複製至目的區塊，如步 驟711所指示。在複製此等資料之後，處理返回至步驟707 I27921.doc -63- 200844740 以判疋另一檔案之資料是否剩餘。若剩餘，則對額外資料 重複步驟709及711之處理。目的區塊係獨立於對不同檔案 之資料的較早選擇而選擇。此繼續，直至在步驟7〇7中判 定在源區塊中不再存在待移動之資料為止，在此情況下， 可按步驟713擦除源區塊。接著可將此區塊放於已擦除區 塊集區中以用於儲存新資料。 返回至圖29之步驟707，若源區塊不含有有效資料（為無 效區塊之情況），則不存在待移動之有效資料。僅需要擦 除源區塊。因此，在該情況下之處理繞過如圖29中展示之 步驟709及711。 在圖29之處理的第一實施例中，由步驟7〇 1維持部分、 過時及無效區塊之單個清單。在清單上之個別項中包括在 區塊中之有效資料量。在步驟703中，自清單選擇為回收 區塊之區塊為具有最少有效資料之區塊。若在清單上存在 一個無效區塊，則首先選擇該區塊，因為該區塊不具有有 效資料。若在清單上存在許多無效區塊，則選擇在此處時 間最長之區塊。若在清單上不存在無效區塊，則接著將具 有最少量有效資料之區塊選擇為回收區塊。藉由在清單上 選擇具有所有區塊之最少量有效資料的區塊，回收操作接 著花費比當存在待自一個區塊複製至另一區塊之更多有效 資料時更短之時間。結果，記憶體系統之其他操作（諸 如’將資料寫入至記憶體及自記憶體讀取資料之速度）得 以維持於高速率。以較少之記憶體效能成本獲得新的已換 除區塊。 127921.doc -64- 200844740 此用於基於在碎形區塊中之 、登探、區r仏 貝'科置而在單個清單上 、擇源£塊之圖29之處理的第 之佟Efc。妙二， 列具有實施相對簡單 之叙點然而，此處理可藉由亦考身 進。部分區塊具有可寫入資料夕 分區塊之值而改 已擦除容量，而過時區塊

π儲i二：不含有任何已擦除容量。在可將過時區塊用 於=新-貝料之财，將任何有效資料自該等過時區塊移出 且移動至另-區塊巾，使得料料區塊可接㈣捧除且 可歸儲存新資料。但部分區塊具有可寫人資料之已捧除 容董’而並非必須承受回收操作之負舉例而言，此可 能會無益於回收一部分區塊’僅因為在部分區塊亦含有可 寫入貢料之大量已擦除容量時含有最少量之有效資料。 因此，在圖29之處理之豆#眘> ，、他實_巾，基於存在於部分 區塊中之有效資料量及已擦除容量之量兩者而將部分區塊 選擇為用於回收源區塊之候選者。在圖3〇中展示在部分區 塊中之資料的成份。區塊（可為元區塊）具有含有有效資料 之特定數目之-或多個頁（可為元頁）及㈣除且可寫人資 料之-或多個其它頁。部分區塊亦可含有一或多個其它 頁，其含有過時資料，如圖30之實例中所示。 在圖29之處理之此等其他實施例中，較佳由步驟7〇1將 部分區塊維持於與過時及無效區塊之清單分離之清單中。 當部分區塊具有較少已擦除容量（其意謂該等部分區塊在 其當箾狀悲下並不非常有用）及需要移動之少量有效資料 時，使該等部分區塊朝其清單之頭部移動以用於回收操 作。此等區塊將主要含有過時資料。相反地，具有大量已 127921.doc -65- 200844740 擦除容量（其意謂該等部分區塊潛在地有用㈣存資料）及 待移動之大量有效資料之部分區塊最不可能被識別為用於 回收區塊之候選者。回收具有已擦除容量之部分區塊並不 如同回收-料區塊般將料容量之—些量添加至邏輯位 址m無效區塊明顯為針對回收之最具吸引力之區塊， 因為此等無效區塊並不具有有^之已擦除容量且並無需要 複製之有效資料。

在圖29之回收區塊識別步驟7〇3之第二實施例巾，由步 ㈣1維持三㈣立清單中部分區塊、過時區塊及無 效區塊中之每—者針對—個清單。若存在無效區塊，則自 無效區塊之清單選擇回收區塊直至該清單上不再存在區塊 =止。除了可能以先進先出（_)次序以使在清單上時間 =之無效區塊得以首先選擇，不存在列出無效區塊之特 序接I右不存在無效區塊，則自過時區塊清單選 擇具有在該清單上之所有區塊之最少量有效資料的區塊。 右在無效清單及過時清單中之任—者上均不存在區塊， =著在㈣703中將在部分區料單上之區塊選擇為回 :塊。儘管可將一部分區塊選擇為具有最少量有效資料 =區塊，但較佳以認識其已擦除容量之益處之方式來 回收增益,，，如下广目的，可對每-部分區塊計算" 回收增益=(S-kE)/V (” 的區塊大小，E 且V為含有需要 其中，S為根據區塊之資料儲存頁之總數目 為可寫入資料之已擦除容量之頁的數目， 127921.do, -66 - 200844740 移動至另一區塊之有效資料之頁的數目。包括常數k以權 衡區塊之已擦除容量之有利效應，但可將其設^。隨著 耻值增大’所得回收增益降低。隨著v之值升高，回收 乓&亦降低。纟步驟7〇3中將具有目收增益之I高值之部 分區塊選擇為时區塊°其他數學表達式可替代地用於定 義根據Ε及V之權衡對含有有效f料之系統操作的損失與 具有已擦除谷量之益處的回收增益。亦可在區塊中每次發 生改變（諸如，每次將資料寫入至其已擦除容量中）時計算 回收增益，且將該回收增益作為由檔案目錄或ριτ維持2 資訊的一部分而儲存。 :圖η中說明此第二實施例，其展示自獨立之部分區塊 清皁、過時區塊清單及無效區塊清單選擇（如由圖Μ之步 驟701所維持）選擇回收區塊（圖29之步驟7〇3)的方法。步驟 721首先判定是否存在於無效區塊清單上列出之區塊。若 存在多個此等區塊，則由步驟723將在清單上最長時間之 區塊選擇為回收區塊。若在無效區塊清單上不存在區塊， 則接著由步驟725判定在過時區塊清單上是否存在項。若 存在，則在一個以上區塊在過時區塊清單上之情況下，由 步驟727將具有最少量有效資料之區塊選擇為回收區塊。 若由步驟725判定在過時區塊清單上不存在項，則接著在 步驟729中查閱部分區塊清單。當在部分區塊清單上存在 一個以上區塊時’將具有最高回收增益者選擇為回收區 塊。回收增益諸如藉由使用上文方程式（1)來考慮在區塊中 之有效貧料I及已擦除谷5：。若在部分區塊清單上不存在 127921.doc •67- 200844740 内各，則藉由返回至步驟721來重複該處理，直至在清單 | k 之者上出現區塊為止。在選擇回收區塊之後，該處理 進行至圖29之步驟705。 由圖32之流私圖展示第三實施例。執行圖之步驟 亦開始於在由圖29之步驟701所維持之無效區塊清單上尋 找一項的步驟741。若在無效區塊清單上存在一個以上 項，則由圖32之步驟743將最舊者選擇為回收區塊。若在 無效區塊清單上不存在項，則下一步驟745判定在過時區 鬼π單上疋否存在項。若存在，隨後步驟與圖3丨之實施例 之不同之處在於，若在部分區塊清單上亦存在至少一項， 則將判定最佳係自過時區塊清單還是部分區塊清單選擇回 收區塊。 圖32之步驟747識別在過時區塊清單上之含有最少量有 效資料的區塊。接著由步驟749判定在部分區塊清單上是 否存在至少一區塊，且若存在，則在步驟751中識別具有 φ 冑少量有效資料之區塊。下-步驟753接著在自過時區塊 清單識別之一個區塊與在部分區塊清單上識別之一個區塊 之間進行選擇。為此目的’對在步驟751中自部分區塊清 * 單識別之區塊計算量（V+kE)，項V、Ε及k與上文之使用相 • @。將此量與在於步驟747中自料區塊清單識別之區塊 中之有效資料的IV進行比較。若關於部分區塊之量 (v+kE)大於過時區塊之v，m接著在步驟755中將該過時區 塊選擇為回收區塊。但若過時區塊之v大於經識別部分區 塊之量(V+kE)，則㈣在步驟757中將該部分區塊選擇為 127921.doc -68- 200844740 回收區塊。 藉由在與經識別過時區塊之僅有效fΜ比較 識別部分區塊之已擦除容量之量kE添加至其有效資料ν經 該處理傾向於贊同選擇過時區塊。保持具有與經識別過時 區塊相同之有效資料量的經識別部分 A仍了…曰在地用於在其已擦除容量中儲存資料。 上’將保持具有比過時區塊之有效f料量小—量k右: 資料量的部分區塊。 政

返回至圖32之步驟745，若在過時區塊清單上不存在 項’則接著在步驟759中判定是否存在於部分區塊清 列出之區塊。若不存在’則該處理返回至步驟川以重 複’直至在三個清單中之一者上放有一區塊為止。若存在 歹J出之夕個σρ分區塊’則接著在步驟76 i中’將具有最少 量有效資料之區塊選擇為回收區塊。或者，可藉由使用如 參考第二實施例（圖31)之步驟731而描述之回收增益來選擇 部分區塊。 ' 。或者’第三實施例可利用僅兩個清單。第—清單為過時 區塊α單，其含有用於含有過時資料且不含有已擦除容量 品鬼的項將無效區塊及過時區塊兩者放在單個"過時” 區塊清單上，而並非使用如圖32中展示之獨立無效區塊清 單區塊了視h況含有有效資料。在清單中之每一項具有 含有用於定義與該項有關之在該區塊中之有效資料量的 值的搁位。在清單中之項根據在此等欄位中之值而排序。 因此，含有過時資料且不含有有效資料之區塊（無效區塊） 127921.doc -69 - 200844740 在此第一清單之頭部處集合在一起。 在此對第三實施例之替代中之第二清單為部分區塊清 單，其含有用於含有一些已擦除儲存容量之區塊的項。區 塊可視情況含有有效資料。在清單中之每一項具有一含有 用於定義與該項有關之在該區塊巾之有效諸量的值的攔 位。在清單中之項根據在此等攔位中之值而排序。可由圖 32之步驟753之技術自第一清單或第二清單之頭部（具有最 少量無效資料之區塊)選擇一區塊。 圖33之表闡述放於部分區塊清單及過時區塊清單上以用 於根據第三實施例之此修改之回收操作的區塊類型的細 節。為放於部分區塊清單上，一區塊含有有效資料及已擦 除谷里兩者。其與在區塊中是否存在任何過時資料無關。 為放於過時區塊清單上，區塊含有過時資料，以及有效資 料或已擦除容量中之一者。 結論 雖然已參考本發明之例示性實施例描述了本發明之各種 悲樣’但應瞭解’本發明有權在隨附申請專利範圍之全部 範疇内受到保護。 【圖式簡單說明】 圖1示意性地說明主機及所連接非揮發性記憶體系統； 圖2為用作圖1之非揮發性記憶體之實例快閃記憶體系統 的方塊圖； 圖3為可在圖2之系統中使用之記憶體單元陣列的代表性 電路圖； 127921.doc -70- 200844740 圖4說明圖2之系統之實例實體記憶體組織； 圖5展示圖4之一部分實體記憶體之放大圖· 圖6展示圖4及圖5之一部分實體記憶體 圖7A、圖7B及圖7C展示且比較操作—放大圖； 系統之三種方法； 再&式化記憶體 圖8A、圖8B及圖8C以不同格式展 7A、围―中所展示相二=較與分別在圏 系統之三種方法以及與域系統之=1再程式化記憶趙 圖9A、圖9B及圖9C以不同格式展一 气展不且比較與分別在圖 8A、圖8B及圖8C中所展示相同之 么认 —% + 1 呆作了再.式化記憶體 糸、、’充之二種方法及與主機之介面； 圖10說明可用於進行圖9C之技 文釘之邏軏至實體區塊映射 的一實例； 圖11展示用以設定參數以進行在圖9C及圖财所說明之 技術的在主機與記憶體系統之間的交互； 圖12說明直接資料檔案系統之操作週期，· 圖13A至圖13D展示寫入檔案資料之四個不同實例； 圖14A至圖14E展示寫入單個資料檔案之順序； 圖15展示回收圖14E之區塊的結果，· 圖16A至圖16D展示儲存於區塊類型之多種允許組合中 之資料檔案的實例； 圖17為給出根據一特定實例之播案之准許狀態的表； 圖18為展示由於程式化資料之准許檔案狀態轉變的狀態 園， 127921.doc -71- 200844740 圖19為描述在圖18中展示之權案狀態轉變之表； 圖2〇為展示由於過時資料之准許檔案狀態轉變的狀態 圖， 圖21為描述在圖20中展示之檔案狀態轉變之表； 圖22為展不由於回收區塊之准許檔案狀態轉變的狀態 圖； 圖23為描述在圖22中展示之檔案狀態轉變的表； 圖24展示資料檔案與邏輯區塊之對準的一實施例； 圖25為展示在用於圖24之資料對準實施例之多種狀況下 的作用區塊之分配的表； 圖26展示資料檔案與邏輯區塊之對準的一替代實施例； 圖27為展示在用於圖26之資料對準實施例之多種狀況下 的作用區塊之分配的表； 圖28A至圖28D展示區塊回收操作之實例； 圖2 9為概括說明回收操作之流程圖； 圖30說明儲存於典型部分記憶體單元區塊中之資料的類 型； ' 圖3 1提供進行圖29之流程圖之步驟中之一者的特定實施 例的細節； 圖32提供執行圖29之流程圖之相同步驟的替代實施例的 細節；及 圖3 3為定義放在又一實施例之兩個區塊清單上之區塊類 型的表。 【主要元件符號說明】 127921.doc -72· 200844740 1 主機糸統 2 快閃記憶體 3 配合零件 4 配合零件 5 應用程式部分 6 驅動程式部分 7 快閃記憶體 8 電路 11 控制器 13 系統匯流排 15 記憶體晶片 17 導體 19 導體 21 導體 23 内部匯流排 25 介面電路 27 處理器 29 唯讀記憶體（ROM) 31 隨機存取記憶體（RAM) 33 電路 35 電路 37 外部接觸 39 時脈 41 平面 127921.doc -73. 200844740 43 平面 45 行控制電路 47 行控制電路 49 位元線 51 位元線 53 子線 55 列控制電路 57 源電壓控制電路 59 源電壓控制電路 61 P型井電壓控制電路 63 P型井電壓控制電路 65 輸入/輸出電路 67 輸入/輸出電路 71 線 73 介面電路 75 狀態機 77 控制線 78 控制線 79 控制線 80 控制線 81 控制線 83 線 91 線 92 線 127921.doc -74- 200844740

93 線 94 線 97 記憶體單元串 98 記憶體单元串 99 記憶體单元串 100 記憶體單元串 101 記憶體單元串 102 記憶體單元串 103 記憶體单元串 104 記憶體單元串 107 電荷儲存記憶體單元 108 電荷儲存記憶體單元 109 電荷儲存記憶體單元 110 電荷儲存記憶體單元 111 選擇電晶體 112 選擇電晶體 115 字線 116 字線 117 字線 118 字線 119 閘極 120 閘極 123 區塊 125 區塊 127921.doc -75- 200844740 131 平面/子陣列 132 平面/子陣列 133 平面/子陣列 134 平面/子陣列 137 區塊 138 區塊 139 區塊 140 區塊 141 元區塊 143 元區塊 145 區塊 146 區塊 147 區塊 148 區塊 151 元頁 153 區 155 1¾ 157 資料部分 159 附加項部分/位元組 161 連續邏輯位址空間 163 區塊/邏輯至實體位址表 165 記憶體單元陣列 167 元區塊 169 元區塊 127921.doc -76- 200844740 171 元區塊 173， 功能 181 實體區塊 183 區塊 184 部分/資料群組 185 區塊 187 資料 189 附加項資料 191 區塊 193 邏輯區塊 195 實體頁/資料檔案之一部分 197 實體頁/檔案之一更新部分 199 實體頁/先前寫入之資料的一部分 201 〜202 、 頁 203 > 204 207

209 211 213 641 643 645 661 663 記憶體裝置 非揮發性儲存空間 主機 内連匯流排 區塊 區塊 區塊 區塊 區塊 127921.doc -77- 200844740 665 區塊 669 區塊 671 區塊 673 區塊 675 區塊 P0、Ρ1···Ρ7 頁

127921.doc -78-

Claims (1)

1. 200844740 十、申請專利範圍： κ 一種識別在一系統内之檔案物件之資料的方法，1 含： ，、匕 維持 s彳分為邏輯區塊之系統邏輯位址空間， 對在該等邏輯區塊中之一或多相之料標案物件中 之個別者指派唯-位址，纟中該等邏輯區塊可個別地含 有一個以上檔案物件之位址，及

   I制對-個別檔案物件指派的亦含有一第二檔案物件 之資料之邏輯區塊的數目。 2·如請求項1之方法，其另外包含： 在-主機系統中進行該方法，該主機系統另外提供該 等，案物件之該資料且在—適於與—記憶體系統連接之 外部介面處利用該邏輯位址空間。 3·如請求項1之方法，其另外包含： 一在-記憶體系統中進行該方法’該記憶體系統另外自 -外部源接收該等檔案物件之該資料且在—與非揮發性 育料儲存媒體之介面處在該記憶體系統内利用該邏輯介 面位址空間。 4_如請求項1之方法，其另外包含： =_單元中進行該方法，該處理單元適於與一供 應該h料檔案物件之主機可移除地連接，且適於與一 在一與該處理單元之介面處利 』用a邏輯位址空間的記憶 體系統可移除地連接。 5·如請求項1至4中任一項之方 方去，其中限制邏輯區塊之該 127921.doc 200844740 數目包括將寫入一個別資料檔案物件的亦含有一第二檔 、勿件之資料的邏輯區塊之數目限於一預定最大數目。 6. 如凊求項5之方法，其中該預定最大數目為2。 7. 種關於—主機系統經由一介面轉移權案物件之資料的 • 方法’該介面適於與—具有可在再程式化之前—起擦除 體單元之區塊的類型之一非揮發性記憶體系統連 . 接，該方法包含： • 在該介面處維持一劃分為邏輯區塊之邏輯位址空間，及 立：該等邏輯區塊可個別地含有一個以上檔案物件但僅 部分填充有一個別檔案物件之資料的邏輯區塊的一數目 限於小於至少_預設極限的—方式指定在該等邏輯區塊 中之一或多者内之該等檔案物件中之個別者内之資料的 位址，以使-或多個其他檔案物件之資料被寫入或可被 寫入至該等部分填充區塊中。 8·如請求項7之方法，其另外包含： • ㈣邏輯位址空間之該等邏輯區塊的大小組態成個別 地具：與—記憶體系統之記憶體單元之該等個別區塊相 同的貝料儲存容量，該主機系統適於與該記憶體系統 • 接。 • 9·如4項7之方法’其中對經由該介面發送該等槽案物 件之賁料的該主機指定該等邏輯區塊中之一或多者内之 該等個別檔案物件的資料之該等位址。 1〇·:種在—具有記憶體單元之區塊之非揮發性記憶體系統 儲存檔案物件之資料的方法，該等記憶體軍元可在用 127921.doc 200844740 該資料再程式化之前一起擦除，其中·· 將一邏輯位址空間劃分為邏輯區塊，該等邏輯區塊個 別地具有對應於該等個別記憶體單元區塊之特徵的至少 一特徵， 對個別檔案物件之資料指派在該等邏輯區塊中之一或 夕者内的位址，其中該等邏輯區塊可個別地含有一個以 上檔案物件之資料的位址，但含有一特定個別檔案物件 之資料加上另一檔案物件之資料的邏輯區塊數目為有限 的，且 該等邏輯區塊之位址在該印，啥挪^ 抑 牡邊°己f思體糸統内映射至記憶體 單元區塊之位址。 11.如請求項U)之方法，其中對該特定檀案物件之資料指派 位址包括將僅部分填充有該特定檔案物件之資料之邏輯 區塊的數目限於一預定數目。 12.如請求項U之方法，其中該預定數目為2。

   13·如請求項1〇之方法，1中兮 ，。 ，、中該至乂 一對應特徵包括該等個 別邏輯區塊的一 ^ ^ ^ >Wr 計储存令里與該等個別記憶體單元區 塊之資料儲存容量相同。 +7°122 少一對應特徵包括： 14·如請求項10之方法，其 a等個別建輯區塊之該資料儲存容量與該等個別 體早兀區塊之該資料儲存容量相同， … 將該等個别邏輯區塊劃 個頁，該等頁具有與該等記憶體單元區多 相同之資料儲存容量，且 別夕個頁 127921.doc 200844740 將忒等個別邏輯區塊之最低頁位址映射至該等個別記 憶體單元區塊之最前頁中。 15·種關於纟機系統經由一介面轉移檀案物件之資料的 方法，該介面適於與一具有可在再程式化之前一起擦除 L體單元之單位的類型之一非揮發性記憶體系統連 接’该方法包含： 在該介面處維持一劃分為邏輯區塊之邏輯位址空間， 根據一在要指定之個別區塊内定址之檔案資料的結構 指定一組複數個邏輯區塊類型， 根據一儲存要指定之個別檔案之資料的一或多個邏輯 區塊之類型的一組合指定一組複數個准許檔案狀態， 維持一在該等邏輯區塊内定址之個別資料檔案之該等 播案狀悲的記錄，及 對根據在該記錄中之該個別檔案之當前狀態選擇的一 類型之邏輯區塊指定一個別檔案之資料的位址。 16·如請求項15之方法，其中該等經指定複數個資料區塊類 型包括第一複數個類型，其中僅一個檔案之資料儲存於 一單個邏輯區塊中；及第二複數個類型，其中兩個或兩 個以上檔案之資料儲存於一單個邏輯區塊中，且其中該 等准許檔案狀態限制可被指定該等檔案中之一單個者的 位址的該第二複數個類型之區塊的一最大數目。 17 · —種電腦系統，其包含： 一介面，其中利用在一劃分為不同區塊之連續邏輯位 址空間内之位址識別資料檔案，及 127921.doc -4 - 200844740 一處理器’其與該介面操作地連接以導致個別檔案之 資料由該等邏輯區塊中之―或多者的位址所識別，該等 邏輯區塊經選擇以維持部分含有該等檔案中之任_者之 負料的s塊的一數目低於一預設極限。 18. 如請求項17之系統，其中該處理器進—步操作以取決於 部分填充有該檔案之資料之位址的邏輯區塊的數目而對 . 該等個別檔案指派複數個經指定狀態中之一者。 19. 如請求項17之系統’其中該處理器進—步操作以對具有 在該等邏輯區塊中定址之資料的每一檔案指派一狀態， 且選擇—給定檔案之資料將根據該給定檔案之該狀態而 定址的該等邏輯區塊中之一者。 20. 如請求項19之系統，其中該處理器進一步操作以至少部 分基於部分填充有該檔案之資料之位址的邏輯區塊的_ 數目來對具有在該等邏輯區塊中定址之資料的每一檔案 指派一狀態。 田a • 21·如請求項2〇之系統，其中該處理器進一步操作以另外基 :邛刀填充有该檔案之資料之位址的亦含有可被指定額 外位址之未用容量的邏輯區塊的一數目來對具有在該等 • 邏輯區塊中定址之資料的每一檔案指派一狀態。 、22·如：求項2〇之系統，其中該處理器進一步操作以另外基 ;:刀填充有該檔案之資料之位址的亦含有一或多個其 他檔案之資料之位址的區塊的一數目來對具有在該等邏 輯區塊中定址之資料的每一檔案指派一狀態。 •如明求項17之系統，其中該介面包括一外部介面。 127921.doc