概念

传统存储管理的特征、缺点

• 一次性:作业必须一次性全部装入内存后才能开始运行。这会造成两个问题:①4
  • 作业很大时，不能全部装入内存，导致大作业无法运行;
  • 当大量作业要求运行时，由于内存无法容纳所有作业，因此只有少量作业能运行，导致多道程序并发度下降。
• 驻留性:一旦作业被装入内存，就会一直驻留在内存中，直至作业运行结束。事实上，在一个时间段内，只需要访问作业的一小部分数据即可正常运行，这就导致了内存中会驻留大量的、暂时用不到的数据，浪费了宝贵的内存资源。

局部性原理

回顾局部性原理

虚拟内存的定义和特征

定义

操作系统虚拟性的个体现，实际的物理内存大小没有变，在逻辑上进行了扩充。

虚拟内存的最大容量：

三个特征

• 多次性:无需在作业运行时一次性全部装入内存，而是允许被分成多次调入内存。
• 对换性:在作业运行时无需一直常驻内存，而是允许在作业运行过程中，将作业换入、换出。
• 虚拟性:从逻辑上扩充了内存的容量，使用户看到的内存容量，远大于实际的容量。

如何实现？

虚拟内存技术，允许一个作业分多次调入内存。如果采用连续分配方式，会不方便实现。因此，虚拟内存的实现需要建立在离散分配的内存管理方式基础上。

总结

请求分页管理方式

页表机制

需要解决的2个问题：

• 与基本分页管理相比，请求分页管理中，为了实现“请求调页”，操作系统需要知道每个页面是否已经调入内存;如果还没调入，那么也需要知道该页面在外存中存放的位置。
• 当内存空间不够时，要实现“页面置换”，操作系统需要通过某些指标来决定到底换出哪个页面;有的页面没有被修改过，就不用再浪费时间写回外存。有的页面修改过，就需要将外存中的旧数据覆盖，因此，操作系统也需要记录各个页面是否被修改的信息。

所以将页表添加了几个字段：

缺页中断机构

缺页中断是因为当前执行的指令想要访问的目标页面未调入内存而产生的，因此属于内中断。

一条指令在执行期间，可能产生多次缺页中断。(如: copy A to B，即将逻辑地址A中的数据复制到逻辑地址B，而A、B属于不同的页面，则有可能产生两次中断)

地址变换

请求分页存储管理与基本分页存储管理的主要区别:

• 在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序。

  操作系统要提供请求调页功能，将缺失页面从外存调入内存。

• 若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存。

  操作系统要提供页面置换的功能，将暂时用不到的页面换出外存。

简略过程

详细过程

总结

页面置换算法

最佳置换算法（OPT）

最佳置换算法（OPT，Optimal):每次选择淘汰的页面将是以后永不使用，或者在最长时间内不再被访问的页面，这样可以保证最低的缺页率。

最佳置换算法可以保证最低的缺页率，但实际上，只有在进程执行的过程巴才能知傅按卜米会功回到的是哪个页面。操作系统无法提前预判页面访问序列。因此，最佳置换算法是无法实现的。

例题：

例:假设系统为某进程分配了三个内存块，并考虑到有一下页面号引用串（会依次访问这些页面):7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1

可以发现7号页面是最长被使用的。

可以发现，1号页面最长被使用，所以3号页面置换1号页面。

整个过程缺页中断发生了9次，页面置换发生了6次。

注意:缺页时未必发生页面置换。若还有可用的空闲内存块，就不用进行页面置换。

缺页率=9/20= 45%

先进先出置换算法（FIFO）

先进先出置换算法（FIFO):每次选择淘汰的页面是最早进入内存的页面

实现方法:把调入内存的页面根据调入的先后顺序排成一个队列,需要换出页面时选择队头页面即可。

队列的最大长度取决于系统为进程分配了多少个内存块。

在0页置换时，3页最先进入，所以应该置换3页。

分配4个内存块

Belady异常――当为进程分配的物理块数增大时，缺页次数不减反增的异常现象。

只有FIFO算法会产生Belady异常。另外，FIFO算法虽然实现简单，但是该算法与进程实际运行时的规律不适应，因为先进入的页面也有可能最经常被访问。因此，算法性能差

最近最久未使用置换算法（LRU）

最近最久未使用置换算法（LRU，least recently used):每次淘汰的贝面是最迎茧人木使用的贝回间实现方法:赋予每个页面对应的页表项中，用访问字段记录该页面自上次被访问以来所经历的时间t。

当需要淘汰一个页面时，选择现有页面中t值最大的，即最近最久未使用的页面。

例如：

在手动做题时，若需要淘汰页面，可以逆向检查此时在内存中的几个页面号。在逆向扫描过程中最后一个出现的页号就是要淘汰的页面。

时钟置换算法（ClOCK）

前面算法出现的问题：

• 最佳置换算法性能最好，但无法实现;
• 先进先出置换算法实现简单，但算法性能差;
• 最近最久未使用置换算法性能好，是最接近OPT算法性能的，但是实现起来需要专门的硬件支持，算法开销大。

时钟置换算法是一种性能和开销较均衡的算法，又称CLOCK算法，或最近未用算法（NRU，NotRecently Used)

简单的CLOCK算法实现方法:为每个页面设置一个访问位，再将内存中的页面都通过链接指针链接成一个循环队列。当某页被访问时，其访问位置为1。当需要淘汰一个页面时，只需检查页的访问位。如果是0，就选择该页换出;如果是1，则将它置为0，暂不换出，继续检查下一个页面，若第一轮扫描中所有页面都是1，则将这些页面的访问位依次置为0后，再进行第二轮扫描（第二轮扫描中一定会有访问位为0的页面，因此简单的CLOCK算法选择一个淘汰页面最多会经过两轮扫描)

第一次扫描

第二次扫描1号页为0，那么可以置换一号页

改进型的时钟置换算法

简单的时钟置换算法仅考虑到一个页面最近是否被访问过。事实上，如果被淘汰的页面没有被修改过，就不需要执行I/O操作写回外存。只有被淘汰的页面被修改过时，才需要写回外存。

因此，除了考虑一个页面最近有没有被访问过之外，操作系统还应考虑页面有没有被修改过。在其他条件都相同时，应优先淘汰没有修改过的页面，避免I/0操作。这就是改进型的时钟置换算法的思想。修改位=0，表示页面没有被修改过;修改位=1，表示页面被修改过。
为方便讨论，用(访问位，修改位）的形式表示各页面状态。如（1，1）表示一个页面近期被访问过，且被修改过。

算法规则：

总结

页面分配策略

驻留集

驻留集:指请求分页存储管理中给进程分配的物理块的集合。

在采用了虚拟存储技术的系统中，驻留集大小一般小于进程的总大小。

若驻留集太小，会导致缺页频繁，系统要花大量的时间来处理缺页，实际用于进程推进的时间很少;驻留集太大，又会导致多道程序并发度下降，资源利用率降低。所以应该选择一个合适的驻留集大小。

页面分配，置换策略

四种策略

何时调入页面?

何处调入页面？

1. 系统拥有足够的对换区空间:页面的调入、调出都是在内存与对换区之间进行，这样可以保证页面的调入、调出速度很快。在进程运行前，需将进程相关的数据从文件区复制到对换区。

1. 系统缺少足够的对换区空间:凡是不会被修改的数据都直接从文件区调入，由于这些页面不会被修改，因此换出时不必写回磁盘，下次需要时再从文件区调入即可。对于可能被修改的部分，换出时需写回磁盘对换区，下次需要时再从对换区调入。

1. UNIX方式:运行之前进程有关的数据全部放在文件区，故未使用过的页面，都可从文件区调入。若被使用过的页面需要换出，则写回对换区，下次需要时从对换区调入。

抖动（颠簸）现象

工作集

总结