第九章 虚拟存储器管理1、虚拟存储系统的基本概念 2、分页存储管理 3、分段存储管理 4、段页式存储管理 5、页（段）的置换算法和系统行为 6、页架分配算法9.1 虚拟存储系统的基本概念1、问题的提出 程序大于内存 程序暂时不执行或运行完是否还要占 用内存2、基本思想程序、数据的大小可以超过内存的大小 ，操作系统把程序当前使用的部分保留 在主存，而把其它部分保存在辅存中， 并在需要时在主存和辅存之间动态交换 。 把辅存当作主存进行扩充，对用户来说 ，计算机系统有一个容量很大的主存。虚存的优点：可容纳大量的进程，提高系统多道并行 程度，提高主存和其他资源的利用率， 提高系统运行效率和系统吞吐率虚存的缺点：（1）额外的主存开销（2）地址转换增加了指令执行时间9.2 分页存储管理 基本概念 地址转换 硬件支持 页的共享一、分页存储管理的基本概念 等分主存：页架、页架号 用户逻辑地址空间的分页：页、页号 逻辑地址的表示：（页号p,页内地址d） 分配原则：以页架为基本分配单位 页表：页号、页架号 分页系统中的地址结构： 页号最大页数 页内地址页架的大小 页面尺寸应是2的幂基本工作原理在程序开始运行之前，不是装入全部 页面，而是装入一个或零个页面，之 后根据程序运行的需要，动态装入其 它页面；当内存空间已满，而又需要 装入新的页面时，则根据某种算法淘 汰某个页面，以便装入新的页面X X X X 7 X 5 X X X 3 4 0 6 1 260K-64K56K-60K 52K-56K48K-52K 44K-48K 40K-44K 36K-40K 32K-36K28K-32K24K-28K 20K-24K16K-20K 12K-16K8K-12K4K-8K0K-4K28K-32K24K-28K 20K-24K16K-20K 12K-16K8K-12K4K-8K0K-4K虚地址空间物理地址空间 虚页页架二、分页系统中的地址转换 直接映象页地址转换 多级页表地址转换 快表的地址转换1、直接映象页地址转换Pdp+L bp dP页表页表地址寄存器虚地址v=(p,d)实地址b0010000000000100110000000000100110在/不在内存页表虚地址 8196物理地址 24580000015 000014 000013 000012 111111 000010 1011 9 0000 8 0000 7 0000 6 0111 5 1001 4 0001 3 1101 2 0011 1 0101 0 页号 页架号 状态2、多级页表地址转换解决页表非常大的问题 访存次数增加，增加一级页表，增加一次 访存次数。3、快表的地址转换页号 页内地址页号 页架号 页架号 页内地址虚地址物理地址快表p页表地址越界l比较 P=1pp . . .快表b+页号p 页内地址dPd物理地址页表地址寄存器页表长度寄存器逻辑地址举例如果查找快表花费的时间是50NS，访问内 存的时间是750NS，试计算命中率为80%， 90%时实际的访存时间。页号在快表：存取时间为50+750=800NS页号在慢表：存取时间为750+750=1500NS命中率为80% 存取时间为0.8*800+0.2*1500=940NS命中率为90% 存取时间为0.9*800+0.1*1500=870NS三、硬件支持 主存管理单元MMU 页表 快表 反向页表1、主存管理单元MMU 页表地址寄存器：页表始址，长度 虚地址分成虚页号和页内地址 判断有越界访问和保护性错误页表中 有效位保护权限2、页表实现页式管理重要的数据结构 内容：页架号修改位有效位引用位保护权限3、快表为加快地址转换而使用高速缓存 内容：页号页架号保护权限4、反向页表完成物理页架号到虚地址的映射 内容：虚页号物理页架号指向哈希链的下一项指针有效位，修改位，引用位保护和加锁信息9.3 分段存储管理 基本概念 地址转换一、分段存储管理的基本概念 进程的逻辑地址空间：段、段号 程序的地址结构：（段号s、段内地址w） 段号最多段数段内地址最大段长 主存分配：以段为单位 段表和段表寄存器 段表：段号、段的长度、段在主存中的起始地 址、段的状态位、访问位、修改位、段的外存 地址 段表寄存器：段表起始地址、段表长度段的动态链接在程序开始运行时，只将主程序段装 配好并调入内存，其它各段的装配是 在主程序段的运行过程中逐步完成。 每当需要调用一个新段时，再将这个 新段装配好，并与主程序段链接。二、分段存储管理地址转换段表长 段表地址段号 段内地址+段表SlL bS w b s+实地址段表地址寄存器 虚地址Cl Cb+段号S 段内地址d比较比较b + d段表S= Cl 快表物理地址段表始址寄存器段表长度寄存器逻辑地址lb.Slb地址越界 d=1d=1地址映射及存储保护机制地址越界地址越界比较举例段长 段起始地址 有效位0 200 500 1 1 400 1000 1 2 100 1400 0 3 900 2000 1 虚地址：（2，250）,（4，470）完成实地址转换1. 缺段中断2. 越界三、存储保护问题 越界保护 存取控制保护四、分段存储管理的优缺点 优点： 便于处理变化的数 据结构 便于共享 提供虚存的功能 提供动态连接的便 利 便于控制存取访问 缺点： 要为存储紧缩付出处 理机机时的代价 分段的最大尺寸受到 主存大小的限制 在外存中管理可变尺 寸的分段比较困难 与分页一样，提高了 硬件成本9.4 段页式存储管理 基本概念 地址转换 存储管理算法 优缺点一、段页式存储管理的基本概念 等分主存：页架、页架号 进程的地址空间采用分段的方式 每一段采用分页的方法 逻辑地址结构：（s,p,d） 主存分配：以页为单位非连续分配 数据结构：段表、页表、段表地址寄存器段号段内地址页号页内地址二、段页式管理的地址转换段表地址寄存器段号S 页号P 页内地址dSSPP页架号 d b s+L b 虚地址实地址S P P段表 页表快表快表的内容段号 虚页号 页架号 保护信息 AGE 有效位三、段页式存储管理算法9.5 页的置换算法 页面访问失效及处理 页面置换算法一、页面访问失效及处理引起失效的原因： 边界错误纯分页：页号超过页表长度纯分段：偏移量超过段长，段号超过段表长度段页式：页号超过该段的页表长度 有效性错误：缺页或缺段中断 保护错误：访问权限错误二、页面置换算法 最佳置换算法OPT 先进先出置换算法FIFO 最近最少使用置换算法LRU 最近未使用置换算法NUR 两次机会置换算法 时钟页面置换算法CLOCK1、最佳置换算法OPT原则：淘汰将来再也不被访问，或者是在最远的将来才被访问的页。举例如果页面的引用顺序为2，3，2，1，5，2 ， 4，5，3，2，5，2，而分配给它们内存页 架数为3，用OPT计算它的缺页次数。2 3 2 1 5 2 4 5 3 2 5 2 2 2 2 2 2 2* 4* 4* 4* 2 2 2 3 3 3 3* 3 3 3 3 3* 3* 3* 1* 5 5 5 5 5 5 5 5OPT调 调 中 调 替 中 替 中 中 替 中 中2、先进先出置换算法FIFO 原则：选择最早进入主存的页面淘汰 缺点： 最早进入主存的页面可能是经常被使用的页 异常现象：进程所分的页架数越多，缺页次 数也越多举例如果页面的引用顺序为2，3，2，1，5，2 ， 4，5，3，2，5，2，而分配给它们内存页 架数为3，用FIFO计算它的缺页次数。2 3 2 1 5 2 4 5 3 2 5 2 2 2 2 2* 5 5 5* 5* 3 3 3 33 3 3 3* 2 2 2 2* 2* 5 51 1 1* 4 4 4 4 4* 2调 调 中 调 替 替 替 中 替 中 替 替 FIFO例2：计算缺页次数某程序在内存中分配m页，初始为空 ，页面走向为1，2，3，4，1，2，5 ，1，2，3，4，5。当m=3，m=4时 缺页中断分别为多少？用FIFO算法 。例子2：计算缺页次数m=3时，缺页中断9次 m=4时，缺页中断10次当分配给进程的页架数增加时，缺页 次数反而增加。3、最近最少使用置换算法LRU 原则：选择最长时间未被访问的页面 基于程序的局部性原理，命中率较高 实现较困难 方法：计数法nn距阵法举例如果页面的引用顺序为2，3，2，1，5，2 ， 4，5，3，2，5，2，而分配给它们内存页 架数为3，用LRU计算它的缺页次数。1）计数法 设置一个计数器，一页一个，初值为0 。每执行一条指令后，计数器自动计 数。发生缺页中断时，选择计数器值 最小的一页淘汰举例如果页面的引用顺序为2，3，2，1，5，2 ， 4，5，3，2，5，2，而分配给它们内存页 架数为3，用LRU计算它的缺页次数。（计数法）2 3 2 1 5 2 4 5 3 2 5 2 2 2 2 2 2* 2 2 2* 3 3 3* 3* 3 3 3* 5 5 5* 5 5 5* 5 51 1 1* 4 4 4* 2 2 2 调 调 中 调 替 中 替 中 替 替 中 中 LRU2）矩阵法设有n个页架，系统维持一个n n的 矩阵，开始时所有位均为0。在页j被 访问到时，首先把第j行的所有位设 置为1，再把第j列的所有位设置成0 。在任何时刻二进制值最小的行所 对应的页架就是最近最少使用的。4、最近未使用置换算法NUR 原则：1、淘汰未被访问过的页2、淘汰未被修改过的页 硬件：每页增设两个硬件位：访问位，修改位