页面置换算法.ppt

1、第五章 虚拟存储器,本章要点（1/2）,目标：了解虚拟存储器的相关概念和技术。 虚拟存储的基本概念 为什么要引入虚拟存储器？ 虚拟存储器是如何扩充内存容量的？ 虚拟存储器具有哪些特征？每种特征的具体含义是什么？它们相互之间存在着什么样的关系？它们与离散分配之间又存在着什么样的关系？ 实现虚拟存储器的关键技术是什么？这些技术的实现需要得到哪些硬件支持和软件支持？,请求分页系统的基本原理 为实现虚拟存储器，必须扩充表项的内容，除了内存块号和存取权限字段以外，页表中还必须增加哪些字段，为什么要增加这些字段？ 请求分页系统的地址变换也必须通过地址变换机构进行，请求分页系统的地址变换机构，是在基本分页系

2、统的地址变换机构的基础上增加了哪些功能而形成？ 常用的页面置换算法有哪些？ 为什么LRU算法具有比较好的性能？它的主要缺点是什么？可用什么方法实现LRU近似算法？,本章要点（2/2）,5.1 虚拟存储器概述 5.2 请求分页存储管理方式 5.3 页面置换算法 5.4 “抖动”与工作集 5.5 请求分段存储管理方式,本章内容,5.1 虚拟存储器概述,5.1 虚拟存储器概述,简单存储器管理方式，都要求将一个作业全部装入内存方能运行。于是出现以下两种情况： 有的作业很大，所要求的内存空间超过了内存的总容量； 有大量的作业要求运行，但由于内存容量不足，难以容纳所有的作业。 解决方法： 从物理上增加内容

3、容量 从逻辑上扩充内存容量,5.1.1 常规存储管理方式的特征和局部性原理,简单存储器的特征 一次性：作业必须一次性全部装入内存才能开始运行，这是一种对内存空间的浪费。 驻留性：作业装入内存后，便一直驻留在内存直至作业运行结束，占据了宝贵的内存资源 一次性及驻留性带来的问题： 会使许多在进程运行时不用的或暂时不用的程序（数据）占据大量的内存空间; 使一些需要运行的作业无法装入运行。,1、常规存储器管理方式的特征,问题的提出(P.Denning) 程序在执行时将呈现出局部性规律，即在一较短时间内，程序的执行仅限于某个部分；相应地，它所访问的存储空间也局限于某个区域。 论点 程序在执行时，大多数情

4、况下是顺序执行的 过程调用将会使程序的执行轨迹由一部分区域转至另一区域，但调用深度通常不超过5 程序中存在许多循环结构，它们虽由少数指令构成，但多次执行 程序中对数据结构的处理，往往都局限于很小的范围内,2、局部性原理,一次性及驻留性是否是程序运行时所必需的？,局部性的表现方式 时间局部性 ：一个数据结构被访问，不久可能再次被访问。典型原因： 程序中存在大量的循环操作 空间局部性：一段时间访问的地址可能集中在一定范围 。典型原因：程序顺序执行,2、局部性原理,sum = 0; for (i = 0; i n; i+) sum += ai; return sum;,1961年英国曼彻斯特大学Ki

5、lbrn等人提出 70年代广泛地应用于大中型计算机系统中 目前许多微型机也开始使用虚拟存储器 是进一步完善主存-辅存存储层次，解决主存容量提出的。 实现思想：当进程运行时，先将一部分程序装入内存，另一部分暂时留在外存，当要执行的指令不在内存时，由系统自动将它们从外存调入内存。,3、虚拟存储器的基本工作情况,什么是虚拟存储？ 定义：具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。它把内存与外存有机结合起来使用，构成容量很大的“内存”。 目的：提高内存利用率,1、虚拟存储器定义,5.1.2 虚拟存储器的定义和特征,虚拟存储器管理应解决以下问题： 主存和辅存的统一管理问题

6、逻辑地址到物理地址的转换问题 部分装入和部分对换问题 把哪一部分装入内存 何时把页面装入 装入内存什么位置 当内存没有空间时淘汰哪个页面,1、虚拟存储器定义,多次性：指一个作业中的程序和数据允许被分成多次调入内存运行，这是虚拟存储器最重要的特征。 对换性：指允许作业中的程序和数据在作业运行过程中换入、换出。 虚拟性：指能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量。这是虚拟存储器表现出的最重要特征，是实现虚拟存储器的最重要的目标。 虚拟性是以多次性和对换性为基础，多次性和对换性是建立在离散分配的基础上。,2、虚拟存储器的特征,5.1.3 虚拟存储器的实现方法,实现虚拟存储的

7、典型过程,虚拟存储器管理的技术支持 必须有相应的硬件支持，用以实现虚拟分页和虚拟分段存储管理； 操作系统必须提供相应的软件支持，管理页或段在内存和外存之间的移动。,在简单分页基础上，增加了请求调页功能、页面置换功能。 置换时以页面为单位进行 系统提供的硬件支持： 请求分页的页表机制； 缺页中断机构； 地址变换机构。 实现请求分页的软件： 请求调页软件 页面置换软件,1、请求分页系统,在分段的基础上，增加了请求调段功能、分段置换功能 置换时以段为单位进行 系统提供的硬件支持： 请求分段的段表机制； 缺段中断机构； 地址变换机构。 实现请求分段的软件： 请求调段软件 段置换软件,2、请求分段系统,

8、5.2 请求分页存储管理方式,5.2 请求分页存储管理方式,建立在基本分页存储管理之上，是目前比较常用的一种虚拟存储管理技术,5.2.1 请求分页中的硬件支持,1、请求页表机制 在请求分页系统中所需要的主要数据结构是请求页表。 作用：将用户地址空间中的逻辑地址变换为内存空间的物理地址。 请求分页系统中的每个页表项如下图所示：,指示该页是否已调入内存,记录本页在一段时间内被访问的次数，或记录本页最近已有多长时间未被访问，供选择换出页面时参考,该页在调入内存后是否被修改过，供置换页面时参考,指出该页在外存上的地址，供调入该页时参考,2、缺页中断机构,缺页中断机构 与一般中断相同的处理步骤：保护CP

9、U环境、分析中断原因、转入中断处理程序进行处理、恢复CPU环境等几个步骤。 缺页中断和一般的中断相比有如下区别： 1）缺页中断在指令执行期间产生和处理中断信号，而一般中断在一条指令执行完后检查和处理中断信号； 2）缺页中断返回到该指令的开始重新执行该指令，而一般中断返回到该指令的下一条指令执行 ； 3）一条指令在执行期间，可能产生多次缺页中断。,2. 缺页中断机构,图 5-1 涉及6次缺页中断的指令,对硬件的要求： 系统中的硬件机构应能够保存多次中断时的状态，并保证最后能够返回到中断前产生缺页中断的指令处，继续执行。,图 5-2 请求分页中的地址变换过程,3、地址变换机构,5.2.2 请求分页

10、中的内存分配,页面分配原则 缺页中断、I/O中断频繁会降低运行效率，因此应尽可能减少缺页中断的次数。 为进程分配物理块时要考虑的问题： 保证进程正常运行所需要的最少物理块； 为进程分配的物理块数目是固定的还是可变的 为进程分配物理块数是采取平均分配算法，还是根据进程的大小比例予以分配。,是指能保证进程正常运行所需最小物理块数。 当系统为进程分配的物理块数少于此值时，进程将无法运行。 每个进程的最小页框数是由计算机结构体系所定义的，最大数是由有效的物理内存所定义的。 PDP-11的移动指令包括多个字，因此指令本身可能会跨2页。另外，它的两个操作数可能是间接引用，所以总共需要6个物理块。 IBM

11、370 MVC指令。因为指令是从存储器地址到存储器地址，需要花费6个字节，并且会跨2个页面。要移动的字符块和将要移至的区域也都会跨2个页面。这种情况就要求有6个页框。,1、最小物理块数的确定,分配策略：固定和可变分配策略。 置换策略：全局置换和局部置换。 三种适用的内存分配策略： 固定分配局部置换(Fixed Allocation, Local Replacement) 可变分配全局置换(Variable Allocation, Global Replacement) 可变分配局部置换(Variable Allocation, Local Replacement),2、内存分配策略,固定分配局

12、部置换 固定分配：为每个进程分配固定数目的物理块，整个运行期间不再改变。 局部置换：如果进程在运行中发现缺页，则只能从在内存中分配给该进程的固定物理块中选出一页换出，然后再调入一页。 难点：为每个进程分配多少物理块难以确定 太少，频繁缺页中断，降低系统吞吐量。 太多，内存驻留进程减少，可能造成资源空闲，而且实现进程对换时，会花费更多的时间。,2、内存分配策略,可变分配全局置换（易于实现） 可变分配：先为系统中的每个进程分配一定数目的物理块，在进程运行期间可以适当增减，而OS自身也保持一个空闲物理块队列。 全局置换：当某进程发现缺页，由系统从空闲的物理块队列中，取出一物理块分配该进程，并将欲调入

13、的缺页装入其中。当空闲物理块用完时，OS从内存中任选一页调出（任意进程）。,2、内存分配策略,可变分配局部置换 根据进程的类型或程序员的要求，为每个进程分配一定数目的物理块。 当某进程发生缺页时，只允许从该进程在内存的页面中选择一页换出，这样就不会影响其它进程的运行。 如果进程在运行中频繁地发生缺页中断，则系统再为该进程分配附加的物理块；反之，若一个进程在运行中缺页频率低，则此时适当减少分配给该进程的物理块。,2、内存分配策略,平均分配算法：物理块平均分配给各进程； 缺点：未考虑到进程本身的大小，不公平。 按比例分配算法：按进程大小的比例分配物理块； n为系统内的进程数；Si为i进程的页面数；

14、m为可用的物理块总数；i进程能分到的物理块数为bi 考虑优先权的分配算法：按照作业的重要性、紧迫性进行分配。 一般将可供分配的物理块分为两部分：一部分按比例分配；另一部分按优先权适当增加份额。 在重要的实时系统中，则可能是完全按优先级为各进程分配物理块。,3、物理块分配算法,5.2.3 页面调入策略,应解决从何时调入页面、从何处调入页面以及如何调入的问题！ 1、何时调入页面 预调页策略：根据空间局部性，将不久之后便会被访问的程序或数据所在的页面，预先调入内存。 特点：预调页的成功率仅有50%。 主要用于进程的首次调入。 请求调页策略：进程在运行时，发现其所访问的程序页面不在内存，请求系统将所需

15、页面调入内存。 特点：系统开销大；易实现。虚拟存储器大多采用此策略。,2、从何处调入页面,系统有足够的存储空间，这时可以全部从对换区调入所需页面，以提高调页的速度。 系统缺少足够的对换区空间，这时凡是不会被修改的文件，都直接从文件区调入；但对于那些可能被修改的部分，在将它们换出时，便须调到对换区，以后需要时再从对换区调入。 UNIX方式，凡是未运行过的页，都应从文件区调入。对于曾经运行过而又被换出的页面，从对换区调入。,缺页中断处理程序通过查找页表，得到该页所在外存的物理块号。 如果此时内存空闲，能容纳新页，则启动磁盘I/O将所缺之页调入内存，然后修改页表。 如果内存已满，则须先按照某种置换算

16、法，从内存中选出一页准备换出； 如果该页未被修改过，可不必将页写入磁盘；但如果该页已被修改，则必须将它重新写入磁盘，然后再将缺页调入内存，并修改页表中的相应表项，再将此页表项写入快表中。据修改后的页表形成去访问数据的物理地址。,3、页面调入过程,衡量指标缺页率f 假定作业p共计n页，系统分配给它的主存块为m (m = n)。如果作业p在运行中成功访问页面的次数为S（所访问的页面在主存中），不成功的访问次数为F，则总的访问次数为： A = S + F f = F / A 影响缺页中断率的因素： 页面大小、进程所分配物理块的数目、页面替换算法、程序固有特性 缺页中断处理时间：t=ta+(1-) t

17、b 其中被置换的页面被修改的概率为，缺页中断处理时间为ta ，被置换页面没有被修改的缺页中断时间为tb 。,4、缺页率,5.3 页面置换算法,5.3 页面置换算法,在进程运行过程中，当所要访问的页面不在内存时，则应将它调入内存。若此时内存已无空闲空间，则应选择一页调出。将哪个页面调出，则须根据一定的算法来确定。 功能：需要调入页面时，选择内存中哪个物理页面被置换，称为replacement policy。 不适当的算法可能会导致进程发生“抖动”。 抖动：刚被换出的页面很快又要被访问，需要重新调入，此时又需要再选一页调出；而此刚被调出的页很快又被访问，又需将它调入，如此频繁地更换页面，以致一个进

18、程在运行中把大部分时间都花费在页面置换上，则称该进程发生了“抖动”。,5.3 页面置换算法,目标：把未来不再使用的或短期内较少使用的页面调出，通常只能在局部性原理指导下依据过去的统计数据进行预测； 常用的页面置换算法 最佳置换算法(Optimal, OPT) 先进先出算法(First In First Out, FIFO) 近期最久未用过算法（Least Recently Used, LRU） CLOCK置换算法（Not Recently Used, NRU） 页面缓冲算法（Page Buffering Algorithm, PBA） 近期最少使用算法(Least Frequently Use

19、d, LFU),5.3.1 最佳置换算法和先进先出置换算法,1、最佳置换算法（OPT） 方法：根据未来使用情况将未来的近期里不用的页替换出去。 实现： 确定要替换的时刻t。 找出主存中每个页将来要用到的时刻ti。 ti -t最大的页将被替换。 特点：命中率高，但难于实现（必须运行一遍，才能知道未来的时刻ti），是理想算法，用于评价其它替换算法。,发生了6次页面置换，9次缺页中断，总访问次数20次，缺页率9/2045 。,1、最佳置换算法（OPT）,图 5-3 利用最佳页面置换算法时的置换图,方法：最早装入主存的页作为被替换的页，即选择在内存中驻留时间最久的页面予以淘汰。 实现： 只需把一个进程

20、已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总可以指向最老的页面。 特点：利用历史信息，但不反映程序的局部性（最先进入的页可能是现在经常使用的页）,2、先进先出(FIFO)页面置换算法,发生了12次页面置换，15次缺页中断，总访问次数20次，缺页率15/2075 。,2、先进先出(FIFO)页面置换算法,页面,引用,7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1,图 5-4 利用FIFO置换算法时的置换图,5.3.2 最近最久未使用和最少使用置换算法,方法：近期最久未访问过的页作为被替换的页 实现： 赋予每个页面一个访问字段，用

21、来记录一个页面自上次被访问以来所经历的时间t，当须淘汰一个页面时，选择现有页面中其t值最大的页面予以淘汰。 特点：计数器硬件较少，主存页面表可由软硬件实现修改，根据“历史”预测“未来”。,1、LRU(Least Recently Used)置换算法的描述,1、LRU(Least Recently Used)置换算法的描述,页面引,用,7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1,发生了9次页面置换，12次缺页中断，总访问次数20次，缺页率12/2060 。,图 5-5 利用LRU页面置换算法时的置换图,LRU硬件机构如下： 每个页面设立移位寄存器：被访问时左边

22、最高位置1，定期右移并且最高位补0，于是寄存器数值最小的是最久未使用页面。 一个特殊的栈：把被访问的页面移到栈顶，于是栈底的是最久未使用页面。,2、LRU置换算法的硬件支持,图 5-6 某进程具有8个页面时的LRU访问情况,2,3,2,1,5,2,4,5,图5-7 用栈保存当前使用页面时栈的变化情况,3,2,5,2,2,3,2,1,5,2,4,5,3,2,5,2,选择到当前时间为止被访问次数最少的页面被置换； 每页设置移位寄存器，每当页面被访问时，将该移位寄存器的最高位置1，再每隔一定时间右移一次； 发生缺页中断时，淘汰 最小的页面。 这种算法不能真正反映出页面的使用情况 ，因为在每一时间间隔

23、内，只是用寄存器的一位来记录页面的使用情况，在该时间间隔内，对某页访问一次和访问1000次是完全等效的。,3、最少使用(LFU： Least Frequently Used)置换算法,5.3.3 Clock置换算法,1、简单的Clock置换算法 每页设置一位访问位，若该页被访问则其访问位被置1； 内存中所有页面都通过链接指针链接成一个循环队列，置换时采用一个指针，从当前指针位置开始按地址先后检查各页，寻找访问位为0的页面作为被置换页； 指针经过的访问位为1的页都将其访问位置0，最后指针停留在被置换页的下一个页。,1、简单的Clock置换算法,图 5-8 简单Clock置换算法的流程,入口,查询

24、指针前进一步， 指向下一个表目,选择该页面淘汰,返回,页面使用位=0？,置页面 使用位=0,N,Y,1、简单的Clock置换算法,1、简单的Clock置换算法,在将一个页面换出时，对于修改过的页面在换出时所付出的开销将比未修改过的页面开销大。 在改进型Clock算法中，它既考虑到页面的使用情况，又考虑页面是否被修改过。即选择换出页面时，既要是未使用过的页面，又要是未修改过的页面，把同时满足两条件的页面作为首选淘汰页。 访问位 A 和修改位 M 的四种组合情况： 1类（A=0，M=0）：表示该页最近既未被访问，又未被修改，是最佳淘汰页 2类（A=0，M=1）：表示该页最近未被访问，但已被修改，并

25、不是很好的淘汰页 3类（A=1，M=0）：最近已被访问，但未被修改，该页有可能再被访问 4类（A=1，M=1）：最近已被访问且被修改，该页可能再被访问,2、改进型Clock置换算法,执行过程： 第一步，寻找第一类页面(不修改A)； 第二步，第一步失败，寻找第二类页面，同时置访问过的A=0； 第三步，重复第一步或第二步，此时必能找到。 特点：（与简单Clock算法比较） 可减少磁盘I/O操作次数；可能须经几次扫描才能找到可置换的页,系统开销增加。,2、改进型Clock置换算法,2、改进型Clock置换算法,5.3.4 页面缓冲算法,页面置换算法 写回磁盘的频率 建立一个已修改换出页面的链表，采用

26、集中写回的方式 读入内存的频率 修改后未写回磁盘的页面，可以直接从已修改换出页面链表中获取,1、影响页面换进换出效率的若干因素,2、页面缓冲算法(PBA： Page Buffering Algorithm) ,内存分配策略：可变分配局部置换 被置换页面的选择和处理：用FIFO算法选择被置换页，把被置换的页面放入两个链表之一。 如果页面未被修改，就将其归入到空闲页面链表的末尾； 否则将其归入到已修改页面链表。 PBA算法的特点： 显著降低了页面换进、换出的频率，减少磁盘I/O次数； 置换策略简单，无须硬件支持，实现简单。,3、访问内存的有效时间,请求分布管理方式的内存有效访问时间： 被访问的页在

27、内存中，且其对应的页表项在快表中 EAT = + t 被访问的页在内存中，且其对应的页表项不在快表中 EAT = 2( + t) 被访问的页不在内存中 EAT = + 2( + t) 考虑快表的命中率和缺页率 EAT = +at+ (1-a) t+f(+ +t)+(1-f) ( +t),其中：为查找快表的时间；t为访问实际物理地址所需的时间； 为缺页中断处理时间；a为快表命中率；f为缺页率。,5.4 “抖动”与工作集,5.4.1 多道程序度与“抖动”,1、多道程序度与处理机利用率,图 5-9 处理机的利用率,产生抖动的原因：同时在系统中运行的进程太多，由此分配给每一个进程的物理块太少，不能满足

28、进程正常运行的基本要求，致使每个进程在运行时，频繁地出现缺页。 这种频繁的换进换出的活动被称为抖动。如果一个进程花费在页面置换的时间多于执行时间，就是抖动。,2、产生“抖动”的原因,5.4.2 工作集,1、工作集的基本概念,进程发生缺页率的时间间隔与进程获得的物理块数有关。 工作集理论： 1968年由Denning提出并推广 理论基础：程序运行时的局部性原理 现象：程序在运行期间，对页面的访问是不均匀的，在一段时间内仅局限于较少的页面，在另一段时间内，又可能局限于另一些较少的页面进行访问。,2、工作集的定义,工作集：是指在某段时间间隔里，进程实际所要访问页面的集合。 工作集的产生：属于预调页策

29、略，用程序过去某段时间内的行为作为程序在将来某段时间内行为的近似。 进程在时间t的工作集记作w(t, ) 工作集的定义：进程在时间间隔（ t-, t）中引用页面的集合 变量 为工作集的“窗口尺寸”。,假定= 10,5.4.3 “抖动”的预防方法,将“抖动”造成的影响限制在较小的范围 效果不佳，“抖动”进程会延长其他进程缺页的中断的处理时间 确定造成处理机利用率低的原因 多道度不够 内存中分配给已有作业的物理块数不够,1、采用局部置换策略,2、把工作集算法融入到处理机调度中,L为缺页之间的平均时间；S为平均缺页服务时间 LS，表示很少发生缺页 LS，表示频繁发生缺页 LS，表示磁盘与处理机均能达

30、到它们的最大利用率 当多道程序度偏高，影响到处理机的利用率，则应选择挂起某些当前活动的进程，将它们对换至外存。 首先选择优先级最低的进程 其次选择优先级较低的进程 再选择并不十分重要、但却较大的进程 选择剩余执行时间最多的进程,3、利用“L=S”准则调节缺页率,4、选择暂停的进程,5.5 请求分段存储管理方式,请求分段式管理需要请求段表机制、缺段中断机构以及地址变换机构。 1、请求段表机制 请求段表是请求分段管理方式的主要数据结构。请求分段的段表项如图所示。,5.5.1 请求分段中的硬件支持,在请求分段系统中，采用的是请求调段策略。 进程访问的段不在内存，缺段中断机构产生一缺段中断信号，进入OS后由缺段中断处理程序将所缺的段调入内存。,2、缺段中断机构,图 5-12 请求分段系统中的中断处理过程,2、缺