示范之虚拟内存课件

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