操作系统 (8).ppt

《操作系统 (8).ppt》由会员分享，可在线阅读，更多相关《操作系统 (8).ppt（95页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第九章 虚拟存储器管理1、虚拟存储系统的基本概念2、分页存储管理3、分段存储管理4、段页式存储管理5、页（段）的置换算法和系统行为6、页架分配算法9.1 虚拟存储系统的基本概念 1、问题的提出、问题的提出 程序大于内存 程序暂时不执行或运行完是否还要占用内存2、基本思想、基本思想程序、数据的大小可以超过内存的大小，操作系统把程序当前使用的部分保留在主存，而把其它部分保存在辅存中，并在需要时在主存和辅存之间动态交换。把辅存当作主存进行扩充，对用户来说，计算机系统有一个容量很大的主存。虚存的优点：可容纳大量的进程，提高系统多道并行程度，提高主存和其他资源的利用率，提高系统运行效率和系统吞吐率虚存的

2、缺点：（1）额外的主存开销（2）地址转换增加了指令执行时间9.2 分页存储管理基本概念地址转换硬件支持页的共享一、分页存储管理的基本概念等分主存：页架、页架号用户逻辑地址空间的分页：页、页号逻辑地址的表示：（页号p,页内地址d）分配原则：以页架为基本分配单位页表：页号、页架号分页系统中的地址结构：页号最大页数页内地址页架的大小页面尺寸应是2的幂基本工作原理 在程序开始运行之前，不是装入全部页面，而是装入一个或零个页面，之后根据程序运行的需要，动态装入其它页面；当内存空间已满，而又需要装入新的页面时，则根据某种算法淘汰某个页面，以便装入新的页面XXXX7X5XXX34061260K-64K56K

3、-60K52K-56K48K-52K44K-48K40K-44K36K-40K32K-36K28K-32K24K-28K20K-24K16K-20K12K-16K 8K-12K 4K-8K 0K-4K28K-32K24K-28K20K-24K16K-20K12K-16K 8K-12K 4K-8K 0K-4K虚地址空间虚地址空间物理地址空间物理地址空间 虚页虚页页架页架二、分页系统中的地址转换直接映象页地址转换多级页表地址转换快表的地址转换1、直接映象页地址转换 Pd p+L bp dP 页表页表地址寄存器虚地址v=(p,d)实地址b0010000000000100110000000000100

4、110在在/不在内存不在内存页表页表虚地址虚地址8196物理地址物理地址245800000150000140000130000121111110000101011 90000 80000 70000 60111 51001 40001 31101 20011 10101 0页号 页架号 状态2、多级页表地址转换解决页表非常大的问题访存次数增加，增加一级页表，增加一次访存次数。3、快表的地址转换、快表的地址转换 页号 页内地址页号 页架号页架号 页内地址虚地址物理地址快表p页表页表地址越界地址越界 l比较比较P=1pp.快表快表 b+页号页号p p 页内地址页内地址dPd物理地址物理地址页表地址

5、寄存器页表地址寄存器页表长度寄存器页表长度寄存器逻辑地址逻辑地址举例如果查找快表花费的时间是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、页表实现页式管理重

6、要的数据结构内容：页架号 修改位 有效位 引用位 保护权限3、快表为加快地址转换而使用高速缓存内容：页号 页架号 保护权限4、反向页表完成物理页架号到虚地址的映射内容：虚页号 物理页架号 指向哈希链的下一项指针 有效位，修改位，引用位 保护和加锁信息9.3 分段存储管理基本概念地址转换一、分段存储管理的基本概念进程的逻辑地址空间：段、段号程序的地址结构：（段号s、段内地址w）段号最多段数段内地址最大段长主存分配：以段为单位段表和段表寄存器段表：段号、段的长度、段在主存中的起始地址、段的状态位、访问位、修改位、段的外存地址段表寄存器：段表起始地址、段表长度段的动态链接 在程序开始运行时，只将主程

7、序段装配好并调入内存，其它各段的装配是在主程序段的运行过程中逐步完成。每当需要调用一个新段时，再将这个新段装配好，并与主程序段链接。二、分段存储管理地址转换 段表长 段表地址段号 段内地址+段表Sl L bS wbs+实地址段表地址寄存器 虚地址 Cl Cb+段号段号S S 段内地址段内地址d比较比较比较比较b +d段段表表S=Cl快表快表物理地址物理地址段表始址寄存器段表始址寄存器段表长度寄存器段表长度寄存器逻辑地址逻辑地址lb.Slb地址越界地址越界d=1d=1地址映射及存储保护机制地址映射及存储保护机制地址越界地址越界地址越界地址越界比较比较举例 段长 段起始地址 有效位 0 200 5

8、00 1 1 400 1000 1 2 100 1400 0 3 900 2000 1 虚地址：（2，250）,（4，470）完成实地址转换1.缺段中断2.越界三、存储保护问题越界保护存取控制保护四、分段存储管理的优缺点优点：便于处理变化的数据结构便于共享提供虚存的功能提供动态连接的便利便于控制存取访问缺点：要为存储紧缩付出处理机机时的代价分段的最大尺寸受到主存大小的限制在外存中管理可变尺寸的分段比较困难与分页一样，提高了硬件成本9.4 段页式存储管理基本概念地址转换存储管理算法优缺点一、段页式存储管理的基本概念等分主存：页架、页架号进程的地址空间采用分段的方式每一段采用分页的方法逻辑地址结构

9、：（s,p,d）主存分配：以页为单位非连续分配数据结构：段表、页表、段表地址寄存器段号段号段内地址段内地址页号页号页内地址页内地址二、段页式管理的地址转换 段表地址寄存器段号S 页号P 页内地址dSSPP页架号 d bs+L b 虚地址实地址S P P段表页表快表快表的内容 段号 虚页号 页架号 保护信息 AGE 有效位三、段页式存储管理算法9.5 页的置换算法页面访问失效及处理页面置换算法一、页面访问失效及处理引起失效的原因：边界错误 纯分页：页号超过页表长度 纯分段：偏移量超过段长，段号超过段表长度 段页式：页号超过该段的页表长度有效性错误：缺页或缺段中断保护错误：访问权限错误二、页面置换

10、算法最佳置换算法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、先进先出置换算法FIF

11、O原则：选择最早进入主存的页面淘汰缺点：最早进入主存的页面可能是经常被使用的页异常现象：进程所分的页架数越多，缺页次数也越多举例如果页面的引用顺序为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 3 3 3 3 3*2 2 2 2*2*5 5 1 1 1*4 4 4 4 4*2 调 调 中 调 替 替 替 中 替 中 替 替 FIFO例2：计算缺页次数 某程序在内存中分配m页，初始为空，页面走向为1，2，3，4，1，2，5，1，2，3，4，5。当m

12、=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

13、，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 5 1 1 1*4 4 4*2 2 2 调 调 中 调 替 中 替 中 替 替 中 中 LRU2）矩阵法设有n个页架，系统维持一个n n的矩阵，开始时所有位均为0。在页j被访问到时，首先把第j行的所有位设置为1，再把第j列的所有位设置成0。在任何时刻二进制值最小的行所对应的页架就是最近最少使用的。4、最近未使用置换算法NUR原则：1、淘汰未被访问过的页 2、淘汰未被修改过的页硬件：每页增

14、设两个硬件位：访问位，修改位访问位，修改位实现：初始：访问位、修改位置0；访问位被定期清零 发生缺页中断时，系统检查访问位，修改位：第0类：无访问，无修改 第1类：无访问，有修改 第2类：有访问，无修改 第3类：有访问，有修改系统随机从编号最小的非空类中选择一页淘汰5、二次机会置换算法原则：按照先进先出算法选择某一页面，检查其访问位，如果为0，则淘汰该页；如果为1，则给第二次机会，将该页移至队列末尾，并将访问位置0。命中率优于FIFO二次机会算法的操作ABCDEFGH最先装入的页面最后装入的页面BCDEFGHA将A作为刚装入页面6、时钟页面置换算法CLOCK两次机会置换算法的改进。实现方法：把

15、所有的页面保存在一个类似时钟表面的环形链表中。有一个指针指向最老的页面。时钟页面置换算法ALK J IHGFEDCB举例如果页面的引用顺序为2，3，2，1，5，2，4，5，3，2，5，2，而分配给它们内存页架数为3，用CLOCK计算它的缺页次数。2 3 2 1 5 2 4 5 3 2 5 2.2 .2 .2*.2*2 2*.2*.2*.2 .2*.2*.2*3 3 3 5 5 5 5*5 5 5*5*1 .1 .1 4 4 3 3 3 3CLOCK 调 调 中 调 替 中 替 中 替 中 中 中9.6 页架分配策略物理主存空闲页面链表页架分配中有关策略分页环境中程序的行为特性1、物理主存非换页

16、池 换页主存池 错误缓冲 内核代码（常驻主存）用户进程 内核代码（动态分配）错误信息与主存相关的数据结构：主存映射图：描述物理主存页表：描述虚存磁盘映射图：描述交换区资源映射图：实现资源（页表、交换区）分配2、空闲页面链表特点：用一专门的独立进程负责页面替换工作链表中的页面并非真正空闲页面置换并不是页在主存中的移动3、页架分配中有关策略调入策略（提前分页，请求分页）局部和全局置换，固定和可变分配工作集页的大小局部和全局置换，固定和可变分配固定分配：分配给进程的页架数不变。可变分配：分配给进程的页架数是可变的。全局置换：从整个主存中选择淘汰页。局部置换：从自己以占有的页架中选择淘汰页。局部、全局

17、置换与固定、可变分配之间的关系 局部置换 全局置换 （1）一个进程的页架数固定固定分配 （2）从分配给该进程的页架中 不可能 选择被替换的页 （1）分配给进程的页架数不断 从主存中所有可用页 可变分配 变化 架中选择被替换的页 （2）从分配给进程的页架中 使进程页架数不断变 选择被替换的页 化工作集模型 基本思想：根据程序的局部性原理，一般情况下，进程在一段时间内总是集中访问一些页面，这些页面称为活跃页面，如果分配给一个进程的页架数太少了，使该进程所需的活跃页面不能全部装入内存，则进程在运行过程中将频繁发生中断。如果能为进程提供与活跃页面数相等的页架数，则可减少缺页中断次数。工作集一个运行进程

18、在t-w到t这个时间间隔内所访问的页的集合称为该进程在时间t的工作集，记为W（t,w）W（t,w）为工作集尺寸：工作集中包含的页面数。w:对于给定的访问序列选取定长的区间，称为工作集窗口工作集：内容取决于页的三个因素内容取决于页的三个因素 a 访页序列特性 b 时刻Ti c 窗口长度()例：26157775162341234443434441327|t1|t2 w(t1)=1,2,5,6,7 w(t2)=3,4页的大小大页面：页内碎片多，缺页次数多小页面：页表空间大大页面：可减少输入输出工作大页面：解决程序局部性降低，快表命中率降低的问题4、分页环境中程序的行为特性局部性的概念分页环境中程序的

19、行为特性减少访问离散性的程序结构（1）局部性的概念时间局部性：某个位置最近被访问，那么往往很快又要被访问。空间局部性：某个位置最近被访问，则它附近的位置也会被访问。（3）减少访问离散性的程序结构For j:=1 to 128do For i:=1 to 128do Ai,j:=0 For i:=1 to 128do For j:=1 to 128do Ai,j:=0 若以行序为主序存数第一种编制：程序执行产生128*128次缺页第二种编制：程序执行产生128次缺页方法功能分区式页式段式段页式固定 可变静态 动态适用环境 多道 多道 多道 多道重定位 静态 动态 动态 动态 动态分配方式 分配连

20、续区以页为单位非连续以段为单位非连续以页为单位非连续释放 执行完全部释放分区释放执行完全部释放淘汰与执行完释放 同左 同左保护 同左 同左 越界保护与存储键越界保护与控制权保护 同左同左 共享 不能 较难 方便 方便 硬件支持保护用寄存器重定位机构地址变换机构中断机构 保护机构地址变换机构中断机构保护机构动态链接机构9.7 共享主存，快表一致性问题主存共享快表一致性问题1、主存共享内核支持相关进程间的copy_on_write页面级共享技术支持传统的共享主存区的进程间的通讯通过存储映射接口实现共享功能2、快表一致性问题概念单处理机的快表一致性问题多处理机的快表一致性问题方法功能分区式页式段式段

21、页式固定 可变静态 动态适用环境 多道 多道 多道 多道 虚拟空间 一维 一维 二维 二维重定位 静态 动态 动态 动态 动态分配方式 分配连续区以页为单位非连续以段为单位非连续以页为单位非连续释放 执行完全部释放分区释放执行完全部释放淘汰与执行完释放 同左 同左保护 同左 同左 越界保护与存储键覆盖与交换越界保护与控制权保护 同左 同左 同左同左内外存统一管理虚存内存扩充 共享 不能 较难 方便 方便 硬件支持保护用寄存器重定位机构地址变换机构中断机构 保护机构地址变换机构中断机构保护机构动态链接机构清除快表表项的三种方法清除一个对应某虚页的快表表项清除整个快表装入一个新的快表表目单处理器上

22、的快表一性需要清除快表表目的情况：保护权限变化被置换出去进程上下文切换exec:进程调用exec执行另一程序6、页架分配算法物理主存空闲页面链表页架分配中有关策略分页环境中程序的行为特性空闲页面链表页架分配中有关策略调入策略（预调，请调）局部和全局置换，固定和可变分配工作集页的大小局部和全局置换，固定和可变分配固定分配：进程的页架数不变。可变分配：进程的页架数是可变的。全局置换：从整个主存中选择淘汰页。局部置换：从自己以占有的页架中选择淘汰页。工作集一个运行进程在t-w到t这个时间间隔内所访问的页的集合称为该进程在时间t的工作集，记为W（t,w）W（t,w）为工作集尺寸：工作集中包含的页面数。

23、页的大小大页面：页内碎片多，缺页次数多小页面：页表空间大大页面：可减少输入输出工作分页环境中程序的行为特性局部性的概念分页环境中程序的行为特性减少访问离散性的程序结构局部性的概念时间局部性：某个位置最近被访问，那么往往很快又要被访问。空间局部性：某个位置最近被访问，则它附近的位置也会被访问。减少访问离散性的程序结构For j:=1 to 512do For i:=1 to 512do Ai,j:=0 For i:=1 to 512do For j:=1 to 512do Ai,j:=0 若以行序为主序存数第一种编制：程序执行产生512*512=262144次缺页第二种编制：程序执行产生512次

24、缺页7、共享主存，快表一致性问题主存共享快表一致性问题主存共享内核支持相关进程间的copy_on_write页面级共享技术支持传统的共享主存区的进程间的通讯通过存储映射接口实现共享功能快表一致性问题概念单处理机的快表一致性问题多处理机的快表一致性问题方法功能分区式页式段式段页式固定 可变静态 动态适用环境 多道 多道 多道 多道 虚拟空间 一维 一维 二维 二维重定位 静态 动态 动态 动态 动态分配方式 分配连续区以页为单位非连续以段为单位非连续以页为单位非连续释放 执行完全部释放分区释放执行完全部释放淘汰与执行完释放 同左 同左保护 同左 同左 越界保护与存储键覆盖与交换越界保护与控制权保护 同左 同左 同左同左内外存统一管理虚存内存扩充 共享 不能 较难 方便 方便 硬件支持保护用寄存器重定位机构地址变换机构中断机构 保护机构地址变换机构中断机构保护机构动态链接机构