TWI417720B - 快閃記憶體管理方法與計算機系統 - Google Patents

Description

快閃記憶體管理方法與計算機系統

本發明係關於一種記憶體裝置之管理方法，特別關於一種可優化快閃記憶體裝置之讀寫操作性能之方法。

快閃記憶體(flash memory)為一種特殊種類的非揮發性(nonvolatile)記憶體，其可儲存資料以及被電性抹除。以快閃記憶體為基礎之儲存裝置具有低功率耗損，並且與以磁碟記憶體為基礎的儲存裝置相比，具有相對小的尺寸。因此，快閃記憶體裝置目前為一些手持電子計算裝置中經常被使用的記憶體裝置，例如數位相機、手機或個人數位助理(personal digital assistants，PDA)等。

在磁碟記憶體裝置中，新的資料可覆寫舊的資料。然而，在快閃記憶體裝置中，若要更新先前儲存的資料，必須先將一區塊(block)範圍進行抹除，即，快閃記憶體裝置的讀取與寫入操作的單位可以是以頁(page)或區段(sector)為基礎，而抹除操作的最小單位為區塊。因此，抹除操作通常比寫入與讀取操作需要更多的時間。此外，由於區塊的大小遠大於頁與區段，即使區塊內不需被寫入的部分也要同時被抹除。

傳統技術中改善讀寫操作性能的方法為透過介質管理層，使用映射的方式，當需要修改某一區塊內儲存的資料時，在系統內取得另一個可用區塊(通常稱此區塊為log區塊)，用以儲存該區塊之修改紀錄，如此一來，每當需要修改該區塊之資料時，僅需將修改資料儲存至該區塊對應的log區塊，即可避免必須抹除一整個區塊的寫入操作。然而，在讀取操作時，為了尋找到最近被更新的資料內容，必須自log區塊的末端倒序地遍曆(visit)log區塊內所儲存的資料，這樣一來，增加了許多不必要的資料讀取操作，更降低了讀取的速度。

因此，需要一種新的快閃記憶體管理方法，可優化快閃記憶體裝置之讀寫操作性能，使得記憶體裝置之讀寫操作速度可大幅地被提升。

根據本發明之一實施例，一種快閃記憶體管理方法，用以管理一快閃記憶體裝置，其中該快閃記憶體裝置配置至少一映射區塊、至少一修改區塊以及至少一快取區塊，包括：接收包含一寫入邏輯位址與一既定資料之一寫入指令，用以寫入該既定資料至該快閃記憶體裝置；以及判斷對應於該寫入邏輯位址之該映射區塊之一頁是否已經被使用。其中當對應於該寫入邏輯位址之該映射區塊之該頁已經被使用，則寫入該既定資料於該修改區塊之一空白頁，包括：根據該寫入邏輯位址由該快取區塊讀取對應於該修改區塊之一快取頁至一隨機存取記憶體裝置，於該隨機存取記憶體裝置內依序讀取該快取頁之資料欄位以獲得該空白頁於該修改區塊內之位置資訊，其中該快取區塊之各快取頁具有複數資料欄位用以依序儲存該修改區塊之各非空白頁所寫入之資料所對應之該位置資訊；以及依據該位置資訊寫入該既定資料於該修改區塊之該空白頁。

根據本發明之另一實施例，一種快閃記憶體管理方 法，用以管理一快閃記憶體裝置，其中該快閃記憶體裝置配置至少一映射區塊、至少一修改區塊以及至少一快取區塊，包括：接收包含一讀取邏輯位址之一讀取指令用以由該快閃記憶體裝置之一頁讀取一既定資料；以及判斷對應於該讀取邏輯位址之該映射區塊之一頁是否已經被使用。其中當對應於該讀取邏輯位址之該映射區塊之頁的資料已經被修改過，則於對應於該映射區塊之該修改區塊中讀取該既定資料，包括：根據該讀取邏輯位址由該快取區塊讀取對應於該修改區塊之一快取頁至一隨機存取記憶體裝置，於該隨機存取記憶體裝置內依序讀取該快取頁之資料欄位以獲得對應於該讀取邏輯位址之頁於該修改區塊內之一位置資訊，其中該快取區塊之各快取頁具有複數資料欄位用以依序儲存該修改區塊之各非空白頁所寫入之資料所對應之該位置資訊；以及依據該位置資訊於該修改區塊之該頁讀取該既定資料。

根據本發明之另一實施例，一種計算機系統，包括一快閃記憶體、一隨機存取記憶體裝置以及一處理器。快閃記憶體配置至少一映射區塊、至少一修改區塊以及至少一快取區塊。處理器耦接至該快閃記憶體與該隨機存取記憶體裝置，接收包含一寫入邏輯位址與既定資料之一寫入指令，當對應於該寫入邏輯位址之該映射區塊之一頁已經被使用，則根據該寫入邏輯位址由該快取區塊讀取對應於該修改區塊之一快取頁至該隨機存取記憶體裝置，並於該隨機存取記憶體裝置內依序讀取該快取頁之內容以獲得該修改區塊內之一空白頁之位置資訊，以及依據該位置資訊 寫入該既定資料於該修改區塊之該空白頁，其中該快取區塊之各快取頁具有複數資料欄位用以依序儲存該修改區塊之各非空白頁所寫入之資料所對應之該位置資訊。

根據本發明之另一實施例，一種計算機系統，包括一快閃記憶體、一隨機存取記憶體裝置以及一處理器。快閃記憶體配置至少一映射區塊、至少一修改區塊以及至少一快取區塊。處理器耦接至該快閃記憶體與該隨機存取記憶體裝置，接收包含一讀取邏輯位址之一讀取指令，當對應於該讀取邏輯位址之該映射區塊之一頁的資料已經被修改過，則根據該讀取邏輯位址由該快取區塊讀取對應於該修改區塊之一快取頁至該隨機存取記憶體裝置，並於該隨機存取記憶體裝置內依序讀取該快取頁之內容以獲得對應於該讀取邏輯位址之該頁於該修改區塊內之一位置資訊，以及依據該位置資訊於該修改區塊之該頁讀取該既定資料，其中該快取區塊之各快取頁具有複數資料欄位用以依序儲存該修改區塊之各非空白頁所寫入之資料所對應之該位置資訊。

根據本發明之另一實施例，一種快閃記憶體管理方法，用以管理一快閃記憶體裝置，其中該快閃記憶體裝置配置至少一映射區塊、至少一修改區塊以及至少一快取區塊。快閃記憶體管理方法包括：接收一包含一邏輯位址之存取指令，用以於該快閃記憶體裝置存取一既定資料；以及當對應於該邏輯位址之該映射區塊之一頁不適於存取該既定資料，則對與該映射區塊對應之該修改區塊進行存取操作，包括：由該快閃記憶體裝置之該快取區塊讀取對應 於該修改區塊之一快取頁至一隨機存取記憶體裝置，於該隨機存取記憶體裝置內依序讀取該快取頁之內容以獲得該既定資料於該修改區塊內之存取位置資訊，其中該快取區塊之各快取頁具有複數資料欄位用以依序儲存該修改區塊之各非空白頁所寫入之資料所對應之該位置資訊；以及依據該存取位置資訊與該快閃記憶體裝置之修改區塊內存取該既定資料。

為使本發明之製造、操作方法、目標和優點能更明顯易懂，下文特舉幾個較佳實施例，並配合所附圖式，作詳細說明如下：

實施例：

第1圖係顯示根據本發明之一實施例所述之計算機系統100，包括快閃記憶體101、處理器102以及隨機存取記憶體裝置103。處理器102根據接收到的指令以及藉由執行既定之程式碼管理快閃記憶體101。根據本發明之一實施例，快閃記憶體101可以是具有一次可抹除資料之最小單位大於一次可寫入資料之最小單位之特性之一種記憶體裝置，例如NAND型或NOR型快閃記憶體。快閃記憶體101可被配置至少一映射區塊、修改區塊以及快取區塊，其中對於NAND型快閃記憶體而言，映射區塊、修改區塊以及快取區塊可分別包括複數頁(page)，而對於NOR型快閃記憶體而言，映射區塊、修改區塊以及快取區塊可分別包括複數區段(sector)。為了簡潔起見，本說明書將統一使用「頁」進行相關的描述，然而值得注意的是，其並非用以限定本發明的範圍，任何熟習此項技藝者，在不脫離本發明之精神和範圍內，當可做些許的更動與潤飾，用以將本發明之精神應用同時於各種快閃記憶體。

根據本發明之一實施例，映射區塊之各頁用以儲存原始資料，並且映射區塊可具有至少一對應之修改區塊，用以當原始資料需被更改時，於該修改區塊之各頁儲存原始資料之更新內容，並且各修改區塊可對應於至少一快取區塊之一頁，用以儲存修改區塊所寫入之資料之位置資訊。第2圖係顯示根據本發明之一實施例所述之快閃記憶體之資料結構示意圖。如圖所示，快閃記憶體200可被配置複數個快取區塊201、複數個映射區塊202以及複數個修改區塊203。快取區塊201之各頁分別包括一資料區域與一冗餘區域，資料區域可包含複數資料欄位，用以依照對應之修改區塊之頁順序儲存修改區塊的各非空白頁之位置資訊。以256百萬位元組(MB)之快閃記憶體為例，可配置2048個區塊，各區塊大小為128KB，並且各區塊可包含256頁(或區段)，各頁之資料區域大小為512位元組(byte)，並具有對應之16byte之冗餘區域。因此，根據本發明之一實施例，若各資料欄位使用2byte紀錄位置資訊，則快取區塊201 之各頁之資料區域可分成256個資料欄位，足以完整紀錄一修改區塊之各頁之所有位置資訊，而快取區塊201的冗餘區域則可用以紀錄該快取區塊201之一快取區塊索引，以及該快取區塊201所對應之修改區塊之物理區塊編號(以下將作詳細介紹)。此外，如第2圖所示，映射區塊202與修改區塊203也可分別包括一資料區域與一冗餘區域，其中映射區塊202與修改區塊203之冗餘區域用以儲存該頁之資料區域所寫入之資料所對應之邏輯區塊編號與邏輯頁編號(以下將作詳細介紹)。

根據本發明之一實施例，當寫入快閃記憶體101時，處理器102接收包含一寫入邏輯位址與既定資料之一寫入指令，並根據該寫入邏輯位址取得對應之一邏輯區塊編號LBN以及一邏輯頁編號LSN。例如，假設寫入邏輯位址為90，其中快閃記憶體101之一區塊包含8頁，並且一頁大小為10byte，則可得到邏輯區塊編號LBN為90除以80之商數，而邏輯頁編號LSN為90除以80之餘數再除以頁大小所得到的數值，即在此範例中，LBN=1，LSN=1，因此處理器102將接收到的既定資料存入第1個邏輯區塊之第1頁。處理器102進一步根據邏輯區塊編號LBN取得對應之一映射區塊，其中此映射區塊為快閃記憶體101中實際被配置之一物理區塊，用以儲存此邏輯區塊的原始資料。當處理器102判斷映射區塊中對應於此邏輯頁編號LSN之一頁尚未被寫入時，處理器102將既定資料寫入至該頁，並且當該頁已被寫入時，處理器102進一步取得對應於此映射區塊之一修改區塊，以及對應於此修改區塊之一快取區塊，處理器102將既定資料寫入至此修改區塊之一空白頁，並且將既定資料之邏輯頁編號LSN寫入至此快取區塊之一空白頁。

根據本發明之一實施例，處理器102更進一步在隨機存取記憶體裝置103內建立一邏輯至映射區塊對應表(第一資訊表)、一物理區塊資訊表(第二資訊表)以及一快取區塊索引表(第三資訊表)。第3圖係顯示根據本發明之一實施例所述之邏輯至映射區塊對應表300之資料結構示意圖。根據本發明之一實施例，邏輯至映射區塊對應表300依照邏輯區塊編號之順序依序儲存各邏輯區塊所對應之映射區塊之一物理區塊編號，例如，對應於邏輯區塊編號LBN=0之一邏輯區塊，其映射區塊之物理區塊編號為0x0002。第4圖係顯示根據本發明之一實施例所述之物理區塊資訊表400之資料結構示意圖。根據本發明之一實施例，物理區塊資訊表400依照物理區塊編號之順序依序儲存各物理區塊之狀態資訊與其連結資訊。例如，物理區塊編號為0之一物理區塊為一空閒區塊(FB)，即，尚未被使用之區塊，其連結資訊則儲存下一個空閒區塊之物理區塊編號。物理區塊編號為2之一物理區塊為一映射區塊(MpB)，其連結資訊則儲存對應之修改區塊之物理區塊編號(0x0003)。物理區塊編號為3之一物理區塊為一修改區塊(MoB)，其連結資訊則儲存對應之快取頁之一快取區塊索引，其中快取區塊索引可用以指示出對應於此修改區塊之快取區塊的位置以及頁資訊。例如，對於同樣包含8頁之快取區塊，快取區塊索引0x0011可指示出快取頁位於系統配置的第1個快取區塊(11除以8之商數)的第3頁(11除以8之餘數)。而物理區塊編號為6之一物理區塊為一快取區塊(CB)，其連結資訊則儲存此快取區塊之快取區塊編號。第5a圖係顯示根據本發明之一實施例所述之快取區塊索引表500之資料結構示意圖。快取區塊索引表500根據快取區塊編號依序紀錄該快取區塊之物理區塊編號與第一個空閒的快取頁(即，快取區塊的第一個空白頁)的頁編號。如圖所示，假設系統最大可配置4個快取區塊，並且各快取區塊可包含8頁，則快取區塊索引表500依序紀錄這4個快取區塊的物理區塊編號與第一個空白頁的編號。根據本發明之一實施例，當一個快取區塊的各頁都被使用過後，才會配置下一個快取區塊。如第5a圖所示，編號0的快取區塊已被存滿資料，因此目前使用中的快取區塊為編號1的快取區塊。

第6圖係顯示根據本發明之一實施例所述之快閃記憶體管理方法流程圖。如圖所示，處理器102首先接收包含一寫入邏輯位址與一既定資料之一寫入指令，用以寫入該既定資料至一快閃記憶體裝置之一頁(步驟S601)。接著，當該頁已寫入資料時，處理器102取得對應於包含該頁之一映射區塊之一修改區塊，以及配置對應於該修改區塊之一快取區塊(步驟S602)。最後，處理器102寫入該既定資料於該修改區塊之一空白頁，並且寫入包含該修改區塊之該頁之位置資訊於該快取區塊之一空白頁(步驟S603)。

第7a-7b圖係顯示根據本發明之一實施例所述之快閃記憶體之寫入操作之詳細流程圖。首先，處理器102根據接收到的寫入指令取得寫入邏輯位址所對應之邏輯區塊編號LBN與邏輯頁編號LSN(步驟S701)。接著，處理器102查詢邏輯至映射區塊對應表以取得映射區塊的物理區塊編號(步驟S702)。接著，處理器102檢查此映射區塊中對應於此邏輯頁編號LSN之一頁是否為空白頁(步驟S703)。若此頁為一空白頁，則處理器102將既定資料寫入此頁(步驟S704)。若此頁已存有資料，則處理器102依據物理區塊資訊表查詢映射區塊是否有對應的修改區塊(步驟S705)。若此映射區塊沒有對應的修改區塊，則處理器102為此映射區塊分配一修改區塊(步驟S706)。接著，處理器102將既定資料寫入此修改區塊的第一頁(步驟S707)，並且分配快取區塊之一頁給此修改區塊(步驟S708)，用以紀錄此既定資料之位置資訊(例如，邏輯頁編號LSN)，並且最後更新物理區塊資訊表(參考第4圖)與快取區塊索引表(參考第5a、5b圖)中映射區塊、修改區塊以及快取區塊的相關資訊(步驟S709)。

另一方面，若此映射區塊已有對應的修改區塊，則處理器102依據物理區塊資訊表中映射區塊的連結資訊取得修改區塊所對應的快取頁的快取區塊索引(步驟S710)。接著，處理器102再根據快取區塊索引查詢快取區塊索引表，以取得此快取頁所對應的快取區塊的物理區塊編號(步驟S711)。接著，處理器102將此快取頁的內容載入隨機存取記憶體裝置103(步驟S712)。接著，處理器102操作於隨機存取記憶體裝置103中，自快取頁之資料尾端倒序遍曆(visit)快取頁所儲存的資料，找出此快取頁的資料區域中，第一個未被使用的空白資料欄位的索引，以取得此快取頁所對應之修改區塊的第一個可使用之空白頁的位置(步驟S713)，並根據此位置資訊將既定資料寫入修改區塊所對應的空白頁(步驟S714)。接著，處理器102將此既定資料的位置資訊(例如，邏輯頁編號LSN)寫入至被載入隨機存取記憶體裝置103之快取頁的下一個空白欄位，並且將此被更新過的快取頁資料更新至快閃記憶體101內之快取區塊的下一個空白頁(步驟S715)。最後，處理器102更新物理區塊資訊表(參考第4圖)與快取區塊索引表(參考第5a、5b圖)中映射區塊、修改區塊以及快取區塊的相關資訊(步驟S716)。

第8a-8e圖係顯示根據本發明之一實施例所述之快閃記憶體之寫入操作之示意圖。值得注意的是，圖式中的虛線用以區隔分別位於快閃記憶體101與隨機存取記憶體裝置103之資料，其中虛線的右側用以顯示快閃記憶體101內的資料結構。如上述，假設處理器102接收到的寫入邏輯位址為90，其中寫入快閃記憶體101之一區塊包含8頁，並且一頁大小為10byte，則可得到邏輯區塊編號LBN為90除以80之商數，而邏輯頁編號LSN為90除以80之餘數再除以頁大小所得到的數值，即在此範例中，LBN=1，LSN=1，因此處理器102必須將接收到的既定資料存入第1個邏輯區塊之第1頁。接著，如第8a圖所示，處理器102根據邏輯區塊編號(LBN=1)查找邏輯至映射區塊對應表801中索引1的資料欄位內容，得到對應之映射區塊之物理區塊編號。其中，根據本發明之一實施例，若該資料欄位為空，代表此邏輯區塊尚未分配對應之映射區塊，處理器102可分配映射區塊給此邏輯區塊。若該資料欄位不為空，代表此邏輯區塊已分配有對應之映射區塊，例如，在此實施例中，對應之映射區塊之物理區塊編號為3，代表此映射區塊實際配置為第3個物理區塊。處理器102接著根據邏輯頁編號(LSN=1)存取映射區塊803(物理區塊3)之第1頁，並且判斷此頁是否已被使用。根據本發明之一實施例，處理器102可根據此頁之冗餘區域中所儲存的LBN與LSN判斷此頁是否已被使用，若無紀錄LBN與LSN，則處理器102可直接將資料寫入該頁。另一方面，若此頁之冗餘區域已紀錄LBN與LSN，代表此頁之資料區域已被使用，如圖所示之映射區塊803之第1頁，其中被填滿的欄位代表該欄位已被使用。因此，處理器102接著根據得到的物理區塊編號查找物理區塊資訊表802中索引3的資料欄位內容，其中物理區塊資訊表802如上述包含狀態與連結資訊兩欄位，狀態欄位用以紀錄此物理區塊為一空閒區塊(FB)、快取區塊(CB)、映射區塊(MpB)或修改區塊(MoB)，而連結資訊如上述分別用以儲存此物理區塊之連結資訊。根據本發明之一實施例，若連結資訊為空，代表此映射區塊內所儲存的資料尚未被修改過，處理器102可配置一修改區塊以及一快取區塊，利用此修改區塊之一空白頁儲存在本次寫入操作要被儲存的既定資料，並且於快取區塊之一空白頁儲存此既定資料所對應之邏輯頁編號(LSN=1)。另一方面，當連結資訊不為空，例如第8a圖所示，處理器102由物理區塊資訊表802中得知映射區塊對應之修改區塊之物理區塊編號為4。

接著，處理器102根據修改區塊之物理區塊編號查找物理區塊資訊表802內對應的欄位，得到修改區塊之連結資訊。如上述，修改區塊之連結資訊儲存對應之快取頁之一快取區塊索引。處理器102接著根據快取區塊索引得到快取區塊之位置資訊，如上述，在此實施例中，快取區塊索引為11，處理器102因此得知對應於此修改區塊之快取頁位於系統配置的第1個快取區塊(11除以8之商數)的第3頁(11除以8之餘數)。請參考第8b圖，處理器102可進一步根據快取區塊索引表809取得此快取頁所對應的快取區塊的物理區塊編號，得知系統配置的第1個快取區塊(快取區塊編號為1)所對應的物理區塊編號為2。處理器102接著可存取系統配置的第1個快取區塊805的第3頁。

值得注意的是，如上述，快取區塊的冗餘區域同樣會紀錄對應之修改區塊之物理區塊編號，例如快取區塊804與805的冗餘區域(右側欄位)可儲存對應之修改區塊之物理區塊編號，用以顯示出各頁之資料區域所儲存之位置資訊屬於哪個修改區塊。根據本發明之一實施例，當處理器102根據快取區塊索引找到對應之快取頁806時，處理器102將快取頁806之內容載入隨機存取記憶體裝置103。

在此實施例中，由於是要將資料寫入快閃記憶體，因此處理器102自快取頁806之資料尾端倒序遍曆(visit)快取頁806之內容，如第8c圖所示，處理器102發現最後一筆被儲存之邏輯頁編號LSN位於快取頁806的第5個欄位。因此，處理器102得知修改區塊內下一個可使用之空白頁為第6頁。

值得注意的是，在本發明之實施例中，由於快取頁806之內容已被載入隨機存取記憶體裝置103，因此處理器102可快速得知修改區塊內下一個可使用之空白頁，因此，與傳統技術中必須在快閃記憶體中倒序遍曆修改區塊的內容以找出下一個空白頁等的技術相比，本發明所提出之快閃記憶體管理方法實際上僅需存取快取區塊之一頁(即，上述之快取頁)，以及修改區塊之一頁，顯然地可大幅度地提升快閃記憶體之寫入速度。

請參考至第8d圖，由於處理器102已得知修改區塊807(物理區塊4)內下一個可使用之空白頁為第6頁，因此處理器102接著將既定資料寫入該頁，並且在該頁的冗餘區域寫入這筆既定資料的邏輯頁編號LSN(以及邏輯區塊編號LBN，圖未示)。此外，請參考回第8c圖，由於處理器102已在遍曆過程中得知快取頁806下一個可被使用之欄位為第6個欄位，如第8c圖中繪出的箭頭所指，處理器102接著將這筆既定資料的邏輯頁編號LSN=1寫入至被載入隨機存取記憶體裝置103之快取頁806第6個欄位。

值得注意的是，由於實際上快取區塊805是被儲存於快閃記憶體內，因此處理器102接著將隨機存取記憶體裝置103內被更新之快取頁806資料寫入至快取區塊805(物理區塊2)的下一個空白頁。根據本發明之一實施例，處理器102根據快取區塊索引表809得知快取區塊805的下一個空白頁為第4頁，因此處理器102如第8e圖所示將被更新之快取頁806資料寫入至快取區塊805(物理區塊2)的第4頁，並且將快取區塊索引表809中此快取區塊的第一空白頁資訊更新為5。此外，修改區塊所對應之快取區塊索引變成12，因此處理器102最後於物理區塊資訊表802內將修改區塊807所對應之快取區塊索引更新成12。

第9圖係顯示根據本發明之另一實施例所述之快閃記憶體管理方法流程圖。首先，處理器102接收包含一讀取邏輯位址之一讀取指令，並根據讀取邏輯位址取得一快取區塊之一快取區塊索引(步驟S901)。接著，處理器102根據快取區塊索引載入快取區塊之複數資料欄位所儲存之位置資訊至一隨機存取記憶體裝置(步驟S902)。接著，處理器102於隨機存取記憶體裝置內自快取區塊之資料欄位尾端倒序尋找讀取邏輯位址所對應之一位置資訊，以取得讀取邏輯位址最近儲存之位置資訊(步驟S903)。最後，處理器102根據取得之位置資訊存取讀取邏輯位址所對應之修改區塊內所儲存之對應於讀取邏輯位址之資料(步驟S904)。

第10圖係顯示根據本發明之一實施例所述之快閃記憶體之讀取操作之詳細流程圖。首先，處理器102根據讀取指令之讀取邏輯位址取得邏輯區塊編號LBN與邏輯頁編號LSN(步驟S1001)。接著，處理器102查詢邏輯至映射區塊對應表以取得映射區塊的物理區塊編號(步驟S1002)。接著，處理器102檢查此映射區塊中對應於此邏輯頁編號LSN之一頁是否為空白頁(步驟S1003)。若是，處理器102返回空白資料(步驟S1004)。若否，處理器102依據物理區塊資訊表查詢映射區塊是否有對應的修改區塊(步驟S1005)。若此映射區塊沒有對應的修改區塊，則處理器102直接返回此頁所儲存之資料(步驟S1006)。若此映射區塊有對應的修改區塊，則處理器102依據物理區塊資訊表中映射區塊的連結資訊取得修改區塊所對應的快取頁的快取區塊索引(步驟S1007)。接著，處理器102再根據快取區塊索引查詢快取區塊索引表，以取得此快取頁所對應的快取區塊的物理區塊編號(步驟S1008)。接著，處理器102將此快取頁的內容載入隨機存取記憶體裝置103(步驟S1009)。接著，處理器102操作於隨機存取記憶體裝置103中，自快取頁之資料尾端倒序遍曆(visit)快取頁所儲存的資料，尋找出最新一筆對應於此邏輯頁編號LSN之紀錄，並取得儲存此邏輯頁編號LSN之欄位之索引(步驟S1010)。最後，處理器102根據此索引讀取修改區塊中對應於此邏輯頁編號LSN之最新一筆資料並返回(步驟S1011)。

第11a-11d圖係顯示根據本發明之一實施例所述之快閃記憶體之讀取操作之示意圖。假設處理器102接收到的讀取邏輯位址為90，則處理器102可得到邏輯區塊編號LBN=1，邏輯頁編號LSN=1。接著，如第11a圖所示，處理器102根據邏輯區塊編號(LBN=1)查找邏輯至映射區塊對應表801中索引1的資料欄位內容，得到對應之映射區塊之物理區塊編號。其中，根據本發明之一實施例，若該資料欄位為空，代表此邏輯區塊尚未分配對應之映射區塊，處理器102無法找到有效之資料，便可直接返回此結果。若該資料欄位不為空，代表此邏輯區塊已分配有對應之映射區塊，例如，在此實施例中，對應之映射區塊之物理區塊編號為3，代表此映射區塊實際配置為第3個物理區塊。處理器102接著根據邏輯頁編號(LSN=1)存取映射區塊803(物理區塊3)之第1頁，並且判斷此頁是否已被使用。根據本發明之一實施例，處理器102可根據此頁之冗餘區域中所儲存的LBN與LSN判斷此頁是否已被使用，若無紀錄LBN與LSN，代表此頁尚未被使用，處理器102可返回空資料。另一方面，若此頁之冗餘區域已記錄LBN與LSN，代表此頁之資料區域已被使用，如圖所示之映射區塊803之第1頁，其中被填滿的欄位代表該欄位已被使用。因此，處理器102接著根據得到的物理區塊編號查找物理區塊資訊表802中索引3的資料欄位內容。根據本發明之一實施例，若映射區塊之連結資訊為空，代表此映射區塊內所儲存的資料尚未被修改過，即，映射區塊內所儲存的資料為有效的，處理器102可直接讀取並返回映射區塊內所儲存的資料。另一方面，當連結資訊不為空，代表此映射區塊內所儲存的資料已被修改過，即，映射區塊內所儲存的資料為無效的。因此，處理器102進一步透過物理區塊資訊表802中得知映射區塊所對應之修改區塊之物理區塊編號為4。

接著，處理器102根據修改區塊之物理區塊編號查找物理區塊資訊表802內對應的欄位，得到修改區塊之連結資訊。如上述，修改區塊之連結資訊儲存對應之快取頁之一快取區塊索引，例如在此實施例中，快取區塊索引為12。接著，處理器102根據快取區塊索引得知對應於此修改區塊之快取頁位於系統配置的第1個快取區塊(12除以8之商數)的第4頁(12除以8之餘數)。請參考第11b圖，處理器102可進一步根據快取區塊索引表809取得此快取頁所對應的快取區塊的物理區塊編號，得知系統配置的第1個快取區塊(快取區塊編號為1)所對應的物理區塊編號為2。處理器102接著可存取系統配置的第1個快取區塊805的第4頁，並且將此快取頁808之內容載入隨機存取記憶體裝置103。

接著，處理器102自快取頁808之資料尾端倒序遍曆快取頁808之內容，以尋找出最後一筆存有LSN=1的資料的索引。如上述，由於快取頁808之內容已被載入隨機存取記憶體裝置103，因此處理器102不需遍曆配置於快閃記憶體101內之修改區塊，僅需透過遍曆儲存於隨機存取記憶體裝置103之快取頁，即可得知修改區塊內最新存有LSN=1的資料的位置。因此，與傳統技術相比，本發明所提出之快閃記憶體管理方法顯然地可大幅度地提升快閃記憶體之讀取速度。再者，雖然本實施例中，處理器102是從尾端開始倒序遍曆隨機存取記憶體裝置103中快取頁的資料欄位元，但是顯然也可以從頭端開始順序遍曆該快取頁的資料欄位元來獲得需要存取的頁在該修改區塊中的位置資訊。

如第11c圖所示，處理器102發現最後一筆存有LSN=1的資料位於快取頁808的第6個欄位。因此，處理器102可得知修改區塊的第6頁儲存著對應於邏輯位址為90的最新資料。最後，如第11d圖所示，處理器102存取修改區塊807(物理區塊4)的第6頁之資料區域，並返回讀取的資料。

根據本發明之一實施例，快取區塊的數量可根據計算機系統的需求而決定。例如，對於一快閃記憶體裝置，可配置四個快取區塊，並依序分配快取區塊編號(例如，0~3)，並且處理器102於快取區塊初始化時，可藉由遍曆修改區塊之冗餘區域所儲存之位置資訊建立出快取區塊。處理器102接著根據映射區塊、修改區塊以及快取區塊之冗餘區域所儲存之資料(包含邏輯塊編號與邏輯頁編號)建立出如第3圖所示之邏輯至映射區塊對應表300、如第4圖所示之物理區塊資訊表400以及如第5圖所示之快取區塊索引表500。根據本發明之一實施例，為了避免不正常關機導致快取區塊所儲存的資料產生錯誤，於計算機系統初始化時，處理器102也可先檢查各快取區塊所儲存的內容是否正確，例如，根據各快取頁之資料欄位所儲存的位置資訊(即，邏輯頁編號)以及各快取頁之冗餘區域所儲存的修改區塊之物理區塊編號，比對該快取頁之各位置資訊是否與此修改區塊之各頁的冗餘區域所儲存的邏輯頁編號相符。若符合則保留此快取區塊，若不符合，則捨棄此快取區塊，直接抹除。此外，當一個快取區塊存滿資料時，處理器102可取出下一個預留的空閒快取區塊使用(如第5a圖與第5b圖所示)，並且當所有已被使用的快取區塊達到系統規定的最大可用快取區塊數量時，例如，若第5b圖所示之快取區塊索引表501中4個快取區塊的第一個空白頁皆紀錄為系統最大頁數8時，處理器102直接抹除所有快取區塊，以釋放出有效的空間。

本領域一般技術人員可以瞭解，雖然於之前描述中是將讀取操作與寫入操作分開說明的，但是本發明讀取與寫入操作的實質特徵是相同的。當邏輯位元址所對應之映射區塊之資料不能直接進行存取時，即在進行寫入操作時映射區塊的該頁已存儲有資料或是在進行讀取操作時映射區塊的該頁資料並不是最新的，處理器需要通過映射區塊的資訊來獲取與映射區塊相對應之修改區塊的第一個空白頁的位置資訊或是與該邏輯位址相對應的最新的頁的位置資訊，進而才能夠高效而準確地完成既定資料的寫入或讀取操作。

此外，當系統對快閃記憶體執行合併(merge)操作時，處理器102可根據各修改區塊之冗餘區域所儲存之邏輯區塊編號LBN與邏輯頁編號LSN判斷修改區塊之資料區域是否依照映射區塊之資料順序被寫入資料。當映射區塊之各頁的更新資料依序被寫入修改區塊時，處理器102可直接抹除映射區塊，並且改為配置修改區塊作為映射區塊。另一方面，當映射區塊之各頁的更新資料依序未被寫入修改區塊時，處理器102可取得一空閒區塊，將修改區塊與映射區塊之有效資料合併至空閒區塊，抹除映射區塊與修改區塊，並且配置此空閒區塊作為新的映射區塊。

本發明雖以較佳實施例揭露如上，然其並非用以限定本發明的範圍，任何熟習此項技藝者，在不脫離本發明之精神和範圍內，當可做些許的更動與潤飾，因此本發明之保護範圍當視後附之申請專利範圍所界定者為準。

100．．．計算機系統

101．．．快閃記憶體

102．．．處理器

103．．．隨機存取記憶體裝置

200．．．快閃記憶體

201．．．快取區塊

202．．．映射區塊

203．．．修改區塊

300、801‧‧‧邏輯至映射區塊對應表

400、802‧‧‧物理區塊資訊表

500、501、809‧‧‧快取區塊索引表

803‧‧‧映射區塊

804、805‧‧‧快取區塊

806、808‧‧‧快取頁

807‧‧‧修改區塊

LBN‧‧‧邏輯區塊編號

LSN‧‧‧邏輯頁編號

第1圖係顯示根據本發明之一實施例所述之計算機系統。

第2圖係顯示根據本發明之一實施例所述之快閃記憶體之資料結構示意圖。

第3圖係顯示根據本發明之一實施例所述之邏輯至映射區塊對應表之資料結構示意圖。

第4圖係顯示根據本發明之一實施例所述之物理區塊資訊表之資料結構。

第5a-5b圖係顯示根據本發明之一實施例所述之快取區塊索引表之資料結構示意圖。

第6圖係顯示根據本發明之一實施例所述之快閃記憶體管理方法流程圖。

第7a-7b圖係顯示根據本發明之一實施例所述之快閃記憶體之寫入操作之詳細流程圖。

第8a-8e圖係顯示根據本發明之一實施例所述之快閃記憶體之寫入操作之示意圖。

第9圖係顯示根據本發明之另一實施例所述之快閃記憶體管理方法流程圖。

第10圖係顯示根據本發明之一實施例所述之快閃記憶體之讀取操作之詳細流程圖。

第11a-11d圖係顯示根據本發明之一實施例所述之快閃記憶體之讀取操作之示意圖。

100．．．計算機系統

101．．．快閃記憶體

102．．．處理器

103．．．隨機存取記憶體裝置

Claims (29)

1. 一種快閃記憶體管理方法，用以管理一快閃記憶體裝置，其中該快閃記憶體裝置配置至少一映射區塊、至少一修改區塊以及至少一快取區塊，包括：接收包含一寫入邏輯位址與一既定資料之一寫入指令，用以寫入該既定資料至該快閃記憶體裝置；判斷對應於該寫入邏輯位址之該映射區塊之一頁是否已經被使用；以及當對應於該寫入邏輯位址之該映射區塊之該頁已經被使用時，根據該寫入邏輯位址由該快取區塊讀取對應於該修改區塊之一快取頁至一隨機存取記憶體裝置，於該隨機存取記憶體裝置內依序讀取該快取頁之資料欄位以獲得該空白頁於該修改區塊內之位置資訊，其中該快取區塊之各快取頁具有複數資料欄位用以依序儲存該修改區塊之各非空白頁所寫入之資料所對應之位置資訊；以及依據獲得之該位置資訊寫入該既定資料於該修改區塊之一空白頁。
2. 如申請專利範圍第1項所述之快閃記憶體管理方法，更包括：寫入包含該修改區塊之存儲該既定資料之該頁之位置資訊於該快取區塊之一空白頁。
3. 如申請專利範圍第1項所述之快閃記憶體管理方法，更包括：根據該寫入邏輯位址取得對應之一邏輯區塊編號以及一邏輯頁編號；以及寫入該邏輯頁編號於該快取區塊，用以做為該修改區 塊之存儲該既定資料之頁之該位置資訊。
4. 如申請專利範圍第3項所述之快閃記憶體管理方法，更包括：於該快取區塊之各快取頁分配一資料區域以及一冗餘區域，其中該資料區域包括該複數資料欄位用以儲存該邏輯頁編號，並且該冗餘區域用以儲存該快取區塊之一快取區塊索引以及該快取區塊之該快取頁所對應之該修改區塊之一物理區塊編號。
5. 如申請專利範圍第3項所述之快閃記憶體管理方法，更包括：於一隨機存取記憶體裝置建立一第一資訊表，用以儲存各邏輯區塊與各映射區塊之一對應關係之資訊；以及於該隨機存取記憶體裝置建立一第二資訊表，用以儲存各物理區塊之一狀態資訊與一連結資訊。
6. 如申請專利範圍第5項所述之快閃記憶體管理方法，更包括：儲存該映射區塊之一物理區塊編號於該第一資訊表；以及儲存該修改區塊之該物理區塊編號以及該快取區塊之一快取區塊索引於該第二資訊表。
7. 如申請專利範圍第5項所述之快閃記憶體管理方法，其中判斷對應於該寫入邏輯位址之該映射區塊之該頁已經被使用之該步驟包括：依據該邏輯區塊編號查詢該第一資訊表以讀取對應於該邏輯區塊編號之該映射區塊之對應於該邏輯頁編號之該 頁；以及讀取該頁之一冗餘區域以判斷該映射區塊之該頁是否已經被使用。
8. 如申請專利範圍第5項所述之快閃記憶體管理方法，其中根據該寫入邏輯位址由該快取區塊讀取對應於該修改區塊之該快取頁至該隨機存取記憶體裝置之該步驟包括：當該映射區塊之該頁已經被使用，依據該映射區塊之一物理區塊編號查詢該第二資訊表以獲得該映射區塊所對應之該修改區塊之一物理區塊編號；依據該修改區塊之該物理區塊編號查詢該第二資訊表以獲得其所對應之該快取區塊之一快取區塊索引；以及依據該快取區塊索引查詢一第三資訊表以將該對應之快取區塊之包含該修改區塊之各非空白頁所對應之該快取頁讀取至該隨機存取記憶體裝置，其中該第三資訊表用以存儲該快取區塊之該快取區塊索引以及對應之一物理區塊編號與第一個空閒的快取頁的頁編號。
9. 如申請專利範圍第1項所述之快閃記憶體管理方法，其中於該隨機存取記憶體裝置內自該快取頁之尾端倒序讀取該些資料欄位以獲得對應於該寫入邏輯位址之空白頁於該修改區塊內之該位置資訊。
10. 一種快閃記憶體管理方法，用以管理一快閃記憶體裝置，其中該快閃記憶體裝置配置至少一映射區塊、至少一修改區塊以及至少一快取區塊，包括： 接收包含一讀取邏輯位址之一讀取指令用以由該快閃記憶體裝置之一頁讀取一既定資料；以及判斷對應於該讀取邏輯位址之該映射區塊之一頁是否已經被修改過，其中當對應於該讀取邏輯位址之該映射區塊之頁的資料已經被修改過，則於對應於該映射區塊之該修改區塊中讀取該既定資料；其中該於對應於該映射區塊的修改區塊中讀取該既定資料的步驟包括：根據該讀取邏輯位址由該快取區塊讀取對應於該修改區塊之一快取頁至一隨機存取記憶體裝置，於該隨機存取記憶體裝置內依序讀取該快取頁之資料欄位以獲得對應於該讀取邏輯位址之頁於該修改區塊內之一位置資訊，其中該快取區塊之各快取頁具有複數資料欄位用以依序儲存該修改區塊之各非空白頁所寫入之資料所對應之位置資訊；以及依據該獲得之位置資訊於該修改區塊之該頁讀取該既定資料。
11. 如申請專利範圍第10項所述之快閃記憶體管理方法，更包括：於一隨機存取記憶體裝置建立一第一資訊表，用以儲存各邏輯區塊與各映射區塊之一對應關係之資訊；以及於該隨機存取記憶體裝置建立一第二資訊表，用以儲存各物理區塊之一狀態資訊與一連結資訊。
12. 如申請專利範圍第11項所述之快閃記憶體管理方法，更包括： 儲存各映射區塊之一物理區塊編號於該第一資訊表；以及儲存各修改區塊之一物理區塊編號、以及各修改區塊所對應之一快取區塊之一快取區塊索引於該第二資訊表。
13. 如申請專利範圍第11項所述之快閃記憶體管理方法，其中判斷對應於該讀取邏輯位址之該映射區塊之該頁是否已經被修改過之步驟包括：根據該讀取邏輯位址取得對應之一邏輯區塊編號以及一邏輯頁編號；根據該邏輯區塊編號查詢該第一資訊表以獲得對應於該邏輯區塊編號之該映射區塊之該物理區塊編號；以及根據該物理區塊編號查詢該第二資訊表以判斷該映射區塊之該頁的資料是否已經被修改過。
14. 如申請專利範圍第11項所述之快閃記憶體管理方法，其中於對應於該映射區塊之該修改區塊中讀取該既定資料之步驟包括：當該映射區塊之該頁的資料已經被修改過，依據該映射區塊之該物理區塊編號查詢該第二資訊表以獲得該映射區塊所對應之該修改區塊之該物理區塊編號；依據該修改區塊之該物理區塊編號查詢該第二資訊表以獲得其所對應之該快取區塊之一快取區塊索引；以及依據該快取區塊索引查詢一第三資訊表以將該快取頁讀取至該隨機存取記憶體裝置，其中該第三資訊表用以存儲該快取區塊之該快取區塊索引以及對應之物理區塊編號與第一個空閒的快取頁的頁 編號。
15. 如申請專利範圍第14項所述之快閃記憶體管理方法，更包括：於該快取區塊之各快取頁分配一資料區域以及一冗餘區域，其中該資料區域包括該複數資料欄位用以儲存該邏輯頁編號，並且該冗餘區域用以儲存該快取區塊之該快取區塊索引以及該快取區塊所對應之該修改區塊之該物理區塊編號。
16. 如申請專利範圍第14項所述之快閃記憶體管理方法，包括於該隨機存取記憶體裝置內自該快取頁之尾端倒序讀取該些資料欄位以獲得對應於該讀取邏輯位址之頁於該修改區塊內之該位置資訊。
17. 一種計算機系統，包括：一快閃記憶體，配置至少一映射區塊、至少一修改區塊以及至少一快取區塊；一隨機存取記憶體裝置；以及一處理器，耦接至該快閃記憶體與該隨機存取記憶體裝置，該處理器接收包含一寫入邏輯位址與既定資料之一寫入指令，當對應於該寫入邏輯位址之該映射區塊之一頁已經被使用，則根據該寫入邏輯位址由該快取區塊讀取對應於該修改區塊之一快取頁至該隨機存取記憶體裝置，並於該隨機存取記憶體裝置內依序讀取該快取頁之內容以獲得該修改區塊內之一空白頁之位置資訊，以及依據該位置資訊寫入該既定資料於該修改區塊之該空白頁，其中該快取區塊之各快取頁具有複數資料欄位用以依 序儲存該修改區塊之各非空白頁所寫入之資料所對應之位置資訊。
18. 如申請專利範圍第17項所述之計算機系統，其中該快取區塊之各快取頁分別包括一資料區域與一冗餘區域，該快取區塊之該資料區域包括該複數資料欄位用以儲存對應之該修改區塊之各頁所寫入之資料所對應之一邏輯頁編號，並且該快取區塊之該冗餘區域用以儲存該快取區塊之一快取區塊索引以及對應之該修改區塊之一物理區塊編號。
19. 如申請專利範圍第17項所述之計算機系統，其中該隨機存取記憶體裝置耦接至該處理器，且儲存一第一資訊表以及一第二資訊表，其中該第一資訊表用以儲存各邏輯區塊與各映射區塊之一對應關係之資訊，該第二資訊表用以儲存各物理區塊之一狀態資訊與一連結資訊。
20. 如申請專利範圍第19項所述之計算機系統，其中於初始化時，該處理器根據該映射區塊、該修改區塊以及該快取區塊之該冗餘區域所儲存之資料建立該第一資訊表以及該第二資訊表。
21. 如申請專利範圍第19項所述之計算機系統，其中該處理器依據該邏輯區塊編號查詢該第一資訊表以讀取對應於該邏輯區塊編號之映射區塊之對應於該邏輯頁編號之頁，並讀取該頁之一冗餘區域以判斷該映射區塊之該頁是否已經被使用。
22. 如申請專利範圍第19項所述之計算機系統，其中當該映射區塊之該頁已經被使用，該處理器依據該映射區 塊之一物理區塊編號查詢該第二資訊表以獲得該映射區塊所對應之該修改區塊之一物理區塊編號，依據該修改區塊之該物理區塊編號查詢該第二資訊表以獲得其所對應之快取區塊之一快取區塊索引，以及依據該快取區塊索引查詢一第三資訊表以將該對應該快取區塊之該快取頁讀取至該隨機存取記憶體裝置，其中該第三資訊表用以存儲該快取區塊之該快取區塊索引以及對應之一物理區塊編號與第一個空閒的快取頁的頁編號。
23. 如申請專利範圍第17項所述之計算機系統，其中當所有之該快取區塊存滿資料時，該處理器直接抹除該快取區塊。
24. 如申請專利範圍第17項所述之計算機系統，其中該快閃記憶體之抹除資料之最小單位大於寫入資料之最小單位。
25. 一種計算機系統，包括：一快閃記憶體，配置至少一映射區塊、至少一修改區塊以及至少一快取區塊；一隨機存取記憶體裝置；以及一處理器，耦接至該快閃記憶體與該隨機存取記憶體裝置，該處理器接收包含一讀取邏輯位址之一讀取指令，當對應於該讀取邏輯位址之該映射區塊之一頁的資料已經被修改過，則根據該讀取邏輯位址由該快取區塊讀取對應於該修改區塊之一快取頁至該隨機存取記憶體裝置，並於該隨機存取記憶體裝置內依序讀取該快取頁之內容以獲得對應於該讀取邏輯位址之該頁於該修改區塊內之一位置 資訊，以及依據該位置資訊於該修改區塊之該頁讀取該既定資料；其中該快取區塊之各快取頁具有複數資料欄位用以依序儲存該修改區塊之各非空白頁所寫入之資料所對應之位置資訊。
26. 如申請專利範圍第25項所述之計算機系統，其中該處理器更於該隨機存取記憶體裝置內建立一第一資訊表，用以儲存各映射區塊之一物理區塊編號，以及建立一第二資訊表，用以儲存各修改區塊之一物理區塊編號、以及各修改區塊所對應之一快取區塊之一快取區塊索引。
27. 如申請專利範圍第26項所述之計算機系統，其中該處理器更根據該讀取邏輯位址取得對應之一邏輯區塊編號以及一邏輯頁編號、根據該邏輯區塊編號查詢該第一資訊表以獲得對應於該邏輯區塊編號之該映射區塊之該物理區塊編號、以及根據該物理區塊編號查詢該第二資訊表以判斷該映射區塊之該頁的資料是否已經被修改過。
28. 如申請專利範圍第26項所述之計算機系統，其中當該映射區塊之該頁的資料已經被修改過，該處理器根據該映射區塊之該物理區塊編號查詢該第二資訊表以獲得該映射區塊所對應之該修改區塊之該物理區塊編號、依據該修改區塊之該物理區塊編號查詢該第二資訊表以獲得其所對應之該快取區塊之該快取區塊索引、以及依據該快取區塊索引查詢一第三資訊表以將該修改區塊所對應之該快取頁讀取至該隨機存取記憶體裝置，其中該第三資訊表存儲於該隨機存取記憶體裝置，用以存儲該快取區塊之該快取 區塊索引以及對應之物理區塊編號與第一個空閒的快取頁的頁編號。
29. 一種快閃記憶體管理方法，用以管理一快閃記憶體裝置，其中該快閃記憶體裝置配置至少一映射區塊、至少一修改區塊以及至少一快取區塊，包括：接收一包含一邏輯位址之存取指令，用以於該快閃記憶體裝置存取一既定資料；以及當對應於該邏輯位址之該映射區塊之一頁不適於存取該既定資料，則對與該映射區塊對應之該修改區塊進行存取操作，包括：由該快閃記憶體裝置之該快取區塊讀取對應於該修改區塊之一快取頁至一隨機存取記憶體裝置，於該隨機存取記憶體裝置內依序讀取該快取頁之內容以獲得該既定資料於該修改區塊內之存取位置資訊，其中該快取區塊之各快取頁具有複數資料欄位用以依序儲存該修改區塊之各非空白頁所寫入之資料所對應之位置資訊；以及依據該存取位置資訊於該快閃記憶體裝置之修改區塊內存取該既定資料。