快闪存储装置及快闪存储装置的运作方法

摘要

本发明提供一种快闪存储装置。于一实施例中，该快闪存储装置包括一快闪存储器以及一控制器。该快闪存储器包括多个区块，其中每一区块包括多个页以供储存数据，每一页具有一实体地址。该控制器划分一主机所运用的多个逻辑地址为多个逻辑地址区间，建立多个地址链接分表以分别储存这些逻辑地址区间所包含的逻辑地址与该快闪存储器的多个实体地址的对应关系，储存这些地址链接分表于该快闪存储器中，整合这些地址链接分表为一地址链接表，并依据该地址链接表将该主机指示的逻辑地址转换为实体地址。

说明书

技术领域

本发明有关快闪存储器，特别是有关快闪存储器的实体地址与逻辑地址间的转换。

背景技术

快闪存储器为一种可由电编程及清除其数据的非挥发性存储器。快闪存储器主要用来作存储卡及通用串行总线(Universal Serial Bus，USB)装置，以供电脑及其它数字产品的一般性数据储存。快闪存储器的制造成本远低于电气可擦拭可规化式只读存储器(Electrically-Erasable Programmable Read-Only Memory，EEPROM)的成本，因此成为市场上的主流产品。快闪存储器的应用范围包括掌上型电脑(PDA)、笔记本电脑、数字音乐播放器、数字相机、以及移动电话。

主机一般利用快闪存储装置进行数据储存。一般的快闪存储装置，例如存储卡，包括一控制器及至少一快闪存储器。当主机欲将数据存入快闪存储装置时，便将欲存入的地址与数据发送至快闪存储装置。主机指定的地址称之为逻辑地址(logical address)，而快闪存储器本身的地址称之为实体地址(physical address)。由于逻辑地址与实体地址并不相同，因此快闪存储装置的控制器必须先将主机指定的逻辑地址转换为实体地址，再将欲存入的数据写入至快闪存储器的实体地址。同样的，当主机欲将数据由快闪存储装置读取时，便将欲读取的地址发送至快闪存储装置。此时，快闪存储装置的控制器必须事先将主机指定的逻辑地址转换为实体地址，再将欲读取的数据由快闪存储器的实体地址读出，以便回传至主机。

由于快闪存储装置的控制器必须进行实体地址与逻辑地址的转换，因此控制器一般而言会以一地址链接表(link table)储存逻辑地址与实体地址的对应关系。如此控制器便可参考地址链接表中的对应关系以进行实体地址与逻辑地址的转换。地址链接表必须记录快闪存储器的所有实体地址的对应关系，当快闪存储器的容量愈大时，地址链接表的数据量亦愈大。一般而言，地址链接表是储存于快闪存储器中，当快闪存储装置启动后，控制器再由快闪存储器加载地址链接表。每当主机存取快闪存储器而造成地址链接表中对应关系的变动，便需重新于快闪存储器中储存新的地址链接表。在主机高频率的存取下，经常储存地址链接表是相当耗费控制器的效能，从而减少数据传输的速率，例如由每秒20MB减少为每秒2MB。因此，需要一种有效地管理地址链接表的方法，以提升快闪存储装置的效能。

发明内容

有鉴于此，本发明的目的在于提供一种快闪存储装置，以解决现有技术存在的问题。于一实施例中，该快闪存储装置包括一快闪存储器(flash memory)以及一控制器(controller)。该快闪存储器包括多个区块，其中每一区块包括多个页以供储存数据，每一页具有一实体地址。该控制器划分一主机所运用的多个逻辑地址为多个逻辑地址区间，建立多个地址链接分表(Partial link table)以分别储存这些逻辑地址区间所包含的逻辑地址与该快闪存储器的多个实体地址的对应关系，储存这些地址链接分表于该快闪存储器中，整合这些地址链接分表为一地址链接表(Linktable)，并依据该地址链接表将该主机指示的逻辑地址转换为实体地址。

本发明提供一种快闪存储装置的运作方法。于一实施例中，一快闪存储器包括多个区块，每一区块包括多个页以供储存数据，且每一页具有一实体地址。首先，划分一主机所运用的多个逻辑地址为多个逻辑地址区间。接着，建立多个地址链接分表(Partial link table)以分别储存这些逻辑地址区间所包含的逻辑地址与该快闪存储器的多个实体地址的对应关系。接着，储存这些地址链接分表于该快闪存储器中。接着，整合这些地址链接分表为一地址链接表(Link table)。最后，依据该地址链接表将该主机指示的逻辑地址转换为实体地址。

为了让本发明的上述和其它目的、特征、和优点能更明显易懂，下文特举数较佳实施例，并配合所附图标，作详细说明如下：

附图说明

图1为依据本发明的数据储存系统的区块图；

图2A为依据本发明的地址链接表的一实施例；

图2B为依据本发明的对应于图2A的地址链接表的索引表的示意图；

图3A为依据本发明的控制器于快闪存储器储存地址链接分表的实施例的示意图；

图3B为依据本发明的对应于图3A的实施例的地址链接表的示意图；

图4为依据本发明的控制器将数据写入快闪存储器的流程图；；

图5为依据本发明的控制器清除快闪存储器的区块中储存的数据的方法的流程图；

图6为依据本发明的无效表的一实施例；

图7为依据本发明的快闪存储器所包含的数据区块的一实施例的示意图；以及

图8为依据本发明的重建地址链接表的方法的流程图。

具体实施方式

图1为依据本发明的一数据储存系统100的区块图。数据储存系统100包括主机102及快闪存储装置104。快闪存储装置104为主机102储存数据。于一实施例中，快闪存储装置104包括一控制器112及一快闪存储器114。快闪存储器114包括多个区块(block)121～12M，用以储存数据。快闪存储器114的每一区块121～12M包括多个页(page)供储存数据，每一页具有一实体地址。控制器112中储存有一地址链接表(Link table)106，该地址链接表106中储存主机102运用的逻辑地址与快闪存储器114运用的实体地址之间的对应关系。当主机102欲存取快闪存储器114时，控制器112将主机欲存取的逻辑地址依据地址链接表106转换为实体地址，再依据转换所得的实体地址为主机102存取快闪存储器114。

图2A为依据本发明的地址链接表200的一实施例。地址链接表200记录主机102运用的所有逻辑地址所对应的快闪存储器114的实体地址。举例来说，逻辑地址L_A1被对应至实体地址P_Q，逻辑地址L_AN被对应至实体地址P_M，而逻辑地址L_KN被对应至实体地址P_W。同时，控制器112将主机102所运用的逻辑地址范围L_A1～L_KN依次划分为多个逻辑地址区间201、202、203、…、20K，每一逻辑地址区间包含多个逻辑地址。例如，逻辑地址区间201包含逻辑地址L_A1～L_AN，逻辑地址区间202包含逻辑地址L_B1～L_BN，而逻辑地址区间20K包含逻辑地址L_K1～L_KN。因此，地址链接表200可依逻辑地址区间201、202、…、20K划分为多个逻辑地址分表，分别储存逻辑地址区间201、202、…、20K所包含的逻辑地址L_A1～L_AN、L_B1～L_BN、…、L_K1～L_KN与多个实体地址的对应关系。如此，逻辑地址分表便仅需要较小的存储空间以供储存。

控制器112将多个地址链接分表201、202、…、20K分别储存于快闪存储器114中。于一实施例中，地址链接分表201、202、…、20K分别储存于快闪存储器114的一储存页(page)，而控制器112还将这些地址链接分表201、202、…、20K的储存页的实体地址记录于一索引表(Index table)表中。图2B为依据本发明的对应于图2A的地址链接表200的索引表250的示意图。由索引表250中可见，对应于逻辑地址区间L_A1～L_AN、L_B1～L_BN、…、L_K1～L_KN的地址链接分表201、202、…、20K的储存页的实体地址分别为P_A、P_B、…、P_K。当快闪存储装置104被主机102重新启动时，控制器112便可自快闪存储器114的地址为P_A、P_B、…、P_K的储存页读取多个地址链接分表201、202、…、20K，并将地址链接分表201、202、…、20K整合为单一的地址链接表200后储存于控制器112的缓存器或随机存取存储器中。如此，控制器112便可依据地址链接表200将主机102指示的逻辑地址转换为实体地址。

图3A为依据本发明的控制器112于快闪存储器114储存地址链接分表的实施例的示意图。假设快闪存储器114包括两区块X及Y，其中区块X包括实体地址为X₁～X_M的储存页，而区块Y包括实体地址Y₁～Y_M为的储存页。图3B为依据本发明的对应于图3A的实施例的地址链接表350的示意图。储存于控制器112中的地址链接表350由多个地址链接分表组合而成，包括逻辑地址范围为L_A1～L_AN的地址链接分表352、逻辑地址范围为L_I1～L_IN的地址链接分表354、以及逻辑地址范围为L_K1～L_KN的地址链接分表356。假设快闪存储装置104首先自主机102接收到逻辑地址分别为L_A1、L_A3、L_A4、L_I1、L_I4的数据D₁、D₂、D₃、D₄、以及D₅。控制器112首先将数据D₁、D₂、D₃分别写入快闪存储器114的区块X的实体地址为X₁、X₂、X₃的储存页，并将新写入的数据D₁、D₂、D₃的逻辑地址L_A1、L_A3、L_A4与实体地址X₁、X₂、X₃的对应关系记录于图3B的地址链接分表352中。

接着，控制器112要将数据D₄及D₅写入快闪存储器114的区块X。然而，数据D₄及D₅的逻辑地址L_I1及L_I4与之前写入的数据D₁、D₂、D₃的逻辑地址L_A1、L_A3、L_A4位于不同的地址链接分表。因此，控制器112先将之前数据D₁、D₂、D₃的地址链接分表352储存于区块X的实体地址X₄的储存页作为地址链接分表T₁，并于索引表250中记录地址链接分表352的最新储存页实体地址X₄。接着，控制器112再将数据D₄及D₅分别写入区块X的实体地址为X₅、X₆的储存页，并将新写入的数据D₄、D₅的逻辑地址L_I1、L_I4与实体地址X₅、X₆的对应关系记录于图3B的地址链接分表354中。假设控制器112接着发现后续接收的数据的逻辑地址与之前写入的数据D₄及D₅的逻辑地址L_I1及L_I4位于不同的地址链接分表，因此控制器112接着将之前数据D₄及D₅的地址链接分表354储存于区块X的实体地址X₇的储存页作为地址链接分表T_P，并于索引表250中记录地址链接分表354的最新储存页实体地址X₇。当控制器112发现区块X的所有储存页均已用于储存数据，控制器112便将目前维护的索引表储存于区块X的最后一储存页X_M。之后，控制器112再将自主机102接收的其它新数据以同一方式写入另一区块Y的储存页Y₁～Y_M中。

图3A和图3B的实施例的数据写入方法可被归纳为一流程图。图4为依据本发明的控制器112将数据写入快闪存储器114的方法400的流程图。首先，控制器112自主机102接收欲写入一目标逻辑地址的数据(步骤402)。接着，控制器112检查该目标逻辑地址是否位于一先前写入数据所对应的一目标地址链接分表的逻辑地址区间(步骤404)。若该目标逻辑地址位于该目前地址链接分表的逻辑地址区间(步骤404)，则控制器112将该数据写入快闪存储器的一目标实体地址的储存页(步骤406)，并将该目标实体地址与该目标逻辑地址的对应关系记录于控制器112中的该目前地址链接分表(步骤408)。若该目标逻辑地址不位于该目前地址链接分表的逻辑地址区间(步骤404)，则控制器112将该目前地址链接分表储存于快闪存储器114的一储存页(步骤412)，将该目前地址链接表的该储存页的实体地址记录于控制器112的一索引表中(步骤414)，并将该目前地址链接分表更新为该目标逻辑地址所对应的地址链接分表(步骤416)。接着，控制器112再将该数据写入快闪存储器的一目标实体地址的储存页(步骤406)，并将该目标实体地址与该目标逻辑地址的对应关系记录于控制器112中的该目前地址链接分表(步骤408)。

图5为依据本发明的控制器112清除快闪存储器114的区块中储存的数据的方法500的流程图。快闪存储器114的多个区块121～12M各自具有一无效表(Invalidtable)，每一无效表分别储存相对应的区块的所有实体地址与逻辑地址的对应关系。图6为依据本发明的无效表600的一实施例。由图中可见，无效表600储存相对应的区块的所有实体地址P₁～P_M与逻辑地址L_X～L_R的对应关系。于一实施例中，控制器112维护这些无效表，并将这些无效表分别储存于对应的区块的最后一页中。

首先，控制器112决定欲清除的一目标区块(步骤502)。接着，控制器112自该目标区块的最后一页读取该目标区块的一无效表(步骤504)。接着，控制器112读取该目标区块的一目标页(步骤506)，并判断该目标页是一无效页或一有效页。当该目标页所储存的数据对应的逻辑地址已经更新而改储存于快闪存储器114中的其它储存页时，该目标页被判断为一无效页。否则，该目标页被判断为一有效页。控制器112首先依据该目标区块的无效表找出该目标页的第一实体地址所对应的第一逻辑地址(步骤508)。接着，控制器112找出该第一逻辑地址于控制器112的地址链接表106中所对应的第二实体地址。若该第二实体地址与该第一实体地址相同(步骤510)，则该目标页所储存的数据并未由快闪存储器114中的其它储存页所储存的数据所取代，因此控制器112归类该目标页为一有效页(步骤512)。若该第二实体地址与该第一实体地址不相同(步骤510)，则该目标页所储存的数据已由快闪存储器114中的其它储存页所储存的数据取代，因此控制器112归类该目标页为一无效页(步骤514)。

接着，控制器112检查是否该目标区块的所有页均已被归类完毕(步骤516)。若目标区块尚有储存页位被归类，则控制器112选取该目标区块的另一页作为该目标页(步骤518)，并重新执行步骤506～510，以归类该新目标页。步骤506～步骤518的循环将重复执行，直到目标区块的所有页均已被归类完毕为止(步骤516)。最后，控制器112将该目标区块的所有有效页的数据依图4的写入方法400写入一新区块(步骤520)。当目标区块的所有有效页的数据均被写入新区块后，目标区块的所有页均已未储存有用的数据，因此控制器112可清除该目标区块的数据(步骤522)。

图7为依据本发明的快闪存储器700所包含的数据区块的一实施例的示意图。快闪存储器700包括多个区块701、…、70(K-1)、70K、…、70M，其中区块701～70(K-1)的所有页均已被写入数据，区块70K仅有部分页Z₁～Z_L被写入数据而其它储存页Z_M～Z_N为未写入数据的空白页，而区块70(K+1)～70M为空白区块。由于数据区块701～70(K-1)的所有页均已被写入数据，因此数据区块701～70(K-1)的最后一页均储存有索引表，其中最后的数据区块70(K-1)的索引表为最新版本的索引表。

假设当控制器112在写入数据D_U至快闪存储器700的区块70K的储存页Z_L后，快闪存储装置104突然遭断电。因此，当快闪存储装置104重新启动后，控制器112必须依照快闪存储器700的数据重构一地址链接表106，以供进行逻辑地址与实体地址的转换。图8为依据本发明的重建地址链接表的方法800的流程图。首先，控制器112自快闪存储器700的多个区块搜寻仅写入部分数据的一目标区块(步骤802)。由图7的快闪存储器700可见，仅写入部分数据的目标区块为区块70K。接着，控制器112自该目标区块70K之前一区块70(K-1)的最后一页Y_N读取最新版本的一索引表(步骤804)。接着，控制器112依据该索引表找出所有地址链接分表的储存页的实体地址(步骤806)。接着，控制器112自这些储存页读取多个地址链接分表，以整合为一地址链接表106(步骤808)。

然而，步骤804中之前一区块70(K-1)的最后一页Y_N所储存的索引表中记录的储存页并非完全都储存最新的地址链接分表。举例来说，区块70K中的地址链接分表T₁～T_Q就不记载于前一区块70(K-1)的最后一页Y_N所储存的索引表中。因此，控制器112依据该目标区块70K储存的所有地址链接分表T₁～T_Q更新控制器中的地址链接表106(步骤810)。然而，目标区块70K中尚有最后数储存页Z_J、Z_L、Z_M的对应关系未被记录于控制器112的地址链接表106中。因此，控制器112首先决定该目标区块70K的一最后地址链接表T_Q的储存页Z₁至一第一空白页Z_M之间的多个数据储存页Z_J～Z_L(步骤812)。接着，控制器112依据这些数据储存页Z_J～Z_L的逻辑地址与实体地址的对应关系更新相对应的一目标地址链接分表，并将该地址链接分表写入第一空白页Z_M(步骤814)。最后，控制器112依据这些数据储存页Z_J～Z_L相对应的目标地址链接分表更新控制器112中的地址链接表106(步骤816)。因此，控制器112已重建了最新版本的地址链接表106，并可依据地址链接表106进行逻辑地址与实体地址的转换。

虽然本发明已以较佳实施例揭露如上，然而其并非用以限定本发明，任何熟悉此项技术者，在不脱离本发明的精神和范围内，当可作出种种等同的改变或替换，因此本发明的保护范围当视后附的本申请权利要求所界定的为准。