第六章 存储管理优秀PPT.ppt
《第六章 存储管理优秀PPT.ppt》由会员分享,可在线阅读,更多相关《第六章 存储管理优秀PPT.ppt(67页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、第六章 存储管理第一页,本课件共有67页进程与外存对应关系进程与外存对应关系n界地址界地址n每进程占一组外存连续块;每进程占一组外存连续块;n每进程占二组外存连续块(双对界)。每进程占二组外存连续块(双对界)。n页式页式n内存一页,外存一块。内存一页,外存一块。n段式段式n每段占外存若干连续块。每段占外存若干连续块。n段页式段页式n内存一页,外存一块。内存一页,外存一块。第二页,本课件共有67页6.5 虚拟存储系统虚拟存储系统n无虚拟问题无虚拟问题n不能运行比内存大的程序;不能运行比内存大的程序;n进程全部装入内存,浪费空间(进程活动具有局部进程全部装入内存,浪费空间(进程活动具有局部性性)。
2、n单控制流的进程需要较少部分在内存;单控制流的进程需要较少部分在内存;n多控制流的进程需要较多部分在内存。多控制流的进程需要较多部分在内存。n虚拟存储虚拟存储n进程部分装入内存,部分(或全部)装入外存,运行进程部分装入内存,部分(或全部)装入外存,运行时访问在外存部分动态调入,内存不够淘汰。时访问在外存部分动态调入,内存不够淘汰。第三页,本课件共有67页6.5.1 虚拟页式存储系统虚拟页式存储系统n基本原理基本原理n进程运行前:进程运行前:n全部装入外存,部分装入内存。全部装入外存,部分装入内存。n进程运行时:进程运行时:n访问页不在内存,发生缺页中断,中断处理程序:访问页不在内存,发生缺页中
3、断,中断处理程序:n找到访问页在外存的地址;找到访问页在外存的地址;n在内存找一空闲页面;在内存找一空闲页面;n如没有,按淘汰算法淘汰一个;如没有,按淘汰算法淘汰一个;n如需要,将淘汰页面写回外存,修改页表和总页表;如需要,将淘汰页面写回外存,修改页表和总页表;n读入所需页面(切换进程);读入所需页面(切换进程);n重新启动中断指令。重新启动中断指令。第四页,本课件共有67页对页表的改进:对页表的改进:对快表的改进:对快表的改进:逻辑页号逻辑页号 p .页框号页框号 外存块号外存块号 内外标识内外标识 访问权限访问权限 修改标志修改标志 f b (0,1)r,w,e (0,1).逻辑页号逻辑页
4、号 页框号页框号 访问权限访问权限 修改标志修改标志 p f r,w,e (0,1).第五页,本课件共有67页6.5.1.2 内存页框分配策略(静态策略)内存页框分配策略(静态策略)1.平均分配平均分配 如内存如内存128页,进程页,进程25个,每个进程个,每个进程5个页架个页架 2.按进程按进程长度长度比例分配比例分配 pi共共si个页面;个页面;S=si;内存共;内存共m个页架个页架 ai=(si/S)m 3.按进程按进程优先级优先级比例分配比例分配 4.按进程按进程长度和优先级别长度和优先级别比例分配比例分配 静态策略没有反映:静态策略没有反映:(1)程序结构;程序结构;(2)程序在不同
5、时刻的行为特性。程序在不同时刻的行为特性。第六页,本课件共有67页6.5.1.3 外存块的分配策略外存块的分配策略 1.静态分配静态分配 外存保持进程的全部页面:外存保持进程的全部页面:优点:速度快优点:速度快-淘汰时不必写回淘汰时不必写回(未修改情况未修改情况)缺点:外存浪费缺点:外存浪费 2.动态分配动态分配 外存仅保持进程不在内存的页面:外存仅保持进程不在内存的页面:优点:节省外存优点:节省外存 缺点:速度慢缺点:速度慢-淘汰时必须写回淘汰时必须写回第七页,本课件共有67页6.5.1.4 页面调入时机页面调入时机 1.请调请调(demand paging)upon page fault,
6、发生缺页中断时调入。发生缺页中断时调入。2.预调预调(prepaging)before page fault,将要访问时调入将要访问时调入(根据程序顺序行为,根据程序顺序行为,不一定准)不一定准)预调必须辅以请调。预调必须辅以请调。第八页,本课件共有67页 用于:页淘汰、段淘汰、快表淘汰。用于:页淘汰、段淘汰、快表淘汰。Objective:lowest page-fault rate.1.最佳淘汰算法最佳淘汰算法(OPT-optimal)淘汰将来最长时间以后才用到的。淘汰将来最长时间以后才用到的。效率最高,效率最高,not feasible。6 6 0 0 1 1 2 2 0 0 3 3 0
7、0 4 4 2 2 3 3 0 0 3 3 2 2 1 1 2 2 0 0 1 1 6 6 0 0 1 16 6 6 6 6 6 2 22 22 22 22 26 60 0 0 0 0 00 04 40 00 00 01 1 1 13 33 33 31 11 1 6.5.1.5 淘汰算法淘汰算法(replacement algorithm)第九页,本课件共有67页2.先进先出先进先出(FIFO)淘汰最先调入的。淘汰最先调入的。依据依据:先进入的可能已经使用完毕。先进入的可能已经使用完毕。实现:队列实现:队列 negative case:有些代码和数据可能整个程序运行中用到。有些代码和数据可能整
8、个程序运行中用到。Belady异常异常:例子:例子:1,2,3,4,1,2,5,1,2,3,4,5 内存内存3个物理页面:页故障率个物理页面:页故障率=9/12 内存内存4个物理页面:页故障率个物理页面:页故障率=10/12 第十页,本课件共有67页FIFO淘汰算法淘汰算法(belady异常异常)12 3 4 1 2 5 1 2 3 4511 1 4 4 4 55 52 2 2 1 1 13 33 3 3 2 22 41 2 3 4 1 2 5 1 2 3 4 51 1 1 15 5 5 5 4 42 2 22 1 1 1 1 53 33 3 2 2 2 244 4 4 3 3 3页故障率页故
9、障率=10/12页故障率页故障率=9/12访问序列访问序列:访问序列访问序列:内存页面内存页面:内存页面内存页面:第十一页,本课件共有67页3.使用过最久的先淘汰(使用过最久的先淘汰(LRU)淘汰最近一次访问距当前时间最长的。淘汰最近一次访问距当前时间最长的。Replace page that hasnt been used for the longest period of time.实现:实现:stack 当一页面被访问时当一页面被访问时,从栈中取出压到栈顶从栈中取出压到栈顶,栈底是栈底是:LRU page.例子:例子:reference string:4,7,0,7,1,0,1,2,1,
10、2,7,1,2 2107472104Stack before aStack before b a b第十二页,本课件共有67页nLRU算法6 6 0 0 1 1 2 2 0 0 3 3 0 0 4 4 2 2 3 3 0 0 3 3 2 2 1 1 2 2 0 0 1 1 6 6 0 0 1 16 6 6 6 6 6 2 22 24 4 4 4 4 4 0 01 11 11 10 0 0 0 0 00 00 0 0 0 3 3 3 33 30 00 01 1 1 13 33 3 2 2 2 2 2 22 22 26 6 第十三页,本课件共有67页4.最近不用的先淘汰最近不用的先淘汰(not u
11、sed recently)淘汰最近一段时间未用到的。淘汰最近一段时间未用到的。实现:每页增加一个访问标志,实现:每页增加一个访问标志,访问置访问置1,定时清,定时清0,淘汰时取标志为淘汰时取标志为0的。的。LRU算法的近似:算法的近似:Reference string:2,3,5,6,4,2,5,6,7,5,6,8,标志清标志清0选择淘汰选择淘汰LRU:3NUR:2,3,4任意任意第十四页,本课件共有67页5.最不经常使用的先淘汰最不经常使用的先淘汰(LFU)淘汰使用次数最少的。淘汰使用次数最少的。依据依据:活跃访问页面应有较大的访问次数活跃访问页面应有较大的访问次数.Suffer:(1)前期
12、使用多,但以后不用,难换出;前期使用多,但以后不用,难换出;(2)刚调入的页面,引用少,被换出可能大。刚调入的页面,引用少,被换出可能大。实现:记数器,调入清实现:记数器,调入清0,访问增,访问增1,淘汰选取最小者。,淘汰选取最小者。6.最经常使用的先淘汰最经常使用的先淘汰(MFU)淘汰使用次数最多的。淘汰使用次数最多的。依据依据:使用多的可能已经用完了。使用多的可能已经用完了。Suffer:程序有些成分是在整个程序运行中都使用的。程序有些成分是在整个程序运行中都使用的。第十五页,本课件共有67页7.二次机会二次机会(second chance)n淘汰装入最久且最近未被访问的页面。淘汰装入最久
13、且最近未被访问的页面。n实现时:采用拉链数据结构实现时:采用拉链数据结构。6/13/14/08/05/19/00/01/13/14/08/05/19/00/01/16/04/08/05/19/00/01/16/03/08/05/19/00/01/16/03/02/1第十六页,本课件共有67页8.时钟算法时钟算法(clock algorithm)n将页面组织成环形,有一个指针指向当前位置。每次需要淘将页面组织成环形,有一个指针指向当前位置。每次需要淘汰页面时,从指针所指的页面开始检查。如果当前页面的访汰页面时,从指针所指的页面开始检查。如果当前页面的访问位为问位为0,即从上次检测到目前,该页没有
14、访问过,则将,即从上次检测到目前,该页没有访问过,则将该页替换。如果当前页面的访问位为该页替换。如果当前页面的访问位为1,则将其清,则将其清0,并,并顺时针移动指针到下一个位置。重复上述步骤直至找到一顺时针移动指针到下一个位置。重复上述步骤直至找到一个访问位为个访问位为0的页面。的页面。n可以看出,时钟算法与二次机会算法的淘汰效果是基本可以看出,时钟算法与二次机会算法的淘汰效果是基本相同的,差别在于二者所采用的数据结构不同,二次机相同的,差别在于二者所采用的数据结构不同,二次机会使用的是链表,需要额外存储空间,且摘链入链速度会使用的是链表,需要额外存储空间,且摘链入链速度很慢。而时钟算法可直接
15、利用页表中的引用位,外加一很慢。而时钟算法可直接利用页表中的引用位,外加一个指针,速度快且节省空间。个指针,速度快且节省空间。第十七页,本课件共有67页页页6/r=1页页3/r=1页页4/r=0页页8/r=0页页10/r=1页页9/r=0页页0/r=0页页1/r=1框框12框框23框框51框框6框框81框框96框框60框框5访问第访问第18页页时钟算法时钟算法第十八页,本课件共有67页页页6/r=0页页3/r=1页页4/r=0页页8/r=0页页10/r=1页页9/r=0页页0/r=0页页1/r=1框框12框框23框框51框框6框框81框框96框框60框框5访问第访问第18页页时钟算法时钟算法第
16、十九页,本课件共有67页页页6/r=1页页3/r=0页页4/r=0页页8/r=0页页10/r=1页页9/r=0页页0/r=0页页1/r=1框框12框框23框框51框框6框框81框框96框框60框框5访问第访问第18页页时钟算法时钟算法第二十页,本课件共有67页页页6/r=0页页3/r=0页页18/r=1页页8/r=0页页10/r=1页页9/r=0页页0/r=0页页1/r=1框框12框框23框框51框框6框框81框框96框框60框框5替换第替换第4页页时钟算法时钟算法第二十一页,本课件共有67页改进的时钟算法改进的时钟算法n考虑修改标志考虑修改标志mnr=0,m=0:最佳淘汰页面:最佳淘汰页面n
17、r=0,m=1:淘汰前回写:淘汰前回写nr=1,m=0:不淘汰:不淘汰nr=1,m=1:不淘汰:不淘汰第二十二页,本课件共有67页改进的时钟算法改进的时钟算法n步骤步骤1:n由指针当前位置开始扫描,选择最佳淘汰页面,不由指针当前位置开始扫描,选择最佳淘汰页面,不改变引用位,将第一个遇到的改变引用位,将第一个遇到的r=0且且m=0的页面作的页面作为淘汰页面;为淘汰页面;n步骤步骤2:n如步骤如步骤1失败,再次从原位置开始,找失败,再次从原位置开始,找r=0且且m=1的页的页面,将第一个满足上述要求的页面作为淘汰页面,同时将面,将第一个满足上述要求的页面作为淘汰页面,同时将扫描过页面的扫描过页面的
18、r位清位清0;n步骤步骤3:n若步骤若步骤2失败,指针再次回到原位置,重新执行步骤失败,指针再次回到原位置,重新执行步骤1。若还失败再次执行步骤若还失败再次执行步骤2,此时定能找到。,此时定能找到。第二十三页,本课件共有67页页页6/r=1 m=1页页3/r=1 m=1页页18/r=1 m=0页页8/r=1 m=0页页10/r=1 m=0页页9/r=0 m=1页页0/r=0 m=1页页1/r=1 m=0框框12框框23框框51框框6框框81框框96框框60框框5访问第访问第15页页改进的时钟算法改进的时钟算法第二十四页,本课件共有67页页页6/r=1 m=1页页3/r=1 m=1页页18/r=
19、1 m=0页页8/r=0 m=0页页10/r=1 m=0页页9/r=0 m=1页页0/r=0 m=1页页1/r=1 m=0框框12框框23框框51框框6框框81框框96框框60框框5访问第访问第15页页改进的时钟算法改进的时钟算法第二十五页,本课件共有67页页页6/r=1 m=1页页3/r=1 m=1页页18/r=1 m=0页页8/r=0 m=0页页10/r=0 m=0页页9/r=0 m=1页页0/r=0 m=1页页1/r=1 m=0框框12框框23框框51框框6框框81框框96框框60框框5访问第访问第15页页时钟算法时钟算法第二十六页,本课件共有67页页页6/r=1 m=1页页3/r=1
20、m=1页页18/r=1 m=0页页8/r=0 m=0页页10/r=0 m=0页页15/r=1 m=0页页0/r=0 m=1页页1/r=1 m=0框框12框框23框框51框框6框框81框框96框框60框框5时钟算法时钟算法第二十七页,本课件共有67页2010年考研试题n某虚拟页式系统,进程空间和内存空间都是64k,页长1K,某进程6个页,内存分配4个页框,采用局部置换,280时刻页表和Clock数据结构如下:逻辑页号 页框号 装入时间 访问标志 0 5 110 1 1 -2 12 160 1 3 8 230 1 4 -5 3 80 10页2页3页5页框5框12框8框3(顺时针)第二十八页,本课件
21、共有67页2010年考研试题n(1)280时刻访问13B7H,逻辑页号是多少?n(2)采用FIFO置换算法,物理页框号是多少?物理地址是多少?n(3)采用CLOCK置换算法,页框号是多少?物理地址是多少?第二十九页,本课件共有67页2010年考研试题n(1)逻辑地址13B7H化为二进制数为0001001110110111,其中后10位为页内地址,前6位为逻辑页号,即逻辑页号为4。n(2)4号页不在内存,发生缺页中断,按FIFO置换算法,应置换第5页,所得页框号3,形成物理地址0000111110110111,划成16进制为0FB7H。n(3)采用CLOCK置换算法,淘汰第0页,得页框5,形成物
22、理地址为0001011110110111,划成16进制为17B7H。第三十页,本课件共有67页6.5.1.6 颠簸颠簸(thrashing)页面在内存与外存之间频繁换入换出。页面在内存与外存之间频繁换入换出。原因:原因:(1)分给进程物理页架过少;分给进程物理页架过少;(2)淘汰算法不合理。淘汰算法不合理。处理:处理:(1)增加分给进程物理页架数;增加分给进程物理页架数;(2)改进淘汰算法。改进淘汰算法。思考题:思考题:在某些虚拟页式存储管理系统中,内存中总保持一个在某些虚拟页式存储管理系统中,内存中总保持一个空闲的物理页架,这样做有什么好处?空闲的物理页架,这样做有什么好处?第三十一页,本课
23、件共有67页6.5.1.7 工作集模型工作集模型(working set model)工作集工作集(working set):进程在一段时间内所访问页面的集合。进程在一段时间内所访问页面的集合。WS(t,)=5,7,1,6,22 6 1 5 7 7 7 7 5 1 6 2 2 1 2 3 (page reference)t:称为窗口尺寸:称为窗口尺寸(window size)。Denning 认为:为使程序有效运行,工作集应能放入内存。认为:为使程序有效运行,工作集应能放入内存。T第三十二页,本课件共有67页WS(t1,)=5,7,1,6,22 6 1 5 7 7 7 7 5 1 6 2 2
24、1 2 3 4 4 4 3 4 3 4 4 4 1 3 4.WS(t2,)=2,3,4 t1t2工作集与时间有关:工作集与时间有关:工作集与窗口尺寸有关:工作集与窗口尺寸有关:程序大小程序大小 WS第三十三页,本课件共有67页窗口尺寸确定:窗口尺寸确定:过小:活动页面不能全部装入,页故障率高;过小:活动页面不能全部装入,页故障率高;过大:内存浪费。过大:内存浪费。Madnick,Donovan建议:建议:1万次访内。万次访内。实现:页表中增加访问位:实现:页表中增加访问位:访问位访问位页表:页表:开始时,全部开始时,全部清清0,访问:置访问:置1,结束时结束时(新新 开始时开始时)访问标志为访
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第六章 存储管理优秀PPT 第六 存储 管理 优秀 PPT
限制150内