《【考研计算机专业课】武汉大学操作系统PPT课件第6章虚拟存储器》由会员分享，可在线阅读，更多相关《【考研计算机专业课】武汉大学操作系统PPT课件第6章虚拟存储器（141页珍藏版）》请在金锄头文库上搜索。
1、第6章 虚拟存储器,常规存储器管理方式要求作业运行前全部装入内存，作业装入内存后一直驻留内存直至运行结束。 这种存储管理方式限制了大作业的运行。而物理扩充内存会增加成本，故应从逻辑上扩充内存。,6.1 虚拟存储器概念,虚拟存储器（Virtual Memory）的理论基础是程序执行时的局部性原理。 局部性原理是指程序在执行过程中一个较短时间内，程序所执行的指令地址和操作数地址分别局限于一定区域内。 例如： 除转移和过程调用外，程序主要是顺序执行。 过程调用使程序从一部分区域转至另一部分区域 循环结构,局部性的体现,局部性体现为： 时间局部性：一条指令的一次执行和下次执行，一个数据的一次访问和下次
2、访问，都集中在一个较短时间内。 空间局部性：当前执行的指令和将要执行的指令，当前访问的数据和将要访问的数据，都集中在一个较小范围内。,虚拟存储器的基本原理,在程序运行之前，将程序的一部分放入内存后就启动程序执行。 在程序执行过程中，当所访问的信息不在内存时，由操作系统将所需要的部分调入内存，然后继续执行程序。 另一方面，操作系统将内存中暂时不使用的内容换出到外存上，从而腾出空间存放将要调入内存的信息。 从效果上看，这样的计算机系统好像为用户提供了一个存储容量比实际内存大得多的存储器，将这个存储器称为虚拟存储器。,虚拟存储器,虚拟存储器是指具有请求调入和置换功能，能从逻辑上对内存容量加以扩充的一
3、种存储器系统。 虚拟存储器是一种以时间换空间的技术。,虚拟存储器的特征,离散性：不连续内存分配 多次性：一个作业分多次装入内存 对换性：允许运行中换进换出 虚拟性：逻辑上扩充内存,虚拟存储器的本质,虚拟存储器的本质是将程序的访问地址和内存的可用地址分离，为用户提供一个大于实际主存的虚拟存储器。 虚拟存储器的容量受限于： 地址结构 外存容量,实现虚拟存储技术的物质基础,相当数量的外存：足以存放多个用户的程序。 一定容量的内存：在处理机上运行的程序必须有一部分信息存放在内存中。 地址变换机构：动态实现逻辑地址到物理地址的变换。,虚拟存储器的实现方法,常用的虚拟存储技术有： 请求分页存储管理 请求分
4、段存储管理 具有请求调页功能的段页式存储管理系统,6.2 请求分页存储管理-6.2.1,请求分页存储管理方法是在分页存储管理的基础上增加了请求调页和页面置换功能。 实现思想：在作业运行之前只装入当前需要的一部分页面便启动作业运行。在作业运行过程中，若发现所要访问的页面不在内存，便由硬件产生缺页中断，请求OS将缺页调入内存。若内存无空闲存储空间，则根据某种置换算法淘汰已在内存的某个页面，以腾出内存空间装入缺页。,请求分页系统中的支持机构,请求分页中的支持机构有： 页表 缺页中断机构 地址变换机构 请求调页和页面置换软件,6.2.2 页表,请求分页系统中使用的主要数据结构仍然是页表。 但由于每次只
5、将作业的一部分调入内存，还有一部分内容存放在磁盘上，故需要在页表中增加若干项。 扩充后的页表项如下所示：,扩充后的页表项,页号和物理块号：其定义同分页存储管理。 状态位：用于表示该页是否在主存中。 访问字段：用于记录本页在一段时间内被访问的次数，或最近已有多长时间未被访问。 修改位：用于表示该页调入内存后是否被修改过。 外存地址：用于指出该页在外存上的地址。,6.2.3 缺页中断与地址变换,在请求分页系统中，当所访问的页不在内存时，便产生缺页中断，请求OS将缺页调入内存。 缺页中断处理程序根据该页在外存的地址把它调入内存。在调页过程中，若内存有空闲空间，则缺页中断处理程序只需把缺页装入并修改页
6、表中的相应项；若内存中无空闲物理块，则需要先淘汰内存中的某些页，若淘汰页曾被修改过，则还要将其写回外存。,缺页中断与一般中断的区别,缺页中断与一般中断的区别主要有： 在指令的执行期间产生和处理缺页中断。 一条指令可以产生多个缺页中断。如：执行一条复制指令copy A to B 缺页中断返回时执行产生中断的指令，一般中断返回时执行下条指令,B:A:Copy ATo B,页面,654321,地址变换,请求分页存储管理系统的地址变换过程类似于分页存储管理，但当被访问页不在内存时应进行缺页中断处理。,地址变换流程,程序请求访问一页,页号页表长度？,页在内存？,Y,N,CPU检索快表,Y,修改快表,页表
7、项在快表中？,产生缺页中断,N,访问页表,越界中断,N,Y,修改访问位和修改位,形成物理地址,A,缺页处理流程,缺页中断处理,保留CPU现场,该页被修改否？,从外存中找到缺页,N,将该页写回外存,内存满否？,Y,选择一页换出,N,Y,从外存读缺页入内存,修改页表,A,6.2.4 页面分配和置换策略,在为进程分配物理块时应确定: 进程需要的最少物理块数 进程的物理块数是固定还是可变 按什么原则为进程分配物理块数,最小物理块数的确定,最小物理块数是指能保证进程正常运行所需的最少物理块数，若小于此值进程无法运行。 一般情况下： 单地址指令且采用直接寻址，则所需最少物理块数为2。 若单地址指令且允许采
8、用间接寻址，则所需最少物理块数为3。 某些功能较强的机器，指令及源地址和目标地址均跨两个页面，则最少需要6个物理块。,页面分配和置换策略,页面分配常采用固定分配和可变分配两种策略。 页面置换也有全局置换和局部置换两种策略。 将分配策略和置换范围组合可得如下三种策略： 固定分配局部置换 可变分配全局置换 可变分配局部置换,固定分配局部置换,固定分配局部置换：基于某种原则为每个进程分配固定数量的物理块，当进程运行中出现缺页时，只能从自己的页面中选择一页换出，然后再调入缺页。 实现这种策略的困难在于：难以确定应为每个进程分配多少个物理块。,可变分配全局置换,可变分配全局置换：先为系统中的每个进程分配
9、一定数量的物理块，操作系统本身也保持一个空闲物理块队列。当某进程发生缺页时，由系统从空闲物理块队列中取出一个物理块分配给该进程；当空闲物理块队列中的物理块用完时，操作系统才从内存中选择一页调出，该页可以是系统中任何一个进程的页面。 这是一种容易实现的页面分配和置换策略，目前已用于若干操作系统中。,可变分配局部置换,可变分配局部置换：根据某种原则为每个进程分配一定数量的物理块，当进程发生缺页中断时，只允许从该进程的页面中选出一页换出。如果某进程的缺页率较高，则系统再为该进程分配若干物理块；反之若某进程的缺页率特别低，则系统可适当减少分配给该进程的物理块数。 该算法比较复杂，但性能较好。,物理块分
10、配算法,物理块分配是指按什么原则给进程分配物理块数，通常有以下几种分配算法： 平均分配算法：将系统中所有可供分配物理块平均分配给每个进程。 按比例分配算法：根据进程大小按比例分配物理块。 按优先级分配算法：有两种实现方案 将可供分配的物理块分为两部分，一部分按比例分配给每个进程，另一部分根据进程的优先级适当增加物理块。 先按比例为进程分配物理块，当高优先级进程发生缺页时，允许它从低优先级进程处获得物理块。,6.2.5 页面置换算法,页面置换（ Page Replacement ）算法又称为页面淘汰算法，是用来选择换出页面的算法。 下面介绍几种比较常用的页面置换算法 。,1最佳置换算法（OPT）
11、,最佳（Optimal）算法是从内存中选择将来最长时间不会使用的页面予以淘汰。 特点：因页面访问的未来顺序很难精确预测，该算法具有理论意义，可以用来评价其他算法的优劣。,最佳置换算法例,假定系统为某进程分配了3个物理块，页面访问序列为：1、2、3、4、1、2、5、1、2、3、4、5，开始时3个物理块均为空闲，采用最佳置换算法时的页面置换情况如下所示：,采用最佳置换算法的页面置换情况,从上表中可以看出，共发生了7次缺页，其缺页率为7/1258.3% 。,5,缺,5,4,3,4,缺,5,2,3,3,2,1,缺,5,2,1,5,2,1,缺,4,2,1,4,缺,3,2,1,3,缺,2,1,2,缺,1,
12、1,块3,块2,块1,走向,2. 先进先出算法（FIFO）,先进先出（ First-In-First-Out ）算法是选择调入主存时间最长的页面予以淘汰。 特点：该算法实现比较简单，对按线性顺序访问的程序比较合适，但可能产生异常现象。很少使用纯粹的FIFO。 Belady现象：在某些情况下，分配给进程的页面数增多，缺页次数反而增加。,先进先出置换算法例,假定系统为某进程分配了3个物理块，页面访问序列为：1、2、3、4、1、2、5、1、2、3、4、5，开始时3个物理块均为空闲，采用先进先出置换算法时的页面置换情况如下所示：,采用先进先出算法的页面置换情况,从上表中可以看出，共发生了9次缺页中断。
13、其缺页率为9/1275% 。,5,缺,4,3,5,4,缺,2,3,5,3,2,1,缺,2,1,5,5,缺,2,1,4,2,缺,3,1,4,1,缺,3,2,4,4,缺,3,2,1,3,缺,2,1,2,缺,1,1,块3,块2,块1,走向,为进程分配4个物理块,从上表中可以看出，共发生了10次缺页中断。其缺页率为10/1283.3% 。,3,3,3,4,4,4,4,块4,缺,2,5,4,5,缺,2,1,4,4,缺,2,1,5,3,缺,2,1,5,2,缺,3,1,5,1,缺,3,2,5,5,2,1,缺,3,2,1,4,缺,3,2,1,3,缺,2,1,2,缺,1,1,块3,块2,块1,走向,无异常现象的
14、页面序列,假定系统为某进程分配了3个物理块，页面访问序列为：7、0、1、2、0、3、0、4、2、3、0、3，开始时3个物理块均为空闲，采用先进先出置换算法时的页面置换情况如下所示：,页面置换情况,从上表中可以看出，共发生了10次缺页中断。其缺页率为10/1283.3% 。,3,缺,3,2,0,0,缺,3,2,4,3,缺,0,2,4,2,缺,0,3,4,4,缺,0,3,2,0,缺,1,3,2,3,0,缺,1,0,2,2,缺,1,0,7,1,缺,0,7,0,缺,7,7,块3,块2,块1,走向,为进程分配4个物理块,从上表中可以看出，共发生了7次缺页中断。其缺页率为7/1258.3% 。,2,2,2
15、,2,块4,3,缺,0,4,3,0,3,2,缺,1,4,3,4,0,缺,1,0,3,3,0,缺,1,0,7,2,缺,1,0,7,1,缺,0,7,0,缺,7,7,块3,块2,块1,走向,3.最近最久未使用置换算法(LRU),最近最久未使用算法选择最近一段时间内最长时间没有被访问过的页面予以淘汰。 为此，应赋予每个页面一个访问字段，用于记录页面自上次访问以来所经历的时间。 LRU是Least Recently Used，也称为最近最少使用,LRU算法例,假定系统为某进程分配了3个物理块，页面访问序列为：1、2、3、4、1、2、5、1、2、3、4、5，开始时3个物理块均为空闲，采用LRU置换算法时的页面置换情况如下所示：,采用LRU算法的页面置换情况,从上表中可以看出，共发生了10次缺页，其缺页率为10/1283.3% 。,缺,5,4,3,5,缺,2,4,3,4,缺,2,1,3,3,2,1,缺,2,1,5,5,缺,2,1,4,2,缺,3,1,4,1,缺,3,2,4,4,缺,3,2,1,3,缺,2,1,2,缺,1,1,块3,块2,块1,走向,为进程分配4个物理块,从上表中可以看出，共发生了8次缺页中断。其缺页率为8/1266.7% 。,3,
