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