第4章 存储器管理2

1、14.1 储存器的层次结构4.2 程序的装入和链接 4.3 连续分配方式 4.4 基本分页存储管理方式 4.5 基本分段存储管理方式 4.6 虚拟存储器的基本概念 4.7 请求分页存储管理方式 4.8 页面置换算法 4.9 请求分段存储管理方式 2常规存储器管理方式要求作业运行前全部装入内存，作业装入内存后一直驻留内存直至运行结束。 这种存储管理方式不仅限制了大作业的运行，也不能满足大量作业同时运行的要求。而物理扩充内存会增加成本，故应从逻辑上扩充内存。3在程序运行之前，将程序的一部分放入内存后就启动程序执行。在程序执行过程中，当所访问的信息不在内存时，由操作系统将所需要的部分调入内存，然后继

2、续执行程序。另一方面，操作系统将内存中暂时不使用的内容换出到外存上，从而腾出空间存放将要调入内存的信息。从效果上看，这样的计算机系统好像为用户提供了一个存储容量比实际内存大得多的存储器，将这个存储器称为虚拟存储器。 请求调入 置换 内存扩充4虚拟存储器是指具有请求调入和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。5程序信息不全部装入主存，能否保证程序的正确运行？回答是肯定的,1968年P.Denning研究了程序执行时的局部性原理。6虚拟存储器的理论基础是程序执行时的局部性原理。局部性原理是指程序在执行过程中一个较短时间内，程序所执行的指令地址和操作数地址分别局限于一定区域内。7程

3、序中只有少量分支和过程调用，大都是顺序执行的指令；过程调用使程序从一部分区域转至另一部分区域，但过程调用深度有限（一般不超过5层），一段时间内，指令引用被局限在很少几个过程中；程序中存在许多循环，是由相对较少的指令组成，在循环过程中，计算被限制在程序中很小的相邻部分中。对于连续访问数组之类的数据结构，往往是对存储区域中相邻位置的数据的操作。8局部性体现为： 时间局部性：一条指令的一次执行和下次执行，一个数据的一次访问和下次访问，都集中在一个较短时间内。 空间局部性：当前执行的指令和将要执行的指令，当前访问的数据和将要访问的数据，都集中在一个较小范围内。例如：循环结构例如：顺序执行9相当数量的外

4、存：足以存放多个用户的程序。一定容量的内存：在处理机上运行的程序必须有一部分信息存放在内存中。地址变换机构：动态实现逻辑地址到物理地址的变换。10常用的虚拟存储技术有：请求分页系统 在分页系统的基础上，增加了请求调页功能、页面置换功能而形成的页式虚拟存储系统。请求分段系统 在分段系统的基础上，增加了请求调段功能、分段置换功能而形成的段式虚拟存储系统。请求段页式系统* 在段页式系统的基础上，增加了请求调页功能、页面置换功能而形成的段页式虚拟存储系统。11多次性 一个作业被分成多次调入内存对换性 允许作业在运行过程中换入换出虚拟性 把辅助存储器作为对主存储器的扩充， 向用户提供一个比实际主存大得多

5、的地址空间。124.1 储存器的层次结构4.2 程序的装入和链接 4.3 连续分配方式 4.4 基本分页存储管理方式 4.5 基本分段存储管理方式 4.6 虚拟存储器的基本概念 4.7 请求分页存储管理方式 4.8 页面置换算法 4.9 请求分段存储管理方式 13请求分页存储管理方法是在分页存储管理的基础上增加了请求调页和页面置换功能。实现思想：在作业运行之前只装入当前需要的一部分页面便启动作业运行。在作业运行过程中，若发现所要访问的页面不在内存，便由硬件产生缺页中断，请求OS将缺页调入内存。若内存无空闲存储空间，则根据某种置换算法淘汰已在内存的某个页面，以腾出内存空间装入缺页。14除了一定容

6、量的内存和外存，请求分页中的支持机构还有： 页表 缺页中断机构 地址变换机构15请求分页系统中使用的主要数据结构仍然是页表。但由于每次只将作业的一部分调入内存，还有一部分内容存放在磁盘上，故需要在页表中增加若干项。扩充后的页表项如下所示： 16页号和物理块号页号和物理块号：其定义同分页存储管理。状态位状态位：用于表示该页是否在主存中。访问字段访问字段：用于记录本页在一段时间内被访问的次数，或最近已有多长时间未被访问。修改位修改位：用于表示该页调入内存后是否被修改过。外存地址外存地址：用于指出该页在外存上的地址。 页号页号 物理块号物理块号 状态位状态位P访问字段访问字段A修改位修改位M 外存地

7、址外存地址17在请求分页系统中，当地址转换机构发现指令所访问的页不在内存时，便产生缺页中断，请求OS将缺页调入内存（必要时淘汰内存中已有页面）并修改页表。18缺页中断作为中断，同样需要经历保护CPU现场、分析中断原因、转缺页中断处理程序进行处理、恢复CPU现场。缺页中断与一般中断的区别主要有： 在指令的执行期间产生和处理缺页中断。 一条指令可以产生多个缺页中断。如：执行一条复制指令copy A to B B: A: Copy A To B页面65432119请求分页存储管理系统的地址变换过程类似于分页存储管理，但当被访问页不在内存时应进行缺页中断处理。缺页中断处理保留CPU现场从外存中找到缺页

8、内存满否？选择一页换出该页被修改否？将该页写回外存OS命令CPU从外存读缺页启动I/O硬件将一页从外存换入内存修改页表否是是否页表项在快表中？CPU检索快表访问页表否页在内存？修改访问位和修改位形成物理地址地址变换结束否页号页表长度?开始程序请求访问一页产生缺页中断请求调页修改快表是越界中断是是21在为进程分配物理块时应确定: 进程需要的最少物理块数 进程的物理块数是固定还是可变（分配策略） 按什么原则为进程分配物理块数（分配算法）22最小物理块数是指能保证进程正常运行所需的最少物理块数，若小于此值进程无法运行。最小物理块数由执行一条指令所涉及的页面数确定。一般情况下：对于单地址指令 单地址指

9、令且采用直接寻址，则所需最少物理块数为2。 若单地址指令且允许采用间接寻址，则所需最少物理块数为3。 某些功能较强的机器，指令及地址均跨两个页面，则最少需要4个（直接寻址）或6个（间接寻址）物理块。23在选择分配物理块的策略和置换范围时，需要考虑以下几个因素： 系统的并发性和吞吐量：分配给每个进程的物理块越少，则驻留在内存的进程就越多，因而系统的并发性和吞吐量就越大。 缺页中断率：分配给进程的物理块较少，则缺页中断率较高；但当分配给进程的物理块超过一定数量后，再增加物理块对减少进程的缺页率没有明显影响。24分配策略：固定分配和可变分配。置换范围：全局置换和局部置换。将分配策略和置换范围组合可得

10、如下三种策略： (1)固定分配局部置换 (2)可变分配全局置换 (3)可变分配局部置换。25固定分配局部置换：基于某种原则为每个进程分配固定数量的物理块，当进程运行中出现缺页时，只能从自己的页面中选择一页换出，然后再调入缺页。实现这种策略的困难在于：难以确定应为每个进程分配多少个物理块。26可变分配全局置换：先为系统中的每个进程分配一定数量的物理块，操作系统本身也保持一个空闲物理块队列。当某进程发生缺页时，由系统从空闲物理块队列中取出一个物理块分配给该进程；当空闲物理块队列中的物理块用完时，操作系统才从内存中选择一页调出，该页可以是系统中任何一个进程的页面。这是一种容易实现的页面分配和置换策略

11、，目前已用于若干操作系统中。27可变分配局部置换：根据某种原则为每个进程分配一定数量的物理块，当进程发生缺页中断时，只允许从该进程自己的页面中选出一页换出。如果某进程的缺页率较高，则系统再为该进程分配若干物理块；反之若某进程的缺页率特别低，则系统可适当减少分配给该进程的物理块数。该算法比较复杂，但性能较好。28按什么原则给进程分配物理块数： 平均分配算法：将系统中所有可供分配物理块平均分配给每个进程。 按比例分配算法：根据进程大小按比例分配物理块。 按优先级分配算法：有两种实现方案 将可供分配的物理块分为两部分，一部分按比例分配给每个进程，另一部分根据进程的优先级适当增加物理块。 先按比例为进

12、程分配物理块，当高优先级进程发生缺页时，允许它从低优先级进程处获得物理块。291. 何时调入页面何时调入页面 预调页策略将一批相邻存放的页/预计可能很快用到的页预先调入内存。预测成功率低，主要用于进程首次调入时。请求调页策略程序运行中需要访问的页不在内存时，由OS将所缺的页调入内存。广泛采用，但是系统开销大。30文件区 用于存放文件； 采用离散分配方式。对换区 用于存放对换页面； 采用连续分配方式。 故对换区的磁盘I/O速度比文件区的高。 2. 从何处调入页面从何处调入页面 31发生缺页请求时，系统应从何处将缺页调入内存，可分成如下三种情况：(1) 系统拥有足够的对换区空间。 这时可以全部从对

13、换区调入所需页面，以提高调页速度。 在进程运行前， 便须将与该进程有关的文件，从文件区拷贝到对换区。 从何处调入页面从何处调入页面 （续）（续） 32(2) 系统缺少足够的对换区空间。 这时凡是不会被修改的文件，都直接从文件区调入；而当换出这些页面时，由于它们未被修改而不必再将它们换出，以后再调入时，仍从文件区直接调入。 但对于那些可能被修改的部分，在将它们换出时，便须调到对换区，以后需要时，再从对换区调入。从何处调入页面从何处调入页面 （续）（续） 33 (3) UNIX方式。 由于与进程有关的文件都放在文件区，故凡是未运行过的页面，都应从文件区调入。 而对于曾经运行过但又被换出的页面，由于

14、是被放在对换区，因此在下次调入时，应从对换区调入。 由于UNIX系统允许页面共享，因此， 某进程所请求的页面有可能已被其它进程调入内存，此时也就无须再从对换区调入。 从何处调入页面从何处调入页面 （续）（续） 344.1 储存器的层次结构4.2 程序的装入和链接 4.3 连续分配方式 4.4 基本分页存储管理方式 4.5 基本分段存储管理方式 4.6 虚拟存储器的基本概念 4.7 请求分页存储管理方式 4.8 页面置换算法 4.9 请求分段存储管理方式 35页面置换算法又称为页面淘汰算法，是用来选择换出页面的算法。研究页面置换算法要考虑： 淘汰页面范围：是全局置换还是局部置换 页面分配：确定分

15、配给进程的物理块数，有固定分配和可变分配 页面置换算法的选择：应有较低的页面置换频率本节中讨论“局部范围”内的置换算法，即局部置换、固定分配361.最佳置换算法（OPT） 选择将来最长时间不会使用的页面予以淘汰。2.先进先出算法（FIFO） 选择调入主存时间最长的页面予以淘汰。3.最近最久未使用置换算法(LRU) 选择最近一段时间内最长时间没有被访问过的页面予以淘汰。4. 时钟（clock）置换算法5. 其它置换算法37OPT算法是从内存中选择将来最长时间不会使用的页面予以淘汰。特点：因页面访问的未来顺序很难精确预测，该算法具有理论意义，可以用来评价其他算法的优劣。38例1：假定系统为某进程分

16、配了3个物理块，页面访问序列为：7、0、1、2、0、3、0、4、2、3、0、3、2、1、2、0、1、7、0、1，开始时3个物理块均为空闲，采用最佳置换算法时的页面置换情况如下所示：397707017 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 203701201243203201可以看出，共发生了6次页面置换。40FIFO算法是选择调入主存时间最长的页面予以淘汰。理由：最早调入内存的页面，其不再被访问的可能性最大。特点：该算法实现比较简单，对按线性顺序访问的程序比较合适，但可能产生异常现象。Belady现象：在某些情况下，分配给进程的页面数增多，缺页次数反而增加

17、。原因：上述理由不成立，最先进入内存的页面可能是今后经常用到的页面。41例1中如果采用先进先出置换算法时的页面置换情况：7707017 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 231023430423201可以看出，共发生了12次页面置换。01371270242070101223042LRU算法选择最近一段时间内最长时间没有被访问过的页面予以淘汰。原理：根据程序局部性原理，那些刚被使用过的页面，可能马上还要被使用，而在较长时间里未被使用的页面，可能不会马上使用到。43上例采用LRU置换算法时的页面置换情况如下所示：7707017 0 1 2 0 3 0 4

18、2 3 0 3 2 1 2 0 1 7 0 1 203032403432201从上表中可以看出，共发生了9次页面置换13210210740244练习：假定系统为某进程分配了4个物理块，页面访问序列为：1、2、3、4、1、2、5、1、2、3、4、5，开始时4个物理块均为空闲，分析采用下列置换算法的页面置换情况。(1) 最佳置换算法(2) 先进先出置换算法(3) 最近最少使用置换算法发生3次页面置换发生6次页面置换发生4次页面置换45LRU算法实现时需要较多的硬件支持，以记录进程中各页面自上次访问以来有多长时间未被访问。下面介绍几种实现方法。 基于寄存器的方法 基于栈的方法46为每个在内存中的页面

19、配置一个n位移位寄存器，可表示为 寄存器初值为0。当进程访问某页面时，将该页面对应寄存器的最高位(即Rn-1)置1，每隔一定时间（例如100ms）将计数器右移1位。那么具有最小数值的寄存器对应的页面就是最近最久未使用的页面。 R=Rn-1Rn-2Rn-3 R2R1R0 47 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

20、1 0 1 1 1页面7对应的寄存器值最小，当发生缺页，首先将它置换出去 48用一个特殊的栈保存当前进程所访问的各页面号。每当进程访问某页面，便将它对应的页面号从栈中移出，压入栈顶。那么栈顶始终是最近访问的页面，而栈底则是最近最久未使用的页面。49例如：设分配给某进程5个物理块，页面访问序列为：4,7,0,7,1,0,1,2,1,2,6，则栈的变化情况如下：447470740704717041017401074121074212074121074262107650LRU算法需要较多硬件支持，实现成本较高，因此实际应用中往往采用LRU的近似算法。clock算法就是用得较多的一种LRU近似算法。5

21、1为每页设置一个访问位，再将内存中所有页面通过链接指针链成一个循环队列。当某页首次调入内存时，将其访问位置1。当某页被访问时，将其访问位置1。52当发生缺页中断时，执行下面的算法选择淘汰页53Page1R=118Page19R=1Page3R=0Page9R=1Page5R=1Page13R=0234567Page11R=1Page21R=0如果此时要求访问page12，应选择哪一页淘汰？替换后状态如何？18Page19R=1Page1R=1Page11R=1Page21R=0Page3R=0Page9R=1Page5R=1Page13R=0234567Page1R=0Page11R=0Pag

22、e12R=154将一个修改过的页面换出需要写磁盘，其开销大于未修改页面。为此在改进型时钟算法中应考虑页面修改情况。设A为访问位，M为修改位，将页面分为以下4种类型： 1类(A=0,M=0)：最近未被访问又未被修改用于置换的最佳页； 2类(A=0,M=1)：最近未被访问但已被修改不是很好，因为在置换之前需将页写出到磁盘； 3类(A=1,M=0)：最近已被访问但未被修改它有可能很快又要被使用； 4类(A=1,M=1)：最近已被访问且已被修改它有可能很快又要被使用，且置换之前需将页写出到磁盘。55第1步：从指针当前位置开始扫描循环队列，寻找A=0,M=0的页面，将满足条件的第一个页面作为淘汰页。第2

23、步：若第1步失败，则开始第2轮扫描，寻找A=0,M=1的页面，将满足条件的第一个页面作为淘汰页，并将所有经历过页面的访问位置0。第3步：若第2步失败，则指针再次回到了开始位置，然后重复第1步，若仍失败则必须重复第2步。此时一定能找到淘汰页面。特点：减少了磁盘I/O次数，但算法本身开销增加。561.缺页率对有效访问时间的影响2.抖动现象3.页面大小的选择57有效访问时间（Effective Access Time, EAT）是指访问存储器所需时间的平均值。58假定内存的读写周期为m 访问快表(相联存储器)的时间为e 快表命中率为 p 则EAT=p(m+e) + (1-p)(m+m+e) u例如：

24、m=100ns，e=20ns，p=90%，则EAT为: 0.9(10020)0.1(100+100+20) 130ns59假设使用了快表，则CPU访问内存时有以下三种情况： 页面在内存且页表项在快表中：只需一次访问内存 页面在内存但页表项不在快表中：需两次访问内存 页面不在内存：缺页中断处理时间60缺页中断处理时间由三部分组成： 缺页中断服务时间 页面传送时间：包括读缺页和写置换页的时间 进程重新执行时间由于缺页中断服务时间及进程重新执行时间较短，这里仅考虑页面传送时间。61设内存读写周期为m，缺页中断处理时间为t，快表命中率为p，快表访问时间可以忽略，缺页中断率为f，则有效访问时间为： EA

25、T = pm + (1-p-f)2m + ft62例如：设p=0.8，m=100ns，t=10ms，则： EAT = 0.80.1 + (1-0.8-f)20.1 + f101000 = 0.12+9999.8f（s）若f为0.001，则EAT为10.1198微秒，是没有缺页（f=0）时EAT值（0.12 s ）的84倍。若要求在缺页时EAT增加不超过10，则必须满足 0.12+9999.8f 0.12+0.012 f 0.0000012631) 分配给进程的物理块数 一般来讲，物理块数与缺页率成反比关系。2) 页面本身的大小 一般来讲，页面较小缺页率小，页面增大缺页率增大然后又下降。3) 程

26、序的编制方法 好的程序结构可以降低缺页率4) 页面置换算法64设页面大小为128字节，二维数组为128128，初始时未装入数据，需将数组初始化为0。若数组按行存放，问下述两个程序段的缺页率各为多少？（注：假设系统分配给整个程序的帧数少于128）u程序1 short int a128128； for (j=0;j=127;j+) for (i=0;i=127;i+) aij=0;u程序2short int a128128； for (i=0;i=127;i+) for (j=0;j=127;j+) aij=0; 65因数组以行为主存放，页面大小为128字节，故每行占一个页面。程序1的内层循环将每

27、行中的指定列置为0，故产生128次中断。外层循环128次，总缺页次数为128128。n程序1 short int a128128； for (j=0;j=127;j+) for (i=0;i=127;i+) aij=0;66因数组以行为主存放，页面大小为128字节，故每行占一个页面。程序2的内层循环将每行的所有列置为0，故产生1次中断。外层循环128次，总缺页次数为128。n程序2 short int a128128； for (i=0;i=127;i+) for (j=0;j=127;j+) aij=0;67下图是CPU利用率与程序道数的关系。开始时CPU利用率会随着程序道数的增加而增加，当

28、程序道数增加到一定数量以后，程序道数的增加会使CPU的利用率急剧下降。0CPU利用率程序道数抖动68抖动(Thrashing) ：如果运行进程的大部分时间都用于页面的换入/换出，而几乎不能完成任何有效的工作，则称此进程处于抖动状态。抖动又称为颠簸。抖动分为： 局部抖动 全局抖动69抖动产生的原因有： 进程分配的物理块太少 置换算法选择不当 全局置换使抖动传播70为防止系统抖动，可采用局部置换策略限制抖动的传播。一旦发现抖动，增加分配给相应进程的物理块或挂起一些进程。选择挂起进程的条件 优先级最低：符合进程调度原则 发生缺页中断的进程：内存不含工作集，缺页时应阻塞 物理块数最少的进程：重新装入开

29、销小 最后被激活的进程：工作集可能不在内存 最大的进程：可释放较多空间 剩余时间最长：有利于提高系统吞吐量71页面大小的选择涉及诸多因素，需要在这些因素之间权衡利弊。 页内碎片问题：页面越大，碎片越大。依此应选择小页面。 内外存传输：大小页面传输时间基本相同，依此应选择大页面。 页表大小：页面越小，页表越长。依此应选择大页面。 页面大小对缺页率的影响：页面较小缺页率小，页面增大缺页率增大然后又下降。 页面大小与主存关系：主存大则页面大。72设系统内每个进程的平均长度为s，页面大小为p，每个页表项需e个字节，内存大小为m。n 则内存中的进程数为：m/sn 内存中页面数为：m/pn 页表项占用空间

30、：me/pn 每进程碎片的平均大小：p/2n 分页系统总开销：pm/2s + me/pn 总碎片空间为：(p/2)(m/s) = pm/2s73n 则内存的浪费率为： f (p) = (pm/2s+me/p)/m = p/2s+e/pn 对p求导数：f(p)=1/2s-e/p2n 分页系统总开销：pm/2s + me/pn 令导数为0：1/2s-e/p2=0，得到p=2esn 则页面大小为：p=2es时，f取得最小值 (2/s )。744.1 储存器的层次结构4.2 程序的装入和链接 4.3 连续分配方式 4.4 基本分页存储管理方式 4.5 基本分段存储管理方式 4.6 虚拟存储器的基本概念

31、 4.7 请求分页存储管理方式 4.8 页面置换算法 4.9 请求分段存储管理方式 75请求分段存储管理系统基于分段存储管理，是在分段存储管理系统的基础上，增加了请求调段、分段置换功能所形成的一种虚拟存储系统。在请求分段存储管理中，作业运行之前，只要求将当前需要的若干个分段装入主存，便可启动作业运行。在作业运行过程中，若所要访问的分段不在主存，则通过调段功能将其调入，同时还可以通过置换功能将暂时不用的分段换出到外存上，以便腾出内存空间。76请求分段的支持机构有： 段表 缺段中断机构 地址变换机构77请求分段系统中使用的主要数据结构仍然是段表。由于每次只将作业的一部分调入内存，还有一部分内容存放

32、在磁盘上，故需扩充段表表项，扩充后的段表项如下所示：78段号、段长和段基址：其定义同分段存储管理。存取方式：标识该分段的存取方式：读、写、执行。访问字段：记录该段在一段时间内被访问的次数。修改位：表示该段调入内存后是否被修改过。存在位：表示该段是否在主存中。增补位：指出该段在运行过程中，是否允许动态增长。外存地址：指出该段在外存上的地址。段号段号段长段长段基址段基址存取存取 方式方式访问字访问字段段修改修改位位存在存在位位增补位增补位外存外存地址地址79在请求分段系统中，每当所访问的段不在内存时，便产生一个缺段中断信号，请求OS将所缺分段调入内存。缺段中断与缺页中断类似，也是在指令执行期间产生和处理。80虚段 S不在内存阻塞请求进程内存中有合适的空闲区吗？从外存读入段 S修改段表及内存空区链唤醒请求进程返回空区容量总和能否满足？空区拼接，以形成一个合适的空区淘汰一个或几个实段，以形成一个合适空区否否是是81内存管理：请求分段的内存管理与与分区管理类似，采用连续内存管理方式。段的置换：调入缺段时，若有足够的