第五讲存储管理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)是不可实现的策略由于需要预先得知整个访问串的序