操作系统第5章存储管理3虚拟存储.ppt

5.6虚存的引入,第5章之三虚拟存储器,（一）程序一次性装入内存带来的问题1.单一连续分配、多道分区分配、分页和分段存储管理的共同特点是：,都需要将程序一次性全部装入内存。,2.程序一次性装入带来一些问题(1)内存总是有限的，当作业很大，内存不足时？,带来的问题是：内存空间连一个作业也无法全部装入！,(2)当使用固定分区管理，分页分段管理需要装入多个作业时，每个作业只能占用内存的一部份，但分给作业的内存不足时？,作业一130K,作业二180K,作业三250K,带来的问题是：没有哪一个分区能完全装入一个用户作业！,（二）程序局部性原理,1.时间局部性：一条指令被执行后，那么它可能很快会再次执行。如循环、子程序、堆栈、计数或累计变量等。2.空间局部性：若某一存储单元被访问，那么与该存储单元相邻的单元可能也会很快被访问。如程序代码的顺序执行，对线性数据结构的访问或处理、常用变量等。,问题：能否将部分程序装入内存后就开始运行作业？为什么？,（三）程序局部性原理的应用,一个程序特别是一个大型程序的一部份装入内存是可以运行的。理由是：1.程序中的某些部份在程序整个运行过程中可能根本不用。如：出错处理程序。2.许多表格占用固定数量的内存空间，而实际上只用到其中的一部份。3.许多程序段是顺序执行的，还有一些程序段是互斥执行的。如菜单选择功能。4.在程序的一次执行过程中，有些程序执行之后，从某个时刻起不再用到。,（四）虚拟存储器的定义与特性,1.虚拟存储器是指仅把作业的一部份装入内存便可以运行作业的存储器系统。也即，指具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。,2.虚拟存储器的新特性虚拟扩充。不是物理上扩大内存空间，而是逻辑上扩充了内存。也即是把大的逻辑地址空间映射到较小的物理内存上。部分装入。每个作业不是全部一次装入内存。只将当前要运行的装入内存就开始运行。离散分配。装入内存的部份作业不必占用连续的内存空间，而是“见缝插针”。多次对换。一个作业运行时，它所需要的程序和数据分成多次调入内存。而在内存中那些暂时不用的程序和数据可换出到外存对换区，以腾出尽量多的内存空间供运行进程使用。,交换区（SWAP）：进程刚建立时，页表记录页面所在辅存位置，即程序文件所在的外存位置。但程序文件中一般包含有程序的二进制目标码及数据初始值和初值为0的工作区。后两者在回写时不能写入程序文件所在辅存区，因此引入了交换区临时存储区。（就绪挂起、阻塞挂起的进程）,例：内存原存放外存的21块和24块（存放数据和初始值），现需调入25和27块，因内存不足，需对换。,3.虚拟存储器的容量不是无限大的。它受两方面的限制。一个是指令中表示的地址长度。假设地址长度为32字节，按字节寻址，则逻辑空间（虚存空间）大小为232个字节。（个字节）另一个是外存容量。用户的虚拟空间不能超过硬盘中作业的存放空间。,（四）虚拟存储器的定义与特性,（五）实现虚拟存储的基本方法可采用页式虚存管理、段式虚存管理和段页式虚存管理。如：页式虚存管理。在页式管理的基础上，仅将进程的一部分页放于主存。页表项中注明该页是否在主存。程序执行时，如果访问的页不在主存，根据页表项的指示，将其从外存调入主存，如果此时无可用的内存空间，则先淘汰若干页帧。（其他方法基本相同）,一、基本原理页式虚拟存储管理方式是在分页系统的基础上，增加了请求调页功能、页面置换功能所形成的虚拟存储器系统。,5.7页式虚存管理,状态位：表示该页是否已经调入内存。访问位：表示该页在内存间是否被访问过修改位：表示该页在内存是否被修改过。,二、页表项结构对页表增加了一些项目，具体如下：,三、地址变换机构与页式管理基本相同，只是缺页时产生缺页中断，先将该页调入内存，再访问。见下图示。,指令执行步骤与缺页中断处理过程,5.8页面置换算法一、目的与要求：1、掌握页面替换策略中的基本概念2、掌握驻留集固定的三种页面替换策略。3、掌握影响缺页中断率的主要因素4、了解动态驻留集的页面替换策略。,二、重点与难点1、固定驻留集算法2、SWS等实用动态驻留集算法。三、课时：2(90分钟)四、教法：讲授法,五、教具六、教学过程1、介绍有关概念及替换策略分类2、详细介绍驻留集固定的页面替换策略3、简略介绍可变驻留集替换策略,本节主要讲述的内容一、页面替换策略中的基本概念二、页面替换策略的分类三、驻留集大小固定的替换策略四、页面替换算法解题举例五、影响缺页中断率的主要因素六、页面替换策略应用实例七、驻留集可变的替换策略八、替换策略选择,一、页面替换(策略)策略中的基本概念页面置换算法：地址映射过程中，若在页面中发现所要访问的页面不再内存中，则产生缺页中断。当发生缺页中断时操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法(策略)。,一、页面替换(策略)策略中的基本概念驻留集(工作集)：进程的合法页集合；也即系统分给一个进程的内存可用块数。访问串（页面走向）：进程的存储访问序列或进程访问虚空间的地址踪迹。页式虚存管理以页为基本单位，只需页号即可。页面走向可合理简化。,页面走向可合理简化原则：（1）对于给定的页面大小，仅考虑其页号，不关心完整的地址。（2）如果当前对页面P进行了访问，那么，马上又对该页访问就不会缺页。这样连续出现的页号就简化为一个页号。,举例：某进程依次访问如下地址：0100，0432，0101，0612，0102，0103，0104，0101，0611，0102，0103，0104，0101，0610，0102，0103，0104，0101，0609，0102，0105。若页面大小为100，上述访问串可简化为：1，4，1，6，1，6，1，6，1，6，1,二、页面替换策略分成两类：驻留集大小固定的替换策略；驻留集大小可变的替换策略。,三、驻留集大小固定的替换策略(一)先进先出置换算法(FIFO)(二)最佳置换算法(OPT)(三)最近最少使用算法(LRU)(四)时钟置换算法(CLOCK),(一)FIFO替换算法,置换策略：优先淘汰最早进入内存的页面，亦即在内存中驻留时间最久的页面,1.FIFO算法举例：驻留集大小为3，访问串为：7,0,1,2,0,3,0,4,2,3,0,3,2设开始三页内存为空，每调入一页均缺页。试列表求出FIFO算法的面页淘汰过程，淘汰的页序和缺页次数？,FIFO算法页面替换过程如下表表示：,7,0,1,2,0,3,0,4,2,3,0,3,2,是,0,1,2,0,3,0,4,2,3,0,3,2,是,是,7,7,1,2,0,3,0,4,2,3,0,3,2,是,是,7,7,7,0,0,是,2,0,3,0,4,2,3,0,3,2,是,是,7,7,7,0,0,是,1,是,0,1,7,0,3,0,4,2,3,0,3,2,是,是,7,7,7,0,0,是,1,是,0,2,0,2,否,是,1,1,0,0,4,2,3,0,3,2,是,是,7,7,7,0,0,是,1,是,0,2,0,2,否,是,1,1,1,2,3,3,是,0,4,2,3,0,3,2,是,是,7,7,7,0,0,是,1,是,0,2,0,2,否,是,1,1,1,2,3,3,是,2,3,0,0,是,0,2,3,0,3,2,是,是,7,7,7,0,0,是,1,是,0,2,0,2,否,是,1,1,1,2,3,3,是,2,3,0,0,是,3,0,4,4,是,0,3,0,3,2,是,是,7,7,7,0,0,是,1,是,0,2,0,2,否,是,1,1,1,2,3,3,是,2,3,0,0,是,3,0,4,4,是,0,0,4,4,2,2,是,0,0,3,2,是,是,7,7,7,0,0,是,1,是,0,2,0,2,否,是,1,1,1,2,3,3,是,2,3,0,0,是,3,0,4,4,是,0,0,4,4,2,2,是,4,2,3,3,是,0,3,2,是,是,7,7,7,0,0,是,1,是,0,2,0,2,否,是,1,1,1,2,3,3,是,2,3,0,0,是,3,0,4,4,是,0,0,4,4,2,2,是,4,2,3,3,是,否,否,结果：缺页次数共10次。,（1）FIFO方法的特点：实现方便。不需要额外硬件。效果不好，有Belady奇异。,（2）FIFO存在Belady奇异：指替换策略不满足随着驻留集的增大，页故障数（缺页中断次数）一定减少的规律。这一规律由Belady于1969年发现，故称为Belady异常,2.对FIFO替换算法的进一步认识,（3）FIFO算法的Belady奇异现象举例对于如下的页面访问序列：1，2，3，4，1，2，5，1，2，3，4，5当内存块数量分别为3和4时，试问：使用FIFO置换算法产生的缺页中断是多少？（所有内存开始时都是空的，凡第一次用到的页面都产生一次缺页中断）内存块为3时，缺页中断次数为9次。,内存块为4时，缺页中断次数为10次。,内存块为3时，缺页中断次数为9次。,内存块为4时，缺页中断次数为10次。,(二)OPT替换算法,置换策略：当要调入一页而必须淘汰旧页时，应该淘汰以后不再访问的页，或距现在最长时间后要访问的页面。,1966年，Belady提出最佳(优)页面替换算法(OPTimalreplacement，OPT)。是操作系统存储管理中的一种全局页面替换策略。,1.OPT算法举例：驻留集大小为3，访问串为：7,0,1,2,0,3,0,4,2,3,0,3,2设开始三页内存为空，每调入一页均缺页。试列表求出FIFO算法的面页淘汰过程，淘汰的页序和缺页次数？,7,0,1,2,0,3,0,4,2,3,0,3,2,是,7,0,1,2,0,3,0,4,2,3,0,3,2,是,是,7,OPT算法置换过程,7,1,2,0,3,0,4,2,3,0,3,2,是,是,7,0,是,7,0,OPT算法置换过程,7,1,2,0,3,0,4,2,3,0,3,2,是,是,7,0,是,7,0,7,0,1,是,OPT算法置换过程,7,1,0,3,0,4,2,3,0,3,2,是,是,7,0,是,7,0,7,0,1,是,7,0,1,1,0,2,2,否,是,OPT算法置换过程,7,1,0,3,0,4,2,3,0,3,2,是,是,7,0,是,7,0,7,0,1,是,7,0,1,1,0,2,2,否,是,2,2,0,0,3,否,是,OPT算法置换过程,7,1,0,3,0,4,2,3,0,3,2,是,是,7,0,是,7,0,7,0,1,是,7,0,1,1,0,2,2,否,是,2,2,0,0,3,否,是,2,2,3,3,否,否,是,4,OPT算法置换过程,7,1,0,3,0,4,2,3,3,2,是,是,7,0,是,7,0,7,0,1,是,7,0,1,1,0,2,2,否,是,2,2,0,0,3,否,是,2,2,3,3,否,否,是,4,否,否,OPT算法置换过程,结果：缺页次数共7次,2.对OPT替换算法的进一步认识(1)是最优的页面替换策略OPT策略对任意一个访问串的控制均有最小的时空积（进程所占空间与时间的乘积）。(2)是不可实现的策略由于需要预先得知整个访问串的序，故不能用于实践,仅作为一种标准，用以测量其他可行策略的性能。,(三)LRU替换算法,置换策略：淘汰上次使用距当前最远的页或最近很少使用的页。,LRU是LeastRecentlyUsed的缩写，即最近最少使用。,1.LRU算法举例：驻留集大小为3，访问串为：7,0,1,2,0,3,0,4,2,3,0,3,2设开始三页内存为空，每调入一页均缺页。试列表求出FIFO算法的面页淘汰过程，淘汰的页序和缺页次数？,7,0,1,2,0,3,0,4,2,3,0,3,2,是,LRU算法置换过程,7,0,1,2,0,3,0,4,2,3,0,3,2,是,是,7,LRU算法置换过程,7,1,2,0,3,0,4,2,3,0,3,2,是,是,7,0,是,7,0,LRU算法置换过程,7,1,2,0,3,0,4,2,3,0,3,2,是,是,7,0,是,7,0,7,0,1,是,LRU算法置换过程,7,1,0,3,0,4,2,3,0,3,2,是,是,7,0,是,7,0,7,0,1,是,7,0,1,1,0,2,2,否,是,LRU算法置换过程,7,1,0,3,0,4,2,3,0,3,2,是,是,7,0,是,7,0,7,0,1,是,7,0,1,1,0,2,2,否,是,2,2,0,0,3,否,是,LRU算法置换过程,7,1,0,3,0,4,2,3,0,3,2,是,是,7,0,是,7,0,7,0,1,是,7,0,1,1,0,2,2,否,是,2,2,0,0,3,否,是,LRU算法置换过程,4,0,0,3,3,是,7,1,0,3,0,4,2,3,0,3,2,是,是,7,0,是,7,0,7,0,1,是,7,0,1,1,0,2,2,否,是,2,2,0,0,3,否,是,LRU算法置换过程,4,0,0,3,3,是,2,0,0,4,4,是,7,1,0,3,0,4,2,3,0,3,2,是,是,7,0,是,7,0,7,0,1,是,7,0,1,1,0,2,2,否,是,2,2,0,0,3,否,是,LRU算法置换过程,4,0,0,3,3,是,2,0,0,4,4,是,3,2,2,4,4,是,7,1,0,3,0,4,2,3,3,2,是,是,7,0,是,7,0,7,0,1,是,7,0,1,1,0,2,2,否,是,2,2,0,0,3,否,是,LRU算法置换过程,4,0,0,3,3,是,2,0,0,4,4,是,3,2,2,4,4,是,否,否,结果：缺页次数共9次,2.对LRU算法的进一步认识到(1)LRU没有Belady奇异。即随着驻留集的增大,页故障一定减少。(2)需要硬件配合，实现费用高，但效果适中。,（3）LRU替换算法无Belady奇异现象举例：对于如下的页面访问序列：1，2，3，5，2，4，5，2，1，3，2，5当内存块数量分别为3和4时，试问：使用LRU置换算法产生的缺页中断是多少？（所有内存开始时都是空的，凡第一次用到的页面都产生一次缺页中断）,LRU算法，内存块为3时，缺页中断次数为8次。,LRU算法，内存块为4时，缺页中断次数为7次。,（4）LRU算法的实现方法实现方法1：用计数器实现LRU。实现方法2：用栈实现LRU。实现方法3：用矩阵实现LRU。实现方法4：用寄存器实现LRU。,实现方法1用计数器实现LRU,每页增加一个计数器，用计数器方法记录情况。命中时，刚访问到的页计数器清0，其余页计数器加1；淘汰时选择页计数器值最大的页面，新换入的页计数器清0，其余页计数器加1。例如：,举例：若驻留集大小为3，访问串为7,0,1,2,0,3,0,4,2,3,0,3,2,淘汰的页序：712304,缺页次数：9次,实现方法2用栈实现LRU,可用一个特殊的栈来保存当前使用的各个页面的页面号。每当进程访问某页面时便将该面页从栈中移出，然后将它压入栈顶。因此，栈顶始终是最新的页号，而栈底则是最近最久未使用的页号。例如:,举例：驻留集大小为3，访问串为7,0,1,2,0,3,0,4,2,3,0,3,2,淘汰的页：712304缺页次数：9次,栈顶,栈底,(四)时钟置换算法(CLOCK)CLOCK算法是LRU算法的近似算法。CLOCK算法给每个页面设置一个访问位，标识该页最近有没有被访问过，再将内存中的所有页面通过一个指针链接成一个循环队列。其算法流程图如下图所示。,CLOCK算法举例：驻留集大小为3，访问串为7,0,1,2,0,3,0,4,2,3,0,3,2,淘汰页序:OOO712034,初始,注意:若循环链表存在当前访问页(命中)时，直接将其访问位改为1指针不移动（命中后指针不移动）；否则，若当前P指针指向页面的访问位为0，则淘汰该页，调入新页将其访问位改为1，指针移到下一个物理块；若当前P指针指向页面的访问位为1则将其访问位改为0,并移动指针到下一个物理块。CLOCK算法的优点是:比LRU算法少了很多硬件的支持，实现比较简单，但和FIFO算法相比，仍需要较多的硬件支持。,四、页面替换算法解题举例例1:在页式管理中，设给定的主存块数为三块，已知页面走向为：4，3，2，1，4，3，5，4，3，2，l，5。调页时分别采用FIFO算法、OPT算法、栈结构实现的LRU算法和计数器实现的LRU时，问：写出淘汰页序，淘汰次数和缺页率各是多少？要求写出算法过程,1、FIFO页面置换算法,缺页次数为9次；缺页中断率f=9/1275%.,2、OPT页面置换算法,缺页次数为7次，缺页中断率：f=7/12=58.3%。,上题OPT页面置换算法，当内存块为4块时，结果又是多少？,缺页次数为6次，缺页中断率：f=6/12=50%。,课堂练习,3、栈结构实现LRU页面置换算法,缺页次数为10次，缺页中断率：f=10/12=83.3%。,课堂练习,对于如下的页面访问序列：7，1，2，0，3，0，4，2，3，0，3，2，7，0。当内存块数量为4时，试问：使用栈结构实现LRU置换算法产生的缺页中断是多少？写出依次淘汰的页号。（所有内存开始时都是空的，凡第一次用到的页面都产生一次缺页中断。要求写出计算步骤。）,缺页次数为7次，缺页中断率：f=7/14=50%。,课堂练习答案,4、页计数器结构实现LRU页面置换算法,课堂练习,对于如下的页面访问序列：7，1，2，0，3，0，4，2，3，0，3，2，7，0。当内存块数量为4时，试问：使用LRU计数器置换算法产生的缺页中断是多少？写出依次淘汰的页号。（所有内存开始时都是空的，凡第一次用到的页面都产生一次缺页中断。要求写出计算步骤。）,课堂练习答案,缺页次数为7次，缺页中断率：f=7/14=50%。,五、关于缺页中断率的讨论（一）概念。假定一个作业共有n页，系统分配给它的主存块是m块（m,n均是正整数，且1=m=n）.因此，该作业最多有m页可同时装入主存。如果作业执行中访问页面的总次数为A，其中有F次访问的页面未装入主存，故产生了F次缺页中断。现定义：f=F/A把f称为“缺页中断率”。,（二）影响缺页中断率的因素1、分配给作业的主存块数分配给作业的主存块数越多，则同时装入主存的页面数就越多，缺页中断的次数就越少。反之，就越高。,2、页面的大小页面的大小取决于主存分块的大小，块越大则页面越大，页面大则作业的页数就越少，一页内装入的信息量就越大，缺页中断的次数就越少。反之，就越高。,3、编制程序的方法程序编制的方法不同，对缺页中断的次数有很大影响。例如：有一个程序要把128128的数组置初值“0”，数组中的每一个元素为一个字。现假定页面的尺寸为每页128个字，数组中的每一行元素存放在一页。能供这个程序使用的主存块只有一块，开始时该内存块为空。若程序编制如下：,intA127,127;for(j=0;j128;j+)for(i=0;i128;i+)Ai,j=0;由于程序是按列清“0”的，所以每执行一次Ai,j=0(清“0”)就会产生一次缺页中断，总共产生了（128*128）次中断。,若重新编制这个程序如下：IntA127,127;for(i=0;i128;i+)for(j=0;j128;j+)Ai,j=0;那么，每装入一页后就对一行元素全部清“0”后才产生缺页中断，故总共只产生了128次缺页中断。,4、与页面调度算法有关页面调度算法对缺页中断率的影响也很大，调度不好就会出现“抖动”。,例：考虑下面的页访问串：1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6。假定分别有1，2，3，4，5，6，7个页块，应用下面的页面替换算法时，各会出现多少次缺页中断？（1）LRU；（2）FIFO；（3）Optimal。,由上可知：（1）不同的调度算法，缺页中断次数有差别，其中OPT算法最优，但无法实现，因为谁也不能对程序的执行中要使用的页面作出精确的断言。然而，它可以作为一个衡量各种具体算法的标准。（2）当驻留集增加到一定数量后，三种算法的缺页中断次数，差别不大。,课堂练习：考虑下述页面走向：4，3，2，1，4，3，5，4，3，2，1，5。当内存块分别为3和4时，试问LRU(基于栈结构算法)、FIFO、OPT这三种置换算法的缺页次数各是多少（假设所有内存块起初为空）？,当给定的内存块=3时，LRU栈结构算法的置换过程如下：,当给定的内存块=4时，LRU栈结构算法的置换过程如下：,六、一个页面替换策略的实用方法（兼顾FIFO和LRU策略）为页帧在页表项中增加一位使用位，硬件每访存一次，即将对应页的使用位置1，操作系统页面管理程序定时将所有使用位清0。淘汰时任选一个使用位为0的页。操作系统选择淘汰页时，尽量避免选被修改过的页。因此，首先选择