【精品】【考研计算机专业课】武汉大学操作系统PPT课件 第6章 虚拟存储器精品ppt课件.ppt

【考研计算机专业课】武汉大学操作系统PPT课件 第6章 虚拟存储器6.1 虚拟存储器概念虚拟存储器概念n虚拟存储器（Virtual Memory）的理论基础是程序执行时的局部性原理。n局部性原理是指程序在执行过程中一个较短时间内，程序所执行的指令地址和操作数地址分别局限于一定区域内。n例如：n除转移和过程调用外，程序主要是顺序执行。n过程调用使程序从一部分区域转至另一部分区域n循环结构局部性的体现n局部性体现为：n时间局部性：一条指令的一次执行和下次执行，一个数据的一次访问和下次访问，都集中在一个较短时间内。n空间局部性：当前执行的指令和将要执行的指令，当前访问的数据和将要访问的数据，都集中在一个较小范围内。虚拟存储器的基本原理n在程序运行之前，将程序的一部分放入内存后就启动程序执行。n在程序执行过程中，当所访问的信息不在内存时，由操作系统将所需要的部分调入内存，然后继续执行程序。n另一方面，操作系统将内存中暂时不使用的内容换出到外存上，从而腾出空间存放将要调入内存的信息。n从效果上看，这样的计算机系统好像为用户提供了一个存储容量比实际内存大得多的存储器，将这个存储器称为虚拟存储器。虚拟存储器n虚拟存储器是指具有请求调入和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。n虚拟存储器是一种以时间换空间的技术。实现虚拟存储技术的物质基础n相当数量的外存：足以存放多个用户的程序。n一定容量的内存：在处理机上运行的程序必须有一部分信息存放在内存中。n地址变换机构：动态实现逻辑地址到物理地址的变换。虚拟存储器的实现方法n常用的虚拟存储技术有：n请求分页存储管理n请求分段存储管理n具有请求调页功能的段页式存储管理系统6.2 请求分页存储管理-6.2.1n请求分页存储管理方法是在分页存储管理的基础上增加了请求调页和页面置换功能。n实现思想：在作业运行之前只装入当前需要的一部分页面便启动作业运行。在作业运行过程中，若发现所要访问的页面不在内存，便由硬件产生缺页中断，请求OS将缺页调入内存。若内存无空闲存储空间，则根据某种置换算法淘汰已在内存的某个页面，以腾出内存空间装入缺页。请求分页系统中的支持机构请求分页系统中的支持机构n请求分页中的支持机构有：n页表n缺页中断机构n地址变换机构n请求调页和页面置换软件6.2.2 页表n请求分页系统中使用的主要数据结构仍然是页表。n但由于每次只将作业的一部分调入内存，还有一部分内容存放在磁盘上，故需要在页表中增加若干项。n扩充后的页表项如下所示：扩充后的页表项n页号和物理块号：其定义同分页存储管理。n状态位：用于表示该页是否在主存中。n访问字段：用于记录本页在一段时间内被访问的次数，或最近已有多长时间未被访问。n修改位：用于表示该页调入内存后是否被修改过。n外存地址：用于指出该页在外存上的地址。页号页号 物理块号物理块号 存在位存在位 访问字段访问字段修改位修改位 外存地址外存地址6.2.3 缺页中断与地址变换缺页中断与地址变换n在请求分页系统中，当所访问的页不在内存时，便产生缺页中断，请求OS将缺页调入内存。n缺页中断处理程序根据该页在外存的地址把它调入内存。在调页过程中，若内存有空闲空间，则缺页中断处理程序只需把缺页装入并修改页表中的相应项；若内存中无空闲物理块，则需要先淘汰内存中的某些页，若淘汰页曾被修改过，则还要将其写回外存。缺页中断与一般中断的区别缺页中断与一般中断的区别n缺页中断与一般中断的区别主要有：n在指令的执行期间产生和处理缺页中断。n一条指令可以产生多个缺页中断。如：执行一条复制指令copy A to Bn缺页中断返回时执行产生中断的指令，一般中断返回时执行下条指令 B:A:Copy A To B页面654321地址变换n请求分页存储管理系统的地址变换过程类似于分页存储管理，但当被访问页不在内存时应进行缺页中断处理。地址变换流程程序请求访问一页页号页表长度？页在内存？YNCPU检索快表Y修改快表页表项在快表中？产生缺页中断N访问页表越界中断NY修改访问位和修改位形成物理地址 A缺页处理流程缺页中断处理保留CPU现场该页被修改否？从外存中找到缺页N将该页写回外存内存满否？Y选择一页换出NY从外存读缺页入内存修改页表 A6.2.4 页面分配和置换策略页面分配和置换策略 n在为进程分配物理块时应确定在为进程分配物理块时应确定:n进程需要的最少物理块数进程需要的最少物理块数n进程的物理块数是固定还是可变进程的物理块数是固定还是可变n按什么原则为进程分配物理块数按什么原则为进程分配物理块数最小物理块数的确定最小物理块数的确定n最小物理块数是指能保证进程正常运行所需的最少物理块数，若小于此值进程无法运行。n一般情况下：n单地址指令且采用直接寻址，则所需最少物理块数为2。n若单地址指令且允许采用间接寻址，则所需最少物理块数为3。n某些功能较强的机器，指令及源地址和目标地址均跨两个页面，则最少需要6个物理块。页面分配和置换策略页面分配和置换策略 n页面分配常采用固定分配和可变分配两种策略。n页面置换也有全局置换和局部置换两种策略。n将分配策略和置换范围组合可得如下三种策略：n固定分配局部置换n可变分配全局置换n可变分配局部置换固定分配局部置换n固定分配局部置换：基于某种原则为每个进程分配固定数量的物理块，当进程运行中出现缺页时，只能从自己的页面中选择一页换出，然后再调入缺页。n实现这种策略的困难在于：难以确定应为每个进程分配多少个物理块。可变分配全局置换n可变分配全局置换：先为系统中的每个进程分配一定数量的物理块，操作系统本身也保持一个空闲物理块队列。当某进程发生缺页时，由系统从空闲物理块队列中取出一个物理块分配给该进程；当空闲物理块队列中的物理块用完时，操作系统才从内存中选择一页调出，该页可以是系统中任何一个进程的页面。n这是一种容易实现的页面分配和置换策略，目前已用于若干操作系统中。可变分配局部置换n可变分配局部置换：根据某种原则为每个进程分配一定数量的物理块，当进程发生缺页中断时，只允许从该进程的页面中选出一页换出。如果某进程的缺页率较高，则系统再为该进程分配若干物理块；反之若某进程的缺页率特别低，则系统可适当减少分配给该进程的物理块数。n该算法比较复杂，但性能较好。物理块分配算法物理块分配算法n物理块分配是指按什么原则给进程分配物理块数，通常有以下几种分配算法：n平均分配算法：将系统中所有可供分配物理块平均分配给每个进程。n按比例分配算法：根据进程大小按比例分配物理块。n按优先级分配算法：有两种实现方案n将可供分配的物理块分为两部分，一部分按比例分配给每个进程，另一部分根据进程的优先级适当增加物理块。n先按比例为进程分配物理块，当高优先级进程发生缺页时，允许它从低优先级进程处获得物理块。6.2.5 页面置换算法页面置换算法n页面置换（Page Replacement）算法又称为页面淘汰算法，是用来选择换出页面的算法。n下面介绍几种比较常用的页面置换算法。1最佳置换算法（OPT）n最佳（Optimal）算法是从内存中选择将来最长时间不会使用的页面予以淘汰。n特点：因页面访问的未来顺序很难精确预测，该算法具有理论意义，可以用来评价其他算法的优劣。最佳置换算法例n假定系统为某进程分配了3个物理块，页面访问序列为：1、2、3、4、1、2、5、1、2、3、4、5，开始时3个物理块均为空闲，采用最佳置换算法时的页面置换情况如下所示：采用最佳置换算法的页面置换情况n从上表中可以看出，共发生了7次缺页，其缺页率为7/1258.3%。5缺 5 4 3 4缺 5 2 3 3 2 1缺 5 2 1 5 2 1缺 4 2 1 4缺 3 2 1 3缺 2 1 2缺 1 1 块3 块2 块1走向2.先进先出算法（FIFO）n先进先出（First-In-First-Out）算法是选择调入主存时间最长的页面予以淘汰。n特点：该算法实现比较简单，对按线性顺序访问的程序比较合适，但可能产生异常现象。很少使用纯粹的FIFO。nBelady现象：在某些情况下，分配给进程的页面数增多，缺页次数反而增加。先进先出置换算法例n假定系统为某进程分配了3个物理块，页面访问序列为：1、2、3、4、1、2、5、1、2、3、4、5，开始时3个物理块均为空闲，采用先进先出置换算法时的页面置换情况如下所示：采用先进先出算法的页面置换情况n从上表中可以看出，共发生了9次缺页中断。其缺页率为9/1275%。5缺 4 3 5 4缺 2 3 5 3 2 1缺 2 1 5 5缺 2 1 4 2缺 3 1 4 1缺 3 2 4 4缺 3 2 1 3缺 2 1 2缺 1 1 块3 块2 块1走向为进程分配4个物理块n从上表中可以看出，共发生了10次缺页中断。其缺页率为10/1283.3%。3 3 3 4 4 4 4 块4缺 2 5 4 5缺 2 1 4 4缺 2 1 5 3缺 2 1 5 2缺 3 1 5 1缺 3 2 5 5 2 1缺 3 2 1 4缺 3 2 1 3缺 2 1 2缺 1 1 块3 块2 块1走向无异常现象的页面序列n假定系统为某进程分配了3个物理块，页面访问序列为：7、0、1、2、0、3、0、4、2、3、0、3，开始时3个物理块均为空闲，采用先进先出置换算法时的页面置换情况如下所示：页面置换情况n从上表中可以看出，共发生了10次缺页中断。其缺页率为10/1283.3%。3缺 3 2 0 0缺 3 2 4 3缺 0 2 4 2缺 0 3 4 4缺 0 3 2 0缺 1 3 2 3 0缺 1 0 2 2缺 1 0 7 1缺 0 7 0缺 7 7 块3 块2 块1走向为进程分配4个物理块n从上表中可以看出，共发生了7次缺页中断。其缺页率为7/1258.3%。2 2 2 2 块4 3缺 0 4 3 0 3 2缺 1 4 3 4 0缺 1 0 3 3 0缺 1 0 7 2缺 1 0 7 1缺 0 7 0缺 7 7 块3 块2 块1走向3.最近最久未使用置换算法(LRU)n最近最久未使用算法选择最近一段时间内最长时间没有被访问过的页面予以淘汰。n为此，应赋予每个页面一个访问字段，用于记录页面自上次访问以来所经历的时间。nLRU是Least Recently Used，也称为最近最少使用LRU算法例n假定系统为某进程分配了3个物理块，页面访问序列为：1、2、3、4、1、2、5、1、2、3、4、5，开始时3个物理块均为空闲，采用LRU置换算法时的页面置换情况如下所示：采用LRU算法的页面置换情况n从上表中可以看出，共发生了10次缺页，其缺页率为10/1283.3%。缺 5 4 3 5缺 2 4 3 4缺 2 1 3 3 2 1缺 2 1 5 5缺 2 1 4 2缺 3 1 4 1缺 3 2 4 4缺 3 2 1 3缺 2 1 2缺 1 1 块3 块2 块1走向为进程分配4个物理块n从上表中可以看出，共发生了8次缺页中断。其缺页率为8/1266.7%。3 3 3 4 4 块4缺 4 2 5 5缺 4 2 1 4缺 5 2 1 3 2 1缺 5 2 1 5 2 1缺 3 2 1 4缺 3 2 1 3缺 2 1 2缺 1 1 块3 块2 块1走向LRU算法的实现nLRU算法实现时需要较多的硬件支持，以记录进程中各页面自上次访问以来有多长时间未被访问。下面介绍几种实现方法。n链表法n计数器法链表法n用一个单链表保存当前进程所访问的各页面号，刚使用过的页面放表尾，则表头一定是最近最久未使用的页面。n实现思想为：n当分配给进程的物理块未用完时，则将进程装入内存的页面按先后顺序构成一个链表n当进程访问的页面在内存时，将页面从链表中移出放到表尾n当进程访问的页面不在内存时，则发生缺页中断，将表头页面置换链表法例n例如：设分配给某进程4个物理块，页面访问序列为：3、2、4、1、5、4、3、2，用单链表实现LRU算法的过程如下：3head 2 4 1 2head 4 1 5 2head 1 5 4 1head 5 4 3 5head 4 3 2 计数器法n为每个页面配置一个计数器（Counter），其初值为0。当进程访问某页时，将计数器的最高位置1，定时器每隔一定时间将计数器右移1位，则数值最小的页是最近最久未使用的页面。计数器法（续）R页面页面 R7 R6 R5 R4 R3 R2 R1 R0 1 2 3 4 5 6 7 8 0 1 1 0 1 0 0 0 1 0 0 1 1 0 0 1 0 1 0 1 0 1 0 1 1 0 0 0 1 0 0 0 0 1 0 1 0 1 0 1 0 1 0 0 1 0 1 1 1 0 0 1 1 1 1 0 0 0 0 1 0 1 1 1最近最久未使用的页是？7 0 0 0 0 0 1 1 14.其他页面置换算法-二次机会算法n二次机会（Second-Chance）算法是FIFO算法的改进，以避免将经常使用的页面淘汰掉。为此设置了页面引用位。n算法思想：使用FIFO算法选择一页淘汰时，先检查该页的引用位，如果是0就立即淘汰该页，如果是1就给它第二次机会，将其引用位清0，并将它放入页面链的末尾，将其装入时间置为当前时间，然后选择下一个页面。简单时钟（clock）算法n简单时钟置换算法既是对二次机会算法的改进，也是对LRU算法的近似。该算法也要求为每页设置一个访问位。n实现思想：将页面排成一个循环队列，类似于时钟表面，并使用一个置换指针。当发生缺页时，检查指针指向的页面，若其访问位为0则淘汰该页，否则将该页的访问位清0，指针前移并重复上述过程，直到找到访问位为0的淘汰页为止。最后指针停留在被置换页的下一页上；n该算法也称为最近未使用（Not Recently Used，NRU）算法。简单时钟置换算法页面链简单时钟置换算法页面链 块号块号 页号页号 访问位访问位 指针指针 0 1 2 4 0 3 4 2 1 5 6 5 0 7 1 1替换指针替换指针简单时钟置换算法流程入口指针前进一步返回指针所指页面访问位=0？N选择该页面淘汰Y置页面访问位为0指针前进一步页面置换情况n从上表中可以看出，共发生了9次缺页中断。其缺页率为9/1275%。0*23*3缺0*2 4 0 3*2*4*3缺 3 2*4*2缺 3 0 4*4 3*0*2*0缺 3*0 2*3 0缺 1 0 2*2缺 1*0*7*1缺0*7*0缺7*7 块3 块2 块1走向 1 0*2*缺改进的时钟算法改进的时钟算法n将一个修改过的页面换出需要写磁盘，其开销大于未修改页面。为此在改进型时钟算法中应考虑页面修改情况。设R为访问位，U为修改位，将页面分为以下4种类型：n1类(R=0,U=0)：未被访问又未被修改n2类(R=0,U=1)：未被访问但已被修改n3类(R=1,U=0)：已被访问但未被修改n4类(R=1,U=1)：已被访问且已被修改改进型时钟算法描述n从指针当前位置开始扫描循环队列，寻找R=0,U=0的页面，将满足条件的第一个页面作为淘汰页。n若第1步失败，则开始第2轮扫描，寻找R=0,U=1的页面，将满足条件的第一个页面作为淘汰页，并将所有经历过页面的访问位置0。n若第2步失败，则将指针返回到开始位置，然后重复第1步，若仍失败则必须重复第2步。此时一定能找到淘汰页面。n特点：减少了磁盘I/O次数，但算法本身开销增加。最不常用算法（LFU）n最不常用算法选择到当前时间为止访问次数最少的页淘汰。n该算法要求为每页设置一个访问计数器，每当页被访问时，该页的访问计数器加1。发生缺页中断时，淘汰计数值最小的页面，并将所有计数器清零。页面缓冲算法n页面缓冲（Page-Buffering）算法是FIFO算法的发展。n页面缓冲置换算法采用FIFO选择被置换页面，选择出的页面不是立即换出，而是放入两个链表之一。页面缓冲算法描述n算法采用FIFO选择淘汰页，规定将淘汰页放入两个链表之一：n空闲链：页面未修改则放入空闲链末尾n修改链：页面已修改则放入修改链末尾n当需要访问一个页面时，若该页在上述两个队列中，则只要将该页面从队列中移出，否则用空闲链的第一个物理块装入该页。当修改链中的页面数达到一定值时，再将它们一次写回磁盘，然后将它们加入空闲页面链表中。6.2.6页面大小选择与影响缺页率因素n页面大小的选择涉及诸多因素，需要在这些因素之间权衡利弊。n页内碎片问题：页面越大，碎片越大。依此应选择小页面。n内外存传输：大小页面传输时间基本相同，依此应选择大页面。n页表大小：页面越小，页表越长。依此应选择大页面。n页面大小与主存关系：主存大则页面大。页面大小选择的分析n设系统内每个进程的平均长度为s，页面大小为p，每个页表项需e个字节。n每个进程页表长度：s/pn每进程碎片的平均大小：p/2n每进程浪费的空间为：se/p+p/2n页表占用空间：se/pn对p求导数：=1/2-se/p2n令导数为0求最小值：1/2s-e/p2=0n则页面大小为：p=2es时，f最小。页面大小选择的分析（续）n考虑其他因素，商用计算机的页面尺寸多在512B到8KB之间。影响缺页率的因素n主存块数：分配的主存块数越多，缺页率越低n页面大小：在页面数一定的情况下，页面大则缺页率低。n页面置换算法：页面置换算法的优劣影响缺页中断率n程序特性：好的程序结构可以降低缺页率。程序结构对缺页率影响例n设页面大小为128字节，二维数组为128128，初始时未装入数据，需将数组初始化为0。若数组按行存放，问下述两个程序段的缺页率各为多少？n程序1 程序2 short int a128128；for(j=0;j=127;j+)for(i=0;i=127;i+)for(i=0;i=127;i+)for(j=0;j=127;j+)aij=0;aij=0;程序1的缺页次数n因数组以行为主存放，页面大小为128字节，故每行占一个页面。n程序1的内层循环将每行中的指定列置为0，故产生128次中断。n外层循环128次，总缺页次数为128128。n程序1 short int a128128；for(j=0;j=127;j+)for(i=0;i=127;i+)aij=0;程序2的缺页次数n因数组以行为主存放，页面大小为128字节，故每行占一个页面。n程序2的内层循环将每行的所有列置为0，故产生1次中断。n外层循环128次，总缺页次数为128。n程序2 short int a128128；for(i=0;i=127;i+)for(j=0;j=127;j+)aij=0;6.2.7 工作集理论和抖动n工作集（Working-Set）：指在某段时间间隔里，进程实际访问的页面集合，具体地说便是把某进程在时间t-到t之间所访问的页面集合记为w(t，)，把变量称为工作集窗口尺寸。n为使进程能有效运行，减少缺页率，就必须使进程的工作集全在内存中。抖动 Thrashingn抖动：如果运行进程的大部分时间都用于页面的换入/换出，而几乎不能完成任何有效的工作，则称此进程处于抖动状态。抖动又称为颠簸、颤动。n抖动分为：n局部抖动n全局抖动CPU利用率与多道程序度的关系n左图是CPU利用率与程序道数的关系。n开始时CPU利用率会随着程序道数的增加而增加，当程序道数增加到一定数量以后，程序道数的增加会使CPU的利用率急剧下降。0CPU利用率多道程序度抖动产生的原因n抖动产生的原因有：n进程分配的物理块太少n置换算法选择不当n全局置换使抖动传播抖动的发现n抖动发生前会出现一些征兆，可利用这些征兆发现抖动并加以防范。这些技术有：n全局范围技术nL=S准则n利用缺页率发现抖动n平均缺页频率全局范围技术n全局范围技术采用时钟置换算法，用一个计数器C记录搜索指针扫描页面缓冲的速度。n若C的值大于给定的上限值，说明缺页率太高（可能抖动）或找不到可供置换的页面，这时应减少程序道数。n若C小于给定的下限值，表明缺页率小或存在较多可供置换的页面，这时应增加程序的道数。L=S准则n实际证明，产生缺页的平均时间L等于系统处理缺页的平均时间S时，CPU的利用率达到最大。n当LS时，表明系统频繁缺页，CPU利用率低，会导致系统抖动。利用缺页率发现抖动n下图是缺页率与进程分得物理块数之间的关系。当缺页率超过上限时会引起抖动，因此应增加分配给进程的物理块；此时每增加一个物理块，其缺页率明显降低；当进程缺页率达到下限值时，物理块的进一步增加对进程缺页率的影响不大。缺页率物理块上限下限缺页率算法n缺页率算法是一种直接的控制抖动方法。该方法要求为每页设一个使用位，当该页被访问时，相应位置1。同时设计一个计数器，记录自上次进程产生缺页以来进程执行的时间。n方法1：设置一个阈值F，如最近两次缺页时间间隔小于F，则分配一个物理块给该进程；否则淘汰使用位为0的页，并减少该进程的物理块数，同时将该进程的剩余页使用位重置为0。缺页率算法（续）n方法2：设置两个阈值，当缺页率达到上限值时为进程增加物理块，当缺页率达到下限值时减少进程的物理块。n缺页率算法的缺点：当进程由一个局部转移到另一个局部时，在原局部中的页面未移出内存之前，连续的缺页会导致该进程在内存的页面迅速增加，产生对内存请求的高峰。平均缺页频率n设ti为两次缺页之间的间隔时间，fi为其缺页频率，则有：fi=1/tin设F为平均缺页频率，则有：n F=（f1+f2+fn）/nn当F大于系统中规定的允许缺页频率时，则说明系统中缺页率过高，有可能引起抖动。抖动的预防及解除n采用局部置换策略可以防止抖动传播n利用工作集模型防止抖动：给进程分配工作集所需的物理块。n挂起进程来解决抖动。n选择挂起进程的条件n优先级最低：符合进程调度原则n发生缺页中断的进程：内存不含工作集，缺页时应阻塞n最后被激活的进程：工作集可能不在内存n最大的进程：可释放较多空间请求页式系统的内存访问流程访内存操作的三种情况访内存操作的三种情况n页在主存中且页表项在快表中：页在主存中且页表项在快表中：访问时间访问时间=查快表时间查快表时间+访问内存时间访问内存时间=+t。n 页在主存中且页表项不在快表中：页在主存中且页表项不在快表中：访问时间访问时间=查快表时间查快表时间+查页表时间查页表时间+修改快表时间修改快表时间+访问内存时间访问内存时间=+t+t=2(+t)n页不在主存中，设处理缺页中断的时间为页不在主存中，设处理缺页中断的时间为t1（包含读入缺页、页表更新、快表更新时间）（包含读入缺页、页表更新、快表更新时间）：访问时间访问时间=查快表时间查快表时间+查页表时间查页表时间+处理缺页中断处理缺页中断时间时间t1+查快表时间查快表时间+访问内存时间访问内存时间=+t+t1+t=t1+2(+t)有效访问时间n内存的读写周期为t，缺页中断服务时间为tl（包含读入缺页、页表更新、快表更新时间），“快表”的命中率为，缺页中断率为f，快表访问时间为，则有效存取时间可表示为：nEAT=*(+t)+(1-)*(1-f)*2(+t)+f*(tl+2(+t)缺页中断处理时间n缺页中断处理时间由三部分组成：n缺页中断服务时间n页面传送时间：包括读缺页和写置换页的时间n进程重新执行时间n由于缺页中断服务时间及进程重新执行时间较短，这里仅考虑页面传送时间。6.2.8 页的共享与保护n在分页存储管理系统中，信息的共享是通过使多个进程页表项指向同一个物理块来实现的。n分页存储管理采用两种方式保护内存：n地址越界保护：页表长度与逻辑地址中的页号比较n存取控制保护：在页表中增加保护位分页系统中信息共享示意图0216061707180 ed1 ed40 data1 data10进程1 ed1 ed40 data1 data10进程2 21 60 61 70页表 21 60 71 80页表 ed1 ed40 data1 data10 data1 data10主存6.3 请求分段存储管理n请求分段存储管理是另一种实现虚拟存储器的方法。6.3.1 请求分段的实现思想n请求分段存储管理系统基于分段存储管理，是在分段存储管理系统的基础上，增加了请求调段、分段置换功能所形成的一种虚拟存储系统。n在请求分段存储管理中，作业运行之前，只要求将当前需要的若干个分段装入主存，便可启动作业运行。在作业运行过程中，若所要访问的分段不在主存，则通过调段功能将其调入，同时还可以通过置换功能将暂时不用的分段换出到外存上，以便腾出内存空间。请求分段的支持机构n请求分段的支持机构有：n段表n缺段中断机构n地址变换机构n请求调段和分段置换软件段表结构段表结构n请求分段系统中使用的主要数据结构仍然是段表。n由于每次只将作业的一部分调入内存，还有一部分内容存放在磁盘上，故需扩充段表表项，扩充后的段表项如下所示：段表项中各字段的说明n段号、段长和段基址：其定义同分段存储管理。n存取方式：标识该分段的存取方式：读、写、执行。n访问字段：记录该段在一段时间内被访问的次数。n修改位：表示该段调入内存后是否被修改过。n存在位：表示该段是否在主存中。n增补位：指出该段在运行过程中，是否作过动态增长。n外存地址：指出该段在外存上的地址。段号段号段长段长段基段基址址存存 取取 方方 式式访问访问字段字段修改修改位位存在存在位位增补增补位位外存外存地址地址缺段中断处理缺段中断处理n在请求分段系统中，每当所访问的段不在内存时，便产生一个缺段中断信号，请求OS将所缺分段调入内存。n缺段中断与缺页中断类似，也是在指令执行期间产生和处理。缺段中断处理流程缺段中断处理阻塞请求进程唤醒请求进程内存中有合适的空闲区吗？N拼接以形成合适的空闲区从外存读入缺段Y修改段表及内存空闲区链NY空闲区容量总和能否满足淘汰实段以形成合适的空闲区返回缺段中断涉及的几个问题n内存管理：请求分段的内存管理与与分区管理类似，采用连续内存管理方式。n段的置换：调入缺段时，若有足够的空闲分区则直接调入，否则查看空闲区之和能否满足要求，若能则进行拼接，否则进行置换。置换时可能要淘汰多段。动态地址变换 n请求分段系统的地址变换是在分段系统地址变换的基础上形成的。n在地址变换过程中，若段在内存则判断其存取权限是否合法，若合法则从段表中取出该段在内存的起始地址，与段内位移相加形成访问内存的物理地址。n若段不在内存，则产生缺段中断信号，请求OS将缺段调入内存，然后修改段表，再利用段表进行地址变换。请求分段的地址变换过程 程序请求访问一段程序请求访问一段段号段号段表长度段表长度,段内位移段内位移 段长？段长？NY符合存取方式？符合存取方式？Y返回返回分段在主存中？分段在主存中？N形成物理地址形成物理地址分段越界处理分段越界处理NY修改访问位和修改位修改访问位和修改位分段保护处理分段保护处理缺段中断处理缺段中断处理引入快表提高访问速度n与请求分页管理一样，请求分段的地址变换过程必须访问内存两次以上。n为提高访问速度，也可以使用快表。6.3.2 段的共享与保护n在分段存储管理系统中，信息的共享是通过使多个进程的段表项指向同一内存区域实现的。n为了实现分段共享，可在系统中设置一张共享段表，所有共享分段都在其中占有一表项。共享段表的格式如下：共享段表及表项n共享进程计数：记录有多少进程共享该段。n存取控制字段：对同一共享段，不同进程有不同的操作权限。n段号：共享段在不同进程中有不同的段号。共享段表共享段表 共享段表项共享段表项 段名段名 段长段长 内存地址内存地址 状态状态 外存地址外存地址 共享进程计数共享进程计数count 状态状态 进程名进程名 进程号进程号 段号段号 存取控制存取控制 表项表项1 1表项表项2 2表项表项n n共享段的分配n当为共享段分配内存时，对第一个请求使用该段的进程，系统为该共享段分配一个内存区，再将该共享段调入，同时将该区的始址填入请求进程的段表，还需在共享段表中增加一项，填写有关数据并将count置1。n此后，当又有其他进程申请使用该共享段时，只需将count加1并填写有关数据结构。共享段的回收n当某进程不再需要使用共享段时，应释放该段。此时应将该进程段表中共享段的对应表项撤消，并将count减1，若结果为0则需要系统回收共享段的物理内存及有关表项，否则仅取消该进程在共享段中的记录。可重入代码n可重入代码又称为纯代码，是允许多个进程同时访问的代码。可重入代码在执行中不能修改。6.3.3 虚拟段页式存储管理系统n虚拟段页式存储管理系统是虚拟页式和虚拟段式存储管理的结合。习题习题nP150n3（1）n3（2）n3（3）n3（4）选择题1n实现虚拟存储器的目的是 _。A.实现存储保护 B.扩充辅存容量C.扩充内存容量 D.实现程序浮动n页式虚拟存储管理的主要特点是 _。A.不要求将作业装入到内存的连续区域B.不要求将作业同时全部装入到内存的连续区域C.不要求进行缺页中断处理D.不要求进行页面置换选择题2n作业在执行中发生了缺页中断，经操作系统处理后，应让其执行 _ 指令。A.被中断的前一条 B.被中断的后一条 C.被中断的那条 D.启动时的第一条n虚拟存储管理系统的基础是程序的 _ 理论。A.虚拟性 B.全局性C.局部性 D.动态性 选择题3n在以下存储管理方案中，属于虚拟存储器管理的是 _。A.请求分页存储管理 B.分段存储管理C.段页式存储管理 D.可重定位分区分配n由于实现_页面置换算法的成本高，通常使用一种近似的页面置换算法 算法。A.Optimal LRU B.LRU Clock C.FCFS Clock D.Clock 改进的Clock选择题4n会产生Belady异常现象的页面置换算法是_。A最佳页面置换算法最佳页面置换算法 B先进先出页面置换算法先进先出页面置换算法 C最近最久未使用置换算法最近最久未使用置换算法 D最少使用页面置换算法最少使用页面置换算法n在请求分页存储管理系统中，下述_策略是不适用的 A固定分配局部置换 B固定分配全局置换 C可变分配全局置换 D可变分配局部置换选择题5n二次机会置换算法与简单时钟置换算法在决定淘汰哪一页时，都用到了_。A快表 B引用位 C修改位 D存在位n请求段页式系统_。A是以页为单位管理用户的虚空间，以段为单位管理内存空间。B是以段为单位管理用户的虚空间，以页为单位管理内存空间。C是以连续的内存区存放每个段。D为提高内存利用率，允许用户使用大小不同的页。填空题1n在请求页式存储管理系统中，常用的页面淘汰算法有：，选择淘汰不再使用或最远的将来才使用的页；，选择淘汰在内存驻留时间最长的页。n程序运行时的局部性表现为：和 。n虚拟存储器的特点是 、。填空题2n所谓虚拟存储器是指具有 和 功能，能从逻辑上对内存容量进行扩充的一种存储器系统。n虚拟存储器的实现方法有三种 、和 。n在请求页式系统中，当访问的页不在主存时，由 将该页调入内存；当主存无空闲块时，必须 一页。UNIX存储管理n在早期的UNIX系统中，为提高内存的利用率，已提供了内存与外存之间的进程对换机制。n在UNIX SYSTEM 中，除对换功能外还支持请求调页的存储管理方式。每个页面的大小随版本不同而异，一般在512B4KB之间。请求调页管理的数据结构n在UNIX系统中，为实现请求调页，核心配置了四种数据结构：n页表n磁盘块描述表n页面数据表n对换使用表页表页表n每个页表项中需包含以下字段：n物理块号。即页在内存中的物理块号。n年龄。记录该页在内存中有多长时间未访问。n访问位。指示该页最近是否被访问过。n修改位。指示该页内容是否被修改过。n有效位。指示该页内容是否有效。n写时拷贝位。指示进程修改该页时，是否要为该页建立拷贝。n保护位。指示该页允许的访问方式，如只读、读写。磁盘块描述表磁盘块描述表n在UNIX系统中，每个页表项对应一个磁盘块描述项，记录页面的磁盘拷贝所在的磁盘块号。磁盘块描述项中包含：n对换设备号：页面副本所在设备号。n块号：页面副本所在块号。n类型：页面副本在可执行文件中时类型为File，在对换设备上时类型为Disk。页表表项和磁盘块描述项 页表表项页表磁盘块描述表页面物理地址 年龄 有效位 访问位 修改位 写时拷贝位 保护位区页表表项 磁盘块描述项磁盘块描述项 对换设备号 块号 类型（对换、文件）页面数据表页面数据表n页面数据表项描述内存中的一个物理块，包含：n页状态。指示页面拷贝是在对换设备上还是在可执行文件中。n内存引用计数。指出引用该页面的进程数目。n逻辑设备。指出含有该页面拷贝的逻辑设备和块号。n空闲页面链指针和散列队列指针。n为分配一个物理块，核心从空闲链表首部摘下一个空闲页表项，修改其对换设备号和块号后，将它放到相应的散列队列中。对换使用表对换使用表n对换设备上的每一块都占有对换使用表中的一个表项。n表项中含有一个引用计数，表示有多少页表项指向该块。四种数据结构间的关系 n一个进程的虚地址为1493K，其物理页为794，其拷贝在对换设备1的2743号块中。页号 794 对换设备1 块号2743页表项 磁盘块描述项对换使用表项块号2743引用数1对换设备1引用数1物理页794对换设备块2743页面数据表项794虚地址1493K偷页进程nUNIX系统中设置了一个偷页进程，其主要任务是：n每隔一定时间增加内存中所有有效页的年龄；n当有效页的年龄达到规定值后便将它换出。增加有效页年龄增加有效页年龄n设用两位作为年龄域，当页面的年龄为0、1、2时，页面处于不可换出状态；而当其年龄达到3时，便可将它换出内存。n当内存中的空闲页面数低于某规定的下限时，核心唤醒偷页进程去检查内存中的每一个活动区，对所有有效页的年龄字段加1。n对于那些年龄字段已增至3的页面便不再加1，而是将它们换出。每当有进程访问了某个页面时，便将该页的年龄设置为0。有效页年龄的变化1在内存 0时间页被换出页被访问不在内存页状态12023上次访问以来对换出页的几种处理方式对换出页的几种处理方式(1)n若对换设备上有换出页的拷贝且换出页的内容未修改，则只需将页表项的有效位清零，并将页面数据表项中的引用数减1，再将该页表项放入空闲页面链表中。对换出页的几种处理方式对换出页的几种处理方式(2)n若对换设备上没有换出页的拷贝，则应将该页写到对换设备上。n通常偷页进程先将要换出的页链到一个链表上，当换出页面链上的页数达到某一规定值时，核心才真正将这些页面换出。对换出页的几种处理方式对换出页的几种处理方式(3)n在对换设备上已有换出页的副本，但该页内容已被修改过。此时核心将该页在对换设备上原来占有的空间释放，再重新将该页拷贝到对换设备上。将换出页面写到对换设备上将换出页面写到对换设备上n当换出页面链上的页数达到规定值时，核心先为这些页分配连续的对换空间以便将它们换出；n当核心向对换设备上写一个页面时，应首先清除该页表项的有效位，并将对应页面数据表项中的引用数减1。n若引用计数为0，表明已无进程引用该页，核心便将其页面数据表项链入空闲页面链表的尾部。n最后，核心将分配给该页的对换空间地址填入相应的磁盘块描述项中，并将对换使用表中的计数加1。将换出页面写到对换设备上例将换出页面写到对换设备上例n例如偷页进程以A、B、C、D的顺序检查进程的页面，并准备分别将进程A、B、C和D的30、40、50和20个页面换出，每64个页面为一批。下图给出了页面的换出过程和对换空间的分配情况。进程B 34页进程A 30页 A30 B34 B6 C50 D8 进程C 50页进程B 6页进程D 8页进程D 12页请求调页n当一个进程存取一个有效位为0的页面时将产生一个有效性错。此时由核心调用有效性错处理程序加以处理。可能有下列两种情况：n若在磁盘块描述项中找不到所缺的页，则表明此次内存访问非法，核心将向该进程发出一个“段违例”软中断信号。n若找到了所缺的页，表明此次内存访问合法；核心为该页分配一个内存块，并将所缺的页调入内存。缺页在可执行文件中缺页在可执行文件中n如果页面对应的磁盘块描述项中的类型是File，表示缺页在可执行文件中。n其具体的调入过程为：根据该文件所对应的系统区表项中的索引节点指针，找到该文件的索引节点；再从磁盘块描述项中找到该页的逻辑块号，以此作为偏移量查找索引节点中的磁盘块号表，便可找到该页所在的磁盘块号，再将该页调入内存。缺页在可执行文件中例缺页在可执行文件