ch44.7虚拟存储管理

1、CH4 存储管理4.1 主存储器 4.2 连续存储空间管理 4.3 分页式存储管理 4.4 分段式存储管理4.5 段页式存储管理4.6 交换技术和覆盖技术 4.7 虚拟存储管理 4.8 实 例 研 究：Intel Pentium存储管理硬件设施14.7 虚拟存储管理4.7.1 虚拟存储管理的概述4.7.2 请求分页虚拟存储管理4.7.3 请求分段虚拟存储管理4.7.4 请求段页式虚拟存储管理24.7.1虚拟存储管理概述 1、问题的提出 程序大于内存 当要运行的作业很多，而内存空间不足的时，只能让一部分作业先运行，大量作业只能在外存中等待。 虚拟存贮管理策略考虑的出发点是基于程序局部性原理在一段

2、时间内，一个程序的执行往往呈现出高度的局部性，它对内存的访问是很不均匀的。32、局部性原理局部性原理：指程序在执行过程中的一个较短时期内，所执行的指令地址和指令的操作数地址分别局限于一定区域。主要表现为：时间局部性：一条指令的一次执行和下次执行，一个数据的一次访问和下次访问都集中在一个较短时期内；原因是由于在程序中存在着大量的循环、子程序等程序结构。 空间局部性：若某一存储单元被访问，那么与该存储单元相邻的单元可能也会很快被访问。4虚拟存储管理的主要技术是部分装入和部分对换。 部分装入：当用户作业被调度开始执行时，不必将作业全部读入主存，而是将当前需要执行的部分读入主存，其他部分根据作业执行的

3、需要逐步装入主存。 部分对换：在程序执行过程中，当内存空间紧张时，操作系统将暂不执行的部分程序和数据调出，保存在外存上，从而腾出内存空间存放将要装入的程序和数据，或者留给系统再分配。 虚拟存储管理的目的：把分开编址的二级存储器内存和辅存,变成面向用户的，逻辑上可以统一编址的虚拟存储器。3、虚拟存储管理的基本思想54、虚拟存储器的定义在具有层次结构存储器的计算机系统中，采用自动实现部分装入和部分对换功能，为用户提供一个比物理主存容量大得多的，可寻址的一种“主存储器”。虚拟存储器的大小受限于计算机的地址结构及可用的外存的容量。总容量不超过物理内存和外存交换区容量之和。65、虚拟存储器的特征 离散性

4、：系统内存管理机构分配给该作业的内存空间不一定是连续的。 多次性：多次性是指一个作业被分成多次调入主存内运行。 对换性：在进程运行过程中，可以把那些暂时不运行的程序和数据，从内存调至外存的对换区，把当前要运行的程序和数据调入内存。可见，对换有利于提高内存的利用率。 虚拟性：操作系统通过把内存和辅存从逻辑上结合起来，使用户感觉到存储容量远远大于实际的内存容量，以实现扩充内存的目的。 7实现虚拟存储器必须解决好以下有关问题：主存辅存统一管理问题逻辑地址到物理地址的转换问题部分装入和部分对换问题虚拟存储管理主要采用以下存储管理方法实现： 请求分页虚拟存储管理请求分段虚拟存储管理请求段页式虚拟存储管理

5、84.7.2 请求分页式存储管理 动态离散分配方式1. 基本思想等份主存、用户逻辑地址空间 将程序的逻辑地址空间划分成若干大小相等的区域，称为页或页面。相应地，将物理内存划分为与页大小相等的区域，称为块或物理块，并分别给页和块编以连续的序号0、1、2、3、主存分配原则 以块为单位分配，作业以页调入块中，作业块不一定是连续的，但不必全部装入。9请求分页式存储管理基本思想部分装入：在进程开始运行之前，不是装入全部页面，而是装入一个或零个页面，之后根据进程运行的需要，动态装入其它页面；部分对换：当内存空间已满，而又需要装入新的页面时，则根据某种算法淘汰某个页面，以便装入新的页面102. 数据结构作业

6、表：整个系统有一个作业表，描述系统内各个进程页表的起始位置和大小，用于地址转换。物理页面表（内存块表）：整个系统有一个物理页面表，描述物理内存空间的空闲和占用状况。页表：每个进程有一个页表，描述该进程相应页在系统中的状况。如是否在内存？页对应的块号？11标志位（存在位）：用于指示该页是在内存还是在外存。访问统计：在近期内被访问的次数，或最近一次访问到现在的时间间隔。决定淘汰哪页（由不同的算法决定）。修改位：表示该页在调入内存后是否被修改过。外存地址：用于指出该页在外存上的地址。页表表项：页号物理块号标志位访问字段修改位外存地址123 .请求分页存储管理系统页面分配过程该页修改过吗？Y写回辅存N

7、根据某种算法淘汰一页调整页表地址映射YN获得逻辑地址：页号、页内位移该页在内存？N有无空闲块？Y调入页面产生缺页中断启动待执行指令执行指令指令地址+1缺页中断处理过程 页面淘汰134.缺页中断什么是缺页中断在地址映射过程中，在页表中发现所要访问的页不在内存，则产生缺页中断。操作系统接到此中断信号后，就调出缺页中断处理程序，根据页表中给出的外存地址，将该页调入内存，使作业继续运行下去。 缺页中断与与一般的中断的区别 在指令执行期间产生和处理中断信号。当所缺的页面调入之后，重新执行被中断的指令。 一条指令在执行期间，可能产生多次缺页中断。14缺页率缺页率f等于 缺页次数F / 内存总访问次数A (

8、比率) 即 f = F / A15发缺页中断5.请求分页地址转换过程(1) 逻辑空间地址主存(用户区)CPU逻辑地址快表主存(系统区) 查页表辅存缺页中断处理分解地址访问MMU查快表命中不命中页表命中调页装入、改表装入快表运行进程映象物理地址页框 页内地址页号 页内地址16分页式虚拟存储系统的硬件支撑(1) 主存管理单元MMU完成逻辑地址到物理地址的转换功能，它接受虚拟地址作为输入，物理地址作为输出，直接送到总线上，对主存单元进行寻址。 17分页式虚拟存储系统的硬件支撑CPUMMU内存CPU把逻辑地址送至MMUMMU把物理地址送至主存 MMU的位置、功能和16个4KB页面情况下MMU的内部操作

9、CPU送入的逻辑地址(8196) 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0MMU送出的物理地址0 010 11 001 12 110 13 000 14 100 15 011 16 000 07 000 08 101 19 000 0页号 页框号 在主存否18MMU主要功能(1)管理硬件页表基址寄存器。(2)分解逻辑地址。(3)管理快表TLB。(4)访问页表。(5)发出缺页中断或越界中断，并将控制权交给内核存储管理处理。(6)设置和检查页表中各个特征位。19 地址转换过程(2)查快表有登记无登记查页表登记入快表发

10、缺页中断在主存在辅存形成绝对地址继续执行指令重新执行被中断指令恢复现场调整页表和主存分配表装入所需页面主存有空闲块保护现场有选择调出页面该页是否修改未修改已修改把该页写回辅存相应位置操作系统硬件逻辑地址无206 .页面的调入和分配策略请求调页(demand paging)：只调入发生缺页时所需的页面。优点：确保只有被访问的页调入主存，节省内存。缺点：调入页的开销大，增加了对外存I/O次数预调页(prepaging)：OS依据某种算法预测，预先将某页或若干页调入主存。优点：提高调页的I/O效率。缺点：基于预测，若调入的页在以后很少被访问，则效率低。常用于程序装入时的调页。（1）调入策略调入策略确

11、定在外存中的页面调入时机。在虚拟页式管理中有两种常用策略。21（2）页面分配策略系统为进程分配主存,需考虑因素: 分给进程的空间越小,同一时间处于主存的进程就越多，至少有一个进程处于就绪态的可能性就越大如果进程只有小部分在主存里,即使局部性很好,缺页中断率还会相当因程序的局部性原理，分给进程的主存超过一定限度后，再增加主存空间,不会明显降低进程的缺页中断率。22页面分配策略：固定分配进程保持页框数固定不变,称固定分配;进程创建时,根据进程类型和程序员的要求决定页框数,只要有一个缺页中断产生,进程就会有一页被替换。23页面分配策略：可变分配进程分得的页框数可变, 称可变分配;进程执行的某阶段缺页

12、率较高,说明目前局部性较差，系统可多分些页框以降低缺页率，反之说明进程目前的局部性较好,可减少分给进程的页框数24页面替换策略：局部替换和全局替换页面替换需要采用一定的算法来实现算法如果页面替换算法的作用范围是整个系统，称全局页面替换算法,它可以在运行进程间动态地分配页框。解决：从那个进程选择页面？缺页中断率是否上升？如果页面替换算法的作用范围局限于本进程，称为局部页面替换算法,它实际上需要为每个进程分配固定的页框。 25固定分配和局部替换策略配合使用(1)进程分得的页框数不变，发生缺页中断，只能从进程的页面中选页替换，保证进程的页框总数不变。策略难点：应给每个进程分配多少页框?给少了,缺页中

13、断率高;给多了,使主存中能同时执行的进程数减少，进而造成处理器和其它设备空闲。26固定分配和局部替换策略配合使用(2) 采用固定分配算法，系统把页 框分配给进程，采用：平均分配，按比例分配, 优先权分配。27可变分配和全局替换策略配合使用先每个进程分配一定数目页框,os保留若干空闲页框,进程发生缺页中断时，从系统空闲页框中选一个给进程,这样产生缺页中断进程的主存空间会逐渐增大,有助于减少系统的缺页中断次数。系统拥有的空闲页框耗尽时 ，会从主存中选择一页淘汰，该页可以是主存中任一进程的页面，这样又会使那个进程的页框数减少，缺页中断率上升。28可变分配和局部替换配合使用其实现要点如下:(1)新进程

14、装入主存时，根据应用类型、程序要求，分配给一定数目页框,可用请页式或预调式完成这个分配。(2)产生缺页中断时,从该进程驻留集中选一个页面替换。(3)不时重新评价进程的分配，增加或减少分配给进程的页框以改善系统性能。297 .页面置换算法最佳置换算法（OPT, Belady算法） 算法：淘汰那些以后永不使用，或者是在最长时间内不再被访问的页。无法实现的，只能作为其它置换算法的衡量标准。 先进先出算法（FIFO） 算法：每次淘汰最先进入主存的页 优点：简单，易于实现 缺点：效率不高，可能产生“抖动”现象30例1：计算缺页次数 某程序在内存中分配三个页面，初始为空，页面走向为4，3，2，1，4，3，

15、5，4，3，2，1，531共缺页中断7次,缺页率=7/12=58%32 共缺页中断9次，缺页率=9/12=75%33例2：计算缺页次数用FIFO算法计算某程序在内存中分配m页初始为空，页面走向为1，2，3，4，1，2，5，1，2，3，4，5。当m=3，m=4时缺页中断分别为多少？34如果在内存中分配3个页面，则缺页情况如下：12次访问中有缺页9次；35如果在内存中分配4个页面，则缺页情况如下：12次访问中有缺页10次；36例2：计算缺页次数m=3时，缺页中断9次m=4时，缺页中断10次注：FIFO页面淘汰算法会产生异常现象，即：当分配给进程的物理页面数增加时，缺页次数反而增加。37抖动现象：采

16、用FIFO算法时，如果对一个进程未分配它所要求的全部页面，有时就会出现分配的页面数增多，缺页率反而提高的异常现象。异常现象的原因：FIFO算法的置换特征与进程访问内存的动态特征是矛盾的，即被置换的页面并不是进程不会访问的。抖动现象38最近最久未使用（LRU）算法 算法：选择淘汰内存中那些在最近一段时间里最久未使用的页面置换。但由于需要记录页面使用时间的先后关系，硬件开销太大。硬件机构如：一个特殊的栈：把被访问的页面移到栈顶，于是栈底的是最久未使用页面。每个页面设立移位寄存器：被访问时左边最高位置1，定期右移并且最高位补0，于是寄存器数值最小的是最久未使用页面。39 缺页中断10次，缺页率=10

17、/12=83%40第二次机会页面替换算法改进FIFO算法,把FIFO与页表中的”引用位”结合起来使用：检查FIFO中的队首页面(最早进入主存的页面),如果它的”引用位”是0,这个页面既老又没有用，选择该页面淘汰; 如果”引用位”是1,说明它进入主存较早，但最近仍在使用。把它的”引用位”清0,并把这个页面移到队尾，把它看作是一个新调入的页。算法含义：最先进入主存的页面，如果最近还在被使用的话,仍然有机会作为像一个新调入页面一样留在主存中。41时钟页面替换算法(1) 算法实现要点(1)： 一个页面首次装入主存，其“引用位”置0 。主存中的任何页面被访问时, ”引用位”置1。淘汰页面时,从指针当前指

18、向的页面开始扫描循环队列，把迁到的”引用位”是1的页面的”引用位”清0,跳过这个页面; 把所迁到的”引用位”是0的页面淘汰掉,指针推进一步。42时钟页面替换算法(2) 算法实现要点(2)：扫描循环队列时，如果迁到的所有页面的”引用位”为1，指针就会绕整个循环队列一圈，把碰到的所有页面的”引用位”清0;指针停在起始位置，并淘汰掉这一页,然后，指针推进一步。43时钟页面替换算法的一个例子 一个页替换前的缓冲区状态下一页替换后的缓冲区状态Page9 use=1Page19Use=1Page1Use=0Page45Use=1Page191Use=1Page556Use=0Page13Use=0Page

19、67Use=1Page33Use=1Page222Use=0下一个帧指针n012345678Page9 use=1Page19Use=1Page1Use=0Page45Use=0Page191Use=1Page727Use=1Page13Use=0Page67Use=1Page33Use=1Page222Use=0n012345678第1页框44时钟页面替换改进算法(1)把”引用位”和”修改位”结合起来使用，共组合成四种情况：(1)最近没有被引用,没有被修改(r=0,m=0)(2)最近被引用,没有被修改(r=1,m=0)(3)最近没有被引用,但被修改(r=0,m=1)(4)最近被引用过,也被修

20、改过(r=1,m=1)45时钟页面替换改进算法(2)步1：选择最佳淘汰页面，从指针当前位置开始,扫描循环队列。扫描过程中不改变”引用位”，把遇到的第一个r=0,m=0的页面作为淘汰页面。步2：如果步1失败，再次从原位置开始，查找r=0且m=1的页面，把把遇到的第一个这样的页面作为淘汰页面，而在扫描过程中把指针所扫过的页面的”引用位”r置0。46时钟页面替换改进算法(3)步3：如果步2失败，指针再次回到了起始位置，由于此时所有页面的”引用位”r均己为0，再转向步1操作，必要时再做步2操作，这次一定可以挑出一个可淘汰的页面。478. 影响缺页次数的因素(1) 分配给进程的物理页面数(2) 页面大小

21、(3) 程序的编制方法(4) 页面淘汰算法489.请求页式存储管理的优缺点优点：作业的程序和数据可按页分散存放在内存中，减少移动开销，有效解决了碎片问题;既有利于改进主存利用率，又有利于多道程序运行。缺点：要有硬件支持，要进行缺页中断处理，机器成本增加，系统开销加大。 4910. 性能问题 颠簸（抖动） 在虚存中，页面在内存与外存之间频繁调度，以至于调度页面所需时间比进程实际运行的时间还多，此时系统效率急剧下降，甚至导致系统崩溃。这种现象称为颠簸或抖动.原因：页面淘汰算法不合理分配给进程的物理页面数太少50工作集模型和工作集置换算法 进程工作集指“在某一段时间间隔内进程运行所需访问的页面集合”

22、。实现思想： 工作集模型用来对局部最佳页面替换算法进行模拟实现，不向前查看页面引用串，而是基于程序局部性原理向后看，在任何给定时刻，一个进程不久的将来所需主存页框数，可通过考查其过去最近的时间内的主存需求做出估计。51 工作集（Working Set）模型 基本思想：根据程序的局部性原理，一般情况下，进程在一段时间内总是集中访问一些页面，这些页面称为活跃页面，如果分配给一个进程的物理页面数太少了，使该进程所需的活跃页面不能全部装入内存，则进程在运行过程中将频繁发生中断。如果能为进程提供与活跃页面数相等的物理页面数，则可减少缺页中断次数。52工作集： 对于给定的访问序列选取定长的区间，称为工作集

23、窗口，落在工作集窗口中的页面集合称为工作集。进程工作集指“在某一段时间间隔内进程运行所需访问的页面集合”。内容取决于页的三个因素： 访页序列特性 时刻Ti 窗口长度()53例： 261234443434441327 | |t1 | |t2 ws(t1)=1,2,5,6,7 ws(t2)=3,45412 请求分页虚拟存储管理的几个设计问题页面大小 .从页表大小考虑 .从主存利用率考虑 .从读写一个页面所需时间考虑 .最佳页面尺寸页面 5512 请求分页虚拟存储管理的几个设计问题 (1)最佳页面尺寸假定S表示用户作业程序的字节数平均长度，P表示以字节为单位的页面长度，且有SP，页表项需要e个字节。

24、作业的页表长度为S/P，占用了Se/P个字节的页表空间，作业的最后一页，浪费的主存平均为P/2字节。对一个作业而言： 浪费的存储字=页表使用的主存空间+内部碎片=Se/P+P/256最佳页面尺寸页面较小时页表占用空间多(因Se/P较大)，页面较大时内部碎片浪费多(因P/2较大)。现对P求一阶导数并令其为0，得到 -Se/P2+1/2=0 那么，可以得出最优页面尺寸 P=根号（2Se） 时，浪费的存储字节最少，称P为最佳 页面尺寸。57(2)页面交换区替换算法要挑选页面淘汰出主存，但被淘汰出去的页面可能很快使用，又要被重新装入主存。操作系统必须保存被淘汰的页面,例如UNIX/Linux使用交换区

25、临时保存页面，系统初始化时,保留一定盘空间作交换区。58(3)写时复制写时复制(copy-on-write)是存储管理节省物理主存(页框)的一种页面级优化技术,已被UNIX和Windows等采用，能减少主存页面内容的复制操作,减少相同内容页面在主存的副本数目。59写时复制(2)原始数据原始数据原始数据进程地址空间物理地址空间原始数据原始数据原始数据进程地址空间物理地址空间原始数据原始数据原始数据进程地址空间原始数据原始数据原始数据进程地址空间页面2副本 页面1页面2页面3页面1页面2页面3604.7.3 请求分段式存储管理 动态离散分配方式1. 基本思想用户程序划分 按程序自身的逻辑关系，将程

26、序的逻辑地址空间划分成若干段，每个段都是独立的逻辑单位，有完整和相对独立的意义。 一个程序由若干段组成，每个段的大小可以不同。 每个程序段都有一个段名，且有一个段号。段号从0开始，每一段也从0开始编址，段内地址是连续的。 61 内存分配 主存以段为单位分配内存，每一个段在内存中占据连续空间，一个进程的各段所分到的主存分区可以是不连续的。部分装入：在作业运行之前，不需要把作业的整个地址空间全部装入主存，而只要将作业当前需要的一段或几段装入主存即可开始运行。部分对换：在执行过程中，当所需要的段不在主存时再将它调入。请求分段式存储管理62特征位：00不在内存，01在内存，11共享段；存取权限：00可

27、执行，01可读，11可写；扩充位：0固定长，1可扩充；标志位：00未修改，01已修改，11不可移动；外存地址：本段在外存上的起始地址。2. 对进程段表的修改段号段长基址特征位存取权限扩充位标志位外存地址633. 缺段中断如果访问的段不在主存中，系统将产生一个缺段中断，请求操作系统将所缺的段调入主存。缺段中断的特殊性缺段中断在指令执行期间产生和进行处理。一条指令的执行可能产生多次缺段中断。64需调入新段S内存中有空闲区S的段长是否合并空闲区，形成长度大于S段长的空闲区为段S分配内存空闲区，调段S至内存修改段表返回内存中空闲区总和大于S段长是按一定的算法淘汰段，形成大于S的空闲区缺段中断处理过程654. 地址转换过程S段在内存否是B 段长？越界中断允许本次访问？YNNY修改访问字段，置访问位和状态分段保护中断查快表或段表，段S的始址+段内位移D形成物理地址67越界中断处理 进程在执行过程中，有时需要扩大分段，如数据段。由于要访问的地址超出原有的段长，所以发越界中断。操作系统处理中断时 ，首先判断该段的“扩充位”，如可扩充，则增加段的长度；否则按出错处理。68