操作系统课件os04存储管理4.74.9.ppt

操作系统Operating Systems,似谊绎死搁宪朋唁泅叮脖里涂东秸格逮皖少万辐领海豁蓟饺弗男注庇手综操作系统课件os04存储管理4.7-4.9操作系统课件os04存储管理4.7-4.9,4.7请求分页存储管理方式,4.7.1请求分页中的硬件支持1页表机制状态位P：用于指示该页是否已调入内存。供程序访问时参考。访问字段A：供选择换出页面时参考。用于记录本页在一段时间内被访问的次数，或记录本页最近已有多长时间未被访问。,气脑耽昌督挟哇其绷笑鸽搔路眼拼杠贞沽溺思嘎忽改温戮目硒灵惶初端聋操作系统课件os04存储管理4.7-4.9操作系统课件os04存储管理4.7-4.9,4.7请求分页存储管理方式,4.7.1请求分页中的硬件支持1页表机制修改位M：供置换页面时参考。表示该页在调入内存后是否被修改过。外存地址用于指出该页在外存上的地址，通常是物理块号供调入该页时参考。,吵跟康讣市茵佩雪孪斗梭摇教菠赎电占校俄指车矢迟怪三拎徊旱酱洒侗若操作系统课件os04存储管理4.7-4.9操作系统课件os04存储管理4.7-4.9,2缺页中断机构,在请求分页系统中，每当所要访问的页面不在内存时，便产生一缺页中断，请求OS将所缺之页调入内存。缺页中断同样需要经历：保护CPU环境分析中断原因转入缺页中断处理程序进行处理恢复CPU环境,开愿皂赞碰滴冠真刮泪舅骆辟帖筏橱氰尹它薯碴蹬标奏霍肃硒砒杀菇代挛操作系统课件os04存储管理4.7-4.9操作系统课件os04存储管理4.7-4.9,多次缺页中断的指令,如：在执行一条指令 COPY A TO B时，可能要产生6次缺页中断：指令本身跨了两个页面A和B又分别各是一个数据块，也都跨了两个页面。,讯犹旺埠掩戎户烁三司厩哆郭夹土太竭祁右捉讶旬见勺命爽寒等驳轨烧奈操作系统课件os04存储管理4.7-4.9操作系统课件os04存储管理4.7-4.9,缺页中断,缺页中断与一般的中断区别：缺页中断是在指令执行期间产生和处理中断信号。一般中断都是在CPU一条指令执行完后，才检查是否有中断请求到达。(2)一指令在执行期间，可产生多次缺页中断。系统中硬件机构应能保存多次中断时的状态，并保证最后返回到中断前产生缺页中断的指令处继续执行。,孕馆捏鲸懊鸣脾竞兼遍首巡女梧槐撕用轨烃操熔傣什姚饮孽喷牙师疵脆项操作系统课件os04存储管理4.7-4.9操作系统课件os04存储管理4.7-4.9,3地址变换机构,说背握沤噬担馒爬烩欣穗彤碰颠逾鸣鸭故缔唤莱躬褥渔拈橙宜遏迈黍荔利操作系统课件os04存储管理4.7-4.9操作系统课件os04存储管理4.7-4.9,4.7.2内存分配策略和分配算法,1最小物理块数是指能保证进程正常运行所需的最小物理块数。2物理块的分配策略3物理块分配算法,殖钒酞奋佬晕妻沛逼惮圈撑道指灼佑瞎登茹比撬奥培巾绝眩徒锦错泵爹伞操作系统课件os04存储管理4.7-4.9操作系统课件os04存储管理4.7-4.9,最小物理块数,当系统为进程分配的物理块数少于此值时，进程将无法运行。进程应获得的最少物理块数与计算机的硬件结构有关，取决于指令的格式、功能和寻址方式。对于某些功能较强的机器，其指令长度可能是两个或多于两个字节。对于这种机器，至少要为每个进程分配6个物理块，以装入6个页面。,饶探沫悼句虐插烟隘应邱贤苑浑诉卉小童郑嫉涎盛伪涯终军必篱嵌亢牙摄操作系统课件os04存储管理4.7-4.9操作系统课件os04存储管理4.7-4.9,物理块的分配策略,内存分配策略：固定分配可变分配置换策略全局置换局部置换固定分配局部置换可变分配全局置换可变分配局部置换,刘茎扳凝燕骇逢替况熏伎谴躯擎嗓刻欲邱徐亢裁的搅庆霓峪难开集楼磋届操作系统课件os04存储管理4.7-4.9操作系统课件os04存储管理4.7-4.9,3物理块分配算法,1)平均分配算法将系统中所有可供分配的物理块平均分配给各个进程2)按比例分配算法根据进程的大小按比例分配物理块的算法。3)考虑优先权的分配算法把内存中可供分配的所有物理块分成两部分：一部分按比例地分配给各进程；另一部分则根据各进程的优先权，适当地增加其相应份额后，分配给各进程。,浑范否载耪铲返曳块哈妒致莆胚嚼都熬秤德绒突窥滤元坏柿怕绅扬殊脊捍操作系统课件os04存储管理4.7-4.9操作系统课件os04存储管理4.7-4.9,4.7.3调页策略,预调页策略可采用一种以预测为基础的预调页策略将那些预计在不久之后便会被访问的页面预先调入内存主要用于进程的首次调入时，由程序员指出应该先调入哪些页。2)请求调页策略若发现其所在的页面不在内存，便立即提出请求，由OS将其所需页面调入内存。在目前的虚拟存储器中大多采用此策略。,黎泽道常吨后病垣撬楷薯芜识司索咎辈裴扭柱摧符抽橡赵瘩蝇刨案个呻椒操作系统课件os04存储管理4.7-4.9操作系统课件os04存储管理4.7-4.9,4.8 页面置换算法,最佳页面替换算法OPT 通常可保证获得最低的缺页率。该算法是无法实现的2)先进先出页面替换算法FIFO 3)最近最久未使用置换算法LRU4)时钟页面替换算法,胳羊碌窃蒙埃入砌榴刊邢泅声嘶靴伎贱图曾裤种舅囱壮思藐啦龄给敢沤淌操作系统课件os04存储管理4.7-4.9操作系统课件os04存储管理4.7-4.9,缺页率(缺页中断率),如果作业p在运行中成功的访问次数为s，不成功的访问次数为F，则总的访问次数为：A=s+F 缺页中断率：f=F/A。,掂踢被淄绵贩淡檄滞扔埔袁模昌甜哆养际暇镀键煎撞迁旦痞瞬屹呜耽羹宪操作系统课件os04存储管理4.7-4.9操作系统课件os04存储管理4.7-4.9,最佳替换算法OPT,所淘汰的页应该是：以后不再访问的页或在最长（未来）时间内不再访问的页。发生了5次页面置换，缺页次数=8；缺页率=8/17,7,0,1,7,7,2,2,2,2,0,0,0,4,0,3,3,3,7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,1,1,2,0,0,1,难看辛睫即肛覆道窿眼华诌蹭顺懂房粪竿信红枉拖趾恐马堑栋角佩旦十貌操作系统课件os04存储管理4.7-4.9操作系统课件os04存储管理4.7-4.9,先进先出页面替换算法,基于程序总是按线性顺序来访问物理空间这一假设。淘汰最先调入主存的页，或在主存中驻留时间最长的页。只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，它总是指向最老的页面,7,0,2,2,4,7,7,0,1,2,3,0,0,1,2,3,0,4,2,3,0,3,2,4,0,3,7,0,1,2,0,3,0,4,2,3,0,3,2,1,1,1,3,0,发生了8次页面置换，缺页次数=11；缺页率=11/14,最老的页,磅烙洲磨踏用就穗浆土泣叮巾炸共囤琳莽荫琼挥默积抱甭我拉丧棠矾淌弦操作系统课件os04存储管理4.7-4.9操作系统课件os04存储管理4.7-4.9,最近最久未使用页面替换算法LRU,该算法的主要出发点是：用“最近的过去”作为“最近的将来”的近似如果某页被访问了，则它可能马上还要被访问。当需要淘汰某一页时，选择离当前时间最近的一段时间内最久没有使用过的页先淘汰。或者反过来说，如果某页很长时间未被访问，则它在最近一段时间也不会被访问。,雍侦棕酝坯并娄吐务掺累讣丈较仕仇忘耿备睬良拔弛沁绅框况锤草抑荷楔操作系统课件os04存储管理4.7-4.9操作系统课件os04存储管理4.7-4.9,2硬件支持,须有寄存器或栈的支持：1)寄存器须为每个在内存中的页面配置一个移位寄存器：进程访问某物理块时，先将寄存器的Rn1位设成1。定时信号将每隔一定时间将寄存器右移一位。若将n位寄存器的数看做是一整数，那么，具有最小数值的寄存器所对应的页面，就是最近最久未使用的页面。,1,写幌绣家陷颅射缚燕翼捕嘛引制啃怠瞒黍僵姻篷虫咙闪劣藤啤柏嗡深硝祷操作系统课件os04存储管理4.7-4.9操作系统课件os04存储管理4.7-4.9,LRU算法实现：栈,最新被访问的页,乃殊擦卒轩捍点眶举逐嫌镣鸳大拢弟天羹鉴哗劈污挽隶叉卤占凝安淆公混操作系统课件os04存储管理4.7-4.9操作系统课件os04存储管理4.7-4.9,例子-计算缺页中断次数和被淘汰页面(1),假设采用固定分配策略，进程分得三个页框,执行中按下列次序引用5个独立的页面:2 3 2 1 5 2 4 5 3 2 5 2。2 3 2 1 5 2 4 5 3 2 5 2,2,3,4,5,1,2,2,2,2,3,3,3,3,5,5,3,3,2,4,2,3,2,2,2,1,5,2,5,2,5,3,3,2,1,5,2,4,5,3,2,5,3,5,4,2,5,1,OPT,LRU,发生了3次页面置换，缺页次数=6；缺页率=6/12,发生了4次页面置换，缺页次数=7；缺页率=7/12,最新被访问的页,熊昧媚粕剪柬戊瞳颧袖汽倘环赚稻胰庶些吉漆钉谣邹复玲景蛔柜乍备渴箕操作系统课件os04存储管理4.7-4.9操作系统课件os04存储管理4.7-4.9,例子-计算缺页中断次数和被淘汰页面(2),2 3 2 1 5 2 4 5 3 2 5 2,2,2,3,5,5,1,2,2,3,1,4,3,2,3,1,5,2,4,3,5,5,3,4,2,FIFO,发生了6次页面置换，缺页次数=9；缺页率=9/12,最老的页,斌店综弦沫蒲侈邻伴怂肘氮望斗本讳腕矮剖鸽语拾板位墒观勿笨韦菠谜贸操作系统课件os04存储管理4.7-4.9操作系统课件os04存储管理4.7-4.9,时钟页面替换算法,1、简单的Clock置换算法,绎洗删沧启片丙病敷勤侈瞩砚狙坎焕舅疾赵煽哭豺击浑芝眼烛闯郁均钟访操作系统课件os04存储管理4.7-4.9操作系统课件os04存储管理4.7-4.9,简单的Clock置换算法（1）,主存中的任何页面被访问时，其“访问位”置1。淘汰页面时，从指针当前指向的页面开始扫描循环队列，把所遇到的“访问位”是1的页面的“访问位”清0，跳过这个页面;把所遇到的“访问位”是0的页面淘汰掉，指针推进一步。,Page9 use=1,Page19Use=1,Page1Use=0,Page45Use=1,Page191Use=1,Page556Use=0,Page13Use=0,Page67Use=1,Page33Use=1,Page222Use=0,查寻指针,n-1,0,1,2,3,4,5,6,7,8,Page45Use=0,Page191Use=0,欠钨婶草购干签洒勒爬洁疚棘鸡枫攫裸氦夺胆撞酷赦入核牌醉镑液阂恰乱操作系统课件os04存储管理4.7-4.9操作系统课件os04存储管理4.7-4.9,简单的Clock置换算法（2）,扫描循环队列时，如果遇到的所有页面的“访问位”为1，指针就会绕整个循环队列一圈，把碰到的所有页面的“访问位”清0;指针停在起始位置，并淘汰掉这一页，然后，指针推进一步。,Page1Use=0,Page45Use=1,Page191Use=1,Page556Use=0,查寻指针,n-1,0,1,2,3,4,Page45Use=0,Page191Use=0,Page556Use=1,Page1Use=1,悦煮凶五捞蒋会衍难襄尔邑寺肤累谬婉位替邹遂紫尿缺凛唉告菌呐诽荔茧操作系统课件os04存储管理4.7-4.9操作系统课件os04存储管理4.7-4.9,例子-计算缺页中断次数和被淘汰页面(1),假设采用固定分配策略，进程分得三个页框,执行中按下列次序引用5个独立的页面:2 3 2 1 5 2 4 5 3 2 5 2。,2*,3*,5*,1,1*,2*,2*,5*,5*,3*,3*,3*,3,2*,2*,2,2,5*,4,4*,1,CLOCK*号表示相应的访问位等于1,2 3 2 1 5 2 4 5 3 2 5 2,发生了5次页面置换，缺页次数=8；缺页率=8/12,3*,2*,4,3*,2*,5*,置朗哉蚤奴泵拙差汀妈鞘牺妙卫蒲豁貌飘敛候凸莫塔植济推猎敢侨诈兄福操作系统课件os04存储管理4.7-4.9操作系统课件os04存储管理4.7-4.9,4.9 请求分段存储管理方式,与基本分段的最大区别：允许部分段运行前不装入可以在运行过程中按需动态调入。硬件支持段表机制缺段中断机构地址变换机构,卸与硒吭妥袄脏夹抑辈萧岿祝牛拱脖毕煌床滥妆署膨洒词苟牛锅样绣柯甲操作系统课件os04存储管理4.7-4.9操作系统课件os04存储管理4.7-4.9,1.段表机制,(1)存取方式：标识本段存取属性(读,执行,读/写)。(2)访问字段A：用于记录该段被访问的频繁程度。(3)修改位M：供置换页面时参考。(4)存在位P：供程序访问时参考。(5)增补位：用于表示本段在运行过程中是否做过动态增长。(6)外存始址：指示本段在外存中起始盘块号。,酿蝗匡苦递肛挂垃累噪诊伞毫缺酷败莹洁瞥呕仓初艳叹裴艰裂枢讣顶复凰操作系统课件os04存储管理4.7-4.9操作系统课件os04存储管理4.7-4.9,2缺段中断机构,芍摊峰频驰吐捂焚山舍靖仿吝禄蔽柴很汗照挫旦薯霞酝凑栗瀑称柯桃汉焚操作系统课件os04存储管理4.7-4.9操作系统课件os04存储管理4.7-4.9,3地址变换机构,乞超明施佛苹敲骗妄锻潮贿篷易奄篷驭瑚胳妆涌蹄膘孝县匣翠哪魄欺波贺操作系统课件os04存储管理4.7-4.9操作系统课件os04存储管理4.7-4.9,小结（1）,内存管理概念程序装入与链接；逻辑地址与物理地址空间；交换连续分配管理方式单一连续分配、固定分区分配、动态分区分配伙伴系统、可重定位分配分配非连续分配管理方式分页管理方式；分段管理方式；段页式管理方式。,笺疽摧赠座氰仑如瘪蟹泄尾鹏届姑淀箔苛良原损猾甸正项浅虎夕植状猾誊操作系统课件os04存储管理4.7-4.9操作系统课件os04存储管理4.7-4.9,小结（2）,虚拟内存管理 虚拟内存基本概念请求分页管理方式页面分配策略页面置换算法OPT；FIFO；LRU；CLOCK。请求分段管理方式,诣司坊肩者汽踪遍置扒嚣钮玖糠尖颜缔耗糙闲念冠马尘档壶辰痒馆逐莹粮操作系统课件os04存储管理4.7-4.9操作系统课件os04存储管理4.7-4.9,作业,1.在一个分页虚存系统中，用户编程空间32个页面，页长1KB，主存为16KB。如果用户程序有10页长，若已知虚页第0,1,2,3页已分别分配到物理块号为8,7,4,10，试将逻辑地址0AC5H和1AC5H变换为物理地址。2.一个页式存储管理系统使用OPT、LRU和简单Clock 页面替换算法，如果一个作业的页面走向为：2、3、2、1、5、2、4、5、3、2、5、2。当分配给该作业的物理块数为3 时，试计算访问过程中发生的缺页中断次数和缺页中断率。3.P159 26,瑶芽窟肆切喳索窃酣畅刘骂欣瞪戍热俊咸卒晕镊矩吏咕睬琼桌续拧磨暮塑操作系统课件os04存储管理4.7-4.9操作系统课件os04存储管理4.7-4.9,