虚拟内存

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