计算机操作系统第四版第5章虚拟存储器

1、第五章 虚拟存储器 第五章第五章 虚拟存储器虚拟存储器 5.1虚拟存储器的基本概念虚拟存储器的基本概念5.2请求分页存储管理方式请求分页存储管理方式5.3页面置换算法页面置换算法5.4 “抖动抖动”与工作集与工作集5.5请求分段存储管理方式请求分段存储管理方式第五章 虚拟存储器 常规存储器管理方式的特征：常规存储器管理方式的特征： 一次性作业在运行前需一次性地全部装入内存。 驻留性作业装入内存后，便一直驻留在内存中，直至作业运行结束。 上述特征，使许多在程序运行中不用或暂不用的程序(数据)占据了大量的内存空间，使得一些需要运行的作业无法装入运行。5.1 虚拟存储器概述虚拟存储器概述第五章 虚拟

2、存储器 1968年，Denning. P提出局部性原理局部性原理：程序在执行时呈现出局部性规律，即在一较短时间内，程序的执行仅限于某个部分，相应地，它所访问的存储空间也局限于某个区域。(论点见P154) 局部性又表现为时间局部性和空间局部性。v时间局部性是指如果程序中的某条指令一旦执行，则不久以后该指令可能再次执行。如果某数据被访问，则不久以后该数据可能再次被访问。(循环)v空间局部性是指一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也将被访问。(程序的顺序执行) 5.1 虚拟存储器概述虚拟存储器概述局部性原理局部性原理第五章 虚拟存储器 基于程序局部性原理，一个作业在运行之前，没有

3、必要全部装入内存，而仅将那些当前要运行的那部分页面或段先装入内存，就可以启动运行。这样就可以使一个较大的程序在较小的内存空间中运行，同时还可以装入更多的程序并发执行。从用户角度来看，该系统所具有的内存容量比实际内存容量大得多。通常把这样的存储器称为虚拟存储器。 所谓虚拟存储器是指仅把作业的一部分装入内存便可运行作业的存储管理系统。它具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充。其逻辑容量取决于内存与外存的容量之和。其运行速度接近于内存，而其每位的成本却接近于外存。5.1 虚拟存储器概述虚拟存储器概述第五章 虚拟存储器 v 多次性指一个作业被分成多次调入内存运行。是虚拟存储器最重要的

4、特征。v 对换性指允许在作业的运行过程中进行换进、换出。v 虚拟性指能够从逻辑上扩充内存容量，使用户看到的容量远大于实际内存容量。5.1 虚拟存储器概述虚拟存储器概述虚拟存储器的特征虚拟存储器的特征第五章 虚拟存储器 1、分页请求系统（请求分页存储管理方式）在基本分页系统的基础上，增加请求调页功能和页面置换功能所形成的页式虚拟存储系统。 当一个用户程序要调入内存时，不是将该程序全部装入内存，而是只装入部分页到内存，就可启动程序运行。在运行的过程中，如果发现要运行的程序或要访问数据不在内存，则向系统发出缺页中断请求缺页中断请求，系统在处理这个中断时，将外存中相应的页调入内存，该程序继续运行。当一

5、些页调入内存时，若内存没有空闲空间，则利用页面置换功能页面置换功能，将内存中暂时不用的页面换出到外存上，再将这些要访问的页调入内存，该程序继续运行。 硬件支持：硬件支持：请求页表机制、缺页中断机构、地址变换机构 软件支持：软件支持：实现请求调页功能和页面置换功能的软件2、请求分段系统（请求分段存储管理方式）类似于请求分页，以段为单位进行请求和置换。5.1 虚拟存储器概述虚拟存储器概述虚拟存储器的实现方法虚拟存储器的实现方法第五章 虚拟存储器 页表机制页表中除了有页号、物理块号两项外，还需要状态位、访问字段、修改位、外存地址等信息。状态位指示该页是否已调入内存。访问字段记录本页在一段时间内被访问

6、的次数或本页最近已有多长时间未被访问。供选择换出页面时参考。修改位表示该页调入内存后是否被修改过。外存地址指示该页在外存的地址。5.2请求分页存储管理方式请求分页存储管理方式(页式虚拟存储管理页式虚拟存储管理)5.2.1 硬件支持硬件支持 请求页表机制第五章 虚拟存储器 缺页中断机构每当所要访问的页面不在内存时，便要产生缺页中断，请求操作系统将所缺的页面调入内存。5.2.1 硬件支持硬件支持缺页中断机构缺页中断与一般中断的区别，在于在指令的执行期间产生和处理中断信号，而且一条指令执行期间，可能产生多次缺页中断（如: copy A to B ）。缺页中断的处理过程是，保留CPU现场，分析中断原因

7、，转入缺页中断处理程序进行处理；从外存中找到缺的页面；若内存已满，则选择一页换出；从外存读入缺页，写入内存，修改页表；中断处理完成，恢复CPU现场。 第五章 虚拟存储器 地址变换机构(见P158图5-2)（在基本分页系统具有快表的地址变换机构的基础上增加缺页处理功能）在进行地址变换时，首先检索快表。若找到，则直接用快表中给出的物理块号与逻辑地址中的页内地址形成物理地址。若未找到，则应去内存中查找页表(慢表)，将有两种可能。 (1)若该页已调入内存，此时则应将该页的页表项写人快表(快表满时，调出一个页表项，然后写入)，用页表中给出的物理块号与逻辑地址中的页内地址形成物理地址； (2)若该页未调入

8、内存，则产生缺页中断，请求操作系统从外存中调入。 5.2.1 硬件支持硬件支持地址变换机构第五章 虚拟存储器 在为进程分配内存时，涉及到三个问题：最小物理块数的确定(2)内存分配策略(3)物理块的分配算法5.2.2 请求分页中的内存分配请求分页中的内存分配第五章 虚拟存储器 最小物理块数能保证进程正常运行所需的最少物理块数。 当系统为进程分配的物理块数少于此值时，进程将无法运行。 它与计算机硬件结构有关，取决于指令的格式、功能和寻址方式。 5.2.2 请求分页中的内存分配请求分页中的内存分配最小物理块数的确定最小物理块数的确定第五章 虚拟存储器 分配策略可以是固定分配和可变分配。分配策略可以是

9、固定分配和可变分配。 固定分配固定分配:为每个进程分配一组固定数目的物理块，在进程运行期间不再改变。 可变分配可变分配：先为每个进程分配一定数目的物理块，在进程运行期间可根据情况根据情况做适当的增加或减少。 置换策略可以是全局置换和局部置换。置换策略可以是全局置换和局部置换。 局部置换局部置换:进程在运行过程中发生缺页时，只能从当前缺页进程当前缺页进程在内存的页面在内存的页面中选出一页进行淘汰，然后再调入所缺页面。 全局置换全局置换：进程在运行过程中发生缺页时，由OS从系统管理的空闲物理块队列中取出一块分配给该进程。当空闲物理块队列中的物理块用完时，OS从系统中任一进程中选出一页系统中任一进程

10、中选出一页进行淘汰，然后再调入所缺页面。（以所有进程的全部物理块为选择目标）（以所有进程的全部物理块为选择目标）5.2.2 请求分页中的内存分配请求分页中的内存分配内存分配策略内存分配策略第五章 虚拟存储器 分配策略和置换策略可以组合出三种内存分配内存分配策略策略： 固定分配局部置换固定分配局部置换:为每个进程分配一组固定数目的物理块，在进程运行期间不再改变。进程在运行过程中发生缺页时，只能从该进程在内存的页面中选出一页进行淘汰。 可变分配全局置换可变分配全局置换：先为每个进程分配一定数目的物理块，在进程运行期间可根据情况做适当的增加或减少。进程在运行过程中发生缺页时，由系统从管理的空闲物理块

11、队列中取出一块分配给该进程。当空闲物理块队列中的物理块用完时，OS才从系统中任一进程中选出一页进行淘汰。 可变分配局部置换可变分配局部置换：先为每个进程分配一定数目的物理块。进程在运行过程中发生缺页时，从该进程在内存的页面中选出一页进行淘汰。但如果进程在运行过程中缺页频繁，系统将再为该进程但如果进程在运行过程中缺页频繁，系统将再为该进程分配若干附加的空闲物理块，直到该进程的缺页率减少到适当程分配若干附加的空闲物理块，直到该进程的缺页率减少到适当程度为止。反之，若进程在运行过程中的缺页率特别低，则系统可度为止。反之，若进程在运行过程中的缺页率特别低，则系统可适当减少分配给该进程的物理块。适当减少

12、分配给该进程的物理块。 5.2.2 请求分页中的内存分配请求分页中的内存分配内存分配策略内存分配策略第五章 虚拟存储器 在采用固定分配策略时，物理块分配算法有： 平均分配算法：将系统中所有可供分配的物理块，平均分配给各个进程。 按比例分配算法：根据进程的大小按比例分配物理块。 考虑优先权的分配算法：将系统中所有可供分配的物理块分成两部分：一部分按比例分配给各进程；另一部分则根据各进程的优先权进行分配，适当地增加高优先权进程的内存份额。5.2.2 请求分页中的内存分配请求分页中的内存分配物理块的分配算法物理块的分配算法第五章 虚拟存储器 1、何时调入所需页面2、从何处调入所需页面3、如何调入所需

13、页面5.2.3 页面调入策略页面调入策略 第五章 虚拟存储器 1 1、预调页策略、预调页策略 系统根据作业系统根据作业( (进程进程) )运行的情况，预测哪些页面将要在不久之运行的情况，预测哪些页面将要在不久之后被访问，在其被访问之前预先调入内存，这样在程序运行的过后被访问，在其被访问之前预先调入内存，这样在程序运行的过程中就不会出现缺页中断。程中就不会出现缺页中断。 这样方法与预测准确度有关。从表面上看起来很好，但系统很这样方法与预测准确度有关。从表面上看起来很好，但系统很难准确预测作业的运行情况，难以实现。目前预调页的成功率仅难准确预测作业的运行情况，难以实现。目前预调页的成功率仅约约50

14、%50%。2 2、请求调页策略、请求调页策略 进程在执行的过程中，发现要执行的程序或处理的数据所在的页面不在内存，向系统提出调入相应页面的请求，系统响应用户的请求，将其所需页面调入内存。 这种方法所确定调入的页面是一定会被访问的，易于实现。目这种方法所确定调入的页面是一定会被访问的，易于实现。目前虚拟存储器大多采用此策略。前虚拟存储器大多采用此策略。5.2.3 页面调入策略页面调入策略 何时调入页面第五章 虚拟存储器 在具有对换功能的OS中，通常把外存分为文件区和对换区。文件区用于存放文件，采取离散分配方式；对换区用于存放从内存换出的进程页面，采取连续分配方式。 从何处调入页面可分成三种情况：

15、1、全部从对换区调入所需页面 （在进程运行之前，将与该进程有关的文件从文件区拷贝到对换区）2、凡是不会被修改的文件，直接从文件区调入；对于那些可能被修改的部分，在将它们换出时调到对换区，以后需要时从对换区调入。3、UNIX方式 凡是未运行过的页面，从文件区调入；对于曾经运行过但又被换出的页面，从对换区调入。5.2.3 页面调入策略页面调入策略 从何处调入页面第五章 虚拟存储器 每当程序所要访问的页面未在内存时（状态位为“0”），便向CPU发出缺页中断请求，中断处理程序首先保留CPU环境，分析中断原因后转入缺页中断处理程序。缺页中断处理程序通过查找页表得到该页在外存的物理块后， 如果此时内存能容

16、纳新页，则启动磁盘I/O，将所缺页面调入内存，然后修改页表，将此表项写入快表中。 如果此时内存已满，则须先按照某种置换算法，从内存中选出一页准备换出: 如果该页未被修改过（修改位为“0”），可不必将该页写回磁盘； 但如果该页已被修改（修改位为“1”），则必须将它写回磁盘，然后再把所缺页面调入内存，并修改页表，且将此表项写入快表中。在缺页调入内存后，利用修改后的页表形成所要访问的物理地址，再去访问内存数据。整个页面的调入过程对用户是透明的。5.2.3 页面调入策略页面调入策略 如何调入所需页面（页面调入过程）第五章 虚拟存储器 假定程序p共有n页，而系统分配给它的内存只有m块(1mn),访问的页

17、在内存，称访问成功，否则为访问失败。设A:页面访问的总次数 S:页面访问成功的次数 F:页面访问失败的次数，则： A = S + F 缺页率 f = F/A 5.2.3 页面调入策略页面调入策略缺页率缺页率第五章 虚拟存储器 当进程运行过程中，如果发现要访问的页面不在内存而需要把它们调入内存，但内存已无空闲空间时，为了保证进程能正常运行，系统必须从内存中调出(淘汰掉)一页程序或数据，送入外存对换区中。用来选择淘汰页面的规则叫做页面置换算法。 最佳（OPT）置换算法(理想置换算法) 先进先出(FIFO)页面置换算法 最近最久未使用(LRU)置换算法5.3 页面置换算法页面置换算法第五章 虚拟存储

18、器 基本思想：选择永不使用或在未来最长时间内不再被访问的页面予以替换。该算法无法实现，只能作为其他算法的衡量标准。例：假如一个作业的页面走向为7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1。系统分配给该作业的物理块数为3。 缺页中断率为：f=F/A=9/20=45% 5.3 页面置换算法页面置换算法最佳置换算法最佳置换算法(理想置换算法理想置换算法OPT)第五章 虚拟存储器 基本思想：选择在内存中驻留时间最久的页面予以替换。例：假如一个作业的页面走向为7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1。系统分配给该作业的物理块数为3。

19、缺页中断率为：f=F/A=15/20=75% 5.3 页面置换算法页面置换算法先进先出先进先出(FIFO)页面替换算法页面替换算法 第五章 虚拟存储器 基本思想：选择过去最长时间未被访问的页面予以替换。 例：假如一个作业的页面走向为7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1。系统分配给该作业的物理块数为3。缺页中断率为：f=F/A=12/20=60% 5.3 页面置换算法页面置换算法最近最久未使用最近最久未使用(LRU)置换算法置换算法第五章 虚拟存储器 在请求分页存储管理系统中，可能会出现这样的现象，即对于刚被替换出去的页，可能马上又要被访问，需要将它调入

20、，因无空闲内存又要替换另一页，而后者可能是即将被访问的页。于是造成了系统需花费大量的时间忙于进行这种频繁的页面交换，致使系统的实际效率很低，严重时导致系统瘫痪。这种现象称为抖动现象抖动现象。 防止抖动现象可以有多种办法，例如，采取局部替换策略、引入工作集算法、挂起若干进程等。 所谓工作集工作集是指在某段时间间隔里，进程实际要访问的页面的集合。引入虚拟存储器后，虽然程序只须有少量的内存就可以运行，但为了使程序有效运行，较少产生缺页，就必须使程序的工作集全部在内存中。 5.4 抖动与工作集抖动与工作集第五章 虚拟存储器 段表中除了有段号、段长、段的基址三项外，还需要存取方式、访问字段、修改位、存在位、增补位、外存起始地址等信息。 5.5 请求分段存储管理方式请求分段存储管理方式(段式虚拟存储管理段式虚拟存储管理) 请求分段中的硬件支持请求分段中的硬件支持一段表机制第五章 虚拟存储器 与缺页中断类似，每当所要访问的段不在内存时，便要产生缺段中断，请求操