虚拟存储器管理.ppt

第九章 虚拟存储器管理,1、虚拟存储系统的基本概念2、分页存储管理3、分段存储管理4、段页式存储管理5、页（段）的置换算法和系统行为6、页架分配算法,9.1 虚拟存储系统的基本概念,1、问题的提出 程序大于内存 程序暂时不执行或运行完是否还要占用内存,2、基本思想程序、数据的大小可以超过内存的大小，操作系统把程序当前使用的部分保留在主存，而把其它部分保存在辅存中，并在需要时在主存和辅存之间动态交换。把辅存当作主存进行扩充，对用户来说，计算机系统有一个容量很大的主存。,虚存的优点：可容纳大量的进程，提高系统多道并行程度，提高主存和其他资源的利用率，提高系统运行效率和系统吞吐率,虚存的缺点：（1）额外的主存开销（2）地址转换增加了指令执行时间,9.2 分页存储管理,基本概念地址转换硬件支持页的共享,一、分页存储管理的基本概念,等分主存：页架、页架号用户逻辑地址空间的分页：页、页号逻辑地址的表示：（页号p,页内地址d）分配原则：以页架为基本分配单位页表：页号、页架号分页系统中的地址结构：页号最大页数页内地址页架的大小页面尺寸应是2的幂,基本工作原理 在程序开始运行之前，不是装入全部页面，而是装入一个或零个页面，之后根据程序运行的需要，动态装入其它页面；当内存空间已满，而又需要装入新的页面时，则根据某种算法淘汰某个页面，以便装入新的页面,虚地址空间,物理地址空间,虚页,页架,二、分页系统中的地址转换,直接映象页地址转换多级页表地址转换快表的地址转换,1、直接映象页地址转换,P,d,p,+,L,b,p,d,P,页表,页表地址寄存器,虚地址v=(p,d),实地址,b,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,1,1,0,0,0,0,0,0,0,0,0,0,1,0,0,110,在/不在内存,页表,虚地址8196,物理地址24580,000,0,15,000,0,14,000,0,13,000,0,12,111,1,11,000,0,10,101,1,9,000,0,8,000,0,7,000,0,6,011,1,5,100,1,4,000,1,3,110,1,2,001,1,1,010,1,0,页号 页架号 状态,2、多级页表地址转换,解决页表非常大的问题访存次数增加，增加一级页表，增加一次访存次数。,3、快表的地址转换,页号 页内地址,页号 页架号,页架号 页内地址,虚地址,物理地址,快表,p,页表,地址越界,l,比较,P=1,p,p,.,.,.,快表,b,+,页号p 页内地址d,P,d,物理地址,页表地址寄存器,页表长度寄存器,逻辑地址,举例,如果查找快表花费的时间是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）段号最多段数段内地址最大段长主存分配：以段为单位段表和段表寄存器段表：段号、段的长度、段在主存中的起始地址、段的状态位、访问位、修改位、段的外存地址段表寄存器：段表起始地址、段表长度,段的动态链接,在程序开始运行时，只将主程序段装配好并调入内存，其它各段的装配是在主程序段的运行过程中逐步完成。每当需要调用一个新段时，再将这个新段装配好，并与主程序段链接。,二、分段存储管理地址转换,段表长 段表地址,段号 段内地址,+,段表,S,l,L b,S w,b,s,+,实地址,段表地址寄存器,虚地址,Cl,Cb,+,段号S 段内地址d,比较,比较,b+d,段表,S=Cl,快表,物理地址,段表始址寄存器,段表长度寄存器,逻辑地址,l,b,.,.,.,S,l,b,地址越界,d=1,d=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 页内地址d,S,S,P,P,页架号 d,b,s,+,L b,虚地址,实地址,S P P,段表,页表,快表,快表的内容,段号 虚页号 页架号 保护信息 AGE 有效位,三、段页式存储管理算法,9.5 页的置换算法,页面访问失效及处理页面置换算法,一、页面访问失效及处理,引起失效的原因：边界错误 纯分页：页号超过页表长度 纯分段：偏移量超过段长，段号超过段表长度 段页式：页号超过该段的页表长度有效性错误：缺页或缺段中断保护错误：访问权限错误,二、页面置换算法,最佳置换算法OPT先进先出置换算法FIFO最近最少使用置换算法LRU最近未使用置换算法NUR两次机会置换算法时钟页面置换算法CLOCK,1、最佳置换算法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 5,OPT,调 调 中 调 替 中 替 中 中 替 中 中,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 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=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 5,1 1 1*4 4 4*2 2 2,调 调 中 调 替 中 替 中 替 替 中 中,LRU,2）矩阵法,设有n个页架，系统维持一个n n的矩阵，开始时所有位均为0。在页j被访问到时，首先把第j行的所有位设置为1，再把第j列的所有位设置成0。在任何时刻二进制值最小的行所对应的页架就是最近最少使用的。,4、最近未使用置换算法NUR,原则：1、淘汰未被访问过的页 2、淘汰未被修改过的页硬件：每页增设两个硬件位：访问位，修改位实现：初始：访问位、修改位置0；访问位被定期清零,发生缺页中断时，系统检查访问位，修改位：第0类：无访问，无修改 第1类：无访问，有修改 第2类：有访问，无修改 第3类：有访问，有修改系统随机从编号最小的非空类中选择一页淘汰,5、二次机会置换算法,原则：按照先进先出算法选择某一页面，检查其访问位，如果为0，则淘汰该页；如果为1，则给第二次机会，将该页移至队列末尾，并将访问位置0。命中率优于FIFO,二次机会算法的操作,A,B,C,D,E,F,G,H,最先装入的页面,最后装入的页面,B,C,D,E,F,G,H,A,将A作为刚装入页面,6、时钟页面置换算法CLOCK,两次机会置换算法的改进。实现方法：把所有的页面保存在一个类似时钟表面的环形链表中。有一个指针指向最老的页面。,时钟页面置换算法,A,L,K,J,I,H,G,F,E,D,C,B,举例,如果页面的引用顺序为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 3,CLOCK,调 调 中 调 替 中 替 中 替 中 中 中,9.6 页架分配策略,物理主存空闲页面链表页架分配中有关策略分页环境中程序的行为特性,1、物理主存,非换页池 换页主存池 错误缓冲,内核代码（常驻主存）,用户进程,内核代码（动态分配）,错误信息,与主存相关的数据结构：主存映射图：描述物理主存页表：描述虚存磁盘映射图：描述交换区资源映射图：实现资源（页表、交换区）分配,2、空闲页面链表,特点：用一专门的独立进程负责页面替换工作链表中的页面并非真正空闲页面置换并不是页在主存中的移动,3、页架分配中有关策略,调入策略（提前分页，请求分页）局部和全局置换，固定和可变分配工作集页的大小,局部和全局置换，固定和可变分配,固定分配：分配给进程的页架数不变。可变分配：分配给进程的页架数是可变的。全局置换：从整个主存中选择淘汰页。局部置换：从自己以占有的页架中选择淘汰页。,局部、全局置换与固定、可变分配之间的关系,局部置换 全局置换（1）一个进程的页架数固定固定分配（2）从分配给该进程的页架中 不可能 选择被替换的页（1）分配给进程的页架数不断 从主存中所有可用页 可变分配 变化 架中选择被替换的页（2）从分配给进程的页架中 使进程页架数不断变 选择被替换的页 化,工作集模型,基本思想：根据程序的局部性原理，一般情况下，进程在一段时间内总是集中访问一些页面，这些页面称为活跃页面，如果分配给一个进程的页架数太少了，使该进程所需的活跃页面不能全部装入内存，则进程在运行过程中将频繁发生中断。,如果能为进程提供与活跃页面数相等的页架数，则可减少缺页中断次数。,工作集,一个运行进程在t-w到t这个时间间隔内所访问的页的集合称为该进程在时间t的工作集，记为W（t,w）W（t,w）为工作集尺寸：工作集中包含的页面数。w:对于给定的访问序列选取定长的区间，称为工作集窗口,工作集：,内容取决于页的三个因素 a 访页序列特性 b 时刻Ti c 窗口长度(),例：|t1|t2 w(t1)=1,2,5,6,7 w(t2)=3,4,页的大小,大页面：页内碎片多，缺页次数多小页面：页表空间大大页面：可减少输入输出工作大页面：解决程序局部性降低，快表命中率降低的问题,4、分页环境中程序的行为特性,局部性的概念分页环境中程序的行为特性减少访问离散性的程序结构,（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次缺页,方法,功能,分区式,页式,段式,段页式,固定 可变,静态 动态,适用环境 多道 多道 多道 多道,重定位 静态 动态 动态 动态 动态,分配方式 分配连续区,以页为单位非连续,以段为单位非连续,以页为单位非连续,释放,执行完全部释放,分区释放,执行完全部释放,淘汰与执行完释放,同左 同左,保护,同左 同左,越界保护与存储键,越界保护与控制权保护,同左,同左,共享 不能 较难 方便 方便,硬件支持,保护用寄存器重定位机构,地址变换机构中断机构 保护机构,地址变换机构中断机构保护机构动态链接机构,9.7 共享主存，快表一致性问题,主存共享快表一致性问题,1、主存共享,内核支持相关进程间的copy_on_write页面级共享技术支持传统的共享主存区的进程间的通讯通过存储映射接口实现共享功能,2、快表一致性问题,概念单处理机的快表一致性问题多处理机的快表一致性问题,方法,功能,分区式,页式,段式,段页式,固定 可变,静态 动态,适用环境 多道 多道 多道 多道,虚拟空间 一维 一维 二维 二维,重定位 静态 动态 动态 动态 动态,分配方式 分配连续区,以页为单位非连续,以段为单位非连续,以页为单位非连续,释放,执行完全部释放,分区释放,执行完全部释放,淘汰与执行完释放,同左 同左,保护,同左 同左,越界保护与存储键,覆盖与交换,越界保护与控制权保护,同左 同左,同左,同左,内外存统一管理虚存,内存扩充,共享 不能 较难 方便 方便,硬件支持,保护用寄存器重定位机构,地址变换机构中断机构 保护机构,地址变换机构中断机构保护机构动态链接机构,清除快表表项的三种方法,清除一个对应某虚页的快表表项清除整个快表装入一个新的快表表目,单处理器上的快表一性,需要清除快表表目的情况：保护权限变化被置换出去进程上下文切换exec:进程调用exec执行另一程序,6、页架分配算法,物理主存空闲页面链表页架分配中有关策略分页环境中程序的行为特性,空闲页面链表,页架分配中有关策略,调入策略（预调，请调）局部和全局置换，固定和可变分配工作集页的大小,局部和全局置换，固定和可变分配,固定分配：进程的页架数不变。可变分配：进程的页架数是可变的。全局置换：从整个主存中选择淘汰页。局部置换：从自己以占有的页架中选择淘汰页。,工作集,一个运行进程在t-w到t这个时间间隔内所访问的页的集合称为该进程在时间t的工作集，记为W（t,w）W（t,w）为工作集尺寸：工作集中包含的页面数。,页的大小,大页面：页内碎片多，缺页次数多小页面：页表空间大大页面：可减少输入输出工作,分页环境中程序的行为特性,局部性的概念分页环境中程序的行为特性减少访问离散性的程序结构,局部性的概念,时间局部性：某个位置最近被访问，那么往往很快又要被访问。空间局部性：某个位置最近被访问，则它附近的位置也会被访问。,减少访问离散性的程序结构,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次缺页,7、共享主存，快表一致性问题,主存共享快表一致性问题,主存共享,内核支持相关进程间的copy_on_write页面级共享技术支持传统的共享主存区的进程间的通讯通过存储映射接口实现共享功能,快表一致性问题,概念单处理机的快表一致性问题多处理机的快表一致性问题,方法,功能,分区式,页式,段式,段页式,固定 可变,静态 动态,适用环境 多道 多道 多道 多道,虚拟空间 一维 一维 二维 二维,重定位 静态 动态 动态 动态 动态,分配方式 分配连续区,以页为单位非连续,以段为单位非连续,以页为单位非连续,释放,执行完全部释放,分区释放,执行完全部释放,淘汰与执行完释放,同左 同左,保护,同左 同左,越界保护与存储键,覆盖与交换,越界保护与控制权保护,同左 同左,同左,同左,内外存统一管理虚存,内存扩充,共享 不能 较难 方便 方便,硬件支持,保护用寄存器重定位机构,地址变换机构中断机构 保护机构,地址变换机构中断机构保护机构动态链接机构,