《第10章虚拟内存ch10虚拟内存》由会员分享，可在线阅读，更多相关《第10章虚拟内存ch10虚拟内存（44页珍藏版）》请在金锄头文库上搜索。
1、操作系统,授课教师：李治军,Operating System,lizhijun_ 综合楼404室,第10章 虚拟内存,Chapter 10: Virtual Memory,内存管理视图,cs:ip,逻辑地址,用户眼里的内存!,cs:ip,逻辑地址,1个4GB(很大)的地址空间,用户可随意使用该地址空间，就象单独拥有4G内存,该地址空间就被称为“虚拟内存”,这个地址空间怎么映射到物理内存，用户全然不知,必须映射，否则不能用!,虚拟内存的优点,优点1: 地址空间物理内存,用户可以编写比内存大的程序,4G空间可以使用，简化编程,优点2: 部分程序放入物理内存,内存中可以放更多进程，并发度好，效率高,
2、将需要的部分放入内存，有些用不到的部分从来不放入内存，内存利用率高,如一些处理异常的代码!,程序开始执行、响应时间等更快,如何实现虚拟内存!,从段页式内存管理开始,段号+偏移(cs:ip),逻辑地址,偏移,物理地址,物理页号,线性地址,部分逻辑地址对应段表项，发现缺段后调入,部分线性地址对应页表项，发现缺页后调入,分页易于硬件实现、对用户透明，适合请求调入,请求调页!,虚拟内存中的页面映射关系,部分线性地址(逻辑页)对应物理页，那其它页呢?,请求调页过程,当访问没有映射的线性地址时,load addr,页错误处理程序,但完成这个过程很费时间(有时候一条指令会引起几次调页)!,显然是一个很好理解
3、的过程,请求调页的性能分析,分析的背景: 又一个计算机基本特征!,决定了请求调页是否可用,请求调页时的有效访问时间,有效访问时间=(1-p)ma+p调页时间,100(1-p)+10000000p= 100+9999900p 110 p0.000001,缺页率(页错误率)应该很小: 1/105,为什么请求调页仍是可行的?,分配给一个进程的物理页框数应该足够多!,页面应该足够大!,这又违背了分页和请求调页的原则，又需要折衷!,如何设计这些参数? 再从计算机的基本特征开始!,实践性很强的学科怎么学?,90/10原则! 90%的程序访问10%的地址!,页面4K，调入一页后许多指令不出现页错误,这些参数
4、从实践中获得!,请求调页的具体实现细节,(1): load addr，而addr没有映射到物理内存,物理内存,根据addr查页表(MMU)，页表项的P位为0，引起缺页中断(page fault),(2): 设置“缺页中断”即可,(3): “缺页中断处理程序”需要读磁盘,(4): 选一个空闲页框,学过磁盘处理后自然就明白了!,(5): 修改页表,(6): 重新开始指令,如何重新开始指令?,在指令执行过程中出现页错误,add r1, r2, r3 mov +(sp), (r2),显然这一切应该对用户透明! 需要一点硬件支持,Fault: epc = 0xffdd0,页错误处理程序,jmp 0xff
5、dd0,0xffdcc: add r1,r2,r3 0xffdd0: ld r1, 0(sp),如何选一个空闲页框?,没有空闲页框怎么办? 分配的页框数是有限的,页面淘汰(置换),需要选择一页淘汰,有多种淘汰选择。如果某页刚淘汰出去马上又要用,FIFO，最容易想到，怎么评价?,有没有最优的淘汰方法，MIN,最优淘汰方法能不能实现，能否借鉴思想，LRU,再来学习几种经典方法，它可以用在许多需要淘汰(置换)的场合,FIFO页面置换,淘汰算法: FIFO,一实例: 分配了3个页框(frame)，页面引用序列为 A B C A B D A D B C B,B,C,B,D,A,D,B,A,C,B,A,评
6、价准则: 缺页次数；本实例，FIFO导致7次缺页,D换A不太合适!,选A、B、C中最远将使用的,MIN页面置换,MIN算法: 选最远将使用的页淘汰。是一种最优的方案，可以证明缺页数最小!,继续上面的实例: (3frame)A B C A B D A D B C B,B,C,B,D,A,D,B,A,C,B,A,本实例，MIN导致5次缺页,可惜，MIN需要知道将来发生的事 怎么办?,LRU页面置换,用过去的历史预测将来。LRU算法: 选最近最长一段时间没有使用的页淘汰(最近最少使用)。,继续上面的实例: (3frame)A B C A B D A D B C B,B,C,B,D,A,D,B,A,C
7、,B,A,本实例，LRU也导致5次缺页,LRU是公认的很好的页置换算法，怎么实现?,和MIN完全一样!,LRU的准确实现,每页维护一个时间戳(time stamp),继续上面的实例: (3frame)A B C A B D A D B C B,B,C,B,D,A,D,B,A,C,B,A,time stamp,选具有最小时间戳的页!,选A淘汰!,每次地址访问都需要修改时间戳，需维护一个全局时钟(该时钟溢出怎么办?)，需要找到最小值 这样的实现代价较大 几乎没人用,LRU准确实现之页码栈,维护一个页码栈,继续上面的实例: (3frame)A B C A B D A D B C B,B,C,B,D,
8、A,D,B,A,C,B,A,页码栈,每次地址访问都需要修改栈(修改10次左右栈指针) 实现代价仍然较大 LRU准确实现用的少,选栈底页淘汰!,LRU近似实现 将时间计数变为是和否,每个页加一个引用位(reference bit),每次访问一页时，硬件自动设置该位,选择淘汰页：扫描该位，是1时清0，并继续扫描；是0时淘汰该页,再给一次机会(Second Chance Replacement),组织成循环队列较合适！,SCR这一实现方法称为Clock Algorithm,Clock算法实例,继续上面的实例: (3frame)A B C A B D A D B C B,B,C,B,D,A,D,B,A
9、,C,B,A,本实例，Clock算法也导致5次缺页,Clock算法是公认的很好的近似LRU的算法,引用位！,扫描指针！,Clock算法分析的改造,如果缺页很少，会?,所有的R=1,hand scan一圈后淘汰当前页，将调入页 插入hand位置，hand前移一位,退化为FIFO!,原因: 记录了太长的历史信息 怎么办?,定时清除R位,再来一个扫描指针!,用来清除R位，移动速度要快!,用来选择淘汰页，移动速度慢!,更像Clock吧!,清除R位的hand如何定速度，若太快?,又成了FIFO!,来看一个实际例子,Solaris下键入命令: vmstat -s,free?,14157550 pages
10、examined by clock daemon 13065972 pages freed by clock daemon 110 revolutions of clock hand # since boot!,原理: 第2条指针不是在缺页时工作，而是定期执行，检查引用位，将为0的页释放到空闲链表中。,最近一段时间没引用,指针扫描速度如何定?,一个定时调度的内核任务,继续这个实际例子,设定值吗?,在slowscan和fastscan之间调整,系统负载并不固定,空闲内存比率高于lotsfree时，扫描速度设为slowscan,并往大调,稳定在这个区间上!,清除指针和扫描指针的距离: handsp
11、read参数,一个夹角,scanrate=100, handspread=1000 两针间隔=10s,两种置换策略,Solaris换页daemon中的freelist,D,全局置换 局部置换,想一想前面的例子!,只能淘汰进程自己的页面,可以淘汰别的进程的页面,全局置换: 实现简单,但全局置换不能实现公平、保护: 一个经过巧妙优化的程序里会出现大量goto，则,局部置换需要考虑的关键问题,给进程分配多少页框(帧frame),分配的多，请求调页的意义就没了!,一定要少?,至少是多少? 可执行任意一条指令，如mov a, b,是不是就选该下界值?,最坏情况需要6帧!,来看一个实例: 操作系统监视CP
12、U使用率，发现CPU使用率太低时，向系统载入新进程。,会发生什么?,CPU利用率急剧下降的原因,系统内进程增多 每个进程的缺页率增大 缺页率增大到一定程度，进程总等待调页完成 CPU利用率降低 进程进一步增多，缺页率更大 ,此时: 进程调入一页，需将一页淘汰出去，刚淘汰出去的页马上要需要调入，就这样,称这一现象为颠簸(thrashing),显然，防止的根本手段给进程分配足够多的帧,问题时怎么确定进程需要多少帧才能不颠簸?,工作集模型,任何计算都需要一个模型! 要确定进程所需的帧数该依靠什么信息呢?,从请求调页的可行性开始!,局部性现象!,只要分配的帧空间能覆盖整个局部就不会出现太多的缺页!,工
13、作集模型就用来计算一个局部的宽度(帧数),工作集定义,进程Pi工作集合WSi = 在最近的时间内访问的页面集合，其中为工作集窗口,一个例子: 定义为10个页引用数!,WSi的用法: (1)计算D= |WSi|; (2)如果Dm，则选择一个进程换出; (3)如果Dm，可以选一个进程换入。,选择哪个进程换入、换出，中程调度,工作集的计算,根据定义，每次引用都重新计算WS，会很低效,该定为多少? 太小盖不住一个局部，太大会包含多个局部。,试试看? 但系统有时并不敏感,提出了基于页错误率的帧分配方案,定期扫描+定期计算(在定时中断中),是近似计算,一种方案: 每个页增加一个属性idle time()。
14、扫描: 如果访问位R为1，=0，R=0; 否则+=CPU执行时间。 计算WS： 在WS中。,UNIX, 扫描周期:几秒.计算周期:几分钟.,基于页错误率的帧分配,页错误率(PFF) = 页错误/指令执行条数,如果PFF上限，增加分配帧数,往往是PFF和WS互相配合,如果没有空闲帧，则换出进程,此种方法简单直接，在处理颠簸时常用。,那WS呢?,有趣的是，帧数越多，PPF并不一定下降,但现代OS并不十分重视颠簸现象，因为CPU更快了，进程很快exit；内存更大了，局部的变化不大,Belady异常,来看一个例子!,引用序列1，2，3，4，1，2，5，1，2，3，4，5,FIFO页置换,3frame,
15、9faults,4frame,10faults,什么样的页置换没有Belady异常,看个模型!,引用序列1，2，3，4，1，2，5，1，2，3，4，5,结论：栈式算法无Belady异常，LRU属于栈式算法!,LRU栈实现,m是分配的帧数,特征: M(m, r)M(m+1,r)，如5,2,15,2,1,4 (m=3) 满足这一特征的算法称为栈式算法!,看看FIFO,一些技术,预调页: 页可以不同自己的页错误而调入,进程创建(换入)时一次调入多个页(可由WS确定),页面尺寸: 该定为多少?受许多因素影响!,减少碎片，页应该小,程序结构:,for(j128)for(i128)Aij=0; /页大小1
16、28,操作系统难吗?不难吗? 难吗?不难吗?,启动快，但可能有页用不着!,降低页错误，页应大,按行存储,128*128faults,for(i128)for(j128)Aij=0;,128faults,整理一下前面的学习,温故而知新,虚拟内存的基本思想,将进程的一部分(不是全部)放进内存,其他部分放在磁盘,需要的时候调入: 请求调页,why?,请求调页的基本思想,what?,当MMU发现页不在内存时，中断CPU,CPU处理此中断，找到一个空闲页框,CPU将磁盘上的页读入到该页框,如果没有空闲页框需要置换某页(LRU),how?,一个实际系统的请求调页!,Linux的请求调页,从哪里开始这个故事?,从缺页中断开始,dpl,Linux处理中断page fault,测试标志P,压入参数,页错误线性地址,取出错误码到e
