《操作系统课程》ppt课件

《《操作系统课程》ppt课件》由会员分享，可在线阅读，更多相关《《操作系统课程》ppt课件（41页珍藏版）》请在金锄头文库上搜索。

1、4.6 虚拟存储器,1 虚拟存储器概述 2 请求分页存储管理方式 3 页面置换算法 4 “抖动”与工作集 5 请求分段存储管理方式,4.6虚拟存储器,1 虚拟存储器概述,1.1 常规存储管理方式的特征和局部性原理,1.常规存储器管理方式的特征 一次性，是指作业必须一次性地全部装入内存后，方能开始运行。这一特征导致了下述两种情况的发生： 当作业很大时，它所要求的内存空间超过了内存总容量，无法将全部作业装入内存，致使该作业无法运行； 当有大量作业要求运行的情况下，由于每一个作业都需要全部装入内存后方能运行，所以每次只能装入少量的作业，导致多道程序度的下降。 驻留性，是指作业被装入内存后，整个作业都

2、一直驻留在内存中，其中任何部分都不会被换出，直至作业运行结束。,2.局部性原理 程序执行时，除了少部分的转移和过程调用指令外，在大多数情况下是顺序执行的。 过程调用将会使程序的执行轨迹，由一部分区域转至另一部分区域。即程序将会在一段时间内，都局限在这些过程的范围内运行。 程序中存在许多循环结构，这些虽然只由少数指令构成，但是它们将多次执行。 程序中还包括许多对数据结构的处理，如对数组进行操作，它们往往都局限于很小的范围内。 局限性又表现在下述两个方面： 时间局限性:如果程序中的某条指令一旦执行，则不久以后该指令可能再次执行；如果某数据被访问过，则不久以后该数据可能再次被访问。 空间局限性:一旦

3、程序访问了某个存储单元，在不久之后，其附近的存储单元也将被访问，即程序在一段时间内所访问的地址，可能集中在一定的范围之内。,1.1 常规存储管理方式的特征和局部性原理,3.虚拟存储器的基本工作情况 应用程序在运行之前，仅须将那些当前要运行的少数页面或段，先装入内存便可运行，其余部分暂留在盘上。 程序在运行时，如果它所要访问的页（段）已调入内存，便可继续执行下去；但如果程序所要访问的页（段）尚未调入内存（称为缺页或缺段），便发出缺页（段）中断请求，此时OS将利用请求调页（段）功能，将它们调入内存，以使进程能继续执行下去。 如果此时内存已满，无法再装入新的页（段），OS还须再利用页（段）的置换功能

4、，将内存中暂时不用的页（段）调至盘上，腾出足够的内存空间后，再将要访问的页（段）调入内存，使程序继续执行下去。,1.1 常规存储管理方式的特征和局部性原理,1.2 虚拟存储器的定义和特征,1.虚拟存储器的定义 具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。其逻辑容量由内存容量和外存容量之和所决定，其运行速度接近于内存速度，而每位的成本却又接近于外存。 虚拟存储技术是一种性能非常优越的存储器管理技术，故被广泛地应用于大、中、小型机器和微型机中。,1.2 虚拟存储器的定义和特征,2.虚拟存储器的特征 多次性 对换性 虚拟性 虚拟性是以多次性和对换性为基础的，或者说，仅当

5、系统允许将作业分多次调入内存，并能将内存中暂时不运行的程序和数据换至盘上时，才有可能实现虚拟存储器；而多次性和对换性，显然又必须建立在离散分配的基础上。,1.分页请求系统 在分页系统的基础上，增加了请求调页功能和页面置换功能，所形成的页式虚拟存储系统。置换时以页面为单位。 （1）硬件支持：请求分页的页表机制、缺页中断机构、地址变换机构。 （2）实现请求分页的软件：实现请求调页的软件和实现页面置换的软件。 2.请求分段系统 在分段系统的基础上，增加了请求调段及分段置换功能后，所形成的段式虚拟存储系统。置换是以段为单位进行的。 为了实现请求分段，系统同样需要必要的硬件和软件支持。 （1）硬件支持：

6、请求分段的段表机制、缺段中断机构、地址变换机构。 （2）实现请求分段的软件：实现请求调段的软件和实现段置换的软件。,1.3 虚拟存储器的实现方法,返回,4.6 虚拟存储器,2 请求分页存储管理方式,2.1 请求分页中的硬件支持 1.请求页表机制 2.缺页中断机构 3.地址变换机构 2.2 请求分页中的内存分配 2.3 页面调入策略,2.1 请求分页中的硬件支持,1.请求页表机制,状态位（存在位）P：仅有一位，故又称位字，用于指示该页是否已调入内存，供程序访问时参考。 访问字段A：记录本页在一段时间内被访问的次数，或记录本页最近已有多长时间未被访问，提供给置换算法（程序）选择换出页面时参考。 修

7、改位M：标识该页在调入内存后是否被修改过。供置换页面时参考。 外存地址：用于指出该页在外存上的地址，通常是物理块号，供调入该页时参考。,2.1 请求分页中的硬件支持,2.缺页中断机构 缺页中断作为中断，同样需要经历诸如保护CPU环境、分析中断原因、转入缺页中断处理程序进行处理，以及在中断处理完成后再恢复CPU环境等几个步骤。 缺页中断又是一种特殊的中断，它与一般的中断相比，有着明显的区别： 在指令执行期间，产生和处理中断信号。 一条指令在执行期间，可能产生多次缺页中断。,2.1 请求分页中的硬件支持,3.地址变换机构,1.最小物理块数的确定 随着为每个进程所分配的物理块的减少，将使进程在执行中

8、的缺页率上升，从而会降低进程的执行速度。 最小物理块数是指，能保证进程正常运行所需的最小物理块数，当系统为进程分配的物理块数少于此值时，进程将无法运行。 进程应获得的最少物理块数，与计算机的硬件结构有关，取决于指令的格式、功能和寻址方式。 对于某些简单的机器，若是单地址指令，且采用直接寻址方式，则所需的最少物理块数为2。其中，一块是用于存放指令的页面，另一块则是用于存放数据的页面。 如果该机器允许间接寻址时，则至少要求有三个物理块。 对于某些功能较强的机器，其指令长度可能是两个或多于两个字节，因而其指令本身有可能跨两个页面，且源地址和目标地址所涉及的区域，也都可能跨两个页面。,2.2 请求分页

9、中的内存分配,2.内存分配策略 （1）固定分配局部置换 固定分配是指，为每个进程分配一组固定数目的物理块，在进程运行期间不再改变。 局部置换是指，如果进程在运行中发现缺页，则只能从分配给该进程的n个页面中，选出一页换出，然后再调入一页。 （2）可变分配全局置换 可变分配是指，先为每个进程分配一定数目的物理块，在进程运行期间，可根据情况做适当地改变。 全局置换是指，如果进程在运行中发现缺页，则将OS所保留的空闲物理块或者以所有进程的全部物理块为标的，选择一块换出，然后将所缺之页调入。 （3）可变分配局部置换 为每个进程分配一定数目的物理块，但当某进程发现缺页时，只允许从该进程在内存的页面中，选择

10、一页换出，如果进程在运行中，频繁地发生缺页中断，则系统须再为该进程分配若干附加的物理块，直至该进程的缺页率减少到适当程度为止。,2.2 请求分页中的内存分配,3.物理块分配算法 （1）平均分配算法：将系统中所有可供分配的物理块，平均分配给各个进程。 （2）按比例分配算法：根据进程的大小按比例分配物理块的算法。 系统中各进程页面数的总和为： 每个进程所能分到的物理块数为bi： （3）考虑优先权的分配算法：把内存中可供分配的所有物理块分成两部分：一部分按比例地分配给各进程；另一部分则根据各进程的优先权进行分配，为高优先进程适当地增加其相应份额。,2.2 请求分页中的内存分配,1.何时调入页面 预调

11、页策略：那些预计在不久之后便会被访问的页面，预先调入内存。 请求调页策略：当进程在运行中需要访问某部分程序和数据时，若发现其所在的页面不在内存，便立即提出请求，由OS将其所需页面调入内存。 2.从何处调入页面 在请求分页系统中的外存分为两部分：用于存放文件的文件区和用于存放对换页面的对换区。 系统拥有足够的对换区空间。 系统缺少足够的对换区空间。 UNIX方式。,2.3 页面调入策略,3.页面调入过程 每当程序所要访问的页面未在内存时（存在位为“0”），便向CPU发出一缺页中断，中断处理程序首先保留CPU环境，分析中断原因后，转入缺页中断处理程序。该程序通过查找页表，得到该页在外存的物理块后，

12、如果此时内存能容纳新页，则启动磁盘I/O，将所缺之页调入内存，然后修改页表。如果内存已满，则须先按照某种置换算法，从内存中选出一页准备换出；如果该页未被修改过（修改位为“O”），可不必将该页写回磁盘；但如果此页已被修改（修改位为“1”），则必须将它写回磁盘，然后再把所缺的页调入内存，并修改页表中的相应表项，置其存在位为“1”，并将此页表项写入快表中。在缺页调入内存后，利用修改后的页表，去形成所要访问数据的物理地址，再去访问内存数据。整个页面的调入过程对用户是透明的。,2.3 页面调入策略,返回,4.6 虚拟存储器,3 页面置换算法,3.1 最佳置换算法和先进先出置换算法,1.最佳置换算法 由B

13、elady于1966年提出的一种理论上的算法。 其所选择的被淘汰页面，将是以后永不使用的， 或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。 假定系统为某进程分配了三个物理块， 并考虑有以下的页面号引用串： 7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1 进程运行时， 先将7，0，1三个页面装入内存。 以后， 当进程要访问页面2时， 将会产生缺页中断。此时OS根据最佳置换算法， 将选择页面7予以淘汰。,3.1 最佳置换算法和先进先出置换算法,2.先进先出页面置换算法 置换时，选择在内存中驻留时间最长的页并予以淘汰。,3.

14、2 最近最久未使用和最少使用置换算法,1.LRU置换算法的描述 选择最后一次访问时间距离当前时间最长的一页并淘汰之。即淘汰没有使用的时间最长的页。实现代价很高（时间戳或硬件方法）。,3.2 最近最久未使用和最少使用置换算法,2. LRU置换算法的硬件支持 寄存器 为了记录某进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器，可表示为 : R=Rn-1Rn-2Rn-3 R2R1R0 。,3.2 最近最久未使用和最少使用置换算法,2. LRU置换算法的硬件支持 （2）栈,3.2 最近最久未使用和最少使用置换算法,3.最少使用LFU置换算法 选择在最近时期使用最少的页面作为淘汰页。

15、 LFU置换算法的页面访问图，与LRU置换算法的访问图完全相同；或者说，利用这样一套硬件既可实现LRU算法，又可实现LFU算法。 这种算法并不能真正反映出页面的使用情况，因为在每一时间间隔内，只是用寄存器的一位来记录页的使用情况，因此，在该时间间隔内，对某页访问一次和访问1000次是完全等效的。,4.3.3 Clock置换算法,1.简单的Clock置换算法,4.3.3 Clock置换算法,2.改进型Clock置换算法 由访问位A和修改位M可以组合成下面四种类型的页面： 1类(A=0, M=0): 该页最近既未被访问，又未被修改，是最佳淘汰页。 2类(A=0, M=1)：该页最近未被访问，但已被

16、修改，并不是很好的淘汰页。 3类(A=1, M=0)：最近已被访问，但未被修改，该页有可能再被访问。 4类(A=1, M=1): 最近已被访问且被修改， 该页可能再被访问。 其执行过程可分成以下三步： (1)从指针所指示的当前位置开始，扫描循环队列，寻找A=0且M=0的第一类页面，将所遇到的第一个页面作为所选中的淘汰页。在第一次扫描期间不改变访问位A。 (2)如果第一步失败，则开始第二轮扫描，寻找A=0且M=1的第二类页面，将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间，将所有扫描过的页面的访问位都置0。 (3)如果第二步也失败，则将指针返回到开始的位置，并将所有的访问位复0。然后重复第一步。,4.3.4 页面缓冲算法PBA,1.影响页面换进换出效率的若干因素 页面置换算法：影响页面换进换出效率最重要的因素，直接影响进程在运行过程中的缺页率，影响页面换进换出的开销。 写回磁盘的频率：如果是采取每个页面换出时，就将它写回磁盘的策略，这