页面大小可变的虚拟内存系统

摘要

本发明提供一种管理页面大小可变的虚拟内存系统的方法。页面大小无需为二的次方。大小可变的、任意大小的页面映射到连续段或虚拟地址空间。本方法也便于在虚拟内存区域有效的迁移、插入和删除数据。本方法还提供虚拟查找表。

说明书

技术领域

本发明涉及计算机和其他电子设备的内存管理，尤其涉及虚拟内存系统中大小可变 页面的映射。同时，还涉及大小可变页面可映射于虚拟内存系统之中的计算机。

背景技术——现有技术说明

虚拟内存系统广泛用于现代计算机和其他电子设备。虚拟内存系统允许程序在一个 或多个虚拟内存区域使用虚拟地址访问数据。

虚拟内存系统的内存管理单元（MMU）将一个地址空间的地址转换为另一个地址空 间的地址。就MMU而言，第一个地址空间称为虚拟地址空间，第二个地址空间称为物理 地址空间。虚拟地址空间的地址称为虚拟地址，物理地址空间的地址称为物理地址。在 某些情况下，必须将物理地址进一步转换为可用地址。

MMU包括查找表（转换旁视缓冲器形式）、页表、反置页表、散列表或类似表，使 虚拟地址空间的一系列地址与页表项相关联。许多MMU结合使用转换旁视缓冲器和页 表。页表项包括转换描述符，也称页描述符。页描述符字段使所述页表项与物理地址空 间的若干（一些）地址相关联。在传统系统中，物理地址空间被分为预定固定大小的页 面。每个页描述符字段包括物理地址空间中的一个页面的地址。通常，页描述符的低位 会被删节。

地址转换过程中，虚拟地址分为页码和页偏移量。MMU定位与页码相关的页表项。 页表项中页描述符字段中的页面地址与虚拟地址的页偏移量部分一起来确定物理地址。

页表项还包括若干访问控制和保护字段，如只写字段、只读字段和执行字段，为页 表项所映射的页面提供访问控制和保护。

时常，可在主存储器或辅助存储器中定位页面。通过虚拟内存系统中的页数据库、 页框数据库或核心地图可跟踪各页面的物理位置。

页面的有效大小为所述页面中地址映射到的虚拟地址的数量。在传统虚拟内存系统 中，页面大小与其有效大小相同。

虚拟内存系统通常在多个级别实施，或与其他地址转换机制一起实施。例如，英特 尔（Intel）80386微处理器执行两级分页地址转换机制，并支持页目录和页表。除了分页 机制之外，英特尔80386微处理器还支持分段机制。

现有虚拟内存系统存在许多缺点。尤其是针对将物理内存映射到虚拟地址空间提供 的框架不灵活，如下所述。

1、页面大小需从少数可能的页面大小中选择。页面不可能为任意大小。页面不可能 为非二的次方的数。

2、页面的物理地址需在固定边界对齐。页面的物理地址需为所述页面大小的倍数。 页面的物理地址不可能在其他或任意选择的边界对齐。

3、某些虚拟内存系统支持可能页面大小中的很多页面大小。在某些情况下，如果两 个或两个以上页面在物理地址空间和虚拟地址空间是连续的，则根据固定规则两个或两 个以上页面结合形成较大的页面。然而，总的来说，在单个虚拟地址空间结合使用任意 大小的页面是不可能、不切实际或无益的。

4、必须在虚拟地址空间的固定边界映射页面。所述虚拟地址需为该页面大小的倍 数。不可能在其他或任意选择的虚拟地址映射页面。如果新虚拟地址未在所述固定边界 对齐，则不可能将之前在虚拟地址映射的页面重新映射到更高或更低的虚拟地址。

5、需把整个页面映射到虚拟地址空间。不会在页面中保持未用、备用或未映射空 间。页面有效大小需与页面大小相等。

6、虽然虚拟地址页偏移量部分未转换，但无需修改即可用作该页面的页偏移量。页 偏移量不另外参与转换或映射过程。

7、页表项将整个页面映射到虚拟地址空间。不会使用页表项映射部分页面。使用多 个页表项映射相同页面或部分相同页面，是毫无意义的。

8、未提供细粒度保护和访问控制。如上所述，保护和访问控制限于固定大小页面。 然而，在实践中，不可能确保需要控制的数据逻辑单元完全适合一个或多个固定大小页 面。

9、未提供创建和管理内存映射功能或程序的方法。

10、未提供创建和管理内存映射虚拟查找表的方法。在编程中，经常希望提供一些 计算结果作为查找表。例如，虚拟查找表可提供自然数的平方根。理想情况下，当在虚 拟地址首先访问所述查找表的项时，可调用用户定义函数计算该位置的相关值。该值可 置于小页面中，该小页面随后可映射到虚拟地址空间。然而，在现有虚拟内存系统中， 页面需相当大，除了预期结果之外，还需计算几个数的平方根。这使得虚拟查找表不可 行。

11、未提供在虚拟内存区域迁移、插入或删除任意量数据的方法，迁移、插入或删 除这些操作可在没有大规模复制现有数据的情况下进行。

12、优化转换旁视缓冲器中有限页表项使用的方法不充分。

因此，需要一种更灵活、更有效的将物理内存映射到虚拟地址空间的方法。

发明目的

本发明的多个目的是提供一种虚拟内存系统，其中：

1、大小不同或有效大小不同的页面映射到连续虚拟地址空间。

2、页面有效大小（即页面的地址映射到的虚拟地址的数量）不需要与所述页面大小 相同。页面有效大小可不时改变。

3、页面大小或有效大小无需固定，而是可能会因页面不同而有所不同，并且可以是 任意方便的大小。页面大小或有效大小不依赖于任何页框大小。

4、页面具有未用、未映射或备用空间。页面中的未用、未映射或备用空间可不时改 变。页面无需存储与页面大小相等的数据，可拥有未用空间，从而存储不等数量的数 据。

5、页面的物理地址无需在固定边界对齐。页面映射到的虚拟地址无需在固定边界对 齐。

6、一个页表项可将两个或两个以上页面，或者两个或两个以上页面的部分内容映射 到虚拟地址空间。若干页表项映射到一个页面或一个页面的部分。

7、为虚拟内存区域的任何部分提供细粒度访问控制和保护。为大小可变或不同大小 页面提供访问控制和保护。此外，可为页面一部分提供访问控制和保护。

8、提供在虚拟内存区域迁移、插入和删除任意量数据的方法，迁移、插入或删除这 些操作不需要大规模复制物理内存中的数据。

9、提供创建和管理有效内存映射功能及程序的方法。此外，还提供创建和管理有效 虚拟查找表的方法。提供的虚拟查找表操作不要求对目标查找表项之外的查找表项值进 行计算。

10、提供优化方法，以优化使用转换旁视缓冲器中有限数量页表项。

根据随后的说明和附图，本发明的进一步目的和优点会更清楚地体现出来。

发明内容

根据本发明，提供创建映射大小可变或不同大小页面的虚拟内存系统的装置和方 法。本发明可将大小可变页面映射到虚拟地址空间。因此，使用该发明时，存储在页面 中的数据量可能会因页面不同而有所不同。

附图

图1显示了本发明内存管理单元101的示意图。

图2A显示了虚拟地址空间。

图2B显示了物理地址空间。

图3显示了虚拟地址。

图4显示了页表结构。

图5显示了页表项结构。

图6显示了映射项结构。

图7显示了转换描述符选择模块的工作情况。

图8显示了地址计算模块的工作情况。

图9显示了将大小可变页面映射到虚拟地址空间的示意图。

图11显示了本发明内存管理单元1101的示意图。

图12显示了转换旁视缓冲器。

图21显示了本发明内存管理单元2101的示意图。

图22显示了转换旁视缓冲器2201。

图31显示了本发明的虚拟内存区域3101。

图32A显示了大小可变页面3201。

图32B显示了大小可变页面3202。

图33显示了页数据库3301。

图34显示了将若干页面3201和3202映射到虚拟地址空间201的情况。

图38A显示了典型内存区域3801。

图38B显示了在迁移某些现有数据和插入新数据之后的典型内存区域3801。

图41显示了虚拟内存区域4101的示意图。

图51显示了虚拟查找表5101的示意图。

本发明详细说明

参考优选实施例和附图，本发明描述如下。但是，所述附图仅说明本发明，不限制 本发明。

图1显示了本发明优选实施例的示意图。相应地，内存管理单元101包括虚拟地址空 间201、物理地址空间202、页表401、页表项选择模块701、转换描述符选择模块702、 地址计算模块801、页面出错处理程序（页面出错处理器）901以及访问控制器1001。

图2A显示了虚拟地址空间。虚拟地址空间201包括若干（一些）虚拟地址。

图2B显示了物理地址空间。物理地址空间202包括若干页面203。每个页面203包括 若干物理地址。

图3显示了虚拟地址301。虚拟地址分为页码302和页偏移量303。

图4显示了页表401。该页表包括若干页表项501。

图5显示了页表项501。页表项包括一个或多个映射项601。

图6显示了映射项601。映射项是转换描述符，包括物理地址映射的虚拟地址，如下 所述。映射项包括LAB字段602、PAB字段603、BC字段604、存在位字段605、访问位字 段606、脏位字段607、只读位字段608、只写位字段609以及执行位字段610。

LAB字段包括一个虚拟地址。PAB字段包括一个物理地址。BC字段包括若干字节。 映射项将若干虚拟地址映射到相同数量的物理地址。LAB和PAB包括完整的地址，并且未 删节低位。

页表项选择模块701通过使用所接收虚拟地址的页码302作为页表索引来选择页表 项。

图7显示了转换描述符号选择模块702。转换描述符号选择模块702尝试在所选页表 项中选择合适的映射项。如果设置了存在位字段，虚拟地址大于或等于LAB值且虚拟地址 小于LAB和BC值之和，则认为适合选择映射项。

图8显示了地址计算模块801的工作情况。地址计算模块801通过将页偏移量303和所 选映射项的PAB值相加来计算指定虚拟地址的物理地址。

图9显示了内存管理单元101的工作情况。在使用虚拟地址进行数据访问期间，页选 择模块选择页表项；转换描述符选择模块在所选页表项中选择映射项。地址计算模块计 算物理地址，如上所述。系统在计算出的物理地址访问数据。

然而，如果不能选择合适的页表项或合适的映射项，则会导致页面出错。页面出错 处理程序901会对页面出错进行处理。页面出错处理程序编写一个合适的页面并在页表项 中插入合适的映射项。然后，页面出错处理程序将控制返回给系统，并且内存访问操作 重启。

当访问映射项映射的内存区域时，内存管理单元在映射项中设置访问位字段。当访 问内存进行写操作时，内存管理单元设置脏位字段。映射项中的访问位字段和脏位字段 用来执行替换策略。

配置访问控制器1001用于执行内存保护和控制策略。需要时，访问控制器在映射项 中设置只读位字段、只写位字段和执行位字段，以提供所需的访问控制，如下所述。如 果在映射项中设置了只读位字段，则尝试修改映射项所映射内存区域的数据时，内存管 理单元会产生异常或故障。如果设置了只写位字段，则尝试读取映射项所映射内存区域 的数据时，内存管理单元会产生异常或故障。如果未设置执行位字段，则尝试执行映射 项所映射内存区域的数据时，内存管理单元会产生异常或故障。利用适当的处理程序可 处理这些异常或故障情况。

映射项所映射的字节数不是固定的，而是需要时可能会发生变化。映射项所映射的 字节数无需为一个或多个具体的页面大小的倍数。映射的字节数无需为二的倍数或二的 次方。映射项所映射的开始虚拟地址和结束虚拟地址无需在虚拟地址空间任何特定边界 对齐，而是需要时可能会发生变化。映射项所映射的开始和结束物理地址无需在物理地 址空间任何特定边界对齐，而是需要时可能会发生变化。

映射项从而将整个或部分页面映射到虚拟地址空间。页面的许多区域可使用一个或 多个页表项中的一个或多个映射项映射到虚拟地址空间。

由于映射项能将页面中任意量数据映射到虚拟地址空间，因此页面可保留未用、备 用或未映射空间。该备用空间可随后映射到虚拟地址空间，并且可用于插入和删除数 据，如随后所述。

正如所见，虚拟内存系统能在虚拟地址空间映射许多任意大小或任意有效大小的页 面。页面大小和有效大小不是固定的，而是无需相同。虚拟内存区域页面的大小和有效 大小无需分别等于所述虚拟内存区域另一个页面的大小和有效大小。页面的物理地址无 需在固定边界对齐。页面第一个地址映射到的虚拟地址无需在固定边界对齐。

图11显示了本发明另一个优选实施例的示意图。相应地，内存管理单元1101包括虚 拟地址空间201、物理地址空间202、转换旁视缓冲器1201、页表项501、映射项601、页 表项选择模块701、转换描述符选择模块702、地址计算模块801、页面出错处理程序901 和访问控制器1001。

图12显示了转换旁视缓冲器1201。转换旁视缓冲器包括一个或多个页表项501。转 换旁视缓冲器中的每个页表项与页码有关。

访问虚拟内存地址时，选择模块使用页码来选择转换旁视缓冲器中的页表项。如果 选择了合适的页表项，则尝试在所选页表项中选择合适的映射项，如前文所述。地址计 算模块计算物理地址，如前文所述。系统现在可以在计算出的物理地址访问数据。

如果不能选择合适的页表项或合适的映射项，则内存管理单元会产生页面出错。页 面出错处理程序901会对页面出错进行处理。页面出错处理程序编写一个物理内存区域或 页面并在转换旁视缓冲器的页表项中插入映射项，然后将控制返回给系统。

所述实施例的其他要素已在前文进行描述。

图21显示了本发明另一个优选实施例的示意图。相应地，内存管理单元2101包括虚 拟地址空间201、物理地址空间202、转换旁视缓冲器2201、页表项501、映射项601、转 换描述符选择模块702、地址计算模块801、页面出错处理程序901和访问控制器1001。

图22显示了转换旁视缓冲器2201。转换旁视缓冲器包括单个页表项501。页表项501 包括一个或多个映射项601。

在所述实施例中，虚拟地址未分为页码和页偏移量。整个虚拟地址被视为页偏移 量。当在虚拟地址访问内存位置时，转换描述符选择模块702尝试从页表项501的映射项 中选择合适的映射项，如前文所述。地址计算模块计算物理地址，如前文所述。系统现 在可以在得出的物理地址访问数据。

如果不能选择合适的映射项，则内存管理单元会产生页面出错。页面出错处理程序 901会对页面出错进行处理。页面出错处理程序编写一个相关的物理内存区域或页面并在 转换旁视缓冲器的页表项中插入合适的映射项，然后将控制返回给系统。

图31显示了本发明的另一个实施例。相应地，虚拟内存区域3101包括内存管理单元 101、大小可变页面3201或3202、页数据库3301、数据迁移模块3501、数据插入模块 3601和数据删除模块3701。

图32A显示了大小可变页面3201（n个字节大小）。n的值可因页面不同而有所不 同。

图32B显示了页面3202，其容量为1024字节，未用或备用空间为91个字节，有效大 小为933个字节，即所述页面的仅933字节会映射到虚拟地址空间。所述页面的有效大小 以及所述页面中未用空间大小可能会因页面不同而有所不同并不时变化。

图33显示了页数据库3301。页数据库包括若干页面3201或3202。页数据库记录虚拟 内存区域的页面及其虚拟地址、各个页面的大小和有效大小。页面的虚拟地址、大小和 有效大小会不时变化。

图34显示了使用内存管理单元101或1101的页表401将页数据库中若干页面3201和 3202映射到虚拟地址空间201的示意图。页表401的一个或多个页表项501中的一个或多 个映射项601将每个大小可变页面中的地址映射到虚拟地址空间。

数据迁移模块3501将虚拟内存区域的一个或多个数据元迁移至更高或更低的虚拟地 址。数据迁移模块通过使页目录中的一个或多个页面与其虚拟地址分离并使所述页面与 新虚拟地址相关联的方式来迁移数据。因此，数据迁移模块可将内存区域的数据迁移至 更高或更低的地址，并且无需物理复制所述数据。

数据插入模块3601在虚拟内存区域插入一个或多个数据元。数据插入模块使用数据 迁移模块将一个或多个现有数据元迁移到新虚拟地址。同时，也配置数据插入模块用于 在页数据库中插入新页面并使新页面与虚拟地址相关联。还配置数据插入模块用于在带 备用容量的页面中插入附加数据元。

数据删除模块3701删除虚拟内存区域中的一个或多个数据元。配置数据删除模块用 于删除页面中的一个或多个现有数据元，从而增加页面的备用容量。同时，也配置数据 删除模块用于使一个或多个数据元与其映射到的虚拟地址分离。还配置数据删除模块用 于删除页数据库中的一个或多个页面。此外，数据删除模块使用数据迁移模块将一个或 多个数据元迁移到新虚拟地址。

配置数据迁移模块、数据插入模块和数据删除模块，用于通过一项或多项以下操作 迁移、插入和删除虚拟内存区域的数据。

1、在页数据库中插入一个或多个新页面。

2、删除页数据库中的一个或多个现有页面。

3、用另一个页面更换数据库中的一个页面。

4、重新编排页数据库中的页面顺序。

5、增加页数据库中的一个或多个页面大小。

6、减少页数据库中的一个或多个页面大小。

7、使页数据库中的一个或多个页面重新关联至虚拟地址空间的更高地址。

8、使页数据库中的一个或多个页面重新关联至虚拟地址空间的更低地址。

9、通过以下方式将新数据插入现有页面：即使用所述页面的未用空间并增加所述页 面的有效尺寸。

10、从页数据库的页面中删除现有数据，增加所述页面的未用空间并减少所述页面 的有效大小。

11、通过修改转换旁视缓冲器或页表中的一个或多个映射项来重新映射或使现有映 射无效。

图38A和38B显示了在内存区域迁移和插入数据的方法。删除数据的方法和插入数据 的方法相反。

图38A显示了典型虚拟内存区域3801包括的若干大小可变页面。相应地，第1、第 2、第3、第4页面在虚拟位置0、63、93和792映射。此外，第1、第2、第3、第4页面将 63、30、699和17个字节分别映射到虚拟地址空间。虚拟地址区域的总大小为809个字 节。

图38B显示了在迁移某些现有数据和插入新数据之后虚拟内存区域3801包括的页 面。相应地，第3页面和第4页面分别在地址105和804映射。第5页面插入内存区域并在 地址93映射。第1页面和第2页面保持不变。第5页面在虚拟地址空间映射的字节数为12。 虚拟内存区域的新大小为821个字节。

按这种方式，第3页面和第4页面中的若干字节迁移至内存区域中更高的地址并且无 需物理复制页面中的数据，第5页面中的若干字节插入内存区域。

图41显示了本发明的另一个实施例。相应地，虚拟内存区域4101包括内存管理单元 101和用户定义函数4102。

用户定义函数4102由系统、程序设计员或用户配置，以进行操作和/或提供数值。

当访问虚拟内存区域的虚拟地址时，发生了页面出错。页面出错处理程序调用用户 定义函数4102。用户定义函数配有该虚拟地址作为输入参数，并根据该参数进行配置操 作和/或计算数值。该数值保存在小页面中。页面出错处理程序使用一个或多个映射项在 虚拟地址映射该页面。现在可在该虚拟地址访问该计算值。

图51显示了本发明的另一个实施例。相应地，虚拟查找表5101包括虚拟内存区域 4101和若干虚拟表项5102。虚拟内存区域的一个或多个虚拟地址代表一个虚拟表项。虚 拟内存区域的所有虚拟表项一起代表虚拟查找表。

当访问虚拟查找表中的项时，发生了页面出错。页面出错处理程序调用用户定义函 数4102。用户定义函数计算数值。该计算值保存在随后会在合适的虚拟地址映射的小页 面中。同样地，无需计算虚拟查找表中访问项之外的项的值。

通过在映射项中设置只读位字段也可为查找表中的项提供保护。然而，如果未使用 只读保护，则可使用虚拟地址修改查找表中的项。任何此类修改可在后续操作中用作用 户定义函数输入。用户定义函数也可使用保存在其他虚拟查找表或虚拟内存区域中的数 值。

发明优点

除了上述优点之外，本发明还有许多其他优点。例如，本发明简化了许多数据结构 及其使用，从而提高了计算机效率。本发明对使用若干不同大小网络数据包创建虚拟内 存区域有用。本发明也对创建带任意大小孔的内存区域有用。

发明范围

本发明可使用页表、转换旁视缓冲器或任何其它合适的机制来实施。本发明也可以 在多个级别实施，使一个级别的物理地址成为另一个级别的虚拟地址。可通过增加页目 录、分段等支持，对分页地址转换机制进行扩展。

映射项结构的一些变化能够缩小页表项或TLB项的大小。例如，可以通过删除一些高 位来缩短LAB字段，因为这些位的数值暗含在页码中。对于带有两个映射项的页表项，无 需第二个映射项的LAB，因为这一数值只要通过前一项的LAB+BC即可获得。另外，第二 个映射项PAB的多个低位可以删除，因为在适当情况下，它们的数值可以为零。

优选实施例显示出一个字节的内存映射粒度。可以通过使用其它的数据类型（例如 位、字、双字或其它的记录类型）来修改映射过程的粒度。

使用本发明能够实现通过单个页表项对多个页面进行映射，或实现将多个页面映射 到单个页框中。页表项的使用还可以实现通过多个页表项来对单个页面进行映射，或者 实现将单个页面映射到多个页框中。另外，无需同时映射某个页框中的所有地址，页表 项也能用于仅仅将页框的一部分映射到物理内存中。

本发明还包括一台具有一个或多个上述特点的电脑或其它电子设备。

尽管上文描述包括许多特征，但这些特征不得解释为发明范围的限制条件，而应是 优选实施例的一个范例。可能还有许多其它的变化。