使用请求调页技术的系统中减少页替换时间的方法和设备

摘要

提供了一种用于在使用请求调页技术的系统中减少页替换时间的方法和设备。所述设备包括：存储器管理单元，发送指示发生页错误的信号；装置驱动器，从非易失性存储器读取具有页错误的页；和页错误处理器，搜索并确保存储器中用于存储具有页错误的页的空间。在预先计算的有限时间内执行存储器中所述空间的搜索和确保，并且将被载入系统的存储器的一部分数据存储在非易失性存储器中。

说明书

本申请要求于2006年1月13日在韩国知识产权局提交的第10-2006-0004140号韩国专利中请的优先权，本申请完全公开于此，以资参考。

                         技术领域

与本发明一致的设备和方法涉及请求调页(demand paging)技术，更具体地讲，涉及在使用请求调页技术的系统中减少页替换(page replacement)时间的技术。

                         背景技术

请求调页技术是这样一种技术：在使用虚拟存储系统的操作系统中将虚拟存储器分配给诸如硬盘的辅助存储装置，并根据用户的请求来执行物理存储映射以有效地使用有限的主存。闪存是非易失性的，它被快速地访问，而且如同硬盘一样，闪存具有低功耗。因此，闪存已被应用于嵌入式系统或移动装置。

请求调页的过程如下。当发生页错误时，页错误处理器首先确保用于载入具有页错误的相应页的物理存储空间。当没有可用的物理存储空间时，页错误处理器用预先分配的页替换所述相应页以确保物理存储空间。在确保物理存储空间之后，错误处理器搜索存储具有页错误的所述页的非易失性存储装置的地址。然后，错误处理器从非易失性存储装置读取所述相应页，并更新存储映射表。

图1是示出根据软件处理和装置I/O之间的关系的相对于时间的请求调页处理的示图。

当发生页错误时，从装置读取数据。页错误处理器10首先从装置读取数据，并确保用于存储所述数据的存储空间。然后，页错误处理器10搜索具有页错误的页的地址并创建命令READ_CMD，以读取相应页的数据。当所述命令被发送给装置时，装置在对应于忙时间的时间过去之后发送数据。所述忙时间是执行在前操作以读取存储在相应页中的数据所需的时间。例如，当从闪存读取数据时，列信号和行信号被发送给存储相应页的区域，从而读取相应数据。执行上述处理需要花费一定的时间。在该时间过去之后，可从闪存发送相应页的数据。当所述数据从装置被发送时，页错误处理器更新映射表并存储接收的数据。

参照图1，页替换操作需要多个处理，例如，从装置读取数据并排列页错误结果，因而页替换时间的减少可对系统性能产生较大的影响。

最近最少使用(LRU)算法可作为最佳页替换算法的示例。LRU算法是确定最近最少使用的页作为替换目标的方法。然而，为了将LRU页替换策略应用于请求调页，需要硬件支持。然而，在大多数系统中没有LRU页替换策略的硬件支持。因此，通常使用类似于LRU算法的算法，诸如时钟算法或Mach 2.5。

公知的调页技术基于诸如硬盘的非易失性存储装置来处理请求调页，但是并没有考虑诸如闪存的非易失性存储装置的特性。从硬盘读取数据的方法不同于从闪存读取数据的方法。然而，在调页技术中，没有考虑这种差别。

在硬盘的情况下，通过使用物理存储器和非易失性存储装置的地址，可将数据从非易失性存储装置读取到物理存储器。然而，在装置中具有缓冲器(或寄存器)的非易失性存储装置(诸如闪存)的情况下，在将数据读入物理存储器(RAM)中之前，应该将数据载入非易失性存储装置中的缓冲器(或寄存器)。然后，将数据从缓冲器或寄存器载入物理存储器。在闪存中，如果对非易失性存储装置的地址发布了读取命令，那么在读取命令被发布之后数据被载入缓冲器(寄存器)。当载入数据时，装置处于忙状态。通常，忙状态的时间为23μsec至35μsec，但是根据闪存而不同。

除了上述情况，当应用调页技术时，会不断地重复不必要的操作。因此，期望一种在请求调页中减少页替换时间的方法和设备。

                        发明内容

已完成本发明示例性实施例以克服上述问题和以上没有描述的其它问题。此外，本发明不需要克服上述问题，本发明的示例性实施例可以不克服上述任何问题。因此，本发明的一方面是考虑诸如闪存的非易失性存储器的特性来应用请求调页技术。

本发明的另一方面是通过在从非易失性存储装置读取数据的同时执行另一操作来提高系统性能。

本发明的各方面不限于以上提及的那些方面，本领域技术人员通过下面的描述将清楚地理解本发明的其它方面。

根据本发明的一方面，一种在使用请求调页技术的系统中减少页替换时间的方法包括：接收指示发生页错误的信号；从非易失性存储器读取具有页错误的页；搜索并确保存储器中用于存储具有页错误的页的空间。在预先计算的有限时间内执行存储器中所述空间的搜索和确保，并且将被载入系统的存储器的一部分数据存储在非易失性存储器中。

根据本发明的另一方面，一种在使用请求调页技术的系统中减少页替换时间的设备包括：非易失性存储装置，在没有电源时也保持存储的数据；存储器，从非易失性存储装置接收数据并存储所述数据，并通过请求调页来管理所述数据，其中，只有在提供电源时存储器才存储所述数据；存储器管理单元，发送指示存储器中发生页错误的信号；页错误处理器，提取具有页错误的页的信息，搜索并确保存储器中用于存储具有页错误的页的空间；和装置驱动器，将具有页错误的页的信息发送给非易失性存储装置，并从非易失性存储装置接收数据。页错误处理器在预先计算的有限时间内运行。

                         附图说明

通过参照附图对本发明示例性实施例进行的详细描述，本发明的上述和其它方面和特点将会变得更加清楚，其中：

图1是示出根据软件处理和装置I/O之间的关系的随着时间的流逝的请求调页处理的示图；

图2是示出根据本发明示例性实施例的在减少数据载入时间的同时的调页处理的时间图；

图3是示出应用了根据本发明示例性实施例的减少所使用的页替换时间的处理的时钟算法的操作的示图；

图4是示出根据本发明示例性实施例的在图3所示的时钟算法中减少页替换时间的处理的示图；

图5示出在Mach 2.5算法中选择替换页的处理的示图；

图6是示出根据本发明示例性实施例的重新设置图5所示的Mach 2.5算法中的无效列表的移动点的处理的示图；

图7是示出根据本发明示例性实施例的在存储器中发送读取命令并执行调页的处理的流程图；

图8是示出根据本发明示例性实施例的减少执行请求调页所需的时间的处理的流程图；和

图9是示出根据本发明示例性实施例的系统的结构的框图。

                       具体实施方式

通过参照下面对示例性的优选实施例和附图的详细描述，可以更容易地理解本发明的各方面和特点以及实现本发明的各方面和特点的方法。然而，可以按许多不同的形式来实现本发明，不应该将本发明解释为限于这里阐述的示例性实施例。相反，提供这些示例性实施例，从而本公开将是完全和完整的，并将本发明的构思完全传达给本领域技术人员，本发明将仅由权利要求限定。贯穿说明书，相同的标号表示相同的部件。

以下，将参照根据本发明示例性实施例的在使用请求调页技术的系统中减少页替换时间的方法和设备的框图或流程图来描述本发明。应该理解，可通过使用计算机程序指令来执行流程图的每个方框和流程图的方框的组合。由于计算机程序指令可包括在通用计算机、专用计算机或可编程数据处理装置的处理器中，所以通过计算机或另一可编程数据处理装置的处理器执行的指令可创建用于执行流程图方框中所描述的功能的单元。这些计算机程序指令可存储在可引导计算机或另一可编程数据处理装置的计算机可用存储器或计算机可读存储器中，从而按特定方式实现所述计算机程序指令。存储在计算机可用存储器或计算机可读存储器中的指令可产生包括用于执行流程图方框中所描述的功能的指令单元的产品。由于计算机程序指令可包括在计算机或另一可编程数据处理装置中，所以所述指令可提供程序以执行流程图方框中所描述的功能，所述指令创建如下处理，即，在计算机或另一可编程数据处理装置上执行一系列操作步骤并由计算机执行，并且所述指令使得计算机或另一可编程数据处理装置被执行。

此外，每个方框可表示包括一个或多个用于执行特定逻辑功能的可执行指令的模块、代码段或部分代码。此外，在一些修改的实施例中，应该理解，方框中描述的功能可以不按顺序执行。例如，根据对应于方框的功能，相邻的两个方框可基本上被同时执行或者可按相反的顺序被执行。

在诸如闪存的非易失性存储装置中，将数据从非易失性存储装置载入缓冲器或寄存器的处理与将载入缓冲器或寄存器中的数据发送给物理存储器(RAM)的处理独立执行。因此，当正将数据从存储单元载入缓冲器或寄存器时，可以执行诸如替换页选择的操作，从而减少请求调页处理所需的时间。此外，除了替换页选择以外，当装置处于忙状态时，可更新存储映射表，或者可使转换后备缓冲器(TLB)或高速缓存器无效。作为请求调页操作的处理，存储映射表的更新或者TLB或高速缓存器无效是必需的。

如上所述，为了从装有闪存的装置读取数据，发布读取命令和地址，然后，在一段时间之后将相应的数据从装置发送给主机。这是因为，在闪存的结构中，为了将存储在非易失性存储装置的单元中的数据载入诸如缓冲器或寄存器的易失性存储装置，需要时间。

如果有效地利用将存储在闪存的单元中的数据载入缓冲器所需的时间，那么可以减少闪存中的数据载入时间。

图2是示出根据本发明示例性实施例的在减少数据载入时间的同时的调页处理的时间图。与图1相比较，当装置处于“忙”状态时，物理存储空间被确保，映射表被更新。当页错误处理器产生命令READ_CMD时，数据从闪存的单元载入缓冲器或寄存器。在这种情况下，在装置处于“忙”状态时的时间T内，页错误处理器可执行独立的操作。参照图2，通过在更新映射表的同时确保物理存储空间，可以减少时间。

图3是示出应用了根据本发明示例性实施例的减少页替换时间的处理的时钟算法的操作的示图。

时钟算法是一种先进先出(FIFO)替换算法。后臂(back arm)用作指示队列中最早进入的页的指针。在选择将被替换的页(替换页)时，检查后臂所指示的页的参考(reference)位。如果相应页的参考位为指示它没有被参考的未参考(UR)，那么相应页被选择为替换页。如果相应页的参考位为参考(R)，那么相应页又有一次机会，后臂移向下一页，并检查后臂所指示的页的参考位。在后臂移动时，在用作指针的前臂(front arm)所指示的页的参考位被改变为UR的同时，前臂移动。按照这种方式来移动前臂和后臂。如果找到了后臂所指示的参考位为UR的页，那么相应页被选择为替换页。

图3是示出使用时钟算法选择替换页的处理的示图。在方框51中，由于后臂指示参考位为R的页，所以后臂和前臂移向下一页，直到后臂找到参考位为UR的页。结果，如方框52中所示，在后臂移了三次之后，页13被选择为替换页。此外，前臂也移了三次，并且后臂移了三次。在移动期间，前臂将页2、11和7的参考位设置为UR状态。如方框53中所示，在选择了替换页之后，分配新页4，并且前臂和后臂都移一次。方框54示出在方框53中参考位为UR的页7被再次参考的情况的示例。在时钟算法中，如果参考位为UR的页被参考，那么参考位被从UR改变到R。结果，如方框55中所示，页7的参考位被改变为“R”。

图4是示出根据本发明示例性实施例的在图3所示的时钟算法中减少页替换时间的处理的示图。在图3中，后臂移动直到参考位为UR的页被找到，而前臂根据后臂的移动来移动指针，并将参考位从R改变为UR。然而，在后臂和前臂之间的所有页的参考位都为R的情况下，指针移动的次数与后臂和前臂之间的页的数量相同。然后，后臂替换其参考位已被前臂改变为UR的页。在图4所示的方框62中，当后臂和前臂之间的所有页的参考位都为R时，后臂应该移动到页25，前臂应该从页25开始连续地将页的参考位改变为UR。然而，这浪费了时间。因此，在图4中，后臂在预定时间T内搜索参考位为UR的页。即使在预定时间T之后后臂没有找到参考位为UR的页，参考位为R的页也被设置为替换页。

在图4所示的方框64中，后臂在预定时间T内搜索参考位为UR的页，但是没有找到参考位为UR的相应页。在预定时间T内，当移动后臂时，前臂被移动，并将前臂所指示的每个页的参考位改变为UR。

当预定时间T过去时，后臂指示页2，前臂指示页26，并且这两个页的参考位都为R。尽管后臂和前臂都指示参考位为R的页，但是也可以将相应页设置为替换页。在方框64中，前臂所指示的页26被设置为替换页。此外，后臂所指示的页2也可以被设置为替换页。

预定时间T可以被设置为根据实现时钟算法的各种系统而改变。此时，当从诸如图2所示的闪存(忙状态)的非易失性存储装置读取数据时，可通过移动后臂和前臂来搜索页。在忙状态期间，系统不能从非易失性存储装置读取数据。因此，如果在忙状态期间执行页错误处理，那么可减少所需的时间。

在图4中，为了减少移动后臂和前臂以进行页替换所需的时间，设置有限时间T。作为示例，所述有限时间T被设置为与从非易失性存储装置读取数据所需的时间交迭。

图5是示出使用Mach 2.5算法选择替换页的处理的示图。

在Mach 2.5算法中，以堆栈的方式管理页。最近参考的页被放置在堆栈的顶部，最近最少参考的页被放置在堆栈的底部。在页替换时，选择放置在堆栈底部的页，从而最近最少参考的页成为替换页。

在Mach 2.5算法中，通过将页划分到有效列表和无效列表中来管理页。在有效列表中，没有发生页错误。因此，在有效列表中不能检查是否参考了页。在无效列表中，页被载入物理存储器但是是无效的，结果伪页错误(pseudopage fault)可发生，从而检查相应页是否被参考。因此，最近参考的页被堆积在有效列表中。每当新页被插入有效列表中时，有效列表中最近最少使用的页被堆积在无效列表中。如果包括在无效列表中的页被参考，那么相应页被放置在有效列表的顶部，并被管理为最近最多参考的页。

图5示出选择替换页并将新参考的页添加到列表的Mach 2.5算法的示例。根据Mach 2.5算法，无效列表中的最后页成为替换页。此外，新添加的页被放置在有效列表的顶部。此时，包括在有效列表中的最后页被移动到无效列表。

在方框(a)中，标号70和80分别表示有效列表和无效列表。页4是最近最多参考的页，包括在无效列表中的页20将首先被替换。为了参考页5，无效列表80中的页20被替换。方框(b)示出替换结果。从无效列表82中移走页20，为页20分配的存储空间被分配给页5，页5存在于有效列表72中。

作为有效列表72中的最后页的页2被移动到无效列表82。因此，如方框(c)中所示，页2从有效列表74移动到无效列表84。

如方框(c)中所示，当包括在无效列表84中的页7被参考时，页7被移动到有效列表。结果，如方框(d)中所示，页7从无效列表86被移走，并被添加到有效列表76的顶部。此外，包括在有效列表76中的页9应该被移动到无效列表86。在方框(e)中，页9被从有效列表78移动到无效列表88。

根据图5所示的Mach 2.5算法的操作，每当页被替换时，包括在有效列表中的页被移动到无效列表。也就是说，当包括在无效列表中的页被参考时，相应页被插入有效列表的顶部，包括在有效列表中的页之一被移动到无效列表。因此，在Mach 2.5算法中，当页被参考时，可能发生列表管理开销。

每当页被参考时，需要花费很长时间来执行上述操作。因此，通过在另一时刻移动无效列表，可减少全部操作所需的时间。

图6是示出根据本发明示例性实施例的重新设置图5所示的Mach 2.5算法中的无效列表的移动点的处理的示图。

在图6中，选择将被替换的页所需的时间是指当系统不执行任何操作时的时间，并且可被举例为当装置等待读取数据时的时间。

当在选择将被替换的页所需的预定时间内没有执行替换页选择或者无效或有效列表更新时，在装置等待时间期间可执行一部分操作，从而提高请求调页处理性能。

在方框(a)中，包括在无效列表100中的页7被参考。结果，如方框(b)中所示，页7被从无效列表102中去除，并被插入有效列表90的顶部，从而产生有效列表92。在图5中，有效列表的最后页被移动到无效列表。然而，在图6中，此时不执行该操作。

在方框(c)中，在方框(b)的状态下新页6被参考。为了分配新页，包括在无效列表104中的替换页被添加到有效列表94，然后，页6被分配。同时，如上所述，包括在有效列表94中的页没有被移动到无效列表104。

在方框(d)中，新页22被参考。结果，新页22被添加到有效列表96，并从无效列表106移走一个页。略掉将页从有效列表96移动到无效列表的处理。

当执行调页处理时，如果装置处于图2所示的“忙”期间，那么装置将包括在有效列表98中的一个页或多个页移动到无效列表108。

也就是说，可从有效列表的最后部分中提取与包括在有效列表中的页的最初数量相比所增加的数量的页，并且将其移动到无效列表。此时，如果大量页应该被移动到无效列表，那么考虑到装置的“忙”时间可在下一个新页被参考时处理在预定时间内没有移动的页。因此，可以防止处理请求调页所需的时间超过所述预定时间。

图7是示出根据本发明示例性实施例的在存储器中发送读取命令并执行调页的处理的流程图。图7示出当在图2中确保物理存储空间并更新映射表的时间T内执行图4或图6所示的调页处理操作时的流程图。

当发生页错误时，应该读取相应页。因此，存储相应页的非易失性存储装置的地址被提取(步骤S120)。映射表可记录这种信息。所述地址与读取命令一起被发送给非易失性存储装置(步骤S122)。

如图2所示，将读取命令发送给非易失性存储装置并再次接收期望的数据需要花费一段时间。在该时间段内，选择替换页以确保存储读取的页的物理存储空间(步骤S124)。映射表被更新(步骤S126)。从非易失性存储装置读取相应页并将其存储在物理存储器中(步骤S128)。

在图7中，步骤S124和S126包括当使用图4所示的时钟算法时在有限时间T内移动后臂和前臂的情况以及当使用图6所示的Mach 2.5算法时在有限时间内管理有效列表和无效列表并且在下一有限时间期间替换没有完成的部分的情况。

同时，在说明书中，图4或图6中使用的有限时间与图2所示的有限时间T不同。如果系统处于空闲状态，那么可以在任何时间执行图4和图6所示的替换页选择和无效列表管理所需的操作。空闲状态的示例可以是系统等待从非易失性存储器读取数据的时间。

图8是示出根据本发明示例性实施例的减少执行请求调页所需的时间的处理的流程图。当使用请求调页时，一部分页被载入或存储在存储器中。因此，如果应用程序请求存储器的预定页，那么页错误可能发生。当接收到指示发生页错误的信号(步骤S200)时，将与具有页错误的页有关的信息，例如，包括逻辑或物理地址的信息发送给非易失性存储器(步骤S210)。图8所示的操作可用于通过缓冲器或寄存器将数据发送给系统以进行数据读取的非易失性存储器(诸如闪存)。在步骤S210，发送页信息(例如，与非易失性存储器有关的地址信息)或者读取对应于所述地址的数据需要花费时间。在发送页信息和读取数据的时间段期间，执行步骤S230和S240。从存储器中选择替换页以存储从非易失性存储器读取的页(步骤S230)。管理列表以执行请求调页(步骤S240)。

从非易失性存储器接收相应页的数据(步骤S250)。接收的数据被存储在存储器中以处理应用程序的操作(步骤S260)。此时，在执行步骤S210和S250中的操作所需的时间期间执行对应于步骤S230和S240的操作。

在上述时钟算法中，步骤S230和S240可对应于如下步骤：移动用于管理将被替换的多个页的指针(后臂和前臂)并确保所述指针所指示的页作为存储具有页错误的页的空间。当然，不必在步骤S210和S250之间执行步骤S230和S240。例如，可在系统空闲时执行步骤S230和S240。

类似地，当使用Mach 2.5算法时，存储器中的页被划分到有效列表和无效列表中。有效列表包括当前参考的页，无效列表包括将被替换的页。包括在有效列表和无效列表中的页可以彼此交换。可在系统空闲时在步骤S230和S240中执行交换页的处理。系统的空闲状态期间可存在于步骤S210和S250之间。

图9是示出根据本发明示例性实施例的系统的结构的框图。示例性实施例中的各个组件中的每个组件可以是(但不限于)执行特定任务的软件或硬件组件，诸如现场可编程门阵列(FPGA)或专用集成电路(ASIC)。模块可被有利地配置为存在于可寻址存储介质上，并被配置为在一个或多个处理器上执行。因而，作为示例，模块可包括诸如软件组件、面向对象的软件组件、类组件和任务组件的组件、过程、函数、属性、程序、子程序、程序代码段、驱动程序、固件、微码、电路、数据、数据库、数据结构、表、数组和变量。所述组件和模块所提供的功能可以组合为更少的组件和模块，或者还可分为另外的组件和模块。此外，可将所述组件和模块实现为在安全多媒体卡中的一个或多个CPU上执行。

系统或装置300包括具有非易失性存储装置的设备，并且可通过蜂窝电话、MP3播放器、PMP、PDA或笔记本电脑作为示例。非易失性存储装置400可使用诸如上述闪存的记录介质。即使不提供电源，非易失性存储装置400(即，非易失性存储器)也可保持数据。非易失性存储装置400可以以例如卡的形式附于所述设备或从所述设备分离，或者可以合并到装置300中。

存储器350从非易失性存储装置400接收数据并存储该数据。当数据被存储在存储器350中时，应该提供电源。通过使用请求调页，存储器350可管理比原始可存储的数据量更大的数据量。为此，存储器管理单元(MMU)320和页错误处理器310被提供。存储器管理单元320将指示发生页错误的信号发送给页错误处理器310。页错误处理器310提取具有页错误的页的信息，并搜索和确保用于存储相应页的存储器350的空间。页错误处理器310可使用上述时钟算法或Mach 2.5算法来搜索并确保存储器350的空间。

装置驱动器340将具有页错误的页的信息发送给非易失性存储装置400，并从非易失性存储装置400接收数据。

发送具有页错误的页的信息并从非易失性存储装置接收数据所需的时间可以是装置300一方的空闲期。页错误处理器310在所述空闲期或预先计算的有限时间内搜索并确保用于存储相应页的存储器350的空间。

页高速缓存管理器330高速缓存并管理页的地址、存储器的位置或对应于非易失性存储装置的信息。

尽管结合本发明的示例性实施例描述了本发明，但是本领域的技术人员将清楚，在不脱离本发明的精神和范围的情况下，可以对其进行各种修改和改变。因此，应该理解，以上示例性实施例不是限制性的，而是在所有方面都是示例性的。

根据本发明的一方面，可以考虑到诸如闪存的非易失性存储装置的特性来使用请求调页技术。

根据本发明的一方面，可以在从非易失性存储装置读取数据所需的时间期间执行另一操作。