5虚拟存储课件

1、第5章 虚拟存储管理,本章目录,5.1 请求页式虚拟存储管理基础,5.1.1 虚拟存储器,5.1.2 请求页式虚拟存储管理,5.2 请求页式的替换策略,5.2.1 替换策略综述,5.2.2 请求页式静态替换策略,5.2.3 关于静态替换策略的进一步讨论,5.2.4 请求页式动态替换策略,5.3 请求段式虚拟存储管理,5.3.1 请求段式虚拟存储管理,5.3.2 段的动态链接,5.4 Linux的存储管理,5.4.1 Linux存储管理的硬件基础,5.4.2 Linux多级页表的地址转换,5.4.3 内存空间的管理,5.4.4 管理虚拟存储空间的数据结构,除分支和调用指令，程序的执行都是顺序的。

2、分支和调用指令在所有程序指令中只占很少一部分。大多数情况下，要读取的下一条指令肯定都是紧跟在已取到的上一条指令之后的。,5.1 请求页式虚拟存储管理基础,5.1.1 虚拟存储器,程序执行的“局部性”原理,1.,程序执行的“局部性”原理，是指程序在执行的某一时刻，并不是均匀地访问它的整个地址空间，而往往是集中于某一小部分区域。,.,.,程序执行的局部性，具体表现在几个方面 ：,(1),(2),程序中很少会出现很长的、一个过程调用接着又一个过程调用的调用序列。在较短的时间内，指令的引用大多局限在很少几个过程中，不会一会儿是这个过程，一会儿是那个过程。,(3),大多数循环结构都由较少的几条指令重复若

3、干次组成，循环过程中的计算，也多被限制在程序中的一个很小的相邻部分完成。,(4),许多程序中的计算都涉及到对数组、文件记录之类数据的处理，而对这些数据的引用，其实都是对位置相邻的数据项进行操作。,局限性又表现在下述两个方面： (1) 时间局限性。如果程序中的某条指令一旦执行， 则不久以后该指令可能再次执行；如果某数据被访问过， 则不久以后该数据可能再次被访问。产生时间局限性的典型原因，是由于在程序中存在着大量的循环操作。 (2) 空间局限性。一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也将被访问，即程序在一段时间内所访问的地址，可能集中在一定的范围之内，其典型情况便是程序的顺序执行

4、。,2. 虚拟存储器,（1） 虚拟存储器的引入,常规存储器管理方式的特征 常规存储管理方式要求将一个进程所需的程序和数据全部装入内存方可执行。 这样的系统存在两个很严重的问题： 第一：对于大进程，如果其所需内存空间超过了内存的最大容量，则无法进行。（也可以采用覆盖技术） 第二：对于多道程序系统，由于每一个进程需要全部装入内存，使同时驻留内存的进程数量受到限制，虽然也可以通过提高内存容量来解决，但是代价太高。（内存空间也不能无限扩大） 如果能将一部分价格较低的外存空间，当作内存使用，从逻辑上扩充内存容量，那么将获得更高的性价比。,虚拟存储的好处 第一：可以运行大程序，包括超过内存实际容量的大程序

5、。 第二：可以在有限的物理内存中运行更多的程序。多道程序系统的度不再受到物理内存空间的限制。 （可概括为更大更多）,虚拟存储器,(2.),程序执行的“局部性”原理给人们重要的启示是：其实程序并不是必须全部都在内存后才能运行，只要关键的那一小部分在内存就可以了。,.,.,有了“局部性”原理的支撑，一个新程序运行时，只需把包含程序开始处的一个或几个块（页或段）从磁盘读入内存就行。运行过程中，若对存储器的访问在这些块里，那么通过页表或段表对逻辑地址的动态重定位，执行就可顺利进行。如果CPU需要访问一个不在内存中的逻辑地址，那就产生一个中断，告知CPU对内存的访问出现了故障。这时，操作系统就阻塞正在执

6、行的进程，产生磁盘I/O请求，把包含引起访问故障的那个逻辑地址所在的块取到内存。这样，被阻塞进程就可重新成为就绪状态，继续运行下去。,.,.,所谓“虚拟存储器”，实为一种扩大内存容量的软件设计技术，它把辅存作为计算机实际内存的后援，操作系统把当前需要使用的那部分程序、数据等内容读入内存，其他部分保存在磁盘上，必要时由操作系统实施内存和磁盘之间的信息交换。 所谓虚拟存储器， 是指具有请求调入功能和置换功能， 能从逻辑上对内存容量加以扩充的一种存储器系统。其逻辑容量由内存容量和外存容量之和所决定，其运行速度接近于内存速度，而每位的成本却又接近于外存。,.,在虚拟存储意义下，系统向每个用户提供一个虚

7、拟存储器，用户作业的相对地址空间，就是系统提供给他的虚拟存储器。这时称用户作业的相对地址空间为“虚拟地址空间”，里面的相对地址称为“虚拟地址”。,图：实现虚拟存储的典型过程,虚拟存储要解决的问题,3.,(1),读取策略,所谓“预约式”，是利用磁盘I/O操作中所具有的寻道时间和旋转延迟特性，一次顺序读入后面的多个块，把可能需要的块提前读入供程序使用，这比需要哪块才去读哪块显得更加有效些。程序启动时，一般采用预约式；程序启动后，可采用任意一种，目前大多采用请求式。,.,指在程序运行过程中，何时把所需要的块调入内存的策略。,.,所谓“请求式”，指当访问需要某块里的信息、而这块当时又不在内存时，才把这

8、块从辅存换入内存,.,放置策略,(2),.,主要是针对请求页式管理的，当要把所需的页面信息从辅存调入内存时，内存必须要有空闲页。放置策略用来决定把所需要的页面存放到内存的哪个空闲页帧去。,.,所谓“固定”的放置策略，就是静态放置策略，指为作业程序分配固定数目的帧，页面只能存放在这些页帧里；所谓“可变”的放置策略，就是动态放置策略，是指分配给作业程序的页帧随需要不断变化。,(3),替换策略,.,如果放置时内存里没有空闲的区域，那么就必须先要把当前暂时不用的信息从内存替换出去，以便腾出位置进行放置，这是替换策略需要解决的问题。,.,所谓“局部”替换策略，指只在分配给作业使用的帧里选择替换对象；所谓

9、“全局”替换策略，指把整个内存页帧都作为替换的候选对象，不去管它们属于哪一个作业进程。,返回目录,1.,请求页式虚拟存储管理的基本思想,5.1.2 请求页式虚拟存储管理,作业全部在磁盘，只把要用的若干页面装入页帧。运行时虚拟地址转换成数对：（页号，页内位移）。由页号查页表，若该页在内存某页帧，就得到物理地址，运行继续进行；若该页面不在内存，表示发生了“页面失效”，俗称“缺页”，运行无法继续。此时系统根据所缺页的页号，把它从辅存调入内存，修改页表后，程序在原先暂停处继续运行。,.,0,4KB,8KB,12KB,16KB,20KB,24KB,28KB,32KB,36KB,40KB,44KB,48K

10、B,52KB,56KB,60KB,64KB,虚拟地址空间,虚拟页面,2,1,6,0,4,3,5,7,X,X,X,X,X,X,X,X,0,4KB,8KB,12KB,16KB,20KB,24KB,28KB,32KB,页帧,物理内存空间,(a) 请求页式的地址映射关系,虚拟地址：,页号,页内位移,I,M,其他控制位,页帧号,页表项：,修改位,页面失效位(缺页中断位),图(b)给出了请求页式的虚拟地址和页表项结构和内容。,图(a)给出了请求页式存储管理的示意。,.,.,(b) 请求页式的虚拟地址和页表项,在请求页式存储管理中，虚拟地址空间中的虚拟地址仍然是一维的。操作系统把虚拟地址空间按照页帧尺寸划分

11、成若干页面，这样一维的虚拟地址就与一个数对（页号，页内位移）对应了。,2.,请求页式虚拟存储管理的特点,向用户提供虚拟存储器,.,由于总是把作业的虚拟地址空间存放在磁盘，因此用户的虚拟存储器可以比实际内存大。,(1),.,虚拟存储器的大小由地址结构决定,(2),.,在请求页式存储管理中，向用户提供的虚拟存储器的大小，由其地址结构决定。,.,比如地址结构为16个二进制位，页帧尺寸是4KB（=212），那么用户作业的虚拟存储器最多可以有16（=24）个页面；若地址结构为20个二进制位，页帧尺寸是4KB，那么用户作业的虚拟存储器最多可以大到有256（=28）个页面。,(3),“页面失效”位和“修改”

12、位,.,“页面失效”位I为“1”，表示对应页面已调入内存的某页帧；如果为“0”，表示对应的页面不在内存（即页面失效），应发出“缺页”中断信号，让操作系统将其调入。,.,“修改”位M为“0”，表示对应页面在调入到内存页帧后没被修改过；这位为“1”，表示对应页面在调入到内存页帧后被修改过，若要把这页从内存调出（即替换），那就需要用页帧中的内容去更新磁盘上的相应页内容。有时，称修改位为0的页是“干净”的，为1的页是“脏”的。,当执行到作业2第0帧中的指令“call 8300”时，系统把虚拟地址8300转换成数对：（2，108）。,3.,请求页式虚拟存储管理的实际运作过程,例5-1 ：,一个请求页式存

13、储管理的整个运作过程。,3,4600,0,已分配,1,已分配,2,已分配,3,空闲,4,已分配,5,已分配,6,已分配,7,空闲,8,已分配,9,空闲,帧号 状态,存储分块表,0,操作系统,0 1 2,1 1 4,2 0 5,作业2第0页,call 8300,作业2第1页,作业1第0页,作业1第1页,作业3第0页,4KB,8KB,12KB,16KB,20KB,24KB,28KB,32KB,36KB,40KB,内存,帧1,帧0,帧2,帧3,帧4,帧5,帧6,帧7,帧8,帧9,页面表信息,长度 起址,1 8KB 2 4160,2 12KB 3 4600,3 4KB 1 4820,尺 寸,作业号,作

14、业表,页表控制寄存器,0 1 5,1 1 6,P I F,P I F,2 1 7,0 1 2,1 1 4,2 0 5,0 1 8,P I F,作业1的页表,作业2的页表,作业3的页表,空闲帧,空闲帧,空闲帧,(a),(b),(c),(d),当系统决定把CPU分配给作业2时，就从作业表中把作业2的页表起址4600和长度3装入页表控制寄存器中。,.,.,.,作业2的第2页不在内存，它的I位（即页面失效位）是0，于是引起“缺页中断”。,.,把作业2第2页调入内 存的第7帧，系统结束缺页 中断处理，返回到指令“call 8300”处重新执行。,.,用第7页帧的起址28K加页内位移108，形成虚拟地址8

15、300对应的绝对地址，真正应该执行的指令是：“call (28K+108)”。,.,请求页式存储管理地址变换的简要流程,准备取下一条指令,执行指令,形成物理地址,该页通过 读/写保护？,出错中断信号,N,Y,分析指令，拆分成(p,d),查快表成功？,N,Y,查页表， 页在内存？,N,Y,快表满否？,Y,按FIFO腾空 一个快表表项,复制页表 项到快表,缺页中断,缺页中断处理程序,内存有空帧？,Y,N,按替换策略选一页淘汰,修改位为1？,N,Y,将淘汰页回写,修改淘汰页页表信息,调入所需页面,修改页表信息,硬件处理,软件处理,中 断 返 回,4.,页面走向与缺页中断率,.,每一个虚拟地址都与一个

16、数对（页号，页内位移）相对应，这种动态特征可用程序执行时页号的变化来描述。通常，称一个程序执行过程中页号的变化序列为该作业的“页面走向”。,.,LOAD 1#，1120,2000,1000,0,100,104,108,ADD 1#，2410,STORE 1#，1124,1KB,1120,1124,2KB,2410,3KB,虚拟存储器,第0页,第1页,第2页,LOAD 1#，1120,2000,1000,0,100,104,108,ADD 1#，2410,STORE 1#，1124,1KB,1120,1124,2KB,2410,3KB,虚拟存储器,第0页,第1页,第2页,3000,(a),(b)

17、,LOAD 1#，1120,0,100,104,108,ADD 1#，2410,STORE 1#，1124,(0，100),1120,1124,2410,用户作业程序,(页号, 页内位移),虚拟地址,页面走向,(c),(1，96),(0，104),(2，354),(0，108),(1，100),1,0,2,0,1,图（a）给出一个用户作业的虚拟地址空间，里面有3条指令。,.,运行结果如图（b）所示，在虚拟地址1124中有结果3000。,.,该程序运行时，虚拟地址的变化情形如图（c）第2栏“虚拟地址”所示。另一方面，每一个虚拟地址都有一个数对与之对应，如图（c）第3栏所示。把它里面的页号抽取出来

18、，就构成了该程序运行时的页面走向，即如图（c）第4栏所示。,把128128的二维数组元素初始化为“0”。数组中的每个元素占一个字。假定页面尺寸为128字，数组按行的顺序存放，分配给该作业两个内存页帧：一个存放程序，另一个用于数组初始化。作业开始运行时，除程序已在内存页帧外，数据均未进入。编写实现数组元素初始化的程序，运行时会有多少次缺页中断？,分配给作业的内存块数：分配给作业的内存块数多，同时能够装入内存的作业页面就多，页面失效的可能性下降，于是发生缺页中断的可能性也就下降。,.,假定一个作业运行的页面走向中涉及到的页面总数为A，其中有F次页面失效（即缺页），必须通过缺页中断把它们调入内存。我

19、们定义： f=F/A 称f为“缺页中断率”。,.,影响缺页中断次数的因素,(1),(2),页面尺寸：页面增大了，在每个页帧里的信息相应增加，缺页的可能性就下降；反之，页面尺寸减少，每帧里的信息减少，缺页的可能性上升。,(3),程序的实现：作业程序的编写方法，对缺页中断产生的次数也会有影响。,例5-2 ：,程序1：程序2： main()main() int a128128; int a128128; int i,j; int i,j; for(i=0;i128;i+) for(j=0;j128;j+) for(j=0;j128;j+) for(i=0;i128;i+) aij=0; aij=0;

20、 ,解：,返回目录,解：第一种缺页中断次数为128次， 第二种缺页中断次数为128*128=16384次,5.2.1 替换策略综述,对请求页式，若采用的放置策略是局部性的，那么当把所缺的页面从磁盘调入内存时，只能把它们放置在自己有权使用的页帧区域里。当该区域里没有空闲页帧时，就只有把这个区域里暂时不用的页面替换出去，以腾出页帧供放置使用。,5.2 请求页式的替换策略,.,.,所谓“静态”替换策略 ，指作业运行过程中，分配给它使用的页帧数不变；所谓“动态”替换策略，指作业运行过程中，可根据其需要，增加或减少所使用的页帧数。,假定某作业有6个页面：0、1、2、3、4、5，分配给它m=4个页帧。其执

21、行时的部分页面走向R=2，0，3，4，3，2，0，1，1，3，,.,.,开始时，4个页帧都是空闲的。由页面失效通过缺页中断调入页面2、0、3、4时，因有空闲页帧存在，所以不会有替换问题。再往下运行时，由于第3页、第2页、第0页都在页帧里，因此也不会有什么问题发生。,.,继续运行需要页面1时，4个页帧分别被2、0、3、4页占用，访问页面1会由于页面失效导致缺页中断，但4个页帧又都不空闲。于是必须从占用4个页帧的页面中挑选一个调出去，以便让页面1调入。这就是说，发生了需要“替换”的情形。,.,缺页中断不一定导致页面替换，但页面替换一定是由于缺页中断所引起。替换策略选择得不好，就可能出现刚调出的页面

22、又要立即调入的情形，致使页面失效增多，这种重复频繁发生页面替换的调出、调入现象，称为“抖动”。,返回目录,0 0 1 3,3 1 2 3,6 4 5 6*,5 4 5* 3,5.2.2 请求页式静态替换策略,1.,最佳页面替换策略,比如分配给作业的页帧数m=3，其页面走向为： R=0，1，2，3，0，1，2，3，0，1，2，3，4，5，6，7 表给出了实施最佳替换策略时，各页帧内容随页面走向发生变化的情形。,.,最佳页面替换（OPT）策略是指在出现页面失效、且需要进行页面替换时，总是把下次访问距离当前最远的那个页面作为调出的对象。,.,页帧/页面,0 1 2,3 0 1 3*,0 0*,1 0

23、 1*,2 0 1 2*,1 0 1 3,2 0 2* 3,3 0 2 3,0 0 2 3,1 1* 2 3,2 1 2 3,4 4* 2 3,7 7* 5 6,行表示某帧在不同时刻被页占用的情况，比如第1行表示第0帧随页面走向的变化而被其中不同页面加载的情形；列表示某时刻页面走向中页面占用各帧的情况，比如第13列表示是第4页占用第0帧，第2页占用第1帧，第3页占用第2帧。在行、列交汇处表项中的数字以“*”标记，表示该页是由页面失效通过缺页中断加载到这个帧里的新页面号。,.,.,数一下表里出现的“*”号，就知针对这样的页面走向，实施最佳替换策略的整个过程中，发生10次缺页中断，缺页中断率f是：

24、 f=10/16=62.5%,基本思想：被置换的页面是将来不再访问，或是在最远的将来才被访问的页面。 若采用固定分配策略，最佳置换算法可以保证系统的缺页率最低。 但是，无法预知一个进程在内存的若干页面中，哪一个页面是将来不再访问的，甚至最长时间内将不再访问的，因而该算法是无法实现的。 该算法可用于评价其他置换算法的性能。（最理想的）,2.,最近最少使用页面替换策略,.,最近最少使用（LRU）页面替换策略的出发点是：最近被访问过的页面，很可能不久又会被访问，因此尽量不把这种页面作为替换的对象，而是选择最长时间没有被使用的页面作为替换的对象。,.,比如分配给作业的页帧数m=3，其页面走向为： R=

25、0，1，2，3，0，1，2，3，0，1，2，3，4，5，6，7 表给出了实施最近最少使用替换策略时，各页帧内容随页面走向发生变化的情形。,0 3 0* 2,3 1 2 3*,6 4 5 6*,5 4 5* 3,页帧/页面,0 1 2,3 3* 1 2,0 0*,1 0 1*,2 0 1 2*,1 3 0 1*,2 2* 0 1,3 2 3* 1,0 2 3 0*,1 1* 3 0,2 1 2* 0,4 4* 2 3,7 7* 5 6,.,比如，随页面走向的变化，需要访问第3页时发生页面失效。这时在三个页帧里的三页，最先被访问的是第0页，接着被访问的是第1页，最近被访问的是第2页。由LRU策略知

26、，应该把0帧里的第0页替换出去，于是就有表中第4列示出的情形。,数一下表里出现的“*”号，就知道针对这个页面走向，实施LRU策略的整个过程中，发生了16次缺页中断，每一次对新页面的访问，都会发生页面失效，都会产生缺页中断。这时的缺页中断率f是： f=16/16=100%,.,3.,最小使用频率页面替换策略,.,最小使用频率（LFU）页面替换策略的出发点是：如果一页过去没有经常使用，那么将来被用到的可能性就小，因此在需要页面替换时，就将其作为替换的对象。在可能有不止一个页面满足被替换的条件时，就在满足条件的那些页面里随便选一个加以替换。,.,比如分配给作业的页帧数m=3，其页面走向为： R=0，

27、1，2，3，0，1，2，3，0，1，2，3，4，5，6，7 表给出了实施最小使用频率替换策略时，各页帧内容随页面走向发生变化的情形。,0 0 1 3,3 3* 1 2,6 3 1 6*,5 3 1 5*,页帧/页面,0 1 2,3 0 1 3*,0 0*,1 0 1*,2 0 1 2*,1 0 1 3,2 0 1 2*,3 0 3* 2,0 0 3 2,1 0 1* 2,2 0 1 2,4 3 1 4*,7 3 1 7*,.,比如，随着页面走向向前到达第7列时，访问页面2又会出现页面失效。这时在页帧中是第0、1、3的三页。在此之前，第0页和第1页都被访问了两次，第3页只被访问过一次。因此根据L

28、FU策略的思想，将第3页替换出去，于是把第2页调入第2页帧。,.,数一下表里出现的“*”号，知道针对这个页面走向，实施LFU策略的整个过程中，发生了12次缺页中断，这时的缺页中断率f是： f=12/16=75%,4.,先进先出页面替换策略,.,先进先出（FIFO）页面替换策略的出发点是：总把在内存页帧中停留最久时间的页面，作为替换时的对象。,.,比如分配给作业的页帧数m=3，其页面走向为： R=0，1，2，3，0，1，2，3，0，1，2，3，4，5，6，7 表给出了实施最小使用频率替换策略时，各页帧内容随页面走向发生变化的情形。,0 3 0* 2,3 1 2 3*,6 4 5 6*,5 4 5

29、* 3,页帧/页面,0 1 2,3 3* 1 2,0 0*,1 0 1*,2 0 1 2*,1 3 0 1*,2 2* 0 1,3 2 3* 1,0 2 3 0*,1 1* 3 0,2 1 2* 0,4 4* 2 3,7 7* 5 6,.,比如，在把0、1、2页调入页帧后，访问第3页时就发生页面失效。这时在三个页帧里的第0页在内存中停留的时间最久，因此把它替换出去，就有表第4列示出的情形。随着页面走向到达5列时，访问的第0页不在内存，故发生页面失效。这时在三个页帧里的第1页在内存中停留时间最久，因此把它替换出去，于是就有表第5列示出的情形。,.,数一下表里出现的“*”号，知道针对这样的页面走向

30、，实施FIFO策略的整个过程中，发生了16次缺页中断，这时的缺页中断率f是： f=16/16=100%,返回目录,该算法与进程的实际运行规律不相适应，进程中的某些程序代码或数据可能需要高频使用，该算法将导致这种类型的页面被反复的换进换出，从而降低系统性能。,某作业的页面走向为：R=1，2，3，4，1，2，5，1，2，3，4，5。实行FIFO页面替换策略。试问：分配的页帧数m分别是3和4时，计算各自的缺页中断率。,3 1 2 3*,5.2.3 关于静态替换策略的进一步讨论,1.,FIFO策略的异常现象,按常理，分给作业的帧数增多，发生页面失效的可能性就下降。但对某些页面走向、且采用FIFO页面替

31、换策略时，有时增加分配给作业可用的帧数，它的页面失效次数反而会上升，性能下降。操作系统中称其为“Belady异常”现象。,.,例5-3 ：,解：,m=3时FIFO策略的实施情况。这时的缺页中断率f是：f=9/12=75%。,(1),(2),m=4时FIFO策略的实施情况。这时的缺页中断率f是：f=10/1284% 。,1 4 1* 3,5 5 3 4,页帧/页面,0 1 2,4 4* 2 3,1 1*,2 1 2*,3 1 2 3*,2 4 1 2*,5 5* 1 2,1 5 1 2,2 5 1 2,3 5 3* 2,4 5 3 4*,1 1 2 3 4,5 4 5* 2 3,页帧/页面,0

32、1 2 3,4 1 2 3 4*,1 1*,2 1 2*,2 1 2 3 4,5 5* 2 3 4,1 5 1* 3 4,2 5 1 2* 4,3 5 1 2 3*,4 4* 1 2 3,m=3时LRU策略的实施情况。实施LRU策略的整个过程中，发生了10次缺页中断，这时的缺页中断率f是：f=10/1284%。,m=4时LRU策略的实施情况。实施LRU策略的整个过程中，发生了8次缺页中断，这时的缺页中断率f是：f=8/1267%。,.,对于LRU页面替换策略，不可能发生所谓的“Belady异常”现象。,例5-4 ：,某作业的页面走向有： R=1，2，3，4，1，2，5，1，2，3，4，5 实行

33、LRU页面替换策略。试问：分配的页帧数m分别是3和4时，计算各自的缺页中断率。,解：,1 4 1* 3,5 3 4 5*,页帧/页面,0 1 2,4 4* 2 3,1 1*,2 1 2*,3 1 2 3*,2 4 1 2*,5 5* 1 2,1 5 1 2,2 5 1 2,3 3* 1 2,4 3 4* 2,3 1 2 3*,(2),1 1 2 3 4,5 5* 2 4 3,页帧/页面,0 1 2 3,4 1 2 3 4*,1 1*,2 1 2*,2 1 2 3 4,5 1 2 5* 4,1 1 2 5 4,2 1 2 5 4,3 1 2 5 3*,4 1 2 4* 3,(1),“二次机会”页

34、面替换策略的基础是FIFO，按页面进入帧的先后次序，把各个帧组织成一个链表队列，为页表里每个页面的表项增加“访问位”R，当页面被访问时就设置它。利用R位是0或是1，区别在最近一段时间内被访问过的页面和未被访问过的页面。,2.,二次机会页面替换策略,.,.,选择替换对象时，总是从队列的第1帧（它是最早进入内存的页面）开始考察，若该页面的R位为“0”，表示从上次页面替换以来，到现在它都没被访问过。即这个页面既老又没用，因此就替换它；若R位为“1”，表示从上次页面替换以来，它被访问过，因此暂时不把它作为替换的对象，而是将它的R位清零，然后排到链表的最后（体现再给它一次机会），在链表上继续往下搜索符合

35、条件的替换对象。,二次机会页面替换策略的示意,.,A,B,C,D,E,F,G,H,链表首指针,链表尾指针,R=1,A,B,C,D,E,F,G,H,链表首指针,链表尾指针,R=0,(a),(b),插入到队列最后,.,二次机会页面替换策略是在页面链表上寻找一个从上次替换以来没有被访问过的页面。若所有的页面都访问过了，那么这个算法就成为纯粹的先进先出页面淘汰算法。,某作业的页面走向有：R=2，3，2， 1，5，2，4，5，3，2，5，2。实行Clock页面 替换策略。试问：分配的页帧数m=3时，计算 缺页中断率。,如图示，最上为页面走向，帧旁箭头是下次替换时考察的帧位置。帧里数字是加载到该帧的页号，

36、数字旁星号“*”是该页面R位目前应是1，所注“F”表示页面走向中的页面是由页面失效通过缺页中断调入帧的。,3.,时钟页面替换策略,.,把页面组织成循环链表的形式，用指针指向当前最先进入内存的页面页帧。当页面失效需替换时，先检查指针指向的页面的R位。若R位为“0”，就替换它，让新页面进入它占用的页帧，然后指针按顺时针方向移动一个位置；若R位为“1”，则将R位清“0”，然后把指针按顺时针方向移动一个位置。重复这一考察过程，直找到一个R位为“0”的页面为止。它是二次机会页面替换策略的变形，称为“时钟”页面替换策略。,A,G,J,D,B,C,L,K,H,I,F,E,指针 移动方向,页面失效时，考察 指

37、针所指页面，根 据R位采取动作： R=0时替换该页； R=1时清零，往下考察,2*,2*,3*,2 3 2 1 5 2 4 5 3 2 5 2,2*,3*,2*,3*,1*,5*,3,1,5*,2*,1,5*,2*,4*,5*,2*,4*,3*,2,4,3*,2*,4,3*,2,5*,3*,2*,5*,页面走向：,F,F,F,F,F,F,F,F,页面失效：,例5-6 ：,解：,返回目录,5.2.4 请求页式动态替换策略,1.,工作集的概念,.,请求页式存储管理是基于“请求式”读取策略的。在这个前提下，固定放置、可变放置、局部替换、全局替换之间，可以交叉形成三种组合：“固定放置、局部替换”，“可

38、变放置、全局替换”以及“可变放置、局部替换”。,工作集，就是一种可以用来实现“可变放置、全局替换”的动态页面替换策略。,.,.,“工作集”，是指一个进程当前正在使用的页面的集合。根据“局部性”原理，任何时刻进程运行时只需要少数几页在内存。若能为一个进程分配可满足其当前局部需要的页帧，随之通过页面失效把这些页面调入，那么运行就会顺利进行，在一段时间间隔内就不会再发生缺页，除非进程的执行进入了另一个“局部”，开始下一个局部页帧的调整。,人们不可能预知不同时刻进程将会访问哪些页面，只能依据进程过去某段时间间隔内的运行行为，来预测和近似其将来某段时间间隔内的运行行为，以确保在进程继续运行以前，它的工作

39、集就已经在内存中了。这就是所谓的“工作集模型”。,.,.,对于某进程，在任一小段时间间隔（t-, t）里，由最近内存访问所用过的页面组成的集合WS(t, )，就是该进程在时间t的工作集。其中，称是工作集的窗口。,.,页面走向：. . . 2 6 1 5 7 7 7 7 5 1 6 2 3 4 1 2 3 4 4 4 3 4 3 4 4 4 1 3 2 3 4 4 4 3 4 4 4 . . .,WS(t1,10) =1,2,5,6,7,WS(t2,10) =3,4,t1,t2,例如：,每个页面有访问位R，访问时置位；,将所有进程的帧组成一个循环链表；,2.,工作集时钟页面替换策略,.,工作集时

40、钟页面替换策略的基础是时钟页面替换策略。基本做法如下：,1620 0,2032 1,2020 1,1213 0,2003 1,2014 1,1980 1,2084 1,1620 0,2032 1,2020 1,1213 0,2003 1,2014 0,1980 1,2084 1,2204,当前实际时间：,上次 使用时间,R位,(a),(b),1620 0,2032 1,2020 1,2204 1,2003 1,2014 0,1980 1,2084 1,(c),新页面,(1),(2),通过指针定位起始页帧，页面替换时就从该页帧开始考虑其作为替换对象；,(3),每个页面有“上次使用时间”域，记录上

41、次使用时间；,(4),(5),替换时，先查指针所指页面。若R=1，表示被访问过，将R置为0，指针指 向下一个页面；,(6),若指针所指帧R=0，且当前实际时间减它上次使用时间（简称“生存时间”）大于，它就是替换对象；,(7),若生存时间小于或等于，暂时做上记号，将来再做定夺；,(8),没合适替换对象时，就把R=0、且生存时间最长的页面作为替换对象。,返回目录,5.3 请求段式虚拟存储管理,5.3.1 请求段式虚拟存储管理,请求段式虚拟存储是在段表的表项里，增加“段失效”位。若段失效位为0，表示所需段不在内存，要通过缺段中断从磁盘调入所需的程序段，以达到扩充内存的目的。,.,请求段式虚拟存储用户

42、空间虚拟地址以及段表的表项如图所示。,.,虚拟地址：,段号(s),段内位移(d),I,M,其他控制位,段起始地址,段表项：,修改位,段失效位(缺段中断位),段长,.,由于组成作业进程程序的各段有可能只有一部分在内存，因此段表表项中必须要有一位用来标明该段当前是否在内存，这就是 “段失效”位I的作用。,.,段表表项中，还需有“修改”位M，用 来表示该段自装入内存后到目前为止内容 是否发生过变化。若没有变化（M=0）， 那在把这段作为替换对象时，就不必往磁盘做回写操作；M=1时，替换该段就必须进行回写。,.,得到一个虚拟地址空间中的虚拟地址后，以地址中给出的“段号”为索引查段表。如果相应表项中的I

43、=1，表示该段现在内存，于是可以根据表项中的“段起始地址”和虚拟地址中的“段内位移”形成物理地址，完成所需的操作；如果I=0，表示该段现在不在内存，于是发出中断请求，根据该段在磁盘的位置，将它调入内存。,返回目录,5.3.2 段的动态链接,1.,段的动态链接,把对程序段的链接编辑工作推迟到程序执行时进行，将它纳入到统一的地址空间中去。那么，这样的链接编辑称为“动态链接”。,.,.,为实现段的动态链接，软、硬件要增加如下的支持功能：,(1),间接字,指令中出现的地址是“直接”的 ，即该地址直接指向操作数；是“间接”的，即该地址指向的是存放直接地址的地方，到那个地方去，才能得到操作数的地址。称存放

44、直接地址的地方为“间接字”。,.,.,LOAD,100,100：,2009,操作码,指令：,操作数地址,LOAD*,200,200：,999,操作码,指令：,间接字地址,间接字,999：,2009,操作数,操作数,(a),(b),图(a)是直接编址的指令形式，图(b)是间接编址的指令形式。为了区分起见，在图(b)的操作码右上角，标注了一个星号“*”。,(2),间接字中的链接中断位,为能告知系统需要实施动态链接，在间接字里增设链接中断位（L），以提供要进行动态链接的信息。若L=0，表示所需程序段已在作业的虚拟地址空间里，不需进行动态链接；若L=1，表示所需程序段当前不在虚拟地址空间里，要进行动态

45、链接，将其纳入到作业的地址空间中来。因此发出“链接中断”信号，进行动态链接处理。,.,运行到指令“LOAD* 1#，2|”时， 发现是间接编址，由地址“2|”到本段的230处得到间接字。由于间接字的链接中断位L=1，发出链接中断，请求进行链接处理。,指令“LOAD 1#，X|”的翻译结果是三个部分：,2.,动态链接的实现,.,以MULTICS系统中采用的动态链接为例。比如在汇编或编译前有如图所示的W段和X段。W段有指令：“LOAD 1#，X|”，表示把X段里处的数据2009227读到1号寄存器。,LOAD 1#，X|, , ,： 2009227, , ,W段,X段,(1),LOAD* 1#，2

46、|, , ,W段(段号=2),1 2|,230, ,260 “7X|”, ,间接字,外部引用 字符串,段表,段起址,段号,0,1,2,段名,段号,0,1,2,MAIN,A,W,段名-段号对照表,(a),(b),链接中断位,(2),间接编址指令“LOAD* 1#，2|”；,a),b),230处的间接字，链接中断位L=1，指明在本段260处，能够得到外部 引用的字符串“7X|”；,c),260处的外部引用字符串，串里的数字“7”，表示该字符串的长度是7个字符。,完成 对段X链接 后，重新执 行“LOAD* 1#，2|”。这时链接中断位L=0， 即“3|”是要访问的地址。用段号“3”查段表，得到 段

47、在内存起址，加上段内位移“200”，得到所需数据“2009227”。,链接中断处理,(3),LOAD* 1#，2|, , ,W段(段号=2),230, ,260 “7X|”, ,段表,段起址,段号,0,1,2,3, ,X段(段号=3),200,2009227, ,0 3|,间接字, ,X段(段号=3),200, 200, ,段名,段号,0,1,2,MAIN,A,W,段名-段号对照表,(a),(b),2009227, ,X段符号表, ,X,3,(c),(4),.,由间接字中的直接地址“2|”得到外部引用字符串，得知需链接的是 X段。编译后，X段的情形如图(a)所示，上面是 X段本身，下面是X段的

48、符号表。,操作系统查阅“段名-段号”对照表后，将段号“3”分配给X段。于是，“段名-段号”对照表如图(b)所示。,.,.,将X段调入内存，填写段表；修改W段间接字里的链接中断位L=0，将地址部分修改为“3|”，完成与X段的链接，如图(c)所示。,返回目录,5.4.1 Linux存储管理的硬件基础,1.,两种工作模式,80386有两种工作模式：实模式和保护模式（也称虚拟地址模式）。实模式下，只能寻址1MB地址空间，不能启用页式机制，不区分特权级，分段功能受到极大限制。保护模式时，按段组织存储器，每段最长4GB，可寻址4GB物理地址及64TB虚拟地址空间，允许每个任务的虚拟地址空间最多可有16K个

49、段。在分段基础上可实行分页，也可不实行分页。Linux采用80386的保护模式。,5.4 Linux的存储管理,.,.,80386有4个32位的控制寄存器：CR0CR3，主要用于操作系统的分页机制。如图所示给出了CR0、CR2和CR3的内容。,PG,PE,CR0：,分页允许位,保护允许位,CR3：,页目录基址寄存器,0,31,0,31,12 11,CR2：,页面失效地址寄存器,0,31,在允许实施分页机制时，Linux常采用二级或三级页表结构，第1级结构称为页目录，它的基址被保存在CR3里。由于页目录总是被放在以4KB（=212B）为单位的存储器边界上，所以其地址的低12位总为0。,.,段描述

50、符表就是通常所说的段表，它里 面的每一个表项称作段描述符，有全局描述符表（GDT）和局部 描述符表（LDT）之分。两个描述符表里的每个段描述符都占用8个字节，具有相同的格式，记录着各段的详细信息。,分段机制通过“段描述符表”和“段选择符”，来实现段内逻辑地址到线性地址的转换的。,2.,Linux的分段机制和分页机制,在保护模式下，Linux可使用分段机制和分页机制来实现地址转换。分段机制和分页机制是两种不同的转换机制，是整个地址转换过程中的不同转换层次。在地址转换中，分段机制总是要启用的，分页机制则根据需要而启用或禁止。,.,.,分段机制是把由段号，段内位移组成的逻辑地址转换成一个32位的线性

51、地址；分页机制是把一个32位的线性地址转换成为物理地址。这样的两个过程，如图所示。,段号，段内位移,虚拟地址：,分段机制,线性逻辑地址,分页机制,物理地址,.,3.,分段机制,.,段描述符表,(1),(2),作业逻辑地址空间一半由GDT映射，一半由LDT映射，它们分别映射8K个段。GDT和LDT的区别是GDT映射的8K个段是系统中所有进程共享的那些段，而LDT映射的则是进程私用的段。在进程切换时，要加载待运行进程的LDT，GDT则保持不变。,段选择符给出当前要转换的逻辑地址的段号。80386通过代码段寄存器（CS）、数据段寄存器（DS）等存放当前进程的各段基址，所以段选择符实际上就是段寄存器的

52、统称。,.,段选择符,(1),(2),段选择符里除记录作为索引的段号外，还有所谓的选择（TI）域（由它决定是从GDT，还是从LDT选择段描述符），以及请求者特权级（RPL）域等。,(3),虚拟地址为：段选择符：段内位移，把虚拟地址转换为线性地址的步骤是：,(a),往段寄存器中装入段选择符，同时把段内位移装入某寄存器；,根据段选择符中的信息（TI、RPL等），以及相应段描述符表中的信息（段基址、段长等），进行一系列合法性检查；,(b),(c),通过检查后，将段描述符中的段基址和某寄存器中的段内位移相加，就得到需要转换的线性地址。,4.,分页机制,在允许分页的情况下，线性地址将由分页机制中的页表转

53、换成为物理地址。,.,.,Linux通常采用两级页表结构：第一级“页目录”共有1K（210）个表项，每个表项长4个字节，存放在一个帧中。页目录的每个表项指向一个页表（第二级）。每个页表也有1K（210）个表项，每个表项长度为4个字节，也存放在一个帧中。,.,80386的控制寄存器CR3指示页目录的起始地址。,80386内部有一个AM（即TLB或快表），它自动保留CPU最近访问的32个页表表项的内容，可覆盖128KB范围内的内存。平均来说，这时的命中率可以达到90%。,.,返回目录,这样，32位的虚拟地址空间，最多划分1M个页面，它的页表里有 1M个表项；若每个表 项占用4B，那么 这个页表就占

54、 4MB大小的存储 空间。把页表又划分成 1024个页面，为它们建 立索引，形成有1024个 表项的页目录。如图 （b）所示。,5.4.2 Linux多级页表的地址转换,1.,二级页表的地址转换,虚拟地址空间分页采用两级机制：先对虚拟地址空间分页，形成页表；再对页表分页，形成页表的页表。这样虚拟地址空间里的页，以及页表中的页，都能存放在不连续帧里，提高了内存的利用率。在Linux里，称“页表的页表”为页目录（或页表索引）。,页面索引号,p1,页号,p2,位移量,d,32位虚拟地址：,10位,10位,12位,一个页面,一个页面,用户虚拟 地址空间,1M个页面,1M个表项 (1024个页面),10

55、24个表项,页表,页表索引,.,按4KB的帧长，32位虚拟地址在二级页式存储管理时，页内位移量d占用12位，把20位页号p细分为10位的“页目录”p1和10位的“页号”p2两个部分，如图（a）所示。,.,.,在知道一个虚拟地址后，就可根据地址的前10位p1，先去查页表索引，以便得到该索引所对应的页表放在哪一个内存块。,.,再由地址中间的10位p2，去查这个页表，得到该页所对应的内存块的起始地址。,最后，与位移量d相加后，就得到最终所需要的物理地址。,p1,p2,d,索引项,页表索引,p1,1页,1页,表项,页表,p2,d,内存,物理 地址,1块,1块,二级页表的地址转换过程,(1),(2),(

56、3),2.,三级页表的地址转换,Linux提供三级 页表式的分页式结 构，第1 级为页表 索引，第 2 级为页 表中间索引，第3 级是页表。三级页表式的分页式 结构，其地址变换将更为复杂，速度会降低。,.,页表或页帧基址,31,12 11,P,R/W,U/S,2 1 0,读/写位,存在位,用户/系统位,D,写标志位,6,pmd,p,d,页目录,页目录基址,页中间目录,虚拟地址：,内存,pgd,页目录,页中间目录,页表,页内位移,页表,1页帧,页目录和页表的表项结构,3.,对于Linux，页目录和页表表项的结构基本相同，如图所示。,.,(a),页表或页帧基址,(b),存在位（P）,(c),读/写位（R/W）,(d),用户/系统位（U/S）,(e),写标志位（D）,返回目录,在Linux存储管理中，帧是进行存储分配和释放的单位。系统设置一张存储分块表mem_map，它的每一个表项是mem_map_t型结构，对应着一帧，记录该帧的有关信息。,5.4.3 内存空间的管理,.,为记录内存各帧的使用情