计算机操作系统(汤小丹)第5章

1第五章虚拟存储器第五章虚拟存储器5.1虚拟存储器概述5.2请求分页存储管理方式5.3页面置换算法5.4“抖动”与工作集5.5请求分段存储管理方式习题2第五章虚拟存储器 5.1虚拟存储器概述第四章所介绍的各种存储器管理方式有一个共同的特点，即它们都要求将一个作业全部装入内存后方能运行。于是，出现了下面这样两种情况：(1)有的作业很大，其所要求的内存空间超过了内存总容量，作业不能全部被装入内存，致使该作业无法运行；(2)有大量作业要求运行，但由于内存容量不足以容纳所有这些作业，只能将少数作业装入内存让它们先运行，而将其它大量的作业留在外存上等待。3第五章虚拟存储器5.1.1常规存储管理方式的特征和局部性原理1.常规存储器管理方式的特征我们把前一章中所介绍的各种存储器管理方式统称为传统存储器管理方式，它们全都具有如下两个共同的特征：(1)一次性(2)驻留性4第五章虚拟存储器2.局部性原理程序运行时存在的局部性现象，很早就已被人发现，但直到1968年，P.Denning才真正指出：程序在执行时将呈现出局部性规律，即在一较短的时间内，程序的执行仅局限于某个部分，相应地，它所访问的存储空间也局限于某个区域。5第五章虚拟存储器局限性又表现在下述两个方面：(1)时间局限性。(2)空间局限性。6第五章虚拟存储器3.虚拟存储器的基本工作情况基于局部性原理可知，应用程序在运行之前没有必要将之全部装入内存，而仅须将那些当前要运行的少数页面或段先装入内存便可运行，其余部分暂留在盘上。7第五章虚拟存储器5.1.2虚拟存储器的定义和特征1.虚拟存储器的定义当用户看到自己的程序能在系统中正常运行时，他会认为，该系统所具有的内存容量一定比自己的程序大，或者说，用户所感觉到的内存容量会比实际内存容量大得多。但用户所看到的大容量只是一种错觉，是虚的，故人们把这样的存储器称为虚拟存储器。8第五章虚拟存储器2.虚拟存储器的特征与传统的存储器管理方式比较，虚拟存储器具有以下三个重要特征：(1)多次性。(2)对换性。(3)虚拟性。9第五章虚拟存储器5.1.3虚拟存储器的实现方法1.分页请求系统1)硬件支持主要的硬件支持有：(1)请求分页的页表机制。(2)缺页中断机构。(3)地址变换机构。2)实现请求分页的软件10第五章虚拟存储器2.请求分段系统1)硬件支持主要的硬件支持有：(1)请求分段的段表机制。(2)缺页中断机构。(3)地址变换机构。2)软件支持11第五章虚拟存储器 5.2请求分页存储管理方式5.2.1请求分页中的硬件支持为了实现请求分页，系统必须提供一定的硬件支持。计算机系统除了要求一定容量的内存和外存外，还需要有请求页表机制、缺页中断机构以及地址变换机构。12第五章虚拟存储器1.请求页表机制在请求分页系统中需要的主要数据结构是请求页表，其基本作用仍然是将用户地址空间中的逻辑地址映射为内存空间中的物理地址。为了满足页面换进换出的需要，在请求页表中又增加了四个字段。这样，在请求分页系统中的每个页表应含以下诸项：页号物理块号状态位P访问字段A修改位M外存地址13第五章虚拟存储器2.缺页中断机构(1)在指令执行期间产生和处理中断信号。(2)一条指令在执行期间可能产生多次缺页中断。14第五章虚拟存储器图5-1涉及6次缺页中断的指令15第五章虚拟存储器3.地址变换机构请求分页系统中的地址变换机构是在分页系统地址变换机构的基础上，为实现虚拟存储器，再增加了某些功能所形成的，如产生和处理缺页中断，以及从内存中换出一页的功能等等。图5-2示出了请求分页系统中的地址变换过程。16第五章虚拟存储器图5-2请求分页中的地址变换过程17第五章虚拟存储器5.2.2请求分页中的内存分配1.最小物理块数的确定一个显而易见的事实是，随着为每个进程所分配的物理块的减少，将使进程在执行中的缺页率上升，从而会降低进程的执行速度。为使进程能有效地工作，应为它分配一定数目的物理块，但这并不是最小物理块数的概念。18第五章虚拟存储器2.内存分配策略在请求分页系统中，可采取两种内存分配策略，即固定和可变分配策略。在进行置换时，也可采取两种策略，即全局置换和局部置换。于是可组合出以下三种适用的策略。1)固定分配局部置换(FixedAllocation，LocalReplacement)2)可变分配全局置换(VariableAllocation，GlobalReplacement)3)可变分配局部置换(VariableAllocation，LocalReplacement)19第五章虚拟存储器3.物理块分配算法在采用固定分配策略时，如何将系统中可供分配的所有物理块分配给各个进程，可采用下述几种算法：(1)平均分配算法，即将系统中所有可供分配的物理块平均分配给各个进程。(2)按比例分配算法，即根据进程的大小按比例分配物理块。如果系统中共有n个进程，每个进程的页面数为Si，则系统中各进程页面数的总和为：n1iiSS20第五章虚拟存储器又假定系统中可用的物理块总数为m，则每个进程所能分到的物理块数为bi可由下式计算：这里，bi应该取整，它必须大于最小物理块数。mSSbii21第五章虚拟存储器(3)考虑优先权的分配算法。在实际应用中，为了照顾到重要的、紧迫的作业能尽快地完成，应为它分配较多的内存空间。通常采取的方法是把内存中可供分配的所有物理块分成两部分：一部分按比例地分配给各进程；另一部分则根据各进程的优先权进行分配，为高优先进程适当地增加其相应份额。在有的系统中，如重要的实时控制系统，则可能是完全按优先权为各进程分配其物理块的。22第五章虚拟存储器5.2.3页面调入策略为使进程能够正常运行，必须事先将要执行的那部分程序和数据所在的页面调入内存。现在的问题是：(1)系统应在何时调入所需页面；(2)系统应从何处调入这些页面；(3)是如何进行调入的。23第五章虚拟存储器1.何时调入页面(1)预调页策略。(2)请求调页策略。24第五章虚拟存储器2.从何处调入页面(1)系统拥有足够的对换区空间，这时可以全部从对换区调入所需页面，以提高调页速度。(2)系统缺少足够的对换区空间，这时凡是不会被修改的文件，都直接从文件区调入；而当换出这些页面时，由于它们未被修改，则不必再将它们重写到磁盘(换出)，以后再调入时，仍从文件区直接调入。但对于那些可能被修改的部分，在将它们换出时便须调到对换区，以后需要时再从对换区调入。(3) UNIX方式。25第五章虚拟存储器3.页面调入过程每当程序所要访问的页面未在内存时(存在位为“0”)，便向CPU发出一缺页中断，中断处理程序首先保留CPU环境，分析中断原因后转入缺页中断处理程序。26第五章虚拟存储器4.缺页率假设一个进程的逻辑空间为n页，系统为其分配的内存物理块数为m(m≤n)。如果在进程的运行过程中，访问页面成功(即所访问页面在内存中)的次数为S，访问页面失败(即所访问页面不在内存中，需要从外存调入)的次数为F，则该进程总的页面访问次数为A = S + F，那么该进程在其运行过程中的缺页率即为AFf27第五章虚拟存储器事实上，在缺页中断处理时，当由于空间不足，需要置换部分页面到外存时，选择被置换页面还需要考虑到置换的代价，如页面是否被修改过。没有修改过的页面可以直接放弃，而修改过的页面则必须进行保存，所以处理这两种情况时的时间也是不同的。假设被置换的页面被修改的概率是β，其缺页中断处理时间为ta，被置换页面没有被修改的缺页中断时间为tb，那么，缺页中断处理时间的计算公式为t=β×ta+(1—β)×tb28第五章虚拟存储器 5.3页面置换算法在进程运行过程中，若其所要访问的页面不在内存，而需把它们调入内存，但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据送到磁盘的对换区中。但应将哪个页面调出，须根据一定的算法来确定。通常，把选择换出页面的算法称为页面置换算法(Page-ReplacementAlgorithms)。置换算法的好坏将直接影响到系统的性能。29第五章虚拟存储器5.3.1最佳置换算法和先进先出置换算法1.最佳(Optimal)置换算法最佳置换算法是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面将是以后永不使用的，或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法通常可保证获得最低的缺页率。但由于人们目前还无法预知，一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，但可以利用该算法去评价其它算法。30第五章虚拟存储器图5-3利用最佳页面置换算法时的置换图31第五章虚拟存储器2.先进先出(FIFO)页面置换算法FIFO算法是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单，只需把一个进程已调入内存的页面按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。但该算法与进程实际运行的规律不相适应，因为在进程中，有些页面经常被访问，比如，含有全局变量、常用函数、例程等的页面，FIFO算法并不能保证这些页面不被淘汰。32第五章虚拟存储器图5-4利用FIFO置换算法时的置换图33第五章虚拟存储器5.3.2最近最久未使用和最少使用置换算法1. LRU(LeastRecentlyUsed)置换算法的描述FIFO置换算法的性能之所以较差，是因为它所依据的条件是各个页面调入内存的时间，而页面调入的先后并不能反映页面的使用情况。最近最久未使用(LRU)的页面置换算法是根据页面调入内存后的使用情况做出决策的。34第五章虚拟存储器图5-5LRU页面置换算法35第五章虚拟存储器2.LRU置换算法的硬件支持1)寄存器为了记录某进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器，可表示为R = Rn-1Rn-2Rn-3…R2R1R036第五章虚拟存储器当进程访问某物理块时，要将相应寄存器的Rn-1位置成1。此时，定时信号将每隔一定时间(例如100ms)将寄存器右移一位。如果我们把n位寄存器的数看作是一个整数，那么，具有最小数值的寄存器所对应的页面，就是最近最久未使用的页面。37第五章虚拟存储器图5-6某进程具有8个页面时的LRU访问情况R实页R7R6R5R4R3R2R1R0101010010210101100300000100401101011511010110600101011700000111801101101R实页38第五章虚拟存储器2)栈可利用一个特殊的栈保存当前使用的各个页面的页面号。每当进程访问某页面时，便将该页面的页面号从栈中移出，将它压入栈顶。因此，栈顶始终是最新被访问页面的编号，而栈底则是最近最久未使用页面的页面号。假定现有一进程，它分有五个物理块，所访问的页面的页面号序列为：4，7，0，7，1，0，1，2，1，2，639第五章虚拟存储器图5-7用栈保存当前使用页面时栈的变化情况40第五章虚拟存储器3.最少使用(LeastFrequentlyUsed，LFU)置换算法在采用LFU算法时，应为在内存中的每个页面设置一个移位寄存器，用来记录该页面被访问的频率。该置换算法选择在最近时期使用最少的页面作为淘汰页。41第五章虚拟存储器5.3.3Clock置换算法1.简单的Clock置换算法当利用简单Clock算法时，只需为每页设置一位访问位，再将内存中的所有页面都通过链接指针链接成一个循环队列。42第五章虚拟存储器图5-8简单Clock置换算法的流程和示例43第五章虚拟存储器2.改进型Clock置换算法在将一个页面换出时，如果该页已被修改过，便须将该页重新写回到磁盘上；但如果该页未被修改过，则不必将它拷回磁盘。换而言之，对于修改过的页面，在换出时所付出的开销比未修改过的页面大，或者说，置换代价大。在改进型Clock算法中，除须考虑页面的使用情况外，还须再增加一个因素——置换代价。44第五章虚拟存储器5.3.4页面缓冲算法(PageBufferingAlgorithm，PB