2.1

虚拟内存的基本概念传统存储管理方式的特征、缺点局部性原理虚拟内存的定义和特征如何实现虚拟内存技术

3.2.2

页面置换算法最佳置换算法OPT先进先出置换算法FIFO最近最久未使用置换算法LRU始终置换算法CLOCK改进型的时钟置换算法

3.2.4

一次性作业必须一次性全部装入内存后才能开始运行。

这回造成两个问题①作业很大时不能全部装入内存导致大作业无法运行②当大量作业要求运行时由于内存无法容纳所有作业因此只有少量作业能运行导致多道程序并发度下降。

驻留性一旦作业被装入内存就会一直驻留在内存中直至作业运行结束。

事实上在一个时间段内只需要访问作业的一小部分数据即可正常运行这就导致了内存中会驻留大量的、暂时用不到的数据浪费了宝贵的内存数据

局部性原理

时间局部性如果执行了程序中的某条指令那么不久后这条指令很多可能再次执行如果某个数据被访问过不久之后该数据很可能再次被访问

空间局部性一旦程序访问了某个存储单元在不久之后其附近的存储单元也很有可能被访问因为很多数据在内存中都是连续存放的并且程序的指令也是顺序地在内存中存放的

基于局部性原理在程序装入时可以将程序中很快会用到的部分装入内存暂时用不到的部分留在外存就可以让程序开始执行

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

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

在操作系统的管理下在用户看来似乎有一个比实际内存大得多的内存这就是虚拟内存

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

多次性无需在作业运行时一次性全部装入内存而是允许被分成多次调入内存

对换性在作业运行时无需一直常驻内存而是允许在作业运行过程中将作业换入、换出

虚拟性从逻辑上扩充了内存的容量使用户看到的内存容量远大于实际的容量

如何实现虚拟内存技术

虚拟内存技术允许一个作业分多次调入内存。

如果采用连续分配方式会不方便实现因此虚拟内存的实现需要建立在离散分配的内存管理方式基础上。

主要区别

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

操作系统要提供请求调页或请求调段功能

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

3.2.2

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

操作系统要提供请求调页功能将缺失页面从外存调入内存操作系统要提供页面置换的功能将暂时用不到的页面换出外存

页表机制

与基本分页管理相比请求分页管理中为了实现“请求调页”操作系统需要知道每个页面是否已经调入内存如果还没调入那么也需要知道该页面在外存中存放的位置。

当内存空间不够时要实现“页面置换”操作系统需要通过某些指标来决定到底换出哪个页面有点页面没有被修改过就不用再浪费时间写回外存。

有的页面修改过就需要将外存中的旧数据覆盖因此操作系统也需要记录各个页面是否被修改的信息

缺页中断机构

在请求分页系统中每当要访问的页面不在内存时便产生了一个缺页中断然后由操作系统的缺页中断处理程序处理中断

此时缺页的进程阻塞放入阻塞队列调页完成后再将其唤醒放回就绪队列

如果内存中有空闲块则为进程分配一个空闲块将所缺页面装入该块并修改页表中相应的页表项

如果内存中没有空闲块则由页面置换算法选择一个页面淘汰若该页面在内存期间被修改过则要将其写回外存。

未修改过的页面不用写回外存。

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

地址变换机构

快表中有的页面一定是在内存中的。

若某个页面被换出外存则快表中的相应表项也要删除否则可能访问错误的页面

找到对应页表项后若对应页面未调入内存则产生缺页中断之后由操作系统的缺页中断处理程序进行处理

3.2.3

每次选择淘汰的页面将是以后永不使用或者在最长时间内不再被访问的页面这样可以保证最低的缺页率

按最佳置换的规则往后寻找最后一个出现的页号就是要淘汰的页面例如2要置换时7是最晚出现的故置换7

注意缺页时未必发生页面置换。

若还有可用的空闲内存块就不用进行页面置换

缺页率缺页发生次数/总共访问多少次页面

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

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

Belady异常

只有FIFO算法会产生Belady异常。

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

因此算法性能差。

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

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

在手动做题时若需要淘汰页面可以逆向检查此时在内存中的几个页面号。

在逆向扫描过程中最后一个出现的页号就是要淘汰的页面。

该算法的实现需要专门的硬件支持虽然算法性能好但是实现困难开销大

始终置换算法CLOCK

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

简单的CLOCK算法实现方法为每个页面设置一个访问位再将内存中的页面都通过链接指针链接成一个循环队列。

当某页被访问时其访问位置为1。

当需要淘汰一个页面时只需检查页的访问位。

如果是0就选择该页换出如果是1则将它置为0暂不换出继续检查下一个页面若第一轮扫描中所有页面都是1则将这些页面的访问位依次置为0后再进行第二轮扫描第二轮扫描中一定会有访问位为0的页面因此简单的CLOCK算法选择一个淘汰页面最多会经过两轮扫描

简答的时钟置换算法仅考虑到一个页面最近是否被访问过。

事实上如果被淘汰的页面没有被修改过就不需要执行I/O操作写回外存。

只有被淘汰的页面被修改过时才需要写回外存。

因此除了考虑一个页面最近有没有被访问过之外操作系统还应考虑页面有没有被修改过。

在其他条件都相同时应优先淘汰没有修过的页面避免I/O操作。

这就是改进型的时钟置换算法的思想。

修改位0表示页面没有被修改过修改位1表示页面被修改过这里采用访问位修改位来表示各页面状态

3.2.4

考虑一个极端情况若某进程共有100个页面则该进程的驻留集大小为100时进程可以全部放入内存运行期间不可能再发生缺页。

若驻留集大小为1则进程运行期间必定会极繁地缺页

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

所以应该选择一个合适的驻留集大小

固定分配操作系统为每个进程分配一组固定数目的物理块在进程运行期间不再改变。

即驻留集大小不变

可变分配先为每个进程分配一定数目的物理块在进程运行期间可根据情况做适当的增加或减少。

即驻留集大小可变

全局置换可以将操作系统保留的空闲物理块分配给缺页进程也可以将别的进程持有的物理块置换到外存再分配给缺页进程。

固定分配局部置换系统为每个进程分配一定数量的物理块在整个运行期间都不改变。

若进程在运行发生缺页则只能从该进程在内存中的页面中选出一页换出然后再调入需要的页面。

这种策略的确定是很难在刚开始就确定应为每个进程分配多少个物理块才算合理。

可变分配全局置换刚开始会为每个进程分配一定数量的物理块。

操作系统会保持一个空闲物理块队列。

当某进程发生缺页时从空闲物理块中取出一块分配给该进程若已无空闲物理块则可选择一个未锁定的页面换出外存再将该物理块分配给缺页的进程。

采用这种策略时只要某进程发生缺页都将获得新的物理块仅当空闲物理块用完时系统才选择一个未锁定的页面调出。

被选择调出的页可能是系统中任何一个进程的页因此这个被选中的进程拥有的物理块会减少缺页率会增加。

可变分配局部置换要根据发生缺页的频率来动态地增加或减少进程的物理块

何时调入页面

预调页策略根据局部性原理一次调入若干个相邻的页面可能比一次调入一个页面更高效。

但如果提前调入的页面中大多数都没被访问过则又是低效。

因此可以预测不久之后可能访问到的页面它们预先调入内存你但目前预测成功率只要50%左右。

故这种策略主要用于进程的首次调入由程序员指出应该先调入哪些部分。

主要指空间局部性即如果当前访问了某个内存单元在之后很有可能会接着访问与其相邻的那些内存单元

该策略主要在运行前调入

请求调页策略进程在运行期间发现缺页时才将所缺页面调入内存。

由这种策略调入的页面一定会被访问到但由于每次只能调入一页而每次调页都要磁盘I/O操作因此I/O开销较大

该策略主要在运行时调入

系统拥有足够的对换区空间页面的调入、调出都是在内存与对换区之间进行这样可以保证页面的调入、调出速度很快。

在进程运行前需将进程相关的数据从文件区复制到对换区

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

对于可能被修改的部分换出时需写回磁盘对换区下次需要时再从对换区调入

UNIX方式运行之前进程有关的数据全部放在文件区故未使用过的页面都可从文件区调入。

若被使用过的页面需要换出则写回对换区下次需要时从对换区调入

抖动颠簸现象

刚刚换出的页面马上又要换入内存刚刚换入的页面马上又要换出外存这种频繁的页面调度行为成为抖动或颠簸。

产生抖动的主要原因是进程频繁访问的页面数目高于可用的物理块数分配给进程的物理块不够

为进程分配的物理块太少会使进程发生抖动现象。

为进程分配的物理块太多又会降低系统整体的并发度降低某些资源的利用率

工作集