虚拟内存41878.pptx
第十章第十章虚拟内存虚拟内存110.1背景背景F第九章所介绍的内存管理算法都是基于一个基第九章所介绍的内存管理算法都是基于一个基本要求：执行指令必须在物理内存中。执行前本要求：执行指令必须在物理内存中。执行前将整个进程放在内存中。将整个进程放在内存中。连续内存分配连续内存分配分页分页分段分段F覆盖是个例外，但需要程序员特别小心。覆盖是个例外，但需要程序员特别小心。必须设计和编写覆盖结构必须设计和编写覆盖结构2背景背景F在许多情况下并不需要将整个程序放到内存中在许多情况下并不需要将整个程序放到内存中处理异常错误条件的代码处理异常错误条件的代码数组、链表和表通常分配了比实际所需要更多的内数组、链表和表通常分配了比实际所需要更多的内存。存。程序的某些选项或特点可能很少使用。即使需要完程序的某些选项或特点可能很少使用。即使需要完整程序，也并不是在某时刻同时需要整程序，也并不是在某时刻同时需要(与覆盖相似与覆盖相似)3背景背景F结论结论:如果只保存部分程序在内存中如果只保存部分程序在内存中可运行一个比物理内存大的多的程序可运行一个比物理内存大的多的程序可以有更多程序同时运行可以有更多程序同时运行程序运行更快程序运行更快4背景背景F虚拟内存虚拟内存物理内存和用户逻辑内存的区分物理内存和用户逻辑内存的区分只有部分运行的程序需要在内存中只有部分运行的程序需要在内存中因此，逻辑地址空间能够比物理地址空间大因此，逻辑地址空间能够比物理地址空间大允许若干个进程共享地址空间允许若干个进程共享地址空间允许更多有效进程创建允许更多有效进程创建5虚拟内存大于物理内存的示意图虚拟内存大于物理内存的示意图6背景背景虚拟内存能够通过以下手段来执行：虚拟内存能够通过以下手段来执行：请求页面调度（请求页面调度（Demandpaging）u用户观点是分段，而操作系统可以通过请求页面调度实现这用户观点是分段，而操作系统可以通过请求页面调度实现这一观点一观点u类似于分页系统加上交换。交换程序对整个进程操作，调页类似于分页系统加上交换。交换程序对整个进程操作，调页程序只对进程的单个页进行操作程序只对进程的单个页进行操作请求分段调度（请求分段调度（Demandsegmentation）7分页的内存与邻接的磁盘空间之间的传递分页的内存与邻接的磁盘空间之间的传递8请求页面调度请求页面调度F只有在一个页需要的时候才把它换入内存只有在一个页需要的时候才把它换入内存.需要很少的需要很少的I/O需要很少的内存需要很少的内存快速响应快速响应多用户多用户F需要页需要页查阅此页查阅此页无效的访问无效的访问中止中止不在内存不在内存换入内存换入内存9有效有效-无效位无效位F在每一个页表的表项有一个有效在每一个页表的表项有一个有效-无效位相关联无效位相关联有效：相关的页既合法且也在内存中有效：相关的页既合法且也在内存中无效：相关的页不在进程的逻辑地址空间内或者有效但是在磁盘上无效：相关的页不在进程的逻辑地址空间内或者有效但是在磁盘上有效有效-无效位无效位iiiiviv帧帧页表页表v10当有些页不在内存中时的页表当有些页不在内存中时的页表11页错误（缺页）页错误（缺页）F如果只访问真正需要的并已在内存中的页，那么如果只访问真正需要的并已在内存中的页，那么进程就可如同所有页都已调入一样正常运行。进程就可如同所有页都已调入一样正常运行。F当进程试图访问那些尚未调入到内存的页时当进程试图访问那些尚未调入到内存的页时页页错误陷阱（缺页）错误陷阱（缺页）FOS查看页表来决定查看页表来决定无效引用无效引用终止终止仅仅不在内存仅仅不在内存u找一个空闲帧找一个空闲帧u将需要的页调入空闲帧将需要的页调入空闲帧u重置页表，有效位为重置页表，有效位为1u重启指令重启指令12处理页错误的步骤处理页错误的步骤13F纯粹请求页面调度纯粹请求页面调度：只有在需要时才将页调入内存所有的页都不在内存中，就开始执行进程，立即出现页错误，当页调入内存时，进程继续执行，并不断出现页错误直到所有所需的页均在内存中。14请求页面调度的性能请求页面调度的性能F页错误的概率（缺页率）页错误的概率（缺页率）0 p 1.0如果如果p=0，没有缺页没有缺页如果如果p=1,每次访问都缺页每次访问都缺页F有效访问时间（有效访问时间（EffectiveAccessTime，EAT)EAT=(1p)*内存访问时间内存访问时间+p*页错误时间页错误时间页错误时间主要包含三个方面：页错误时间主要包含三个方面：1、处理页错误中断、处理页错误中断2、读入页、读入页3、重新启动进程、重新启动进程15性能举例性能举例F内存访问时间内存访问时间=100nsF平均页错误处理时间平均页错误处理时间=25msF有效访问时间有效访问时间EAT=(1p)*100+p*25,000,000=100+24,999,900*p性能与缺页率直接有关性能与缺页率直接有关如果需要性能降低不超过如果需要性能降低不超过10%110100+25000000p1025000000pp降低缺页率降低缺页率21页置换算法页置换算法F需要一个最小的缺页率需要一个最小的缺页率F通过运行一个内存访问的特殊序列（访问序列）通过运行一个内存访问的特殊序列（访问序列），计算这个序列的缺页次数，计算这个序列的缺页次数引用串：只考虑页码，任何紧跟着的引用不会出错引用串：只考虑页码，任何紧跟着的引用不会出错22F内存访问地址顺序内存访问地址顺序:0100,0432,0101,0612,0102,0103,0104,0101,0611,0102,0103,0104,0101,0610,0102,0103,0104,0101,0609,0102,0105F页大小页大小100B，页码序列页码序列:1,4,1,6,1,1,1,1,6,1,1,1,1,6,1,1,1,1,6,1,1F引用串引用串:1,4,1,6,1,6,1,6,1,6,123理想的缺页与帧数量关系图理想的缺页与帧数量关系图F给定引用串给定引用串:1,4,1,6,1,6,1,6,1,6,1F如果有三帧如果有三帧:3次缺页次缺页F如果只有一帧如果只有一帧:11次缺页次缺页24FIFO页置换页置换FFIFO算法算法:可以创建一个可以创建一个FIFO队列来管理内存中的所有页队列来管理内存中的所有页调入页时，将它加到队列的尾部调入页时，将它加到队列的尾部当必须置换一页时，将选择最旧的页当必须置换一页时，将选择最旧的页总共总共15次缺页次缺页25Belady异常异常F引用串引用串:1,2,3,4,1,2,5,1,2,3,4,5F3帧帧F4帧帧FFIFO置换算法置换算法Belady异常异常期望期望:增加帧数增加帧数降低缺页率降低缺页率1231234125349 page faults1231235124510 page faults44326存在存在Belady异常的异常的FIFO置换缺页曲线图置换缺页曲线图27最优页置换最优页置换F被置换的页将是最长时间不被使用的页被置换的页将是最长时间不被使用的页F很难实现，因为需要引用串的未来知识很难实现，因为需要引用串的未来知识F4帧的例子帧的例子1,2,3,4,1,2,5,1,2,3,4,5最优页置换的作用：用来衡量你的算法的效率最优页置换的作用：用来衡量你的算法的效率12346 page faults4528最优页置换total9pagefaults29LRU页置换页置换FLRU置换为每个页记录该页最后的使用置换为每个页记录该页最后的使用时间时间F当必须进行页置换时，当必须进行页置换时，LRU选择最近最选择最近最长未被使用的页。长未被使用的页。30LRU页置换F引用串引用串:1,2,3,4,1,2,5,1,2,3,4,5F计数器的实现计数器的实现每一个页表项每一个页表项有一个计数器，每次页通过这个表项被有一个计数器，每次页通过这个表项被访问，把记录拷贝到计数器中访问，把记录拷贝到计数器中当一个页需要改变是，查看计数器来觉得改变哪一个当一个页需要改变是，查看计数器来觉得改变哪一个页页0123544358 page faults31LRU页置换total12pagefaults32LRU页置换F计数器计数器每个页表项都关联一个使用时间域每个页表项都关联一个使用时间域需要一个逻辑时钟或计数器，对每次内存引用，计需要一个逻辑时钟或计数器，对每次内存引用，计数器都会增加。数器都会增加。每次内存引用时，时钟寄存器的内容都会复制到相每次内存引用时，时钟寄存器的内容都会复制到相应页表项的使用时间域内应页表项的使用时间域内进行页置换时，选择具有最小时间（或者计数器值）进行页置换时，选择具有最小时间（或者计数器值）的页的页F问题问题需要搜索页表需要搜索页表每次内存访问都需要写页表项的使用时间域每次内存访问都需要写页表项的使用时间域上下文切换时需要维护页表上下文切换时需要维护页表需要考虑时钟溢出需要考虑时钟溢出33LRU页置换F栈栈在一个双链表中保留一个记录页数目的栈在一个双链表中保留一个记录页数目的栈F被访问的页被访问的页:u移到栈顶移到栈顶u最坏情况下需要改变最坏情况下需要改变6个指针个指针无需为置换进行查找无需为置换进行查找34用堆栈来记录最近使用的页35LRU近似页置换F引用位引用位每个页都与一个位相关联，初始值位每个页都与一个位相关联，初始值位0当页被访问时，将该页的引用位设为当页被访问时，将该页的引用位设为1如果存在的话置换位为如果存在的话置换位为0的页。然而我们并不知道的页。然而我们并不知道这个置换顺序这个置换顺序F一些通过引用位实现的一些通过引用位实现的LRU近似页置换算法近似页置换算法附加引用位算法附加引用位算法二次机会法二次机会法增强型二次机会法增强型二次机会法36附加引用位算法附加引用位算法F附加引用位算法附加引用位算法在规定时间间隔里（如在规定时间间隔里（如100ms）记录引用位记录引用位操作系统把每个页的引用位转移到其操作系统把每个页的引用位转移到其8bit字字节的高位，而将其它位右移节的高位，而将其它位右移选择具有最小值的页进行置换选择具有最小值的页进行置换37二次机会算法二次机会算法F二次机会算法二次机会算法FIFO+引用位引用位所有帧形成一个循环队列所有帧形成一个循环队列每次内存访问，需将访问页的引用位置每次内存访问，需将访问页的引用位置1检查当前帧检查当前帧u如果引用位为如果引用位为1，则置为，则置为0，并跳到下一帧，并跳到下一帧u如果引用位为如果引用位为0，则置换该页，则置换该页假如某个页被频繁访问，那么它就不会被置换假如某个页被频繁访问，那么它就不会被置换出去出去38二次机会算法二次机会算法39增强型二次机会算法增强型二次机会算法F增强型二次机会算法增强型二次机会算法一个一个FIFO循环队列循环队列引用位引用位修改位修改位F四种类型（引用位，修改位）：四种类型（引用位，修改位）：(0,0)最近没有使用也没有修改过最近没有使用也没有修改过(0,1)最近没有使用但曾经被修改过最近没有使用但曾经被修改过(1,0)最近使用过，但没有被修改过最近使用过，但没有被修改过(1,1)最近使用过并且修改过最近使用过并且修改过F当需要置换时，检查页属于哪一类型当需要置换时，检查页属于哪一类型F置换在最低非空类型中所碰到的页置换在最低非空类型中所碰到的页缺点缺点:需要多次搜索整个循环队列需要多次搜索整个循环队列40基于计数的页置换F用一个计数器记录对每一个页的访问次数。用一个计数器记录对每一个页的访问次数。F最不经常使用页置换算法（最不经常使用页置换算法（LFU）替换具有最小计数的页替换具有最小计数的页定期将计数右移一位，以形成指数衰减的平均定期将计数右移一位，以形成指数衰减的平均使用次数使用次数F最常使用页置换算法最常使用页置换算法(MFU)基于如下理论：具有最小次数的页可能刚刚被基于如下理论：具有最小次数的页可能刚刚被置换进来，并且可能尚未使用。置换进来，并且可能尚未使用。41帧分配F每个进程所需要的最少的页的数目每个进程所需要的最少的页的数目F例子例子:IBM370需要需要6页以处理页以处理MOV指令指令:指令长度为指令长度为6字节，可能跨越字节，可能跨越2页页2页用于处理移动的源页用于处理移动的源2页用于处理移动的目的页用于处理移动的目的F两个主要的分配策略两个主要的分配策略固定分配固定分配优先分配优先分配42分配算法F平均分配例：如果有平均分配例：如果有100个帧，和个帧，和5个进程，则每个进程分个进程，则每个进程分给给20个帧个帧F按比例分配按比例分配根据每个进程的大小来分配根据每个进程的大小来分配43分配算法分配算法F优先级分配：根据优先级而不是大小来使用优先级分配：根据优先级而不是大小来使用比例分配策略比例分配策略F如果进程如果进程Pi产生一个缺页产生一个缺页选择替换其中的一个页帧选择替换其中的一个页帧从一个较低优先级的进程中选择一个页从一个较低优先级的进程中选择一个页面来替换面来替换44全局分配与局部分配全局分配与局部分配F全局置换全局置换进程在所有的帧中选择一进程在所有的帧中选择一个替换页面；一个进程可以从另一个进个替换页面；一个进程可以从另一个进程中获得帧程中获得帧u高优先级进程可以从低优先级进程中选择帧以高优先级进程可以从低优先级进程中选择帧以便置换便置换问题问题:进程不能控制其缺页率进程不能控制其缺页率更好的系统吞吐量更好的系统吞吐量F局部置换局部置换每个进程只从属于它自己的每个进程只从属于它自己的帧中选择帧中选择45颠簸颠簸F如果一个进程没有足够的页，那么缺页率将很如果一个进程没有足够的页，那么缺页率将很高，这将导致高，这将导致CPU利用率低下利用率低下操作系统认为需要增加多道程序设计的道数操作系统认为需要增加多道程序设计的道数系统中将加入一个新的进程系统中将加入一个新的进程FThrashing（颠簸）颠簸）一个进程忙于换入换出页一个进程忙于换入换出页.46颠簸颠簸F工作集合策略检查进程真正需要多少帧工作集合策略检查进程真正需要多少帧F局部模型局部模型进程从一个局部移到另一个局部进程从一个局部移到另一个局部局部可能重叠局部可能重叠F为什么颠簸会发生为什么颠簸会发生 局部局部总的内存总的内存47内存引用模式中的局部性内存引用模式中的局部性48工作集合模型工作集合模型F 工作集合窗口工作集合窗口 检查最近检查最近 个页的引用个页的引用FWSSi进程在进程在ti工作集合工作集合如果如果 太小，它不能包含整个局部太小，它不能包含整个局部如果如果 太大，可能包含多个局部太大，可能包含多个局部.如果如果=包含进程执行所碰到的所有页的集包含进程执行所碰到的所有页的集合合.FD=WSSi 总的帧需求量总的帧需求量F如果如果Dm颠簸颠簸F策略：如果策略：如果Dm,操作系统选择暂停一个进程，换操作系统选择暂停一个进程，换出。出。F防止了颠簸并尽可能提高了多道程序的级别防止了颠簸并尽可能提高了多道程序的级别49工作集合模型工作集合模型50页错误频率页错误频率F另一种控制颠簸的更为直接的方法是设置可接受的缺页另一种控制颠簸的更为直接的方法是设置可接受的缺页率率.如果缺页率太低，回收一些进程的帧如果缺页率太低，回收一些进程的帧.如果缺页率太高，就分给进程一些帧如果缺页率太高，就分给进程一些帧.51其它考虑其它考虑F预约式页面调度：同时将所需要的所有页一起预约式页面调度：同时将所需要的所有页一起调入到内存中调入到内存中F影响页面大小因素影响页面大小因素页表大小：减低页大小页表大小：减低页大小增加页表大小增加页表大小碎片：小页更好利用内存碎片：小页更好利用内存I/O开销：寻道和延迟时间远大于传输时间，开销：寻道和延迟时间远大于传输时间，需要小页需要小页局部：较小页允许每个页更精确的匹配程序局部：较小页允许每个页更精确的匹配程序局部局部52其它考虑其它考虑FTLB范围范围-从从TLB可访问的内存量可访问的内存量FTLB范围范围=(TLB条数条数)*(页大小页大小)F理想地理想地,每进程的工作集存储在每进程的工作集存储在TLB中。否则中。否则有很高的缺页率。有很高的缺页率。F增加页大小。因为不是所有的应用程序都要求增加页大小。因为不是所有的应用程序都要求一个较大的页大小，这可以导致碎片的增加。一个较大的页大小，这可以导致碎片的增加。F提供多种页大小。提供多种页大小。53小结小结F虚拟内存技术允许执行一个进程，它的逻辑地虚拟内存技术允许执行一个进程，它的逻辑地址空间比物理空间大址空间比物理空间大F虚拟内存技术提高了多道程序程度，虚拟内存技术提高了多道程序程度，CPU利用利用率和吞吐量率和吞吐量54小结小结F纯请求页面调度纯请求页面调度备份仓库备份仓库缺页缺页页表页表OS内部帧表内部帧表F缺页率低缺页率低=性能可接受性能可接受55小结小结F页置换算法页置换算法FIFOuBelady异常异常最优最优LRU（最近最少使用）最近最少使用）计数器计数器u最不经常使用最不经常使用(LFU)56小结小结F帧分配策略帧分配策略固定固定(i.e.equalshare)按比例按比例(toprogramsize)优先级优先级F工作集模型工作集模型局部局部F颠簸颠簸如果一个进程工作集未获得足够内存，将引起颠簸如果一个进程工作集未获得足够内存，将引起颠簸57F作业2,4,5,8,11,17,18,2058
