最佳順序性簇管理的fat分析的製作方法

2023-10-08 17:50:39 2

專利名稱：最佳順序性簇管理的fat分析的製作方法
技術領域：
本發明大體上涉及用於與計算系統一起使用的數據存儲系統，且更確切地說，涉及用於在非易失性存儲器存儲裝置上保存數據的技術。
背景技術：
如今，有許多商業上成功的非易失性存儲器產品正被使用，特別是具有小型卡形式的存儲器產品，這類產品使用形成在一個或一個以上集成電路小片上的快閃記憶體EEPROM(電可擦除可編程只讀存儲器)單元陣列。通常提供單獨集成電路小片上的存儲器控制器來作為對主機的接口。主機可使用控制器來對非易失性存儲器執行多種操作(例如，讀、寫)。控制器通常包含微處理器、某種非易失性只讀存儲器(ROM)、易失性隨機存取存儲器(RAM)和一個或一個以上專用電路，例如在編程和讀取數據期間在數據穿過控制器時從數據中計算出誤差校正碼(ECC)的專用電路。一些可在市面上買到的卡是壓縮快閃記憶體TM(CF)卡、多媒體卡(MMC)、安全數字(SD)卡、智能媒體卡、人事標籤(P-Tag)和存儲器存儲卡。主機包含個人計算機、筆記本計算機、個人數字助理(PDA)、各種數據通信裝置、數位相機、蜂窩式電話、可攜式音頻播放機、汽車音響系統和類似類型的設備。除了存儲卡實施方案之外，非易失性存儲器可替代性地嵌入到各種類型的主機系統中。
如在大多數集成電路應用中，快閃記憶體EEPROM存儲單元陣列也存在縮小實施某種集成電路功能所需的矽襯底面積的壓力。始終需要增加可存儲在給定矽襯底面積中的數字數據的數量，以便增加給定尺寸的存儲卡及其它類型的封裝的存儲容量，或者既增加容量同時又減小尺寸。增加數據存儲密度的一種方法是在每個存儲單元和/或每個存儲單位或元件中存儲一位以上的數據。通過將存儲元件電荷電平電壓範圍窗口劃分成兩種以上狀態來完成這種做法。使用四種此類狀態允許每個單元存儲兩位數據，每種狀態在每個存儲元件中存儲三位數據，等等。第5,043,940號和第5,172,338號美國專利中描述了使用浮柵的多狀態快閃記憶體EEPROM結構及其操作，且前述第2003/0109093號美國專利申請公開案中描述了使用介電浮柵的結構。出於多種原因，也可用第5,930,167號和第6,456,528號美國專利中描述的方式以兩種狀態(二進位)來操作多狀態存儲單元陣列的選定部分。
典型的快閃記憶體EEPROM陣列的存儲單元被劃分為離散的單元「區塊」，所述區塊可被一起擦除。每個擦除區塊通常存儲一個或一個以上頁面的數據，頁面是編程和讀取的最小單位，雖然也可在不同子陣列或平面中並行編程或讀取一個以上頁面。每個頁面通常存儲一個或一個以上扇區的數據，扇區大小是由主機系統定義的。實例性扇區根據由磁碟驅動器建立的標準而包含512個字節的用戶數據，加上若干字節的與用戶數據和/或存儲所述用戶數據的擦除區塊有關的額外開銷信息。此類存儲器通常在每個擦除區塊內配置有32、128或更多的頁面，且每個頁面存儲一個或僅若干個主機扇區的數據。還應注意，為了將數據重新寫入區塊，應首先擦除所述區塊。
為了在將用戶數據編程到存儲器陣列中和從存儲器陣列中讀取用戶數據期間增加並行度，通常將所述陣列劃分成子陣列(一般稱為平面)，所述子陣列中含有其各自的數據寄存器和其它電路以實現並行操作，從而使得可同時將若干扇區的數據編程到若干平面或所有平面中的每一者中或從若干平面或所有平面中的每一者中讀取若干扇區的數據。可將單個集成電路上的陣列以物理形式劃分成多個平面，或可由單獨的一個或一個以上集成電路小片形成每個平面。第5,798,968號和第5,890,192號美國專利中描述了此類存儲器實施方案的實例。
為了進一步高效地管理存儲器，可將擦除區塊以邏輯形式連結在一起，以形成虛擬區塊或元區塊。也就是說，可將每個元區塊定義為包含來自每個平面的一個擦除區塊。第WO 02/058074號國際專利申請公開案中描述了所述元區塊的使用。元區塊由主機邏輯區塊地址識別為用於編程和讀取數據的目的地。同樣，元區塊的所有擦除區塊被一起擦除。與此類大型區塊和/或元區塊一起操作的存儲器系統中的控制器執行若干功能，包含從主機接收的邏輯區塊地址(LBA)與存儲單元陣列內的物理區塊編號(PBN)之間的轉譯。通常由區塊地址內的偏移量來識別區塊內的個別頁面。地址轉譯通常涉及使用邏輯區塊編號(LBN)和邏輯頁面的中間項。因此，存儲器陣列中的區塊可由單個擦除區塊組成或可由以邏輯形式連結起來以形成元區塊的兩個或兩個以上擦除區塊組成。
從主機應用程式的角度看，可將快閃記憶體存儲器劃分成從邏輯地址零(0)開始且以邏輯地址N結束的邏輯地址空間。圖1說明主機的邏輯地址空間102，其被分割成多個「邏輯扇區」。主機將若干(例如，四到六十四(4-64)個)邏輯扇區分組成一簇。如圖1所示，主機可將邏輯地址空間102劃分成多個簇，包含簇A、B、C、D、E、F、G和H。由此，這些簇中的每一者可代表預定數目的扇區(例如，每個簇四到六十四(4-64)個邏輯扇區)。在任何情況下，主機均以數據的邏輯單位來分配數據，所述邏輯單位可稱為「簇」。舉例來說，簇A、B和C可用來分配文件1，而簇D用來分配文件2。應注意，主機以簇分配文件。然而，並非簇中的所有邏輯扇區均需要含有一文件的數據。舉例而言，簇C中只有一部分(例如，只有一個邏輯扇區)可具有數據。然而，主機通常將整個簇分配給文件，即使並非需要所述簇中的所有邏輯扇區。
主機可使用文件分配表(FAT)104來跟蹤文件。文件分配表(FAT)104有效地代表邏輯文件結構，且也指示已為邏輯文件結構中的每個文件分配了哪個簇。主機通過更新文件分配表(FAT)104來維護邏輯文件結構。舉例而言，當分配了新文件時，對文件分配表(FAT)104進行更新，以尤其指示已為新文件分配了哪個(些)簇。同樣，當刪除文件或目錄時，主機更新文件分配表(FAT)104。應注意，由於更新的原因，主機可能會對簇解除分配。舉例而言，當主機刪除文件1時，可能會得到經過更新的文件分配表(FAT)106，其中主機有效地對被分配用於存儲文件1的簇A、B和C解除分配。
與主機的邏輯地址空間相反，快閃記憶體存儲器控制器的邏輯地址空間被劃分成多個「邏輯區塊」。換句話說，可將同一邏輯地址空間102表示為控制器的邏輯地址空間103。在此實例中，邏輯地址空間102和邏輯地址空間103的基礎單位均為扇區。如圖1所示，可將邏輯地址空間103劃分成多個邏輯區塊，包含邏輯區塊1和邏輯區塊2，每個邏輯區塊包括多個扇區的數據，所述扇區的數據被映射到存儲器陣列的單個區塊。這些邏輯區塊被映射到可作為擦除單位的存儲器區塊(例如，單個擦除區塊或元區塊)中。因此，邏輯區塊與存儲器陣列的區塊之間存在一一對應，其中邏輯區塊中的所有扇區均存儲在單個區塊中。舉例來說，邏輯區塊1可被映射到區塊2中，等等。總而言之，主機和控制器使用不同的存儲器邏輯單位。主機將邏輯地址空間劃分成多個簇，而控制器將邏輯地址空間劃分成多個邏輯區塊。還應注意，通常僅將主機簇施加到分配給應用數據和子目錄條目的邏輯地址空間。此外，主機可能不會將分配給其它系統數據的邏輯地址空間作為簇來管理。還應注意，第一簇一般並不位於邏輯地址空間的開始處。因此，簇和邏輯區塊可能並不彼此對準。
然而，常規控制器並不知道主機所使用的邏輯結構。常規上，控制器僅將主機所使用的邏輯地址102映射成邏輯地址103，然後再將其映射成物理地址110。這意味著常規控制器不會考慮主機的數據邏輯結構或主機操作可能對數據造成的結果。舉例而言，當分配了新文件時，更新邏輯文件系統104以尤其指示已為所述新文件分配了哪個(些)簇。同樣，當刪除了文件或目錄時，主機會更新邏輯文件系統104。此外，主機可能會將一個或一個以上簇解除分配。舉例而言，當主機刪除了文件1時，經過更新的文件分配表106指示主機已對先前分配用於存儲文件1的簇A、B和C有效地解除分配(即，在更新的文件分配表106中已不再表示文件1)。雖然簇A、B和C已被主機解除分配且可被擦除，但常規控制器不會對對應於已解除分配的簇A、B和C的數據進行「垃圾收集」。這意味著數據將繼續在存儲器上。垃圾收集是將有效扇區的數據從含有廢棄扇區的數據的初始區塊拷貝到更新區塊的操作。當已經拷貝了所有有效扇區的數據時，可對初始區塊進行標記以供擦除。通常以此方式將數據從兩個或兩個以上區塊合併到單個區塊中，因而更有效率地存儲數據且釋放存儲器陣列中的空間。垃圾收集期間不必要的數據拷貝會降低此類操作的效率。此外，在可將兩個區塊中的數據合併到一個區塊中時，在垃圾收集期間會在更新區塊時將解除分配的數據拷貝若干次。
為了進一步說明，圖1中描繪初始區塊120。為簡單起見，假設初始區塊120包含對應於主機用來分配文件1和2的邏輯簇A、B、C和D的數據。此外，進一步假設主機後來對文件1(簇A、B和C)解除分配，初始區塊120仍然含有所有邏輯簇A、B、C和D，因為控制器無法知道文件1已被主機解除分配。然而，主機已要求控制器更新初始區塊120的數據部分D。換句話說，在某一點處，主機可能想改變文件2，因此其使用其知道的對應於一個或一個以上應被更新的邏輯扇區的數據的邏輯地址來發送寫入請求。控制器確定主機所定址的這些邏輯扇區對應於已由主機寫入的扇區(例如，簇D)，因此更新區塊122是被部分地使用，因為初始區塊120中的數據無法被覆寫。這意味著可在一段時間內使用兩個區塊來代表邏輯區塊，直到更新區塊122被「關閉」(即，初始區塊120中的所有數據均被拷貝到區塊122)為止。(例如)在垃圾收集循環期間，可將初始區塊120與更新區塊122組合，以使得更新區塊122成為「初始」區塊122，且先前初始區塊120被擦除並被返回到可用存儲器區塊的集區。在任何情況下，應注意，遲早會將對應於被解除分配的簇(A、B和C)的數據拷貝到更新區塊122，以使得更新區塊122可被關閉且初始區塊120可被擦除。控制器可在易失性存儲器或非易失性存儲器內保存映射表，所述映射表定義存儲器區塊對於數據的邏輯區塊的分配。拷貝存儲在非易失性存儲器中的數據會花費大量時間和資源。然而，拷貝已被解除分配的數據(例如，已被解除分配的簇A、B和C)並不是必須的。因此，如果不拷貝已被解除分配的數據，可進一步增強系統性能。一般來說，需要在遵守普遍使用的定址慣例的同時儘可能地增強系統性能。
因此，替代性非易失性存儲器管理技術將是有用的。

發明內容
概括地說，本發明涉及用於管理非易失性存儲器系統(例如，快閃記憶體存儲器)中的數據的技術。根據本發明的一個方面，控制器可使用與主機的文件系統有關的信息來確定一個或一個以上簇(或一個或一個以上簇內的一個或一個以上扇區)當前是否被分配，所述與主機的文件系統有關的信息由主機存儲在非易失性存儲器上。將了解到，控制器可(尤其)使用與主機的文件系統有關的信息來確保(例如)在垃圾收集循環期間沒有將一個或一個以上簇(或一個或一個以上扇區)從存儲器中的一個位置拷貝到另一位置。因此，可避免某些常規上執行的不必要操作(例如拷貝數據)，且增強系統性能。
還將了解到，控制器可直接使用一般由主機寫入在文件分配表(FAT)中的信息來確定是否已將一個或一個以上先前分配的簇解除分配。或者，控制器可使用寫入在根目錄、子目錄和文件分配表(FAT)中的信息來(例如)在數據分配表(DAT)中產生和/或維護其自身關於簇分配的信息。然而，應明了，可將本發明實施為利用一般存儲在文件分配表(FAT)中的信息。因此，控制器不必維護其自身的信息或產生任何額外數據結構(例如，數據分配表)。然而，如下文將要描述的，維護數據分配表(DAT)帶來的益處可能會多於僅僅依賴於從文件分配表(FAT)獲得的信息。因此，還將進一步說明(例如)實施為數據分配表(DAT)的數據屬性存儲(DAS)。
一般來說，控制器可在非易失性存儲器中維護數據屬性存儲(DAS)，所述數據屬性存儲(DAS)包含一個或一個以上數據屬性。數據屬性可提供關於數據的有用信息(例如分配或解除分配狀態、大小、優先權)。由此，可使用數據屬性存儲(DAS)來更智能地管理數據。本發明的另一方面涉及用於使用數據屬性存儲(DAS)來管理數據的技術。
在一個實施例中，將數據屬性存儲(DAS)實施為分配存儲(AS)。所述分配存儲(AS)可(例如)實施為表或提供每個數據簇(主機的邏輯單位)的分配狀態的數據分配表(DAT)。簇代表主機用來以邏輯形式組織數據的邏輯單位。為了實現更好的存儲器管理，非易失性存儲器系統的控制器可存取數據分配表(DAT)。由此，數據分配表(DAT)有效地提供主機所使用的邏輯結構與控制器之間的橋接。這允許控制器可有效地了解主機的邏輯結構。此外，控制器還監視主機活動以確定(例如)主機是否已將一簇解除分配。舉例而言，可監視DOS順應系統的根目錄、文件分配表(FAT)和子目錄以檢測主機對數據簇的解除分配。根目錄、文件分配表(FAT)或子目錄中的變化可能是(例如)因為主機刪除了文件或文件中的一部分而導致的。在任何情況下，當已檢測到對一個或一個以上數據簇的解除分配時，控制器更新數據分配表(DAT)。因此，數據分配表(DAT)可提供關於數據的更新的信息。此信息可用來更智能地管理數據。舉例而言，可使用解除分配狀態來確定在垃圾收集期間是否應當拷貝數據。無需拷貝已被解除分配的數據。因此，可避免常規上執行的某些不必要的操作且可增強系統性能。
在另一實施例中，可使用由主機存儲在FAT中或在DAS中的信息來確定應當怎樣存儲主機發送的一部分數據。以非順序性方式接收的數據可被以非順序性方式存儲，或者，可通過從其它地方拷貝數據以填充接收到的數據中的任何間隙來以順序性方式存儲。這種順序性存儲是有利的一種情況是主機向邏輯地址空間(例如簇)的可用(空閒的或被解除分配的)部分進行寫入。此類數據寫入指示主機正在存儲新數據，且並不指示任何以非順序性方式存儲數據的理由。通過將主機發送的數據扇區的邏輯地址與空閒簇的邏輯地址範圍進行比較，控制器可確定主機是否正寫入下一空閒簇。根據這一確定，控制器可選擇一種針對所述扇區的存儲方案。
在一個實施例中，確定從主機接收的扇區是否指示主機正在寫入下一空閒簇。如果是的話，將數據以順序性形式寫入在區塊中，用從存儲器陣列的其它地方拷貝的數據來填充數據中的任何間隙。如果不是的話，可考慮額外標準以確定以順序性方式還是以非順序性方式存儲數據。舉例來說，如果從主機接收到若干扇區且扇區之間存在邏輯地址的跳躍，那麼跳躍的大小可確定存儲方案。如果跳躍較小，那麼可用拷貝的數據來填充所得的間隙，且更新的數據可以用順序性格式來保存。在另一實例中，在更新區塊是順序性的且接近完整的情況下，更新區塊可由數據充滿以將其保持為順序性的，而並非寫入以非順序性方式接收的扇區。可基於從非易失性存儲器中的FAT的拷貝中直接獲得的信息或可基於從FAT導出的DAS或類似結構中的信息來選擇存儲方案。
可以多種方式來實施本發明，包含作為方法、系統、裝置、設備或計算機可讀媒體。將從以下詳細描述中容易了解本發明的其它方面和優點，所述詳細描述結合附圖舉例說明了本發明的原則。


附圖各圖中以實例而並非限制的方式說明本發明，在附圖中相似的參考元件符號指代類似的元件，且其中圖1說明邏輯地址空間，其可被分割為若干邏輯扇區。
圖2A描繪根據本發明一個實施例的拷貝管理方法。
圖2B描繪根據本發明一個實施例的計算環境。
圖3A描繪根據本發明一個實施例的數據分配表(DAT)。
圖3B描繪根據本發明一個實施例的數據分配表(DAT)的條目。
圖3C描繪根據本發明一個實施例的可由控制器使用的主機的邏輯數據結構。
圖4描繪根據本發明一個實施例的用於向快閃記憶體存儲器控制器提供關於存儲在快閃記憶體存儲器上的數據的信息的方法。
圖5說明根據本發明一個實施例的快閃記憶體存儲器維護方法。
圖6說明根據本發明一個實施例的監視方法。
圖7描繪根據本發明一個實施例的示範性垃圾收集方法。
圖8描繪根據本發明一個實施例的數據分配表(DAT)。
圖9A展示文件分配表(FAT)的實例。
圖9B展示從圖9A的FAT導出的DAT。
圖9C展示針對一部分主機數據的簇與扇區之間的對應的實例。
圖9D展示將非順序性數據存儲在混亂區塊中且之後將其拷貝到順序性區塊。
圖9E展示將非順序性數據直接存儲在順序性區塊中。
圖10展示根據本發明一實施例的用於為一部分主機數據選擇存儲方案的流程圖。
圖11展示根據本發明另一實施例的用於為一部分主機數據選擇存儲方案的流程圖。
圖12A展示以順序性方式存儲的非順序性數據的實例。
圖12B展示以非順序性方式存儲的非順序性數據的第一實例。
圖12C展示以非順序性方式存儲的非順序性數據的第二實例。
圖12D展示以非順序性方式存儲的非順序性數據的第三實例。
具體實施例方式
本發明涉及用於管理非易失性存儲器系統(例如快閃記憶體存儲器)中的數據的技術。根據本發明的一個方面，控制器可使用與主機的文件系統有關的信息來確定一個或一個以上簇(一個或一個以上簇內的一個或一個以上扇區)當前是否被分配，所述與主機的文件系統有關的信息由主機存儲在非易失性存儲器上。將了解到，控制器可(尤其)使用與主機的文件系統有關的信息來確保(例如)在垃圾收集循環期間沒有將一個或一個以上簇(或所述簇內的一個或一個以上扇區)從存儲器中的一個位置拷貝到另一位置。因此，可避免某些常規上執行的不必要操作(例如拷貝數據)，且可增強系統性能。
還應了解到，控制器可直接使用一般由主機寫入在文件分配表(FAT)中的信息來確定是否已將一個或一個以上先前被分配的簇解除分配。或者，控制器可使用寫入在根目錄、子目錄和文件分配表(FAT)中的信息來(例如)在數據分配表(DAT)中產生和/或維護其自身關於簇分配的信息。然而，應明了，本發明可被實施成利用一般存儲在文件分配表(FAT)中的信息。因此，控制器不必維護其自身的信息或產生任何額外數據結構(例如，數據分配表(DAT))。然而，如以下將要描述的，維護數據分配表(DAT)帶來的益處可能會多於僅僅依賴於從文件分配表(FAT)獲得的信息。因此，也將進一步說明可(例如)實施為數據分配表(DAT)的數據屬性存儲(DAS)。
一般來說，包含一個或一個以上數據屬性的數據屬性存儲(DAS)可由控制器維持在非易失性存儲器中。數據屬性可提供關於數據的有用信息(例如分配或解除分配狀態、大小、優先權)。由此，可使用數據屬性存儲(DAS)來更智能地管理數據。本發明的另一方面涉及用於使用數據屬性存儲(DAS)來管理數據的技術。
在一個實施例中，將數據屬性存儲(DAS)構建為分配存儲(AS)。可將分配存儲(AS)(例如)構建為表或提供每個數據簇(主機的邏輯單位)的分配狀態的數據分配表(DAT)。簇代表主機用來以邏輯形式組織數據的邏輯單位。為了實現更好的存儲器管理，非易失性存儲器系統的控制器可存取數據分配表(DAT)。由此，數據分配表(DAT)有效地提供主機所使用的邏輯結構與控制器之間的橋接。這允許控制器可有效地了解主機的邏輯結構。此外，控制器還監視主機活動以確定(例如)主機是否已將一簇解除分配。舉例而言，可監視DOS順應系統的根目錄、文件分配表(FAT)和子目錄以檢測主機對數據簇的解除分配。根目錄、文件分配表(FAT)或子目錄中的變化可能是因為(例如)主機刪除了文件或文件中的一部分而導致的。在任何情況下，當檢測到對一個或一個以上數據簇的解除分配時，控制器更新數據分配表(DAT)。因此，數據分配表(DAT)可提供關於數據的更新的信息。可使用此信息來更智能地管理數據。舉例而言，可使用解除分配狀態來確定在垃圾收集期間是否應當拷貝數據。無需拷貝已被解除分配的數據。因此可避免常規上執行的某些不必要的操作且可增強系統性能。
以下參照圖2A到圖8來論述本發明的實施例。然而，所屬領域的技術人員將容易了解，此處關於這些附圖給出的詳細說明出於解釋性目的，因為本發明超出這些有限實施例。舉例來說，雖然描述參考了快閃記憶體存儲器，但可使用其它類型的非易失性存儲器。其它類型的非易失性存儲器包含磁阻RAM(MRAM)、鐵電RAM和相變存儲器(也稱為奧弗辛斯基電效應統一存儲器或OUM)。
如上所述，根據本發明的一個方面，控制器可使用與主機的文件系統有關的信息來確定一個或一個以上簇(或簇內的扇區)當前是否被分配，所述與主機的文件系統有關的信息由主機存儲在非易失性存儲器上。控制器可(尤其)使用與主機的文件系統有關的信息來確保在垃圾收集循環期間沒有將一個或一個以上簇(或簇內的扇區)從存儲器中的一個位置拷貝到另一位置。為了進一步說明，圖2A描繪根據本發明一個方面的拷貝管理250。首先，主機使用非易失性存儲器裝置來存儲(252)供文件系統使用的信息。接下來，控制器使用由主機存儲(252)的信息來確定(254)一個或一個以上簇(或一個或一個以上簇內的一個或一個以上扇區)當前是否被分配給任何有效文件。如所屬領域的技術人員將了解，控制器可直接使用一般由主機寫入在文件分配表(FAT)中的信息，以便確定(254)一個或一個以上簇(或一個或一個以上簇內的一個或一個以上扇區)當前是否被分配給任何有效文件。或者，控制器可使用根目錄、子目錄和FAT中寫入的信息連同由主機寫入到裝置的邏輯扇區序列，以便產生和維護其自身的關於簇分配的信息。舉例來說，控制器可產生和/或維護其自身的數據分配表(DAT)。在任何情況下，控制器確保(256)在存儲器內在垃圾收集操作期間沒有將被確定(254)為當前未被分配的任何簇(或簇內的扇區)從一個位置拷貝到另一位置。換句話說，只在確定(254)了簇(或簇內的扇區)當前被分配的情況下才拷貝所述簇(或簇內的扇區)。操作256之後結束拷貝管理方法250。
如上所述，維護數據分配表(DAT)帶來的益處可能會多於僅僅依賴於從文件分配表(FAT)獲得的信息。如所屬領域的技術人員將了解，FAT可能不會總是指示簇已被解除分配。舉例來說，FAT中可能存在沒有連結到目錄中的任何文件參考的簇條目鏈。
當文件被刪除時，其目錄條目被主機中的文件系統修改(文件名的首字符被改為0xE5)以表示文件已被刪除。然而，FAT中的簇條目可能會保持其連結信息，就好像其仍被分配給一文件。用於重新使用簇和用於將FAT簇條目更新為「0x0000」以表示未使用的算法通常是主機中的特定文件系統實施方案的功能。DAT可使用目錄或子目錄信息中的變化來允許簇屬性反映所述簇對一文件的當前分配狀態，而無需依賴於主機文件系統。對於某些環境，DAT的實施甚至可能會比僅僅依賴於FAT更安全。當僅使用FAT來確定簇的分配狀態時，存儲器系統可能直到主機在文件結尾處更新FAT時才會知道簇對於文件的分配情況。因此，如果主機在寫入FAT前修改了已經寫入的文件的一部分，那麼控制器可能會丟棄某些仍然具有已解除分配狀態的有效數據。DAT的實施可有效地解決這一問題。
此外，根據本發明的原理而提供的數據分配表(DAT)也可提供FAT通常不會提供的特徵。舉例來說，FAT為簇定義單一的分配狀態。然而，DAT可被實施成(例如)允許記錄多位狀態，從而允許將分配狀態分解成在一簇內的一扇區或扇區群組。這允許控制器避免在文件之間拷貝未被分配的扇區，其中僅部分地使用第一文件的最後簇。鑑於DAT可提供的優點和額外特徵，以下描述的實施例進一步說明在數據屬性存儲(DAS)(例如，DAT)中保存其自身的信息的控制器。然而，顯而易見，控制器可在不偏離本發明範圍和精神的情況下，僅依賴於FAT來確定與主機所使用的各種文件相關聯的分配狀態。
圖2B描繪根據本發明一個實施例的計算環境200。在計算環境200中，快閃記憶體存儲器控制器202允許主機應用程式204存取非易失性存儲器(例如，快閃記憶體存儲器206)。換句話說，主機應用程式204將快閃記憶體存儲器控制器202用作到快閃記憶體存儲器206的接口。因此，主機應用程式204可要求快閃記憶體存儲器控制器202對快閃記憶體存儲器206執行各種存取操作(例如，讀取、寫入)。主機應用程式204可使用邏輯地址空間來定址數據。快閃記憶體存儲器控制器將主機的邏輯地址空間映射成控制器邏輯地址空間，後者又被映射成快閃記憶體存儲器206上的物理地址空間。
此外，快閃記憶體存儲器可建立並維護數據屬性存儲(DAS)208。所述DAS 208包含關於與存儲在快閃記憶體存儲器206中的數據相關聯的各種屬性的信息。舉例而言，存儲在數據屬性存儲(DAS)208中的數據屬性可包含數據的分配狀態、所分配的數據的大小、優先權。一般來說，數據屬性存儲(DAS)208可存儲任何需要的數據屬性，且用一個或一個以上位的信息來代表所述屬性。應注意到，快閃記憶體存儲器控制器204提供數據屬性監視器208以監視主機應用程式204的活動。數據屬性監視器208可解譯主機應用程式204關於存儲在快閃記憶體存儲器206上的數據的活動。這意味著數據屬性監視器208可確定應在何處改變數據屬性並相應地在DAS 208中更新數據屬性。
為了進一步說明，圖3A描繪根據本發明一個實施例的數據屬性存儲(DAS)208。在此實施例中，將數據屬性208實施為數據分配表(DAT)308。由此，DAT 308提供關於非易失性存儲器系統的不同數據部分的分配/解除分配狀態的信息。將了解，可根據邏輯數據結構(即主機應用程式204使用的邏輯數據結構)來組織這些各種數據部分。如上所述，主機應用程式可將數據組織成主機邏輯單位，所述主機邏輯單位可稱為簇。可將DAT 308分割成代表這些簇的單位。
這意味著可將主機應用程式使用的每個邏輯簇表示為DAT 308中的條目。舉例來說，簇1可由第一(第1)條目來表示，簇10可由第十(第10)條目來表示，等等。此外，DAT 308的每一條目可指示簇的分配/解除分配狀態。舉例來說，可針對DAT 308的每一條目使用一個位來指示一邏輯簇當前是被分配還是被解除分配。應注意到，可使用若干位來提供關於一屬性的更多信息和/或關於若干屬性的信息。在任何情況下，DAT308實現對數據的更好管理。舉例而言，基於數據部分的分配/解除分配狀態，快閃記憶體存儲器控制器可避免拷貝已被主機應用程式解除分配的數據。
為了進一步說明，圖3B描繪根據本發明一個實施例的DAT 208的條目302。表條目302包含4個位，其中第一位(位0)可提供分配/解除分配狀態，且其它三(3)個位(位1-3)可一起指示已分配了多少數據(例如，「100」指示半滿，「111」指示滿，等)。同樣，可使用更多的位來提供關於簇的另一屬性的信息。舉例而言，每個簇可由四(4)個位來表示，其中一(1)個位代表解除分配狀態，且三(3)個位指示簇的哪個部分已被解除分配。如所屬領域的技術人員將了解，可以其它若干方式來定義簇的多個位。舉例來說，可利用極性(或次序)或可使用更多的位(例如，6、8、12)。或者，可分配所有的位來指示被完全解除分配的扇區的「子簇」的數目，且可(例如)由將所有位設定為零(0)來標記被完全分配的簇。
如上所述，數據屬性監視器210監視主機應用程式204的活動。基於這種監視，數據屬性監視器259可更新數據屬性存儲(DAS)208。如圖2所示，為了解譯主機應用程式204的活動，數據屬性監視器210需要實現主機了解和使用的數據的邏輯結構。為了進一步說明，圖3C描繪主機的邏輯數據結構，其可由根據本發明一個實施例的控制器使用。如圖3C所示，主機可將邏輯地址空間劃分成系統310和用戶空間312。系統數據310可包含文件分配表1(FAT1)、FAT2(FAT1的拷貝)和根目錄信息，其均可存儲為系統數據310。用戶空間可包含關於子目錄的信息。數據屬性監視器210可監視FAT1、FAT2、根目錄和子目錄，以確定主機應用程式202是否對任何數據解除分配(例如，移除文件、使文件變短等)。下文也將參照圖6來描述對數據的監視。
然而，現在參看圖4，圖中描繪了根據本發明一個實施例的用於向快閃記憶體存儲器控制器提供關於存儲在快閃記憶體存儲器上的數據的信息的方法400。快閃記憶體存儲器控制器可使用所述關於數據的信息(例如)來在數據維護(例如垃圾收集)期間作出關於數據的可靠決定。方法400可(例如)由圖2中的快閃記憶體存儲器控制器202使用。
首先，為快閃記憶體存儲器存儲裝置的控制器產生(402)數據屬性存儲(DAS)。所述數據屬性存儲(DAS)提供快閃記憶體存儲器存儲裝置中的複數個數據部分中的每一者的一個或一個以上屬性。對使用控制器來存取數據的主機的活動進行監視(404)。接下來，基於所述監視(404)，確定(406)是否應當更新與快閃記憶體存儲器存儲裝置的數據部分有關的屬性。相應地，如果確定(406)應當對快閃記憶體存儲器存儲裝置的至少一個數據部分執行更新，那麼更新(408)與至少一個數據部分有關的至少一個屬性。更新(408)之後，監視404主機的活動。此後，可以與上述相似的方式來繼續進行方法400，直到不再想要或需要監視數據為止。
如上所述，可提供數據屬性存儲(DAS)並由快閃記憶體存儲器控制器使用來執行維護操作(例如垃圾收集)。圖5描繪根據本發明一個實施例的快閃記憶體存儲器維護方法500。首先，確定502快閃記憶體存儲器控制器是否需要對存儲在快閃記憶體存儲器存儲裝置上的一部分數據執行維護操作。如果確定502控制器需要執行維護操作，那麼確定504數據屬性存儲(DAS)的哪個部分提供關於待維護的數據部分的信息。相應地，從數據屬性存儲(DAS)讀取506與數據部分有關的至少一個屬性。最後，基於至少一個數據屬性來執行508操作。應了解，基於由所述至少一個數據屬性提供的信息可更智能地執行維護操作。
圖6描繪根據本發明一個實施例的監視方法600。所述監視方法600說明可在圖4中說明的監視和更新操作(即，圖4中的操作404、406和408)期間執行的某些示範性操作。監視方法600可(例如)由快閃記憶體存儲器控制器來執行。首先，確定(602)接收到對寫入操作的請求。接下來，確定所述寫入操作是否定址指定的地址空間。舉例而言，指定的地址空間可包含由在DOS環境中操作的主機定址的邏輯地址空間的FAT1、FAT2、根目錄和子目錄。可根據根目錄中和其它子目錄中的信息來確定子目錄的指定地址空間。一般來說，指定的地址空間代表主機活動可能指示數據已被進行解除分配操作(例如，移除或修改文件目錄、編輯文件等)的地址空間。在任何情況下，如果在操作604處確定寫入操作是針對指定的地址空間，那麼讀取(606)當前存儲在指定地址空間中的數據。接下來，執行(608)寫入操作。在執行(608)了寫入操作之後，將先前讀取(606)的舊數據與寫入(608)的數據進行比較(610)。相應地，確定(612)數據中是否存在變化。如果確定(612)數據中沒有變化，那麼確定(602)是否接收到對寫入操作的請求。
或者，在更新的數據與舊數據寫入在不同的位置中的快閃記憶體存儲器系統中，可直接在舊位置與新位置處的數據之間進行比較(610)而不執行先前的讀取(606)。
然而，如果確定(612)已檢測到數據的改變，那麼對所述變化進行解譯(614)以確定(616)是否已將一個或一個以上簇解除分配。如果確定沒有將任何簇解除分配，那麼確定(602)是否接收到對寫入操作的請求。然而，應注意到，如果確定(616)已將一個或一個以上簇解除分配，那麼將數據分配表(DAT)中的所述一個或一個以上簇的狀態改變成指示「被解除分配」狀態。相應地，當察覺(616)指定地址空間中的數據變化已導致了對數據的解除分配時，監視方法600有效地更新(618)數據分配表(DAT)。
另一方面，如果確定(604)寫入操作不是針對指定的地址空間，那麼執行(620)寫入操作。此外，識別(622)已被寫入的簇，以使得可將一個或一個以上所識別的簇的狀態設定為「分配」。將了解，這一操作確保當寫入操作在非指定的地址空間中執行時，將代表所識別的簇的DAT的條目設定為「分配」。在將DAT中代表的簇的狀態設定(624)為「分配」時，可確定(602)是否接收到了對寫入操作的請求。
如上所述，數據屬性存儲(DAS)可(例如)用來執行維護操作。為了進一步說明，圖7描繪根據本發明一個實施例的示範性垃圾收集方法700。將了解，所述垃圾收集方法700利用數據分配表(DAT)，以便在更新操作期間實現更好的區塊更新。首先，當起初確定(702)將關閉一更新區塊時，確定是否所述更新區塊的所有扇區均已被寫入。如果所述更新區塊的所有邏輯區塊均已被寫入，那麼更新區塊便可有效地替換初始區塊。相應地，將更新區塊標記(706)為初始區塊，且將先前的初始區塊擦除(708)以使得其以後可被使用。
另一方面，如果確定(702)所述更新區塊的所有扇區均未被寫入，那麼識別(710)對應於未寫入扇區的邏輯扇區。隨後，將所識別(710)的邏輯扇區映射(712)到簇。在數據分配表(DAT)中查找(714)簇。相應地，確定716是否DAT指示所有識別(710)的簇均已解除分配。如果DAT指示所有簇均已被解除分配，那麼將更新區塊標記(706)為初始的，且將舊區塊擦除(708)。
應注意，當DAT指示(716)所有簇均已被解除分配時，不拷貝一個或一個以上簇。只有當DAT表指示一個或一個以上簇仍被分配時，才將保持被分配的數據拷貝(718)到更新區塊。在任何情況下，應注意到，可立即關閉更新區塊，或者以後在所述區塊裝滿時關閉。可將更新區塊作標記706且擦除708先前的初始區塊(舊區塊)，但避免了對未分配的數據的不必要拷貝。擦除(708)之後，垃圾收集方法700結束。
將了解，可使用快閃記憶體存儲器來實施根據本發明一個實施例的數據屬性存儲(DAS)。為了進一步說明，圖8描繪根據本發明一個實施例的數據分配表(DAT)800。使用存儲器部分801來實施數據分配表(DAT)800。存儲器部分801可以是可作為擦除單位的區塊。存儲器部分801大於表示數據分配表(DAT)800所需的存儲器。每個區段可位於一個或一個以上頁面中，其中頁面是編程存儲器的最小單位。
如圖8所示，可將數據屬性存儲(DAS)800分成複數個區段，即初始區段DAS1(802)、DAS2(804)、DAS3(806)和DAS4(808)，其最初寫入在存儲器部分801的開始處。這些初始區段中的每一者可代表複數個由主機用來以邏輯形式組織數據的簇。當需要更新與一簇相關聯的數據屬性時，可通過為數據屬性存儲(DAS)800的合適初始區段寫入更新區段來更新數據屬性存儲(DAS)800的相應區段。在最後的初始區段(即DAS4(808))之後寫入此更新區段。舉例而言，通過寫入新區段816來更新初始DAS3(806)。同樣，當需要更新初始DAS1(802)時，可寫入新區段812。寫入新區段818以代表初始DAS4(818)，等等。
此外，可使用索引方案來維護數據分配表(DAT)800。如圖8所示，存儲器的每個區段包含索引部分(Ii-U)。最後條目(806)的此索引部分參考數據屬性存儲(DAS)800的當前區段。這意味著，索引820、830、840和850分別指向數據屬性存儲(DAS)800的第一、第二、第三和第四當前區段(DAS1、DAS2、DAS3、DAS4)。(例如)當存儲器801基本上裝滿以使得當前區段(DAS1、DAS2、DAS3、DAS4)被重新產生為初始區段時，可對存儲器部分801進行垃圾收集。
還應注意到，可實施本發明以使得數據屬性存儲(DAS)的使用是任意的。數據屬性存儲(DAS)的使用可(例如)依賴於系統順應性，系統順應性由驗證過程確定以確保主機的實際數據邏輯結構遵守特定操作環境(例如DOS)的既定數據結構。或者，可通過由主機傳輸一命令來啟用數據屬性存儲(DAS)的使用，所述命令傳輸指示其順應特定操作環境的數據結構。應注意到，數據分配表(DAT)不必在被分配的簇剛被解除分配時就立刻改變簇(或簇內的扇區)的狀態。換句話說，當簇已解除分配時認為其仍是被分配的，這並不會造成嚴重問題。由此，可等待一段時間再將分配狀態設定為被解除分配的。將了解，同時針對一簇群組將分配狀態設定為被解除分配的，而不是在不同時間一個接一個地設定，可進一步增強系統性能。另一方面，所屬領域的技術人員將了解，有效的、被分配的簇的狀態信息應當一直是極為準確的且現時的(即，被分配的簇應當一直被標記為被分配的)。為了確保被分配的簇被正確標記，每當主機向簇寫入數據時，可自動地將簇的分配狀態設定為被分配的。此外，將了解到，數據分配表(DAT)中的信息可與映射表中的信息同時更新以記錄最近寫入的扇區或簇，所述映射表定義物理存儲器區塊對於數據邏輯區塊的分配。
此外，將了解到，數據屬性存儲(DAS)可用於其它許多維護操作。舉例而言，當數據屬性存儲(DAS)指示對應於一區塊的所有簇均已被解除分配時，可擦除所述區塊。這一擦除可(例如)作為背景來執行以進一步增強性能。
在另一實施例中，可使用由主機存儲在非易失性存儲器中的信息來確定應當怎樣存儲從主機接收到的數據。在一個實例中，可使用由主機存儲在FAT和目錄中的信息來確定應當以順序性方式還是以非順序性(混亂)方式來存儲數據。
某些存儲器系統根據從主機接收到的數據是順序性的還是非順序性的而使用不同的存儲方案來存儲所述數據。舉例來說，2003年12月30日申請的標題為「Non-volatilememory and method with block management system」的且全文以引用的方式併入本文中的第10/750,155號美國專利申請案描述了某些用於處理由主機以非順序性方式發送的數據的技術。確切地說，可向順序性更新區塊指派順序性更新，而可向可能以任意次序存儲數據的混亂更新區塊指派非順序性更新。雖然將數據存儲在混亂的更新區塊中對某些類型的數據更新提供了優勢，但其可能會對其它類型的數據更新造成無效。出於這一原因，第10/750,155號申請案描述了用於以滿足預定標準的順序性方式存儲某些以非順序性方式接收的數據的技術。在本發明一實施例中，可通過分析由主機存儲在非易失性存儲器中的信息來確定用於確定在以非順序性方式接收數據時將數據以順序性方式還是非順序性方式寫入非易失性存儲器中的標準。2003年12月30日申請的標題為「Managementof non-volatile memory systems having large erase blocks」的且全文以引用的方式併入本文中的第10/749,831號美國專利申請案描述了管理由主機發送以供存儲在非易失性存儲器陣列中的數據的額外方法。確切地說，描述了用於管理由主機以非順序性方式更新的數據的方法。可根據預定標準而對數據使用不同的指定區塊。
在本發明一實施例中，可將主機正寫入的數據部分(例如扇區)的邏輯地址與FAT、根目錄或子目錄(或存儲在非易失性存儲器中的類似主機數據)進行比較，或可將其與例如存儲在DAS中的信息的導出信息進行比較，以確定正被寫入的數據部分是否在下一空閒簇中具有邏輯地址。如果數據部分在下一空閒簇中具有地址，那麼這表明主機正在下一可用位置處存儲新數據。在諸如此類的存儲形式中，以順序性方式存儲數據並通過拷貝已存儲在非易失性存儲器中的數據來填充更新區塊中的任何間隙，而不是以非順序性次序存儲數據且稍後再將其拷貝到其順序性存儲的位置，這可能是有利的。
圖9A展示FAT表900的實例。每個簇0-8均在FAT表中具有指示文件中下一簇的條目。因此，簇0的條目為「1」，這指示這一文件的下一簇在簇1中。簇1中的條目為「5」，這指示下一簇為簇5。簇5中的條目為「6」，這指示下一簇為簇6。簇6中的條目為「EOF」，這指示「文件結尾(End of File)」，或指示不再有任何簇含有這一文件的數據。另一文件以類似方式存儲在簇3和4中。簇4、7和8被指示為「空閒」或未被分配的。這可能是主機進行解除分配的結果，例如在使文件廢棄的情況下。應注意，主機解除分配並不一定意味著數據在非易失性存儲器中被擦除，而只是使得用來存儲文件的邏輯地址範圍可用於存儲新數據。廢棄數據可保持物理性存儲在非易失性存儲器中，直到稍後某一時間為止。也可將含有廢棄控制信息的簇解除分配。也由主機存儲在非易失性存儲器中的根目錄或子目錄可指示文件的第一簇。
圖9B展示從FAT 900導出的DAT 910，連同包含在根目錄和子目錄中的信息。DAT910含有針對每個簇的條目，其指示所述簇是被分配的還是空閒的。也可如先前所述那樣將額外數據存儲在DAT 910中。可維護一DAT，以使得存儲在DAT中的信息比FAT和子目錄中的信息更現時。一旦主機發送新的數據以供存儲便可更新DAT，然後主機才寫入更新的FAT或目錄信息。同樣，可對DAS中的其它信息進行維護以使得其是現時的。
圖9C展示針對FAT 900的一部分邏輯地址範圍的扇區與簇之間的對應。在此實例中，簇具有四個數據扇區。也可使用具有不同數目的扇區的簇。簇通常含有4個到64個扇區。簇4具有扇區X、扇區X+1、扇區X+2和扇區X+3。雖然主機對一系列邏輯地址的分配大體上是在逐個簇的基礎上進行的，但存儲器控制器大體上在扇區中處理數據。一般來說，將簇分配為單個單位，以使得即便簇的整個邏輯地址範圍均未用於存儲數據，仍使得簇的整個邏輯地址範圍不可用於稍後存儲其它數據。圖9C將來自被分配的簇5和6的扇區展示為陰影的，以指示這些邏輯地址不可被主機用來存儲數據。
圖9D和9E展示用於存儲以非順序性方式從主機接收的數據的兩種替代方案。這兩張圖均展示正從主機接收扇區X到X+3和X+12到X+15以存儲在非易失性存儲器中。這些扇區對應於圖9C中的簇4和7。在圖9D中，所接收到的數據被寫入混亂的更新區塊920。這一區塊之所以是混亂的，是因為扇區X+12直接寫在扇區X+3後面，以使得從扇區X+3到扇區X+12的邏輯地址範圍中存在跳躍。起初，當混亂區塊920含有扇區X到X+3時，其可能是順序性更新區塊，隨後，當存儲了扇區X+12時，其轉換為混亂的更新區塊。一般來說，在主機以非順序性方式發送數據的情況下，將使用混亂(非順序性)區塊。圖9D的混亂區塊920中的有效數據最終被重新定位到順序性區塊922，在所述區塊922中其與扇區X+4到X+11一起存儲，所述扇區X+4到X+11可能是從另一位置拷貝來的。這大體上作為合併操作的一部分來進行。對於長期存儲而言順序性區塊一般是優選的，因為扇區是以預定方式配置的，且因此可能不需要在區塊內索引扇區。在混亂區塊920中的所有有效數據均被拷貝到另一位置之後，可將混亂區塊920標記為廢棄的，且可將其擦除。
圖9E展示在順序性區塊930中正以順序性方式更新非順序性數據——扇區X到X+3和X+12到X+15。可首先寫入扇區X到X+3，以使得區塊930在此點處為順序性區塊。當接收到扇區X+12時，可作出以順序性方式存儲數據的確定，即使所述數據是以非順序性方式接收到的。可通過從初始區塊拷貝扇區X+4到X+11(對應於簇5和6)來填充從主機接收的扇區之間的邏輯地址範圍來實現順序性存儲。可將扇區X+4到X+11視為填補扇區，因為其是用來填充或「填補」主機發送的扇區中的間隙的。扇區X+4到X+11是從另一位置拷貝的有效數據扇區。以此方式，所接收到的扇區被存儲在順序性區塊930中，而不經過混亂區塊中的中間存儲階段。因此，這兩種技術之間的主要區別在於，在圖9E的實例中，不必先將扇區X到X+3和X+12到X+15寫入混亂區塊920且稍後再擦除混亂區塊920。在此實例中，寫入扇區X到X+3和X+12到X+15一次，且仍然拷貝扇區X+4到X+12。這需要的扇區寫入少了八次，且擦除操作少了一次，因而改進了數據存儲的效率。
可基於多種標準來確定是以順序性方式還是以非順序性方式來存儲以非順序性方式接收的數據。某些數據更適合非順序性存儲，特別是很可能很快要再次更新的數據。舉例來說，可在混亂區塊中更加高效地存儲控制數據或主機數據中的頻繁更新的部分。某些數據更適合順序性存儲，特別是在數據不太可能很快被再次更新的情況下。雖然以非順序性方式接收的數據可能一般會以非順序性方式來存儲，但在某些情況下將其以順序性方式寫入是有利的。因為避免了在混亂區塊中的中間存儲，所以無需對混亂區塊進行垃圾收集以使數據具有順序性格式。這避免了圖9D中所示的合併操作，且因此減少了額外開銷並改進了性能。當主機寫入下一空閒簇時，指示主機只是在下一可用位置處寫入新數據，且一般並不指示將很快再次更新邏輯地址範圍。因此，選擇例如圖9E中所展示的順序性更新方案比選擇例如圖9D中所展示的混亂更新方案更有效率。因此，可根據數據是否來自下一空閒簇來確定使用的存儲方案。當數據來自下一空閒簇(如在圖9E中)時，可選擇順序性存儲。因此，在此實例中，將不會為此數據選擇圖9D的存儲方案。
圖10是展示根據本發明一實施例的存儲方案的選擇的流程圖。當從主機接收到非順序性數據時，控制器確定所述數據是否來自下一空閒簇10。可通過直接查看由主機存儲在非易失性存儲器中的FAT和目錄信息或者通過查看從FAT和目錄信息導出的信息(例如，存儲在DAS或DAT中的信息)來進行這一確定。如果當前定址的簇並不是下一空閒簇，那麼根據默認方案12以普通方式來存儲數據。這可能意味著以非順序性方式來存儲數據，或在某些實例中，可能存在其它使得數據被以順序性方式寫入的標準。如果當前定址的簇是下一空閒簇，那麼選擇順序性寫入。在此實例中，將有效的數據簇從初始元區塊拷貝到當前順序性元區塊14以填補最後寫入的簇與當前定址的簇之間的邏輯地址間隙。接著，將來自當前定址的簇的接收到的數據寫入當前順序性元區塊。因此，當前元區塊16保持順序性。
圖11是展示在一個實施例中為從主機接收到的扇區選擇存儲方案的流程圖。第10/750,155號申請案中展示了類似的存儲方案選擇流程圖。如果存在開放的更新區塊20，更新區塊是順序性的22，且扇區與更新區塊中的最後扇區成順序性的24，那麼將所述扇區寫入26所述更新區塊。如果扇區不是與更新區塊中的最後扇區成順序性的，那麼確定是否應當執行強制性順序性寫入27。如果從更新區塊中的最後扇區到所接收到的扇區的地址跳躍不大於預定量(CB)28，那麼可用拷貝的扇區來填補最後扇區與接收到的扇區之間的間隙30，以將更新區塊維持為順序性區塊(如先前所述)。如果更新區塊中的未填充的物理區塊的數目不大於預定量(CC)32，那麼可將所述更新區塊關閉34，以將其維持為順序性區塊且可分配新的更新區塊36(如先前描述)。導致強制性順序性寫入的第三種情形是在主機正寫入到下一可用簇時40。當發生此類寫入時，用從非易失性存儲器中的其它地方拷貝來的扇區填補接收到的扇區與更新區塊中最後扇區之間的間隙30，以使得更新區塊可被維持為順序性區塊。如果沒有滿足這些用於以順序性形式寫入數據的標準中的任何一者，那麼可將更新區塊轉換成混亂更新區塊42。因此，用於選擇存儲方案的選擇標準可包含從由主機存儲在非易失性存儲器中的數據導出的屬性。
圖12A展示存儲器系統以非順序性方式從主機接收數據的實例，所述存儲器系統將所述數據以順序性方式存儲在更新區塊50中。接收到簇2的扇區A，且隨後接收到簇7的扇區B。當接收到扇區A時，其可能是更新區塊50的最初幾個扇區，且如果更新區塊50隻含有扇區A的話，其被認為是順序性的。或者，如圖12A所示，更新區塊50可能是順序性的，因為扇區A是與先前存儲在更新區塊50中的扇區成順序性地存儲的。假設更新區塊50在接收扇區B之前是順序性的，那麼在接收到扇區B時確定是將更新區塊50維持為順序性更新區塊還是將扇區B直接存儲在寫入到更新區塊50的最後扇區(扇區A)後面且從而將更新區塊50轉換成混亂區塊。在此實例中，簇7是扇區A之後的下一空閒簇。因此，當接收到來自簇7的扇區B時，發生強制性順序性寫入，且若干扇區被拷貝到更新區塊50以填充扇區A與扇區B之間的間隙。因此，在圖12A的更新區塊50中，數據是以順序性方式存儲的。
圖12B展示存儲器系統以非順序性方式從主機接收數據的實例，所述存儲器系統將所述數據以非順序性方式存儲在更新區塊52中。首先如圖12A一樣接收到扇區A。扇區A是以順序性方式存儲的，以使得當編程扇區A時，更新區塊52是順序性的。接著，接收到扇區X。扇區X並未被寫入下一空閒簇。扇區X被寫入被分配的簇，且因此不導致執行強制性的順序性寫入。可以非順序性方式寫入扇區X，或如果存在其它某一順序性寫入的原因(例如扇區X與扇區S之間的邏輯間隙小於閾值)，那麼可以順序性方式寫入扇區X。此處，扇區X被展示為寫入到更新區塊52中的下一可用空間。因此，更新區塊52變成混亂的。在圖12C中的第二實例中，扇區Y是在扇區A之後接收到的。在接收到扇區Y之前，更新區塊54是順序性的。扇區Y不是來自下一空閒簇，因為在更新區塊中最後寫入的扇區(扇區A)與扇區Y之間存在空閒簇(簇7)。因此，扇區Y並不導致強制性的順序性寫入，且其可被寫入到更新區塊54而不進行填補，從而導致更新區塊54變成混亂的。在圖12D所示的第三實例中，扇區Z是在扇區A之後接收到的。更新區塊56在接收到扇區Z之前是順序性的。扇區Z來自簇0且因此其並非來自下一空閒簇，因為簇0在簇2前面，且因而，按照圖中所示的次序，簇0不是下一空閒簇。因此，扇區Z可直接寫入在簇A後面，從而導致更新區塊56變成混亂的。
本發明有多種優點。不同的實施例或實施方案可能會產生以下優點中的一種或一種以上。應注意到，這並不是詳盡的列舉，而可能會存在本文中未描述的其它優點。本發明的一個優點在於可改進非易失性存儲器系統的性能。本發明的另一優點在於可使用廣泛使用的常規做法來實施本發明。本發明的又一優點在於其可在快閃記憶體存儲器中實施為相對較小的屬性表。在其它實施方案中，沒有一個表是必需的。再一優點在於本發明可實施成適於任意用途和/或適於在後臺維護操作期間使用。
可單獨使用或以各種組合形式使用本發明的上述各方面或特徵。本發明還可通過硬體或硬體與軟體的組合來實施。本發明還可作為計算機可讀代碼而在計算機可讀媒體上實施。所述計算機可讀媒體是任何可存儲數據的數據存儲裝置，所述數據之後可被計算機系統讀取。計算機可讀媒體的實例包含只讀存儲器、隨機存取存儲器、CD-ROM、DVD、磁帶、光學數據存儲裝置和載波。計算機可讀媒體也可分布在網絡耦合的計算機系統上，以使得以分布方式來存儲和執行計算機可讀代碼。
從所述書面描述中容易了解本發明的許多特徵和優點，且因此希望所附權利要求書覆蓋本發明的所有這些特徵和優點。此外，由於所屬領域的技術人員容易了解多種修改和變化，因而不希望將本發明限制於所說明和描述的確切構造和操作。因此，所有適合的修改和均等物均可歸入本發明的範圍內。
權利要求
1.一種以一適應性方式將若干部分的數據存儲在一存儲器系統中的方法，所述存儲器系統包含一控制器和一非易失性存儲器陣列，所述方法包括所述控制器從一主機存儲在所述非易失性存儲器陣列中的一文件分配表或目錄中的信息中獲得一邏輯地址範圍的一屬性；所述控制器根據所述邏輯地址範圍的所述屬性從複數個存儲方案中為具有所述邏輯地址範圍內的一邏輯地址的一部分數據選擇一存儲方案；和所述控制器根據所述選擇的存儲方案來存儲所述部分的數據。
2.根據權利要求1所述的方法，其中所述邏輯地址範圍的所述屬性在於所述邏輯地址範圍是用於存儲主機數據的下一空閒邏輯地址範圍。
3.根據權利要求2所述的方法，其中所述選擇的存儲方案包含將所述部分的數據存儲在一順序性更新區塊中。
4.根據權利要求1所述的方法，其中所述邏輯地址範圍的所述屬性在於所述邏輯地址範圍不是用於存儲主機數據的下一空閒邏輯地址範圍。
5.根據權利要求4所述的方法，其中所述選擇的存儲方案包含將所述部分的數據存儲在一混亂更新區塊中。
6.根據權利要求1所述的方法，其中所述部分的數據先前存儲在所述非易失性存儲器陣列中的一第一位置處，所述邏輯地址範圍的所述屬性在於所述邏輯地址範圍由所述主機分配，且所述選擇的存儲方案包含將所述部分的數據從所述非易失性存儲器陣列中的所述第一位置拷貝到一第二位置。
7.根據權利要求6所述的方法，其中所述部分的數據先前存儲在所述非易失性存儲器陣列中的一第一位置處，所述邏輯地址範圍的所述屬性在於所述邏輯地址範圍由所述主機解除分配，且所述選擇的存儲方案將所述部分的數據維持在所述第一位置處，而不將所述部分的數據從所述第一位置拷貝到一第二位置。
8.根據權利要求1所述的方法，其中從一數據屬性存儲中獲得所述屬性，而所述數據屬性存儲是從所述文件分配表或目錄中導出的。
9.一種將從一主機接收的數據存儲在一非易失性存儲器陣列中的方法，其包括從所述主機接收一個或一個以上可定址的數據單位，分析由所述主機存儲在所述非易失性存儲器陣列中的信息，以識別複數個可由所述主機用來存儲數據的邏輯地址範圍；將所述複數個所述主機可使用的邏輯地址範圍與所述一個或一個以上可定址的數據單位的邏輯地址進行比較，以確定所述一個或一個以上可定址的數據單位是否被分配給所述主機可使用的下一邏輯地址範圍；和以一依賴於所述確定的方式來存儲所述一個或一個以上可定址的數據單位。
10.根據權利要求9所述的方法，其中如果所述一個或一個以上可定址的單位被指派給接下來的可用順序性位置，那麼所述存儲所述一個或一個以上可定址單位的方式為一順序性方式，且如果所述一個或一個以上可定址的單位不被指派給接下來的可用順序性位置，那麼所述存儲方式是一非順序性方式。
11.根據權利要求9所述的方法，其中存儲所述一個或一個以上可定址的數據單位是以一依賴於額外因素的方式進行，所述額外因素包含所述一個或一個以上可定址的數據單位的所述邏輯地址與所述最後寫入的可定址數據單位的所述邏輯地址之間的一邏輯地址間隙是否超出一預定量。
12.根據權利要求11所述的方法，其中一額外因素是用於存儲所述一個或一個以上可定址數據單位的一更新區塊是否含有超過一預定量的一順序性形式的數據。
13.一種用於在非易失性存儲器中存儲數據的存儲器裝置，所述數據是以可定址的數據單位從一主機接收的，所述存儲器裝置包括一非易失性存儲器陣列，其含有一主機文件分配表的一拷貝；和一存儲器控制器，其與所述非易失性存儲器陣列通信，所述存儲器控制器監視所述主機文件分配表的所述拷貝的內容，所述存儲器控制器根據所述主機文件分配表的所述拷貝確定一部分邏輯地址空間的一分配狀態，且所述存儲器控制器響應於所述分配狀態為具有所述部分的邏輯地址空間內的一邏輯地址的一可定址數據單位選擇一數據管理方案。
14.根據權利要求13所述的存儲器裝置，其中所述存儲器裝置形成一可移除地連接到一控制器的可移除存儲卡的一部分。
15.根據權利要求13所述的存儲器裝置，其中所述存儲器控制器在一數據屬性存儲中記錄所述部分的邏輯地址空間的所述分配狀態。
16.根據權利要求13所述的存儲器裝置，其中從一主機處接收所述可定址的數據單位以供存儲在所述非易失性存儲器陣列中，所述數據管理方案包括在所述部分的邏輯地址空間是下一空閒部分時在一順序性區塊中存儲，且所述數據管理方案包括在所述部分的邏輯地址空間不是下一空閒部分時在一混亂區塊中存儲。
17.根據權利要求13所述的存儲器裝置，其中當所述存儲器裝置進行一垃圾收集操作時，所述可定址的數據單位被存儲在所述非易失性存儲器陣列中的一第一位置中，所述數據管理方案是在所述部分的邏輯地址空間被分配時將所述可定址的數據單位拷貝到所述非易失性存儲器陣列中的一第二位置，且所述數據管理方案是在所述部分的邏輯地址空間未被分配時將所述可定址的數據單位維持在所述第一位置中而不進行拷貝。
18.一種包含程序代碼的計算機可讀媒體，所述程序代碼用於在一存儲器控制器可用來在一非易失性存儲器中存儲主機數據的多個替代性存儲方案之間進行選擇，所述計算機可讀媒體包括用於識別的電腦程式代碼，其根據一主機存儲在所述非易失性存儲器中的信息來識別複數個部分的邏輯地址空間的一分配狀態，並將所述分配狀態提供給所述存儲器控制器；和用於選擇的電腦程式代碼，其根據包含所述部分的數據的邏輯地址的一部分邏輯地址空間的一分配狀態為一部分主機數據選擇一數據管理方案。
19.根據權利要求18所述的計算機可讀媒體，其進一步包括電腦程式代碼，所述電腦程式代碼根據所述選擇的管理方案對所述部分的主機數據進行操作，以在所述部分的邏輯地址空間是未被分配的下一部分的邏輯地址空間時將所述部分的數據存儲在一順序性區塊中，且否則將所述部分的數據存儲在一混亂區塊中。
20.根據權利要求18所述的計算機可讀媒體，其進一步包括電腦程式代碼，所述電腦程式代碼根據所述選擇的管理方案對所述部分的主機數據進行操作，以在所述部分的邏輯地址空間被分配時將所述部分的數據從一舊位置拷貝到一新位置，且在所述部分的邏輯地址空間未被分配時將所述部分的數據保留在所述舊位置中而不拷貝到一新位置。
21.根據權利要求18所述的計算機可讀媒體，其進一步包括電腦程式代碼，所述電腦程式代碼提供一含有所述複數個部分的邏輯地址空間的所述分配狀態的數據屬性存儲。
全文摘要
本發明揭示用於管理一非易失性存儲器系統(例如，快閃記憶體存儲器)中的數據的技術。一控制器可使用由一主機存儲在非易失性存儲器上的與所述主機有關的文件系統的信息來確定一個或一個以上簇(或具有簇的扇區)當前是否被分配。所述控制器可使用所述與所述主機的文件系統有關的信息來識別所述主機何時向下一空閒簇發送數據並通過從所述非易失性存儲器中的其它位置拷貝數據來以一順序格式存儲所述數據。
文檔編號G06F12/02GK101027651SQ200580030163
公開日2007年8月29日 申請日期2005年6月17日 優先權日2004年7月21日
發明者凱文·M·康利, 艾倫·韋爾什·辛克萊, 彼得·約翰·史密斯 申請人:桑迪士克股份有限公司