公开/公告号CN113039530A
专利类型发明专利
公开/公告日2021-06-25
原文格式PDF
申请/专利权人 零点科技公司;
申请/专利号CN201980075036.7
申请日2019-11-14
分类号G06F12/08(20160101);G06F9/46(20060101);
代理机构51258 成都超凡明远知识产权代理有限公司;
代理人王晖;曹桓
地址 瑞典哥德堡
入库时间 2023-06-19 11:35:49
技术领域
本主题总体而言涉及电子计算机中存储器的数据压缩领域。
背景技术
数据压缩是一种通用技术，其通过相比于不频繁的数据集合(collection ofdata)更有效地对频繁的数据集合进行编码来更有效地储存和转移数据。出于多种原因，通常更有效地储存和转移数据是有意义的。在计算机存储器中，例如在保存数据和处理设备在例如主存储器或高速缓存存储器上运行的计算机指令的存储器中，令人感兴趣的是更有效地储存所述数据，比方说K倍，因为这样可以将所述存储器的尺寸潜在地减小为原来的1/K，使用潜在地减小为原来1/K的通信容量在存储器与另一个存储器之间转移数据，并且利用潜在地减小为原来1/K的能量开销在计算机系统内部或之间以及/或者存储器之间储存和转移所述数据。可选地，与没有数据压缩相比，可以潜在地在可用的计算机存储器中储存K倍的数据。令人感兴趣的是在不需要增加更多的存储器的情况下获得计算机潜在的K倍性能，这由于资源的限制而可能是昂贵的或者可能是不太理想的。作为另一个示例，智能手机、平板电脑、笔记本电脑/台式机或机顶盒的尺寸和重量是受限的，因为更大或更重的智能手机、平板电脑、笔记本电脑/台式机或机顶盒对于终端用户而言价值更低；因此潜在地降低了此类产品的市场价值。然而，更多的存储容量可能潜在地增加产品的市场价值，因为更多的存储容量可以引起更高的性能，从而提高产品的实用性。
总而言之，在计算机化产品的总体布局中，包括孤立的设备或互连的设备，数据压缩可能潜在地提高性能、降低能耗或降低由存储器开销的成本和面积。因此，数据压缩在此处所提到的那些产品之外的各种计算机化产品中具有广泛的实用性。
现有技术中的压缩存储系统通常在通过从磁盘读取或者经由存储器分配来创建存储页面时对存储页面进行压缩。压缩可以使用各种众所周知的方法，通过软件例行程序或硬件加速器来完成。当处理器从存储器中请求数据时，必须先对数据进行解压缩，然后再为请求的处理器提供服务。由于此类请求最终会在关键的存储器访问路径上结束，因此通常会对解压缩进行硬件加速，以对存储器访问时间的影响降至最小。
压缩式存储系统的一个问题是，它们面临着管理大小可变的存储页面的问题。不同于没有压缩的常规存储系统，在常规存储器系统中所有页面的大小都是一样的，而在压缩式存储系统中，每个页面的大小取决于页面的可压缩性，而页面的可压缩性与数据高度相关。此外，由于页面中数据的修改可能会影响其可压缩性，因此每个页面的大小在主存储器中的生命周期可能会发生变化。为此，一个基本的问题是如何动态管理通过压缩释放出来的存储器的量。
在压缩式存储系统中，管理释放的存储空间的现有技术采取了多种方法。通常，存储管理是操作系统的组成部分，更具体地说，是虚拟存储器管理(VMM)例行程序。VMM的任务是有效地管理可用的物理主存储空间。在启动时，VMM通常会确立有多少物理主存储器可用。在此基础上，它可以基于需求来决定哪些页面应该驻留在可用的物理存储空间中；当需要时，VMM通常会选择不太可能很快被访问的页面作为页面调出到磁盘的牺牲者。然而在压缩存储器中，可用存储容量的量会动态变化。为此，常规的VMM例行程序无法工作，因为它们在启动时假设了物理存储器的量是固定的。
替代方法是修改VMM，以了解在任何时间点的可用的存储器的量。然而，这是极不可取的，因为无论操作系统是否使用压缩，对操作系统的改变都必须应用于计算机系统。相反，现有技术中的几种方法以对操作系统公开的方式来解决管理问题。一种方法是在假设物理存储器的量大于可用存储器的量的情况下，让操作系统启动。如果通过压缩释放的内存的量小于该量，则将页面交换到磁盘上以降低存储器压力。然而，这种解决方案可能会因抖动(thrash)而出现稳定性问题，因此并不可取。
另一种对操作系统公开的方法是在主存储器中保留存储区域作为交换空间。代替将页面逐出到次级储存器件(例如磁盘)，将页面逐出到保留的交换空间。这样做的好处是，它可以比从次级储存器转移到存储器中的速度快得多，次级储存器的速度可能比存储器的速度慢得多。然而，这使系统可直接访问的存储器的尺寸减小。可以有选择地压缩交换到交换空间的页面，从而更有效地利用交换空间。然而，交换空间通常是可用物理存储容量的一小部分，通常是百分之几十。例如，假设交换空间占可用物理存储容量的20％。此外，假设压缩比为2。在交换空间与压缩相结合的情况下，其将释放出0.8×1+0.2×2＝1.2，即20％的存储空间，相反，如果对整个存储器中的所有数据进行压缩，则可以释放100％的存储空间。
显然，需要有系统和方法来管理压缩存储器中的空闲空间，这些系统和方法对操作系统是公开的，并且其允许所有的存储器被压缩而不受到稳定性问题的影响。
与压缩式存储系统相关的另一个问题是如何有效地定位压缩存储器中的某个项。在压缩存储器中，每个单独的高速缓存行或存储块(以下，块和行可互换使用)，就像存储页面一样，具有可变的大小。此外，可变大小的压缩数据必须被压紧，这可能会改变存储器的布局。因此，存储页面和块不必放在常规的非压缩式存储系统中的原始位置。
在现有技术中，协调物理地址与压缩地址之间的地址转换的一种方法是将物理存储器分割成固定大小的单元，这里称为分段。例如，一个4KB的存储页面可以被划分成四个分段，从而使分段的大小为1KB。现在，如果页面的压缩系数为2，则它将需要两个分段，而不是像常规的非压缩式存储系统那样需要四个分段。为了使用分段的概念来定位存储块，需要元数据作为地址转换的一部分，以定位所请求的存储块驻留的分段。较大的分段的优点是减少定位分段所需的元数据量，但其缺点是导致更多的内部碎片化，从而降低存储器的利用率。因此，这种方法要么元数据量大，要么存储器利用率低。
高速缓存系统通常以存储块的间隔尺寸(granularity)来管理数据，存储块的大小通常为64B，由于存储块在压缩式存储系统中具有可变的大小，因此存在如何在压缩存储页面内定位它们的额外问题。现有技术中的一种方法是使用指针来定位存储页面内的块。例如，如果页面大小为4KB，12比特指针可以定位页面内的任何块。假设块大小为64B，则4KB的存储页面内有64个块。因此，每个存储页面需要多达64×12比特＝768比特的元数据。
现有技术中的另一种方法是将每个块与该块的大小相关联。例如，如果容纳64种不同的大小，则每个存储块用于对大小进行编码的元数据将需要6比特。在这种情况下，与用于定位每个块的存储页面相关联的元数据量是64×6＝384，这比使用指针要少得多。然而，要定位某个块，例如最后一个块，将需要在存储页面中对该块之前的所有块的大小进行求和，这可能会导致地址转换过程中的大量等待时间(latency)。为了缩短该等待时间，可以限制压缩块的大小。然而，这会大大降低压缩存储器的利用率。例如，假设四个块被压缩的系数为2、4、8和16。采用基于指针的方法，将获得压缩的全部可能性，从而产生的压缩系数为4/(1/2+1/4+1/8+1/16)＝4.3，而将大小限制为4，将产生的压缩系数为4/(1/2+1/4+1/4+1/4)＝3.2。
在压缩式存储系统中定位存储块所需的元数据通常被高速缓存在处理器芯片上，其类似于常规计算机系统中的转换-查找-缓冲对虚拟到物理地址转换的作用，以避免必须访问存储器来定位物理存储器中的存储块。由于这种地址转换机制必须快速，因此大小有限，通常无法保存所有需要的元数据。因此，所有的元数据都需要放置在存储器(或储存器)中。因此，需要限制元数据的量，以节省存储空间，并减少将元数据从存储器带到处理器芯片上的地址转换机制所需的额外存储器访问。然而，如前所述，现有技术中用于减少元数据的大小的方法可能会增加地址转换机制中的大量等待时间，或者可能会由于碎片化而导致压缩存储器的利用率差。
因此，现有技术中的地址转换方法要么受到大量元数据的影响，要么受到地址转换过程中的大量等待时间的影响，或受到由于碎片化而导致的压缩存储器利用率差的影响。显然，与现有技术中已知的方法相比，需要一种系统、设备和方法来更有效地定位修改后的物理地址空间或额外的压缩地址空间中的数据。
此外，与现有技术中已知的方法相比，实质上需要一种更有效地管理压缩存储器中的空闲空间的系统和方法。
发明内容
本发明的目的是在电子计算机的存储器中的数据压缩领域提供改进，并解决、消除或减轻上述问题中的一个或多个。
本发明公开了用于管理压缩式存储系统中的存储空间的系统和方法，并包括维持压缩式存储系统中的关于每个压缩页面的大小和位置的布局。这包括物理存储器中通过存储器压缩释放的区域，以及处理操作系统对页面的请求的处理，无论这些页面是由辅助存储器进行页面调入还是页面调出，辅助存储器均由通过压缩释放的物理存储空间组成。
所公开的发明的一个方面是一种用于计算机系统的压缩存储器管理设置，该计算机系统具有一个或更多个处理器、可压缩主存储器、次级存储器和操作系统，其中可压缩主存储器具有压缩存储空间，该压缩存储空间包括可直接访问所述一个或更多个处理器的活动部分以及不可直接访问所述一个或更多个处理器的非活动部分，该压缩存储空间的形式为通过存储器压缩而释放的内存。压缩存储器管理设置包括辅助存储器，其用于维持可压缩主存储器的压缩存储空间的布局，该布局包括各个存储页面的大小和位置以及所述压缩存储空间中的空闲存储区域。压缩存储器管理设置还包括使所述操作系统、所述次级存储器和所述辅助存储器交互的选择器功能。该存储器管理设置被配置为：a)触发对可压缩主存储器中的存储页面的压缩；b)拦截从所述操作系统到所述次级存储器的页面调入请求，使用由辅助存储器维持的压缩存储空间的布局以在可用时，在所述辅助存储器中定位由页面调入请求所请求的页面，以及使所定位的请求页面可用在压缩存储空间的活动部分中；以及c)拦截所述操作系统到所述次级存储器的页面调出请求，使用由辅助存储器维持的压缩存储空间的布局，以为由页面调出请求所请求的页面获得空闲区域，以及将所请求的页面容纳在获得的辅助存储器的空闲区域中。
所公开的发明的另一个方面是一种用于计算机系统的压缩存储器管理方法，所述计算机系统具有一个或更多个处理器、可压缩主存储器、次级存储器和操作系统，其中可压缩主存储器具有压缩存储空间，该压缩存储空间包括可直接访问所述一个或更多个处理器的活动部分以及不可直接访问所述一个或多个处理器的非活动部分，该压缩存储空间的形式为通过存储而器压缩释放的内存。该压缩存储器管理方法包括：a)在辅助存储器中维持可压缩主存储器的压缩存储空间的布局，该布局包括各个存储页面的大小和位置以及所述压缩存储空间中的空闲存储区域；b)触发可压缩主存储器中的存储页面的压缩；c)拦截所述操作系统到所述次级存储器的页面调入请求，使用由辅助存储器维持的压缩存储空间的布局，以在可用时，在所述辅助存储器中定位由页面调入请求所请求的页面，以及使所定位的请求页面可用在压缩存储空间的活动部分；d)拦截所述操作系统到所述次级存储器的页面调出请求，使用由辅助存储器维持的压缩存储空间的布局，以为由页面调出请求所请求的页面获得空闲区域，以及将所请求的页面容纳在获得取的辅助存储器的空闲区域中。
在另一个方面，所公开的发明包括辅助存储器，该辅助存储器在任何时间点上维持关于每个页面的位置及其大小的存储器布局，包括使用存储器压缩释放的每个存储区域的位置和大小。所述辅助存储器包括用于响应来自操作系统的页面调入/页面调出请求的装置和响应这些请求的装置，允许其中一些请求由所述辅助存储器提供服务，而不是由例如相当慢的磁盘设备提供服务。次级储存器可以被表示为例如磁盘、SSD、USB闪存驱动器、SD卡或其任何虚拟表示。所述辅助存储器还包括以下装置：拦截来自所述次级储存设备的页面调入请求；将来自所述辅助存储器的页面转移到主存储器中；拦截页面调出请求，以将相应的页面暂时储存在所述辅助存储器中，并潜在地识别出从所述辅助存储器中逐出的页面。
在另一方面，所公开的发明包括操作辅助存储器以在任何时间点上维持关于每个页面的位置及其的大小的存储器布局的方法，包括使用存储器压缩释放的每个存储区域的位置和大小。此外，操作所述辅助存储器的方法包括响应来自操作系统的页面调入/页面调出请求以及响应这些请求的方法，允许其中一些请求由所述辅助存储器提供服务，而不是由例如相当慢的磁盘设备提供服务。还提供了拦截来自次级存储器的页面调入请求的方法；将来自所述辅助存储器页面转移到主存储器；拦截页面调出请求以将相应的页面临时储存在所述辅助存储器中，以及潜在地识别从所述辅助存储器中逐出的页面的方法。
在另一个方面，所公开的发明包括辅助存储器，该辅助存储器在任何时间点上修改关于每个页面的位置及其大小的存储器布局，包括使用存储器压缩释放的每个存储区域的位置和大小。所述辅助存储器包括用于响应来自操作系统的页面调入/页面调出请求的装置和响应这些请求的装置，允许其中一些请求由所述辅助存储器提供服务，而不是由例如相当慢的磁盘设备提供服务。所述辅助存储器还包括以下装置：拦截来自次级储存设备的页面调入请求，不需要将页面从所述辅助存储器转移到主存储器，而是更新相关的元数据；拦截页面调出请求，以将相应的页面暂时储存在所述辅助存储器中，并潜在地识别从所述辅助存储器中逐出的页面。
在另一个方面，所公开的发明包括操作辅助存储器的方法，该辅助存储器在任何时间点上修改关于每个页面的位置及其大小的存储器布局，包括使用存储器压缩释放的每个存储区域的位置和大小。此外，操作所述辅助存储器的方法包括响应来自操作系统的页面调入/页面调出请求以及响应这些请求的方法，使得其中一些请求由所述辅助存储器服务，而不是由例如相当慢的磁盘设备服务。还提供了以下方法：拦截来自次级储存设备的页面调入请求，不需要将页面从所述辅助存储器转移到主存储器，而是更新相关的元数据；拦截页面调出请求，以将相应的页面暂时储存在所述辅助存储器中，以及潜在地识别从所述辅助存储器逐出的页面的方法。
附图说明
图1描述了现有技术的计算机系统，该计算机系统包括具有一个或多个处理单元的微处理器芯片、典型的三级高速缓存层级结构、连接到一个或多个片外存储器的一个或多个存储器控制器。
图2描述了如图1所示的现有技术的计算机系统，该计算机系统被配置为对存储器中的数据和指令进行压缩和解压缩。
图3描述了如图1所示的现有技术的计算机系统，该计算机系统可以使用操作系统功能和交换存储器的概念来实现压缩存储器。
图4描述了如图2所示的具有压缩存储器的计算机系统如何与操作系统和磁盘交互，其中压缩存储器增加了如本文所公开的选择器和辅助存储器。
图5描述了所公开的压缩存储空间的存储器布局。
图6描述了辅助存储器维持压缩存储空间的存储器布局的过程。
图7描述了用于定位储存在辅助存储器中的页面的数据结构。
图8描述了辅助存储器的内容的示例性布局。
图9描述了辅助存储器拦截并响应来自VMM的页面调出(page-out)请求的过程。
图10描述了辅助存储器拦截并响应来自VMM的页面调入(page-in)请求的过程。
图11描述了从虚拟地址到物理地址到压缩地址的地址转换。
图12描述了用于零复制辅助存储器(Zero-copy Auxiliary memory)实施方式的压缩页面的示例性存储器布局以及支持所述布局所需的元数据。
图13描述了零复制辅助存储器实施方式中的换入(swap-in)操作的示例性过程。
图14描述了零复制辅助存储器实施方式中的换出(swap-out)操作的示例性过程。
图15描述了压缩页面的示例性存储器布局，其用于压缩页面分割以更好地利用空闲存储空间的实施方式。
图16包括两副图16A和16B。图16A描述了包含高速缓存行的未压缩页面的布局，而图16B描述了压缩形式的同一页面包含压缩和压紧的高速缓存行。
图17描述了粗粒度分段存储器(coarse-grain segmented memory)的示例性存储器布局，其中压缩页面与连续分段相关联。
图18描述了粗粒度分段存储器的示例性存储器布局，其中压缩页面与非连续分段相关联。
图19描述了细粒度分段存储器(fine-grain segmented memory)的示例性存储器布局，其中压缩页面与连续分段相关联。
图20描述了未压缩形式的示例性扇区布局。
图21描述了压缩形式的示例性扇区布局。
图22描述了示例性的基于扇区的转换元数据格式，其中扇区元数据包括扇区指针(PTR)。
图23描述了示例性的基于扇区的转换元数据格式，其中扇区元数据包括扇区指针(PTR)，并且压缩大小元数据(CSM)与压缩数据混合。
图24描述了示例性的基于扇区的转换元数据格式，其中扇区元数据包括扇区指针(PTR)和压缩扇区大小(SIZE)以及压缩大小元数据(CSM)与压缩数据混合。
图25描述了用于访问驻留在物理计算机存储器中的压缩式计算机存储器的方法的第一实施方式，其中转换元数据遵循图22的示例性格式，并且其中该方法与图27中的设备相关联。
图25B描述了用于访问驻留在物理计算机存储器中的压缩式计算机存储器的方法的第三实施方式，其中该方法与图28中的设备相关联。
图26描述了用于访问驻留在物理计算机存储器中的压缩式计算机存储器的方法的第二实施方式，其中转换元数据遵循图23或图24的示例性格式，并且该方法与图27B中的设备相关联。
图27描述了用于访问驻留在物理计算机存储器中的压缩式计算机存储器的设备的第一实施方式，其中该设备与图25中的方法相关联。
图27B描述了用于访问驻留在物理计算机存储器中的压缩式计算机存储器的设备的第二实施方式，其中该设备与图26中的方法相关联。
图27C描述了用于访问驻留在物理计算机存储器中的压缩式计算机存储器的设备的第二实施方式的替代方案。
图28描述了用于访问驻留在物理计算机存储器中的压缩式计算机存储器的设备的第三实施方式，其中增加了动态数据选择控制(Ctrl)机制，并且其中图25B中示出了相关方法。
图29描述了示例性的基于扇区的混合转换元数据格式，其中地址转换元数据包括扇区指针(PTR)和高速缓存行大小(CL-SIZE)。
图30A至图30B描述了基于扇区的混合转换方法的第一示例，其中转换元数据遵循图29的示例性格式，并且其中总是根据读取请求来提取扇区，但压缩数据以扇区或高速缓存行间隔尺寸写入，其中图30B是图30A的某些部分的详细视图。
图31A至图31D描述了基于扇区的混合转换方法的第二示例，其中转换元数据遵循图29的示例性格式，其中添加了动态数据选择控制(Ctrl)过程以决定根据读取请求提取的压缩数据是压缩扇区还是压缩高速缓存行，并且其中图31B至图31D是图31A的详细视图。
图32描述了用于访问驻留在物理计算机存储器中的压缩式计算机存储器的设备的第四实施方式，其中转换元数据遵循图29的示例性格式。
图33包括图33A和图33B。每个图描述了示例性的基于扇区的混合转换元数据格式，其中每个扇区内的压缩高速缓存行被限制为特定大小，因此地址转换元数据包括扇区指针(PTR)和每个扇区的一个CL-SIZE。在图33A中扇区日志大小(SectorLogSize)为8，在图33B中为4。
图34描述了示例性的基于扇区的转换元数据格式，其中每个扇区内的压缩数据的顺序已经改变为空间参考位置性的系数(在此图中跨度为2)。
图35描述了示例性的压缩页面，其中压缩高速缓存行被压紧并且可以放置在任何字节位置。
图36描述了图35的示例性压缩页面，其中压缩高速缓存行与固定大小的分段相关联，因此它们在压缩空间中的位置与分段边界对齐。
图37描述了图35的示例性压缩页面，其中压缩高速缓存行与可变大小的分段相关联，因此它们在压缩空间中的位置适应最频繁的压缩高速缓存行大小。这使用了与图36相同的元数据，但可以实现更好的压缩和压缩空间利用率。
图38描述了启发式方法的实施方式，该方法找到合适的可变长度的分段格式，从而使开销(overhead)最小化。
图39包括两个图39A和图39B。图39A描述了示例性页面帧，其中扇区被压缩，但在其原始位置(与未压缩时一样)对齐，留下未使用的空闲空间。图39B描述了图39A的同一页面，其中扇区1由于扇区1内的动态数据变化而扩展了大小。
图40包括两个图40A和图40B。图40A描述了示例性的页面帧，其中压缩页面包括彼此相邻压缩和压紧的扇区，以便利用空闲空间(释放区域)来映射牺牲页面以及与所述压缩页面相关联的区间(Range)。图40B描述了图40A的同一页面，其中扇区1由于扇区1内的动态数据变化而扩展了大小。
图41A至图41C描述了扇区溢出方法的实施方式，其中图41B至图41C是图41A的详细视图。
图42描述了扇区溢出设备的实施方式。
图43描述了存储器压缩系统的实施方式，该存储器压缩系统包括基于扇区的地址转换设备、扇区溢出设备、辅助存储器设备、压缩和解压缩设备以及压缩存储器，该压缩存储器还包括区间以及压缩数据。
图44描述了用于如本文中所述的计算机系统的压缩存储器管理方法。
图45描述了用于访问驻留在如本文中所述的物理计算机存储器中的压缩式计算机存储器的方法。
具体实施方式
没有压缩存储器的计算机系统
图1中描述了常规计算机系统100的示例性实施方式。该系统包括微处理器芯片110和一个或多个存储模块，所述存储模块被表示为M
如图1中的实施方式所例示，计算机系统可能因被表示为M
带有压缩存储器的计算机系统
为了特别解决主存储容量有限和存储器带宽有限的问题，图1中的示例性系统可以被配置成能将数据和指令压缩到主存储器中。在图2示出这样的计算机系统200。在微处理器芯片210上增加了三个功能块。这些块包括地址转换单元211、压缩器单元212和解压缩器单元213。这些块一侧与存储器控制器相连，而另一侧与最后一级高速缓存C3相连。地址转换单元211的目的是将常规的物理地址PA转换成压缩地址CA，以在压缩存储器中定位存储块。本领域技术人员认识到，在压缩存储器中需要这样的地址转换，因为在未压缩的常规系统中使用的固定大小的页面(例如4KB)可以被压缩到小于压缩式存储系统中物理地址空间的固定大小的任何大小。
压缩器单元212的目的是压缩已经被修改并从最后一级高速缓存中逐出的存储块。为了对存储器系统的性能产生的影响可以忽略不计，压缩必须快速并且通常由专用的压缩器单元加速。类似地，当由处理器请求存储块并且在任何一级高速缓存(例如，在图2的示例性实施方式中的C1、C2和C3)中不可用时，必须从主存储器M
压缩式存储系统的目标之一是有效地增加主存储器，并避免对次级慢速存储器或次级储存设备(例如磁盘)进行高代价的访问。图3示出了作为示例性实施方式的计算机系统300，该计算机系统300已经扩展(与图2中的计算机系统200相比)有以磁盘330形式的次级存储器。在常规的计算机系统中，当在主存储器(例如存储器芯片M
如图1中的所示没有压缩存储器的常规计算机系统仍然可以使用操作系统中的常规支持来获得容量增加。图3示出了根据图1的实施方式的没有压缩存储器的常规计算机系统300。在常规的存储器系统中，操作系统320中的虚拟存储器管理器(VMM)负责在请求新页面(页面调入)或逐出修改过的页面以便为另一个页面留出空间(页面调出)时向磁盘330提出请求。一些系统在物理存储器(这里以存储模块M
辅助存储器-基本概念
在压缩式存储系统中，固定大小的物理存储器的某些部分将用于压缩存储块-称为活动部分(active portion)，而物理存储器的其余部分将包括通过存储器压缩释放出来而不使用的部分-不动部分(passive portion)。辅助存储器由被动部分组成，以扩展物理存储器的容量。辅助存储器管理通过将页面放置在释放出来的部分中以供处理器使用来扩展存储器的容量。在一些实施方式中，页面在物理存储器的活动部分和不动部分之间移动，而在另一些实施方式中，活动部分和不动部分被直接访问。
图4提供了所公开的辅助存储器概念的概述。为计算机系统400提供了压缩存储器管理设置405。计算机系统400具有一个或更多个处理器P
压缩存储器管理设置405包括辅助存储器440，其用于维持可压缩主存储器414的压缩存储空间的布局。该布局包括各个存储页面的大小和位置以及压缩存储空间中的空闲存储区域。此外，压缩存储器管理设置405包括使操作系统420、次级存储器450和辅助存储器440交互的选择器功能430。
如将在下面参考的详细说明，存储器管理设置405被配置为a)触发可压缩主存储器414中的存储页面的压缩；b)拦截从操作系统420向次级存储器450提出的页面调入请求，使用由辅助存储器440维持的压缩存储空间的布局，以在可用时在辅助存储器430中定位由页面调入请求的页面，并使定位的请求页面可用在压缩存储空间的活动部分中；以及c)拦截从操作系统420向次级存储器450提出的页面调出请求，使用由辅助存储器440维持的压缩存储空间布局，以为由页面调出请求所请求的页面获得空闲区域，并在辅助存储器440获得的空闲区域中容纳请求页面。
在一些实施方式中，辅助存储器440(即，压缩存储空间的非活动部分)物理上驻留在可压缩主存储器414中，并且表示可压缩主存储器414中通过存储器压缩而释放的区域。在其他实施方式中，辅助存储器440可以在与可压缩主存储器414物理上分离的存储器中维持可压缩主存储器414的压缩存储空间的布局。
如下文将进一步详细解释的，压缩存储器管理设置405的选择器功能430可以被配置为根据系统条件和相关策略来触发存储页面的压缩。此外，当存储页面要被页面调出时或当存储页面要被页面调入时，选择器功能430可以被配置为在分配新的存储页面(参见下面图6中的611)时触发存储页面的压缩。
图44中公开了用于计算机系统400的相应的通用压缩存储器管理方法4400。压缩存储器管理方法4400包括在辅助存储器440中维持4410可压缩主存储器414的压缩存储空间的布局，该布局包括各个存储页面的大小和位置以及所述压缩存储空间中的空闲存储区域。该方法还包括：a)触发4420对可压缩主存储器414中的存储页面的压缩；b)拦截4430从操作系统420向次级存储器450提出的页面调入请求，使用4432由辅助存储器440维持的压缩存储空间的布局，在可用时在辅助存储器430中定位由页面调入请求所请求的页面，并使4434所定位的请求页面可用在压缩存储空间的活动部分中，以及c)拦截4440从操作系统420向次级存储器450提出的页面调出请求，使用4442由辅助存储器440维持的压缩存储空间的布局以为由页面调出请求所请求的页面获得空闲区域，并将在辅助存储器440的获得的空闲区域中容纳4444请求页面。
参考回图4，在任何时间点上，空闲空间都由图4所示的辅助存储器440跟踪和管理。辅助存储器440可以通过设备驱动器(这里称为选择器并实现上述选择器功能430)与计算机系统410交互，该计算机系统410如图2所示的支持压缩存储器，通常由常规的操作系统例行程序访问。在一个示例性实施方式中，所述设备可以具有与磁盘类似的接口。在另一个示例性实施方式中，所述设备可以具有类似于前端交换的接口。选择器430也可以触发页面的压缩。辅助存储器可以以将在后面描述的方式访问主存储器的空闲空间。与现有技术中提出的存储器设备(例如ZSWAP或ZRAM)类似，辅助存储器的目标是通过将它们交换到物理存储器中的某个区域(释放空间)而不是交换到磁盘，从而避免对磁盘的高代价访问。然而，诸如ZSWAP等技术为存储器设备专门划定了固定的存储区域，并可选地尝试压缩其内容，以便为上述区域中的更多的页面腾出空间。然而，它们并没有利用由压缩式存储系统提供的整个物理存储器中释放的存储空间。
本文中公开的辅助存储器收集了压缩式存储系统中释放的所有存储空间。由于释放的内存的量随时间变化，取决于当前的压缩比，因此辅助存储器没有固定的大小。它的大小与可用的空闲空间的当前量相同，并将随着时间的流逝而随着主存储器中存在的页面的可压缩性相应地变化。
辅助存储器-第一种实施方式
现在详细说明在一个实施方式中辅助存储器是如何实现和操作的。这在图5-9中进行说明。该实施方式不应被解释为优选的实施方式。本领域技术人员可以实现替代性实施方式。意图是，这种替代性实施方式也涵盖在本发明公开的内容中。
图5示出了如何将物理地址空间510中的物理页面映射到压缩地址空间520中的压缩存储器中的示例性存储器布局。在常规的存储系统中，如物理地址空间515的存储器布局所示，物理页面在主存储器中被一个接一个地映射。例如，假设页面大小为4KB，则第一页面从地址0开始，并且下一个页面从字节地址2
在所描述的实施方式中，假设任何物理页面将从压缩存储空间中的相同地址开始，如同在常规的非压缩(线性)式物理地址空间中一样。例如，如在压缩地址空间525的存储器布局中所见，页面0从物理地址空间以及压缩地址空间中的第一地址开始，如虚线530所描述的那样。类似地，第二页面从物理地址空间和压缩地址空间中的字节地址2
图6示出了过程610，通过该过程，辅助存储器在任何时间点都可能触发页面的压缩，并保持着物理页面如何在压缩地址空间中的映射以及所有空闲分段在压缩地址空间中位于何处的最新记录。就像在常规的存储系统中一样，新页面响应于磁盘读取操作或页面分配事件而被分配在主存储器中611。与常规的存储系统中不同，在压缩式存储系统中，并且参考过程612中的第一动作，每个进入主存储系统的新页面将潜在地首先被硬件加速器潜在地压缩。在这个过程中，除了空闲碎片的起始地址和大小之外，还确定了页面的大小。这被记录在存储器640的专用区域中，辅助存储器630和压缩存储器650中的机制达成一致，并且两者都可以读取和修改。专用存储区域640也被称为元储存(MetaStorage)(以下，专用存储区域和元储存可互换使用)。在替代的实施方式中，当页面被分配时，可以被压缩或可以不被压缩，而在某些系统条件下，例如当系统存储器利用率较高或当页面被换出时，页面可以被压缩。
辅助存储器以如下方式跟踪每个新压缩页面613的位置和所有贡献给空闲空间614的空闲碎片。每次VMM分配新页面时，该分配请求被图4中的选择器430拦截，该选择器430将该请求连同该页面的物理起始地址一起转发到辅助存储器440。在替代实施方式中，选择器430可以根据系统条件而决定要压缩哪些页面。例如，在一个实施方式中，当页面被VMM逐出时，就对页面进行压缩。由于辅助存储器可以通过上述专用区域640访问每个压缩页面的大小，因此它可以计算相应空闲碎片的大小和起始地址。辅助存储器在数据结构中维持空闲碎片的索引，该索引能使用碎片的大小作为属性进行有效搜索。图6示出了这样的搜索树620的示例性实施方式，它以对数时间提供搜索操作，其中每个记录(am_ff)621的碎片大小是属性。如示例性搜索树所示，如果大小小于或等于当前记录，则搜索向左进行622，而如果大小大于当前最高的记录，则搜索向右进行623。在不同的实施方式中，可以使用具有概率保证的数据结构(例如跳过列表)。最终的结果是，辅助存储器在任何时间点都会跟踪有关每个页面映射的位置和所有空闲碎片的位置和大小的存储器布局，也就是说，从存储器压缩中获得的当前可用的释放存储器。
因此，如上文已经针对图6所说明的，当存储页面被触发而被压缩时，图4中的压缩存储器管理设置405可以被配置为：压缩存储页面612；确定压缩存储页面的大小612；确定由存储页面的压缩释放出来的存储区域的起始地址和大小；在由辅助存储器440维持的压缩存储空间的布局中插入压缩存储页面613；以及在由辅助存储器440维持的压缩存储空间的布局中插入所释放的存储区域的起始地址和大小614。
另外，图4中的压缩存储器管理设置405可以被配置为将释放的存储区域的起始地址和大小插入614到归因于所释放的存储区域的大小的数据结构(诸如搜索树620)中，所述数据结构是由辅助存储器440维持的压缩存储空间的布局的一部分。
现在将注意力转向辅助存储器如何充当由VMM逐出的页面的快速备份储存。在常规系统中，如果这些页面没有被修改或以其他方式发送到磁盘或固定大小的专用交换空间(诸如ZSWAP或ZRAM)，则这些页面通常会被丢弃。在固定大小的专用交换空间中，页面调入(从磁盘读到物理存储器的页面)和页面调出(从物理存储器中逐出的页面)操作是微不足道的，而且很好理解。相反，辅助存储器的大小是变化的，各个碎片的大小也是变化的，这取决于每个页面在压缩存储器中的压缩程度。这就提出了所公开的发明所要解决的一些问题。
再次回顾图4，在页面调出操作中，操作系统将使用设备驱动器向磁盘发送请求。在所公开的发明中，提出了一种新的设备驱动器(称为选择器430)，它将拦截操作系统中来自VMM的所有页面调出操作。选择器将尝试将页面储存在辅助存储器440中可用的空闲空间中，而不是丢弃该页面或将其写回到磁盘，以便以后避免高代价的磁盘访问。在辅助存储器不具有用于该页面的空间的情况下，它将不得不通过逐出一个或多个当前储存的页面来为其腾出空间。然后，这些页面被逐出到磁盘450中。同样，在页面调入操作中，选择器将拦截请求，而不是从磁盘请求页面。如果该页面存在于辅助存储器中，则辅助存储器将响应并将该页面从空闲碎片转移到由操作系统确定的位置。可选的，为了避免通过基本的加载和储存操作进行高代价的转移操作，可以使用DMA(直接存储器转移)支持来加速此操作。请注意，从辅助存储器转移的页面将不会被解压缩。在辅助存储器不要具有所请求的页面得情况下，必须从磁盘450中检索该页面。现在详细描述这些过程中的每个过程，如图7-9所示。
对于所描述的实施方式，首先描述一些关键的数据结构，这些数据结构被辅助存储器用来定位驻留在其中的页面。图7以树的形式示出了数据结构，该数据结构跟踪储存在辅助存储器中的每个页面的位置。驻留在辅助存储器中的每个页面与起始地址、其大小(压缩后)和标识(表示为Id)相关联。起始地址由页面被储存在辅助存储器中的位置确定，并且确定该地址的过程将在后面描述。结合图6进行描述，其大小从前述的称为“专用存储区域”的数据结构已知。所述标识，即“Id”，由操作系统中的VMM提供。任何来自VMM的对磁盘的请求，根据有关图4的描述，由选择器430拦截。选择器建立数据结构，该数据结构包含关于储存在辅助存储器中并以Id作为唯一标识符的任何页面的信息。因此，Id可以被选择器用来确定该页面是否驻留在辅助存储器中。回到图7，驻留在辅助存储器中的页面由所示的示例性树结构来跟踪。为了定位页面，Id被用作关键字(key)，并且遍历树以定位在对数时间内定位的页面的记录。在每个节点上，如果该Id小于节点的Id，则在左分支720中进行搜索，否则在右分支730中进行搜索。在不同的实施方式中，可以使用支持基于关键字的搜索而不是树的其他数据结构，例如哈希表和关键字值储存。
回到压缩式存储系统的示例性但任意的时间点的存储器布局，根据图5，空闲空间550是由所有空闲碎片构成的。回顾这些空闲碎片构成了可用于辅助存储器的存储器，考虑一个示例性的快照，该“释放的”空间是如何使用的。这在图8中进行了说明。其示出了三个示例性页面(页面0、页面1和页面2)的存储器布局。聚焦于储存页面0(810)的页面帧的示例性使用，在图8的左边，注意到页面0(810)占据了为其分配的物理页面帧的第一部分。释放的空间，如果没有使用，则与其余部分相关联。在示例性快照中，在空闲碎片中分配了当前使用了释放的空间的页面，表示为“换出的页面”830。在所述实施方式中，储存在辅助存储器中的页面将被分配在尚未分配的空闲碎片中，该页面将被储存在页面帧的末端。因此，放置“换出的页面”830。在分配了换出的页面之后，将创建新的空闲碎片(820)，其大小是页面帧的大小减去压缩页面和换出的页面的大小之间的差值，即，原空闲碎片中分配的储存页面。
当来自VMM的分配和释放请求到达辅助存储器时，空闲碎片将被换出的页面所占用，并将创建新的空闲碎片。作为示例性快照，考虑图8中储存页面1的页面帧的布局。在这里，页面1被分配在页面帧的起始端，然后是空闲碎片，然后是储存在辅助存储器中的页面(换出的页面)，然后是空闲碎片，最后是另一个换出的页面。最后，对于图8的最右边，页面帧被分配的页面占据，表示页面2，而页面帧的其余部分是空闲碎片。
图9描述了辅助存储器处理页面调出请求的过程。当操作系统的VMM已经决定逐出页面时，回顾如关于图4所解释的，相应的页面调出请求被选择器430拦截。辅助存储器通过从选择器430中检索该页面的页面条目信息910开始。下一步是从存储器布局中检索该页面的大小920。如关于图6所解释的，辅助存储器可以通过存储器640中的专用区域访问其存储器布局中的每个页面的大小，如在图5的背景中所述。然后，它通过在图6的树状数据结构620中进行搜索来使用该信息寻找页面的空间930。如果存在空间，对应于判定框940中的“是”，则启动从其当前位置到搜索空间中标识的空闲碎片的页面转移950。这可以通过简单的加载/储存操作来完成，或者通过直接存储器访问(DMA)来加速。利用与该页面相对应的新记录更新与图7有关描述的搜索结构700，以便以后可以对其进行定位。另一方面，如果不存在空间，则当前驻留在辅助存储器中的一个页面或可能是多个页面可能必须被逐出并转移到磁盘960。当辅助存储器中存在用于逐出页面的空间时，该页面从碎片的末端复制，以便如图8的示例性存储器布局中所示，尽可能远离共享相同页面帧的压缩页面。当压缩页面的大小将由于动态数据变化而增加时，这一点很重要。在不同的实施方式中，如果要被逐出的页面是压缩的，并且在同一帧中驻留有其他换出的页面，例如在图8的页面0中，则选择器可以选择将压缩的页面810和换出的页面830同时转移到辅助存储器的另一部分，将其称为“急切的页面调出逐出”。本领域技术人员可以考虑使用依靠后面描述的溢出机制的惰性逐出的替代实施方式。
无论如何，除非已存入辅助存储器的页面具有与空闲碎片完全相同的大小，否则将创建比原来的空闲碎片小的新的空闲碎片。这个空闲碎片被保留在图6中620的搜索结构中，以帮助后续的页面调出操作。
如将从上面理解的那样，图4中的压缩存储器管理设置405因此被进一步配置为通过检查由辅助存储器440维持的压缩存储空间的布局，以找到对所请求的页面来说足够大的空闲区域，从而为由页面调出请求所请求的页面获得空闲区域。如果找到足够大的空闲区域，则压缩存储器管理布局405在找到的空闲区域中容纳所请求的页面，否则在辅助存储器440中选择牺牲页面，通过将牺牲页面写入次级存储器450来逐出该牺牲页面，并从通过逐出牺牲页面而释放的空间中获得空闲区域。在替代实施方式中，如果没有找到足够大的空闲区域，则在辅助存储器440中选择牺牲页面，并且只要存在足够大以容纳将所述牺牲页面拆分得到的所有子页面的多个空闲区域，就将牺牲页面分割成多个子页面。否则，通过将牺牲页面写入次级存储器450来逐出牺牲页面，以从逐出牺牲页面所释放的空间中获得空闲区域。在另一替代实施方式中，如果没有找到足够大的空闲区域，则只要存在足够大以容纳将所请求的页面拆分得到的所有子页面的多个空闲区域，就将请求的页面分割成多个子页面。否则，在辅助存储器440中选择牺牲页面，并通过将牺牲页面写入次级存储器450来逐出牺牲页面，其中，空闲区域从通过逐出牺牲页面而释放的空间中获得。
图10描述了辅助存储器处理页面调入请求的过程1000。首先，在每个页面调入请求中，VMM将提供包括所请求的页面的虚拟地址或唯一的Id以及该页面将被复制到的物理地址(称为“空闲页面帧地址”以供后续参考)的页面条目信息1010。选择器430跟踪当前储存在辅助存储器中的所有页面及其相关的Id。如果没有找到该页面，即，没有匹配的Id，则判定框1030选择下一步是从磁盘中检索该页面1050，像在常规系统中那样。另一方面，如果有匹配的，下一步是在辅助存储器中定位该页面1040。然后，该请求被转发到带有上述“空闲页面帧地址”的辅助存储器。辅助存储器使用由选择器提供的Id，以通过识别与图7所述的搜索数据结构700中与页面相关联的记录来定位该块。当记录被定位时，它可以在由辅助存储器维持的空闲空间中检索所请求的页面的大小和起始地址。然而，在它能将该页面复制到由VMM支配的“空闲页面帧地址”之前，它必须确定所请求的页面的大小与上述“空闲页面帧地址”的大小相同或更小。辅助存储器将在涉及图6所述的专用存储区域640中进行查找，以建立可用于所请求的页面的大小。如果所请求的页面大小大于可用的大小，则必须回收空间。这包括将储存在该页面帧的空闲碎片中的一个或几个页面移动到辅助存储器中的其它可用的空闲碎片。这遵循与图9有关的描述的页面调出过程。这可能导致多个存储器对存储器的复制操作，这些操作可以由普通的加载/储存或备选的DMA支持。为了避免一些此类的复制操作，可以使用几种试探性方法。一种试探性方法是不考虑储存在辅助存储器中未压缩的页面。另一种试探性方法是在辅助存储器中只储存压缩到一定程度的页面。可以考虑其他试探性方法，这些方法可以被本领域技术人员所理解，并且旨在成为本专利公开的一部分。
正如已经提到的，压缩页面的大小在其生命周期内可能动态变化。本发明包括跟踪这种变化并协助维持存储器布局的系统、设备和方法。当压缩页面的大小在存储器写入操作期间被修改时，该修改可能是由硬件加速器完成的，该页面可能会扩展到随后的空闲碎片(例如，如图8的页面0)，或者收缩创建更多的空闲空间。随着页面的新写入请求到达存储器，负责处理页面的实际压缩大小的变化的设备从现在起被称为溢出设备(overflowdevice)。稍后将参考图39至图43描述扇区溢出设备和相关的扇区溢出处理的一个示例性实施方式；然而，正如技术人员将易于认识到的，其他实施方式也是完全可以想到的。在压缩页面扩展的长度足以开销整个下面的空闲碎片并与换出的页面相冲突的情况下，本发明包括中断机制。所述中断机制确保被换出的页面不会被覆盖，并且辅助存储器应将其适当移动到空闲空间，以供压缩页面扩展。
现在详细说明跟踪页面大小的动态变化的系统的一个实施方式。在专用存储区域(640)中跟踪关于压缩页面的大小和它们与空闲碎片之间的边界的信息。图8中示出了示例性的页面帧。所述信息包括压缩页面的大小、示出第一空闲碎片开始的边界(803)和示出换出的页面驻留的边界(806)(如果有的话)。由于压缩存储器机制(即，上述溢出设备)和辅助存储器都可能修改专用存储区域(640)中的信息，因此包括锁定机制以保护数据不被损坏。溢出设备可以利用下面的空闲碎片自由地扩展压缩页面的大小，并适当地移动相关边界(FB 803)，但不超过表示换出页面所在的边界(VB806)。每当需要使用空闲碎片时，压缩大小的修改可以由辅助存储器通过验证专用存储区域的内容进行跟踪。在不同的实施方式中，这种验证可以周期性地进行。在另一个实施方式中，可以使用附加的硬件加速信息系统来将这种变化从溢出设备传播到辅助存储器。当辅助存储器利用空闲碎片并放置换出的页面时，或者当辅助存储器处理页面调入请求时，辅助存储器修改专用存储区域(640)的内容。回到溢出设备可能扩展压缩页面的情况，如果下面的空闲碎片不够大并且两个边界发生冲突，则溢出设备就会引发中断，而辅助存储器通过移动换出页面来处理它的方法，类似于页面调出操作，以释放更多的空间。
如上所述，存储器管理设置405被配置为处理压缩页面中的动态数据变化。此外，存储器管理设置405被配置为通过以下方式跟踪动态数据变化：作为一个或更多个新写入请求的结果，能使压缩存储页面扩展到压缩存储空间中的空闲存储区域(可能是相邻的空闲存储区域)；如果压缩存储页面扩展到压缩存储空间中的相邻的换出的页面，则引起中断；以及通过捕获中断并将换出的页面移动到空闲存储区域来保护换出的页面不被覆盖，从而能使压缩存储页面扩展。
辅助存储器-第二种实施方式
将“活动页面”定义为当前正在被应用程序或系统使用的存储器的页面，这意味着它存在于物理存储器中，即在操作系统的页面表中，在它的虚拟地址与它的物理地址之间存在有效的映射。因此，它可以被处理器直接使用标准的加载和储存指令进行读取或写入。将已经从物理存储器中丢弃的存储页面称为“非活动页面”，例如已经被选择储存在层次的较低部分(例如交换储存器空间)中的页面。因此，基于如在前面的辅助存储器实施方式中所描述的本发明，在使用压缩地址空间寻址的主存储器(即，实际压缩存储器)中可以同时存在活动页面和非活动页面。不同之处在于，例如，当处理器加载或储存命令被触发时，或者作为第二个示例，当操作系统触发页面调出操作时，活动页面必须能够被即时找到。另一方面，通过所述存储器检索由辅助存储器放置在压缩存储器中的非活动页面。
在图5的示例性存储器布局中，物理地址空间维持了存储器的未压缩视图，该视图是暴露给操作系统和处理器的，使得存储器压缩对处理器/操作系统的其余部分是透明的。压缩地址空间也是以页面帧划分的，其中每个帧具有与物理地址空间相同的固定大小。在所述示例性存储器布局中，由OS映射到物理页面帧的活动页面，例如页面1(图5的左侧)，也期望在压缩地址空间中的同一帧中被找到，即也是页面1(图5的右侧)。不同之处在于，在物理地址空间中页面的大小总是固定的(例如，4KB)，而在压缩地址空间中页面的大小可能是不同的。因此，通过这样的存储器布局，从物理地址空间到压缩地址空间的转换仅需要包括压缩活动页面的实际大小，以便辅助存储器知道在需要时(例如在页面调出操作时)要复制或移动的数据量。
换句话说，所有活动页面都被定位并与非压缩式存储系统中的存储器帧对齐。这意味着，由操作系统给出的物理页面帧的地址隐含地指向压缩空间中数据的起始端。为了支持这种转换，系统需要在每当选择页面用于换入或换出情况时，在辅助存储空间内来回复制或移动压缩页面。这可能会导致不必要的数据转移。
在所提出的辅助存储器的第二个实施方式中，称为零复制(Zero-Copy)，通过引入从物理地址到压缩地址的替代的存储器转换过程，可以避免前面提到的在辅助存储空间和操作系统管理的物理存储空间之间的页面转移。在这种情况下，如图11所示，虚拟地址1110中的页面号1114被操作系统转换成帧号1124，从而得到物理地址1120。然后在零复制是虚拟帧的情况下的该帧号被转换成物理存储器帧(也称为压缩帧-CFrame)1134和压缩帧偏移(CF-Offset)1136，因为在物理地址空间和压缩地址空间中页面的起始地址之间没有对齐。使用通常储存在元储存(图6的专用存储区域640)中的额外元数据(在下一段中详述)来执行这最后的转换1124。
在压缩空间和空闲空间的第一种示例性管理中，压缩帧的起始端留空，以便OS能够轻松地分配新的存储空间。因此，在零复制中，页面在第一次成为换出事件的目标时被移动一次。图12中示出了存储器布局与示例交换事件的演变的示例；对于用拉丁编号表示的三个执行点，存在所述布局的三个示例性实例：i、ii和iii。
压缩存储器1210包括页面帧1211(例如，存储器布局1210i中的1211ai、1211bi等)。活动页面PA 1214i最初与页面帧0×10 1211ai对齐。活动页面还具有相应的空间，以用于在其内容导致压缩比改变的情况下使其大小增长；在前述的辅助存储器实施方式中，所述空间是以图8中边界FB 803和VB 806限定的空闲碎片。所述空间被称为区间(Range)；对于PA 1214i来说，该区间是RA 1212i，即帧1211ai中的其余空间。用于压缩页面PA 1214i的转换元数据包括两对字段：一对是压缩帧1222i和压缩帧偏移1224i，它们限定了该页面储存在压缩存储器中的位置；第二对RAb 1226i和RAe 1228i限定了与PA相关联的区间边界；RAb 1226i是区间RA的起始地址，而RAe 1228i是所述区间的结束地址。此外，在第一布局实例i中，还有两个其他页面PB 1215i和PC 1217i，它们是不活动的，并储存在帧1211ci中。如果系统现在请求针对PA 1214i的换出事件，则调用辅助存储器，并在帧1211bii(布局实例ii)中给PA空闲碎片。该页面被选择为不完全置于所述帧1211bii的末端，以便每当PA成为活动状态时可以在那里分配区间。对于另一个新的事件，该事件是针对页面PC 1217ii的换入事件，所述处于非活动状态的页面没有被移动到请求1230iii中的交换中提到的帧0×15，而是维持在它所在的帧0×12中，并且由零复制辅助存储器系统通过修改元储存1220iii中的相应条目而设置为“活动”。第一对字段是压缩帧0×12 1222iii和压缩帧偏移0×70 1224iii，表示压缩页面PC的起始地址和偏移量；第二对字段限定了与PC相关联的区间，该PC为RC 1219iii，其地址区间为RCb 1226iii和RCe 1228iii。注意，所述页面PC的元储存条目由OS在换入事件中提供的帧数(0×15)确定。如图所示，活动页面现在可以在存储器的任何位置，而不仅仅是与帧边界对齐。
在替代实施方式中，当PA 1214i被换出到帧1211bii时，页面被放置在帧的末端，比前述实施方式更有效地利用了空闲区域。然而，如果它成为活动的，那么如果在所述帧中没有可用的空间来分配给区间，或者被分配到远程区间，或者根本没有分配到任何区间，则可以选择将页面移动到另一个用于区间的空间的帧中，并且如果“区间”扩展，需要移动到另一个帧。
在图13的流程图中呈现零复制实施方式中的换入事件所遵循的事件顺序。如果发出换入事件以将页面X从交换空间带到帧Y，则首先检查页面X是否存在于辅助存储空间中1310。如果该页面不存在，则需要找到足够大的空闲碎片，将页面内容带入1320，并记录空闲碎片位置1330。注意，该空闲碎片不需要像前面的实施方式那样与帧的起始端对齐。然后使用例如如前所述的DMA操作转移该页面1340。其位置的起始地址是由压缩帧和压缩帧偏移提供的，它们需要被复制到帧Y的元数据中的第一对字段(1370)。其余的空闲碎片空间被用作分配给输入页面的区间1360，因此它的边界地址(起始端和末端)也被复制到帧Y的元储存条目中1370。
如果页面存在于辅助存储器中(检查1310中的结果为“是”)，则它的起始地址(即，成对的压缩帧和压缩帧偏移)被填入帧Y的元储存条目中。通过在帧Y的元储存条目的其余字段中填入该区间的起始端和结束端地址(Rb和Re)，为页面分配区间。请注意，在这种情况下，没有数据转移以将辅助存储器中的页面设置为活动状态。
在图14的流程图中呈现零复制辅助存储器实施方式中的换出事件所遵循的步骤顺序。对当前被分配到帧Y的页面X发出换出事件；所述帧Y的分配是由OS完成的，但不一定是页面X被储存在压缩存储器中的帧。首先检查这是否为该页面X的第一次换出1410。这是通过检查压缩帧偏移是否等于0来完成的，这意味着该页面与帧边界对齐，因为如前所述，执行将页面从帧的起始端带到帧的结束端。在这是页面X第一次换出的情况下，那么就会在辅助存储器中查询用于储存该页面的空闲碎片1420。请注意，如果找不到空闲碎片，将执行程序从辅助存储器中逐出页面，以释放所需的空间，如第[0100]段所述。当识别出空闲碎片时，该页面将被移动到该目的地1430。这是零复制实施方式中唯一的默认数据转移。用于空闲碎片的更新大小和页面的信息都由辅助存储器运行时管理1440。由于该页面现在是不活动的，因此删除用于帧Y的元储存中的元数据(1450)。
对于这不是页面X的第一次换出(1410的结果“否”)的情况，那么程序是通过删除元储存中的用于帧Y的条目使该页面不活动1450。
在零复制辅助存储器的实施方式中，除了第一次换出操作时的默认页面转移外，不需要再进行页面移动。在替代实施方式中，如果页面的压缩大小由于页面数据的动态变化而发生变化，导致页面无法适应帧中的指定区域，从而需要移动页面，则可以进行页面移动。在第二种替代实施方式中，可以移动其他页面或数据来代替。在第三种实施方式中，可以对页面进行解压缩。其他替代性的方案可以由本领域的技术人员实现。
在前面所述的辅助存储器的实施方式中，当存在请求以将页面移动到辅助存储器中的空闲碎片时，如果没有足够大的空闲碎片来储存所述页面，则需要将所述页面储存在较低级的存储层次(即，交换空间)中。虽然单个空闲碎片可能无法满足该请求，但可用的总空闲碎片空间可能足够大，以满足该相同请求。因此，针对这些实施方式的优化方案被称为页面拆分(Split-Page)，并且能够将压缩后的页面拆分成不同的块，这些块可以被储存到多个可用的空闲碎片中。所述块不是固定大小的，因此页面拆分不会受到内部碎片化的影响。
在图15的示例性实施方式1500中，压缩页面1514i在换出事件时被拆分成两个块1514aii和1514bii。在替代实施方式中，拆分可以以额外的元数据信息为代价延伸至任何数量的块，以跟踪原始页面的不同部分被储存的空闲碎片。如果每个页面可以被储存成两个不同的空闲碎片，则有必要跟踪所述两个碎片的两个起始地址，以储存原始压缩页面的两个拆分部分。显然推断，如果要支持将压缩页面拆分成N个部分，则这将导致储存N个指向可能的块的指针，其中所述部分将被储存在辅助存储器中。
在辅助存储器管理系统的第一实施方式中，其中压缩页面与物理帧对齐，所述系统需要跟踪换出的页面被储存的位置；因此，需要扩展用于储存压缩不活动页面的位置的内部数据结构，以支持两个指向可能储存数据的两个部分的起始地址的指针。
另一方面，对于零复制辅助存储器的实施方式，每个元储存条目必须被扩展为包含两对帧号和偏移量，其中一对用于拆分数据所在的空闲碎片的起始地址，因为现在每个条目可以包含活动页面或非活动页面。因此，元储存的每个条目都包含两对，其中要么两对都包含有效值，要么在页面内容未被拆分的情况下两对中仅有一对包含有效值。重要的是要注意，对于零复制来说，页面可能在被拆分后变为活动状态，因此元数据条目需要相应的更新。拆分页面优化方案可以更好地利用可用的空闲碎片空间，从而避免数据转移到存储层次的较低级。但是，一些数据操作可能会比较慢：对于辅助存储器的第一种实施方式，非活动的拆分页面必须在换入操作时合并，从而从不同的存储器位置读取。对于零复制的实施方式，在对拆分页面进行换入操作后，其内容仍将被拆分；如果相比于后者，前者需要同时激活更多的存储行，这可能会导致比非拆分页面的存储器访问时间慢。在替代实施方式中，每当有较大的空闲碎片可用时，可以对拆分页面进行再压紧以减少所述开销(overhead)。
关于辅助存储器的第一实施方式和第二实施方式之间的差异的结论性意见如下。在第一实施方式中，存储器管理设置405被配置为通过将定位页面从非活动部分转移到压缩存储空间的活动部分而使页面调入请求的定位页面可用在压缩存储空间的活动部分中，其中，存储器管理设置405被配置为通过将所请求的页面从压缩存储空间的活动部分转移到非活动部分而使页面调出请求的页面容纳在获得的辅助存储器440的空闲区域中。
另一方面，在第二实施方式中，存储器管理设置405被配置为通过更新元数据以反映定位页面属于压缩存储空间的活动部分而使页面调入请求的定位页面可用在压缩存储空间的活动部分中，其中，存储器管理设置405被配置为通过更新元数据以反映所请求的页面属于压缩存储空间的非活动部分而使页面调出请求所请求的页面容纳在获得的辅助存储器440的空闲区域中。
与本文所述的存储器管理设置405及其不同实施方式相对应的方法，将包括由存储器管理设置405及其不同实施方式执行的功能步骤。
优化方案
除了所描述的实施方式之外，还可以考虑许多优化方案。优化方案的一个方面涉及当辅助存储器没有用于页面调出的空间时为新页面调出的页面腾出空间。优化方案的另一个方面涉及如何更有效地管理空闲碎片。在接下来的段落中，将关注一些这样的优化方案。
当找不到足够大小的空闲碎片时，对于为新页面调出的页面腾出空间，有几种替代方案。一种替代方案是跟踪当前储存在辅助存储器中的页面的“使用年限(age)”。利用使用年限，就可以理解为页面已经在辅助存储器中驻留了多长时间(逻辑或物理挂钟)。使用年限可以基于作为“挂钟(wall clock)”的辅助存储器请求来跟踪，或者在逻辑上通过来自VMM的请求率来跟踪。储存在辅助存储器中的每个页面都以表格形式将“使用年限”关联为计数器。在每次向辅助存储器提出请求时，当前储存在辅助存储器中的所有页面的计数器值都会递增。具有最大计数器值的一个页面将被逐出，并在需要空间时被发送到磁盘。
在压缩存储器中，页面具有变化的大小。只有具有低使用年限和小尺寸(高压缩性)的页面才会被选择以储存在辅助存储器中。相反地，具有高使用年限和大尺寸(低压缩性)的页面可能会被选择以被逐出并发送到磁盘。为此，可以根据使用年限和大小特征建立用于将页面从辅助存储器逐出到磁盘的试探性方法(heuristics)。本领域技术人员可以理解，使用年限可以由最近最少使用(LRU)的概念来建模，并且可以基于具有VMM中使用的基于例如参考比特的近似值的该概念建立试探性方法。
关于如何更有效地管理空闲碎片，目标是尽可能有效地使用空闲碎片。回到图8，并考虑如何使用储存页面1的页面帧，我们注意到它储存了三个页面：页面1和两个换出页面，所述换出页面当前使用与页面帧相关联并由辅助存储器管理的空闲碎片。我们注意到，在示例性方案中，页面帧的利用率可以很低。提高空闲空间利用率的一种方法是偶尔运行压紧程序，其目的是压紧页面帧内的空间。
一种方法是在当前映射到页面帧的页面和驻留在辅助存储器中并利用空闲碎片的页面之间形成尽可能多的空间。这种方法可以通过将所有驻留在辅助存储器中的页面推向页面帧中较高的地址来实现。这将产生在分配页面的中间的最大的空闲碎片以及利用辅助存储器中的空闲碎片的页面。其他的替代方案也是可能的，正如本领域技术人员所认识的那样，并且它们全部在所公开的发明中进行考虑。
在页面调出操作中，建议的选择器430将拦截来自操作系统中的VMM的所有页面调出操作。在外出页面(outgoing page)未被压缩的情况下，选择器可以选择利用压缩器单元212来压缩该页面，潜在地使用硬件加速器来压缩该页面。然后，将从步骤930尝试图9中描述的相同过程，其中选择器将尝试将页面储存在辅助存储器440中的可用空闲空间中，以避免以后高代价的磁盘访问。
地址转换
现在把注意力转向物理地址与压缩存储器中的地址之间所需的地址转换。如前所述，存储页面不一定放在传统非压缩式存储系统中的原始位置，该原始位置需要转换步骤以将它们定位在压缩地址空间(CAs)中。此外，高速缓存系统通常以存储块或高速缓存行(以下，块和行可互换使用)的粒度管理数据，所述存储块或高速缓存行的大小通常为64B，所述高速缓存行在压缩式存储系统中也具有可变的大小，因此存在额外的步骤：将所述高速缓存行定位在压缩存储页面中。图16A示出了包含未压缩的高速缓存行1620的示例性存储页面1610，而图16B示出了其高速缓存行1620被压缩和压紧的同一页面1610。当从常规的物理地址(PA)转换为压缩地址(CA)时，例如由图2的示例性系统中的地址转换单元(211)进行转换时，必须支持所述转换。
现有技术遵循不同的方法以提供PA与CA之间的地址转换。一种方法使用大量的元数据以通过保持每个压缩块的内向指针来确定页面内每个压缩块的确切位置；具有64个高速缓存行(在未压缩时每个高速缓存行为64B)的页面需要大小为64×12b＝768比特(b)的元数据，因为12比特的指针被用来指向页面内的任何字节位置。第二种方法只使用压缩大小，因此它需要的元数据大大减少(每个页面64×6b＝384b)，但在计算压缩位置时要经历高等待时间，因为它需要累加(accumulate)压缩大小；例如，计算第64个块的压缩地址需要累加63个大小。还有一种方法是将高速缓存行限制为一个大小(即，页面中的最大压缩尺寸)；这种方法需要的元数据量可以忽略不计(每个页面2b)，但大大限制了压缩(和空闲空间)的可能性。
其他方法试图通过将存储器划分为固定大小的分段并在元数据中对由压缩数据使用的分段的数量进行编码来减少转换元数据。分段可以是粗粒度的或细粒度的。图17示出了粗粒度分段实施方式，其中存储器被划分为1KB的分段(1720)。在该示例中，未压缩的页面1710是4KB，同一页面压缩后的1730是2321B，并使用3个分段(1722、1724和1726)。在压缩1750时另一个页面1740可能只需要一个分段1728。元数据1760需要对起始分段和每个页面的分段的数量进行编码，因为压缩后的页面被映射到连续的分段。然而，因为页面的实际压缩大小与分段大小不完全一致，所以压缩空间未被充分利用，导致内部碎片化(1774和1778)。图18示出了图17的替代实施方式，其中压缩页面1830被映射到非连续分段1822、1826和1829。这导致更多的元数据字段(1864a-d)，然而，内部碎片化问题(1874和1878)仍然存在。图19示出了细粒度的分段布局，其中存储器1910被划分为8B分段1915。页面元数据1930包括用于每个压缩高速缓存行1925的压缩大小1934(即分段的数量)。例如，CL0具有3个分段1934a的大小(24B)，而在图16B的非分分段转换布局中，CL0具有18字节1635a的大小。因此，虽然分段有助于减少元数据，但它对可压缩性具有负面影响。
即使在芯片上存在缓冲器(类似于转换后备缓冲器)以保持从物理地址到压缩地址转换的转换元数据，这个缓冲器由于面积限制而无法高速缓存所有的元数据。因此，元数据必须被储存在存储器中。大量的元数据会在存储容量中带来大量的开销，而如果所述元数据需要从存储器转移到芯片上的地址转换单元，则由于压缩而带来的带宽增益就会消失。减少元数据开销要么增加等待时间导致性能下降，要么限制压缩率导致存储容量和带宽收益的破坏性影响。此外，所有基于分段的方法都经历内部碎片化，这限制了容量和带宽的增益，因为它们分配了不必要的空间以使压缩数据与分段边界对齐。
地址转换：基于扇区的实施方式
本发明公开了通过引入一种新的数据实体(称为扇区)来解决上述问题的装置和方法。扇区具有固定的“逻辑”大小(称为SectorLogSize)，但根据其压缩比而可变的“物理”大小(称为SectorPhysSize)。逻辑大小使它所包含的高速缓存行(或普通块)的数量量化，而物理大小使它的大小(例如，以字节为单位)量化。扇区包括固定数量的高速缓存行，例如，2、3或10，但逻辑大小通常优选为2的幂：2、4、8、16等。图20示出了未压缩形式的扇区2020，而图21示出了压缩形式的同一扇区2120，其中物理大小以字节为单位进行测量；SectorLogSize是8个高速缓存行，而SectorPhysSize是压缩的CL大小2130的总和，在示例性扇区中是18+44+10+22+60+54+2+8＝218B。
固定的逻辑大小(SectorLogSize)使得任何存储器请求都可以自动转换为扇区请求，而不需要保持额外的元数据。通过使用高速缓存行索引与SectorLogSize相除的结果的整数部分，基于原始存储器请求的地址来自动找到正确的扇区。例如，如果SectorLogSize是8并且存储器请求在高速缓存行5之后进行，则必须被请求的是扇区0
可变物理大小背后的动机是，它减轻了内部碎片化问题，因为可以从存储器访问可变大小的压缩数据。扇区的另一个优点是，它将多个连续的高速缓存行打包在一起。因此，如果运行的系统和/或应用程序表现出空间参考位置性，即使必须重新布置数据以处理动态数据的变化，也能保证由于压缩而导致的带宽改善。例如，如果压缩后的高速缓存行大小增大，将有可能导致扇区大小增大。如果压缩溢出机制要将扇区移动到其他地方，则该扇区内的所有高速缓存行将一起移动。压缩溢出机制处理动态数据变化，详见第[0207-0213]段。
基于扇区的转换的另一个重要益处是，它实质上需要较少的元数据。在基于扇区的转换元数据格式的第一实施方式中，元数据包括识别压缩页面内的扇区位置的指针。图22示出了如何在压缩页面2210内识别压缩扇区2220。存在8个扇区(4KB的未压缩页面包括64个CL，因此8个扇区的SectorLogSize为8)；所需的元数据是8(扇区)×12b；每个指针(PTR2234)标识压缩页面内的扇区位置，即<＝4KB)。每个页面2230的元数据只有96比特。扇区大小是通过从下一个指针减去当前指针来确定的；例如扇区1 2226的大小是从Sec2 PTR2234b-Sec1 PTR 2234a得出的。最后一个扇区的大小是通过从压缩后的页面大小中减去其PTR得出的；如果页面大小没有保持在元数据中，则最后一个扇区的大小就是元数据的一部分。在基于扇区的转换元数据格式的另一个实施方式中，如图23所示，压缩大小元数据(CSM)2318与数据混合保存在扇区的起始端的固定区域中(2323、2326等)。如果扇区内的一个或多个特定压缩块2314必须被解压缩并在访问扇区时首先返回，则所述CSM确定在扇区内的移位量。在又另一个实施方式中，通过将每个CSM放置在每个压缩块之前，可以将CSM分布在扇区上。其他替代的实施方式可以由本领域技术人员实现。在本实施方式中，CSM对应于压缩高速缓存行的元数据，但可以概括为任何压缩块实体。在图24中描述的基于扇区的转换元数据格式的第四实施方式中，元数据包括指针(PTR)2434，该指针标识压缩页面内扇区的位置以及扇区的大小(SIZE)2438。所需的元数据量仅为8(扇区)×12b+8(扇区)×8b＝160b。扇区大小元数据字段的宽度由扇区的最大大小决定，当扇区的SectorLogSize为8时，未压缩的扇区大小为512B。未压缩的扇区在SIZE中被编码为大小为0，然而另一个压缩的扇区大小(例如511)可以被用来编码未压缩的扇区。所述基于扇区的元数据转换格式的优点是，它允许扇区重新排序，以便能够更灵活地处理扇区数据中的动态变化。这是在前述三个实施方式之一的基础上用少量的元数据(约60b)实现的，而在现有技术中，需要大量的元数据，潜在地多达8倍的元数据。其他的替代方案可以由本领域的技术人员实现。
减少转换元数据宽度的好处是，所述元数据在存储器中需要的空间更小，减少了存储器中的整体元数据开销。此外，在芯片上存在转换元数据缓冲器的情况下，较小的元数据宽度的值被转换为芯片空间中较少的面积开销，从而导致潜在的更少的功率和能量。相反地，节省的面积可以用来增大转换元数据表的覆盖区间，也就是页面转换的数量，以提高性能。
图45描述了根据本文的教导的用于访问驻留在物理计算机存储器中的压缩式计算机存储器的一般方法4500。该方法包括将压缩存储块表示为扇区，其中所有扇区包含固定数量的压缩存储块，诸如高速缓存行，所有扇区都具有呈固定数量的压缩存储块形式的固定逻辑尺寸，并且所有扇区都具有呈储存在各压缩存储块中的数据的总尺寸形式的变化的物理尺寸4510。该方法还包括提供基于扇区的转换元数据以跟踪压缩存储页面内的扇区4520，接收包括物理计算机存储器中的地址的物理存储器访问请求4530，使用物理存储器访问请求中的地址得出存储块索引4540，使用存储块索引和扇区的固定逻辑大小来确定扇区id 4550，使用基于扇区的转换元数据来将具有扇区id的扇区定位在压缩存储页面中4560，以及使用物理存储器访问请求的地址来将所请求的数据定位在所述扇区之内4570。
用于访问驻留在物理计算机存储器中的压缩式计算机存储器的相应设备，将包括执行方法4500的功能步骤的装置。
图25中描述了用于访问驻留在物理计算机存储器中的压缩式计算机存储器的方法的第一实施方式，该方法涉及基于扇区的元数据转换，该元数据转换包括作为存储器读取或写入请求的一部分的压缩和解压缩。图27中描述了相关的设备。压缩页面的转换元数据还包括所述页面的起始地址(PageStAddr)，该起始地址在使用基于扇区的元数据计算压缩地址时被用作基准地址。在图5的示例性布局中，因为如前所述的物理帧与压缩地址空间中的帧对齐，因此不需要PageStAddr。在图12的第二示例性布局中，PageStAddr包括PFN和偏移量。在第三示例性布局中，如果扇区元数据可以指向存储器的任意位置而不是压缩页面内，则可以省略PageStAddr。
在该第一实施方式中，每个存储器请求必须被转换为基于扇区的请求。在该方法实施方式中，基于扇区的转换根据请求R的原始大小而将请求R转换为一个或多个扇区请求R'。首先，触发转换元数据检索过程2510，其中检查转换元数据是否可用(2513)。如果没有，则触发对元储存的元数据请求(2516)。当转换可用时，触发基于扇区的计算2520，并且基于PageStAddr和扇区指针来计算R'地址2523。根据请求R的地址及其大小，可能需要请求一个或多个扇区S。R'的大小是扇区大小2526，在图24的示例性扇区元数据格式中，它是可用的(2526a)，而在图23的第二示例性扇区元数据格式中，它是使用扇区指针(2526b)计算的。当请求R'属性准备就绪时，将R'发送到存储器2529。当存储器利用压缩扇区数据进行响应时2530，扇区被解压缩2540。如果请求R是读取请求，则返回所请求的数据(基于R→addr和R→size)2550；否则(R是写入请求)，则遵循基于扇区的压缩过程2560：将旧的扇区数据与新的数据合并(合并是基于R→addr和R→size驱动的)2564，新的扇区S'被再压缩2568，然后写入存储器；当请求是写入请求时，转换元数据(即，扇区SIZE和/或扇区PTR)也相应更新。在一个实施方式中，所述元储存被保存在主存储器中。在第二个实施方式中，它被储存为磁盘中的文件。其他替代方案可以由本领域的技术人员实现。
图26中描述了用于访问驻留在物理计算机存储器中的压缩式计算机存储器的方法的第二实施方式，其中使用图23或图24的示例性元数据格式代替。转换元数据检索2610和基于扇区的CA计算2620与图25的实施方式相似。然而，当存储器以压缩扇区数据2630响应时，可以基于CSM2318/2418来定位对应于所请求的数据(基于R→addr和R→size得出)的一个或多个压缩块，并优先解压缩，而不是解压缩整个扇区2660，从而潜在地降低解压缩等待时间。这仅适用于读取请求；如果请求是写入请求，则与前述实施方式一样遵循基于扇区的压缩2650。图26中的方法与图27B中的设备相关联。
在第二实施方式的替代方案下，使用图23或图24的示例性元数据格式代替。如果请求R是写入请求，则压缩的扇区S数据和新数据(R->数据)可以在解压缩和再压缩整个扇区S的情况下进行合并，但仅通过压缩R->数据并使用CSM元数据来将旧的压缩数据替换为所述新的压缩数据。图27C中描述了根据这种替代方案操作的设备。
在另一替代方案中，如果整个扇区在读取请求时被解压缩，则尚未被请求的其余解压缩数据可以被缓冲，以备将来被请求。如果正在运行的应用程序或程序表现出空间参考位置性，则这种情况经常发生。另一种情况是，如果整个扇区在读取请求时被解压缩，则所有解压缩数据都可以被缓冲，以备将来被请求时使用。如果正在运行的应用程序或程序表现出时间和/或空间参考位置性，则这种情况就会经常发生。在又另一个替代方案中，在写入请求时，整个扇区可以被缓冲(以压缩或解压缩的形式)，以备随后针对这个扇区的其他写入请求。如果正在运行的应用或程序表现出时间和/或空间参考位置性，则这种情况就会发生。
其他替代方案可以由本领域技术人员实现，并且目的是考虑所有这些方案。
图27描述了用于访问驻留在物理计算机存储器中的压缩式计算机存储器的设备2700的第一实施方式。该设备2700与图25中的方法相关联。该设备2700包括基于扇区的转换设备(2710-2730，2760-2770)以及基于扇区的存储器压缩系统中的压缩器2780(CMPR)和解压缩器2750(DCMP)。在图27的底部，还存在以压缩形式储存数据的主存储器2740。在具体的CPU系统实施方式中，诸如在图2的示例性系统中，所描述的压缩系统是在存储器控制器210(该存储器控制器连接到压缩主存储器)和处理器以及高速缓存层次之间。压缩系统从框图的顶部接收存储器请求(2704-2706)。如图2的示例性系统中所描述的，这样的存储器请求可以由C3高速缓存发出。然而其他单元可以产生存储器请求，例如，GPU、显示控制器等。
在图27的系统中，基于扇区的转换设备包括地址转换表(ATT)2710、压缩地址计算器单元(CACalc)2720、扇区REQ单元2730、扇区合并单元2770和选择器(SEL)2760。所有的存储器请求都被图27的压缩系统拦截。与存储器请求是存储器读取请求还是存储器写入请求(R在任一情况下)无关，其物理地址2704被传递给ATT 2710。ATT是基于物理页面(即，物理帧号(PFN))可寻址的，并且高速缓存每个物理页面的转换元数据。这种转换元数据包括PageStAddr 2714和扇区元数据2718。如果元数据格式是图22或23中的一种，则扇区元数据还包括用于每个扇区的指针，或者如果元数据格式是图24中的一种，则扇区元数据包括用于每个扇区的指针和大小。如果ATT 2710已经高速缓存了输入请求R的页面转换，则它为ATT命中，否则它为ATT未命中。在后一种情况下，向存储器(元储存)提出元数据请求2719。从存储器返回元数据2742，并更新ATT。如前所述，ATT基于物理帧号(PFN)进行寻址，该物理帧号的计算方法如下：R→Addr>>12b，假设物理页面是4KB。CA计算单元2720将物理地址转换为压缩地址，具体如下：CA＝PageStAddr+扇区→PTR；将请求R的大小转换为扇区大小请求(即，对于图22和23的元数据格式进行计算，或者对于图24的元数据格式从ATT返回)。扇区REQ单元2730创建新的请求R'，该请求是扇区请求，并与请求R相关联，所述单元2730还保留着原始请求R 2704与转换后的请求R'2735的关联。当压缩扇区数据2745从存储器返回时，它被DCMP 2750解压缩。如果原始请求R 2704是读取请求，则对应于R的解压缩数据被返回2708，而其余的数据被丢弃。这由选择器2760使用R→
图28中描述了用于访问驻留在物理计算机存储器中的压缩式计算机存储器的设备2800的第三实施方式。该设备2800与图25B中的方法有关。在第二实施方式中，增加了动态数据选择控制单元2890。所述单元包括PB(预取缓冲器)2898，其以未压缩的形式缓冲在存储器请求R'时从存储器到达的(解压缩)扇区数据2855、解复用器2894和选择器2892。基于以下事实：运行的应用程序和/或操作系统可以表现出高空间参考位置性，并且由于扇区具有比由处理器和高速缓存所要求的典型高速缓存行粒度更大的逻辑大小，因此，由于请求R要求所述扇区内的特定高速缓存行而被访问的“预取”扇区数据，现在可以被预解压缩(提前预取)并储存在PB中，以期待未来对其的访问。在图28的所述基于扇区的转换设备实施方式中，使用输入的读取请求的地址和大小(R→
在替代方案中，如果对同一扇区存在背对背的读写请求，则写入请求也可以从PB的存在中受益。如果在PB中找到了未被写入请求触及的扇区数据，则在写入请求之前不需要调度读取请求，甚至节省更多的带宽。在另一个替代实施方式中，可以将相同的PB或另一个PB放在扇区合并器的前面以储存扇区。如果存在发往同一扇区的背对背写入请求，则这可能是有益的。
在使用图23或图24的元数据格式的替代方案中，其中CSM可用于在扇区内选择性地解压缩所请求的压缩块，整个扇区或其中的一部分可以储存在置于DCMPR之前的PB中，以便它以压缩形式保持输入的(来自存储器的)扇区数据。该PB的工作原理类似于前述实施方式的PB。然而，除非明确要求对数据进行解压缩，否则不会对数据进行解压缩。如果存在低空间参考位置性或没有空间参考位置性，则这可以潜在地节省带宽和由于解压缩而产生的动态能量。
在另一替代方案中，可以将前面所有实施方式中的每个的转换设备进行流水线化，以便能够同时转换和处理多个存储器请求。
其他实施方式和替代方案可以由本领域的技术人员实现。
上述基于扇区的转换格式解决了由于其可变的物理大小而导致的内部碎片化问题，同时它可以大幅减少所需的元数据量以及改善带宽。然而，为了避免或减轻由于存储器写入所需的扇区读取而造成的存储器带宽的严重开销，特别是如果所述存储器写入没有空间参考位置性，或者如果读取扇区(要与写入请求合并)的再利用距离大于预取缓冲器本身的大小，可以进行进一步的改进。现在将描述这种改进的示例。
地址转换：基于混合扇区的实施方式
纯基于扇区的转换格式的替代方案将扇区元数据与高速缓存行元数据相结合，并在图29中进行描述。这样的转换格式被称为混合元数据。在所述格式中，对于包括压缩扇区2920的压缩页面2910，每个页面2930的元数据包括扇区元数据2931和用于每个扇区2934的高速缓存行元数据2932。扇区元数据2931仅包括扇区指针2931a、2931b等，并且高速缓存行元数据包括高速缓存行大小(CL-SIZE)2932a、2932b等。每个CL-SIZE子字段元数据都对各自CL的高速缓存行大小2940进行编码。例如，CL-SIZE子字段2932a1对扇区0 2923的第一高速缓存行的压缩大小进行编码。在图29的实施方式中，SectorLogSize是8，因此高速缓存行元数据包括8个CL大小。在替代的实施方式中，其中SectorLogSize不同，扇区和高速缓存行元数据将包括更多或更少的子字段。这样的元数据格式可以在访问压缩数据时允许更多的灵活性，因为它现在可以提取或写入一个或多个扇区或一个或多个高速缓存行。此外，如前段所述，它还可以减少扇区读取或写入操作的开销，从而潜在地改善带宽使用情况。在这种混合格式实施方式中，转换元数据的大小已经增大到：(8×12b)+(64×6)＝96b+384b＝480b，即与图24的扇区元数据格式(扇区指针+大小)相比，元数据开销增加了320b。
在替代方案中，高速缓存行元数据可以用其他元数据替换，例如，如果数据的压缩粒度小于高速缓存行粒度，则可以用压缩大小元数据(CSM)替换。
图30中描述了基于扇区的混合转换方法的第一示例，包括转换元数据检索过程3010、基于扇区的混合CA计算过程3020、基于扇区的压缩3070、基于扇区的解压缩3050以及存在于存储器压缩系统中的其它过程。转换元数据检索过程3010与图25和图26的2510/2610相似。当针对输入请求R(2513的箭头“是”)的转换可用时，首先检查它是读取请求还是写入请求。如果是读取请求，则在类似于图25的示例方法计算压缩地址3021和大小3022之后，将请求整个扇区3023。然而，如果是写入请求，则可以立即对请求R的写入数据进行压缩3030；将其大小(CS)与旧的大小进行比较3027，该大小进一步由写入请求所属扇区的CLi→Size元数据确定。如图25/26的2523/2623中那样计算扇区3025；通过移位地址(对于64Bytes的物理高速缓存行)的6个最低有效位来计算CLi(即，所述扇区内CL的索引)3025，并利用SectorLogSize计算其余地址的模数。如果写入请求的大小大于一个高速缓存行，则旧数据的大小由这次写入请求中所涉及的CL的总和(CL→Size)确定。将CS与旧的CL大小进行比较，可以得到三种可能的结果：如果CS>旧数据(3027的结果为“是”)，则需要读取整个扇区(步骤3021-3023、3040)，解压缩3050，与新数据合并3073，压缩(3076)并写入存储器(3079)。如果CS＝旧数据(3027的结果为“否”)，则压缩数据在计算出其准确的压缩地址和大小之后，可以通过步骤3029立即写入存储器3080，而不需要读取扇区。
最后，如果CS<旧数据，写入新的压缩数据并更新元数据中的CL→Size会导致转换元数据错误。因此，存在不同的方法来处理这个问题。在一个实施方式中，可以立即将压缩数据写入存储器(步骤3029和3080的路径)，但首先用与差值(旧数据-CS)一样多的“无关”比特来填充压缩数据，这种方式会产生无法跟踪的内部碎片化。在另一个替代方案中，内部碎片化可以通过每扇区每CL增加一个比特(对于页面元数据，总计为64b)来跟踪，该比特在产生内部碎片化时被设置。在另一个实施方式中，在最常见的情况下，当未压缩的高速缓存行逐渐变成压缩形式时，可以“借用”可能的CL→Size值中的一个来对内部碎片进行编码，这样就可以在扇区内的高速缓存行准备被压紧形成压缩扇区时检测到内部碎片化。在另一种替代方案中，可以将这种情况处理成CS>旧数据的情况(3027的结果为“是”)，尽管会产生外部碎片化(即，碎片不再是扇区的一部分)。不过，外部碎片化可以通过再压紧扇区(定期或按需)来消除，而不需要额外的元数据。如本领域技术人员所意识到的，外部碎片化所占用的空间可以使用扇区指针元数据和CL-size元数据来检索。
在确定必须应用哪种写入方案后，需要相应地更新转换元数据(即，扇区SIZE和/或扇区PTR和/或CL大小)。
在替代方案中，当需要读取整个扇区时，可能不需要如先前所描述的那样对新扇区数据与旧扇区数据进行合并来解压缩该扇区。
如果写入请求的大小与存在可用转换元数据的高速缓存行不一致，则整个扇区被读取、解压缩、与新数据合并以及写回，或者涉及高速缓存行。本领域技术人员可以实现其他替代实施方式，其复杂性可以更高或更低，这取决于这种请求情况发生的频率。这样的其他实施方式也是可以考虑的。
在图31A至图31D(其中图3B至图3D是图31A的详细视图)的基于扇区的混合转换方法的第二示例中，压缩扇区或压缩高速缓存行的选择性提取也可以应用于读取请求，相应地改善读取带宽和等待时间。当存在空间参考位置性时，或者当压缩比(CR)较高时(即，CR>＝SectorLogSize)，读取整个扇区都是有利的，否则可以优先读取与原始请求R一样多的大小。因此，该第二实施方式需要对方法进行一些修改：1)增加动态数据选择控制流程3190，该动态数据选择控制流程包括类似于图28中的PB单元2890的功能的预取缓冲器功能3193、判定机构3196和选择器3199；2)通过增加计算CA和比扇区小的压缩大小R'的流程步骤3124，修改基于扇区的混合CA计算流程3020。在一个实施方式中，空间参考位置性可以通过测量预取缓冲区的利用率来确定，而CR已经从转换元数据中得知。通过测量例如储存在缓冲器中的扇区数据的命中率来跟踪预取缓冲器的利用率。在替代性方案中，可以选择仅读取压缩的高速缓存行，但用影子扇区数据标记预取缓冲器，以模拟预取缓冲器的利用率。
在基于扇区的混合转换方法3100的第二示例中，判定过程步骤3196的判定标准因此可以由以下公式确定：
其中512是扇区的未压缩物理大小，单位为字节(8×64B，如果SectorLogSize为8)，1+7×U：在非压缩系统中访问1个高速缓存行，而7×U是由扇区读取提取的额外高速缓存行数，并且U是预取缓冲器利用率(即，实际访问了其中的多少)，
64：高速缓存行的未压缩物理大小，单位为字节。
如果求解公式使CR成为判定的变量，则必须满足以下条件：
在另一种替代方案中，可以修改公式以补偿由于元数据而产生的额外流量，例如如下所示：
本领域技术人员可以在不同的参数下，例如在另一个SectorLogSize值下求解该公式。此外，本公开的判定标准并不局限于具体的公式，但本领域技术人员可以意识到其他类似的公式，以结合可压缩性和扇区预取利用率的影响，或其他标准；例如，仅使用可压缩性，或PB利用率，或监控并预测访问模式，以判断提取扇区还是单个高速缓存行是更可取的。
图32描述了用于访问驻留在物理计算机存储器中的压缩式计算机存储器的设备3200的第四实施方式。该设备3200包括基于扇区的混合转换设备(3210-3230、3270和3290)以及基于混合扇区的存储器压缩系统中的压缩器3280(CMPR)和解压缩器3250(DCMP)。图32还包括压缩存储器3240。所有的存储器请求都被图32的设备3200拦截。基于扇区的混合转换设备包括基于扇区的转换和地址计算单元(3210-3230)、动态数据选择控制3290、基于扇区的混合写入单元3270。ATT 3210包括对于每个页面的PageStAddr 3214，以及基于扇区的混合元数据PTR 3216和扇区CL-SIZE 3218。ATT的访问和更新类似于图27和图28的实施方式2710/2810。
使用输入的读取请求R(在本实施方式中，针对写入请求不检查PB)的地址和大小(R→
如果原始请求R是写入请求，则(R的)数据3206首先被CMPR 3280压缩。压缩数据的压缩大小(CS)被发送到基于扇区的混合写入单元3270的CL ovf(溢出)单元3278。CL ovf3278实现类似于图31A至图31D的前述实施方式中描述的3125、3127、3129中的那些功能。如果不存在CL溢出，则可以立即将压缩数据写入存储器；否则，类似于图27和图28的实施方式，必须由单元3210-3230创建出压缩扇区请求，然后所述压缩扇区必须由3250解压缩，在3274中与新数据合并，在3280中再次压缩，以及然后最终写入压缩存储器3240。如果原始写入请求的大小与一个或多个扇区一致，则可以省略扇区读取步骤。
在所述基于混合扇区的设备3200中，动态数据选择控制3290的判定单元3299对请求R是否应该转换为扇区请求，或子扇区请求(即多个连续的高速缓存行)，或CL请求进行预测。所述预测判定可以基于一个或多个标准进行。在一个实施方式中，一个标准是监控到的可压缩性；在替代实施方式中，标准可以是PB利用率；在又一个实施方式中，可以使用第[0165]段中描述的公式(1)、(2)或(3)做出判定。在一个示例中，可以通过跟踪CMPR 3280中的压缩数据大小来监控可压缩性；在替代实施方式中，可以使用来自ATT 3210的压缩扇区或CL大小来计算特定页面的可压缩性。可以通过测量PB 3298的命中率来量化PB的利用率。然而，当仅优选读取CL时，PB可能没有足够的数据，因为它们的数据通常不会储存在PB中。因此，当解压缩数据3255不对应于某个扇区而是对应于一个或多个CL时，可以使用伪有效元数据比特在PB中标记所述CL所属的扇区，该元数据位限定其数据实际上不在PB中，但如果访问该扇区，则可能已经在PB中。在这种情况下，当查找PB并且设置伪有效位时，则它是伪命中(而不是命中)，并且可以在测量PB利用率时类似于命中使用。量化PB利用率或可压缩性监控的其他实施方式可以由本领域的技术人员实现，并且也可以预期到这样的实施方式。
在替代的基于扇区的转换格式中，将扇区元数据与高速缓存行元数据相结合，然而如图33A所示，每个扇区内的高速缓存行被限制为特定的压缩大小；所述格式被称为基于扇区的混合受限转换格式，因为它限制了额外元数据的数量。例如，CL-size元数据每扇区只有6比特，而不是SectorLogSize×元数据_宽度；而在混合元数据格式中，其中CL-size元数据开销是每扇区8×6＝48比特，每个页面总共384比特，而在该示例的元数据格式中，它是每扇区6比特，总共只有48比特。在这种替代的基于扇区的转换中，每个页面3330的元数据总量为96+48＝144比特。然而，这种元数据格式会大大降低可压缩性，因为扇区内的所有高速缓存行必须具有最大的压缩高速缓存行3314的大小。例如，现在扇区0 3323的压缩大小为480字节，而在基于扇区的混合体中，扇区0的2223/2323大小反而是218字节。这样的元数据格式可能对较小的SectorLogSize的扇区更有利。在图33B的替代方案中，SectorLogSize被设置为4，因此存在16个扇区。对应于图33A的实施方式的扇区0 3323的压缩扇区0 3423和压缩扇区13426的大小现在是416字节(而不是图33A中的480字节)。然而，扇区转换元数据现在是图33A的替代方案中的2倍。如果选择这种格式，本领域技术人员可以识别哪种元数据开销与压缩效率是最好的。
支持这种基于扇区的混合受限转换格式的方法和设备分别与前述基于扇区的混合转换方法(图30和图31)和设备(图32)相似，除了以下功能之外：1)特定高速缓存行的压缩地址的计算按如下方式：R'→Addr＝PageStAddr+S→PTR+#pCLs×S→CL-Size，其中#pCLs为存在于请求的本扇区内的高速缓存行之前的高速缓存行的数量；2)当扇区被写入存储器时，必须确定扇区内压缩高速缓存行之中的最大压缩大小；3)如果压缩高速缓存行的大小大于CL-size，则必须对该扇区内的所有高速缓存行进行读取、解压缩、合并和再压缩(相当于对扇区进行读取、解压缩、合并和压缩)；4)如果压缩高速缓存行的大小增加并且必须以未压缩的方式储存，则必须对整个扇区进行解压缩。
在图34中描述的基于扇区的转换格式的另一个替代方案中，每个扇区内的压缩数据的顺序除了可以进行压缩以外，还可以改变空间参考位置性，从而更好地改善存储器带宽。这在存在PB 2898(图28)和3298(图32)的情况下将特别有利，因为这可以提高PB的利用率。所述转换格式被称为压缩数据重新排序的基于扇区的转换格式。在图34的示例性格式中，扇区0 3423收集高速缓存行(CL)0、2、4、6、8、10、12、14；扇区1 3426收集CL1、3、5、7、9、11、13、15；扇区2 3429收集CL16、18、20、22、24、26、28、30；等等。如果存储器请求的步幅为2，则所述示例性格式组织扇区压缩数据。扇区数据的组织被编码在额外的字段扇区编码3432中，以便地址转换方法和设备能够将存储器请求与特定扇区相关联。与先前公开的实施方式相比，这需要的额外元数据量可以忽略不计。元数据按页面保存，从而允许对不同的页面进行不同的重新排序类型。在替代方案中，如果对整个基于扇区的压缩存储器应用一种重新排序类型，则可以省略所述元数据。
在压缩数据基于扇区转换进行重新排序的示例中，当页面被压缩时，在扇区中组织的数据的重新排序就会发生。存在一组预配置的重新排序模式，例如，所访问数据大小的2、3、4的步幅(例如，通常是高速缓存行)。重新排序的确切类型是由预测过程判定的，该预测过程在数据压缩之前监控页面内数据的访问流量，并尝试将其与预配置的重新排序模式之一进行匹配。当页面第一次被压缩时，选择最佳匹配的一种。在替代实施方式中，可以通过再压缩页面来调整重新排序的类型，特别是当预测器发现之前的预测不准确的情况下。
如果针对常规访问模式监控存储器流量，则在所监控的访问模式是基于步幅的示例性实施方式中，步幅度值集的边界可以由每个页面所监控的访问模式的数据块的总数除以SectorLogSize(以所述数据块的数量测量)来限制。例如，如果以高速缓存行粒度监控访问模式，则对于包括64个高速缓存行的4KB页面，并且对于4个高速缓存行的SectorLogSize，步幅度属于值集[0,16]；对于步幅度16，扇区0将包括高速缓存行(CL)0、16、32、48；扇区1将包括CL1、17、33、49；等等。如果针对非常规访问模式监控存储器流量，则在示例性实施方式中，监控机制可以包括计数器的2D数组(2D array)，其中每个维度宽度由页面(例如高速缓存行)中监控的数据块的数量确定。该2D数组跟踪页面内连续的块访问之间的可能相关性。即使中间发生在不同页面中的访问，本领域技术人员也可以实施能够监控页面内的连续块访问的实施方式2D数组的一个维度用于指在先的数据块访问，而另一个维度用于指当前的数据块访问，因此基于在先的访问和当前的访问的组合，关联的计数器将递增。例如，位于(10，40)的计数器表示页面内块10和40之间发生连续访问发生的次数。所述计数器组定期或按需评估，以判定计数器的数组是否可以导出正式的基于相关性的模式，该模式将用于对扇区内的数据块进行分组。所述分组仍然可以用扇区编码元数据字段进行编码，但它需要生成哈希函数，以便能够确定针对输入的存储器请求地址的正确扇区。
如果孤立地监控每个页面的访问模式，则这可能需要大量的资源来维持所有的访问模式。在又一个实施方式中，可以使用一个以上页面的访问模式来确定特定页面的重新排序类型。这样的预测可能不太准确，但是预测器需要较少的资源来做出判定。监控流量可以是仅读取流量、仅写入流量和/或兼具两者。
在基于扇区转换重新排序的压缩数据的替代方案中，当页面中的数据第一次被压缩时，对组织在扇区中的数据进行重新排序。在这种情况下，整个页面需要从存储器中读取，压缩并写回到存储器。在每个扇区内重新排序的数据是高速缓存行，然而，在其他替代实施方式中，可以考虑对其他大小的数据块进行重新排序。
在先的基于扇区的地址转换方法(和设备)如果通过预测方法(设备)增强，则可以支持基于扇区的转换格式重新排序的压缩数据，该预测方法(设备)监控图25、图26、图30和图31(图27、图28和图32)的输入的存储器请求(R)，以及页面第一次被压缩(元数据确定页面是否被压缩)通过相应地更新元数据3434a、b、c等和扇区编码3432，对页面的数据进行读取、重新排序、压缩并储存在存储器中。在替代实施方式中，该页面不需要已经被压缩，但是如果当前扇区编码类型与预测的扇区编码类型不匹配，则可以被再压缩。
在基于扇区转换格式的重新排序、方法和设备的替代实施方式中，除了实现更好的空间定位外，可以基于其他标准对扇区内的压缩数据进行重新排序。在另一个替代实施方式中，扇区内的压缩数据可以基于其压缩大小来重新排序，以有利于与潜在的现有固定大小的存储块大小更好地对齐。在数据压缩用于最小化来自/去往存储器的流量的情况下，这样的实施方式将是优选的。例如，如果扇区内的压缩块的大小为40B、50B、20B和10B，则存储器访问块大小为64B，并且目标是使最坏情况下的流量最小化(即，压缩数据的流量应小于或等于访问的每个数据块的未压缩数据，因此提取隔离的压缩数据块-当访问模式不利于提取扇区时-与未压缩的存储器相比，不应导致提取更多的存储块)，然后按照原始顺序对压缩数据进行排序，结果是50B的压缩数据块跨越了两个存储器访问块；为解决这个问题而不对扇区内的块进行重新排序，将需要在推动40B大小的块之后引入一个碎片，以使50B的块适合于大小等于存储器访问块大小的块，然而，这将导致需要进一步推动20B和10B大小的块，这需要额外的空间并降低了可压缩性；相反，通过对压缩块进行如下的重新排序40B、20B、50B、10B，可以保持同样的可压缩性水平，同时也实现了对齐。基于压缩块大小对扇区内的数据进行重新排序，每个扇区需要少量的元数据，这些元数据限定了压缩数据块的排序，即，SectorLogSize×(log
上述参照图20至图34描述的各种实施方式和替代方案可以总结如下。用于访问驻留在物理计算机存储器中的压缩式计算机存储器2740、2840、3240的设备2700、2800、3200、2700'、2700"包括地址转换单元2710、2810、3210，压缩地址计算器单元2720、2820、3220，扇区请求单元2730、2830、3230，选择器单元2760、2890、3290，扇区合并单元2770、2870、3270，解压缩器2750、2850、3250和压缩器2780、2880、3280。
地址转换单元2710、2810、3210、压缩地址计算器单元2720、2820、3220和扇区请求单元2730、2830、3230被组合配置为：将物理存储器访问请求R转换为基于扇区的压缩存储器请求R'，其中，使用所述物理存储器访问请求R的地址2704、2804、3204自动提取扇区id，所述扇区id被用于由基于扇区的转换元数据2742、2842、3242确定压缩式计算机存储器2740、2840、3240中的扇区的位置，计算所确定的扇区的压缩地址CA和大小Size，以及基于压缩地址CA和大小Size，向压缩式计算机存储器2740、2840、3240提出扇区请求R'2735、2835、3235。
解压缩器2750、2850、3250和选择器单元2760、2890、3290被组合配置为：对响应于扇区请求R'而从压缩式计算机存储器2740、2840、3240中检索到的压缩扇区数据2745、2845、3245进行操作，以使用所述物理存储器访问请求R的地址和大小2705、2805、3205，从所述压缩扇区数据2745、2845、3245中获得读取请求响应数据，并且将获得的读取请求响应数据以解压缩形式2708、2808、3208返回给在是读取请求时的所述物理存储器访问请求R的源。
扇区合并单元2770、2870、3270和压缩器2780、2880、3280被组合配置为：将所述压缩扇区数据2745、2845、3245-响应于扇区请求R'而从压缩式计算机存储器2740、2840、3240中检索到的数据-与所述物理存储器访问请求R中的数据2706进行合并，以使用在是写入请求时的所述物理存储器访问请求R的地址和大小2705、2805、3205来获得基于扇区的写入请求数据，并将获得的基于扇区的写入请求数据作为压缩扇区数据2785、2885、3285储存在压缩式计算机存储器2740、2840、3240中。
根据图27的用于访问驻留在物理计算机存储器中的压缩式计算机存储器的设备2700的第一实施方式(及其在图25中的相关方法)、根据图27B的设备2700'的第二实施方式(及其在图26中的相关方法)、根据图27C的替代设备2700"、根据图28的设备2800的第三实施方式(及其在图25B中的相关方法)以及根据图32的设备3200的第四实施方式都是上述设备2700、2800、3200、2700'、2700"的实施方式。
相应的方法可以看作是包括由上述设备2700、2800、3200、2700'、2700"执行的功能步骤。
对于上述设备2700、2800、3200、2700'、2700"，所述压缩式计算机存储器2740、2840、3240中的压缩存储块被表示为扇区，其中所有扇区都包含固定数量的压缩存储块，诸如高速缓存行，所有扇区都具有呈固定数量的压缩存储块形式的固定逻辑尺寸，并且所有扇区都具有呈储存在各压缩存储块中的数据的总尺寸形式的变化的物理尺寸。
特别是对于设备2700、2800、3200的第一实施方式、第二实施方式和第三实施方式，解压缩器2750、2850、3250被配置为对响应于扇区请求R'而从压缩式计算机存储器2740、2840、3240中检索到的压缩扇区数据2745、2845、3245进行解压缩，并将解压缩的扇区数据2755、2855、3255提供给选择器单元2760、2890、3290和扇区合并单元2770、2870、3270。选择器单元2760、2890、3290被配置为使用所述物理存储器访问请求R的地址和大小2705、2805、3205从解压缩的扇区数据2755、2855、3255中获得数据，并且响应于所述读取请求而将获得的数据返回2708、2808给所述物理存储器访问请求R的源。扇区合并单元2770、2870、3240被配置为使用所述物理存储器访问请求R的地址和大小2705、2805、3205从解压缩的扇区数据2755、2855、3255中获得数据，将获得的数据与所述物理存储器访问请求R中的数据2706合并为新的未压缩扇区数据2775、2875、3275，并且将新的未压缩扇区数据2775、2875、3275提供给压缩器2780、2880、3280。压缩器2780、2880、3280被配置为响应于所述写入请求而压缩新的未压缩扇区数据2775、2875、3275并将其作为所述压缩扇区数据2785、2885、3285储存在压缩式计算机存储器2740、2840、3240中。相应的方法可以被视为还包括第一实施方式、第二实施方式和第三实施方式的设备2700、2800、3200的功能步骤。
特别是对于设备2800、3200的第二实施方式和第三实施方式，选择器单元2890、3290可以包括预取缓冲器2898、3298，其被配置为对来源于作为第一读取请求的所述物理存储器访问请求R的解压缩扇区数据2755、2855、3255的全部或部分进行缓冲。选择器单元2890、3290被配置为，对于作为第二读取请求的随后的物理存储器访问请求，使用所述第二读取请求的地址和大小来检查所请求的数据是否存在于预取缓冲器2898、3298中，并且如果是，则从预取缓冲器2898、3298中检索所请求的数据，并将其返回到所述第二读取请求的源，或者否则，则针对第二读取请求检索并返回所请求的数据，如前述的针对作为读取请求的物理存储器访问请求所限定的。预取缓冲区2898、3298可以有利地被配置为对解压缩的扇区数据2755、2855、3255中的尚未返回到所述第一读取请求的源的部分进行缓冲。相应的方法可以被视为还包括设备2800、3200的第二实施方式和第三实施方式的功能步骤。
所述压缩式计算机存储器3240中的压缩存储页面可以包括多个扇区，每个扇区包含所述固定数量的压缩存储块，诸如高速缓存行，特别是对于设备3200的第三实施方式，对于每个压缩存储页面，基于扇区的转换元数据3242、2930包括：a)扇区元数据2931a、2931b、PTR，其包括指向压缩存储页面的扇区2934a、2934b的指针，以及b)存储块元数据2932a、2932b、CL-SIZE，其包括每个扇区的存储块的大小2932a1、2932a2。该设备3200被配置为将物理存储器访问请求R选择性地转换为以下任一项i)，对于压缩式计算机存储器3240中的至少一个扇区的基于扇区的请求，或ii)对于压缩式计算机存储器3240中的一个存储块或多个连续的存储块的基于块的请求。
特别是对于设备3200的第三实施方式，选择器单元3290可以包括判定功能3299，该判定功能被配置为做出如下判定：使压缩地址计算器单元3220和扇区请求单元3230选择性地向压缩式计算机存储器3240提出基于扇区的读取请求或基于块的读取请求。判定功能3299可操作地基于以下任何一项作出所述判定：监控到的压缩器3280的可压缩性、监控到的存储器访问模式、如前所述的预取缓冲区的利用率、所请求得扇区相对于其未压缩的物理大小的压缩比的评估、以及所请求的扇区相对于其未压缩的物理大小的压缩比的评估和每次请求的平均元数据。另外，选择器合并单元3270可以被配置为根据物理存储器访问请求R的大小，选择性地将物理存储器访问请求R转换为对压缩式计算机存储器3240的基于扇区的写入请求或基于块的写入请求。相应的方法可以被视为还包括上述设备3200的第三实施方式的功能步骤。
可以回顾的是，所述压缩式计算机存储器2740中的压缩存储页面包括多个扇区，每个扇区包含所述固定数量的压缩存储块，诸如高速缓存行。特别是对于设备2700'的第二实施方式，每个扇区2423包括压缩块元数据2418、CSM，其指示该扇区2423的压缩存储块2414的各自大小。选择器单元2760被配置为通过使用压缩扇区数据2745中的压缩块元数据2418、CSM来从压缩式计算机存储器2740中检索到的压缩扇区数据2745中获得读取请求响应数据，以提取一个或更多个压缩存储块，并用于将所提取的一个或多个压缩存储块2761提供给解压缩器2750。解压缩器2750被配置为对所提取的一个或更多个压缩存储块2761进行解压缩，并且响应于所述读取请求而将解压缩的一个或更多个存储块2753返回2708到所述物理存储器访问请求R的源。
进一步地，对于设备2700'的第二实施方式，选择器单元2760还可以被配置为将从压缩式计算机存储器2740中检索到的压缩扇区数据2745提供2762给解压缩器2750。解压缩器2750被配置为对由选择器单元2760提供的压缩扇区数据2762进行解压缩，并将解压缩的扇区数据2755提供给扇区合并单元2770。扇区合并单元2770被配置为使用所述物理存储器访问请求R的地址和大小2705从解压缩的扇区数据2755中获得数据，将获得的数据与所述物理存储器访问请求R中的数据合并为新的未压缩扇区数据2775，并且将新的未压缩扇区数据2775提供给压缩器2780。压缩器2780被配置为响应于所述写入请求而压缩新的未压缩扇区数据2775并将其作为所述压缩扇区数据2785储存在压缩式计算机存储器2740中。
替代地，对于第二实施方式的替代方案2700"，压缩器2780和扇区合并单元2770可以被配置为将所述物理存储器访问请求R中的数据2706压缩成压缩块数据2785，接收从压缩式计算机存储器2740中检索到的压缩扇区数据2745，使用所述物理存储器访问请求R的地址和大小2705以及压缩扇区数据2745中的压缩块元数据2418、CSM以将压缩块数据2785与压缩扇区数据2745合并；并响应于所述写入请求而将合并后的压缩扇区数据2745储存在压缩式计算机存储器2740、2840中。
相应的方法可以被视为还包括如上所述的设备2700'或其替代方案2700"的第二实施方式的功能步骤。
地址转换：可变分段的实施方式
通过在压缩扇区和/或压缩高速缓存行(对于基于扇区的混合转换实施方式)中应用分段，可以进一步使元数据开销最小化(甚至更多地减少存储器带宽和开销)。图35示出了包括压缩高速缓存行3514的压缩页面3510，其CL-SIZE以字节为单位测量。图36示出了所述页面的替代方案，其中CL-SIZE以分段的数量测量。分段将存储器划分为固定大小的分段3634，例如8字节，因此压缩扇区(或高速缓存行)被限制为一组预限定的大小，而不是如由CL-SIZE元数据3624a进行编码，该元数据由满足某个压缩大小所需的分段的数量确定。未与分段边界对齐的压缩大小需要四舍五入(round up)到最接近的分段边界。例如，CL0为27B，但在图36的分段元数据转换中需要四舍五入到32B。这样一来，可能的大小空间就缩小了，结果需要更少的比特来表示压缩大小；但是，这样会造成内部碎片化和更差的可压缩性，因为分段越宽，造成的内部碎片化就越大，即，由于压缩数据大小和分段边界之间的未对齐，导致未充分利用更多空间。
图37中描述了替代的元数据转换格式，其中压缩数据是分段的，但分段的长度是可变的，基于这样的观察，某些压缩大小比其他大小更频繁出现，因此特定数量的分段比其他大小更重要。在一个示例中，频率大小分布3740分段边界26-38可以比其他部分更频繁地出现。因此，可变长度分段是基于压缩数据大小分布的。“热”数量的分段(经常发生的压缩大小)是窄的，而“冷”数量的段(较少发生的压缩大小)是宽的；例如，分段0-25B 3734a是冷的，而分段31-32B 3734b是热的。因此，先前实施方式中的CL-SIZE元数据需要用CL-meta代替，所述CL-meta对可变长度分段边界进行编码而不是大小。可变长度分段可以由本领域技术人员应用于高速缓存行、扇区或其他压缩数据实体。
在上述任何一种基于扇区的转换元数据格式(纯扇区、混合扇区、受限混合扇区等)中使用可变长度分段，都会触发以下问题限定：
对于压缩数据，最小和最大可能大小分别为S
overhead(开销)＝Sum(freq(s)*(bound(s)-s))，其中bound(s)＝B
其中
ceil(s)＝{B
解决先前问题的一个示例方法是图38的试探性步骤3800，其工作原理如下：
在图38中，从单个分段[S
可变分段可以集成在具有类似于图27、图28和图32中的转换设备实施方式的存储器压缩系统中，通过还添加额外的单元，该单元是收集压缩大小分布的机制。这是通过分析压缩数据来实现的。在一个实现统计压缩的实施方式中，当压缩设备收集用于压缩编码的数据值统计信息时，所述收集压缩大小分布可以在采样期间完成。在替代实施方式中，可以通过收集来自实际压缩数据的信息来建立分布。必须支持两组分段边界。在初始化期间，可以将边界初始化为代表固定大小的分段。然后，在运行时，建立压缩大小的分布，并且可变大小的分段可以被限定为第二组分段。每个压缩实体都需要被映射到它所对应的分段边界。这可以在不同的粒度(高速缓存行、扇区、页面)中完成，该粒度具有可变元数据开销。例如，如果允许每个压缩实体被映射到不同的分段边界，元数据需要为每个压缩实体增加1比特。替代地，如果同一页面的压缩实体被强制映射到相同的分段边界，则每个页面只需增加一个比特即可。从一种分段方案到另一种分段方案的迁移必须应用于共享同一分段集(segmentation set)的所有压缩实体。例如，如果一个页面中的所有压缩实体都被映射到同一个分段集，则它们都必须同时迁移到新的分段集。在一个替代方案中，迁移可以按需进行，即当新的分段集被创建后，每个到达的写入请求都会触发使用新分段集的再压缩。在几个压缩实体共享同一个分段方案的情况下，当其中一个实体的写入请求到达时，所有的实体都必须被再压缩。当一组分段边界将要更新时，映射到该组的每个压缩实体都需要使用第二分段集(不受影响的那个)进行再压缩。
上述参照图35至图38描述的实施方式和替代方案可以概括为一种用于导出特定大小的压缩元数据的方法，该压缩元数据使用于数据的压缩块的目标效果最大化。该方法包括分析压缩块的大小，导出所述压缩块的频率和大小分布，识别一个或多个候选压缩块大小(压缩块将被四舍五入为该大小)，评估所述识别的大小是否在用所述特定大小的元数据表示的同时使目标效果最大化，如果是，则相应地生成压缩元数据格式，或者，否则，从导出步骤开始重复该方法。所述特定大小通常可以是给定的，或者是目标效果的一部分，以使元数据的开销最小化，同时使压缩比最大化。数据块通常是以下任何一种：存储块、网络块、高速缓存行、存储页面或扇区。
用于导出特定大小的压缩元数据的相应设备，该压缩元数据使数据的压缩块的目标效果最大化，该设备将包括用于执行上述方法所述功能步骤的装置。
地址转换：数据动态变化-扇区溢出处理
所公开的基于扇区的转换格式、方法和设备展示了一种有效的解决方案，以减少高转换元数据开销、消除内部碎片化和增大带宽增益，这些问题是先前的转换方案所面临的。除此以外，由于动态数据变化而导致的压缩数据溢出由现有技术通过以下方式之一处理：以细粒度引入外部碎片化，该外部碎片化需要后续(或定期地)大量工作通过再压紧来(重新)创建连续空间；仅限于再压紧高速缓存行。前者是可以通过保留元数据来实现的，这些元数据确定了压缩高速缓存行的确切位置和它们的大小，从而导致每个页面超过1000比特(即，64×12+64×6＝1152比特，与第[0133]段中描述的768比特相比)的元数据开销；此外，由于不可避免地破坏了空间参考位置性而导致碎片化，从而降低了带宽收益。另一方面，在后一种情况下，再压紧往往会增加大量的等待时间；这也会影响空闲存储器量，并对空闲存储器管理产生不利影响。
在图39A的示例性的页面帧中，压缩页面3920的压缩扇区3924a、3924b等在页面帧3910的原始位置上对齐，这些位置确定如下：扇区i×SectorLogSize×64B；例如，扇区1被放置在压缩页面的第512字节中。当压缩扇区可以帮助改善存储器带宽需求，但增大存储容量不是要关注的时，这样的放置是有益的。因此，压缩后释放的空间是未使用的(3928a、3928b等)。此外，每个页面的转换元数据2430需要包含扇区SIZE，由于最大扇区物理大小(SectorPhysSize)为512B(当扇区未压缩时)，所以在本实施方式中该扇区SIZE为8b；因此，每个页面转换元数据的总大小为64b。在所述实施方式中，如果扇区的压缩数据由于动态数据变化而扩展了大小，则压缩扇区将扩展大小，从未使用的空间中获得空间；例如，图39b的实施方式中扇区1的大小为175B，从未使用的空间3928b中获得更多空间，并且所述变化反映在元数据中。如果压缩扇区的扩展超过了可用的未使用空间，则将被强制解压缩并以未压缩的形式储存。这种由于动态数据变化而导致的压缩扇区扩展，由前文详述的所公开的基于扇区的转换设备和方法实施方式处理，而不需要额外的功能。
图40A示出了替代的页面帧布局，其中如由转换元数据4050的扇区PTR 4054所示，压缩扇区被一个接一个地放置；所述压缩扇区数据的放置有利于改善存储器带宽需求，同时也提高了有效存储容量。在所述示例性的页面帧实施方式中，活动页面4020包括压缩扇区4024a、4024b等。由于页面帧的数据压缩而释放的区域4014通过放置两个牺牲页面V14038和V2 4034而被示例性辅助存储器利用，同时存在空闲碎片(ff)4039。也如区间元数据4056所示，释放区域还包括与活动压缩页面4020相关联的区间4040。所述元数据4056包括像图12的实施方式那样的区间起始端(Rb)4056a和结束端(Re)4056b边界，并且还包括区间使用(u)比特4056c；所述u比特4056c可以用于指示区间是否被使用。例如，如果扇区1(S1)4024b由于扇区1的压缩数据的动态数据变化而扩展了大小，并且具有175字节的新大小，则S1不能适应同一位置。如图40b所示，而是利用区间来写入扩展的扇区1。这就导致改变Sec1 PTR 4054a(图40B)以指向新的位置，更新SIZE 4058a，相应地更新区间边界，本例中Rb4056a指向位置3475(175字节向右)，并将u比特4056c设置为‘1’。S1的旧位置现在成为碎片4060。在该示例性实施方式中，碎片位置由于未被记录因而不能直接利用，然而可以使用扇区PTR和SIZE元数据动态跟踪碎片的位置。在替代实施方式中，可以将创建的碎片记录在元数据中，然而这将增加转换元数据的开销。在替代实施方式中，如果存在可以跟踪区间被使用的机制，则可以省略u比特。
在一个实施方式中，与压缩页面相关联的区间可以是与压缩页面连续的。在替代实施方式中，与压缩页面相关联的区间可以与压缩页面不连续，但仍在同一页面帧内。在又另一个实施方式中，与压缩页面相关联的区间可以与压缩页面不连续，并且在不同的页面帧中，然而所述实施方式需要更多的元数据，即除了区间边界之外，还需要将区间定位在其中的页面帧。
所述压缩扇区溢出处理方法与现有技术相比有两个优点：1)扇区的所有压缩数据仍然被打包在一起，因此如果空间参考位置性表现出来，则仍然可以通过获得整个扇区来改善带宽。2)所创建的碎片化是外部的，因此是可跟踪的；更重要的是它的粒度较粗，因此可以更好地利用。在另一个示例性的页面帧实施方式中，一个或多个碎片4060可以用于填充其他扩展的扇区。
图41A至图41C中描述了一种扇区溢出处理方法的示例性实施方式，其中图41B至图41C是图41A部分的详细说明。所述方法除其他步骤外，还包括碎片利用过程4120、区间利用过程4130、再压紧过程4140和下溢处理过程4180。所述扇区溢出处理方法是输入新的压缩扇区版本的大小(S')和同一扇区的旧版本的大小(S)。首先检查S'是否大于S 4110。如果不是，则触发下溢处理过程，该过程检查大小S'是否小于S的大小，如果是(4184的结果为“是”)，则为未使用的空间创建新的碎片，并在元储存4188中用S'→SIZE更新扇区SIZE元数据；如果S'和S的大小相同(4184的结果为“否”)，则不需要进一步处理。另一方面，如果S'→SIZE>S→SIZE(4110的结果为“是”)，则为扇区溢出。
首先触发碎片利用过程4120，并在列表中查找由于先前将另一个扇区重新定位到区间中而在压缩页面中创建的碎片4123；如果存在碎片Fi，其中S'4126可以适应，则首先，创建新的碎片F'，以记录旧版本的扇区S的当前位置(S→PTR)和大小(S→SIZE)4129(顶部)；之后，更新扇区转换元数据(元储存)4129(底部)。如果碎片Fi的大小不能被完全利用以适应S'，则必须更新Fi的位置和大小，以记录所述碎片的未使用空间。如连接4129和4123的箭头所示，必须同时更新Fi和F'的碎片列表。这样一来，就可以处理扇区溢出。
如果不存在将被利用以处理扇区溢出的碎片，则触发区间利用过程4130。所述过程4130首先检查与压缩扇区所属的页面相关联的区间是否有足够的大小以容纳S'4134。如果有(4134中的结果为“否”)，则首先，创建新的碎片F'，以记录旧版本的扇区S的当前位置(S→PTR)和大小(S→SIZE)4138(顶部)；之后，更新扇区转换元数据(元储存)4138(底部)，使扇区指针指向区间的起始端，并以S'的大小更新扇区大小；此外，还必须相应地更新区间的边界以及将区间的使用比特设置为‘1’。这样一来，就可以处理扇区溢出。
如果区间利用者不能处理溢出，则会触发的再压紧过程4140。所述过程的目标是将扇区一个接一个地放置，以便消除任何外部碎片化。所述过程具有预处理步骤4143，其读取基于扇区的转换元数据扇区PTR和扇区SIZE；扇区指针(PTR)通常在基于扇区的转换元数据中；扇区大小(SIZE)要么被提供(图24)；要么可以通过减去扇区指针来计算(图22/23)，或者通过针对每个扇区将扇区内所有高速缓存行的CL-SIZE相加来计算(图29)，或者通过针对每个扇区将CL-SIZE与扇区内高速缓存行的数量相乘来计算(图33)。所述预处理步骤4143还可以利用碎片列表以快速判断是否有可用的碎片。预处理步骤4143使用整个区间或部分区间来计算所述扇区如果再压紧后是否可以适合现有的压缩页面。如果成功(4146的结果为“是”)，则通过以下步骤执行再压紧4149：从存储器中读取所述扇区，将其再压紧在缓冲器中，并将其写回压缩存储器，从而更新元储存中的扇区转换元数据和区间元数据。如果不成功(4146的结果为“否”)，则扇区溢出以如下两种方式处理：或者通过扩展区间(如果可能的话)4150并再次触发区间利用过程4130，或者通过对压缩页面进行完全解压缩4170；特别是如果压缩页面的大小及其区间超过未压缩页面(即，页面帧)的大小4160，则优选后者。无论那种情况，存储器压缩系统的空闲管理器必须保证解压缩页面或扩展的区间不会覆盖与对其处理过扇区溢出的所述压缩页面无关的其他数据。
在替代实施方式中，在碎片利用4120中，如果碎片Fi的大小不能完全利用以适合S'，则扇区S'的数据可以用无关比特来填充以适合其余的碎片空间。这可以潜在地简化碎片管理，但会产生内部碎片化(在新的扇区S'中)，同时解压缩器必须能够对混合有无关比特的数据进行解压缩。
在又一替代实施方式中，碎片利用过程可以被绕过，以更好的空间利用率来换取更快的溢出处理。在又一替代实施方式中，可以完全省略碎片利用，以更好的空间利用率来换取更简单的溢出处理。在又一替代实施方式中，可以省略4188，从而在扇区中创建内部碎片化(即，不可跟踪的碎片化)。其他替代实施方式可以由本领域技术人员实现，并且还考虑了这样的实施方式。
图42描述了扇区溢出设备4200，其包括以下单元：Ovf检查单元4210、碎片利用单元4220、区间利用单元4230和再压紧器单元4240。所述单元实现图41A至图41C的方法中所述的功能；Ovf检查单元4210实现4110和4180的功能，碎片利用单元4220实现4120的功能，区间利用单元4230实现4130的功能，并且再压紧器单元实现4140和4160的功能。
图43描述了存储器压缩系统4300的实施方式，该系统包括基于扇区的地址转换设备4310、扇区-溢出设备4320、空闲存储器管理器设备4330、压缩设备4340和解压缩设备4350，最后是压缩存储器4360，该压缩存储器4360还包括区间4365以及压缩数据或者压缩数据和非压缩数据的混合。基于扇区的地址转换设备4310可以是2700、2800或3200中的任何一个(包括解压缩设备4350和压缩设备4340，共同形成用于访问压缩式计算机存储器的设备4305)。扇区溢出设备可以是实施方式4200。空闲存储器管理设备可以是管理空闲存储器的设备的任何实施方式，例如，辅助存储器设备(第一实施方式，零复制)的任何实施方式。压缩设备和解压缩设备可以实现任何压缩和解压缩算法，但解压缩设备必须能够对用所述压缩设备压缩的数据进行解压缩。对于存储器中的每个压缩页面，可以存在与所述压缩页面相关联的区间4365；所述区间被用作扇区溢出设备4320与空闲存储器管理设备4330之间的同步点，以确定有多少空间用于存储容量扩展和溢出处理。如前所述，扇区溢出设备4320/4200可以静默地处理溢出，直到区间利用4230、碎片利用4220和再压紧器4240可以处理所述溢出；如果所述溢出设备不能处理所述溢出，则对压缩页面进行解压缩，或对区间进行扩展。无论那种情况，都会通知空闲存储器管理器4330(例如，通过中断)以对压缩存储器进行重新组织，使得其他不相关的数据不会被这些动作中的任何一个覆盖。这是所述设备之间同步的一个示例。本领域技术人员可以使用锁定机制或其他这样的机制来实现所述单元的同步。在替代实施方式中，如果所述溢出设备不能处理所述溢出，则可以将整个页面重新定位到存储器中的另一个位置(如第[0118]段所述)，或者将页面拆分(如第[0120]段所述)。
因此，图43可以被视为基于扇区的存储器压缩系统4300，其包括压缩存储器4360、如本文前面所述的用于访问压缩式计算机存储器的设备4305、2700、2800、3200以及空闲存储器管理设备4330。
有利的是，空闲存储器管理设备4330包括压缩存储器管理设置405(参见图4和相关描述)，用于具有一个或更多个处理器P
空闲存储器管理设备4330的存储器管理设置405被配置为触发可压缩主存储器414中的存储页面的压缩，拦截从所述操作系统420向所述次级存储器450提出的页面调入请求，使用由辅助存储器440维持的压缩存储空间的布局，以在可用时将由页面调入请求所请求的页面定位在所述辅助存储器430中，并使所定位的请求页面可用在压缩存储空间的活动部分中。空闲存储器管理设备4330的存储器管理设置405还进一步被配置为拦截从所述操作系统420到所述次级存储器450的页面调出请求，使用由辅助存储器440维持的压缩存储空间的布局来为由页面调出请求所请求的页面获得空闲区域，并且在获得的辅助存储器440的空闲区域中容纳请求的页面。
如已经说明过的，基于扇区的存储器压缩系统4300还可以包括扇区溢出设备4320、4200，其中，扇区溢出设备4320、4200包括溢出检查单元4210、碎片利用单元4220、区间利用单元4230和再压紧单元(4240)。溢出检查单元4210被配置为检查压缩扇区的新版本的大小是否大于旧版本的大小，并且如果不是，则允许用扇区的新版本覆盖旧版本。碎片利用单元4220被配置为：如果由溢出检查单元4210发现扇区的新版本的大小大于旧版本的大小，则在空闲存储碎片列表中搜索适当大小的存储碎片以适合该扇区的新版本，并且如果成功地找到这样的存储碎片，则在找到的存储碎片中插入该扇区的新版本，并通过在空闲存储碎片列表中插入旧版本所在的区域使该扇区的旧版本无效。区间利用单元4230被配置为通过相应地更新区间数据4365、Range中的空闲数据量来在区间数据4365、Range中容纳扇区的新版本，并且如果是这样，则通过在空闲存储碎片列表中插入旧版本驻留的区域来使扇区的旧版本无效。最后，再压紧单元4240被配置为重新设置扇区数据，使得将不同的存储碎片移动到一起，以形成一个连续的空闲存储碎片空间。
在一个或更多个实施方式中，溢出检查单元4210还包括扇区下溢处理单元，该扇区下溢处理单元被配置为检查压缩扇区的新版本的大小是否小于旧版本的大小，如果不是，则允许旧版本被扇区的新版本覆盖，否则在空闲存储碎片列表中插入新的存储碎片，该新的存储碎片的大小等于扇区的旧版本与新版本之间的差值，并相应地用新版本覆盖扇区的旧版本的部分。
被区间利用单元4230利用的区间数据4365、Range可以是与扇区连续的存储空间、与扇区不连续的存储空间或非存储空间。
在一个或更多个实施方式中，基于扇区的存储器压缩系统4300还包括如上文参照图35至图38所述的用于导出压缩元数据的设备。
结束语
回顾所公开的发明的一个方面是一种压缩存储器管理设置，其用于具有一个或更多个处理器、可压缩主存储器、次级存储器和操作系统的计算机系统，其中可压缩主存储器具有压缩存储空间，该压缩存储空间包括可直接访问所述一个或更多个处理器的活动部分，以及不可直接访问所述一个或更多个处理器的非活动部分，该压缩存储空间的形式为通过存储器压缩而释放的内存。压缩存储器管理设置包括辅助存储器，其用于维持可压缩主存储器的压缩存储空间的布局，该布局包括各个存储页面的大小和位置以及所述压缩存储空间中的空闲存储区域。压缩存储器管理设置还包括使所述操作系统、所述次级存储器和所述辅助存储器交互的选择器功能。该存储器管理设置被配置为：a)触发对可压缩主存储器中的存储页面的压缩；b)拦截从所述操作系统到所述次级存储器的页面调入请求，使用由辅助存储器维持的压缩存储空间布局以在可用时在所述辅助存储器中定位由页面调入请求所请求的页面，并使所定位的请求页面可用在压缩存储空间的活动部分中；以及c)拦截从所述操作系统到所述次级存储器的页面调出请求，使用由辅助存储器维持的压缩存储空间布局，以为由页面调出请求所请求的页面获得空闲区域，并在获得的辅助存储器的空闲区域中容纳所请求的页面。
显然，措辞“可压缩的主存储器具有压缩存储空间，该压缩存储空间包括对所述一个或更多个处理器可直接访问的活动部分，以及对所述一个或更多个处理器不可直接访问的非活动部分，该压缩存储空间的形式为通过存储器压缩而释放的内存”并不要求可压缩的主存储器的内容本身对一个或更多个处理器可直接访问。计算机系统领域的技术人员将认识到，在物理主存储器、操作系统和处理器之间将始终存在关于内容的检索和转移的某种程度的间接性。因此，正如本领域技术人员将理解的那样，“……压缩存储空间包括可直接访问所述一个或更多个处理器的活动部分”可能涉及在需要时在虚拟地址与物理地址之间的映射(例如地址转换查找)，由操作系统根据需要执行必要的地址转换以根据例如页面调入请求检索信息并使请求的信息对处理器可用。
在页面调入(或存储器分配)操作过程中，虚拟地址空间与物理地址空间之间的映射由操作系统创建。操作系统的页面表中存在多个有效的映射，其中一部分映射被保存在用于活动地访问的存储器的转换后备缓冲器(TLB)中。因此，由于操作系统在内核上运行，活动的存储器可由内核直接寻址，并且处理器可以通过TLB映射而使用标准的加载和储存指令来直接读取或写入信息。已经从物理存储器中丢弃的页面，例如那些被选择以储存在层次结构的较低部分(诸如交换储存空间)中的页面，被视为是储存在存储器的非活动部分的非活动页面。因此，辅助存储器可以在使用压缩地址空间寻址的主存储器(即，实际的压缩存储器)中同时维持活动页面和非活动页面。区别在于，活动页面必须能够被即时找到，例如，当处理器加载或储存命令被触发时，或者作为第二个示例，当操作系统触发页面调出操作时。另一方面，已经被辅助存储器放置在压缩存储器中的非活动页面被所述存储器检索。
换句话说，一旦操作系统执行了表格查找，存在于物理主存储器的压缩存储空间(即，压缩存储器地址空间)的活动部分中的信息将易于为处理器所用。正如技术人员所熟知的那样，这在当代计算机系统中是普遍存在的。相反，在当代计算机系统中，当这种信息驻留在压缩存储器的非活动部分中时，它将不易于为处理器所用，因为它是由存储器压缩释放出来的存储器构成的，而处理器对此过程是完全未知的。
从前面的详细描述中应该显而易见的是，所公开的发明的主要特征在于：通过提供包括辅助存储器的压缩存储器管理设置，也利用通过存储器压缩而释放的内存，即，属于压缩存储空间的非活动部分的部分，扩展了物理主存储器的容量。然而，这并不改变如下事实，即处理器和操作系统都不能直接访问压缩存储空间的非活动部分；本发明的带有辅助存储器的压缩存储器管理设置负责这一点。
然而，所公开的发明的存储器压缩管理机制与被称为鼓胀(ballooning)的现有技术方法有很大的不同。本领域技术人员将知道，基于鼓胀的存储器压缩机制通过向空闲空间分配新的物理地址来过量使用给予操作系统的存储器。熟悉存储器压缩技术的人员知道，鼓胀机制既针对空闲存储器，也针对存储空间中的其他存储器，并迫使操作系统将页面从活动存储器中换出。鼓胀机制会导致整个系统上的等待时间过长。
本发明的发明者已经认识到这一点。相反，所公开的发明则提供了一种压缩存储器管理设置，其具有辅助存储器，该辅助存储器用于维持压缩存储空间的布局。该布局包括各个存储页面的大小和位置以及压缩存储空间中的空闲存储区域，即，通过可压缩主存储器的存储器压缩而释放出来的存储区域(见上面第[0087]段)。带有辅助存储器的压缩存储器管理设置通过执行以下功能来跟踪和管理压缩存储空间中的空闲存储区域(见上面第[0086]段)：
-带有辅助存储器的压缩存储器管理设置拦截从操作系统到次级存储器的页面调入请求，利用由辅助存储器维持的压缩存储空间的布局以在辅助存储器中定位由页面调入请求所请求的页面，并使所定位的请求页面可用在压缩存储空间的活动部分中。
–此外，带有辅助存储器的压缩存储器管理设置，拦截从操作系统到次级存储器的页面调出请求，使用由辅助存储器维持的压缩存储空间的布局，以获得页面调出请求所请求的页面的空闲区域，并将所请求的页面容纳在获得的辅助存储器的空闲区域中。
由于带有辅助存储器的压缩存储器管理设置维持了空闲存储区域，因此不需要像现有技术中的鼓胀方式那样，通过诸如鼓胀等机制为空闲空间分配新的物理地址。
机译： 在具有转发条目集和多个空闲空间段队列的转发数据库中用于空闲空间管理的方法和设备
机译： -带有内置地址空间管理器和存储系统的地址空间管理器，用于将部分地址空间分配给数据存储，而无需不可寻址的单元半导体存储器
机译： 数据库空闲空间管理系统
