非易失性存儲器控制裝置及其多階重新排序方法

2023-05-27 18:04:46

專利名稱：非易失性存儲器控制裝置及其多階重新排序方法
技術領域：
本發明涉及一種非易失性存儲器的存取方法，且特別涉及一種非易失性存儲器控 制裝置及其多階重新排序方法。
背景技術：
快閃記憶體(flash memory)是一種可編程(programmable)的只讀存儲器(read only memory, ROM)，其允許被多次的抹除並更新所存儲的數據。這種快閃記憶體在現今的 電子產品中的應用非常廣泛，常見於存儲卡及隨身盤等作為數字電子產品間交換數據的媒 介。通常，快閃記憶體被劃分成多個存儲區塊(block)，而每一個存儲區塊中又被細分 為許多容量相同的存儲頁(page)。在此，快閃記憶體存在著一個限制，就是在當對快快閃記憶體儲 器進行數據的更新時，必須需針對要被更新的地址所在的存儲區塊進行抹除的動作後，再 把新的數據寫入。然而隨著快閃記憶體技術的發展，快閃記憶體的工藝技術越來越新進，且 容量越來越大，而使得存儲區塊的抹除與寫入所需的時間越來越長，如此一來在執行快閃 存儲器的存取動作時，很容易超出事先所限定的最大存取時間(如某些存儲器裝置為250 毫秒)，而使得快閃記憶體的數據寫入失敗。請參照圖1 圖2，圖1 圖2為現有技術的快閃記憶體的存取方法的動作示 意圖。在圖1中，邏輯區塊地址(logical block address)LBAN對應的物理區塊地址 (physical block address)為ΡΒΑ0，數據Wl W3依序被寫入物理區塊地址PBAO的數據 區塊中，其中當數據W3被寫入物理區塊地址PBAO時，數據W3所預定寫入的部份存儲頁已 被數據W2所使用，因此必須先抹除物理區塊地址PBAO上所有的數據後才能將數據W3寫入 物理區塊地址ΡΒΑ0。然而，快閃記憶體的數據抹除動作將會耗費許多時間，且數據W1、W2 仍為使用者所欲保留的數據，因此不能將物理區塊地址PBAO上的數據刪除。此時便需要進 行如圖2所示的數據存取動作，將物理區塊地址PBAO的數據Wl複製到邏輯區塊地址LBAN 所對應的另一物理區塊地址PBAl，並將數據W2讀出後與數據W3重新排序，然後將重新排序 後的數據W2與W3存儲到物理地址PBAl。完成邏輯區塊地址LBAN的重新排序操作後，便 可以抹除物理區塊地址PBAO的存儲區塊，並將邏輯區塊地址LBAN改對應到物理區塊地址 PBAl,以增加一個可用的空白物理區塊地址。然而，由於前述將物理區塊地址PBAO的數據複製到物理區塊地址PBAl (ΡΒΑ0- > PBA1)的操作會使得存儲器裝置處於忙碌(busy)狀態而無法回應主機(host)的存取要求， 因此一般非易失性存儲器的規範標準均會定義非易失性存儲器裝置處於忙碌狀態的最大 時間長(即額定忙碌期限)。現有的快閃記憶體存取方法雖可解決數據寫入時，數據寫入位 置已被使用而無法進行寫入的情形，但當數據區塊中所存儲的數據量過大時，重新排序數 據將花費許多時間，而使得快閃記憶體的存取動作無法於額定忙碌期限內完成，而造成數 據存取失敗。

發明內容
本發明提供一種非易失性存儲器控制裝置及其多階重新排序方法，可避免非易失 性存儲器裝置的存取時間超過額定的規格值。本發明提出一種非易失性存儲器裝置的多階重新排序方法，其步驟包括當一邏輯 區塊地址需要進行重新排序時，將邏輯區塊地址所對應的存儲區塊切分為多個子區塊。接 著，在一額定忙碌期限內，執行一主機命令，以及對上述子區塊中的一個子區塊進行重新排 序。的後，在另一額定忙碌期限內，執行另一主機命令，以及對上述子區塊中的另一個子區 塊進行重新排序。在本發明的一實施例中，上述的多階重新排序方法，還包括建立一重新排序狀態 表，其中重新排序狀態表包含一邏輯地址欄位與一重新排序階段欄位。當邏輯區塊地址需 要進行重新排序時，將邏輯區塊地址登記於重新排序狀態表的邏輯地址欄位。在本發明的一實施例中，上述的多階重新排序方法，還包括當上述子區塊全部完 成重新排序時，將邏輯區塊地址自重新排序記錄表中刪除。在本發明的一實施例中，上述的重新排序狀態表還包含一物理地址欄位，以記錄 邏輯區塊地址所對應的物理區塊地址。在本發明的一實施例中，上述的重新排序階段欄位記錄上述子區塊中尚待進行重 新排序的子區塊。在本發明的一實施例中，上述的重新排序階段欄位記錄上述子區塊中已完成重新 排序的子區塊。在本發明的一實施例中，上述的重新排序階段欄位記錄多階重新排序中的目前階 段狀態。在本發明的一實施例中，上述的重新排序狀態表建立在一存儲裝置中。在本發明的一實施例中，上述的存儲裝置為靜態存儲器或動態存儲器。本發明提出一種非易失性存儲器控制裝置，用以存取一快閃記憶體，非易失性存 儲器控制裝置包括一控制器，耦接快閃記憶體，當一邏輯區塊地址需要進行重新排序時，控 制器將邏輯區塊地址所對應的存儲區塊切分為多個子區塊，在一額定忙碌期限內，執行一 主機命令，以及對上述子區塊中的一個子區塊進行重新排序，並在另一額定忙碌期限內，執 行另一主機命令，以及對上述子區塊中的另一個子區塊進行重新排序。在本發明的一實施例中，上述的非易失性存儲器控制裝置更包括一存儲裝置，耦 接控制器，存儲裝置建立一重新排序狀態表，其中重新排序狀態表包含一邏輯地址欄位與 一重新排序階段欄位，當邏輯區塊地址需要進行重新排序時，將邏輯區塊地址登記於重新 排序狀態表的邏輯地址欄位。在本發明的一實施例中，上述的非易失性存儲器控制裝置，還包括一傳輸接口，耦 接控制器，傳輸接口用以接收主機命令。基於上述，本發明利用在額定忙碌期限內，執行完存取指令的剩餘時間，來對子區 塊進行重新排序，以避免非易失性存儲器的存取時間超過額定的規格值。為讓本發明的上述特徵和優點能更明顯易懂，下面特舉實施例，並配合附圖作詳 細說明如下。


圖1 圖2為現有技術的快閃記憶體的存取方法的動作示意圖。圖3A 圖;3B為本發明一實施例的非易失性存儲器存取方法的動作示意圖。圖4為本發明的非易失性存儲器的多階重新排序方法的一實施例的動作流程圖。圖5A 圖5C為本發明的非易失性存儲器的多階重新排序方法的實施例的動作示 意圖。圖6為本發明的一實施例的非易失性存儲器控制裝置的方塊圖。主要元件符號說明600 存儲器控制裝置；610 控制器；620:存儲裝置；630:傳輸接口；640 非易失性存儲器；PBAO PBA100 物理區塊地址；LBAN、LBAO 邏輯區塊地址；Wl W4 數據；SO S3:子區塊；S410 S430:多階重新排序的步驟。
具體實施例方式圖3A 圖;3B為本發明一實施例的非易失性存儲器存取方法的動作示意圖，請同 時參照圖3A 圖;3B，在圖3A 圖;3B的實施例中，邏輯區塊地址LBAN最多可同時對應到三 個物理區塊地址PBAO PBA2，然不以此為限。如圖3A所示，數據Wl W3依序被寫入物理 區塊地址PBAO的數據區塊中，其中當數據W3被寫入物理區塊地址PBAO時，數據W3所預定 寫入的數據區塊的位置已被數據W2所使用。此時為避免過度頻繁地對非易失性存儲器進 行抹除與寫入而造成時間的浪費，可將數據W3存入到邏輯區塊地址LBAN所對應的另一物 理區塊地址PBAl (其為一空白物理區塊地址)。如此一來，便可免去讀取並抹除物理區塊地 址PBAO的數據W1、W2後，再重新寫入數據Wl W3等步驟而省下許多時間。類似地，圖 為另一針對邏輯區塊地址LBAN寫入的數據W4，當數據W4所預定寫入的數據區塊的位置已 被物理區塊地址PBAO的數據W2以及物理區塊地址PBAl的數據W3所使用時，可將數據W4 存入到邏輯區塊地址LBAN所對應的另一物理區塊地址PBA2 (其為一空白物理區塊地址)。依此類推，邏輯區塊地址LBAN所對應的三個物理區塊地址PBAO PBA2可提供 給寫入邏輯區塊地址LBAN的數據存儲，而當數據的預定寫入位置在三個物理區塊地址 PBAO PBA2中皆已被使用時，便需要對邏輯區塊地址LBAN進行重新排序，也就是對非易 失性存儲器中邏輯區塊地址LBAN所對應的三個物理區塊地址PBAO PBA2進行重新排序。 以下將列舉本發明的實施例，以提供不同於現有技術的非易失性存儲器的重新排序方法， 避免如現有技術般，因重新排序數據花費過多時間，而使得快閃記憶體的存取動作無法於 限定的時間內完成。以下請參照圖4，圖4為本發明的非易失性存儲器的多階重新排序方法的一實施 例的動作流程圖。並請同時參照圖5A 圖5C，圖5A 圖5C為本發明的非易失性存儲器的 多階重新排序方法的實施例的動作示意圖。在本實施例中，其步驟包括首先，當一邏輯區塊地址需要進行重新排序時，將該 邏輯區塊地址所對應的存儲區塊切分為多個子區塊(步驟S410)。例如圖:3B所示，邏輯區塊地址LBAN所對應的三個物理區塊地址PBAO PBA2需要進行重新排序。在本實施例中 是藉由建立一「重新排序狀態表」來管理多階重新排序的階段狀態，以確保全部子區塊都可 以完成重新排序。因此，步驟S410將要進行重新排序的邏輯區塊地址登記於重新排序狀態 表中。然而，管理多階重新排序的階段狀態的方式並不以此為限。例如，在其他實施例中可 以使用暫存器來記錄多階重新排序的目前階段狀態。如圖5A所示，非易失性存儲器中邏輯區塊地址LBAN所對應的物理區塊地址 PBAO PBA2可被切割為4個子區塊SO S3，而重新排序狀態表可如下列表1所示
邏輯區塊地址物理區塊地址重新排序階段LBANPBAO0PBAlPBA2表 1重新排序狀態表可包括邏輯地址欄位、物理地址欄位以及重新排序欄位。其中「邏 輯地址」欄位記錄需進行重新排序的邏輯區塊地址，「物理地址」欄位記錄邏輯區塊地址所 對應的物理區塊地址，另外「重新排序階段」欄位則記錄多階重新排序中目前的階段狀態。 例如，重新排序階段欄位可記錄在子區塊SO S3中目前已完成重新排序的子區塊的名稱 或是數量，或是記錄在子區塊SO S3中尚待進行重新排序的子區塊的名稱或是數量。在 本實施例中表1所示重新排序階段欄位被用來記錄多階重新排序中的目前階段狀態，其中 「0」表示目前為第1個階段狀態。子區塊SO將會在此第1個階段狀態中被重新排序，而其 他子區塊Sl S3則不會被重新排序。在此，重新排序狀態表是被建立在一個存儲裝置中， 而這個存儲裝置可以是動態存儲器或是靜態存儲器。另外請特別注意，分割的子區塊的數目不一定要與本實施例相同為4個。在本發 明的精神中，子區塊的數目可依據實際的狀況來分割，而至少為1個。舉例來說，可依物理 區塊地址所對應的數據區塊的大小來切割，當數據區塊越大時所需切割出的子區塊數目越 多，相反地，當數據區塊越小時所需切割出的子區塊數目越少。接著，在一額定忙碌期限內，執行一主機命令，以及對上述分割出的子區塊中的一 個子區塊進行重新排序(步驟S420)。其中，額定忙碌期限為非易失性存儲器執行任何數據 存取時所預設的規格值(例如250毫秒)，而主機命令可能是主機所發出要對某一邏輯區塊 地址進行存取的要求。一般而言，步驟S420所述主機命令所存取的邏輯區塊地址以及進行重 新排序的邏輯區塊地址二者可以是不相同的。非易失性存儲器必須在額定忙碌期限內完成主 機命令的相關操作。舉例來說，若主機命令指示對邏輯區塊地址LBAN進行數據的寫入，則非 易失性存儲器裝置必須在250毫秒內完成對邏輯區塊地址LBAN的寫入操作，並將所處忙碌狀 態解除並回報給主機。然而，一般寫入的動作均少於額定忙碌期限(例如僅需120毫秒)即 可完成，此時便可利用剩餘的時間(130毫秒)進行邏輯區塊地址LBAN的部分重新排序。例如，如圖5A所示可先將邏輯區塊地址LBAN所對應存儲區塊的子區塊SO進行重 新排序。也就是說，將物理區塊地址PBAO、PBAl與PBA2的子區塊SO的數據讀出並進行更 新操作，然後將更新後的數據寫入到另一數據區塊中(例如物理區塊地址PBA100所對應的數據區塊)。另外，值得注意的是，主機命令所指示執行的數據存取動作並不限定於需要進 行重新排序的邏輯區塊地址(亦即邏輯區塊地址LBAN)，當主機命令所指示對邏輯區塊地 址LBAN以外的邏輯區塊地址進行存取時，亦可利用剩餘的時間對邏輯區塊地址LBAN進行 重新排序。完成子區塊SO的重新排序操作後，表1所示重新排序階段欄位會被更新為「1」， 表示目前為第2個階段狀態而準備對下一個子區塊Sl進行重新排序。類似地，當非易失性存儲器因執行另一主機命令而處於另一個忙碌期間時，非易 失性存儲器必須在另一額定忙碌期限(以下稱第二期限)內完成所述另一主機命令的相關 數據存取操作。若完成所述另一主機命令的相關操作後亦有剩餘的時間，則可以在所述第 二期限內對上述分割出的子區塊Sl S3中的另一個子區塊進行重新排序(步驟S430)。 如圖5B所示，可利用剩餘時間對子區塊Sl進行重新排序，而將子區塊Sl的已更新數據寫 入到物理區塊地址PBA100對應的數據區塊中。完成子區塊Sl的重新排序操作後，表1所 示重新排序階段欄位會被更新為「2」，表示目前為第3個階段狀態而準備對下一個子區塊 S2進行重新排序。此時重新排序狀態表所紀錄的內容可如下列表2所示
權利要求
1.一種非易失性存儲器裝置的多階重新排序方法，包括當一邏輯區塊地址需要進行重新排序時，將該邏輯區塊地址所對應的存儲區塊切分為 多個子區塊；在一額定忙碌期限內，執行一主機命令，以及對所述多個子區塊中的一個子區塊進行 重新排序；以及在另一額定忙碌期限內，執行另一主機命令，以及對所述子區塊中的另一個子區塊進 行重新排序。
2.根據權利要求1所述的非易失性存儲器裝置的多階重新排序方法，還包括建立一重新排序狀態表，其中該重新排序狀態表包含一邏輯地址欄位與一重新排序階 段欄位；以及當該邏輯區塊地址需要進行重新排序時，將該邏輯區塊地址登記於該重新排序狀態表 的邏輯地址欄位。
3.根據權利要求2所述的非易失性存儲器裝置的多階重新排序方法，還包括當所述多個子區塊全部完成重新排序時，將該邏輯區塊地址從該重新排序記錄表中刪除。
4.根據權利要求2所述的非易失性存儲器裝置的多階重新排序方法，其中該重新排序 狀態表還包含一物理地址欄位，以記錄該邏輯區塊地址所對應的物理區塊地址。
5.根據權利要求2所述的非易失性存儲器裝置的多階重新排序方法，其中該重新排序 階段欄位記錄所述多個子區塊中尚待進行重新排序的子區塊。
6.根據權利要求2所述的非易失性存儲器裝置的多階重新排序方法，其中該重新排序 階段欄位記錄所述多個子區塊中已完成重新排序的子區塊。
7.根據權利要求2所述的非易失性存儲器裝置的多階重新排序方法，其中該重新排序 階段欄位記錄多階重新排序中的目前階段狀態。
8.根據權利要求2所述的非易失性存儲器裝置的多階重新排序方法，其中該重新排序 狀態表建立在一存儲裝置中。
9.根據權利要求8所述的非易失性存儲器裝置的多階重新排序方法，其中該存儲裝置 為靜態存儲器或動態存儲器。
10.一種非易失性存儲器控制裝置，用以存取一非易失性存儲器，包括一控制器，耦接該非易失性存儲器，當一邏輯區塊地址需要進行重新排序時，將該邏輯 區塊地址所對應的存儲區塊切分為多個子區塊，在一額定忙碌期限內，執行一主機命令，以 及對所述多個子區塊中的一個子區塊進行重新排序，並在另一額定忙碌期限內，執行另一 主機命令，以及對所述多個子區塊中的另一個子區塊進行重新排序。
11.根據權利要求10所述的非易失性存儲器控制裝置，還包括一存儲裝置，耦接該控制器，建立一重新排序狀態表，其中該重新排序狀態表包含一邏 輯地址欄位與一重新排序階段欄位，當該邏輯區塊地址需要進行重新排序時，將該邏輯區 塊地址登記於該重新排序狀態表的邏輯地址欄位。
12.根據權利要求11所述的非易失性存儲器控制裝置，其中該存儲裝置在所述多個子 區塊全部完成重新排序時，將該邏輯區塊地址自該重新排序記錄表中刪除。
13.根據權利要求11所述的非易失性存儲器控制裝置，其中該重新排序狀態表還包含一物理地址欄位，以記錄該邏輯區塊地址所對應的物理區塊地址。
14.根據權利要求11所述的非易失性存儲器控制裝置，其中該重新排序階段欄位記錄 所述多個子區塊中尚待進行重新排序的子區塊。
15.根據權利要求11所述的非易失性存儲器控制裝置，其中該重新排序階段欄位記錄 所述多個子區塊中已完成重新排序的子區塊。
16.根據權利要求11所述的非易失性存儲器控制裝置，其中該重新排序階段欄位記錄 多階重新排序中的目前階段狀態。
17.根據權利要求11所述的非易失性存儲器控制裝置，其中該存儲裝置為靜態存儲器 或動態存儲器。
18.根據權利要求10所述的非易失性存儲器控制裝置，還包括 一傳輸接口，耦接該控制器，用以接收該主機命令。
全文摘要
本發明提供一種非易失性存儲器控制裝置及其多階重新排序方法。其中該多階重新排序方法，其步驟包括當一邏輯區塊地址需要進行重新排序時，將邏輯區塊地址所對應的存儲區塊切分為多個子區塊。接著，在一額定忙碌期限內，執行一主機命令，以及對上述子區塊中的一個子區塊進行重新排序。最後，在另一額定忙碌期限內，執行另一主機命令，以及對上述子區塊中的另一個子區塊進行重新排序。
文檔編號G06F12/06GK102117246SQ200910215389
公開日2011年7月6日 申請日期2009年12月31日 優先權日2009年12月31日
發明者邱文智, 陳孟豪 申請人:點序科技股份有限公司