页面置换算法

第五章虚拟存储器本章要点（1/2）目标：了解虚拟存储器的相关概念和技术。虚拟存储的基本概念为什么要引入虚拟存储器？虚拟存储器是如何扩充内存容量的？虚拟存储器具有哪些特征？每种特征的具体含义是什么？它们相互之间存在着什么样的关系？它们与离散安排之间又存在着什么样的关系？实现虚拟存储器的关键技术是什么？这些技术的实现须要得到哪些硬件支持和软件支持？恳求分页系统的基本原理为实现虚拟存储器，必需扩充表项的内容，除了内存块号和存取权限字段以外，页表中还必需增加哪些字段，为什么要增加这些字段？恳求分页系统的地址变换也必需通过地址变换机构进行，恳求分页系统的地址变换机构，是在基本分页系统的地址变换机构的基础上增加了哪些功能而形成？常用的页面置换算法有哪些？为什么LRU算法具有比较好的性能？它的主要缺点是什么？可用什么方法实现LRU近似算法？本章要点（2/2）5.1虚拟存储器概述5.2恳求分页存储管理方式5.3页面置换算法5.4“抖动”与工作集5.5恳求分段存储管理方式本章内容5.1虚拟存储器概述5.1虚拟存储器概述简洁存储器管理方式，都要求将一个作业全部装入内存方能运行。于是出现以下两种状况：有的作业很大，所要求的内存空间超过了内存的总容量；有大量的作业要求运行，但由于内存容量不足，难以容纳全部的作业。解决方法：从物理上增加内容容量从逻辑上扩充内存容量5.1.1常规存储管理方式的特征和局部性原理简洁存储器的特征一次性：作业必需一次性全部装入内存才能起先运行，这是一种对内存空间的奢侈。驻留性：作业装入内存后，便始终驻留在内存直至作业运行结束，占据了珍贵的内存资源一次性及驻留性带来的问题：会使很多在进程运行时不用的或短暂不用的程序（数据）占据大量的内存空间;使一些须要运行的作业无法装入运行。1、常规存储器管理方式的特征问题的提出(P.Denning)程序在执行时将呈现出局部性规律，即在一较短时间内，程序的执行仅限于某个部分；相应地，它所访问的存储空间也局限于某个区域。论点程序在执行时，大多数状况下是依次执行的过程调用将会使程序的执行轨迹由一部分区域转至另一区域，但调用深度通常不超过5程序中存在很多循环结构，它们虽由少数指令构成，但多次执行程序中对数据结构的处理，往往都局限于很小的范围内2、局部性原理一次性及驻留性是否是程序运行时所必需的？局部性的表现方式时间局部性：一个数据结构被访问，不久可能再次被访问。典型缘由：程序中存在大量的循环操作空间局部性：一段时间访问的地址可能集中在确定范围。典型缘由：程序依次执行2、局部性原理sum=0;for(i=0;i<n;i++) sum+=a[i];returnsum;1961年英国曼彻斯特高校Kilbrn等人提出70年头广泛地应用于大中型计算机系统中目前很多微型机也起先运用虚拟存储器是进一步完善主存-辅存存储层次，解决主存容量提出的。实现思想：当进程运行时，先将一部分程序装入内存，另一部分短暂留在外存，当要执行的指令不在内存时，由系统自动将它们从外存调入内存。3、虚拟存储器的基本工作状况什么是虚拟存储？定义：具有恳求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。它把内存与外存有机结合起来运用，构成容量很大的“内存”。目的：提高内存利用率1、虚拟存储器定义5.1.2虚拟存储器的定义和特征虚拟存储器管理应解决以下问题：主存和辅存的统一管理问题逻辑地址到物理地址的转换问题部分装入和部分对换问题把哪一部分装入内存何时把页面装入装入内存什么位置当内存没有空间时淘汰哪个页面1、虚拟存储器定义多次性：指一个作业中的程序和数据允许被分成多次调入内存运行，这是虚拟存储器最重要的特征。对换性：指允许作业中的程序和数据在作业运行过程中换入、换出。虚拟性：指能够从逻辑上扩充内存容量，运用户所看到的内存容量远大于实际内存容量。这是虚拟存储器表现出的最重要特征，是实现虚拟存储器的最重要的目标。虚拟性是以多次性和对换性为基础，多次性和对换性是建立在离散安排的基础上。2、虚拟存储器的特征5.1.3虚拟存储器的实现方法实现虚拟存储的典型过程虚拟存储器管理的技术支持必需有相应的硬件支持，用以实现虚拟分页和虚拟分段存储管理；操作系统必需供应相应的软件支持，管理页或段在内存和外存之间的移动。在简洁分页基础上，增加了恳求调页功能、页面置换功能。置换时以页面为单位进行系统供应的硬件支持：恳求分页的页表机制；缺页中断机构；地址变换机构。实现恳求分页的软件：恳求调页软件页面置换软件1、恳求分页系统在分段的基础上，增加了恳求调段功能、分段置换功能置换时以段为单位进行系统供应的硬件支持：恳求分段的段表机制；缺段中断机构；地址变换机构。实现恳求分段的软件：恳求调段软件段置换软件2、恳求分段系统5.2恳求分页存储管理方式5.2恳求分页存储管理方式建立在基本分页存储管理之上，是目前比较常用的一种虚拟存储管理技术5.2.1恳求分页中的硬件支持1、恳求页表机制在恳求分页系统中所须要的主要数据结构是恳求页表。作用：将用户地址空间中的逻辑地址变换为内存空间的物理地址。恳求分页系统中的每个页表项如下图所示：页号物理块号状态位P访问字段A修改位M外存地址指示该页是否已调入内存记录本页在一段时间内被访问的次数，或记录本页最近已有多长时间未被访问，供选择换出页面时参考该页在调入内存后是否被修改过，供置换页面时参考指出该页在外存上的地址，供调入该页时参考2、缺页中断机构缺页中断机构与一般中断相同的处理步骤：爱护CPU环境、分析中断缘由、转入中断处理程序进行处理、复原CPU环境等几个步骤。缺页中断和一般的中断相比有如下区分：1）缺页中断在指令执行期间产生和处理中断信号，而一般中断在一条指令执行完后检查和处理中断信号；2）缺页中断返回到该指令的起先重新执行该指令，而一般中断返回到该指令的下一条指令执行；3）一条指令在执行期间，可能产生多次缺页中断。2.缺页中断机构图5-1涉及6次缺页中断的指令对硬件的要求：系统中的硬件机构应能够保存多次中断时的状态，并保证最终能够返回到中断前产生缺页中断的指令处，接着执行。图5-2恳求分页中的地址变换过程3、地址变换机构5.2.2恳求分页中的内存安排页面安排原则缺页中断、I/O中断频繁会降低运行效率，因此应尽可能削减缺页中断的次数。为进程安排物理块时要考虑的问题：保证进程正常运行所须要的最少物理块；为进程安排的物理块数目是固定的还是可变的为进程安排物理块数是实行平均安排算法，还是依据进程的大小比例予以安排。是指能保证进程正常运行所需最小物理块数。当系统为进程安排的物理块数少于此值时，进程将无法运行。每个进程的最小页框数是由计算机结构体系所定义的，最大数是由有效的物理内存所定义的。PDP-11的移动指令包括多个字，因此指令本身可能会跨2页。另外，它的两个操作数可能是间接引用，所以总共须要6个物理块。IBM370MVC指令。因为指令是从存储器地址到存储器地址，须要花费6个字节，并且会跨2个页面。要移动的字符块和将要移至的区域也都会跨2个页面。这种状况就要求有6个页框。1、最小物理块数的确定安排策略：固定和可变安排策略。置换策略：全局置换和局部置换。三种适用的内存安排策略：固定安排局部置换(FixedAllocation,LocalReplacement)可变安排全局置换(VariableAllocation,GlobalReplacement)可变安排局部置换(VariableAllocation,LocalReplacement)2、内存安排策略固定安排局部置换固定安排：为每个进程安排固定数目的物理块，整个运行期间不再变更。局部置换：假如进程在运行中发觉缺页，则只能从在内存中安排给该进程的固定物理块中选出一页换出，然后再调入一页。难点：为每个进程安排多少物理块难以确定太少，频繁缺页中断，降低系统吞吐量。太多，内存驻留进程削减，可能造成资源空闲，而且实现进程对换时，会花费更多的时间。2、内存安排策略可变安排全局置换（易于实现）可变安排：先为系统中的每个进程安排确定数目的物理块，在进程运行期间可以适当增减，而OS自身也保持一个空闲物理块队列。全局置换：当某进程发觉缺页，由系统从空闲的物理块队列中，取出一物理块安排该进程，并将欲调入的缺页装入其中。当空闲物理块用完时，OS从内存中任选一页调出（随意进程）。2、内存安排策略可变安排局部置换依据进程的类型或程序员的要求，为每个进程安排确定数目的物理块。当某进程发生缺页时，只允许从该进程在内存的页面中选择一页换出，这样就不会影响其它进程的运行。假如进程在运行中频繁地发生缺页中断，则系统再为该进程安排附加的物理块；反之，若一个进程在运行中缺页频率低，则此时适当削减安排给该进程的物理块。2、内存安排策略平均安排算法：物理块平均安排给各进程；缺点：未考虑到进程本身的大小，不公允。按比例安排算法：按进程大小的比例安排物理块；n为系统内的进程数；Si为i进程的页面数；m为可用的物理块总数；i进程能分到的物理块数为bi考虑优先权的安排算法：依据作业的重要性、紧迫性进行安排。一般将可供安排的物理块分为两部分：一部分按比例安排；另一部分按优先权适当增加份额。在重要的实时系统中，则可能是完全按优先级为各进程安排物理块。3、物理块安排算法5.2.3页面调入策略应解决从何时调入页面、从何处调入页面以及如何调入的问题！1、何时调入页面预调页策略：依据空间局部性，将不久之后便会被访问的程序或数据所在的页面，预先调入内存。特点：预调页的成功率仅有50%。主要用于进程的首次调入。恳求调页策略：进程在运行时，发觉其所访问的程序页面不在内存，恳求系统将所需页面调入内存。特点：系统开销大；易实现。虚拟存储器大多接受此策略。2、从何处调入页面

系统有足够的存储空间，这时可以全部从对换区调入所需页面，以提高调页的速度。系统缺少足够的对换区空间，这时凡是不会被修改的文件，都干脆从文件区调入；但对于那些可能被修改的部分，在将它们换出时，便须调到对换区，以后须要时再从对换区调入。UNIX方式，凡是未运行过的页，都应从文件区调入。对于曾经运行过而又被换出的页面，从对换区调入。缺页中断处理程序通过查找页表，得到该页所在外存的物理块号。假如此时内存空闲，能容纳新页，则启动磁盘I/O将所缺之页调入内存，然后修改页表。假如内存已满，则须先依据某种置换算法，从内存中选出一页准备换出；假如该页未被修改过，可不必将页写入磁盘；但假如该页已被修改，则必需将它重新写入磁盘，然后再将缺页调入内存，并修改页表中的相应表项，再将此页表项写入快表中。据修改后的页表形成去访问数据的物理地址。3、页面调入过程衡量指标——缺页率f假定作业p共计n页，系统安排给它的主存块为m(m<=n)。假如作业p在运行中成功访问页面的次数为S（所访问的页面在主存中），不成功的访问次数为F，则总的访问次数为：A=S+Ff=F/A影响缺页中断率的因素：页面大小、进程所安排物理块的数目、页面替换算法、程序固有特性缺页中断处理时间：t=β×ta+(1-β)×tb其中被置换的页面被修改的概率为β，缺页中断处理时间为ta，被置换页面没有被修改的缺页中断时间为tb。4、缺页率5.3页面置换算法5.3页面置换算法在进程运行过程中，当所要访问的页面不在内存时，则应将它调入内存。若此时内存已无空闲空间，则应选择一页调出。将哪个页面调出，则须依据确定的算法来确定。功能：须要调入页面时，选择内存中哪个物理页面被置换，称为replacementpolicy。不适当的算法可能会导致进程发生“抖动”。抖动：刚被换出的页面很快又要被访问，须要重新调入，此时又须要再选一页调出；而此刚被调出的页很快又被访问，又需将它调入，如此频繁地更换页面，以致一个进程在运行中把大部分时间都花费在页面置换上，则称该进程发生了“抖动”。5.3页面置换算法目标：把将来不再运用的或短期内较少运用的页面调出，通常只能在局部性原理指导下依据过去的统计数据进行预料；常用的页面置换算法最佳置换算法(Optimal,OPT)先进先出算法(FirstInFirstOut,FIFO)近期最久未用过算法（LeastRecentlyUsed,LRU）CLOCK置换算法（NotRecentlyUsed,NRU）页面缓冲算法（PageBufferingAlgorithm,PBA）近期最少运用算法(LeastFrequentlyUsed,LFU)5.3.1最佳置换算法和先进先出置换算法1、最佳置换算法（OPT）方法：依据将来运用状况将将来的近期里不用的页替换出去。实现：确定要替换的时刻t。找出主存中每个页将来要用到的时刻ti。ti-t最大的页将被替换。特点：命中率高，但难于实现（必需运行一遍，才能知道将来的时刻ti），是志向算法，用于评价其它替换算法。页面

引用

7

0

1

2

0

3

0

4

2

3

0

3

2

1

2

0

1

7

0

1

7

7

7

2

2

2

2

2

7

0

0

0

0

4

0

0

0

物

理

块

1

1

3

3

3

1

1

缺页

x

x

x

x

x

x

x

x

x

置换

√

√

√

√

√

√

发生了6次页面置换，9次缺页中断，总访问次数20次，缺页率9/20＝45％

。1、最佳置换算法（OPT）图5-3利用最佳页面置换算法时的置换图方法：最早装入主存的页作为被替换的页，即选择在内存中驻留时间最久的页面予以淘汰。实现：只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总可以指向最老的页面。特点：利用历史信息，但不反映程序的局部性（最先进入的页可能是现在常常运用的页）2、先进先出(FIFO)页面置换算法

发生了12次页面置换，15次缺页中断，总访问次数20次，缺页率15/20＝75％

。2、先进先出(FIFO)页面置换算法

页面引用

7

0

1

2

0

3

0

4

2

3

0

3

2

1

2

0

1

7

0

1

7

7

7

2

2

2

4

4

4

0

0

0

7

7

7

0

0

0

3

3

3

2

2

2

1

1

1

0

0

物理块

1

1

1

0

0

0

3

3

3

2

2

2

1

缺页

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

图5-4利用FIFO置换算法时的置换图5.3.2最近最久未运用和最少运用置换算法方法：近期最久未访问过的页作为被替换的页实现：赐予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经验的时间t，当须淘汰一个页面时，选择现有页面中其t值最大的页面予以淘汰。特点：计数器硬件较少，主存页面表可由软硬件实现修改，依据“历史”预料“将来”。1、LRU(LeastRecentlyUsed)置换算法的描述1、LRU(LeastRecentlyUsed)置换算法的描述7

7

7

2

2

4

4

4

0

1

1

1

0

0

0

0

0

0

3

3

3

0

0

物理块

1

1

3

3

2

2

2

2

2

7

缺页

x

x

x

x

x

x

x

x

x

x

x

x

页面引用

7

0

1

2

0

3

0

4

2

3

0

3

2

1

2

0

1

7

0

1

发生了9次页面置换，12次缺页中断，总访问次数20次，缺页率12/20＝60％

。图5-5利用LRU页面置换算法时的置换图LRU硬件机构如下：每个页面设立移位寄存器：被访问时左边最高位置1，定期右移并且最高位补0，于是寄存器数值最小的是最久未运用页面。一个特殊的栈：把被访问的页面移到栈顶，于是栈底的是最久未运用页面。2、LRU置换算法的硬件支持图5-6某进程具有8个页面时的LRU访问状况2233222311235512225144255542图5-7用栈保存当前运用页面时栈的变更状况335422355523225322323223123152512251425452543354235253522352×××××××选择到当前时间为止被访问次数最少的页面被置换；每页设置移位寄存器，每当页面被访问时，将该移位寄存器的最高位置1，再每隔确定时间右移一次；发生缺页中断时，淘汰最小的页面。这种算法不能真正反映出页面的运用状况，因为在每一时间间隔内，只是用寄存器的一位来记录页面的运用状况，在该时间间隔内，对某页访问一次和访问1000次是完全等效的。3、最少运用(LFU：LeastFrequentlyUsed)置换算法5.3.3Clock置换算法1、简洁的Clock置换算法每页设置一位访问位，若该页被访问则其访问位被置1；内存中全部页面都通过链接指针链接成一个循环队列，置换时接受一个指针，从当前指针位置起先按地址先后检查各页，找寻访问位为0的页面作为被置换页；指针经过的访问位为1的页都将其访问位置0，最终指针停留在被置换页的下一个页。1、简洁的Clock置换算法图5-8简洁Clock置换算法的流程入口查询指针前进一步，指向下一个表目选择该页面淘汰返回页面运用位=0？置页面运用位=0NY1、简洁的Clock置换算法1、简洁的Clock置换算法在将一个页面换出时，对于修改过的页面在换出时所付出的开销将比未修改过的页面开销大。在改进型Clock算法中，它既考虑到页面的运用状况，又考虑页面是否被修改过。即选择换出页面时，既要是未运用过的页面，又要是未修改过的页面，把同时满足两条件的页面作为首选淘汰页。访问位A和修改位M的四种组合状况：1类（A=0，M=0）：表示该页最近既未被访问，又未被修改，是最佳淘汰页2类（A=0，M=1）：表示该页最近未被访问，但已被修改，并不是很好的淘汰页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页面缓冲算法页面置换算法写回磁盘的频率建立一个已修改换出页面的链表，接受集中写回的方式读入内存的频率修改后未写回磁盘的页面，可以干脆从已修改换出页面链表中获得1、影响页面换进换出效率的若干因素2、页面缓冲算法(PBA：PageBufferingAlgorithm)内存安排策略：可变安排局部置换被置换页面的选择和处理：用FIFO算法选择被置换页，把被置换的页面放入两个链表之一。假如页面未被修改，就将其归入到空闲页面链表的末尾；否则将其归入到已修改页面链表。PBA算法的特点：显著降低了页面换进、换出的频率，削减磁盘I/O次数；置换策略简洁，无须硬件支持，实现简洁。3、访问内存的有效时间恳求分布管理方式的内存有效访问时间：被访问的页在内存中，且其对应的页表项在快表中EAT=λ+t被访问的页在内存中，且其对应的页表项不在快表中EAT=2(λ+t)被访问的页不在内存中EAT=ε+2(λ+t)考虑快表的命中率和缺页率EAT=λ+a×t+(1-a)×[t+f×(ε+λ+t)+(1-f)×(λ+t)]其中：λ为查找快表的时间；t为访问实际物理地址所需的时间；ε为缺页中断处理时间；a为快表命中率；f为缺页率。5.4“抖动”与工作集5.4.1多道程序度与“抖动”1、多道程序度与处理机利用率图5-9处理机的利用率产生抖动的缘由：同时在系统中运行的进程太多，由此安排给每一个进程的物理块太少，不能满足进程正常运行的基本要求，致使每个进程在运行时，频繁地出现缺页。这种常见的换进换出的活动被称为抖动。假如一个进程花费在页面置换的时间多于执行时间，就是抖动。2、产生“抖动”的缘由5.4.2工作集1、工作集的基本概念进程发生缺页率的时间间隔与进程获得的物理块数有关。工作集理论：1968年由Denning提出并推广理论基础：程序运行时的局部性原理现象：程序在运行期间，对页面的访问是不匀整的，在一段时间内仅局限于较少的页面，在另一段时间内，又可能局限于另一些较少的页面进行访问。2、工作集的定义工作集：是指在某段时间间隔里，进程实际所要访问页面的集合。工作集的产生：属于预调页策略，用程序过去某段时间内的行为作为程序在将来某段时间内行为的近似。进程在时间t的工作集记作w(t,Δ)工作集的定义：进程在时间间隔（t-Δ,t）中引用页面的集合变量Δ为工作集的“窗口尺寸”。假定Δ=105.4.3“抖动”的预防方法将“抖动”造成的影响限制在较小的范围效果不佳，“抖动”进程会延长其他进程缺页的中断的处理时间确定造成处理机利用率低的缘由多道度不够内存中安排给已有作业的物理块数不够1、接受局部置换策略2、把工作集算法融入到处理机调度中L为缺页之间的平均时间；S为平均缺页服务时间L>>S，表示很少发生缺页L<S，表示频繁发生缺页L≈S，表示磁盘与处理机均能达到它们的最大利用率当多道程序度偏高，影响到处理机的利用率，则应选择挂起某些当前活动的进程，将它们对换至外存。首先选择优先级最低的进程其次选择优先级较低的进程再选择并不特别重要、但却较大的进程选择剩余执行时间最多的进程……3、利用“L=S”准则调整缺页率4、选择暂停的进程5.5恳求分段存储管理方式恳求分段式管理须要恳求段表机制、缺段中断机构以及地址变换机构。1、恳求段表机制恳求段表是恳求分段管理方式的主要数据结构。恳求分段的段表项如图所示。5.5.1恳求分段中的硬件支持段名段长段基址存取方式访问字段A修改字段M存在位P增补位外存始址在恳求分段系统中，接受的是恳求调段策略。进程访问的段不在内存，缺段中断机构产生一缺段中断信号，进入OS后由缺段中断处理程序将所缺的段调入内存。2、缺段中断机构

图5-12恳求分段系统中的中断