第5章虚拟存储器

1、2022-3-5阜阳师范学院计算机与信息学院1第五章 存储器管理5.1 虚拟存储器的基本概念5.2 请求分页存储管理方式5.3 页面置换算法5.4 “抖动”与工作集5.5 请求分段存储管理方式2022-3-5阜阳师范学院计算机与信息学院25.1 虚拟存储器的基本概念5.1.1 虚拟存储器的引入（1） 常规存储器管理方式的特征 一次性、驻留性（2）局部性原理：时间、空间局限性（3）虚拟存储器的定义：具有请求调入和置换功能，能从逻辑上对内存容量进行扩充的一种存储系统。2022-3-5阜阳师范学院计算机与信息学院3虚拟存储器的容量o 一个虚拟存储器容量是由计算机的总线地址结构确定的。如：若CPU的有

2、效地址长度为32位，则程序可以寻址范围是0 232 -1 ，即虚存容量为 4GB。o 以CPU时间和外存空间换取昂贵内存空间，这是操作系统中的资源转换技术。2022-3-5阜阳师范学院计算机与信息学院4例题1o 设主存容量为1MB，外存容量为400MB，计算机系统的地址寄存器有32位，那么虚拟存储器的最大容量是（ ）o 1MBo 401MBo 1MB+232BA. 232BD2022-3-5阜阳师范学院计算机与信息学院55.1.2 虚拟存储器的特征 n离散性：在分配内存时采用离散分配方式n多次性：一个作业被分成多次调入内存运行n对换性：允许在作业的运行过程中进行换进、换出。n虚拟性：能够从逻辑

3、上扩充内存容量，使用户所看到的内存容量远大于实际内存容量。 虚拟性以多次性和对换性为基础；多次性和对换性又必须建立在离散分配的基础上。2022-3-5阜阳师范学院计算机与信息学院6例题2o 下列关于虚拟存储器的叙述中，正确的是（ ）o 虚拟存储只能基于连续分配技术o 虚拟存储只能基于非连续分配技术o 虚拟存储容量只受外存容量的限制o 虚拟存储容量只受内存容量的限制B2022-3-5阜阳师范学院计算机与信息学院75.1.3 虚拟存储器的实现方法 需要动态重定位一、请求分页系统 以页为单位转换 需硬件：（1）请求分页的页表机制（2）缺页中断（3）地址变换机构 需实现请求分页机制的软件（置换软件等）

4、二、请求分段系统 以段为单位转换:（1）请求分段的段表结构（2）缺段中断（3）地址变换机构 需实现请求分段机制的软件（置换软件等）2022-3-5阜阳师范学院计算机与信息学院85.2 请求分页存储管理方式 2022-3-5阜阳师范学院计算机与信息学院92. 缺页中断机构TO B指令copy A A: B:页面6543212022-3-5阜阳师范学院计算机与信息学院103. 地址变换机构 缺页中断处理保留CPU现场从外存中找到缺页内存满否？选择一页换出该页被修改否？将该页写回外存OS命令CPU从外存读缺页启动I/O 硬件将一页从外存换入内存修改页表否是是否页表项在快表中？CPU检索快表访问页表否

5、页在内存？修改访问位和修改位形成物理地址地址变换结束否页号页表长度?开始程序请求访问一页产生缺页中断请求调页修改快表是越界中断是是2022-3-5阜阳师范学院计算机与信息学院11在为进程分配物理块时，要解决下列的三个问题：（1 1） 保证进程可正常运行所需要的最少物理块数 最小物理块数的确定（2 2） 每个进程的物理块数，是固定值还是可变值 物理块的分配策略（3 3） 不同进程所分配的物理块数，是采用平均分配算法还是根据进程的大小按照比例予以分配。 物理块的分配算法2022-3-5阜阳师范学院计算机与信息学院12如： mov A, B允许间接寻址：则至少要求3个物理块。mov A,B1000X

6、XXX若是单地址指令，且采用直接寻址方式，则所需最少物理块数为2。2022-3-5阜阳师范学院计算机与信息学院132. 物理块的分配策略 2022-3-5阜阳师范学院计算机与信息学院141）固定分配局部置换思路：分配固定数目的内存空间（物理块），在整个运行期间都不改变策略：如果缺页，则先从该进程在内存的页面中选中一页，进行换出操作，然后再调入一页。特点：为每个进程分配多少物理块是合适的值难以确定。（少：置换率高 多：资源浪费）。2. 物理块的分配策略 2022-3-5阜阳师范学院计算机与信息学院152 2）可变分配全局置换思路：每个进程预先分配一定数目的物理块，同时OSOS也保持一个空闲物理块

7、队列。策略：当缺页时，首先将对OSOS所占有的空闲块进行分配，从而增加了各进程的物理块数。当OSOS的空闲块全部用完，将引起换出操作,OS,OS从内存中选择一页，可能是系统中任一进程的页。是一种最易实现的策略2. 物理块的分配策略 2022-3-5阜阳师范学院计算机与信息学院163 3）可变分配局部置换思路：先为每个进程预先分配一定数目的物理块，系统根据缺页率动态调整各进程占有的物理块数目，使其保持在一个比较低的缺页率状态下。策略：如果缺页，则先从该进程在内存的页面中选中一页，进行换出操作特点：使大部分进程可以达到比较近似的性能2. 物理块的分配策略 2022-3-5阜阳师范学院计算机与信息学

8、院173. 物理块分配算法 将系统中所有可供分配的物理块，平均分配给各个进程。缺点：未考虑各进程本身的大小。2022-3-5阜阳师范学院计算机与信息学院18niiSS1mSSbii3. 物理块分配算法2022-3-5阜阳师范学院计算机与信息学院19 在实际应用中，为了照顾重要的、急迫的作业尽快完成，应为它分配较多的内存空间。方法：一部分按比例分配给各进程；另一部分则根据各进程的优先权，适当地增加其相应份额后，分配给各进程。3. 物理块分配算法2022-3-5阜阳师范学院计算机与信息学院205.2.3 调页策略 （1）预调(prepaging)提前取页：预先装入主存一页或几页。（根据程序顺序行为

9、空间局部性，主要用于进程的首次调入时） （2）请调(demand paging)请求取页：当用到某页而不在主存时即发生缺页中断时调入。（每次仅调入一页，较费系统开销）2022-3-5阜阳师范学院计算机与信息学院21 外存有两个部分：文件区和对换区。对换区I/O操作速度比文件区相对快一些，因此一般应当尽量使用对换区来调入页面。对于不同情况，采用不同的策略：存储内容驻留时间主要目标分配方式文件区文件较长久提高文件存储空间的利用率离散对换区从内存换出的进程短暂提高进程换入和换出的速度连续2022-3-5阜阳师范学院计算机与信息学院221) 缺页中断 2) 保留CPU现场环境，转入缺页中断处理程序 3

10、) 缺页中断处理：查找页表，得到对应的外存物理块号。如果内存有空闲，则启动磁盘操作，将所缺的页面读入，并修改页表。否则，到4)。 4) 若内存没有空闲，则执行置换算法，选出要换出的页面，如果该页修改过，应将其写入磁盘，然后将所缺页调入内存，修改相应表项，将其存在位置为1，并放入快表。 5) 利用修改后的页表，形成物理地址，访问内存数据。2022-3-5阜阳师范学院计算机与信息学院23假设一个进程的逻辑空间为n页，系统为其分配的内存物理块数为m（mn）。pS访问页面成功的次数（即所访问页面在内存中）pF访问页面失败的次数（即所访问页面不在内存中， 需要从外存调入）pA=S+F进程总的页面访问次数

11、 则：缺页率 f=F/A2022-3-5阜阳师范学院计算机与信息学院24假设被置换的页面被修改的概率是，pta 缺页中断处理时间，ptb 被置换页面没有被修改的缺页中断时间那么，缺页中断处理时间的计算公式为： t= ta+（1-） tb2022-3-5阜阳师范学院计算机与信息学院255.3 页面置换算法(Page-Replacement Algorithms) 5.3.1 最佳置换(OPT)和先进先出(FIFO)置换算法5.3.2 最近最久未使用(LRU)置换算法5.3.3 Clock置换算法 5.3.4 其它置换算法2022-3-5阜阳师范学院计算机与信息学院265.3.1最佳置换算法和先进

12、先出置换算法1. 最佳(Optimal)置换算法2022-3-5阜阳师范学院计算机与信息学院271. 最佳(Optimal)置换算法2022-3-5阜阳师范学院计算机与信息学院282. 先进先出(FIFO)页面置换算法 算法：淘汰最先进入主存的页2022-3-5阜阳师范学院计算机与信息学院29 （2）实现：已调入内存的页面，按先后次序链接成一队列 （3）依据: 先进入的可能已经使用完毕。 理论上来说，如果分配的块数增加的话，缺页率 是会减少，但是FIFO算法对于一些特殊的页面访问序列会有随着分配的块数增加，缺页率也增加的异常现象。 （4） 随着物理块数的增多缺页率增大！(举例) （5）性能差、

13、有异常现象（Belady现象）2022-3-5阜阳师范学院计算机与信息学院30先进先出页面置换算法（FIFO）（例） 有一虚拟存储系统，采用FIFO的页面淘汰算法。在内存中为每个进程分配3个物理块。进程有5页，执行时访问页面的顺序为0，1，2，3，0，1，4，0， 1，2，3，4，（1）该进程运行时总共出现了几次缺页（2）若为每个进程在内存中分配4个物理块，又将产生几次缺页。（3）如何解释所出现的现象。2022-3-5阜阳师范学院计算机与信息学院31物理块m=3访问序列：0，1，2，3，0，1，4，0， 1，2，3，42022-3-5阜阳师范学院计算机与信息学院32物理块m=4访问序列：0，1

14、， 2， 3， 0，1，4，0， 1，2，3，42022-3-5阜阳师范学院计算机与信息学院33FIFO算法与Belady现象o Belady现象： 采用FIFO算法时，若对一个进程未分配它所要求的全部页面，有时就会出现分配的物理块数增多，缺页率反而提高的异常现象。o Belady现象的描述： 一个进程P要访问 M个页， OS分配 N个内存页面给进程 P；对一个访问序列S ，发生缺页次数为 PE(S, N)。当N增大时， PE(S, N) 时而增大，时而减小。o Belady现象的原因： FIFO算法的置换特征与进程访问内存的动态特征是矛盾的，即被置换的页面并不是进程不会访问的。2022-3-

15、5阜阳师范学院计算机与信息学院345.3.2 最近最久未使用(LRU)置换算法 2022-3-5阜阳师范学院计算机与信息学院35 虽然是一种比较好的算法，但要求系统有较多的支持硬件，须有两类硬件之一的支持：寄存器或栈。1）寄存器 为每个在内存中的页面配置一个移位寄存器，用来记录某进程在内存中各页的使用情况。移位寄存器表示为: R=Rn-1Rn-2Rn-3R2R1R0 当进程访问某物理块时，要将相应寄存器的Rn-1位置成1。此时，定时信号将每隔一定时间将寄存器右移一位。2. LRU置换算法的硬件支持 R0R1R2R3R4R5R6R7 R实页0001011110011110011010110101

16、01011000100001010101100110010100100012345678某进程具有8个页面时的LRU访问情况R0R1R2R3R4R5R6R7 R实页000000000000000000000000000000000000000000000000000000000001011112345678某进程具有8个页面时的LRU访问情况R0R1R2R3R4R5R6R7 R实页000000000000000000000000000000000000000000000000000101110000000012345678某进程具有8个页面时的LRU访问情况R710011110R0R1R2R3

17、R4R5R6R7 R实页000000000000000000000000000000000000000000010111100111100000000012345678某进程具有8个页面时的LRU访问情况R701101011R0R1R2R3R4R5R6R7 R实页000101111001111001101011010101011000100001010101100110010100100012345678某进程具有8个页面时的LRU访问情况2022-3-5阜阳师范学院计算机与信息学院36 利用一个特殊的栈来保存当前使用的各个页面的页面号。把被访问的页面页号移到栈顶，于是栈底则是最近最久未使用页

18、面的页面号。44设一进程访问页面的页面号序列为：设一进程访问页面的页面号序列为：4，7，0，7，1，0，1，2，1，2，6随着进程的访问，栈中页面号的变化情况：随着进程的访问，栈中页面号的变化情况：477470040774071147100470114701224702114701227012662）栈栈底栈底栈顶栈顶栈顶栈顶栈顶栈顶栈顶栈顶栈顶栈顶2022-3-5阜阳师范学院计算机与信息学院37 选择到当前时间为止被访问次数最少的页面被置换； 每页设置访问计数器，每当页面被访问时，该页面的访问计数器加1； 发生缺页中断时，淘汰计数值最小的页面，并将所有计数清零；2022-3-5阜阳师范学院计

19、算机与信息学院385.3.3 Clock置换算法 v 每页设置一位访问位，内存中的所有页链接成一个循环队列；v 循环检查各页面的使用情况，访问位为“0”，选择该页淘汰；访问位为“1”，复位访问位为“0”，查询指针前进一步（给该页第二次驻留内存的机会，简称“第二次机会”算法）。v 又称为“最近未使用”置换算法（NRU）2022-3-5阜阳师范学院计算机与信息学院392. 改进型Clock置换算法 由访问位A和修改位M可以组合成下面四种类型的页面： 1类(A=0, M=0): 表示该页最近既未被访问，又未被修改， 是最佳淘汰页。 2类(A=0, M=1)： 表示该页最近未被访问，但已被修改， 并不

20、是很好的淘汰页。 3类(A=1, M=0)： 最近已被访问， 但未被修改，该页有可能再被访问。 4类(A=1, M=1): 最近已被访问且被修改，该页可能再被访问。 2022-3-5阜阳师范学院计算机与信息学院40执行过程 访问位A，修改位M共同表示一个页面的状态 四种状态：00 01 10 11 三轮扫描：v第一轮：查找00页面，未找到，下一步；v第二轮：查找01页面，将所扫描过的页面的A位复位为“0”，未找到，下一步；v第三轮：若第2步失败，重复1和2（如果需要）。2022-3-5阜阳师范学院计算机与信息学院41 系统为一个有6页的进程分配4个物理块，其页表如下所示，页的大小为1K，请计算

21、逻辑地址为17C8H的物理地址。（表中：R(读/ 访问)、 M(修改) ）按FIFO算法为多少？按LRU算法为？按CLOCK算法为多少？例题32022-3-5阜阳师范学院计算机与信息学院42分析o CLOCK算法： 淘汰R=0,M=0的页面0，对应的块号为7（111），o FIFO算法：n淘汰120时刻转入的页面2，对应的块号为2（10）o LRU算法：n淘汰260时刻引用的页面1，对应的块号为4（100）1 17 7C C8 800010001011101111100110010001000逻辑地址为：17C8H页号页内地址（10位）0001 010001 0111 1100 100011

22、1100 1000页号页内地址（10位）0001 010001 0111 1100 100011 1100 10002022-3-5阜阳师范学院计算机与信息学院43例题4o设某计算机的逻辑地址空间和物理地址空间均为64KB，按字节编址。若某进程最多需要6页数据存储空间，页的大小为1KB，操作系统采用固定分配局部置换策略为此进程分配4个物理块。页号物理块号装入时刻访问位0713011423012220013916012022-3-5阜阳师范学院计算机与信息学院44当该进程执行到时刻260时，要访问逻辑地址为17CAH的数据，请回答下列问题：（1）该逻辑地址对应的页号是多少？（2）若采用先进先出（

23、FIFO）置换算法，该逻辑地址对应的物理地址是多少？要求给出计算过程。 （3）若采用时钟（Clock）置换算法，该逻辑地址对应的物理地址是多少？要求给出计算过程。（设搜索下一页的指针沿顺时针方向移动，且当前指向2号物理块，如图所示）2022-3-5阜阳师范学院计算机与信息学院45解答o17CAH=（0001 0111 1100 1010）2 （1）页大小为1K，所以页内偏移地址为10位，页号为6位所以其对应的页号为5.（2）FIFO算法：被置换的页面0所在的物理块号为7，所以其对应的物理地址为（0001 1111 1100 1010）2 =1FCAH（3） Clock算法：被置换的页面2所在的

24、物理块号为2，所以其对应的物理地址为（0000 1011 1100 1010）2 =0BCAH 页号（6位）页内地址（10位）0001 010001 0111 1100 101011 1100 10102022-3-5阜阳师范学院计算机与信息学院46练习o 页式存储管理，允许用户编程空间为32个页面（每页1KB），主存为16KB，如有一用户程序有10页长，且某时刻该用户程序页表如下表所示：o 若分别遇到有以下三个逻辑地址：0AC5H、1AC5H、3AC5H处的操作，试计算并说明存储管理系统将如何处理。逻辑页号物理块号0817243102022-3-5阜阳师范学院计算机与信息学院47（1）影响页

25、面换进换出效率的若干因素q 页面置换算法q 写回磁盘的频率q 读入内存的频率5.3.4 页面缓冲算法(PBA)2022-3-5阜阳师范学院计算机与信息学院48（2）页面缓冲算法(PBA)q被置换页面的选择和处理：用FIFO算法选择被置换页 如果页面未被修改，就将其归入到空闲页面链表的末尾 否则将其归入到已修改页面链表。 此时页面在内存中并不做物理上的移动，只是将页表中的表项移到上述两链表之一5.3.4 页面缓冲算法(PBA)2022-3-5阜阳师范学院计算机与信息学院49q需要调入新的页面时，将新页面内容读入到空闲页面链表的第一项所指的页面。q空闲页面和已修改页面，仍停留在内存中一段时间，如果

26、这些页面被再次访问，只需较小开销，而被访问的页面可以返还作为进程的内存页。q当已修改页面达到一定数目后，再将它们一起调出到外存，然后将它们归入空闲页面链表，这样能大大减少I/O操作的次数。页面缓冲算法(PBA)2022-3-5阜阳师范学院计算机与信息学院50补充作业 在一个请求页式存储管理系统中，进程P共有5页。访问串为3、2、1、0、3、2、4、3、2、1、0、4时，试采用FIFO、LRU置换算法，计算当分配给该进程的物理块分别为3、4时，访问过程中发生的缺页次数和缺页率，比较所得的结果，浅析原因。2022-3-5阜阳师范学院计算机与信息学院515.4 “抖动”与工作集（驻留集）o 产生抖动

27、的原因n 同时在系统中运行的进程太多，分配给每一个进程的物理块太少n 不能满足进程正常运行的基本要求n 频繁地出现缺页，必须请求系统将所缺之页调入内存2022-3-5阜阳师范学院计算机与信息学院525.4 “抖动”与工作集（驻留集）o 进程在运行时对页面的访问是不均匀的，即往往在某段时间内的访问仅局限于较少的若干个页面；而在另一段时间内，则又可能仅局限于对另一些较少的页面进行访问。o 这些页面被称为活动页面o 如果能够预知进程在某段时间间隔内要访问哪些页面，并能将这些页面提前调入内存，将会大大地降低缺页率，从而减少置换工作，提高CPU的利用率。o 所谓驻留集，是指在某段时间间隔内，进程要访问的

28、页面集合。具体地说，把某进程在时间t的驻留集记作w（t，），变量称为驻留集的“窗口大小” 2022-3-5阜阳师范学院计算机与信息学院535.4 “抖动”与工作集（驻留集）o 抖动的预防方法n 采取局部置换策略n 把工作集算法融入到处理机调度中n 利用L=S准则调节缺页率n 选择暂停的进程2022-3-5阜阳师范学院计算机与信息学院54例题5 请求分页管理系统中，假设某进程的页表内容如下表所示。 页号页框号有效位（存在位）0 0101H101H1 11 1-0 02 2254H254H1 1 页面大小为4KB，一次内存的访问时间是100ns，一次快表（TLB）的访问时间是10ns，处理一次缺页

29、的平均时间为108ns（已含更新TLB和页表的时间），进程的驻留集大小固定为2，采用最近最少使用置换算法（LRU）和局部淘汰策略。2022-3-5阜阳师范学院计算机与信息学院55假设 TLB初始为空； 地址转换时先访问TLB，若TLB未命中，再访问页表（忽略访问页表之后的TLB更新时间）； 有效位为0表示页面不在内存，产生缺页中断，缺页中断处理后，返回到产生缺页中断的指令处重新执行。设有虚地址访问序列2362H、1565H、25A5H，请问： （1） 依次访问上述三个虚地址，各需多少时间？给出计算过程。 （2） 基于上述访问序列，虚地址1565H的 物理地址是多少？请说明理由。 2022-3-

30、5阜阳师范学院计算机与信息学院56分析 （1）页面大小为4KB= 212 ，可得三个虚地址的页号P如下： 2362H：P=2，访问快表10ns，因初始为空，访问页表100ns得到页框号，合成物理地址后访问主存100ns，共计10ns+100ns+100ns=210ns。 1565H：P=1，访问快表10ns，落空，访问页表100ns落空，进行缺页中断处理108ns，合成物理地址后访问主存100ns，共计10ns+100ns+108ns+100ns=318ns。 25A5H：P=2，访问快表，因第一次访问已将该页号放入快表，因此花费10ns便可合成物理地址，访问主存100ns，共计10ns+10

31、0ns=110ns。 2022-3-5阜阳师范学院计算机与信息学院57例题6某请求分页系统的页面置换策略如下： 从0时刻开始扫描，每隔5个时间单位扫描一轮驻留集（扫描时间忽略不计）且在本轮没有被访问过的页框被系统回收，并放入到空闲页框链尾，其中内容在下一次分配之前不清空。当发生缺页时，如果该页曾被使用过且还在空闲页链表中，则重新放回进程的驻留集中；否则，从空闲页框链表头部取出一个页框。 2022-3-5阜阳师范学院计算机与信息学院58 忽略其它进程的影响和系统开销，初始时进程驻留集为空。目前系统空闲页的页框号依次为32、15、21、41 进程P依次访问的为、 、 、 、 、 、 （1）当虚拟页

32、为时，对应的页框号是什么？分析： 初始驻留集为空，l 1页对应的页框为空闲链表中的第一个空闲页框32l 3页对应的页框为空闲链表中的第一个空闲页框15l 0页对应的页框为空闲链表中的第三个空闲页框212022-3-5阜阳师范学院计算机与信息学院59 忽略其它进程的影响和系统开销，初始时进程驻留集为空。目前系统空闲页的页框号依次为32、15、21、41 进程P依次访问的为、 、 、 、 、 、 。（2）当虚拟页为时，对应的页框号是什么？分析：l 在第二轮扫描中只对0页进行扫描，而1和3页对应的页框插入到空闲页框链尾l 发生在第三轮扫描中，此刻该页又被重新访问，因此应被重新放回驻留集中，其页框为322022-3-5阜阳师范学院计算机与信息学院60 忽略其它进程的影响和系统开销，初始时进程驻留集为空。目前系统空闲页的页框号依次为32、15、21、41 进程P依