计算机操作系统-第四版-汤小丹-梁红兵-哲凤屏_第5章(2016-2017-1)

第五章虚拟存储器第五章虚拟存储器5.1虚拟存储器概述5.2请求分页存储管理方式5.3页面置换算法5.4“抖动”与工作集5.5请求分段存储管理方式第五章虚拟存储器5.1虚拟存储器概述前面所介绍的各种存储器管理方式有一个共同的特点，即它们都要求将一个作业全部装入内存后方能运行，于是，出现了下面这样两种情况：(1)有的作业很大，其所要求的内存空间超过了内存总容量，作业不能全部被装入内存，致使该作业无法运行。(2)有大量作业要求运行，但由于内存容量不足以容纳所有这些作业，只能将少数作业装入内存让它们先运行，而将其它大量的作业留在外存上等待。第五章虚拟存储器1.常规存储器管理方式的特征(1)一次性。常规存储管理方式都要求将作业全部装入内存后方能运行。然而，许多作业在每次运行时，并非其全部程序和数据都要用到。5.1.1常规存储管理方式的特征和局部性原理(2)驻留性。作业装入内存后，便一直驻留在内存中，直至作业运行结束。然而，有的程序模块在运行过一次后就不再需要(运行)了。问题：一次性及驻留性在程序运行时是否是必需的?第五章虚拟存储器2．局部性原理Denning.P在1968指出：程序在执行时将呈现出局部性规律，即在一较短的时间内，程序的执行仅局限于某个部分；相应地，它所访问的存储空间也局限于某个区域。他提出了下述几个论点：(1)程序执行时，除了少部分的转移和过程调用指令外，在大多数情况下仍是顺序执行的;(2)在过程调用中，程序将会在一段时间内都局限在这些过程的范围内运行；(3)程序中存在许多循环结构；(4)程序中许多对数据结构的处理，往往都局限于很小的范围内。5.1.1常规存储管理方式的特征和局部性原理第五章虚拟存储器3.虚拟存储器的基本工作情况基于局部性原理，应用程序在运行之前，仅须将那些当前要运行的少数页面或段先装入内存便可运行，其余部分暂留在盘上。程序在运行时，如果程序所要访问的页(段)尚未调入内存，此时程序应利用OS所提供的请求调页(段)功能，将它们调入内存，以使进程能继续执行下去。如果此时内存已满，则须再利用页(段)的置换功能，将内存中暂时不用的页(段)调至盘上，再将要访问的页(段)调入内存，使程序继续执行下去。5.1.1常规存储管理方式的特征和局部性原理第五章虚拟存储器5.1.2虚拟存储器的定义和特征具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储系统。其逻辑容量是内存容量和外存容量之和，其运行速度接近于内存速度。1.虚拟存储器的定义2.虚拟存储器的特征1)多次性.一个作业被分成多次调入内存运行2)对换性.作业的运行过程中进行换进、换出3)虚拟性.能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量。第五章虚拟存储器1.分页请求系统在分页系统的基础上增加了请求调页功能和页面置换功能。它允许只装入少数页面的程序(及数据)，便启动运行。以后，再通过调页功能及页面置换功能，陆续地把即将要运行的页面调入内存，同时把暂不运行的页面换出到外存上。置换时以页面为单位。为了能实现请求调页和置换功能，系统必须提供必要的硬件支持和相应的软件。5.1.3虚拟存储器的实现方法虚拟存储器建立在离散分配存储管理方式第五章虚拟存储器2.请求分段系统在分段系统的基础上，增加了请求调段及分段置换功能后所形成的段式虚拟存储系统。它允许只装入少数段(而非所有的段)的用户程序和数据，即可启动运行。以后再通过调段功能和段的置换功能将暂不运行的段调出，同时调入即将运行的段。置换是以段为单位进行的。5.1.3虚拟存储器的实现方法第五章虚拟存储器5.2请求分页存储管理方式5.2.1请求分页中的硬件支持1.请求页表机制在请求分页系统中所需要的主要数据结构是页表。其基本作用仍然是将逻辑地址变换为物理地址。页号物理块号状态位P访问字段A修改位M外存地址请求分页系统建立在基本分页基础上，增加了请求调页功能和页面置换功能。请求分页系统中的页表第五章虚拟存储器在请求分页系统中，每当所要访问的页面不在内存时，便产生一缺页中断，请求OS将所缺之页调入内存。缺页中断是一种特殊的中断，主要表现在下面两个方面：(1)在指令执行期间产生和处理中断信号。(2)一条指令在执行期间可能产生多次缺页中断。基于这些特征，系统中的硬件机构应能保存多次中断时的状态，并保证最后能返回到中断前产生缺页中断的指令处继续执行。5.2.1请求分页中的硬件支持2.缺页中断机构第五章虚拟存储器图5-2请求分页中的地址变换过程缺页中断处理保留CPU现场从外存中找到缺页内存满否？选择一页换出该页被修改否？将该页写回外存OS命令CPU从外存读缺页启动I/O硬件将一页从外存换入内存修改页表否是是否页表项在快表中？CPU检索快表访问页表否页在内存？修改访问位和修改位形成物理地址地址变换结束否页号＞页表长度?开始程序请求访问一页产生缺页中断请求调页修改快表是越界中断是是5.2.1请求分页中的硬件支持3．地址变换机构11月11日第五章虚拟存储器1．最小物理块数的确定最小物理块数是指能保证进程正常运行所需的最小物理块数。当系统为进程分配的物理块数少于此值时，进程将无法运行。进程应获得的最少物理块数与计算机的硬件结构有关，取决于指令的格式、功能和寻址方式。5.2.2请求分页中的内存分配第五章虚拟存储器2.内存分配策略1)固定分配局部置换(FixedAllocation，LocalReplacement)基于进程的类型，或根据程序员、程序管理员的建议，为每个进程分配一定数目的物理块，在整个运行期间都不再改变。如果进程在运行中发现缺页，则从该进程在内存的n个页面中选出一个页换出，然后再调入一页。5.2.2请求分页中的内存分配第五章虚拟存储器2)可变分配全局置换(VariableAllocation，GlobalReplacement)2.内存分配策略先为系统中的每个进程分配一定数目的物理块，而OS自身也保持一个空闲物理块队列。当某进程发现缺页时，由系统从空闲物理块队列中取出一个物理块分配给该进程，并将欲调入的(缺)页装入其中。这样，凡产生缺页(中断)的进程，都将获得新的物理块。当空闲物理块用完时，OS才能从内存中选择一页调出，被选择调出的页可能试系统中的任何一页。5.2.2请求分页中的内存分配第五章虚拟存储器3)可变分配局部置换(VariableAllocation，LocalReplacement)5.2.2请求分页中的内存分配先为每个进程分配一定数目的物理块，但当某进程发现缺页时，只允许从该进程在内存的页面中选出一页换出，这样就不会影响其它进程的运行。如果进程在运行中频繁地发生缺页中断，则系统须再为该进程分配若干附加的物理块，直至该进程的缺页率减少到适当程度为止；反之，若一个进程在运行过程中的缺页率特别低，则此时可适当减少分配给该进程的物理块数。2.内存分配策略第五章虚拟存储器3.物理块分配算法1)平均分配算法将系统中所有可供分配的物理块平均分配给各个进程。5.2.2请求分页中的内存分配2)按比例分配算法根据进程的大小按比例分配物理块的算法。系统中共有n个进程，每个进程的页面数为Si,可用的物理块总数为m，则每个进程所能分到的物理块数为bi。niiSS1mSSbii第五章虚拟存储器3)考虑优先权的分配算法在实际应用中，为了照顾到重要的、紧迫的作业能尽快地完成，应为它分配较多的内存空间。通常采取的方法是把内存中可供分配的所有物理块分成两部分：一部分按比例地分配给各进程；另一部分则根据各进程的优先权，适当地增加其相应份额后，分配给各进程。5.2.2请求分页中的内存分配3.物理块分配算法第五章虚拟存储器5.2.3页面调入策略1)预调页策略采用一种以预测为基础的预调页策略，将那些预计在不久之后便会被访问的页面预先调入内存。这种策略主要用于进程的首次调入时，由程序员指出应该先调入哪些页。2)请求调页策略当进程在运行中需要访问某部分程序和数据时，若发现其所在的页面不在内存，便立即提出请求，由OS将其所需页面调入内存。每次仅调入一页，目前虚拟存储器大多采用此策略。1.何时调入页面第五章虚拟存储器2．从何处调入页面请求分页系统中的外存分为文件区和对换区。当发生缺页请求时，有三种情况将缺页调入内存：(1)系统拥有足够的对换区空间，这时可以全部从对换区调入所需页面，以提高调页速度。(2)系统缺少足够的对换区空间，凡不会被修改的文件都直接从文件区调入。对于那些可能被修改的部分，将它们换出时须调到对换区。(3)UNIX方式。与进程有关的文件都放在文件区，故凡是未运行过的页面，都应从文件区调入；对于曾经运行过但又被换出的页面，放在对换区。第五章虚拟存储器3.页面调入过程每当程序所要访问的页面未在内存时，便向CPU发出一缺页中断，中断处理程序首先保留CPU环境，分析中断原因后转入缺页中断处理程序。在缺页调入内存后，利用修改后的页表，形成所要访问数据的物理地址，再去访问内存数据。整个页面的调入过程对用户是透明的。5.2.3页面调入策略第五章虚拟存储器5.2.3页面调入策略4.缺页率假设一个进程的逻辑空间为n页，系统为其分配的内存物理块数为m(m≤n)。如果在进程的运行过程中，访问页面成功的次数为S，访问页面失败的次数为F。则该进程在运行过程中的缺页率为：f=F/(S+F)第五章虚拟存储器5.3页面置换算法5.3.1最佳置换算法和先进先出置换算法1.最佳(Optimal)置换算法由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面，将是以后永不使用的，或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。页面置换算法是指选择换出页面的算法。不适当的算法可能会导致进程发生“抖动”。第五章虚拟存储器例：假定系统为某进程分配了三个物理块，考虑有以下的页面号引用串：7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1进程运行时，先将7，0，1三个页面装入内存。引用率70770170122010320304243230321201201770101页框(物理块）243图5-3利用最佳页面置换算法时的置换图1.最佳(Optimal)置换算法第五章虚拟存储器2.先进先出(FIFO)页面置换算法该算法淘汰最先进入内存的页面。5.3.1最佳置换算法和先进先出置换算法引用率70770170122010323104430230321013201770201页框230420423023012712701例：页面号引用串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1.进程运行时，先将7，0，1三个页面装入内存。FIFO算法时进行了12次页面置换第五章虚拟存储器1.LRU(LeastRecentlyUsed)置换算法选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t，当须淘汰一个页面时，选择t值最大的页面.5.3.2最近最久未使用和最少使用置换算法引用率70770170122010320304403230321132201770101页框402432032102LRU页面置换算法第五章虚拟存储器2．LRU置换算法的硬件支持1)寄存器移位寄存器，记录某进程在内存中各页的使用情况。R = Rn-1Rn-2Rn-3…R2R1R05.3.2最近最久未使用和最少使用置换算法R实页R7R6R5R4R3R2R1R0101010010210101100300000100401101011511010110600101011700000111801101101图5-6某进程具有8个页面时的LRU访问情况第五章虚拟存储器2)栈可利用一个特殊的栈来保存当前使用的各个页面的页面号。每当进程访问某页面时，便将该页面的页面号从栈中移出，将它压入栈顶。假定现有一进程所访问的页面号序列为：4，7，0，7，1，0，1，2，1，2，6.随着进程的访问，栈中页面号的变化情况如图所示。2．LRU置换算法