哪里网站海报做的比较好,桂林建设信息网站,怎么制作网站卖东西,苏州论坛型网站建设Virtual Memory Primitives for User Program
安德鲁阿普尔#xff08;Andrew Appel#xff09;和李凯#xff08;Kai Li#xff09;
普林斯顿大学计算机科学系
摘要
传统上#xff0c;内存管理单元#xff08;MMUS#xff09;被操作系统用于实现磁盘分页的虚拟内存…Virtual Memory Primitives for User Program
安德鲁·阿普尔Andrew Appel和李凯Kai Li
普林斯顿大学计算机科学系
摘要
传统上内存管理单元MMUS被操作系统用于实现磁盘分页的虚拟内存。一些操作系统允许用户程序指定页面的保护级别不可访问、只读、读写并允许用户程序处理保护违规。但这些机制不总是坚固、高效也不总是与应用程序的需求匹配。
我们调查了几种使用页面保护技术的用户级算法并分析了它们的共同特点试图回答以下问题“操作系统应该为用户进程提供什么虚拟内存基元当前的操作系统如何提供它们”
1引言
虚拟内存的“传统”目的是通过只允许常访问的地址空间子集驻留在物理内存中来增加用户程序可见的地址空间的大小。但是虚拟内存已经被用于许多其他目的。操作系统可以在进程之间共享页面使指令空间只读从而保证可重入性使内存的部分区域在需求时清零或在写入时复制等等。实际上操作系统可以利用页面保护硬件执行一大类“技巧”。
现代操作系统也允许用户程序执行此类技巧方法是允许用户程序为保护违规提供“处理程序”。例如Unix允许用户进程指定每当生成段错误信号时执行特定子例程。当程序访问超出其合法虚拟地址范围的内存时用户提供的信号处理程序可以生成用户友好的错误消息而不是令人不安的“段错误core dumped”。
这个简单的用户模式故障处理程序示例是“危险的”因为它可能会使操作系统和硬件设计者相信用户模式故障处理程序不需要高效地进入这对于“优雅的错误关闭”示例来说肯定是正确的。但是用户模式故障处理程序有更有趣的应用。这些应用程序对页面保护和故障处理机制进行了相当严格的测试并且应该被操作系统实现者理解。
本文描述了几种利用页面保护技术的算法。在许多情况下这些算法可以用“传统”的分页硬件替代曾经使用过的“特殊”微码。在共享内存多处理器上这些算法利用页面保护硬件实现了中粒度同步并且开销较低以避免具有显著开销的同步指令序列。
我们对多个系统进行了基准测试以分析当今的操作系统对用户级页面保护技术的支持情况。最后从这些算法中我们总结了有关页面保护成本、内存映射机制的效用、翻译缓冲区的清理、页面大小以及操作系统实现的其他方面的经验教训。
2 虚拟内存基元(Virtual memory primitives)
我们将描述的每个算法都需要操作系统提供以下一些虚拟内存服务
TRAP在用户模式下处理页面错误陷阱
PROT1降低页面的可访问性
PROTN降低 N 个页面的可访问性
UNPROT增加页面的可访问性
DIRTY返回自上次调用以来被修改的页面列表。
MAP2在同一地址空间中以不同的保护级别将同一物理页面映射到两个不同的虚拟地址。
最后一些基于更小PAGESIZE的算法可能会比通常用于磁盘分页的PGAESIZE更有效率。
我们区分“降低页面的可访问性”和“降低一批页面的可访问性”之间的区别有一个特定的原因。同时更改多个页面的保护的成本可能不会比更改一个页面的保护的成本高出多少。我们描述的几种算法只在大批量中保护页面使其更不可访问。因此如果操作系统的实现无法有效地降低一个页面的可访问性但可以以较低的每页成本降低大批量页面的可访问性则对于某些算法来说这是足够的。
我们不会对单个页面与多个页面的解除保护进行区分因为我们描述的所有算法都不会同时解除保护多个页面。一些多线程算法要求一个线程在其他线程对页面出现错误时仍能访问特定页面。对于这种问题有很多解决方案稍后将描述但一个简单且高效的解决方案是将页面映射到多个虚拟地址在一个地址上页面是可访问的而在另一个地址上它会出现错误。出于效率原因这两个不同的虚拟地址应该在同一个页表中这样就不需要在线程之间进行昂贵的页表上下文切换。
用户程序可以使用PROTN、TRAP和UNPROT跟踪脏页面我们将DIRTY列为单独的基元因为操作系统直接提供此服务可能更有效率。
3 虚拟内存应用(Virtual memory application)
在本节中我们展示了一些应用示例这些示例使用虚拟内存基元来代替软件测试、特殊硬件或微码。页面保护硬件可以高效地在地址上测试简单的谓词否则每次获取和/或存储可能需要额外的一两条指令这是一个相当大的节省因为获取和存储操作确实非常常见。我们调查了几种算法以便我们可以尝试得出关于用户程序对操作系统和硬件的需求的一般结论。
并发垃圾回收
并发实时的复制式垃圾回收算法可以利用页面错误机制在收集器线程和mutator线程之间实现中等粒度的同步。页面机制提供了足够粗糙以保证高效的同步同时又足够精细以使延迟较低。该算法基于Baker的顺序实时复制收集器算法。
Baker的算法将内存堆分为两个区域from-space和to-space。在收集开始时所有对象都位于from-space中而to-space为空。从寄存器和其他全局根开始收集器追踪从根可达的对象图将每个可达对象复制到to-space中。从from-space中的对象指针通过将其指向旧对象的to-space副本进行转发。当然一些from-space中的对象永远不会被复制到to-space中因为从未有指针指向它们这些对象是垃圾。
一旦寄存器被转发mutator线程就可以恢复执行。可达对象在mutator分配新对象的同时逐渐从from-space中复制出来。每当mutator分配新对象时它都会调用收集器来从from-space中复制更多对象。Baker的算法保持以下不变性
收集器只看到其寄存器中的to-space指针。新区域中的对象仅包含to-space指针因为新对象是从寄存器初始化的。扫描区域中的对象仅包含to-space指针。未扫描区域中的对象包含from-space和to-space指针。
为了满足mutator只看到其寄存器中的to-space指针这一不变性从对象中获取的每个指针都必须进行检查以查看它是否指向from-space。如果是就将from-space对象复制到to-space并更新指针然后将指针返回给mutator。这种检查需要硬件支持才能高效实现因为否则每次获取都必须执行一些额外的指令。此外mutator和收集器必须交替进行它们无法真正并发地操作因为它们可能同时尝试将相同的对象复制到不同的位置。
与从内存中获取的每个指针进行检查相反并发收集器[4]使用虚拟内存页面保护来检测from-space内存引用并同步收集器和mutator线程。为了同步mutator和collector线程该算法将未扫描区域页面的虚拟内存保护设置为“无访问权限”。每当mutator尝试访问未扫描的对象时它将收到一个页面访问陷阱。收集器捕获陷阱并扫描该页面上的对象根据需要复制from-space对象并转发指针。然后它取消保护页面并将mutator定位到故障指令处。对于mutator来说该页面始终只包含to-space指针因此mutator只会将to-space指针获取到其寄存器中。收集器还与mutator并发执行扫描未扫描区域中的页面并在每次扫描完成后取消保护它们。同时扫描的页面越多mutator收到的页面访问陷阱就越少。由于mutator不需要额外的操作与collector同步因此编译器无需进行重组。多个处理器和mutator线程几乎无需额外的工作即可适应。此算法需要TRAP、PROTN、UNPROT和MAP2。需要陷阱来检测从未扫描区域获取的内容需要对多个页面进行保护以在完成翻转时将整个to-space设置为不可访问对于每个页面的扫描需要取消保护。此外由于用户模式处理程序处理页面所需的时间与页面大小成正比因此可能适合使用较小的页面大小以减少延迟。我们需要对同一页面进行多次映射以便垃圾回收器在对mutator不可访问的情况下扫描页面。在第5节中讨论了多映射的替代方法。
共享虚拟内存
访问保护分页机制已被用于在计算机网络上实现共享虚拟内存在没有共享内存的多计算机系统上实现共享虚拟内存以及基于互连网络的多处理器上实现共享虚拟内存。共享虚拟内存的基本思想是使用分页机制来控制和维护页面级别的单写多读一致性。图1显示了一个典型系统的系统架构。在多计算机系统中系统中的每个节点由处理器和其内存组成。节点通过快速消息传递网络连接在一起。 该系统为所有处理器提供一个大的一致共享内存地址空间。任何处理器都可以随时访问任何内存位置。共享内存地址空间的大小可以达到处理器所提供的内存地址空间的大小该地址空间在任何时候都是一致的也就是说读操作返回的值始终与最近写入相同地址的写操作的值相同。
该系统的地址空间被划分为页面。标记为“只读”的页面可以在多个处理器的物理内存中同时存在副本。但是当前正在写入的页面只能存在于一个处理器的物理内存中(proudcer-cosumer)。如果处理器希望写入当前驻留在其他处理器上的页面则必须获取页面的最新副本然后通知其他处理器使其副本无效。内存映射管理器将其本地内存视为其关联处理器的SVM地址空间的大缓存就像传统的虚拟内存一样。共享内存本身实际上是虚拟存在的。当内存引用导致页面错误时即当包含内存位置的页面不在处理器的当前物理内存中时内存映射管理器将从磁盘或另一个处理器的内存中检索页面。
该算法使用了TRAP、PROT1和UNPROT。陷阱处理程序需要访问仍然受客户线程保护的内存。内存映射MAP2可能需要访问内存。此外较小的页面大小可能是合适的。
并发检查点
访问保护页面错误机制已成功地用于使检查点成为并发和实时操作。这种用于共享内存多处理器的算法与目标程序并发运行以小而固定的时间间隔中断目标程序并且对于被检查点程序及其编译器是透明的。该算法通过使用分页机制允许检查点中最耗时的操作与正在进行检查点的程序的运行重叠从而实现了效率。
首先停止被检查点程序中的所有线程。接下来保存程序的可写主内存空间包括堆、全局变量和每个线程的堆栈。此外为每个线程保存足够的状态信息以便可以重新启动。最后重新启动线程。
与一次性将可写主内存空间全部保存到磁盘不同该算法通过使用访问保护页面错误机制来避免这种长时间等待。首先将整个地址空间的可访问性设置为“只读”。此时重新启动了被检查点程序的线程并且一个复制线程顺序扫描地址空间将页面复制到单独的虚拟地址空间。当复制线程完成复制一页时将其访问权限设置为“读/写”。
当用户线程对只读页面进行读取内存引用时它们的运行速度与没有进行检查点时一样快。如果程序的线程在复制之前写入页面则会发生写内存访问错误。此时复制线程立即复制页面并将页面的访问权限设置为“读/写”然后重新启动出错的线程。
在DEC Firefly多处理器上使用了几个基准程序来测量此算法的性能。测量结果显示约90%的检查点工作与目标程序同时进行而且没有线程被中断超过1秒。
这种方法也适用于进行增量检查点保存自上次检查点以来发生更改的页面。与保护所有页面为“只读”不同该算法可以仅保护自上次检查点以来已更改的“脏”页面。Feldman和Brown通过使用可逆执行来实现了用于调试系统的顺序版本并提出并实现了系统调用DIRTY。
该算法使用了TRAP、PROT1、PROTN、UNPROT和DIRTY中等大小的页面大小可能是适当的。
分代垃圾回收
分代垃圾回收是内存保护的一个重要应用是一种非常高效的算法依赖于LISP和其他编程语言中动态分配记录的两个属性
年轻的记录比年长的记录更有可能很快死亡。如果一条记录已经存活了很长时间那么它很可能会继续存活下去新的记录很可能是计算的临时中间值的一部分。
#感觉这也是局部性原理的一种体现
年轻的记录倾向于指向年长的记录因为在LISP和函数式编程语言中分配记录的行为也会将其初始化为指向已经存在的记录。
属性1表明垃圾收集器的大部分工作应该集中在年轻的记录上属性2提供了一种实现这一点的方式。分配的记录将被保留在内存的几个不同区域Gi中称为代。同一代中的记录具有相似的年龄而Gi代中的所有记录都比Gi1代中的记录年长。根据上述第2条观察对于i jGi到Gj的指针应该非常少或没有。收集器通常会在最年轻的代中进行收集因为其中垃圾的比例最高。为了在一个代中执行收集收集器需要了解指向该代的所有指针这些指针可以在机器寄存器中、全局变量中和堆栈上。然而由于上述第2条属性的存在较旧的代中很少有这样的指针。
较老的代可以指向较年轻的代的唯一方式是通过对已经存在的记录进行赋值。为了检测这样的赋值必须检查对堆对象的每次修改以查看是否违反了第2条属性。这种检查可以通过特殊硬件完成也可以通过编译器完成。在后一种情况下需要两个或更多的指令。幸运的是在Lisp、Smalltalk和类似的语言中非初始化的赋值很少发生但是进行检查的指令序列的开销没有特殊硬件仍然在总执行时间的5–10%左右。
虚拟内存硬件可以检测对旧对象的赋值。如果存在DIRTY功能收集器可以检查已修改的页面从而推导出从旧一代指向年轻一代的指针并对其进行处理。在没有这种服务的情况下收集器可以使用页面保护机制可以将较旧的代写保护以便任何对它们的存储操作都会引发陷阱。用户陷阱处理程序可以将触发陷阱的页面地址保存在垃圾收集器的列表中然后必须取消保护该页面以允许存储指令的执行。在垃圾收集时收集器将需要扫描陷阱列表上的页面以查找可能指向最年轻一代的指针。这种算法的变体已经表现出相当良好的性能随着堆和内存的增大这种方案开始占据主导地位超过其他技术。这种技术使用了TRAP、PROT1和UNPROT特性或者只使用DIRTY。此外由于用户模式处理程序处理页面的时间与页面大小无关而垃圾收集器最终扫描页面的时间与页面大小成正比因此使用较小的页面大小可能是适当的。
持久存储
持久存储是一种从一个程序调用到下一个程序调用持续存在的动态分配堆。程序的执行可以遍历持久存储中的数据结构就像它在自己的堆中一样。它可以修改持久存储中的对象甚至使它们指向自己的新分配的对象然后可以提交这些修改到持久存储中或者可以中止操作在这种情况下对持久存储没有净影响。在执行之间和期间持久存储被保留在稳定的存储设备如磁盘上以便“数据库”不会消失。
在持久存储中对指针的遍历与主内存中的取值和存储一样快是很重要的理想情况下持久存储中的数据结构不应该被程序的编译代码与内存中的数据结构区分开。这可以通过使用虚拟内存来实现持久存储是一个内存映射的磁盘文件通过持久存储进行指针遍历就像在内存中进行指针遍历一样如果对存储的新部分进行检查则会发生页面错误。
#这是怎么做到一样快的呢
然而当持久存储中的对象被修改时永久镜像必须在提交时才能被修改。在内存中的镜像被修改时并且只有在提交时“脏”页面可能包括一些新创建的页面才会被写回磁盘。为了减少新页面的数量适合在提交时进行垃圾回收。
数据库是一个存储管理系统可以提供锁定对象、带有中止/提交的事务、检查点和恢复等功能。虚拟内存技术与数据库实现的整合已经被长期研究。编译程序可以非常快速、轻松地遍历其堆中的数据因为每个访问操作只是一个编译的取值指令。在传统数据库中遍历数据要慢得多因为每个操作都是通过过程调用完成的访问过程确保事务的同步和中止能力。持久存储可以被增强以清晰地处理并发和锁定这样的系统有时被称为面向对象的数据库可以通过取值指令快速遍历同时也可以提供同步和锁定通过使用垃圾回收器将相关对象分组到同一页中、将小对象与大对象区别对待等方式可以提高访问的效率
这些方案需要使用TRAP和UNPROT以及文件映射与写时复制如果其他情况下不可用可以使用PROT、UNPROT和MAP来模拟。
扩展可寻址性
持久存储可能变得非常庞大包含的对象数量超过了例如32位指针所能寻址的范围。现代硬盘驱动器特别是光盘肯定可以容纳如此大的数据库但传统处理器使用32位地址。然而在对持久存储进行的任何一次程序运行中访问的对象数量可能少于32位指针所能表示的范围。
解决这个问题的一种方法是修改持久存储机制使内存中的对象使用32位地址而磁盘上的对象使用64位地址。每个磁盘页面的长度恰好是内存页面的两倍。当从磁盘将页面加载到内存时其64位磁盘指针将通过一个转换表被翻译成32位内存指针。当其中一个32位内存指针第一次被解引用时可能会发生页面错误错误处理程序会从磁盘中加载另一个页面并将其转换为短指针。
转换表仅针对在单个执行中访问的对象有条目这就是为什么32位指针就足够的原因。内存中的指针可能指向尚未访问的页面这样的页面在内存中未分配但转换表中有一条目显示其未翻译内容存储在哪个64位指针磁盘页面上。
在内存中使用短指针和在磁盘上使用长指针并且仅为一个会话中使用的对象子集创建转换表的想法起源于Smalltalk-80的LOOM系统。使用页面错误机制来实现这一点是较近期的方法。该算法使用TRAP、UNPROT、PROT1或PROTiV在多线程环境中和可能与较小的页面大小很好地配合工作。
堆溢出检测
进程或线程的堆栈需要防止溢出访问。在大多数系统中使用的一种众所周知且实用的技术是将堆栈顶部以上的页面标记为无效或无法访问。对这些页面的任何内存访问都将导致页面错误。操作系统可以捕获这样的错误并通知用户程序发生了堆栈溢出。在大多数Unix实现中堆栈页面在首次使用之前不会被分配操作系统对页面错误的响应是分配物理页面、标记它们为可访问并在不通知用户进程的情况下恢复执行除非超出资源限制。
#Lab: trap运用到的思想
这种技术需要TRAP、PROTbJ和UNPROT。但由于这类错误非常罕见大多数进程不使用太多的堆栈空间效率并不是问题。
相同的技术可以用于在垃圾收集系统中检测堆溢出。通常在这种系统中堆溢出是通过对每个内存分配执行比较和条件分支来检测的。通过让用户进程在由警戒页面终止的内存区域中分配新记录可以消除比较和条件分支。当达到可分配内存的末尾时会触发页面错误陷阱调用垃圾收集器。通常情况下不需要重新调整内存保护因为在收集后可以重新使用相同的分配区域。因此这种技术需要PROT1和TRAP。
在这里TRAP的效率是一个问题。一些语言实现可能会频繁地分配新的单元比如每50条指令分配一次。在分代垃圾收集器中分配区域的大小可能非常小以使最年轻的代完全适应数据缓存例如一个64KB的分配区域可以容纳16k个列表单元。在一个非常频繁分配的系统中例如将活动记录保存在堆上的系统这样的数据比例非常小因此垃圾收集时间本身会很短。因此我们有
堆溢出之前执行的指令数
(64k/8) X 50 400k。
使用比较和分支的额外指令数
(64k/8) X 2 16k。
如果一个陷阱处理需要1200个周期通常情况下见第4节那么这种技术将将开销从4%降低到0.3%是一个值得的节省。如果一个陷阱需要更长的时间那么这种技术将不会那么高效。
由于还有其他有效的技术可以减少堆限制检查的开销例如在展开的循环中组合几个连续分配的限制检查因此这种虚拟内存的应用可能是本文讨论的最不有趣的之一。
4原始VM的性能(VM primitive performance)
我们在本文中描述的几乎所有算法都可以归类为两种类别。第一类算法是以大批量保护页面的形式进行然后在每次页面故障陷阱时取消保护一个页面。第二类算法是对页面进行保护然后在线程或进程完成对页面的使用后立即取消保护。由于PROT1或PROTN、TRAP和UNPROT总是一起使用因此一个操作系统中如果其中一个操作非常高效而其他操作速度很慢那么该系统将不会很有竞争力。
我们进行了两项整体用户模式虚拟内存性能的测量。第一项是PROT1、TRAP和UNPROT的总和通过以下基准程序的100次重复来测量
访问一个随机保护的页面并且在故障处理程序中保护另一个页面并取消保护故障页面。
重复此过程100次以获取更准确的计时。
第二项测量是PROTiN、TRAP和UNPROT的总和。基准程序测量
保护100个页面以随机顺序访问每个页面并且在故障处理程序中取消保护故障页面。
在开始计时之前这两个程序都会写入每个页面以消除填充缓存和TLB的瞬时效应。
我们比较了在几个平台上执行这些基准测试时的Ultrix、Sun OS和Mach的性能。作为校准我们还展示了单条指令ADD的时间使用一个包含18个加法、一个比较和一个分支的20条指令循环进行测量。我们还显示了一个不改变任何内存保护的陷阱处理程序的时间这对于堆溢出检测是有用的。结果如表1所示。请注意此基准测试不是“整体操作系统吞吐量”基准测试并且不应受到磁盘速度的影响它测量的是用于用户级程序的由CPV处理的虚拟内存服务的性能。 对于每个操作以微秒为单位给出了经过的时间。对于Mach我们同时测量了异常端口机制“exc”和外部页面接口“xp”的时间。TRAP的时间是操作系统开销加上标准库中提供的用户模式陷阱处理程序的部分。对于PROT1和PROTN基准测试我们显示每页的时间。MAP 2表示系统是否支持在不同地址映射相同的页面请参阅第4节。PAGE SIZE是操作系统报告的页面大小。 我们还尝试在同一个进程中使用SunOS和Ultrix的共享内存操作SIMNOP以及在Mach中使用VM-MAP将物理页面映射到两个不同的虚拟地址。SunOS和Mach允许这样做但Ultrix不允许我们在同一个进程中的两个不同地址附加SLLMAT相同的共享内存对象。
显然即使在相同的硬件上这些操作系统的性能也存在很大的差异。这表明某些或所有这些系统都可能存在相当大的改进空间。此外一些操作系统的几个版本在mprotect调用后没有正确刷新其翻译缓冲区这表明许多操作系统的实现者并未认真对待这一特性。
这些操作系统服务的效率至关重要。这里的论点比虚无的“效率是好的”要具体得多。对于磁盘分页页面故障通常意味着需要等待磁盘转到正确的扇区这通常需要20毫秒。因此3到5毫秒的故障处理开销几乎不会被视为故障处理延迟的贡献者。但在本文中调查的算法中故障将完全在CPU内部处理。例如我们实现了一个垃圾收集器每个字的to-space大约执行10条指令。对于20 MIPS机器上的4096字节页面大小1024个字处理故障的计算时间将约为10 * 0.05 * 1024即约500微秒。如果操作系统的故障处理和页面保护开销为1200微秒平均值那么操作系统显然是瓶颈。
如果程序表现出良好的引用局部性那么垃圾收集故障将很少发生并且操作系统的开销将不那么重要。但对于必须满足对延迟严格的实时程序来说即使偶尔发生的“慢故障”也会引起问题。例如如果客户端程序不能被中断超过一毫秒那么500微秒的故障处理器计算时间就没有足够的空间来容纳1200微秒的操作系统开销当考虑到连续的多个故障时这个问题会变得更加复杂参见[11]进行分析。图4(#应该是图2吧)显示了每个处理器在保护一个页面、处理故障和取消保护一个页面所需时间内可以完成的ADD指令数量。
我们的基准测试显示在实现虚拟内存原语方面存在广泛的效率差异。基于Intel 80386处理器的机器运行N2i/2操作系统一个用于iPSC/2超立方体多处理器系统的简单操作系统在我们的基准测试中表现最佳。它的标准化基准性能约为最差性能者在Sparcstatlion上的Mach的十倍。显然这些原语不一定就会慢。硬件和操作系统设计者应该将内存保护性能视为设计过程中的一个重要权衡因素。 5系统设计问题(System design issue)
通过我们对虚拟内存应用的调查我们可以从中学到一些关于硬件和操作系统设计的重要经验教训。大多数应用以类似的方式使用虚拟内存这清楚地说明了需要哪些支持同样重要的是哪些是不必要的。
TLB一致性
这里介绍的许多算法将内存分批次变得不太可访问并且一次性使内存中的一个页面变得更容易访问。这对于多处理器特别有好处因为它解决了TLB转换后备缓冲区一致性问题。当一个页面变得更易访问时TLB中的过时信息是无害的最多只会导致一个次要的、容易修复的TLB未命中或TLB故障。但是当一个页面变得不太可访问时TLB中的过时信息可能导致对页面的非法访问。为了防止这种情况发生必须清除该页面可能驻留的每个TLB中的页面。这种清除可以通过软件中断每个其他处理器并请求其从TLB中清除页面来完成也可以通过各种基于总线的硬件方案来完成。
如果要中断的处理器很多软件清除可能非常昂贵。我们对解决清除问题的方法是对清除进行批处理同时涵盖多个页面的软件清除的成本不比单个页面的清除成本更高当将开销中断进程以通知它们有关清除的情况摊销到多个页面上时每个页面的成本变得可以忽略不计。本文描述的保护页面的算法“无意中”利用了批量清除的优势。
#批处理最早应该诞生于20世纪50、60年代。主要是为了解决计算机系统中 CPU 和 IO 设备之间速度不匹配的问题。
批处理之所以被提出是因为这里描述的算法的结构但它也可以解决传统的磁盘分页的清除问题。在磁盘分页中页面变得不太可访问即被“分页出”以释放物理页面以便其他虚拟页面重新使用。如果操作系统可以保持大量未使用的物理页面那么它可以批量执行分页出以补充储备这将使清除成本在整个批次上摊销。因此虽然曾经声称软件解决方案效果不错但可能需要硬件辅助但是通过批处理硬件可能是不必要的。
最佳页面大小
在这里描述的许多算法中页面错误完全在 CPU 中处理并且错误处理时间不包括开销是页面大小的一个小常数。
当页面错误发生在物理内存和磁盘之间进行分页时磁盘旋转和磁头移动会造成数十毫秒的延迟。在页面错误处理程序中增加几毫秒的计算开销几乎不会被注意到特别是如果没有其他进程准备执行。因此出于许多原因包括动态 RAM 的寻址特性页面传统上相当大错误处理开销很高。
然而对于由 CPU 中的用户算法完全处理的用户处理的错误不存在这种固有的延迟。要减半每个错误的时间不包括陷阱时间只需减半页面大小。这里描述的各种算法可能在不同的页面大小下表现最佳。
可以通过使用小页面大小的硬件来实现页面大小的变化。在 VMP Virtual Memory Management System系统中转换缓冲区和缓存是相同的具有 128 字节的线大小[8]这种体系结构可能非常适合本文描述的许多算法。对于 PROT 和 UNPROT 操作将使用小页面对于磁盘分页将使用连续的多页块如今在大多数系统上都很常见。
当使用小页面时迅速捕获和更改页面保护尤其重要因为这种开销与页面大小无关而实际计算通常花费的时间与页面大小成正比。
访问受保护页面
许多算法在多处理器上运行时需要一种用户模式服务例程访问页面的方式而客户线程则无法访问。这些算法包括并发垃圾回收、扩展地址能力、共享虚拟内存和数据压缩分页。
实现用户模式访问受保护页面有几种方式我们使用并发垃圾回收算法来说明
在同一地址空间中的不同地址以及不同级别的保护上多次映射相同页面。垃圾回收器在 to-space 中的页面上有访问权限而mutator将 to-space 视为受保护的。可以提供一个系统调用来复制内存到受保护区域和从受保护区域复制内存。垃圾回收器在每个页面上需要调用此调用三次一次在从 from-space 复制记录到 to-space 时一次在扫描 to-space 页面之前一次在扫描后使页面对mutator可访问之前。这种解决方案不太理想因为复制所有这些东西的效率不高。在允许进程之间共享页面的操作系统中垃圾回收器可以在与mutator不同的重量级进程中运行并具有不同的页表。这种技术的问题在于每个垃圾回收页面陷阱都需要两个昂贵的重量级上下文切换。但是在多处理器上可能足以对另一个处于正确上下文的处理器进行 RPC这个选项可能更具吸引力。垃圾回收器可以在操作系统内核中运行。这可能是最有效的但也许这不是垃圾回收器的适当位置它可能导致内核不可靠并且每种编程语言都有一个不同的运行时数据格式垃圾回收器必须理解。
我们主张对于具有物理地址缓存的计算机体系结构同一地址空间中的多重虚拟地址映射是一种清晰高效的解决方案。它不需要重量级上下文切换、数据结构复制也不需要在内核中运行。这样做的一个小缺点是每个物理页面将需要在页表中有两个不同的条目根据页表条目大小与页面大小的比率这将增加物理内存需求高达1%。
#页表的雏形
对于虚拟地址缓存多重虚拟地址映射方法存在缓存一致性的潜在问题因为在一个映射中的更新可能存在于缓存中而另一个映射包含过时的数据。在并发垃圾回收算法的背景下这个问题很容易解决。当垃圾回收器扫描页面时mutator无法访问页面因此在mutator的地址中该页面的缓存行不会填充。扫描页面后垃圾回收器应该刷新该页面的缓存行可能使用缓存刷新系统调用。此后垃圾回收器将永远不会引用该页面因此永远不会出现不一致的危险。 扩展地址可寻性和数据压缩分页仅使用PROT1来移除不活跃的页面可以使用第5节中描述的批处理技术来替代。基于虚拟内存的堆溢出检测甚至可以在没有显式内存保护原语的情况下使用只要在可访问和不可访问内存之间存在可用的边界例如在普通Unix中的“断点”。脏页跟踪可以通过使用PROTN、TRAP和UNPROT来模拟。
这种行为在高度流水线化的机器上是不可接受的除非像在 VAX 8800 上那样有用于“撤销”那些已经完成的后续指令或地址模式副作用的硬件。事实上即使在 Motorola 68020 上使用页面故障来检测堆溢出也是不可靠的。因此除了堆溢出检测之外我们介绍的所有算法对硬件来说都不会比普通的磁盘分页带来更多问题邀请到地狱的信函可以退回给发件人然而操作系统必须确保为硬件提供充分的支持使半同步陷阱处理程序能够正确地恢复故障操作。
#居然看到了Motorala真是时代的眼泪啊
其他原语
操作系统可以提供其他虚拟内存原语。对于带有事务的持久存储将页面固定在内存中可能是有用的这样直到事务完成才会将其写回到后备存储器中。
Mach 的外部分页器接口提供了至少一种我们描述的原语缺少的功能操作系统可以告诉客户端哪些页面最近使用的最少因此即将被分页出去。客户端可以选择销毁这些页面而不是将它们写入磁盘。这对于数据压缩分页和扩展可寻址性可能特别有用。此外在具有垃圾回收的系统中客户端可能知道某个区域只包含垃圾并且可以安全地销毁[12]。
#LRU是吗
总的来说外部分页器接口避免了操作系统分页器将不经常使用的页面写入磁盘不必要地重复进行用户模式故障处理程序正在进行的工作的问题。
6结论
在过去虚拟内存只是实现大型地址空间和保护一个用户进程免受另一个用户进程影响的工具但现在它已经发展成为硬件和操作系统接口的用户级组件。我们调查了几种依赖虚拟内存原语的算法过去并未对这些原语给予足够的关注。在设计和分析新机器和新操作系统的性能时页面保护和故障处理效率必须作为设计空间的一个参数加以考虑页面大小是另一个重要参数。相反对于许多算法来说TLB硬件的配置例如在多处理器系统中可能并不特别重要。
表2显示了这些算法的用途和要求。一些算法逐个保护页面PROT1而另一些算法以大批量方式保护页面PROTN这种方式更容易高效实现。一些算法在并发运行时需要访问受保护的页面HMAP。一些算法仅使用内存保护来跟踪修改过的页面DIRTY这项服务可能可以更有效地作为一种原语提供。一些算法可能使用比常用更小的页面大小运行更高效PAGESIZE。
许多利用虚拟内存的算法共享几个特征
页面大批量变得不易访问逐页变得更易访问这对TLB一致性算法有重要意义。故障处理几乎完全由CPU执行并且所需时间与页面大小成正比比例常数相对较小这对首选页面大小有影响。每个页面故障导致故障页面变得更易访问。故障的频率与客户程序的引用局部性呈负相关这将使这些算法在长期内保持竞争力。用户模式服务例程需要访问从用户模式客户例程保护的页面。用户模式服务例程不需要检查客户的CPU状态。
除了堆溢出检测外本文描述的所有算法共享五个或更多个这些特征。
大多数程序在中等时间段内只访问其地址空间的一小部分。这就是使传统磁盘分页有效的原因以不同的方式这也使得这里描述的算法效率高。例如并发垃圾收集算法必须扫描和复制相同数量的数据而不受mutator访问模式的影响但mutator的引用局部性降低了故障处理开销。在分代收集算法、并发检查点和持久存储算法中的“写障碍器”利用了局部性如果一小部分对象占据了大部分更新则利用了局部性。而共享虚拟内存算法利用了一种特殊的分区引用局部性其中每个处理器具有不同的局部引用模式。
我们相信由于这些算法非常依赖于引用局部性它们将具有良好的可扩展性。随着内存变得越来越大计算机变得越来越快程序往往会更积极地使用其地址空间的一小部分而这些算法的开销将继续减少。重要的是硬件和操作系统设计者要确保这些算法所需的虚拟内存机制健壮且高效。
致谢
感谢Rick Rashid、David Tarditi和Greg Morrisett将我们的各个版本的基准程序移植到Mach并在Mach机器上运行并感谢Larry Rogers在SunOS上运行它。Rafael Alonso、Brian Bershad、Chris Clifton、Adam Dingle、Mary Fernandez、John Reppy和Carl Staelin在论文初稿中提出了有益的建议。
Andrew W. Appel部分受NSF资助资助号为CCR-8806121。Kai Li部分受NSF资助资助号为CCR-8814265并受Intel超级计算机系统部门资助。
