[转帖]操作系统-内存管理

内存管理

所有用户进程和系统所需要的全部程序和数据不可能都放入到主存中，操作系统将内存空间进行合理的划分和有效地动态分配，这就是内存管理。

 

内存管理主要需要满足的需求包括；重定位、保护、共享、逻辑组合和物理组织。

 

内存管理的主要功能有：

1. 内存空间的分配与回收：由操作系统完成主存储器空间的分配和管理，
2. 地址转换：在多道程序环境下，程序中的逻辑地址与内存中的物理地址不可能一致，因此存储管理器必须提供地址变换功能，把逻辑地址转换成相应的物理地址。
3. 内存空间的扩充：利用虚拟存储技术或者自动覆盖技术，从逻辑上扩充内存。
4. 存储保护：保证各道作业在各自的存储空间内运行，互不干扰。

基址寄存器和变址寄存器

• 基址寄存器：存储数据内存的起始位置
• 变址寄存器：存储应用程序的长度。

 

物理地址（绝对地址，实地址）

内存中存储单元的地址，可直接寻址。

逻辑地址（相对地址，虚拟地址）

用户程序经过编译、汇编后形成目标代码，目标代码通常采用相对地址的形式，其首地址为0，其余地址都相对于首地址而编址，不能用逻辑地址读取内存中的信息，需转换成物理地址。

 

为了保证CPU执行指令时可正确访问内存单元，需将用户程序中的逻辑地址转换为运行时可由机器直接寻址的物理地址，这一过程称为地址重定位。

静态重定位：当用户程序加载到内存时，一次性实现逻辑地址到物理地址的转换，一般可以由软件完成。

动态重定位：在进程执行过程中进行地址变换，即逐条指令执行时完成地址转换，需要硬件部分支持。

 

覆盖：由于程序运行时并非任何时候都要访问程序及数据的各个部分，因此可以把用户空间分成一个固定去和若干个覆盖区。将经常活跃的部分放在固定去，其余部分按调用关系分段。把即将要访问的段放入覆盖区，其他段放在外存，在需要调用前，再调入覆盖区，替换掉原有的段。

 

交换：把处于等待状态的程序从内存移到辐存，把内存空间腾出来，称之为换出。把准备好的竞争CPU运行的程序从辐存移动到内存，称之为换入。

 

内存保护：内存分配前，需要保护操作系统不受用户进程的影响，保护用户进程不受其他用户进程的影响。

 

页框：内存中一个固定长度的块

 

页：一个固定长度的数据块，存储在二级存储器如磁盘中。数据页可以临时复制到内存的页框中

 

段：一个变长的数据块，存储在二级存储器中。整个段可以临时复制到内存的一个可用区域内，或者可以将一个段分为许多页，将每页单独复制到内存中。

 

内部碎片：已经被分配出去的的内存空间大于请求所需的内存空间。

外部碎片：还没有分配出去，但是由于大小太小而无法分配给申请空间的新进程的内存空间空闲块。

 

内存分区的方法

技术	说明	优点	缺点
固定分区	内存被划分成许多静态分区	简单，开销低	有内部碎片、内存使用不充分，活动进程最大数目是固定的
动态分区	根据进程大小动态创建分区	没有内部碎片，充分利用内存	需要压碎外部碎片，处理器利用率低
简单分页	内存被分为大小相等的页框，每个进程被分成许多大小与页框相等的页，把进程包含的页装入到内存内不一定连续的某些页框中。	没有外部碎片	少量内部碎片
简单分段	每个进程被划分成许多段，要装入一个进程，需要把进程包含的所有段都装入到不一定连续的动态分区中	没有内部碎片，相对于动态分区，提高了内存利用率，减少了开销	存在外部碎片
虚拟内存分页	不需要装入一个进程的所有页，非驻留页在需要的时候自动调入	没有外部碎片，支持更高道数的多道程序设计，巨大的虚拟内存空间	复杂的内存管理开销
虚拟内存分段	不需要装入一个进程的所有段，非驻留段在需要的时候自动调入	没有内部碎片，支持更高道数的多道程序设计，巨大的虚拟内存空间，支持保护和共享	复杂的内存管理开销
虚拟内存段页	用户空间分为段，段划分成固定页，页的长度等于页框大小。	具有两者的优点	复杂性和开销增加。硬件以及占用的内存增加，执行速度下降。

固定分区和动态分区属于连续分配管理方式，为一个用户程序分配一个连续的内存空间。而分页和分段的方法属于非连续分配管理方法，允许一个程序分散地装入到不相邻的内存分区中，存储密度低，但是内存利用率提高。固定分区的内存块大小可以不一致，分页是一致的。

基本内存管理方案

• 整个进程进入内存中一片连续区域
• 单一连续区
• 固定分区
• 可变分区
• 整个进程进入内存中若干不连续的区域
• 页式
• 段式
• 段页式

单一连续区：

一段时间内只有一个进程在内存，简单，内存利用率低

固定分区：

把内存空间分割成若干个区域，称为分区。每个分区的大小可以相同也可以不同，分区大小固定不变。每个分区装一个且只能装一个进程。

可变分区：

根据进程需要，把内存空闲空间分割出一个分区，分配给该进程，剩余部分成为新的空闲区。

 

碎片问题解决

碎片：很小的、不易利用的空闲区，碎片会导致内存利用率下降。

解决方案：紧缩技术，在内存移动程序，将小的空闲区合并为较大的空闲区，又称：压缩技术，紧致技术，搬家技术

物理内存管理（动态分区）

空闲内存管理

位图：内存可能被划分为小到几个字或大到几千字节的分配单元。每个分配单元对应于位图中的一位，0代表空闲，1代表占用（也可以相反）。

空闲块链表

 

 

使用位图的存储管理

图 a 表示一段有 5 个进程和 3 个空闲区的内存，刻度为内存分配单元，阴影区表示空闲（在位图中用 0 表示）；图 b 表示对应的位图；

分配单元的大小是一个重要的设计因素，分配单位越小，位图越大。然而，即使只有 4 字节的分配单元，32 位的内存也仅仅只需要位图中的 1 位。32n 位的内存需要 n 位的位图，所以1 个位图只占用了 1/32 的内存。如果选择更大的内存单元，位图应该要更小。如果进程的大小不是分配单元的整数倍，那么在最后一个分配单元中会有大量的内存被浪费。

位图提供了一种简单的方法在固定大小的内存中跟踪内存的使用情况，因为位图的大小取决于内存和分配单元的大小。这种方法有一个问题是，当决定为把具有 k 个分配单元的进程放入内存时，内容管理器(memory manager) 必须搜索位图，在位图中找出能够运行 k 个连续 0 位的串。在位图中找出制定长度的连续 0 串是一个很耗时的操作，这是位图的缺点。（可以简单理解为在杂乱无章的数组中，找出具有一大长串空闲的数组单元）

使用链表进行管理

维护一个记录已分配内存段和空闲内存段的链表，段会包含进程或者是两个进程的空闲区域。链表中的每一项都可以代表一个 空闲区(H) 或者是进程(P)的起始标志，长度和下一个链表项的位置。

段链表(segment list)是按照地址排序的。这种方式的优点是，当进程终止或被交换时，更新列表很简单。一个终止进程通常有两个邻居（除了内存的顶部和底部外）。相邻的可能是进程也可能是空闲区，它们由四种组合方式。

 

内存分配算法

首次适配（first fit）：在空闲区表中找到第一个满足进程要求的空闲区

下次适配（next fit）：从上次找到的空闲区接着查找

最佳适配（best fit）：查找整个空闲区表，找到能够满足进程要求的最小空闲区

最差适配（worst fit）：总是分配满足进程要求的最大空闲区

 

当按照地址顺序在链表中存放进程和空闲区时，用以上几种算法可以为创建的进程（或者从磁盘中换入的进程）分配内存。我们先假设内存管理器知道应该分配多少内存，最简单的算法是使用 首次适配(first fit)。内存管理器会沿着段列表进行扫描，直到找个一个足够大的空闲区为止。除非空闲区大小和要分配的空间大小一样，否则将空闲区分为两部分，一部分供进程使用；一部分生成新的空闲区。首次适配算法是一种速度很快的算法，因为它会尽可能的搜索链表。

首次适配的一个小的变体是 下次适配(next fit)。它和首次匹配的工作方式相同，只有一个不同之处那就是下次适配在每次找到合适的空闲区时就会记录当时的位置，以便下次寻找空闲区时从上次结束的地方开始搜索，而不是像首次匹配算法那样每次都会从头开始搜索。Bays(1997) 证明了下次算法的性能略低于首次匹配算法。

另外一个著名的并且广泛使用的算法是 最佳适配(best fit)。最佳适配会从头到尾寻找整个链表，找出能够容纳进程的最小空闲区。最佳适配算法会试图找出最接近实际需要的空闲区，以最好的匹配请求和可用空闲区，而不是先一次拆分一个以后可能会用到的大的空闲区。比如现在我们需要一个大小为 2 的块，那么首次匹配算法会把这个块分配在图3-6 c） 位置 5 的空闲区，而最佳适配算法会把该块分配在位置为 18 的空闲区。

那么最佳适配算法的性能如何呢？最佳适配会遍历整个链表，所以最佳适配算法的性能要比首次匹配算法差。但是令人想不到的是，最佳适配算法要比首次匹配和下次匹配算法浪费更多的内存，因为它会产生大量无用的小缓冲区，首次匹配算法生成的空闲区会更大一些。

最佳适配的空闲区会分裂出很多非常小的缓冲区，为了避免这一问题，可以考虑使用 最差适配(worst fit) 算法。即总是分配最大的内存区域（所以你现在明白为什么最佳适配算法会分裂出很多小缓冲区了吧），使新分配的空闲区比较大从而可以继续使用。仿真程序表明最差适配算法也不是一个好主意。

如果为进程和空闲区维护各自独立的链表，那么这四个算法的速度都能得到提高。这样，这四种算法的目标都是为了检查空闲区而不是进程。但这种分配速度的提高的一个不可避免的代价是增加复杂度和减慢内存释放速度，因为必须将一个回收的段从进程链表中删除并插入空闲链表区。

如果进程和空闲区使用不同的链表，那么可以按照大小对空闲区链表排序，以便提高最佳适配算法的速度。在使用最佳适配算法搜索由小到大排列的空闲区链表时，只要找到一个合适的空闲区，则这个空闲区就是能容纳这个作业的最小空闲区，因此是最佳匹配。因为空闲区链表以单链表形式组织，所以不需要进一步搜索。空闲区链表按大小排序时，首次适配算法与最佳适配算法一样快，而下次适配算法在这里毫无意义。

 

另一种分配算法是 快速适配(quick fit) 算法，它为那些常用大小的空闲区维护单独的链表。例如，有一个 n 项的表，该表的第一项是指向大小为 4 KB 的空闲区链表表头指针，第二项是指向大小为 8 KB 的空闲区链表表头指针，第三项是指向大小为 12 KB 的空闲区链表表头指针，以此类推。比如 21 KB 这样的空闲区既可以放在 20 KB 的链表中，也可以放在一个专门存放大小比较特别的空闲区链表中。

快速匹配算法寻找一个指定代销的空闲区也是十分快速的，但它和所有将空闲区按大小排序的方案一样，都有一个共同的缺点，即在一个进程终止或被换出时，寻找它的相邻块并查看是否可以合并的过程都是非常耗时的。如果不进行合并，内存将会很快分裂出大量进程无法利用的小空闲区。

 

交换技术：

处理内存超载方案，在较小的内存空间运行较大的进程。

内存扩充技术

• 内存紧缩技术（例如：可变分区）
• 交换技术
• 覆盖技术
• 虚拟存储技术

覆盖技术：

　　程序执行过程中，程序的不同部分在内存中相互替代，按照其自身的逻辑结构，将那些不会同时执行的程序段共享同一块内存区域，其要求程序各模块之间有明确的调用结构。程序员声明覆盖结构，操作系统完成自动覆盖。覆盖技术主要用于早期的操作系统。

交换技术：

内存空间紧张时，系统将内存中某些进程暂时移到外存，把外存中某些进程换进内存，占据前者所占用的区域（进程在内存与磁盘之间的动态调度）

运行时创建或修改的内容：栈和堆

交换区：一般系统会指定一块特殊的磁盘区域作为交换空间，包含连续的磁道，操作系统可以使用底层的磁盘读写操作对其高效访问。

进程空间增长：

很多程序设计语言都允许从堆中动态地分配内存， 那么当进程空间试图增长时， 就会出现问题。 若该进程与一个空闲区相邻， 那么可把该空闲区分配给该进程让它在这个空闲区增大。 另一方面， 若进程相邻的是另一个进程， 那么要么把需要增长的进程移到内存中一个足够大的区域中去， 要么把一个或多个进程交换出去， 以便生成一个足够大的空闲区。 若一个进程在内存中不能增长， 而且磁盘上的交换区也已满了， 那么这个进程只有挂起直到一些空间空闲（或者可以结束该进程） 。

如果大部分进程在运行时都要增长， 为了减少因内存区域不够而引起的进程交换和移动所产生的开销，一种可用的方法是， 当换入或移动进程时为它分配一些额外的内存。 然而， 当进程被换出到磁盘上时， 应该只交换进程实际上使用的内存中的内容， 将额外的内存交换出去是一种浪费。 在图3-5a中可以看到一种已为两个进程分配了增长空间的内存配置。

 

如果进程有两个可增长的段， 例如， 供变量动态分配和释放的作为堆使用的一个数据段， 以及存放普通局部变量与返回地址的一个堆栈段， 则可使用另一种安排， 如图3-5b所示。 在图中可以看到所示进程的堆栈段在进程所占内存的顶端并向下增长， 紧接在程序段后面的数据段向上增长。 在这两者之间的内存可以供两个段使用。 如果用完了， 进程或者必须移动到足够大的空闲区中（它可以被交换出内存直到内存中有足够的空间） ， 或者结束该进程。

 

虚拟存储技术

虚拟存储技术是指：当进程运行时，先将其一部分装入内存，另一部分暂留在磁盘，当要执行的指令或访问的数据不在内存时，由操作系统自动完成将它们从磁盘调入内存的工作。

虚拟地址空间：分配给进程的虚拟内存

虚拟地址：在虚拟内存中指令或数据的位置，该位置可以被访问。

虚存

虚存：把内存与磁盘有机地结合起来使用，从而得到一个容量很大的内存。虚存是对内存的抽象，构建在存储体系之上，由操作系统协调各存储器的使用，虚存提供了一个比物理内存空间大得多的地址空间。虚拟内存的大小受限于计算机系统的编址方案以及可用辅助存储器的大小，而与主存储器单元的实际数目无关。

地址保护

确保每个进程有独立的地址空间

确保进程访问合法的地址范围

确保进程的操作是合法的

 

虚拟页式

虚拟存储技术+页式存储管理方案=虚拟页式存储管理系统

基本思想：

进程开始运行之前，不是装入全部页面，而是装入一个或两个页面，之后根据进程需要，动态装入其他页面，当内存空间已满，而又需要装入新的页面时，则根据某种算法置换内存中的某个页面，以便装入新的页面。

具体方式：

请求调页、预先调页

 

页式：

用户进程地址空间被划分为大小相等的部分，称为页或页面，从0开始编号

内存空间按同样大小划分为大小相等的区域，称为页框，从0开始编号；也称为物理页面，页帧，内存块

内存分配规则

以页为单位进行分配，并按进程需要的页数来分配；逻辑上相邻的页，物理上不一定相邻。

页面尺寸：4K或4M

逻辑地址：页号+页内地址

 

页表：虚拟地址与物理内存地址之间的映射关系。

32位虚拟地址空间的页表规模

页面大小为4KB，页表项大小为4字节

一个进程地址空间有2^20个页号（32-12（4K的偏移量（2^12=4K））= 20），页号有20位，可以存2^20个页号，页号是页表项的记录条数，而不是页表的页数。

其页表需要占1024页（页表页），页号为2^20个，即页表项有2^20条记录，所以需要2^20*4B大小，除以页面大小4KB，等于2^10=1024页。一个页面1024个页表项，所以查找1024个页面，两级页表结构就可以了，即外层页号和内层页号各占10位，偏移量12位。

 

32位虚拟地址空间的页表规模

页面大小为4KB，页表项大小为8字节

页表规模：32000TB

 

页表页在内存中不连续存放，需要引入页表页的地址索引表，即页目录

 

页表项：记录了逻辑页号和页框号的对应关系。

页表项：

• 页框号：内存块号、物理页面号、页帧号
• 有效位（驻留位、中断位）：表示该页是在内存还是在磁盘
• 访问位：引用位
• 修改位：此页在内存中是否被修改过
• 保护位：读/可读写

通常，页表项是硬件设计的。

每个进程一个页表，存放在内存

地址转换过程：

CPU取到逻辑地址，自动划分为页号和页内地址；用页号查页表，得到页框号，再与页内偏移拼接称为物理地址

 

二级页表结构及地址映射

32位虚拟地址空间由1024个页表页，即页目录由1024条记录，每条记录一个页表，

 

 

反转（倒排）页表

从物理地址空间出发，系统建立一张页表，页表项记录进程i的某虚拟地址（虚页号）与页框号的映射关系。实际内存中的每个页框对应一个表项，而不是每个虚拟页面对应一个表项。采用这种解决方案的有 PowerPC、UltraSPARC 和 Itanium。

虽然倒排页表节省了大量的空间，但是它也有自己的缺陷：那就是从虚拟地址到物理地址的转换会变得很困难。当进程 n 访问虚拟页面 p 时，硬件不能再通过把 p 当作指向页表的一个索引来查找物理页。而是必须搜索整个倒排表来查找某个表项。另外，搜索必须对每一个内存访问操作都执行一次，而不是在发生缺页中断时执行。

 

MMU：内存管理单元

MMU计算物理地址：

虚拟地址8196（二进制是0010000000000100）， 输入的16位虚拟地址被分为4位的页号和12位的偏移量。 4位的页号可以表示16个页面， 12位的偏移可以为一页内的全部4096个字节编址。0010为2，查询页表中2的页框号为110，在与000000000100拼接，

得到110000000000100。

 

快表（TLB）

多级页表需要两次或两次以上的内存访问，CPU的指令处理速度与内存指令的访问速度差异大，CPU的速度等不到充分利用，为了加快地址映射关系，以改善系统性能，引入快表（TLB）。

TLB 其实就是一组相联快速存储，一种内存缓存，用于减少访问内存所需要的时间，它就是 MMU 的一部分，TLB 会将虚拟地址到物理地址的转换存储起来，通常可以称为地址翻译缓存(address-translation cache)。TLB 通常位于 CPU 和 CPU 缓存之间，它与 CPU 缓存是不同的缓存级别。TLB保存正在运行进程的页表的子集（部分页表项）。

如果CPU需要访问某一页首先在TLB里面找，如果TLB里面有就不用访问内存了，因为TLB是寄存器，CPU访问寄存器的速度远大于对内存的访问速度。这样就可以提升时间性能了。那么如何提升命中率的，首先TLB肯定是越大越好，但是TLB材料很贵，不会做得很大。TLB的大小大概是[64,1024]。为什么TLB里面存放这么少的项就能实现“近似访存1次”？因为程序的局部性原理。程序的局部性原理在用户程序里面对应的就是循环。

 

多级页表提高了空间效率，快表提高了时间效率

 

页错误

又称页面错误、页故障、页面失效。是地址转换过程中硬件产生的异常。原因主要有：

• 所访问的虚拟页面没有调入物理内存，即缺页异常
• 页面访问违反权限（读/写、用户/内核）
• 错误的访问地址
• 。。。。

缺页异常

在地址映射过程中，硬件检查页表时发现要访问的页面不在内存，则产生该异常--缺页异常，操作系统执行缺页异常处理程序：获得磁盘地址，启动磁盘，将该页调入内存。如果内存中有空闲页框，则分配一个页框，将新调入页装入，并修改页表中相应页表项的有效位及相应的页框号，若内存中没有空闲页框，则置换内存中某一页框；若该页框内容被修改过，则要将其写会磁盘。

 

驻留集：

给每个进程分配多少页框

固定分配策略：

进程创建时确定，可以根据进程类型（交互、批处理、应用类）或基于程序员或系统管理员的需要来确定

可变分配策略：

根据缺页率评估进程局部性表现，缺页率高，增加页框数，缺页率低，减少页框数。可变分配策略会增加系统的开销。

 

置换范围：

局部置换策略：仅在产生本次缺页的进程的驻留集中选择

全局置换策略：将内存中所有未锁定的页框都作为置换的候选

 

置换策略：

决定置换当前内存中的某一个页框

目标：置换最近最不可能访问的页

约束：不能置换被锁定的页框

 

页框锁定：

通过设置页框的相应锁定位，不让操作系统将进程使用的页面换出内存，避免产生由交换过程带来的不确定的延迟。例如：操作系统核心代码，关键数据结构、I/O缓冲区

 

清除策略：

清除：从进程的驻留集中收回页框

虚拟页式系统工作的最佳状态：发生缺页异常时，系统中有大量的空闲页框。在系统中保存一定数目的空闲页框供给比使用所有内存并在需要时搜索一个页框有更好的性能。

设计一个分页守护进程，多数时间睡眠着，可定期唤醒以检查内存的状态。如果空闲页框过少，分页守护进程通过预定的页面置换算法选择页面换出内存，如果页面装入内存后被修改过，则将它们写回磁盘，分页守护进程可保证所有的空闲页框时是干净的。

 

当进程需要使用一个已置换出的页框时，如果该页框还没有被新的内容覆盖，将它从空闲页框集合中移出即可恢复该页面

页缓冲技术：

不丢弃置换出的页，将它们放入两个表之一：如果未被修改，则放到空闲页链表中，如果修改了，则放到修改链表中。

被修改的页定期写回磁盘（不是一次只写一个，大大减少I/O操作的数量，从而减少了磁盘的访问时间）

被置换的页仍然保留在内存中，一旦进程又要访问该页，可以迅速将它加入该进程的驻留集合（代价很小）

 

页面置换算法

最佳页面置换算法（OPT）

置换以后不在需要的或最远的将来才会用到的页面

在实际情况下很难实现，作为一种标准来衡量其他算法的性能。

先进先出算法

由操作系统维护一个所有在当前内存中的页面的链表，最早进入的放在表头，最新进入的页面放在表尾。在发生缺页异常时，会把头部的页移除并且把新的页添加到表尾。

先进先出算法会产生异常现象（belady现象），即：当分配给进程的物理页面数增加时，缺页次数反而增加。

第二次机会页面置换算法

我们上面学到的 FIFO 链表页面有个缺陷，那就是出链和入链并不会进行 check 检查，这样就会容易把经常使用的页面置换出去，为了避免这一问题，我们对该算法做一个简单的修改：我们检查最老页面的 R 位，如果是 0 ，那么这个页面就是最老的而且没有被使用，那么这个页面就会被立刻换出。如果 R 位是 1，那么就清除此位，此页面会被放在链表的尾部，修改它的装入时间就像刚放进来的一样。然后继续搜索。

 

假设在时间20发生了一次缺页中断， 这时最老的页面是A， 它是在时刻0到达的。 如果A的R位是0， 则将它淘汰出内存， 或者把它写回磁盘（如果它已被修改过） ， 或者只是简单地放弃（如果它是“干净”的） ；另一方面， 如果其R位已经设置了， 则将A放到链表的尾部并且重新设置“装入时间”为当前时刻（20） ， 然后清除R位。 然后从B页面开始继续搜索合适的页面。

 

时钟页面置换算法

上面提到的第二次页面置换算法也是一种比较合理的算法，但它经常要在链表中移动页面，既降低了效率，而且这种算法也不是必须的。一种比较好的方式是把所有的页面都保存在一个类似钟面的环形链表中，一个表针指向最老的页面。

当发生缺页中断时， 算法首先检查表针指向的页面， 如果它的R位是0就淘汰该页面， 并把新的页面插入这个位置， 然后把表针前移一个位置； 如果R位是1就清除R位并把表针前移一个位置， 重复这个过程直到找到了一个R位为0的页面为止。

 

最近未使用页面置换算法

选择在最近一段时间内未使用过的一页并置换

实现：设置页表项的两位，访问位（R）、修改位（M）。

为使操作系统能够收集有用的统计信息， 在大部分具有虚拟内存的计算机中， 系统为每一页面设置了两个状态位。 当页面被访问（读或写） 时设置R位； 当页面（即修改页面） 被写入时设置M位。 这些位包含在页表项中。 每次访问内存时更新这些位， 因此由硬件来设置它们是必要的。 一旦设置某位为1， 它就一直保持1直到操作系统将它复位。

如果硬件没有这些位， 则可以进行以下的软件模拟： 当启动一个进程时， 将其所有的页面都标记为不在内存； 一旦访问任何一个页面就会引发一次缺页中断， 此时操作系统就可以设置R位（在它的内部表格中） ， 修改页表项使其指向正确的页面， 并设为READ ONLY模式， 然后重新启动引起缺页中断的指令； 如果随后对该页面的修改又引发一次缺页中断， 则操作系统设置这个页面的M位并将其改为READ/WRITE模式。

可以用R位和M位来构造一个简单的页面置换算法： 当启动一个进程时， 它的所有页面的两个位都由操作系统设置成0， R位被定期地（比如在每次时钟中断时） 清零， 以区别最近没有被访问的页面和被访问的页面。

当发生缺页中断时， 操作系统检查所有的页面并根据它们当前的R位和M位的值， 把它们分为4类：

第0类： 没有被访问， 没有被修改。

第1类： 没有被访问， 已被修改。

第2类： 已被访问， 没有被修改。

第3类： 已被访问， 已被修改。

尽管第1类初看起来似乎是不可能的， 但是一个第3类的页面在它的R位被时钟中断清零后就成了第1类。 时钟中断不清除M位是因为在决定一个页面是否需要写回磁盘时将用到这个信息。 清除R位而不清除M位产生了第1类页面。

NRU（Not Recently Used， 最近未使用） 算法随机地从类编号最小的非空类中挑选一个页面淘汰之。 这个算法隐含的意思是， 在最近一个时钟滴答中（典型的时间是大约20ms） 淘汰一个没有被访问的已修改页面要比淘汰一个被频繁使用的“干净”页面好。NRU主要优点是易于理解和能够有效地被实现， 虽然它的性能不是最好的， 但是已经够用了。

最近未使用算法也可以用时钟算法实现，

1. 从指针的当前位置开始，扫描页框缓冲区，选择遇到的第一个页框（r=0；m=0）用于置换（本扫描过程中，对使用位不做任何修改）
2. 如果第一步失败，则重新扫描，选择第一个（r=0；m=1）的页框（本次扫描过程中，对每个跳过的页框，将其使用位置为0）
3. 如果第二步失败，指针将回到它的最初位置，并且集合中所有页框的使用位均为0,。重复第一步，并且，有必要，重复第二步。这样将可以找到供置换的页框。

 

最近最少使用页面置换算法

选择最后一次访问时间距离当前时间最长的一页并置换，即置换未使用时间最长的一页。

虽然 LRU 在理论上是可以实现的，但是从长远看来代价比较高。为了完全实现 LRU，会在内存中维护一个所有页面的链表，最频繁使用的页位于表头，最近最少使用的页位于表尾。困难的是在每次内存引用时更新整个链表。在链表中找到一个页面，删除它，然后把它移动到表头是一个非常耗时的操作，即使使用硬件来实现也是一样的费时。

然而，还有其他方法可以通过硬件实现 LRU。让我们首先考虑最简单的方式。这个方法要求硬件有一个 64 位的计数器，它在每条指令执行完成后自动加 1，每个页表必须有一个足够容纳这个计数器值的域。在每次访问内存后，将当前的值保存到被访问页面的页表项中。一旦发生缺页异常，操作系统就检查所有页表项中计数器的值，找到值最小的一个页面，这个页面就是最少使用的页面。

现在让我们看一看第二个硬件实现的LRU算法。 在一个有n个页框的机器中， LRU硬件可以维持一个初值为0的n×n位的矩阵。 当访问到页框k时， 硬件首先把k行的位都设置成1， 再把k列的位都设置成0。 在任何时刻， 二进制数值最小的行就是最近最少使用的， 第二小的行是下一个最近最少使用的， 以此类推。 这个算法的工作过程可以用图3-17所示的实例说明， 该实例中有4个页框， 页面访问次序为：0 1 2 3 2 1 0 3 2 3

访问页面0后的状态如图3-17a所示， 访问页1后的状态如图3-17b所示， 以此类推。

最不经常使用算法（NFU）

选择访问次数最少的页面置换

LRU的一种软件解决方案

实现：

它需要一个软件计数器来和每个页面关联，一页一个，初始化的时候是 0 。在每个时钟中断时，操作系统会浏览内存中的所有页，会将每个页面的 R 位（0 或 1）加到它的计数器上。这个计数器大体上跟踪了各个页面访问的频繁程度。当缺页异常出现时，则置换计数器值最小的页面。

NFU 最主要的问题是它不会忘记任何东西，想一下是不是这样？例如，在一个多次（扫描）的编译器中，在第一遍扫描中频繁使用的页面会在后续的扫描中也有较高的计数。事实上，如果第一次扫描的执行时间恰好是各次扫描中最长的，那么后续遍历的页面的统计次数总会比第一次页面的统计次数小。结果是操作系统将置换有用的页面而不是不再使用的页面。

老化算法（AGING）

改进（模拟LRU）：计数器在加R前先右移一位，R位加到计数器的最左端。

 

图3-18解释了它是如何工作的。 假设在第一个时钟滴答后，页面0到页面5的R位值分别是1、 0、 1、 0、 1、 1（页面0为1， 页面1为0， 页面2为1， 以此类推） 。 换句话说， 在时钟滴答0到时钟滴答1期间， 访问了页0、 2、 4、 5， 它们的R位设置为1， 而其他页面的R位仍然是0。 对应的6个计数器在经过移位并把R位插入其左端后的值如图3-18a所示。 图中后面的4列是在下4个时钟滴答后的6个计数器的值。

发生缺页中断时， 将置换计数器值最小的页面。 如果一个页面在前面4个时钟滴答中都没有访问过， 那么它的计数器最前面应该有4个连续的0， 因此它的值肯定要比在前面三个时钟滴答中都没有被访问过的页面的计数器值小。

该算法与LRU有两个区别。 如图3-18e中的页面3和页面5， 它们都连续两个时钟滴答没有被访问过了，而在两个时钟滴答之前的时钟滴答中它们都被访问过。 根据LRU， 如果必须置换一个页面， 则应该在这两个页面中选择一个。 然而现在的问题是， 我们不知道在时钟滴答1到时钟滴答2期间它们中的哪一个页面是后被访问到的。 因为在每个时钟滴答中只记录了一位， 所以无法区分在一个时钟滴答中哪个页面在较早的时间被访问以及哪个页面在较晚的时间被访问， 因此， 我们所能做的就是置换页面3， 原因是页面5在更往前的两个时钟滴答中也被访问过而页面3没有。

LRU和老化算法的第二个区别是老化算法的计数器只有有限位数（本例中是8位） ， 这就限制了其对以往页面的记录。 如果两个页面的计数器都是0， 我们只能在两个页面中随机选一个进行置换。 实际上， 有可能其中一个页面上次被访问是在9个时钟滴答以前， 另一个页面是在1000个时钟滴答以前， 而我们却无法看到这些。 在实践中， 如果时钟滴答是20ms， 8位一般是够用的。 假如一个页面已经有160ms没有被访问过，那么它很可能并不重要。

 

CPU正在以某个频率前进，该频率的周期称为时钟滴答或时钟周期。一个 100Mhz 的处理器每秒将接收100,000,000个时钟滴答。

 

影响缺页次数的因素

• 页面置换算法
• 页面本身的大小
• 程序的编制方法
• 分配给进程的页框数量

颠簸（抖动）

虚存中，页面在内存与磁盘之间频繁调度，使得调度页面所需的时间比进程实际运行的时间还多，这样导致系统效率急剧下降，这种现象称为颠簸或抖动。

 

页面尺寸问题

确定页面大小对于分页的硬件设计非常重要，而对于操作系统是个可选的参数

要考虑的因素：

• 内部碎片
• 页表长度
• 辅存的物理特性

多种页面尺寸：为有效使用TLB带来灵活性，但给操作系统带来复杂性。

 

分配给进程的页框数与缺页率的关系

 

工作集模型

由Denning提出（1968）

基本思想：

根据程序的局部性原理，一般情况下，进程在一段时间内总是集中访问一些页面，这些页面称为活跃页面，如果分配给一个进程的物理页面数太少了，使该进程所需的活跃页面不能完全装入内存，则进程在运行过程中将频繁发送中断。

如果能为进程提供与活跃页面数相等的物理页面数，则可减少缺页中断次数。

工作集

工作集：一个进程当前正在使用的页框集合

工作集w=该进程在过去的△个虚拟时间单位中访问到的页面集合

内容取决于三个因素：

• 访页序列特性
• 时刻t
• 工作集窗口长度（△）窗口越大，工作集越大

工作集算法

基本思路：找出一个不在工作集中的页面并置换

思路：

• 每个页表项中有一个字段：记录该页面最后一次被访问的时间
• 设置一个时间值T
• 根据一个页面的访问时间是否落在“当前时间-T”之前或之中决定其在工作集之外还是之内。

实现：

扫描所有页表项，执行操作

• 如果一个页面的R位是1，则将该页面的最后一次访问时间设为当前时间，将R位清零
• 如果一个页面的R位是0，则检查该页面的访问时间是否在“当前时间-T”之前，如果是，则该页面为被置换的页面；如果不是，记录当前所有被扫描过页面的最后访问时间里面的最小值。扫描下一个页面并重复1,2。

 

工作集时钟页面置换算法

　　当缺页异常发生后，需要扫描整个页表才能确定被淘汰的页面，因此基本工作集算法还是比较浪费时间的。一个对基本工作集算法的提升是基于时钟算法但是却使用工作集的信息，这种算法称为WSClock(工作集时钟)。由于它的实现简单并且具有高性能，因此在实践中被广泛应用。与时钟算法一样， 所需的数据结构是一个以页框为元素的循环表。 最初， 该表是空的。当装入第一个页面后， 把它加到该表中。 随着更多的页面的加入， 它们形成一个环。 每个表项包含来自基本工作集算法的上次使用时间， 以及R位（已标明） 和M位（未标明） 。

 

　　与时钟算法一样， 每次缺页中断时， 首先检查指针指向的页面。 如果R位被置为1， 该页面在当前时钟滴答中就被使用过， 那么该页面就不适合被淘汰。 然后把该页面的R位置为0， 指针指向下一个页面， 并重复该算法。 该事件序列之后的状态参见图3-21b。

现在来考虑指针指向的页面在R=0时会发生什么， 参见图3-21c。 如果页面的生存时间大于τ并且该页面是干净的， 它就不在工作集中， 并且在磁盘上有一个有效的副本。 申请此页框， 并把新页面放在其中， 如图3-21d所示。 另一方面， 如果此页面被修改过， 就不能立即申请页框， 因为这个页面在磁盘上没有有效的副本。 为了避免由于调度写磁盘操作引起的进程切换， 指针继续向前走， 算法继续对下一个页面进行操作。 毕竟， 有可能存在一个旧的且干净的页面可以立即使用。

　　原则上， 所有的页面都有可能因为磁盘I/O在某个时钟周期被调度。 为了降低磁盘阻塞， 需要设置一个限制， 即最大只允许写回n个页面。 一旦达到该限制， 就不允许调度新的写操作。

　　如果指针经过一圈返回它的起始点会发生什么呢？ 这里有两种情况：

　　1)至少调度了一次写操作。

　　2)没有调度过写操作。

　　对于第一种情况， 指针仅仅是不停地移动， 寻找一个干净页面。 既然已经调度了一个或者多个写操作，最终会有某个写操作完成， 它的页面会被标记为干净。 置换遇到的第一个干净页面， 这个页面不一定是第一个被调度写操作的页面， 因为硬盘驱动程序为了优化性能可能已经把写操作重排序了。

　　对于第二种情况， 所有的页面都在工作集中， 否则将至少调度了一个写操作。 由于缺乏额外的信息， 一个简单的方法就是随便置换一个干净的页面来使用， 扫描中需要记录干净页面的位置。 如果不存在干净页

面， 就选定当前页面并把它写回磁盘。

 

页面置换算法小结

算法	评价
OPT（最优算法）	不可实现，但可作为基准
NRU（最近未使用）	LRU的很粗糙的近似
FIFO（先进先出）	可能置换出重要的页面
第二次机会算法	比FIFO有很大的改善
时钟算法	现实的
LRU （最近最少）	很优秀，但很难实现
NFU（最不经常使用）	LRU的相对粗略的近似
AGING（老化算法）	非常近似LRU的有效算法
WORKING SET（工作集算法）	实现起来开销很大
WSClock（工作集时钟算法）	比较有效的算法

• 最优算法在当前页面中置换最后要访问的页面。不幸的是，没有办法来判定哪个页面是最后一个要访问的，因此实际上该算法不能使用。然而，它可以作为衡量其他算法的标准。
• NRU 算法根据 R 位和 M 位的状态将页面氛围四类。从编号最小的类别中随机选择一个页面。NRU 算法易于实现，但是性能不是很好。存在更好的算法。
• FIFO 会跟踪页面加载进入内存中的顺序，并把页面放入一个链表中。有可能删除存在时间最长但是还在使用的页面，因此这个算法也不是一个很好的选择。
• 第二次机会算法是对 FIFO 的一个修改，它会在删除页面之前检查这个页面是否仍在使用。如果页面正在使用，就会进行保留。这个改进大大提高了性能。
• 时钟 算法是第二次机会算法的另外一种实现形式，时钟算法和第二次算法的性能差不多，但是会花费更少的时间来执行算法。
• LRU 算法是一个非常优秀的算法，但是没有特殊的硬件(TLB)很难实现。如果没有硬件，就不能使用 LRU 算法。
• NFU 算法是一种近似于 LRU 的算法，它的性能不是非常好。
• 老化 算法是一种更接近 LRU 算法的实现，并且可以更好的实现，因此是一个很好的选择
• 最后两种算法都使用了工作集算法。工作集算法提供了合理的性能开销，但是它的实现比较复杂。WSClock  是另外一种变体，它不仅能够提供良好的性能，而且可以高效地实现。

 

总之，最好的算法是老化算法和WSClock算法。他们分别是基于 LRU 和工作集算法。他们都具有良好的性能并且能够被有效的实现。还存在其他一些好的算法，但实际上这两个可能是最重要的。

 

段式：

用户进程地址空间：按程序自身的逻辑关系划分为若干个程序段，每个程序段都有一个段名。

内存空间被动态划分为若干长度不相同的区域，称为物理段，每个物理段由起始地址和长度确定。

内存分配规则：以段为单位进行分配，每段在内存中占据连续空间，但各段之间可以不相同。

逻辑地址：段号+段内地址

段表：

段表项：记录段号，段首地址和段长度之间的关系

每个进程一个段表，存放在内存

地址转换过程：

CPU取到逻辑地址，划分为段号和段内地址，用段号查段表，得到该段在内存的起始地址，与段内偏移地址计算出物理地址。

段页式：

综合段式和页式方案的优点。

用户进程划分：先按段划分，每一段在按页面划分。

逻辑地址：

 

内存划分：同页式存储管理方案

内存分配：以页为单位进行分配

段表：记录了每一段的页表始址和页表长度

页表：记录了逻辑页号与页框号的对应关系，每一段有一张页表，一个进程由多个页表

空闲区管理：同页式管理

内存分配、回收：同页式管理

地址转换过程：

CPU取到逻辑地址，划分为段号和段内地址，用段号查段表，得到页表的起始地址和长度，段内地址划分成页号和页内地址，用页号查页表，得到页框号，再与页内偏移拼接称为物理地址。

 

内存映射文件

基本思想

进程通过一个系统调用将一个文件（或部分）映射到其虚拟地址空间的一部分，访问这个文件就像访问内存中的一个大数组，而不是对文件进行读写

在多数实现中，在映射共享的页面时不会实际读入页面的内容，而是在访问页面时，页面才会被每次一页的读入，磁盘文件则被当做后备存储

当进程退出或者显示地解除文件映射时，所有被修改页面会写回文件

 

写时复制

例如：两个进程共享三个页面，每页都标记成写时复制，当其中一个进程试图改变页面2的数据后，会复制出一个新的页面，新复制的页面对执行写操作的进程时私有的，对其他共享写时复制页面的进程时不可见的。