第五讲存储管理3虚拟存储

5.6.1虚存的引入5.6虚拟存储器〔一〕程序一次性装入内存带来的问题1.单一延续分配、多道分区分配、分页和分段存储管理的共同特点是： 都需求将程序一次性全部装入内存。2.程序一次性装入带来一些问题(1)内存总是有限的，当作业很大，内存缺乏时？OS内存用户作业带来的问题是：内存空间连一个作业也无法全部装入！(2)当运用固定分区管理，分页分段管理需求装入多个作业时，每个作业只能占用内存的一部份，但分给作业的内存缺乏时？OS40K内存80K120K作业一130K作业二180K作业三250K带来的问题是：没有哪一个分区能完全装入一个用户作业！〔二〕程序部分性原理1.时间部分性：一条指令被执行后，那么它能够很快会再次执行。如循环、子程序、堆栈、计数或累计变量等。2.空间部分性：假设某一存储单元被访问，那么与该存储单元相邻的单元能够也会很快被访问。如程序代码的顺序执行，对线性数据构造的访问或处置、常用变量等。问题：能否将部分程序装入内存后就开场运转作业？为什么？〔三〕程序部分性原理的运用一个程序特别是一个大型程序的一部份装入内存是可以运转的。理由是：1.程序中的某些部份在程序整个运转过程中能够根本不用。如：出错处置程序。2.许多表格占用固定数量的内存空间，而实践上只用到其中的一部份。3.许多程序段是顺序执行的，还有一些程序段是互斥执行的。如菜单项选择择功能。4.在程序的一次执行过程中，有些程序执行之后，从某个时辰起不再用到。〔四〕虚拟存储器的定义与特性1.虚拟存储器是指仅把作业的一部份装入内存便可以运转作业的存储器系统。也即，指具有恳求调入功能和置换功能，能从逻辑上对内存容量进展扩展的一种存储器系统。2.虚拟存储器的新特性虚拟扩展。不是物理上扩展内存空间，而是逻辑上扩展了内存。也即是把大的逻辑地址空间映射到较小的物理内存上。部分装入。每个作业不是全部一次装入内存。只将当前要运转的装入内存就开场运转。离散分配。装入内存的部份作业不用占用延续的内存空间，而是“见缝插针〞。多次对换。一个作业运转时，它所需求的程序和数据分成多次调入内存。而在内存中那些暂时不用的程序和数据可换出到外存对换区，以腾出尽量多的内存空间供运转进程运用。交换区〔SWAP〕：进程刚建立时，页表记录页面所在辅存位置，即程序文件所在的外存位置。但程序文件中普通包含有程序的二进制目的码及数据初始值和初值为0的任务区。后两者在回写时不能写入程序文件所在辅存区，因此引入了交换区—暂时存储区。〔就绪挂起、阻塞挂起的进程〕23222625272326222527212423242526272421外存交换区外存202122换出21，换入25换出24，换入27内存页表例：内存原存放外存的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算法页面交换过程如下表表示：次序7012030423032页面分配情况是否缺页换出的页7012030423032是次序7012030423032页面分配情况是否缺页换出的页012030423032是是77次序7012030423032页面分配情况是否缺页换出的页12030423032是是77700是次序7012030423032页面分配情况是否缺页换出的页2030423032是是77700是1是017次序7012030423032页面分配情况是否缺页换出的页7030423032是是77700是1是0202否是11次序7012030423032页面分配情况是否缺页换出的页7000423032是是77700是1是0202否是111233是次序7012030423032页面分配情况是否缺页换出的页7010423032是是77700是1是0202否是111233是2300是次序7012030423032页面分配情况是否缺页换出的页7012023032是是77700是1是0202否是111233是2300是3044是次序7012030423032页面分配情况是否缺页换出的页7012303032是是77700是1是0202否是111233是2300是3044是004422是次序7012030423032页面分配情况是否缺页换出的页7012300032是是77700是1是0202否是111233是2300是3044是004422是4233是次序7012030423032页面分配情况032是否缺页换出的页7012304032是是77700是1是0202否是111233是2300是3044是004422是4233是否否次序7012030423032页面分配情况123042300012304237770123042是否缺页是是是是否是是是是是是否否换出的页7012304结果：缺页次数共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次。次序123412512345页面分配情况341253422341253111234125是否缺页是是是是是是是否否是是否换出的页123412内存块为4时，缺页中断次数为10次。次序123412512345页面分配情况4512345334512342223451231111234512是否缺页是是是是否否是是是是是是换出的页123451(二)OPT交换算法置换战略：当要调入一页而必需淘汰旧页时，应该淘汰以后不再访问的页，或距如今最长时间后要访问的页面。1966年，Belady提出最正确(优)页面交换算法(OPTimalreplacement，OPT)。是操作系统存储管理中的一种全局页面交换战略。1.OPT算法举例：驻留集大小为3，访问串为：7,0,1,2,0,3,0,4,2,3,0,3,2…设开场三页内存为空，每调入一页均缺页。试列表求出FIFO算法的面页淘汰过程，淘汰的页序和缺页次数？次序7012030423032页面分配情况是否缺页换出的页7012030423032是次序7012030423032页面分配情况是否缺页换出的页7012030423032是是7OPT算法置换过程次序7012030423032页面分配情况是否缺页换出的页712030423032是是70是70OPT算法置换过程次序7012030423032页面分配情况是否缺页换出的页712030423032是是70是70701是OPT算法置换过程次序7012030423032页面分配情况是否缺页换出的页71030423032是是70是70701是7011022否是OPT算法置换过程次序7012030423032页面分配情况是否缺页换出的页171030423032是是70是70701是7011022否是22003否是OPT算法置换过程次序7012030423032页面分配情况是否缺页换出的页1071030423032是是70是70701是7011022否是22003否是2233否否是4OPT算法置换过程次序7012030423032页面分配情况302是否缺页换出的页1047103042332是是70是70701是7011022否是22003否是2233否否是4否否OPT算法置换过程次序7012030423032页面分配情况113330000407772222是否缺页是是是是否是否是否否是否否换出的页7104结果：缺页次数共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算法的面页淘汰过程，淘汰的页序和缺页次数？次序7012030423032页面分配情况是否缺页换出的页7012030423032是LRU算法置换过程次序7012030423032页面分配情况是否缺页换出的页7012030423032是是7LRU算法置换过程次序7012030423032页面分配情况是否缺页换出的页712030423032是是70是70LRU算法置换过程次序7012030423032页面分配情况是否缺页换出的页712030423032是是70是70701是LRU算法置换过程次序7012030423032页面分配情况是否缺页换出的页71030423032是是70是70701是7011022否是LRU算法置换过程次序7012030423032页面分配情况是否缺页换出的页171030423032是是70是70701是7011022否是22003否是LRU算法置换过程次序7012030423032页面分配情况是否缺页换出的页1271030423032是是70是70701是7011022否是22003否是LRU算法置换过程40033是次序7012030423032页面分配情况是否缺页换出的页12371030423032是是70是70701是7011022否是22003否是LRU算法置换过程40033是20044是次序7012030423032页面分配情况是否缺页换出的页123071030423032是是70是70701是7011022否是22003否是LRU算法置换过程40033是20044是32244是次序7012030423032页面分配情况230是否缺页换出的页123047103042332是是70是70701是7011022否是22003否是LRU算法置换过程40033是20044是32244是否否次序7012030423032页面分配情况113322200000033777224440是否缺页是是是是否是否是否否是否否换出的页712304结果：缺页次数共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次。次序123524521325页面分配情况334115222222211155533是否缺页是是是是否是否否是是否是换出的页13451LRU算法，内存块为4时，缺页中断次数为7次。次序123524521325页面分配情况5555333112222221111443是否缺页是是是是否是否否是是否否换出的页134〔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,20/71/70/02/71/00/10/22/01/11/20/02/12/21/00/33/20/01/30/41/02/31/42/00/22/40/31/20/01/32/21/00/33/22/01/30/2淘汰的页序：712304缺页次数：9次实现方法2—用栈实现LRU可用一个特殊的栈来保管当前运用的各个页面的页面号。每当进程访问某页面时便将该面页从栈中移出，然后将它压入栈顶。因此，栈顶一直是最新的页号，而栈底那么是最近最久未运用的页号。例如:举例：驻留集大小为3，访问串为7,0,1,2,0,3,0,4,2,3,0,3,2707107210021302032403240324032302230淘汰的页：712304缺页次数：9次栈顶栈底(四)时钟置换算法(CLOCK)CLOCK算法是LRU算法的近似算法。CLOCK算法给每个页面设置一个访问位，标识该页最近有没有被访问过，再将内存中的一切页面经过一个指针链接成一个循环队列。其算法流程图如以下图所示。开场该页命中？P指针不动，将命中页的页面访问位置为1P指针所指页面访问位=0？淘汰该页，换入新页，该页页面访问位置为1P指针下移一个页面置该页页面访问位为0P指针下移一个页面YESNOYESNOCLOCK算法的流程图读取要访问的页号读取要访问的页号CLOCK算法举例：驻留集大小为3，访问串为7,0,1,2,0,3,0,4,2,3,0,3,2淘汰页序:OOO7120341/70/-0/-1/71/01/71/01/10/70/00/11/20/00/11/21/00/11/21/01/30/20/00/31/40/00/31/41/20/31/41/21/30/40/21/01/30/21/01/31/21/00/40/20/31/20/00/11/20/01/30/-0/-0/-初始留意:假设循环链表存在当前访问页(命中)时，直接将其访问位改为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时，问：写出淘汰页序，淘汰次数和缺页率各是多少？要求写出算法过程

次序432143543215页面分配情况432143521432143524321435是否缺页是是是是是是是否否是是否淘汰的页4321431、FIFO页面置换算法缺页次数为9次；缺页中断率f=9/12＝75%.

次序432143543215页面分配情况432155543333144422是否缺页是是是是否否是否否是是否淘汰的页21432、OPT页面置换算法缺页次数为7次，缺页中断率：f=7/12=58.3%。次序432143543215页面分配情况155222233333444441是否缺页是是是是否否是否否否是否淘汰的页14上题OPT页面置换算法，当内存块为4块时，结果又是多少？缺页次数为6次，缺页中断率：f=6/12=50%。课堂练习次序432143543215页面分配情况214354321533214354321444321435432是否缺页是是是是是是是否否是是是淘汰的页43215433、栈构造实现LRU页面置换算法缺页次数为10次，缺页中断率：f=10/12=83.3%。课堂练习对于如下的页面访问序列：7，1，2，0，3，0，4，2，3，0，3，2，7，0。当内存块数量为4时，试问：运用栈构造实现LRU置换算法产生的缺页中断是多少？写出依次淘汰的页号。〔一切内存开场时都是空的，凡第一次用到的页面都产生一次缺页中断。要求写出计算步骤。〕次序71203042303270页面分配情况0304303270220304303271112230440327777112222403是否缺页是是是是是否是否否否否否是否淘汰的页714缺页次数为7次，缺页中断率：f=7/14=50%。课堂练习答案次序432143543215页面分配情况是否缺页是是是是是是是否否是是是淘汰的页43215434、页计数器构造实现LRU页面置换算法240304141302012312041122032114052413041523031425022413012312051122课堂练习对于如下的页面访问序列：7，1，2，0，3，0，4，2，3，0，3，2，7，0。当内存块数量为4时，试问：运用LRU计数器置换算法产生的缺页中断是多少？写出依次淘汰的页号。〔一切内存开场时都是空的，凡第一次用到的页面都产生一次缺页中断。要求写出计算步骤。〕次序71203042303270页面分配情况是否缺页是是是是是否是否否否否否是淘汰的页7143727070121020300410010044214022012243000223444321012305400221717111231221032132333031303200213072333课堂练习答案缺页次数为7次，缺页中断率：f=7/14=50%。五、关于缺页中断率的讨论〔一〕概念。假定一个作业共有n页，系统分配给它的主存块是m块〔m,n均是正整数，且1<=m<=n〕.因此，该作业最多有m页可同时装入主存。假设作业执行中访问页面的总次数为A，其中有F次访问的页面未装入主存，故产生了F次缺页中断。现定义：f=F/A把f称为“缺页中断率〞。〔二〕影响缺页中断率的要素1、分配给作业的主存块数 分配给作业的主存块数越多，那么同时装入主存的页面数就越多，缺页中断的次数就越少。反之，就越高。2、页面的大小 页面的大小取决于主存分块的大小，块越大那么页面越大，页面大那么作业的页数就越少，一页内装入的信息量就越大，缺页中断的次数就越少。反之，就越高。3、编制程序的方法 程序编制的方法不同，对缺页中断的次数有很大影响。例如： 有一个程序要把128×128的数组置初值“0〞，数组中的每一个元素为一个字。现假定页面的尺寸为每页128个字，数组中的每一行元素存放在一页。能供这个程序运用的主存块只需一块，开场时该内存块为空。假设程序编制如下：intA[127,127];for(j=0;j<128;j++) {for(i=0;i<128;i++) {A[i,j]=0;} }由于程序是按列清“0〞的，所以每执行一次A[i,j]=0(清“0〞)就会产生一次缺页中断，总共产生了〔128*128〕次中断。假设重新编制这个程序如下：IntA[127,127]; for(i=0;i<128;i++) { for(j=0;j<128;j++) {A[i,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。页块号LRUFIFOOptimal12020202171815315161141016115812767977777由上可知：〔1〕不同的调度算法，缺页中断次数有差别，其中OPT算法最优，但无法实现，由于谁也不能对程序的执行中要运用的页面作出准确的断言。然而，它可以作为一个衡量各种详细算法的规范。〔2〕当驻留集添加到一定数量后，三种算法的缺页中断次数，差别不大。课堂练习：思索下述页面走向：4，3，2，1，4，3，5，4，3，2，1，5。当内存块分别为3和4时，试问LRU(基于栈构造算法)、FIFO、OPT这三种置换算法的缺页次数各是多少〔假设一切内存块起初为空〕？次序432143543215页面分配情况214354321533214354321444321435432是否缺页是是是是是是是否否是是是淘汰的页4321543当给定的内存块=3时，LRU栈构造算法的置换过程如下：次序432143543215页面分配情况143543215221435432133321435432444432111543是否缺页是是是是是是是否否是是是淘汰的页2154当给定的内存块=4时，LRU栈构造算法的置换过程如下：六、一个页面交换战略的适用方法〔兼顾FIFO和LRU战略〕为页帧在页表项中添加一位运用位，硬件每访存