内存管理分页技术

内存管理分页技术，（简称：分页）(Paging)是一种内存管理方案，是将进程以页的形式从辅助内存中检索到主存中的过程，不需要连续分配物理内存，将每个进程划分为页。分页的主要思想是将主存的虚拟(逻辑)地址空间和真实(物理)地址空间划分成容量和大小相等的页，使所有地址都可以用页号拼接页内地址的形式表示。

在计算机操作系统中，连续分配的算法阻碍了存储管理方案的设计，造成了大量的内存碎片，因此需要考虑非连续分配的算法，分页管理就是其中最具代表性的一种。1959年，亚多拉斯系统被开发出来，使用分页将虚拟地址映射到主存，并于1962年投入使用。1969年，IBM的研究人员证明了虚拟内存覆盖系统比早期的手动系统工作得更好。在20世纪70年代，大型机和小型计算机通常使用虚拟内存。1982年Intel在80286处理器的保护模式下引入了虚拟内存，1985年80386出来的时候引入了分页支持。

分页存储管理将内存空间分成若干大小相等、位置固定的小分区，每个小分区称为一个存储块，依次编号。每个存储块的大小由不同的系统决定，一般是2的n次方。分页提高了内存管理的效率，进而提高了系统性能和响应能力。但是在页面存储下，程序的模块化较差，需要占用大量的存储空间。

早期操作系统采用的连续分配管理模式，要求分配给进程的物理空间必须是连续的，这是产生大量碎片的主要原因，所以一直考虑非连续分配算法。在分页技术出现之前，内存管理方案偶尔会使用覆盖技术。它只需要将CPU当前需要的指令和数据保存在内存中，以维持计算机系统的运行。当需要其他指令、数据或程序段时，只需将它们加载到不再需要的指令所占用的内存空间中。

分页管理是不连续分配管理中具有代表性的算法，它要求将物理内存空间划分成固定大小的块，分页技术不会产生外部碎片。分页技术的具体应用可以追溯到一个早期的重要系统Atlas，它是在1959年开发的，使用分页将虚拟地址映射到主存，并于1962年投入使用。1969年，IBM的研究人员证明了虚拟内存覆盖系统比早期的手动系统工作得更好。在20世纪70年代，大型机和小型计算机通常使用虚拟内存。1982年Intel在80286处理器的保护模式下引入了虚拟内存，1985年80386出来的时候引入了分页支持。

随着分页技术的不断成熟，它已经成为一种关键的内存管理技术，用于实现计算机操作系统中的虚拟内存管理方法，提供进程间的内存保护和隔离。后来随着硬件技术的发展，Intel在1985年推出了Intel 80386微处理器，开启了处理器内置分页机制的时代。

为了降低分页机制的缺页率，提高虚拟内存的性能，相关技术人员开发了许多页面替换算法，包括最优替换算法、先进先出替换算法、最近未使用替换算法等页面替换算法。20世纪10年代，云计算开始出现。是计算服务的分发，虚拟化是云计算的基础，通过制作虚拟镜像，有助于共享系统资源。分页作为一种内存管理技术，也应用于云计算，读写数据到硬盘。

分页的主要思想是将主存的虚拟(逻辑)地址空间和真实(物理)地址空间划分成容量和大小相等的页面，使所有地址都可以用页号拼接页内地址的形式表示，按页分配主存的存储管理方式称为页管理。

系统中通常有一个地址翻译机制，将程序在地址空间中的逻辑地址翻译成在内存空间中的物理地址，实现它们之间的重定位。当访问和操作一个进程的逻辑地址时，地址翻译机制自动将有效逻辑地址根据页面大小分为两部分:页码和页内位移。逻辑地址除以页面长度得到的商和余数分别是逻辑页码和页内位移。

在分页中，物理内存被划分为固定大小的块，称为页帧，其大小与进程使用的页面大小相同。进程的逻辑地址空间也分为固定大小的块，称为页面，其大小与页框相同。当进程请求内存时，操作系统将为该进程分配一个或多个页框，并将该进程的逻辑页映射到物理页框。逻辑页面和物理页面帧之间的映射由页面表维护，内存管理单元使用该页面表将逻辑地址转换为物理地址。页表将每个逻辑页号映射到物理页框号。

分页技术提高了主存的利用率，有利于多程序运行，可以增加ram(随机存取存储器)或期望分页的数量，提高RAM读取的命中率来提高系统性能，还可以通过减少CPU等待从磁盘加载页面的时间来提高性能。

多级页面表：多级页表可以去除页表中的无效区域，对页表进行索引。采用分页存储管理模式时，页表会占用相当大的内存空间。因为很难找到足够的内存空间来存储页表，所以也可以将页表分成若干页并进行编号，这样就可以将每一页离散地存储在不同的物理块中。为了管理这些页表，需要建立另一个页表，称为外页表，也就是页表的索引表。外部页表的每个页表条目记录页表页的物理块号。

对于32位机器，采用两级页表结构是合适的，但对于64位机器，则需要采用多级页表，对外层页表进行分页，然后将每个页离散地分布到不相连的物理块中，再用二级页表映射它们的关系。

散列页表：哈希页表是操作系统用来有效管理虚拟和物理内存地址之间的内存映射的数据结构。与传统的页表相比，搜索速度更快，只存储当前使用的页面的条目就可以减小页表的大小。

使用以逻辑页号作为哈希值的哈希页表。在哈希页表中，每个页表项都包含一个链表，链表中元素的哈希值都指向同一个位置，哈希值相同的元素使用队列处理冲突。哈希页表的地址转换过程是根据逻辑页号找到哈希值，并将这个页号与链表中第一个元素的字段进行比较。如果匹配，则将对应的物理块号和位移拼接形成物理地址；如果不匹配，则沿着链表依次搜索匹配的页表项。

倒页表：传统的页表和哈希页表包含数百万个页表项，会消耗大量的内存空间。所以引入了倒排页表，按物理地址排序。每个物理块都有一个条目，每个条目包含物理块中存储的页面的逻辑地址和拥有该页面的进程的信息。当使用倒排页表进行地址转换时，将根据进程标识符和页码检索倒排页表。如果检索到匹配的页表项，则页表项的序列号(中间的)是该页的物理块号，它可以与页中的地址一起用于形成物理地址，并将其发送到存储器地址寄存器。如果搜索了整个倒排页表，但没有找到匹配的页表条目，则意味着该页还没有被加载到内存中。

请求页面调度：在按需分页中，操作系统仅在程序运行时将程序的必要页面加载到内存中。当程序启动时，它首先不会将任何页面加载到内存中。当程序访问当前不在内存中的页面时，会发生页面错误，然后操作系统将所需的页面从磁盘加载到内存中，并相应地更新页面表。

高级分页：预分页将所有页面加载到内存中，当进程实际引用这些页面时，它们将被一起调用，因此加载到主存中的页面可能会被使用，也可能不会被使用。预分页是用来在进程开始的时候尽量减少大量的页面错误，但是会有资源的浪费。

分段分页：段-页管理模式是将进程的逻辑地址空间分段，建立段表，实现分段模式下的地址翻译，然后对每个段进行分页建立页表，实现分页模式下的地址翻译。大多数CPU都采用这种思路，比如Intel CPU的Intel 80386架构。

命中缺页：当CPU试图从主内存中获取所需的页面，并且该页面存在于主内存(RAM)中时，这被称为“页面命中”，当页面丢失时，就会发生“未命中”。当进程试图访问物理内存中不存在的页面时，就会发生页面错误。页面出错的原因有三:一是页面从未被加载到内存中；第二，页面已经从内存中删除；第三，页面在内存中被修改，需要写回磁盘。

操作系统使用分页方法或终止进程来处理页面错误。如果该页不重要或者程序不在临界区，则终止程序，或者将未使用的页移到辅助存储器，并将导致页面错误的页引入主存储器。此外，通过使用适合当前需求并最大化页面命中率的适当页面替换算法，可以减轻页面错误对性能的影响。

缺页率：缺页率是指一定时间内缺页中断次数与页面趋势次数的比值。缺页中断是影响程序性能的一个重要指标。系统在处理缺页中断时会产生大量的开销。通常，缺页率越低，系统的性能就越高。缺页率计算过程举例:采用最优替换算法，假设系统给一个进程分配三个物理块，进程运行时的页面走向为:4，3，2，1，4，3，5，4，3，2，3，5，三个物理块一开始都是空闲的。

页面替换：页面替换是当一个页面由于缺页而中断时所采用的策略。页面替换算法可以选择换出页面，并将内存中的页面换出到外部存储器。常用的页面替换算法包括OPT、FIFO、LRU等页面替换算法。

最佳置换算法：最好的替换算法是从存储器中选择不再被访问的页面或者在最长时间之后需要被访问的页面来消除。这种算法很难实现，因为很难准确预测页面访问的未来顺序，但可以用来评估其他算法的优劣。

先进先出排列算法：先进先出替换算法总是选择在内存中停留时间最长的页面进行淘汰，即先进入内存的页面先退出内存。这个算法很容易实现，但是没有考虑到缓存页面被使用的情况，会有一个频繁访问的页面会被清除出缓存。最近一段时间内最长时间未被访问的页面由最长时间替换算法选择以被消除。这种算法的性能接近最佳算法，但实现起来比较困难。它需要花费巨大的系统开销来找出最长时间没有使用的页面，为每个页面设置相关记录，记录页面访问情况。

其他页面替换算法

第二次机会算法：第二次机会算法是先进先出算法的改进，以避免消除频繁使用的页面。它与页表中的“参考位”相结合。算法的实现思想是:在选择一个页面替换时，先检查先入先出页面队列中队列的第一页。如果其“参考位”为0，则消除该页面。如果为1，则将它的“参考位”清除为0。

简单时钟算法：简单时钟算法是二次机会算法的改进，也是LRU算法的近似。该算法要求为每个页面设置一个访问位，并将内存中的所有页面链接到一个循环队列中。当访问页面时，系统将其访问位设置为1。替换时，使用指针从当前指针位置开始按顺序检查页面。如果访问位为0，则选择要替换的页面。如果访问位为1，则其被设置为0，并且重复该过程，直到找到具有0的参考页面的页面。最后，指针停留在被替换页面的下一页。

在计算机操作系统中，内存分配策略包括固定分配和可变分配，在替换页面时也可以采用两种策略，即全局替换和局部替换。全局替换允许一个进程从所有内存物理块的集合中选择过时对象，而局部替换规定每个进程只能从分配给它的物理块中选择过时对象。

固定分配：固定分配是一种持续的内存管理技术，在这种技术中，主内存被划分为固定大小的分区(分区大小可以相等，也可以不相等)。当需要分配进程内存时，会找到一个足够大的空闲分区来容纳该进程。然后将内存分配给该进程。如果没有空闲空间，进程就在队列中等待分配内存。

可变分配：变量分配也是一种连续内存管理技术，在这种技术中，不会将主内存划分为分区，而是将足够大的可用内存块分配给进程。剩余的空间被视为可用空间，可以被其他进程进一步使用。它还提供了压缩的概念。在压缩中，空闲空间和未分配给进程的空间组合在一起，形成一个大的内存空间。

保护：分页技术为进程间的内存提供保护和隔离。通过为每个进程分配一个独立的虚拟地址空间和页表，保证了进程只能访问自己的存储空间。每个逻辑地址访问都通过硬件地址转换机制映射到进程的物理地址空间。这样，所有的进程活动都被限制在它们自己的内存空间中。确保一个进程不能访问或修改另一个进程的内存。

分享：操作系统中有许多程序和数据由多个作业共享。内存中的每个进程在调用它们之前，必须将这些共享的程序和数据放入自己的地址空间。在共享内存中，内存的一部分被映射到一个或多个进程的地址空间，操作系统在这个内存段中读写。要实现信息共享，需要解决共享信息的保护问题，可以通过在页表中增加一个标志位来表示该页的信息只读/读写/可执行状态，并在进程访问该页时检查访问方式来实现。重入技术也是一种实现共享的技术，支持内存的高效使用。共享程序的副本只留在内存中，其他共享者用指针连接，帮助系统解决多任务共享同一个程序的问题。

优势：空间利用率高:进程不需要占用内存中连续的空间，减少了内存碎片，提高了主存的空间利用率。每个程序最多浪费不到一页的内存空间。

页表结构简单:与段表相比，页表结构更简单，字段更少，可以有效节省页表所需的存储空间。

快速地址转换:地址转换只需要建立虚拟页号和实际页号的映射关系，简化了用户程序加载到主存的过程，加快了地址转换的速度。

辅助存储管理的简化:页的大小通常是512字节的整数倍，现代存储系统中常见的页的大小范围是1KB到16KB，简化了辅助存储的管理。

劣势：程序的模块化较差:在页面存储管理下，用户程序被划分为固定大小的页面，程序段的实际长度不固定，因此一个页面可能只是一个程序段的一部分，也可能在一个页面中包含两个或两个以上的程序段，不能代表一个完整的程序段功能。内存空间占用大:页表的长度也比较长，需要占用很大的存储空间。通常，虚拟内存的每一页都在页表中占据一个存储字。如果分页虚拟内存的虚拟空间为4GB，每页的大小为1KB，则页数为4M，页表的容量为4M存储字。

影响因素：分页系统的性能取决于各种因素，包括页大小、页表大小、页替换算法和页表组织。

内存管理分页技术

页面大小:页面大小越大，需要的页表就越少，这可能会导致更快的内存访问时间。但是，较大的页面大小也会导致内部碎片，并且会由于进程的实际大小与页面大小之间的差异而浪费内存。

页面替换算法:分页的性能取决于所使用的页面替换算法，算法的选择会影响页面出错的次数和访问页面所需的时间；用于将虚拟地址映射到物理地址的页表大小将影响存储器访问速度。页表越大，内存访问时间越慢。

页表大小:页表的组织也会影响分页的性能。例如，分层页表可以减小页表的大小，提高内存访问速度。

系统颠簸:系统颠簸也会影响计算机系统的性能，是由于频繁的页面调度活动导致系统效率大大降低的现象。Bump在大多数情况下会使系统处于等待状态，进程被频繁访问、调入和淘汰，会耗费大量的系统开销，降低系统的性能。

这种现象可以通过添加性能分析和调整软件，持续监控执行任务的缺页情况，并动态调整它们的页面分配，增加分配给那些产生大量缺页的任务的可用页面来解决。

翻译后备缓冲区(TLB)：为了解决由于进程存储器太大而导致寄存器可能无法容纳所有页表条目的问题，为页表条目设置了一个称为翻译后备缓冲器(TLB)的高速缓存，以跟踪最近使用的事务。当进行进程调用时，TLB首先检查该页是否已经在主存中，如果不在主存中，它发出一个页错误，然后更新TLB以包含一个新的页条目。

软件干预：通过添加性能分析和调整软件，我们可以持续监控执行任务的缺页情况，并动态调整它们的页面分配。对于那些产生大量缺页的任务，我们可以增加分配给它们的可用页面来解决系统颠簸现象。