最新【考研计算机专业课】武汉大学操作系统PPT课件 第6章 虚拟存储器(共142张PPT课件).pptx

《最新【考研计算机专业课】武汉大学操作系统PPT课件 第6章 虚拟存储器(共142张PPT课件).pptx》由会员分享，可在线阅读，更多相关《最新【考研计算机专业课】武汉大学操作系统PPT课件 第6章 虚拟存储器(共142张PPT课件).pptx（142页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第6章章 虚拟存储器虚拟存储器n常规存储器管理方式(fngsh)要求作业运行前全部装入内存，作业装入内存后一直驻留内存直至运行结束。n这种存储管理方式限制了大作业的运行。而物理扩充内存会增加成本，故应从逻辑上扩充内存。第一页，共一百四十二页。6.1 虚拟存储器概念虚拟存储器概念(ginin)n虚拟存储器（Virtual Memory）的理论基础是程序执行时的局部性原理。n局部性原理是指程序在执行过程中一个较短时间内，程序所执行的指令地址和操作数地址分别局限于一定(ydng)区域内。n例如：n除转移和过程调用外，程序主要是顺序执行。n过程调用使程序从一部分区域转至另一部分区域n循环结构第二页，

2、共一百四十二页。局部性的体现(txin)n局部性体现为：n时间(shjin)局部性：一条指令的一次执行和下次执行，一个数据的一次访问和下次访问，都集中在一个较短时间(shjin)内。n空间局部性：当前执行的指令和将要执行的指令，当前访问的数据和将要访问的数据，都集中在一个较小范围内。第三页，共一百四十二页。虚拟存储器的基本原理n在程序运行之前，将程序的一部分放入内存后就启动程序执行。n在程序执行过程中，当所访问的信息不在内存时，由操作系统将所需要(xyo)的部分调入内存，然后继续执行程序。n另一方面，操作系统将内存中暂时不使用的内容换出到外存上，从而腾出空间存放将要调入内存的信息。n从效果上看

3、，这样的计算机系统好像为用户提供了一个存储容量比实际内存大得多的存储器，将这个存储器称为虚拟存储器。第四页，共一百四十二页。虚拟存储器n虚拟存储器是指具有请求调入和置换功能，能从逻辑上对内存容量加以(jiy)扩充的一种存储器系统。n虚拟存储器是一种以时间换空间的技术。第五页，共一百四十二页。虚拟存储器的特征(tzhng)n离散性：不连续内存分配n多次性：一个作业分多次装入内存n对换性：允许运行(ynxng)中换进换出n虚拟性：逻辑上扩充内存第六页，共一百四十二页。虚拟存储器的本质(bnzh)n虚拟存储器的本质是将程序的访问地址和内存的可用地址分离，为用户提供(tgng)一个大于实际主存的虚拟存

4、储器。n虚拟存储器的容量受限于：n地址结构n外存容量第七页，共一百四十二页。实现(shxin)虚拟存储技术的物质基础n相当数量的外存：足以存放多个(du )用户的程序。n一定容量的内存：在处理机上运行的程序必须有一部分信息存放在内存中。n地址变换机构：动态实现逻辑地址到物理地址的变换。第八页，共一百四十二页。虚拟存储器的实现(shxin)方法n常用的虚拟存储技术有：n请求分页存储管理n请求分段存储管理n具有请求调页功能(gngnng)的段页式存储管理系统第九页，共一百四十二页。6.2 请求分页存储管理-6.2.1n请求分页存储管理方法是在分页存储管理的基础上增加了请求调页和页面置换功能。n实现

5、思想：在作业运行之前只装入当前需要的一部分页面便启动作业运行。在作业运行过程中，若发现所要访问的页面不在内存，便由硬件产生缺页中断，请求OS将缺页调入内存。若内存无空闲存储空间，则根据某种置换算法淘汰(toti)已在内存的某个页面，以腾出内存空间装入缺页。第十页，共一百四十二页。请求分页系统中的支持请求分页系统中的支持(zhch)机构机构n请求分页中的支持机构有：n页表n缺页中断机构n地址变换机构n请求调页和页面置换(zhhun)软件第十一页，共一百四十二页。6.2.2 页表n请求分页系统中使用的主要数据结构仍然是页表。n但由于每次只将作业的一部分调入内存，还有一部分内容存放(cnfng)在磁

6、盘上，故需要在页表中增加若干项。n扩充后的页表项如下所示： 第十二页，共一百四十二页。扩充(kuchng)后的页表项n页号和物理块号：其定义同分页存储管理。n状态位：用于表示该页是否在主存中。n访问(fngwn)字段：用于记录本页在一段时间内被访问(fngwn)的次数，或最近已有多长时间未被访问(fngwn)。n修改位：用于表示该页调入内存后是否被修改过。n外存地址：用于指出该页在外存上的地址。 页号页号 物理块号物理块号 存在位存在位 访问字段访问字段修改位修改位 外存地址外存地址第十三页，共一百四十二页。6.2.3 缺页中断缺页中断(zhngdun)与地址变与地址变换换n在请求分页系统中，

7、当所访问的页不在内存时，便产生缺页中断，请求OS将缺页调入内存。n缺页中断处理程序根据该页在外存的地址把它调入内存。在调页过程中，若内存有空闲空间，则缺页中断处理程序只需把缺页装入并修改(xigi)页表中的相应项；若内存中无空闲物理块，则需要先淘汰内存中的某些页，若淘汰页曾被修改(xigi)过，则还要将其写回外存。第十四页，共一百四十二页。缺页中断与一般缺页中断与一般(ybn)中断的区别中断的区别n缺页中断与一般中断的区别主要有：n在指令的执行(zhxng)期间产生和处理缺页中断。n一条指令可以产生多个缺页中断。如：执行一条复制指令copy A to Bn缺页中断返回时执行产生中断的指令，一般

8、中断返回时执行下条指令B:A:CopyAToB页面(ymin)654321第十五页，共一百四十二页。地址变换n请求分页存储管理系统的地址变换过程类似于分页存储管理，但当被访问(fngwn)页不在内存时应进行缺页中断处理。第十六页，共一百四十二页。地址变换流程(lichng)程序(chngx)请求访问一页页号页表长度(chngd)？页在内存？YNCPU检索快表Y修改快表页表项在快表中？产生缺页中断N访问页表越界中断NY修改访问位和修改位形成物理地址A第十七页，共一百四十二页。缺页处理(chl)流程缺页中断(zhngdun)处理保留(boli)CPU现场该页被修改否？从外存中找到缺页N将该页写回外

9、存内存满否？Y选择一页换出NY从外存读缺页入内存修改页表A第十八页，共一百四十二页。6.2.4 页面页面(y min)分配和置换策略分配和置换策略 n在为进程分配在为进程分配(fnpi)物理块时应确定物理块时应确定:n进程需要的最少物理块数进程需要的最少物理块数n进程的物理块数是固定还是可变进程的物理块数是固定还是可变n按什么原则为进程分配物理块数按什么原则为进程分配物理块数第十九页，共一百四十二页。最小物理最小物理(wl)块数的确定块数的确定n最小物理块数是指能保证进程(jnchng)正常运行所需的最少物理块数，若小于此值进程(jnchng)无法运行。n一般情况下：n单地址指令且采用直接寻址

10、，则所需最少物理块数为2。n若单地址指令且允许采用间接寻址，则所需最少物理块数为3。n某些功能较强的机器，指令及源地址和目标地址均跨两个页面，则最少需要6个物理块。第二十页，共一百四十二页。 页面页面(y min)分配和置换策略分配和置换策略 n页面分配常采用固定分配和可变分配两种策略。n页面置换也有全局(qunj)置换和局部置换两种策略。n将分配策略和置换范围组合可得如下三种策略：n固定分配局部置换n可变分配全局置换n可变分配局部置换第二十一页，共一百四十二页。固定分配(fnpi)局部置换n固定分配局部置换：基于某种原则为每个进程分配固定数量的物理块，当进程运行中出现缺页时，只能从自己的页面

11、中选择一页换出，然后再调入缺页。n实现(shxin)这种策略的困难在于：难以确定应为每个进程分配多少个物理块。第二十二页，共一百四十二页。可变分配全局(qunj)置换n可变分配全局置换：先为系统中的每个进程分配一定(ydng)数量的物理块，操作系统本身也保持一个空闲物理块队列。当某进程发生缺页时，由系统从空闲物理块队列中取出一个物理块分配给该进程；当空闲物理块队列中的物理块用完时，操作系统才从内存中选择一页调出，该页可以是系统中任何一个进程的页面。n这是一种容易实现的页面分配和置换策略，目前已用于若干操作系统中。第二十三页，共一百四十二页。可变分配局部(jb)置换n可变分配局部置换：根据某种原

12、则(yunz)为每个进程分配一定数量的物理块，当进程发生缺页中断时，只允许从该进程的页面中选出一页换出。如果某进程的缺页率较高，则系统再为该进程分配若干物理块；反之若某进程的缺页率特别低，则系统可适当减少分配给该进程的物理块数。n该算法比较复杂，但性能较好。第二十四页，共一百四十二页。物理块分配物理块分配(fnpi)算法算法n物理块分配(fnpi)是指按什么原则给进程分配(fnpi)物理块数，通常有以下几种分配(fnpi)算法：n平均分配算法：将系统中所有可供分配物理块平均分配给每个进程。n按比例分配算法：根据进程大小按比例分配物理块。n按优先级分配算法：有两种实现方案n将可供分配的物理块分为

13、两部分，一部分按比例分配给每个进程，另一部分根据进程的优先级适当增加物理块。n先按比例为进程分配物理块，当高优先级进程发生缺页时，允许它从低优先级进程处获得物理块。第二十五页，共一百四十二页。6.2.5 页面置换页面置换(zhhun)算法算法n页面置换(zhhun)（ Page Replacement ）算法又称为页面淘汰算法，是用来选择换出页面的算法。n下面介绍几种比较常用的页面置换算法 。第二十六页，共一百四十二页。1最佳(zu ji)置换算法（OPT）n最佳（Optimal）算法是从内存中选择将来最长时间不会使用的页面(y min)予以淘汰。n特点：因页面访问的未来顺序很难精确预测，该算

14、法具有理论意义，可以用来评价其他算法的优劣。第二十七页，共一百四十二页。最佳置换(zhhun)算法例n假定系统(xtng)为某进程分配了3个物理块，页面访问序列为：1、2、3、4、1、2、5、1、2、3、4、5，开始时3个物理块均为空闲，采用最佳置换算法时的页面置换情况如下所示：第二十八页，共一百四十二页。采用(ciyng)最佳置换算法的页面置换情况n从上表中可以看出(kn ch)，共发生了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走向(zux

15、ing)第二十九页，共一百四十二页。2. 先进先出算法(sun f)（FIFO）n先进先出（ First-In-First-Out ）算法是选择调入主存时间最长的页面予以淘汰。n特点：该算法实现比较简单，对按线性顺序访问的程序比较合适，但可能产生异常现象。很少使用纯粹的FIFO。nBelady现象：在某些情况下，分配给进程的页面数增多(zn du)，缺页次数反而增加。第三十页，共一百四十二页。先进先出置换(zhhun)算法例n假定系统为某进程分配了3个物理块，页面(ymin)访问序列为：1、2、3、4、1、2、5、1、2、3、4、5，开始时3个物理块均为空闲，采用先进先出置换算法时的页面置换情

16、况如下所示：第三十一页，共一百四十二页。采用先进先出算法的页面置换(zhhun)情况n从上表中可以看出，共发生(fshng)了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走向(zuxing)第三十二页，共一百四十二页。为进程分配(fnpi)4个物理块n从上表中可以看出(kn ch)，共发生了10次缺页中断。其缺页率为10/1283.3% 。 3 3 3 4 4 4 4 块4缺 2 5 4 5缺 2 1 4 4缺 2 1

17、 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走向(zuxing)第三十三页，共一百四十二页。无异常现象的页面(y min)序列n假定系统(xtng)为某进程分配了3个物理块，页面访问序列为：7、0、1、2、0、3、0、4、2、3、0、3，开始时3个物理块均为空闲，采用先进先出置换算法时的页面置换情况如下所示：第三十四页，共一百四十二页。页面置换(zhhun)情况n从上表中可以(ky)看出，共发生了10次缺页中断。其缺页率为10/1283.3% 。 3缺 3 2 0 0缺 3 2 4 3缺 0

18、 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走向(zuxing)第三十五页，共一百四十二页。为进程分配(fnpi)4个物理块n从上表中可以(ky)看出，共发生了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走向(zuxing)第三十六页，共一百四十二页。3.最近最久未使用(shyng)置换算法(LRU)n最近最久未使用算

19、法选择最近一段时间内最长时间没有被访问过的页面予以淘汰。n为此(wi c)，应赋予每个页面一个访问字段，用于记录页面自上次访问以来所经历的时间。nLRU是Least Recently Used，也称为最近最少使用第三十七页，共一百四十二页。LRU算法(sun f)例n假定系统(xtng)为某进程分配了3个物理块，页面访问序列为：1、2、3、4、1、2、5、1、2、3、4、5，开始时3个物理块均为空闲，采用LRU置换算法时的页面置换情况如下所示：第三十八页，共一百四十二页。采用LRU算法(sunf)的页面置换情况n从上表中可以(ky)看出，共发生了10次缺页，其缺页率为10/1283.3% 。缺

20、 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走向(zuxing)第三十九页，共一百四十二页。为进程分配(fnpi)4个物理块n从上表中可以(ky)看出，共发生了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走向(zuxing)第四十页，共一百四十二页。LRU算

21、法(sun f)的实现nLRU算法实现时需要较多的硬件支持，以记录进程中各页面自上次访问以来有多长时间未被访问。下面介绍几种(j zhn)实现方法。n链表法n计数器法第四十一页，共一百四十二页。链表法n用一个单链表保存当前进程所访问(fngwn)的各页面号，刚使用过的页面放表尾，则表头一定是最近最久未使用的页面。n实现思想为：n当分配给进程的物理块未用完时，则将进程装入内存的页面按先后顺序构成一个链表n当进程访问的页面在内存时，将页面从链表中移出放到表尾n当进程访问的页面不在内存时，则发生缺页中断，将表头页面置换第四十二页，共一百四十二页。链表法例(f l)n例如：设分配给某进程4个物理块，页

22、面访问(fngwn)序列为：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，定时器每隔一定(ydng)时间将计数器右移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

23、 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最近(zujn)最久未使用的页是？7 0 0 0 0 0 1 1 1第四十五页，共一百四十二页。4. 其他(qt)页面置换算法-二次机会算法n二次机会（ Second-Chance ）算法是FIFO算法的改进，以避免将经常使用的页面淘汰掉。为此设置了页面引用位。n算法思想：使用FIFO算法选择一页淘汰时，先检查该页的引用位，如果是0就立即淘汰该页，如果是1就给它第二次机

24、会，将其引用位清0，并将它放入页面链的末尾(mwi)，将其装入时间置为当前时间，然后选择下一个页面。第四十六页，共一百四十二页。简单(jindn)时钟（clock）算法n简单时钟置换算法既是对二次机会算法的改进，也是对LRU算法的近似。该算法也要求为每页设置一个访问位。n实现思想：将页面排成一个循环队列，类似于时钟表面，并使用一个置换指针。当发生缺页时，检查(jinch)指针指向的页面，若其访问位为0则淘汰该页，否则将该页的访问位清0，指针前移并重复上述过程，直到找到访问位为0的淘汰页为止。最后指针停留在被置换页的下一页上；n该算法也称为最近未使用（Not Recently Used，NRU）

25、算法。第四十七页，共一百四十二页。简单时钟置换算法简单时钟置换算法(sun f)页面链页面链块号块号 页号页号 访问访问(fngwn)位位 指针指针 0 1 2 4 0 3 4 2 1 5 6 5 0 7 1 1替 换替 换( t hun)指针指针第四十八页，共一百四十二页。简单时钟置换算法(sun f)流程入口(rku)指针(zhzhn)前进一步返回指针所指页面访问位=0？N选择该页面淘汰Y置页面访问位为0指针前进一步第四十九页，共一百四十二页。页面(y min)置换情况n从上表中可以看出，共发生(fshng)了9次缺页中断。其缺页率为9/1275% 。0*23* 3缺0* 2 4 0 3*

26、 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走向(zuxing) 1 0* 2*缺第五十页，共一百四十二页。改进的时钟改进的时钟(shzhng)算法算法n将一个修改过的页面换出需要写磁盘，其开销大于未修改页面。为此(wi c)在改进型时钟算法中应考虑页面修改情况。设R为访问位，U为修改位，将页面分为以下4种类型：n1类(R=0,U=0)：未被访问又未被修改n2类(R=0,U=1)：未被访问但已被修改n3类(R=1,U=0)：已被访问但未被修改n4

27、类(R=1,U=1)：已被访问且已被修改第五十一页，共一百四十二页。改进型时钟(shzhng)算法描述n从指针当前位置开始扫描循环队列，寻找R=0,U=0的页面，将满足条件的第一个页面作为淘汰页。n若第1步失败，则开始第2轮扫描，寻找R=0,U=1的页面，将满足条件的第一个页面作为淘汰页，并将所有经历过页面的访问位置0。n若第2步失败，则将指针返回到开始位置，然后重复第1步，若仍失败则必须重复第2步。此时一定能找到淘汰页面。n特点：减少(jinsho)了磁盘I/O次数，但算法本身开销增加。第五十二页，共一百四十二页。最不常用(chnyn)算法（LFU）n最不常用(chnyn)算法选择到当前时间

28、为止访问次数最少的页淘汰。n该算法要求为每页设置一个访问计数器，每当页被访问时，该页的访问计数器加1。发生缺页中断时，淘汰计数值最小的页面，并将所有计数器清零。第五十三页，共一百四十二页。页面(y min)缓冲算法n页面缓冲(hunchng)（ Page-Buffering ）算法是FIFO算法的发展。n页面缓冲置换算法采用FIFO选择被置换页面，选择出的页面不是立即换出，而是放入两个链表之一。第五十四页，共一百四十二页。页面缓冲(hunchng)算法描述n算法采用FIFO选择淘汰页，规定将淘汰页放入两个链表之一：n空闲链：页面未修改则放入空闲链末尾n修改链：页面已修改则放入修改链末尾n当需要

29、访问一个页面时，若该页在上述(shngsh)两个队列中，则只要将该页面从队列中移出，否则用空闲链的第一个物理块装入该页。当修改链中的页面数达到一定值时，再将它们一次写回磁盘，然后将它们加入空闲页面链表中。第五十五页，共一百四十二页。6.2.6页面大小选择(xunz)与影响缺页率因素n页面大小的选择涉及诸多因素，需要在这些因素之间权衡利弊。n页内碎片问题：页面越大，碎片越大。依此应选择小页面。n内外(niwi)存传输：大小页面传输时间基本相同，依此应选择大页面。n页表大小：页面越小，页表越长。依此应选择大页面。n页面大小与主存关系：主存大则页面大。第五十六页，共一百四十二页。页面大小(dxio)

30、选择的分析n设系统内每个进程的平均长度为s，页面大小(dxio)为p，每个页表项需e个字节。n每个进程(jnchng)页表长度：s/pn每进程碎片的平均大小：p/2n每进程浪费的空间为：se/p+p/2n页表占用空间：se/pn对p求导数：=1/2-se/p2n令导数为0求最小值：1/2s-e/p2=0n则页面大小为：p=2es时，f最小。第五十七页，共一百四十二页。页面大小选择(xunz)的分析（续）n考虑(kol)其他因素，商用计算机的页面尺寸多在512B到8KB之间。第五十八页，共一百四十二页。影响(yngxing)缺页率的因素n主存块数：分配的主存块数越多，缺页率越低n页面大小：在页面

31、数一定的情况下，页面大则缺页率低。n页面置换算法：页面置换算法的优劣(yu li)影响缺页中断率n程序特性：好的程序结构可以降低缺页率。第五十九页，共一百四十二页。程序结构对缺页率影响(yngxing)例n设页面大小为128字节(z ji)，二维数组为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;第六十页，共

32、一百四十二页。程序(chngx)1的缺页次数n因数组以行为主存放(cnfng)，页面大小为128字节，故每行占一个页面。n程序1的内层循环将每行中的指定列置为0，故产生128次中断。n外层循环128次，总缺页次数为128128。n程序(chngx)1 short int a128128； for (j=0;j=127;j+) for (i=0;i=127;i+) aij=0;第六十一页，共一百四十二页。程序(chngx)2的缺页次数n因数组以行为主存放，页面大小为128字节，故每行占一个页面。n程序2的内层循环(xnhun)将每行的所有列置为0，故产生1次中断。n外层循环128次，总缺页次数为

33、128。n程序(chngx)2 short int a128128； for (i=0;i=127;i+) for (j=0;j=127;j+) aij=0;第六十二页，共一百四十二页。6.2.7 工作集理论(lln)和抖动n工作集（ Working-Set）：指在某段时间间隔(jing)里，进程实际访问的页面集合，具体地说便是把某进程在时间t-到t之间所访问的页面集合记为w(t，)，把变量称为工作集窗口尺寸。 n为使进程能有效运行，减少缺页率，就必须使进程的工作集全在内存中。第六十三页，共一百四十二页。抖动(dudng) Thrashingn抖动：如果运行进程的大部分时间都用于页面的换入/换

34、出，而几乎不能完成任何有效的工作，则称此进程处于抖动状态。抖动又称为(chn wi)颠簸、颤动。n抖动分为：n局部抖动n全局抖动第六十四页，共一百四十二页。CPU利用率与多道程序度的关系(gun x)n左图是CPU利用率与程序(chngx)道数的关系。n开始时CPU利用率会随着程序道数的增加而增加，当程序道数增加到一定数量以后，程序道数的增加会使CPU的利用率急剧下降。0CPU利用率多道程序度第六十五页，共一百四十二页。抖动产生(chnshng)的原因n抖动产生的原因有：n进程(jnchng)分配的物理块太少n置换算法选择不当n全局置换使抖动传播第六十六页，共一百四十二页。抖动(dudng)的

35、发现n抖动发生前会出现一些征兆，可利用这些征兆发现(fxin)抖动并加以防范。这些技术有：n全局范围技术nL=S准则n利用缺页率发现抖动n平均缺页频率第六十七页，共一百四十二页。全局(qunj)范围技术n全局范围技术采用时钟置换算法(sun f)，用一个计数器C记录搜索指针扫描页面缓冲的速度。n若C的值大于给定的上限值，说明缺页率太高（可能抖动）或找不到可供置换的页面，这时应减少程序道数。n若C小于给定的下限值，表明缺页率小或存在较多可供置换的页面，这时应增加程序的道数。第六十八页，共一百四十二页。L=S准则(zhnz)n实际证明，产生缺页的平均时间L等于(dngy)系统处理缺页的平均时间S时

36、，CPU的利用率达到最大。n当LS时，表明系统频繁缺页，CPU利用率低，会导致系统抖动。第六十九页，共一百四十二页。利用(lyng)缺页率发现抖动n下图是缺页率与进程分得物理块数之间的关系。当缺页率超过上限时会引起抖动，因此应增加分配给进程的物理块；此时(c sh)每增加一个物理块，其缺页率明显降低；当进程缺页率达到下限值时，物理块的进一步增加对进程缺页率的影响不大。缺页率物理(wl)块上限下限第七十页，共一百四十二页。缺页率算法(sun f)n缺页率算法是一种直接的控制抖动方法。该方法要求为每页设一个使用位，当该页被访问时，相应位置1。同时设计一个计数器，记录自上次进程产生缺页以来进程执行的

37、时间。n方法1：设置一个阈值F，如最近两次缺页时间间隔小于F，则分配一个物理(wl)块给该进程；否则淘汰使用位为0的页，并减少该进程的物理(wl)块数，同时将该进程的剩余页使用位重置为0。第七十一页，共一百四十二页。缺页率算法(sun f)（续）n方法2：设置两个阈值，当缺页率达到上限值时为进程(jnchng)增加物理块，当缺页率达到下限值时减少进程(jnchng)的物理块。n缺页率算法的缺点：当进程由一个局部转移到另一个局部时，在原局部中的页面未移出内存之前，连续的缺页会导致该进程在内存的页面迅速增加，产生对内存请求的高峰。第七十二页，共一百四十二页。平均(pngjn)缺页频率n设ti为两次

38、缺页之间的间隔时间，fi为其缺页频率，则有： fi= 1/tin设F为平均缺页频率，则有：n F=（ f1+f2+fn）/nn当F大于系统(xtng)中规定的允许缺页频率时，则说明系统(xtng)中缺页率过高，有可能引起抖动。第七十三页，共一百四十二页。抖动的预防(yfng)及解除n采用局部置换策略可以防止抖动传播n利用工作集模型防止抖动：给进程分配工作集所需的物理块。n挂起进程来解决抖动。n选择挂起进程的条件n优先级最低：符合进程调度原则n发生缺页中断(zhngdun)的进程：内存不含工作集，缺页时应阻塞n最后被激活的进程：工作集可能不在内存n最大的进程：可释放较多空间第七十四页，共一百四十

39、二页。请求页式系统(xtng)的内存访问流程第七十五页，共一百四十二页。访内存操作的三种访内存操作的三种(sn zhn)情况情况n页在主存中且页表项在快表中：页在主存中且页表项在快表中：访问时间访问时间=查快表时间查快表时间+访问内存访问内存(ni cn)时间时间= +t。n 页在主存中且页表项不在快表中：页在主存中且页表项不在快表中：访问时间访问时间=查快表时间查快表时间+查页表时间查页表时间+修改快表时间修改快表时间+访问内存时间访问内存时间= +t+ +t=2( +t)n页不在主存中，设处理缺页中断的时间为页不在主存中，设处理缺页中断的时间为t1（包含读入缺页、页表更新、快表更新时间）（

40、包含读入缺页、页表更新、快表更新时间）：访问时间访问时间=查快表时间查快表时间+查页表时间查页表时间+处理缺页中断处理缺页中断时间时间t1+查快表时间查快表时间+访问内存时间访问内存时间= +t+t1+ +t=t1+2( +t)第七十六页，共一百四十二页。有效(yuxio)访问时间n内存的读写周期为t，缺页中断服务时间(shjin)为tl（包含读入缺页、页表更新、快表更新时间）， “快表”的命中率为，缺页中断率为f，快表访问时间为，则有效存取时间可表示为：nEAT= *( +t )+(1- )* (1-f) *2 ( +t ) +f*(tl+ 2 ( +t ) )第七十七页，共一百四十二页。缺

41、页中断(zhngdun)处理时间n缺页中断处理时间(shjin)由三部分组成：n缺页中断服务时间n页面传送时间：包括读缺页和写置换页的时间n进程重新执行时间n由于缺页中断服务时间及进程重新执行时间较短，这里仅考虑页面传送时间。第七十八页，共一百四十二页。6.2.8 页的共享与保护(boh)n在分页存储管理系统中，信息的共享是通过使多个进程页表项指向同一个物理块来实现的。n分页存储管理采用(ciyng)两种方式保护内存：n地址越界保护：页表长度与逻辑地址中的页号比较n存取控制保护：在页表中增加保护位第七十九页，共一百四十二页。分页系统(xtng)中信息共享示意图0216061707180ed1e

42、d40data1 data10进程(jnchng)1ed1 ed40data1 data10进程(jnchng)221 6061 70页表21 6071 80页表 ed1 ed40data1 data10data1 data10主存第八十页，共一百四十二页。6.3 请求(qngqi)分段存储管理n请求(qngqi)分段存储管理是另一种实现虚拟存储器的方法。第八十一页，共一百四十二页。6.3.1 请求分段的实现(shxin)思想n请求分段存储管理系统基于分段存储管理，是在分段存储管理系统的基础上，增加了请求调段、分段置换功能所形成的一种虚拟存储系统。n在请求分段存储管理中，作业运行之前，只要求将

43、当前需要的若干个分段装入主存，便可启动作业运行。在作业运行过程中，若所要访问(fngwn)的分段不在主存，则通过调段功能将其调入，同时还可以通过置换功能将暂时不用的分段换出到外存上，以便腾出内存空间。第八十二页，共一百四十二页。请求分段(fn dun)的支持机构n请求分段的支持机构有：n段表n缺段中断(zhngdun)机构n地址变换机构n请求调段和分段置换软件第八十三页，共一百四十二页。段表结构段表结构(jigu)n请求分段系统中使用的主要数据结构仍然是段表。n由于每次只将作业(zuy)的一部分调入内存，还有一部分内容存放在磁盘上，故需扩充段表表项，扩充后的段表项如下所示：第八十四页，共一百四

44、十二页。段表项中各字段的说明(shumng)n段号、段长和段基址：其定义(dngy)同分段存储管理。n存取方式：标识该分段的存取方式：读、写、执行。n访问字段：记录该段在一段时间内被访问的次数。n修改位：表示该段调入内存后是否被修改过。n存在位：表示该段是否在主存中。n增补位：指出该段在运行过程中，是否作过动态增长。n外存地址：指出该段在外存上的地址。段号段号段长段长段基段基址址存存 取取 方方 式式访问访问字段字段修改修改位位存在存在位位增补增补位位外存外存地址地址第八十五页，共一百四十二页。缺段中断缺段中断(zhngdun)处理处理n在请求分段系统(xtng)中，每当所访问的段不在内存时，

45、便产生一个缺段中断信号，请求OS将所缺分段调入内存。n缺段中断与缺页中断类似，也是在指令执行期间产生和处理。第八十六页，共一百四十二页。缺段中断处理(chl)流程缺段中断(zhngdun)处理阻塞请求(qngqi)进程唤醒请求进程内存中有合适的空闲区吗？N拼接以形成合适的空闲区从外存读入缺段Y修改段表及内存空闲区链NY空闲区容量总和能否满足淘汰实段以形成合适的空闲区返回第八十七页，共一百四十二页。缺段中断涉及的几个(j )问题n内存管理：请求分段的内存管理与与分区管理类似(li s)，采用连续内存管理方式。n段的置换：调入缺段时，若有足够的空闲分区则直接调入，否则查看空闲区之和能否满足要求，若

46、能则进行拼接，否则进行置换。置换时可能要淘汰多段。第八十八页，共一百四十二页。动态(dngti)地址变换 n请求分段系统的地址变换是在分段系统地址变换的基础上形成的。n在地址变换过程中，若段在内存(ni cn)则判断其存取权限是否合法，若合法则从段表中取出该段在内存(ni cn)的起始地址，与段内位移相加形成访问内存(ni cn)的物理地址。n若段不在内存，则产生缺段中断信号，请求OS将缺段调入内存，然后修改段表，再利用段表进行地址变换。第八十九页，共一百四十二页。请求分段(fn dun)的地址变换过程 程序请求程序请求(qngqi)访问一段访问一段段号段号段表长度段表长度(chngd),段内

47、位移段内位移 段长？段长？NY符合存取方式？符合存取方式？Y返回返回分段在主存中？分段在主存中？N形成物理地址形成物理地址分段越界处理分段越界处理NY修改访问位和修改位修改访问位和修改位分段保护处理分段保护处理缺段中断处理缺段中断处理第九十页，共一百四十二页。引入快表提高(t go)访问速度n与请求(qngqi)分页管理一样，请求(qngqi)分段的地址变换过程必须访问内存两次以上。n为提高访问速度，也可以使用快表。第九十一页，共一百四十二页。6.3.2 段的共享与保护(boh)n在分段存储管理系统中，信息(xnx)的共享是通过使多个进程的段表项指向同一内存区域实现的。n为了实现分段共享，可在

48、系统中设置一张共享段表，所有共享分段都在其中占有一表项。共享段表的格式如下：第九十二页，共一百四十二页。共享段表及表项n共享进程计数：记录有多少进程共享该段。n存取控制字段：对同一共享段，不同(b tn)进程有不同(b tn)的操作权限。n段号：共享段在不同进程中有不同的段号。共享段表共享段表 共享段表项共享段表项段名段名 段长段长 内存地址内存地址 状态状态(zhungti) 外存地址外存地址 共享进程计数共享进程计数count 状态状态 进程名进程名 进程号进程号 段号段号 存取控制存取控制 表项表项1 1表项表项2 2表项表项n n第九十三页，共一百四十二页。共享段的分配(fnpi)n当

49、为共享段分配内存时，对第一个请求使用该段的进程，系统(xtng)为该共享段分配一个内存区，再将该共享段调入，同时将该区的始址填入请求进程的段表，还需在共享段表中增加一项，填写有关数据并将count置1。n此后，当又有其他进程申请使用该共享段时，只需将count加1并填写有关数据结构。第九十四页，共一百四十二页。共享段的回收(hushu)n当某进程不再需要使用共享段时，应释放该段。此时应将该进程段表中共享段的对应表项撤消，并将count减1，若结果为0则需要系统回收共享段的物理内存及有关表项，否则仅取消(qxio)该进程在共享段中的记录。第九十五页，共一百四十二页。可重入代码(di m)n可重入

50、代码又称为纯代码，是允许多个进程同时访问的代码。可重入代码在执行(zhxng)中不能修改。 第九十六页，共一百四十二页。6.3.3 虚拟(xn)段页式存储管理系统n虚拟(xn)段页式存储管理系统是虚拟(xn)页式和虚拟(xn)段式存储管理的结合。第九十七页，共一百四十二页。习题习题(xt)nP150n3（1）n3（2）n3（3）n3（4）第九十八页，共一百四十二页。选择题1n实现虚拟存储器的目的是 _ 。A.实现存储保护 B.扩充辅存容量C.扩充内存容量D.实现程序浮动n页式虚拟存储管理的主要特点是 _ 。A. 不要求将作业装入到内存的连续(linx)区域B. 不要求将作业同时全部装入到内存的