CN101409108B - 平均磨损方法及使用此方法的控制器 - Google Patents

Abstract

本发明提出一种用于非易失性存储器的平均磨损方法，其中易失性存储器实质上分割为多个区块且此些区块至少分组为数据区、备用区、替换区与暂态区，此平均磨损方法包括：当从备用区中提取区块时依据不同的用途来提取区块，以及执行耗损调整程序。

Description

平均磨损方法及使用此方法的控制器 

技术领域

本发明是有关于一种平均磨损方法，且特别是有关于一种用于非易失性存储器的平均磨损方法以及使用此方法的控制器。 

背景技术

数字相机、手机相机与MP3在这几年来的成长十分迅速，使得消费者对储存媒体的需求也急速增加，由于闪存(Flash Memory)具有数据非易失性、省电、体积小与无机械结构等的特性，适合可携式应用，最适合使用于这类可携式由电池供电的产品上。除了可携式产品内建存储器需要之外，对于小型存储卡与随身碟等外接式产品来说，每个人可能同时拥有多个随身碟与小型存储卡，所以市场规模较那些设备更大。因此，近年闪存产业成为电子产业中相当热门的一环。 

虽然闪存具有可写入、可抹除、以及断电后仍可保存数据的优点。然而，闪存区块的抹除次数是有限的，例如存储器区块抹除一万次后就会磨损。当存储器区块磨损导致储存容量的部分的使用损失或性能的明显退化时，会造成使用者储存数据的损失或无法储存数据等不利影响。 

闪存区块的磨损取决于每一区块中被程序(program)或抹除的次数。也就是，若一区块仅被程序(或者写入)一次，而后未被再程序时，则此区块的磨损将相对地低，反之，若一区块被重复地程序与抹除时，则此区块的磨损就会相对地高。例如，当存取存储器区块的主机重复地使用相同逻辑区块地址来写入数据时，则闪存内的相同物理位置的区块会被重复地写入与抹除。 

当某些区块被磨损同时其它区块相对地未磨损时，一般而言磨损区块的存在会降低闪存的性能。除了磨损区块本身性能的退化之外，当未磨损的区块不足以储存数据时，闪存整体的性能亦会降低。也就是，当闪存发生超过门坎数的磨损区块时，即使仍有其它区块未磨损，然，此闪存会被判为无法再使用。当实质上未磨损区块被视为无法使用时，将为造成资源实际上的浪费。 

为了增加闪存的寿命，会尽可能平均地使用闪存的区块。一般来说，闪存的区块会区分为数据区与备用区，传统平均磨损的方法是循序地在闪存每执行一段时间时将数据区中的区块与备用区中的区块逻辑上交换，以期使得抹除次数较少的区块可被交换至备用区以供程序(或写入)使用。然而，此种依序地将数据区中的区块与备用区中的区块逻辑上交换的方式，无法确保交换的是抹除次数较少的区块，若所交换的是抹除次数较多个区块反而更加速其磨损，因此平均磨损的效果有限。 

基此，有需要发展一种平均磨损方法，以有效地延长闪存的寿命。 

发明内容

本发明提供一种用于非易失性存储器的平均磨损方法，其可有效地平均存储器区块的磨损，以延长存储器的使用寿命。 

本发明提供一种控制器，其可执行用于非易失性存储器的平均磨损方法，由此有效地平均存储器区块的磨损，以延长存储器的使用寿命。 

本发明提出一种用于非易失性存储器的平均磨损方法，其中该非易失性存储器实质上分割为多个区块且该些区块至少分组为数据区、备用区、替换区与暂态区，该平均磨损方法包括：a.在该备用区中区分一热区，以标记在该备用区的区块之中抹除次数相对多的至少一个区块；b.当从该备用区中提取用于该替换区的第一区块时，倘若该第一区块的抹除次数≤该热区的区块的抹除次数加第一门坎值时搬移该第一区块至该替换区，倘若该第一区块的抹除次数＞该热区的区块的抹除次数加该第一门坎值时搬移该热区中的区块的其中之一至该替换区并且将该第一区块标记为该热区的区块；以及c.执行耗损调整程序，其中该耗损调整程序包括：将该热区中该至少一个区块的其中之一搬移至该数据区，同时将该数据区的第三区块搬移至该备用区且将该第三区块标记为该热区的区块，其中该第三区块是在该数据区之中具有相对少抹除次数的区块。 

在本发明的一实施例中，上述的平均磨损方法还包括：从备用区提取用于暂态区的第二区块，其中第二区块是备用区之中具有相对少抹除次数的区块。 

在本发明的一实施例中，上述的平均磨损方法，还包括：当热区的区块的抹除次数＞所有区块的抹除次数之中最大抹除次数与最小抹除次数的中间 值加第二门坎值时则将计数值加1；以及当计数值大于第三门坎值时，则执行步骤c并且重置计数值。 

在本发明的一实施例中，上述的平均磨损方法还包括：当执行写入或抹除指令时，则将计数值加1；以及当计数值大于第三门坎值时，则执行步骤c并且重置计数值。 

在本发明的一实施例中，上述的平均磨损方法还包括：当热区的区块的抹除次数＞所有区块的抹除次数之中最大抹除次数与最小抹除次数的中间值加第四门坎值时则执行步骤c。 

在本发明的一实施例中，上述的平均磨损方法还包括以随机方式执行步骤c。 

在本发明的一实施例中，上述的平均磨损方法还包括建立对应数据区的至少一个区域的至少一个数据区块抹除次数表、备用区块抹除次数表、替换区块抹除次数表与暂态区块抹除次数表，其分别用以记录数据区、备用区、替换区与暂态区的区块的抹除次数。 

在本发明的一实施例中，上述的建立至少一个数据区块抹除次数表是以对应逻辑物理对映表来建立，其中至少一个数据区块抹除次数表是对应逻辑物理对映表来分别地记录数据区的区块的抹除次数。 

在本发明的一实施例中，上述的平均磨损方法还包括执行主机端正常的写入指令来完成步骤c。 

本发明提供一种控制器，其适用于储存装置，该储存装置的非易失性存储器实质上分割为多个区块并且该些区块至少分组为数据区、备用区、替换区与暂态区，该控制器包括：非易失性存储器接口，用以存取该非易失性存储器；以及存储器管理模块，用以管理该非易失性存储器，其中该存储器管理模块会执行平均磨损方法，该平均磨损方法包括：a.在该备用区中区分一热区，以标记在该备用区的区块之中抹除次数相对多的至少一个区块；b.当从该备用区中提取用于该替换区的第一区块时，倘若该第一区块的抹除次数≤该热区的区块的抹除次数加第一门坎值时搬移该第一区块至该替换区，倘若该第一区块的抹除次数＞该热区的区块的抹除次数加该第一门坎值时搬移该热区中的区块的其中之一至该替换区并且将该第一区块标记为该热区的区块；以及c.执行耗损调整程序，其中该耗损调整程序包括：将该热区中该至少一个区块的其中之一搬移至该数据区，同时将该数据区的第三区块搬移 至该备用区且将该第三区块标记为该热区的区块，其中该第三区块是在该数据区之中具有相对少抹除次数的区块。 

在本发明的一实施例中，上述的平均磨损方法还包括：从备用区提取用于暂态区的第二区块，其中第二区块是备用区之中具有相对少抹除次数的区块。 

在本发明的一实施例中，上述的平均磨损方法，还包括：当热区的区块的抹除次数＞所有区块的抹除次数之中最大抹除次数与最小抹除次数的中间值加第二门坎值时则将计数值加1；以及当计数值大于第三门坎值时，则执行步骤c并且重置计数值。 

在本发明的一实施例中，上述的平均磨损方法还包括：当执行写入或抹除指令时，则将计数值加1；以及当计数值大于第三门坎值时，则执行步骤c并且重置计数值。 

在本发明的一实施例中，上述的平均磨损方法还包括：当热区的区块的抹除次数＞所有区块的抹除次数之中最大抹除次数与最小抹除次数的中间值加第四门坎值时则执行步骤c。 

在本发明的一实施例中，上述的平均磨损方法还包括以随机方式执行步骤c。 

在本发明的一实施例中，上述的平均磨损方法还包括执行主机端正常的写入指令来完成步骤c。 

在本发明的一实施例中，上述的平均磨损方法还包括当抹除或写入区块时，增加所抹除区块的抹除次数。 

本发明提出一种用于非易失性存储器的平均磨损方法，其中该非易失性存储器实质上分割为多个区块且该些区块至少分组为数据区、备用区与替换区，该平均磨损方法包括：a.在该备用区中区分一热区，以标记在该备用区的区块之中抹除次数相对多的至少一个区块；b.从该备用区提取用于该暂态区的第二区块，其中该第二区块是该备用区之中具有相对少抹除次数的区块；以及c.执行耗损调整程序，其中该耗损调整程序包括将该热区中该至少一个区块的其中之一搬移至该数据区，同时将该数据区的第三区块搬移至该备用区且将该第三区块标记为该热区的区块，其中该第三区块是在该数据区之中具有相对少抹除次数的区块。 

在本发明的一实施例中，还包括：当从该备用区中提取用于该替换区的 第一区块时，倘若第一区块的抹除次数≤热区的区块的抹除次数加第一门坎值时搬移第一区块至替换区，倘若第一区块的抹除次数＞热区的区块的抹除次数加第一门坎值时搬移热区中的区块的其中之一至替换区并且将第一区块标记为热区的区块。 

在本发明的一实施例中，上述的平均磨损方法还包括：当热区的区块的抹除次数＞区块的抹除次数之中最大抹除次数与最小抹除次数的中间值加第二门坎值时则将计数值加1；以及当计数值大于第三门坎值时，则执行步骤c并且重置计数值。 

在本发明的一实施例中，上述的平均磨损方法还包括：当执行写入或抹除指令时，则将计数值加1；以及当计数值大于第三门坎值时，则执行步骤c并且重置计数值。 

在本发明的一实施例中，上述的平均磨损方法，还包括：当热区的区块的抹除次数＞区块的抹除次数之中最大抹除次数与最小抹除次数的中间值加第四门坎值时则执行步骤c。 

本发明提供一种控制器，其适用于储存装置，该储存装置的非易失性存储器实质上分割为多个区块并且该些区块至少分组为数据区、备用区与替换区，该控制器包括：非易失性存储器接口，用以存取该非易失性存储器；缓冲存储器，用以暂时地储存数据；微处理单元，用以控制该控制器的整体运作；以及存储器管理模块，用以管理该非易失性存储器，其中该存储器管理模块会执行平均磨损方法，该平均磨损方法包括：a.在该备用区中区分一热区，以标记在该备用区的区块之中抹除次数相对多的至少一个区块；b.从该备用区提取用于该暂态区的第二区块，其中该第二区块是该备用区之中具有相对少抹除次数的区块；以及c.执行耗损调整程序，其中该耗损调整程序包括将该热区中该至少一个区块的其中之一搬移至该数据区，同时将该数据区的第三区块搬移至该备用区且将该第三区块标记为该热区的区块，其中该第三区块是在该数据区之中具有相对少抹除次数的区块。 

在本发明的一实施例中，上述的平均磨损方法还包括：当从该备用区中提取用于该替换区的第一区块时，倘若第一区块的抹除次数≤热区的区块的抹除次数加第一门坎值时搬移第一区块至替换区，倘若第一区块的抹除次数＞热区的区块的抹除次数加第一门坎值时搬移热区中的区块的其中之一至替换区并且将第一区块标记为热区的区块。 

在本发明的一实施例中，上述的平均磨损方法还包括：当热区的区块的抹除次数＞区块的抹除次数之中最大抹除次数与最小抹除次数的中间值加第二门坎值时则将计数值加1；以及当计数值大于第三门坎值时，则执行步骤c并且重置计数值。 

在本发明的一实施例中，上述的平均磨损方法还包括：当执行写入或抹除指令时，则将计数值加1；以及当计数值大于第三门坎值时，则执行步骤c并且重置计数值。 

本发明提供一种用于非易失性存储器的平均磨损方法，其中非易失性存储器实质上分割为多个区块且此些区块至少分组为数据区、备用区、替换区与暂态区，此平均磨损方法包括：a.在备用区中区分热区，以标记在备用区的区块之中抹除次数相对多的至少一个区块；b.从备用区中提取用于替换区的第一区块；c.以热区的抹除次数比对特定值为计数的判断条件；以及d.当计数值大于第三门坎值时，执行耗损调整程序，其中该耗损调整程序包括将该热区中该至少一个区块的其中之一搬移至该数据区，同时将该数据区的第三区块搬移至该备用区且将该第三区块标记为该热区的区块，其中该第三区块是在该数据区之中具有相对少抹除次数的区块。 

在本发明的一实施例中，上述的判断条件包括：当热区的区块的抹除次数＞特定值加第二门坎值时则将计数值加1。 

在本发明的一实施例中，上述的特定值为区块的抹除次数之中最大抹除次数与最小抹除次数的中间值。 

在本发明的一实施例中，上述的平均磨损方法还包括建立对应数据区的至少一个区域的至少一个数据区块抹除次数表、备用区块抹除次数表、替换区块抹除次数表与暂态区块抹除次数表，其分别用以记录数据区、备用区、替换区与暂态区的区块的抹除次数。 

本发明提出一种平均磨损方法，其可适时地平均使用存储器区块，由此平均存储器区块的磨损，以延长存储器的使用寿命。 

为让本发明的上述特征和优点能更明显易懂，下文特举较佳实施例，并配合所附图式，作详细说明如下。 

附图说明

图1A是根据本发明第一实施例绘示使用非易失性存储器储存装置的主机。 

图1B是绘示图1A所示非易失性存储器储存装置的详细方块图。 

图1C是根据本发明另一实施例绘示控制器的方块图。 

图2A与2B是根据本发明第一实施例绘示非易失性存储器124及其运作的详细方块图。 

图3是根据本发明第一实施例绘示平均磨损方法的流程图。 

图4A是根据本发明第一实施例绘示逻辑物理对映表与数据区块抹除次数表的示意图。 

图4B是根据本发明第一实施例绘示备用区块表与备用区块抹除次数表的示意图。 

图4C是根据本发明第一实施例绘示替换区块表与替换区块抹除次数表的示意图。 

图4D是根据本发明第一实施例绘示暂态区块表与暂态区块抹除次数表的示意图。 

图5是根据本发明第二实施例绘示平均磨损方法的流程图。 

图6是根据本发明第三实施例绘示平均磨损方法的流程图。 

图7是根据本发明第四实施例绘示平均磨损方法的流程图。 

图8是绘示本发明实施例的平均磨损方法可应用的装置的示意图。 

[主要元件标号说明] 

100：主机 

102：微处理器 

104：随机存取存储器 

106：输入/输出装置 

108：系统总线 

110：数据传输接口 

120：非易失性存储器储存装置 

122：控制器 

122a：存储器管理模块 

122b：非易失性存储器接口 

122c：主机传输接口 

122d：缓冲存储器 

122e：程序存储器 

122f：错误校正模块 

122g：电源管理模块 

122h：微处理单元 

124：非易失性存储器 

124-0、124-1、124-2、124-N：区块 

202：系统区 

204：数据区 

206：备用区 

208：替换区 

210：暂态区 

M、C、T：区块 

S1310、S1310’、S1310”、S1320、S1320’：步骤 

S301、S303、S305、S307、S309、S311、S313、S315、S317、S319、S321、S323、S317’、S323’：步骤 

401：逻辑物理对映表 

402：数据区块抹除次数表 

403：备用区块表 

404：备用区块抹除次数表 

405：替换区块表 

406：替换区块抹除次数表 

407：暂态区块表 

408：暂态区块抹除次数表 

802：USB快闪碟 

804：数字相机 

804a：SD卡 

804b：MMC卡 

804c：CF卡 

804d：记忆棒 

806：固态硬盘 

具体实施方式

非易失性存储器储存系统一般而言包括非易失性存储器与控制器(控制芯片)。通常非易失性存储器储存系统会与主机系统一起使用，以使主机系统可将数据写入至非易失性存储器储存系统或从非易失性存储器储存系统中读取数据。另外，亦有非易失性存储器储存系统是包括嵌入式非易失性存储器与可执行于主机系统上以实质地作为此嵌入式闪存的控制器的软件。 

[第一实施例] 

图1A是根据本发明第一实施例绘示使用非易失性存储器储存装置的主机。 

请参照图1A，主机100一般包括微处理器102、随机存取存储器(randomaccess memory，RAM)104、输入/输出(input/output，I/O)装置106、系统总线108以及数据传输接口110。必须了解的是，主机100可还包括其它元件，例如显示器装置或网络装置等。 

主机100可以是计算机、数字相机、摄影机、通信装置、音频播放器或视频播放器等系统。一般而言，主机100可实质地为可储存数据的任意系统。 

在本发明实施例中非易失性存储器储存装置120是通过数据传输接口110与主机100的其它元件电性连接。通过微处理器102、随机存取存储器104与输入/输出装置106的处理可将数据写入至非易失性存储器储存装置120或从非易失性存储器储存装置120中读取数据。 

图1B是绘示图1A所示非易失性存储器储存装置的详细方块图。 

请参照图1B，非易失性存储器储存装置120一般包括控制器122与非易失性存储器124。 

控制器122用以控制非易失性存储器储存装置120的整体运作，例如数据的储存、读取与抹除等。控制器122包括存储器管理模块122a、缓冲存储 器122d、微处理单元122h与非易失性存储器接口122b。 

存储器管理模块122a用以管理非易失性存储器124，例如执行平均磨损(wear leveling)方法、坏区块管理、维护对映表(mapping table)等。 

非易失性存储器接口122b用以存取非易失性存储器124，也就是主机100欲写入至的数据会经由非易失性存储器接口122b转换为非易失性存储器124所能接受的格式。 

缓冲存储器122d用以暂时地储存系统数据(例如对映表)或者主机所读取或写入的数据。在本实施例中，缓冲存储器122d为静态随机存取存储器(static random access memory，SRAM)。然而，必须了解的是，本发明不限于此，动态随机存取存储器(DRAM)、磁阻式存储器(MRAM)、相变化存储器(PRAM)或其它适合的存储器亦可应用于本发明。 

微处理单元122h用以控制控制器122的整体运作。 

非易失性存储器124用以储存数据。在本实施中非易失性存储器124为闪存，更具体来说，非易失性存储器124为多层存储单元(Multi Level Cell，MLC)反及(NAND)闪存。但必须了解的是，本发明不限于此，例如非易失性存储器124亦可为单层存储单元(Single Level Cell，SLC)反及闪存。 

在本发明另一实施例中，控制器还包括主机传输接口122c、程序存储器122e、错误校正模块122f与电源管理模块122g(如图1C所示的122’)。 

主机传输接口122c用以与主机100通讯，主机传输接口122c可以是USB接口、IEEE 1394接口、SATA接口、PCI Express接口、MS接口、MMC接口、SD接口、CF接口或IDE接口。 

程序存储器122e用以储存控制器所执行用以控制非易失性存储器储存装置120的程序码。 

错误校正模块122f用以计算错误校正码(error correcting code)来检查与校正主机所读取或写入的数据。 

电源管理模块122g用以管理非易失性存储器储存装置120的电源。 

非易失性存储器124通常实质上分割为多个物理区块(physicalblock)124-0至124-N，为方便说明以下将物理区块简称为区块。一般而言，在闪存中区块为抹除的最小单位。亦即，每一区块含有最小数目之一并被抹除的存储单元。每一区块通常会分割为数个页(page)。页通常为程序(program)的最小单元，但要特别说明的是于有些不同的闪存设计，最小的程序单位也 可为一个扇区(sector)大小，即一页中有多个扇区并以一扇区为程序的最小单元。换言之，页为写入数据或读取数据的最小单元。每一页通常包括使用者数据区D与冗余区R。使用者数据区用以储存使用者的数据，而冗余区用以储存系统的数据(例如，上述的ECC code)。 

为对应于磁盘驱动器的扇区(sector)大小，一般而言，使用者数据区D通常为512字节，而冗余区R通常为16字节。也就是，一页为一个扇区。然而，亦可以多个扇区形成一页，例如一页包括4个扇区。一般而言，区块可由任意数目的页所组成，例如64页、128页、256页等。区块124-0至124-N通常会被分组为数个区域(zone)，以区域来管理存储器某种程度上是彼此独立地操作以增加操作执行的平行程度且简化管理的复杂度。 

当非易失性存储器124的某些区块被持续地程序(例如重复地写入及抹除)时，此些区块一般而言会较未被持续地程序的区块更快磨损。为有效地平均非易失性存储器124内的区块的磨损，通过本发明所提出的平均磨损方法可自动地减少使用已被持续程序的区块而使用未被持续程序的区块，由此延长非易失性存储器124的寿命。 

以下将根据本发明并配合图式详细说明非易失性存储器的运作。必须了解的是，在以下描述中使用“提取”、“搬移”、“交换”等词来操作闪存区块是逻辑上的概念。也就是说，闪存区块的实际位置并未更动，而是逻辑上对闪存区块进行操作。 

图2A与2B是绘示非易失性存储器124及其运作的详细方块图。 

请参照图2A，在本发明实施例中，为了有效率地程序(即写入与抹除)非易失性存储器124，非易失性存储器124的区块124-1至124-N会在逻辑上分组为系统区202、数据区204与备用区206。一般来说，非易失性存储器124中属于数据区204的区块会占90％以上，剩下的才是系统区202与备用区206。 

系统区202中的区块用以记录系统数据，系统数据例如是关于非易失性存储器124的区域数、每一区域的区块数、每一区块的页数、逻辑物理对映表等。 

数据区204中的区块用以储存使用者的数据，一般来说就是主机100所操作的逻辑区块地址所对应的区块。 

备用区206中的区块是用以替换数据区204中的区块，因此在备用区206 中的区块为空的区块，即无记录数据或标记为已没用的无效数据。具体来说，由于若要对已写过数据位置再次写入数据时，必须先执行抹除的操作。然而，如前所述闪存写入单位为页，而抹除单位为区块。一个抹除的单位大于写入的单位，这表示若要执行区块抹除操作，必须先将欲抹除区块中的有效页复制至其它区块后才可进行。因此，当欲在数据区204中已写过数据位置的区块M中写入新数据时，一般会在备用区206中提取一区块C，然后将区块M中的有效数据复制至区块C且将新数据写入区块C后，将区块M抹除后搬移至备用区206同时将区块C搬移至数据区204。必须了解的是，将区块M抹除后搬移至备用区206同时将区块C搬移至数据区204是逻辑上将区块M关联于备用区206而将区块C关联于数据区204。其中本领域技术人员皆能了解数据区204中区块的逻辑关系可由逻辑物理对映表来维护。 

在本发明实施例中，为了更有效率地使用非易失性存储器124，区块124-1至124-N在逻辑上还分为替换区208与暂态区210。 

请参照图2B，替换区208是用以暂时存放准备替换数据区204的区块的区块。更详细而言，当上述备用区206的区块C被提取来取代数据区204的区块M时，在本发明实施例中会将新数据入至区块C，但不会立刻将区块M中的有效数据搬移至区块C而抹除区块M。此是因为，区块M中的有效数据有可能在下个操作中变成无效，因此立刻将区块M中的有效数据搬移至物理区块C会造成无谓的搬移。在本发明实施例中，会将写入新数据的区块C暂时地关联为替换区，并且在逻辑区块地址与物理区块地址的对映上会记录多个物理区块地址对应到一个逻辑区块地址的情况，也就是区块M与区块C的内容整合起来才是所对映逻辑区块的内容，由此提升区块的使用效率。此等母子区块(区块M与区块C)的关系可依据控制器122中缓冲存储器122d的大小而定，在本发明实施例中是以五组来实作。 

暂态区210的功能与替换区208类似。如上所述，在本发明实施例中是使用MLC NAND闪存。此MLC NAND闪存1页中可包括4个扇区，即1页中有4个512 bytes的扇区，共2K bytes。如上所述，闪存在写入时是以页为单位，因此在使用MLC NAND闪存的情况下每次必须程序4个扇区，由此当写入小量数据时会造成资源的浪费。在本发明实施例中，暂态区210是用以暂时存放此类少量数据。具体来说，如上所述当欲写入替换区208的区块C的数据为不满一个页的小量数据时，会从备用区206中提取一区块T，然后将此 小量数据写入至区块T并且将区块T关联为暂态区210。之后，当后续写入的数据量足够写入一页时再将此些数据写入至区块C，然后再将区块T抹除且从暂态区210中搬移至备用区206。 

值得一提的是，在非易失性存储器储存装置的运作期间上述区块的逻辑对映关系会在缓冲存储器122d中持续更新，并且例如在非易失性存储器储存装置结束运作或者每操作一定次数后将此些信息记录至系统区202的区块中。其中此些逻辑对映关系会以逻辑物理对映表、备用区块表、替换区块表与暂态区块表来记录，此些表格将在以下配合图4A-4D来详细说明。 

一般来说，经常会在数据区204与备用区206之间交换的区块称为动态数据区块。在本发明实施例中，使用替换区208与暂态区210的设计是为了使动态数据区块的使用更有效率。另外，在数据区204中往往有一些数据写入后就长时间未曾更动，例如数据区204中有100首MP3歌曲为使用者喜爱的音乐，写入后不曾再去更动。储存此类数据的区块称为静态数据区块。静态数据区块由于很少更动，因此其抹除次数会相对低。在本发明实施中，控制器122的存储器管理模块122a会执行平均磨损方法，以有效地平均区块124-1至124-N的磨损。 

图3是绘示上述控制器122所执行的平均磨损方法的流程图，其用于程序存储器区块时平均地使用存储器区块以达到平均磨损的目的。本发明的平均磨损方法包括依据不同的用途而根据不同的判断条件来从备用区中提取区块(步骤S1310)以及执行耗损调整程序(步骤S1320)。以下将配合图3详细说明平均磨损方法。 

请参照图3，为了平均区块的磨损，必须记录非易失性存储器124内区块124-1至124-N的抹除次数。在步骤S301中，当初始化非易失性存储器储存装置120时，会建立或加载至少一个数据区块抹除次数表、一备用区块抹除次数表、一替换区块抹除次数表与一暂态区块抹除次数表。具体来说，倘若非易失性存储器124的系统区202未储存此些抹除次数表时则会重新建立，倘若系统区202中储存有此些抹除次数表时，则将其加载至控制器122的缓冲存储器122d中。 

图4A是根据本发明实施例绘示逻辑物理对映表与数据区块抹除次数表的示意图。图4B是根据本发明实施例绘示备用区块表与备用区块抹除次数表的示意图。图4C是根据本发明实施例绘示替换区块表与替换区块抹除次数表 的示意图。图4D是根据本发明实施例绘示暂态区块表与暂态区块抹除次数表的示意图。 

请参照图4A，逻辑物理对映表401的位置为逻辑区块地址(logical blockaddress，LBA)，地址内的值为此LBA对应到非易失性存储器124内部的物理区块地址(physical block address，PBA)，也就是数据区204的区块。基此，建立一个与逻辑物理对映表相同维度大小的表格，称为数据区块抹除次数表402，此表格是为了记录所有逻辑物理对映表内对应的PBA的抹除次数。举例来说，逻辑物理对映表401中第3个地址LBA 2的值是100，而数据区块抹除次数表402第3个位置的值是50，则表示LBA 2对应到物理区块100，而物理区块100的抹除次数是50。值得一提的是，如上所述为了管理方便，一般会将非易失性存储器的物理区块分为数个区域(Zone)，因此实际上逻辑物理对映表会依据区域的数目而建立。例如，将物理区块分为8个区域时，则会建立8个逻辑物理对映表。在本发明中，亦会根据逻辑物理对映表的数目来建立相同数目的数据区块抹除次数表。为了方便说明，在本实施例中是以一个区域为例。 

在本发明实施中，当主机100不断存取逻辑物理对映表401内的区块时，控制器122会实时更新数据区块抹除次数表，并且会在抹除与写入区块的忙碌时间内，扫描整个数据区块抹除次数表402并记录抹除次数最少的区块。当如上述将非易失性存储器124分割为N个区域的情况下，控制器122会分别记录N个数据区块抹除次数表402内的具最少抹除次数的区块的抹除次数，再比较从N个数据区块抹除次数表402中所记录的每一最小抹除次数，然后记录具有最少抹除次数的区块。 

请参照图4B，备用区块表403是记录关联于备用区206的区块，而备用区块抹除次数表404则是依据备用区块表403来记录每一备用区206中的区块的抹除次数。例如，倘若备用区块表403的第一个位置记录110时，且备用区块抹除次数表404的第一个位置记录55时，表示区块110目前属于备用区206且其抹除次数为55。 

请参照图4C，替换区块表405是记录关联于替换区208的区块，而替换区块抹除次数表406则是依据替换区块表405来记录每一替换区208中的区块的抹除次数。例如，倘若替换区块表405的第一个位置记录120时，且替换区块抹除次数表406的第一个位置记录60时，表示区块120目前属于替换 区208且其抹除次数为60。 

请参照图4D，类似地，暂态区块表407是记录归属于暂态区210的区块，而暂态区块抹除次数表408则是依据暂态区块表407来记录每一暂态区210中的区块的抹除次数。例如，倘若暂态区块表407的第一个位置记录130时，且暂态区块抹除次数表408的第一个位置记录40时，表示区块130目前属于暂态区210且其抹除次数为40。 

值得一提的是，在非易失性存储器储存装置的运作期间每当抹除区块时，则上述抹除次数表会在缓冲存储器122d中持续更新，并且例如在非易失性存储器储存装置120结束运作或者每操作一定次数后会将此些信息记录至系统区202的区块中，此备份操作是避免因不正常断电而遗失已更新的此些区块表与抹除次数表。 

请再参考图3，在步骤S303中，会在备用区206中区分一热区206a，以标记备用区206的区块之中抹除次数相对多的一个区块。具体来说，会依据步骤S301所建立或加载的备用区块表与备用区块抹除次数表来搜寻并记录抹除次数相对多的一个区块。在此，必须了解的是所谓相对多的抹除次数意指在特定数个区块之中具有最多或较多抹除次数，例如在备用区的区块之中较多抹除次数的区块表示在备用区中抹除次数多于备用区的区块的平均抹除次数的区块。由于备用区206中的区块经常会被提取作为替换区块，因此标记热区206a的目的是希望尽可能不要提取备用区206中抹除次数较多的区块。值得一提的是，虽然在本发明实施例中，热区206a仅标示一个抹除次数较多的一个区块，但在本发明另一实施例中，热区206a可标示多个抹除次数较多的区块，例如2个或3个。 

当欲从备用区206中提区区块(即程序存储器区块时)时，在步骤S305中会判断欲提取的区块是用于替换区208或暂态区210。也就是说，在平均磨损方法中，当从备用区206中提区区块时会判断欲提取的区块是用于一般数据使用(替换区208)或者是暂时储存数据使用(暂态区210)。具体来说，在本发明实施例中会依据所提取的区块是用于替换区208或暂态区210而有不同的提取判断条件。 

倘若在步骤S305中判断欲提取的区块是用于替换区208时，则在步骤S307中会按照顺序从备用区206中提取区块(以下将此提取用于替换区208的区块称为第一区块)并且在步骤S309中会判断是否满足EC1≤(ECH+P1)条 件，其中EC1表示第一区块的抹除次数、ECH表示热区206a中的区块的抹除次数且P1表示第一门坎值。特别是，第一门坎值是根据预期达到的平均磨损效果而决定的数目，在本实施例中，第一门坎值可以是10～50的任意数，其中最佳为20。另外，在本发明另一实施例中，倘若热区206a中标示超过一个区块时，ECH表示是在热区206a中任一区块的抹除次数。 

倘若在步骤S309中判断EC1≤(ECH+P1)时，则在步骤S311中会将第一区块搬移至替换区208。具体来说，在步骤S311中所谓的搬移会产生第一区块与替换区208的关联同时取消第一区块与备用区206的关联。倘若在步骤S309中判断EC1＞(ECH+P1)时，则在步骤S313中会以热区206a的区块作为搬移至替换区208的区块以取代第一区块。具体来说，在步骤S313中会产生热区206a中的区块与替换区208的关联同时取消热区中的区块与备用区206的关联并且之后将第一区块标记为热区206a的区块。 

另外，在本发明另一实施例中，倘若热区206a中标示超过一个区块时，则会以热区206a中任一区块来与第一区块进行交换。 

倘若在步骤S305中判断所提取的区块是用于暂态区210时，则在步骤S315中会选择在备用区206的区块之中抹除次数相对少的区块(以下将此提取用于暂态区210的区块称为第二区块)来搬移至暂态区210。也就是，取消第二区块与备用区206的关联同时产生第二区块与暂态区210的关联。在此，必须了解的是所谓相对少的抹除次数意指在特定数个区块之中具有最少或较少抹除次数，例如在备用区的区块之中较少抹除次数的区块表示在备用区中抹除次数少于备用区的区块的平均抹除次数的区块。 

在平均磨损方法中除上述依据不同的用途从备用区中提取区块之外还包括启动与执行耗损调整程序(步骤S1320)。在本实施例中，会以热区的抹除次数比对一特定值为计数的判断条件。具体来说，每当从备用区206中提取区块之后，判断是否满足ECH＞(ECL+ECS)/2+P2条件(步骤S317)。其中ECL与ECS分别表示数据区204、备用区206、替换区208与暂态区210中的所有区块中最大抹除次数与最小抹除次数，但依据不同的设计需要，也可只选其中特定的数据区或区块来定义最大与最小抹除次数ECL及ESC，且P2表示第二门坎值。在本发明实施例中，第二门坎值是根据预期达到的平均磨损效果而决定的数目，在本实施例中第二门坎值是要使(ECL+ECS)/2+P2所计算出的值比ECL与ECS的平均大但比ECL小的任意正数。倘若在步骤S317中判断 满足ECH＞(ECL+ECS)/2+P2时，则在步骤S319中会将计数值加1累计于缓冲存储器122d中。 

在本发明另一实施例中，增加计数值的条件亦可是在执行写入或抹除时将将此计数值加1累计于缓冲存储器122d中(未绘示)。 

在步骤S321中，会判断计数值是否大于第三门坎值。其中第三门坎值是根据预期达到的平均磨损效果而决定的数目。在本实施例中，第三门坎值可以是任意正数，其中本实施例中第三门坎值为10。倘若在步骤S321中判断计数值是大于第三门坎值时，则在步骤S323中会在数据区204之中选择具有抹除次数相对少的区块(以下称为第三区块)来与热区206a的区块交换并且重置计数值(例如重置为0)。也就是，产生热区206a中的区块与数据区204的关联同时取消热区206a中的区块与备用区206的关联，并且产生第三区块与备用区206的关联且将第三区块标记为热区206a的区块同时取消第三区块与数据区204的关联(即耗损调整程序)。 

另外，在热区206a具有多个区块的另一实施例中，则第三区块会与热区206a中任一或具相对多抹除次数的区块交换。 

在本发明另一实施例中，在步骤S323中还包括倘若数据区204的区块之中具有多个具最少抹除次数的区块时，则会选择具有对应最大LBA的区块作为第三区块。 

在本发明另一实施例中，在步骤S323中还包括倘若数据区204的区块之中具有多个具最少抹除次数的区块时，则会选择具有对应最小LBA或任意随机LBA的区块作为第三区块。 

值得一提的是，在本发明另一实施例中，步骤S323的执行是由控制器122执行主机100正常的写入指令来完成。具体来说，在本实施例中，当执行步骤S323时，控制器122会执行写入指令，而欲写入的数据为空集合，由此执行上述产生母子区块的方式的一般写入指令来替换热区206a的区块与第三区块。 

[第二实施例] 

本发明第二实施例的硬件架构、非易失性存储器运作以及区块抹除次数的记录是相同于第一实施例(如图1A～1B、2A～2B、4A～4D)，因此在此不再重复说明。第二实施例与第一实施例所不同之处在于第二实施例在平均磨损方法中仅对用于替换区的区块提取设定规则。 

图5是根据在本发明第二实施例绘示平均磨损的流程图。请参照图5，图5所示的流程图与图3所示的流程图其不同之处在于图5的步骤S1310’仅对于用于替换区208的区块提取设定提取规则。在第二实施例用于替换区208的区块的提取规则与其它执行耗损调整的步骤是相同于图3，在此不再重复说明。 

[第三实施例] 

本发明第三实施例的硬件架构、非易失性存储器运作以及区块抹除次数的记录是相同于第一实施例(如图1A～1B、2A～2B、4A～4D)，因此在此不再重复说明。第三实施例与第一实施例所不同之处在于第二实施例在平均磨损方法中仅对用于暂态区的区块提取设定规则。 

图6是根据在本发明第三实施例绘示平均磨损的流程图。请参照图6，图6所示的流程图与图3所示的流程图其不同之处在于图6的步骤S1310”仅对于用于暂态区210的区块提取设定提取规则。在第三实施例用于暂态区210的区块的提取规则与其它执行耗损调整的步骤是相同于图3，在此不再重复说明。 

[第四实施例] 

本发明第四实施例的硬件架构、非易失性存储器运作以及区块抹除次数的记录是相同于第一实施例(如图1A～1B、2A～2B、4A～4D)，因此在此不再重复说明。第四实施例与第一实施例所不同之处在于第四实施例在平均磨损方法中简化启动调整耗损程序的步骤。 

图7是根据在本发明第四实施例绘示平均磨损的流程图。请参照图7，图6所示的流程图与图3所示的流程图其不同之处在于在图7中将原本图3的步骤S317-S323合并简化为步骤S1320’，除此之外其它步骤相同于图3，在此不再重复说明。步骤S1320’包括判断是否满足ECH＞(ECL+ECS)/2+P2’条件(图7的步骤S317’)以及倘若ECH＞(ECL+ECS)/2+P2’时启动与执行上述耗损调整程序(图7的步骤S323’)。其中P2’表示第四门坎值。在本发明中，第四门坎值是根据预期达到的平均磨损效果而决定的数目。 

值得一提的是上述图3、图5、图6与图7的实施例皆是以特定条件下启动与执行耗损调整程序。然而，在本发明另一实施例中亦可以随机方式启动与执行耗损调整程序(未绘示)。 

在根据本发明所提出的平均磨损方法是适用于非易失性存储器，因此本 发明所提出的平均磨损方法可应用各种以非易失性存储器作为储存媒体的装置。例如图8所示的USB快闪碟802、数字相机(摄影机)804所使用的SD卡804a、MMC卡804b、CF卡804c与记忆棒(memory stick)804d以及固态硬盘806等。尤其是固态硬盘806更需要好的平均磨损方法。 

综上所述，本发明所提出用于非易失性存储器的平均磨损方法可有效地平均存储器内区块的磨损，由此延长存储器的寿命。再者，本发明所提出的平均磨损方法的总抹除次数与传统方法的总抹除次数差异不大并不会增加造成额外抹除负担，然而本发明的方法比传统方法更可以平均存储器区块的抹除次数。 

虽然本发明已以较佳实施例揭露如上，然其并非用以限定本发明，任何本领域技术人员，在不脱离本发明的精神和范围内，当可作些许的更动与润饰，因此本发明的保护范围当视所附的权利要求范围所界定者为准。 

Claims (29)

1.一种用于非易失性存储器的平均磨损方法，其中该非易失性存储器实质上分割为多个区块且该些区块至少分组为数据区、备用区、替换区与暂态区，该平均磨损方法包括：

a.在该备用区中区分一热区，以标记在该备用区的区块之中抹除次数相对多的至少一个区块；

b.当从该备用区中提取用于该替换区的第一区块时，倘若该第一区块的抹除次数≤该热区的区块的抹除次数加第一门坎值时搬移该第一区块至该替换区，倘若该第一区块的抹除次数＞该热区的区块的抹除次数加该第一门坎值时搬移该热区中的区块的其中之一至该替换区并且将该第一区块标记为该热区的区块；以及

c.执行耗损调整程序，其中该耗损调整程序包括：

将该热区中该至少一个区块的其中之一搬移至该数据区，同时将该数据区的第三区块搬移至该备用区且将该第三区块标记为该热区的区块，其中该第三区块是在该数据区之中具有相对少抹除次数的区块。

2.根据权利要求1所述的用于非易失性存储器的平均磨损方法，还包括：

从该备用区提取用于该暂态区的第二区块，其中该第二区块是该备用区之中具有相对少抹除次数的区块。

3.根据权利要求1所述的用于非易失性存储器的平均磨损方法，还包括：

当该热区的区块的抹除次数＞该些区块的抹除次数之中最大抹除次数与最小抹除次数的中间值加第二门坎值时则将计数值加1；以及

当该计数值大于第三门坎值时，则执行步骤c并且重置该计数值。

4.根据权利要求1所述的用于非易失性存储器的平均磨损方法，还包括：

当执行写入或抹除指令时，则将计数值加1；以及

当该计数值大于第三门坎值时，则执行步骤c并且重置该计数值。

5.根据权利要求1所述的用于非易失性存储器的平均磨损方法，还包括：

当该热区的区块的抹除次数＞该些区块的抹除次数之中最大抹除次数与最小抹除次数的中间值加第四门坎值时则执行步骤c。

6.根据权利要求1所述的用于非易失性存储器的平均磨损方法，还包括：

以随机方式执行步骤c。

7.根据权利要求1所述的用于非易失性存储器的平均磨损方法，还包括建立对应该数据区的至少一个区域的至少一个数据区块抹除次数表、备用区块抹除次数表、替换区块抹除次数表与暂态区块抹除次数表，其分别用以记录该数据区、该备用区、该替换区与该暂态区的区块的抹除次数。

8.根据权利要求7所述的用于非易失性存储器的平均磨损方法，其中建立该至少一个数据区块抹除次数表是以对应逻辑物理对映表来建立，其中该至少一个数据区块抹除次数表是对应该逻辑物理对映表来分别地记录该数据区的区块的抹除次数。

9.根据权利要求1所述的用于非易失性存储器的平均磨损方法，其中还包括执行主机端正常的写入指令来完成步骤c。

10.一种控制器，其适用于储存装置，该储存装置的非易失性存储器实质上分割为多个区块并且该些区块至少分组为数据区、备用区、替换区与暂态区，该控制器包括：

非易失性存储器接口，用以存取该非易失性存储器；以及

存储器管理模块，用以管理该非易失性存储器，其中该存储器管理模块会执行平均磨损方法，该平均磨损方法包括：

a.在该备用区中区分一热区，以标记在该备用区的区块之中抹除次数相对多的至少一个区块；

b.当从该备用区中提取用于该替换区的第一区块时，倘若该第一区块的抹除次数≤该热区的区块的抹除次数加第一门坎值时搬移该第一区块至该替换区，倘若该第一区块的抹除次数＞该热区的区块的抹除次数加该第一门坎值时搬移该热区中的区块的其中之一至该替换区并且将该第一区块标记为该热区的区块；以及

c.执行耗损调整程序，其中该耗损调整程序包括：将该热区中该至少一个区块的其中之一搬移至该数据区，同时将该数据区的第三区块搬移至该备用区且将该第三区块标记为该热区的区块，其中该第三区块是在该数据区之中具有相对少抹除次数的区块。

11.根据权利要求10所述的控制器，其中该平均磨损方法还包括：

从该备用区提取用于该暂态区的第二区块，其中该第二区块是该备用区之中具有相对少抹除次数的区块。

12.根据权利要求10所述的控制器，其中该平均磨损方法还包括：

当该热区的区块的抹除次数＞该些区块的抹除次数之中最大抹除次数与最小抹除次数的中间值加第二门坎值时则将计数值加1；以及

当该计数值大于第三门坎值时，则执行步骤c并且重置该计数值。

13.根据权利要求10所述的控制器，其中该平均磨损方法还包括：

当执行写入或抹除指令时，则将计数值加1；以及

当该计数值大于第三门坎值时，则执行步骤c并且重置该计数值。

14.根据权利要求10所述的控制器，其中该平均磨损方法还包括：

当该热区的区块的抹除次数＞该些区块的抹除次数之中最大抹除次数与最小抹除次数的中间值加第四门坎值时则执行步骤c。

15.根据权利要求10所述的控制器，其中该平均磨损方法还包括：

以随机方式执行步骤c。

16.根据权利要求10所述的控制器，其中该平均磨损方法还包括执行主机端正常的写入指令来完成步骤c。

17.一种用于非易失性存储器的平均磨损方法，其中该非易失性存储器实质上分割为多个区块且该些区块至少分组为数据区、备用区、替换区与暂态区，该平均磨损方法包括：

a.在该备用区中区分一热区，以标记在该备用区的区块之中抹除次数相对多的至少一个区块；

b.从该备用区提取用于该暂态区的第二区块，其中该第二区块是该备用区之中具有相对少抹除次数的区块；以及

c.执行耗损调整程序，其中该耗损调整程序包括将该热区中该至少一个区块的其中之一搬移至该数据区，同时将该数据区的第三区块搬移至该备用区且将该第三区块标记为该热区的区块，其中该第三区块是在该数据区之中具有相对少抹除次数的区块。

18.根据权利要求17所述的用于非易失性存储器的平均磨损方法，还包括：

当从该备用区中提取用于该替换区的第一区块时，倘若该第一区块的抹除次数≤该热区的区块的抹除次数加第一门坎值时搬移该第一区块至该替换区，倘若该第一区块的抹除次数＞该热区的区块的抹除次数加该第一门坎值时搬移该热区中的区块的其中之一至该替换区并且将该第一区块标记为该热区的区块。

19.根据权利要求17所述的用于非易失性存储器的平均磨损方法，还包括：

当该热区的区块的抹除次数＞该些区块的抹除次数之中最大抹除次数与最小抹除次数的中间值加第二门坎值时则将计数值加1；以及

当该计数值大于第三门坎值时，则执行步骤c并且重置该计数值。

20.根据权利要求17所述的用于非易失性存储器的平均磨损方法，还包括：

当执行写入或抹除指令时，则将计数值加1；以及

当该计数值大于第三门坎值时，则执行步骤c并且重置该计数值。

21.根据权利要求17所述的用于非易失性存储器的平均磨损方法，还包括：

当该热区的区块的抹除次数＞该些区块的抹除次数之中最大抹除次数与最小抹除次数的中间值加第四门坎值时则执行步骤c。

22.一种控制器，其适用于储存装置，该储存装置的非易失性存储器实质上分割为多个区块并且该些区块至少分组为数据区、备用区、替换区与暂态区，该控制器包括：

非易失性存储器接口，用以存取该非易失性存储器；

缓冲存储器，用以暂时地储存数据；

微处理单元，用以控制该控制器的整体运作；以及

存储器管理模块，用以管理该非易失性存储器，其中该存储器管理模块会执行平均磨损方法，该平均磨损方法包括：

a.在该备用区中区分一热区，以标记在该备用区的区块之中抹除次数相对多的至少一个区块；

b.从该备用区提取用于该暂态区的第二区块，其中该第二区块是该备用区之中具有相对少抹除次数的区块；以及

c.执行耗损调整程序，其中该耗损调整程序包括将该热区中该至少一个区块的其中之一搬移至该数据区，同时将该数据区的第三区块搬移至该备用区且将该第三区块标记为该热区的区块，其中该第三区块是在该数据区之中具有相对少抹除次数的区块。

23.根据权利要求22所述的控制器，其中该平均磨损方法还包括：

当从该备用区中提取用于该替换区的第一区块时，倘若该第一区块的抹除次数≤该热区的区块的抹除次数加第一门坎值时搬移该第一区块至该替换区，倘若该第一区块的抹除次数＞该热区的区块的抹除次数加该第一门坎值时搬移该热区中的区块的其中之一至该替换区并且将该第一区块标记为该热区的区块。

24.根据权利要求22所述的控制器，其中该平均磨损方法还包括：

当该热区的区块的抹除次数＞该些区块的抹除次数之中最大抹除次数与最小抹除次数的中间值加第二门坎值时则将计数值加1；以及

当该计数值大于第三门坎值时，则执行步骤c并且重置该计数值。

25.根据权利要求22所述的控制器，其中该平均磨损方法还包括：

当执行写入或抹除指令时，则将计数值加1；以及

当该计数值大于第三门坎值时，则执行步骤c并且重置该计数值。

26.一种用于非易失性存储器的平均磨损方法，其中非该易失性存储器实质上分割为多个区块且该些区块至少分组为数据区、备用区、替换区与暂态区，该平均磨损方法包括：

a.在该备用区中区分一热区，以标记在该备用区的区块之中抹除次数相对多的至少一个区块；

b.从该备用区中提取用于该替换区的第一区块；

c.以该热区的抹除次数比对特定值为计数的判断条件；以及

d.当该计数值大于第三门坎值时，执行耗损调整程序，其中该耗损调整程序包括将该热区中该至少一个区块的其中之一搬移至该数据区，同时将该数据区的第三区块搬移至该备用区且将该第三区块标记为该热区的区块，其中该第三区块是在该数据区之中具有相对少抹除次数的区块。

27.根据权利要求26所述的用于非易失性存储器的平均磨损方法，其中该判断条件包括：

当该热区的区块的抹除次数＞该特定值加第二门坎值时则将计数值加1。

28.根据权利要求26所述的用于非易失性存储器的平均磨损方法，其中该特定值为该些区块的抹除次数之中最大抹除次数与最小抹除次数的中间值。

29.根据权利要求26所述的用于非易失性存储器的平均磨损方法，其中该平均磨损方法还包括建立对应该数据区的至少一个区域的至少一个数据区块抹除次数表、一备用区块抹除次数表、一替换区块抹除次数表与一暂态区块抹除次数表，其分别用以记录该数据区、该备用区、该替换区与该暂态区的区块的抹除次数。

Images