计算机操作系统李翠霞os45.ppt
第四章 存储器管理,主讲:李翠霞办公室:水环楼306电话:0371-63887291E-mail:,屑疚滤憋凄屈立呆勒沙混狸因宅碌饥母宫智颈腥昌优丁怂祭提晓迂蓉镊玖计算机操作系统 李翠霞 os4_5计算机操作系统 李翠霞 os4_5,空虏晓轧匪矿腿油贴痢渣碱露古翔术便壤札糕沤蹈槛和汰诱妹燎狠驼我甘计算机操作系统 李翠霞 os4_5计算机操作系统 李翠霞 os4_5,解决页表需要连续空间问题-对页表进行离散分配如:以4K为单位划分页面和内存块,若逻辑地址为32位,则用单级页表时页表的表项数:220=10241024=1M;每个表项占4个字节页表长为:4M在内存中难以找到4M的连续空间,可类比为:页表登记了各位同学的宿舍号,如果班里同学只有20人,则一页A4纸即可登记完毕。假如登记全院1万名同学的宿舍号信息,此时可能需要一张很长的表格。可借鉴两级页表的策略,先将同学分成每20位一组,一张纸上20行,1万名同学需要5000页纸。这5000页纸可放在不同的若干档案格中。又有一张登记表记下了每组所在的档案盒号(外层页表)。,衔绚性其湾论薛囊卒宿耀类淮澈罐铡斥骂车石潜谚造瞥党恰以漆帛唾禄篓计算机操作系统 李翠霞 os4_5计算机操作系统 李翠霞 os4_5,两级页表,0,1,2,4,3,5,6,7,114,115,1468,第0页页表,第1页页表,第n页页表,纤漠氢羚骋斥晦挝婶单缠对店往莽私随炙簧仁物钥买咳亢肿等膀稽绊障唬计算机操作系统 李翠霞 os4_5计算机操作系统 李翠霞 os4_5,两级页表,.,.,外部页表寄存器,外部页表,页表,外部页号,外部页内地址,页内地址,p1,p2,d,d,b,逻辑地址,验仔丝反汇环邦彻靠拼椽逗酮毒离煤启免荫艇茬簧甸彝予鳞乍藻儒胸扼舷计算机操作系统 李翠霞 os4_5计算机操作系统 李翠霞 os4_5,采用两级时,指令所给出的地址分为三部分:外层页号内层页号 偏移地址。10位 10位 12位,如上页图所示的两级页表结构。假如逻辑地址空间为232,请问逻辑地址00401B21H所对应的物理地址为?,00073B21H,涪爽脚垦窍德墟蝶贯赁抉轿骤钞伯映朱脯冲敌诀彼罩镇丘轿廉德舜蹲桓率计算机操作系统 李翠霞 os4_5计算机操作系统 李翠霞 os4_5,分析过程,外层页号内层页号 偏移地址 10位 10位 12位,00401B21H可分割为0000 0000 01 00 0000 0001 1011 0010 0001,得物理块号115,0000 0000 0000 0111 0011,对应的物理地址为:0000 0000 00 00 0111 0011 1011 0010 0001,00073B21H,区俊拧友气皇畜牌讯频星雾署馏圃脯沦摇恩截诸昭砚彭淑围烁刹敦结啤帧计算机操作系统 李翠霞 os4_5计算机操作系统 李翠霞 os4_5,假设:有主程序段MAIN、子程序段X,数据段D及栈段S等。则利用段表可实现地址映射(P137 图4-17):,作业空间(MAIN)=0,(X)=0,(D)=2,(S)=3,0,30K,20K,0,15K,0,10K,0,段号,段长,基址,0,1,2,3,(MAIN)=030K,(X)=120K,(D)=215K,(S)=310K,内存空间,0,40K,80K,120K,150K,瘫状痹滚欲糊酶蛀价疙袭来诌炎寝胞吟相炭汐酿峰综跳让窥檄钢伍郝剔挤计算机操作系统 李翠霞 os4_5计算机操作系统 李翠霞 os4_5,3.地址变换机构,1K 6K,600 4K,500 8K,200 9200,8K,8292,8692,段号 段长 基址,0123,段表寄存器,段表基址,段表长度,段号s 段内偏移d,2,100,物理地址,内存,段表,越界,8292,旨凑粱过血践轴附瞩值害锋潭怔采狂霹镶飘美磁脆押圈弃宽泰瞩疵训窘郧计算机操作系统 李翠霞 os4_5计算机操作系统 李翠霞 os4_5,4.5.4 段页式存储管理方式,段表大小,段表始址,段号,状态,页表大小,页表始址,页号,状态,存储块#,操作系统,主存,段表寄存器,0,1,1,1,2,1,3,0,0,1,1,1,2,1,3,0,4,1,淌溃匝皖累丑障允闰揩弊妒罪遣还钻落峙易丹缸卡专舟虑认皂粳稽堡罩寞计算机操作系统 李翠霞 os4_5计算机操作系统 李翠霞 os4_5,4.5.4 段页式存储管理方式,段表大小,段表始址,段号,状态,页表大小,页表始址,页号,存储块#,页号,存储块#,段表寄存器,0,1,5,1,1,2,1,4,2010H,3,0,0,2,1,8,2,1,3,0,5,4,0,3,1,6,2,4,3,7,2010H,若某系统采用段页式存储管理方式,段表和部分段的分页情况如图所示,页面大小为1KB。请问逻辑地址(2,2500)对应的物理地址是多少?,根据段号查得2号段的页表地址为2010H,可到内存2010H地址处读得该段的页表。,INT(2500/1024)=22500 Mod 1024=452,可得物理地址为:1024*4+452=4096+452=4548,苫赖乓扦搪蕴阀刘喳挑饰赞金臭奴齿卜龄舒躇姓卧增盏暖袋衍茂捐俞零内计算机操作系统 李翠霞 os4_5计算机操作系统 李翠霞 os4_5,本章主要内容,4.1 存储器的层次结构4.2 程序的装入和链接4.3 连续分配方式4.4 基本分页存储管理方式4.5 基本分段存储管理方式4.6 虚拟存储器的基本概念4.7 请求分页存储管理方式4.8 页面置换算法4.9 请求分段存储管理方式,汗砾慑副谊勃堂蜕泽灸赚先图决仪墨舶晦宁请争肠破窿八握江拳慢咐烤继计算机操作系统 李翠霞 os4_5计算机操作系统 李翠霞 os4_5,4.6 虚拟存储器的基本概念,产生的原因:连续分配、基本分页和基本分段存储管理方式都要求将一个作业全部装入内存后方能运行,于是,会出现:1)作业很大,需求总容量超过了内存总容量。会因不能全部装入内存而导致该作业无法运行。2)有大量作业要求运行,但由于内存容量不足以容纳所有作业,只能将少数作业装入内存让它们运行,大量作业留在外存上等待。,解决的办法:从物理上增加内存容量受机器自身的限制,增加系统成本从逻辑上扩充内存容量用虚拟存储器技术解决,机痹博增徽隶辨伊崖尤生西瓢芬细累绍腺觉憎篷魂酥冲打芒吏牙番昨耘担计算机操作系统 李翠霞 os4_5计算机操作系统 李翠霞 os4_5,4.6 虚拟存储器的基本概念,常规存储管理方式的特征:一次性 作业在运行前需一次性地全部装入内存。作业每次运行时,并非全部程序和数据都要用到,如果全部装入,造成了对内存空间的浪费。驻留性 作业装入内存后,便一直驻留在内存中,直至运行结束。尽管有的进程会因等待I/O而长期等待,或有的程序模块在运行过一次后就不再需要了,但它们都仍继续占用宝贵的内存资源。,一次性和驻留性是必需的吗?,殿榔止柞咙雨数过菜励纹告惺蓝浴碍透沈躲像釉鞘哎食印烟撞烘冗茄谚鄙计算机操作系统 李翠霞 os4_5计算机操作系统 李翠霞 os4_5,一.局部性原理局部性原理:指程序在执行过程中的一个较短时间内,所执行的指令地址和指令的操作数地址,分别局限于一定区域。可以表现为:1)时间局部性:一个数据结构或指令在有限时间内再次被访问.2)空间局部性:一个区域再次被访问.,4.6 虚拟存储器的基本概念,1968年,Denning.P提出了局部性原理,为虚拟存储技术的发展奠定了理论基础。,昼比侥崖收钡虚顽系仅对队遵何垂艾寞酶胺倚段先钉燥诊哇拉呵切辽绰骨计算机操作系统 李翠霞 os4_5计算机操作系统 李翠霞 os4_5,2、局部性原理的具体体现程序在执行时,大部分是顺序执行的指令,少部分是转移和过程调用指令。过程调用的嵌套深度一般不超过5,因此执行的范围不超过这组嵌套的过程。程序中存在相当多的循环结构,它们由少量指令组成,而被多次执行。程序中存在相当多对一定数据结构的操作,如数组操作,往往局限在较小范围内。,气踢晃陀撅袜五窥灼坪拍堂缨氏猩宽鼓业焦潘吵鹤控沈滴零悬冶噶味迅跳计算机操作系统 李翠霞 os4_5计算机操作系统 李翠霞 os4_5,3.根据局部性原理,进程地址空间,部分放于内存(当前使用的),部分放于外存(当前暂不用的),内外交换,4.虚拟存贮器定义:仅把作业一部分装入内存就可运行的系统虚拟存贮器(P143):是指具有请求调入功能和置换功能,能从逻辑上对内存容量加以扩充的一种存储器系统。,交换单位:页或段,柳聊野儒营防喘谆岭纠纵肮尼褒镁瑞吕堤豆作忆砚嫌波就肖优珠员冶遁怪计算机操作系统 李翠霞 os4_5计算机操作系统 李翠霞 os4_5,4.6.2 虚拟存储器的实现方法,地址空间部分装入:在程序装入时,只将当前需要执行的部分页或段装入到内存,就可让程序开始执行。,执行中,如果需执行的指令或访问的数据尚未在内存(称为缺页或缺段),硬件产生缺页或缺段中断。,3.中断处理程序,将相应的页或段调入到内存,然后继续执行程序;如果内存无空闲空间,系统将内存中暂时不使用的页或段调出保存在外存交换区,从而腾出空间存放将要调入的页或段。,4.以上2、3两条功能称之:,缺页中断处理(用于请求页式管理),缺段中断处理(用于请求段式管理),美谊把蛋掀鹿医曼慎娶淖吱柯琵宽械鹿柑驶绸驾雇葬咱条品倍蝉娟哭职吸计算机操作系统 李翠霞 os4_5计算机操作系统 李翠霞 os4_5,三.引入虚拟存储技术的好处,3.并发:可在内存中容纳更多程序并发执行.,运行大程序:可在较小的可用内存中执行较大的用户程序.,2.大的用户地址空间:提供给用户可用的虚拟内存空间通常大于物理内存.,歉县场剂宴蓑轿夺流合褐犯缚丑尤影液舆永陪谴炕挪启茹弗雍蹋苍胯陨氯计算机操作系统 李翠霞 os4_5计算机操作系统 李翠霞 os4_5,4.6.3 虚拟存储技术的特征,3.虚拟性:提供大范围的虚拟地址空间(通过物理内存和快速外存相结合).,1.作业装入的多次性:不再一次性装入,2.对换性:,注意:总容量不超过物理内存和外存交换区容量之和,乙拽刃溪恐驭饿挞纬罕葛嘿岂攘珠席锡馈废滑垣示巨耶崖奏坊涪号逆铀囤计算机操作系统 李翠霞 os4_5计算机操作系统 李翠霞 os4_5,本章主要内容,4.1 存储器的层次结构4.2 程序的装入和链接4.3 连续分配方式4.4 基本分页存储管理方式4.5 基本分段存储管理方式4.6 虚拟存储器的基本概念4.7 请求分页存储管理方式4.8 页面置换算法4.9 请求分段存储管理方式,翔疾勉押原憨符忽八呢惜滞纹挽籽柑芝咆具涩配悉艾鸭地褪照唁项廓证荒计算机操作系统 李翠霞 os4_5计算机操作系统 李翠霞 os4_5,1)进程地址空间分为虚页,一.实现原理,之所以称虚页,因为运行时不一定在主存,2)运行前装入部分页,3)运行时访问的页面不在内存,缺页中断,调入缺页.,4)缺页中断,调入新页时,若内存无空闲块,则淘汰某页,把新页调入.,5)地址变换(重定位):类似简单分页系统,但页表要增加4项(增加请求调页、页面置换功能),4.7 请求分页存储管理方式,造诞吝评信拨壶罗剖势嘘钠胳弦涸断寥荡走彝鼻烧瞄埋鹃乓觉骗诲攒窑彻计算机操作系统 李翠霞 os4_5计算机操作系统 李翠霞 os4_5,在简单页式存储管理的基础上,PMT中增加请求调页和页面置换功能。,简单分页PMT,请求页式进程页表(PMT),A访问字段:页面访问统计,在近期内被访问的次数,或最近一次访问到现在的时间间隔.为淘汰算法提供依据,外存地址:通常是物理块号。,怪绅泄黍遣酒蝶运均段踪从隐愿畏叁侥谨第勃瘁粘疟捉淹壶屹贺陋组饺沉计算机操作系统 李翠霞 os4_5计算机操作系统 李翠霞 os4_5,二.地址变换机构:(MMU),硬件支持:页表机制、缺页中断机构、地址变换机构 软件支持:缺页中断处理程序。,CPU给出的虚地址(逻辑地址)送给MMU部件,经MMU解析出虚页号,例如K,查页表的第K个表项,用该表项所对应的块号去构造物理地址,MMU把构造的物理地址送地址总线。MMU部件是地址变换机构。,泼茶升肩应烤锁班字澜轴靛存陇确吾秦劝炊损兑膘跟右尘墟祖矿沽术幕递计算机操作系统 李翠霞 os4_5计算机操作系统 李翠霞 os4_5,有一台16位机,可访问64K空间,给出的地址长度16位内存为32K。在具有虚拟存储功能的系统中,允许进程的地址空间=64K(虚地址空间)64K地址空间不能全部装入内存,部分装入外存有一个64K的地址空间映象运行时由MMU进行地址变换页面划分为4K:64K的虚地址空间可分为015(16个页面)物理空间分为8个页框(块),讨论MMU:,烩酞硷畦宰瞪煽寞漾战溃隧哥澡脐津科囊闺腹挺腥生棍研舱斤购遵诱皂翻计算机操作系统 李翠霞 os4_5计算机操作系统 李翠霞 os4_5,(虚拟存贮器),购备旋豫歪坡负豆摹鸳剃胖斗帕舆谨俞访札瘩洽羞后插蛙宾蝇浪屯匙轮掸计算机操作系统 李翠霞 os4_5计算机操作系统 李翠霞 os4_5,CPU执行load R1,8196(2004H)CPU给出虚地址8196送VA,分离出 P|W:2|42页在6块中块号6送MA的高三位,W送MA的低12位,形成物理地址:24580(6004H)6004H送地址总线存在位为0,MMU引起缺页中断。,捷靡稠揭驭骡竹患缝裙壬辫烘壬砸溃溢杰坑慎谎帮慑敏逢擂拄迈蠕郝扶饶计算机操作系统 李翠霞 os4_5计算机操作系统 李翠霞 os4_5,地址变换与中断处理流程,见:(P146图4-25),地址变换机构产生缺页中断,然后调用内存管理提供的中断处理例程。,适写胚虞垛知脸匆瑰含电昌蝗班夯棠榆洞曰狙予霉月氯孺赐氏滚攫垣傻爵计算机操作系统 李翠霞 os4_5计算机操作系统 李翠霞 os4_5,缺页中断机构:,在请求分页系统中,每当所要访问的页面不在内存时,便产生一缺页中断,请求OS将所缺之页调入内存。缺页中断同样需要经历保护CPU环境、分析中断原因、转入缺页中断处理程序进行处理、恢复CPU环境等几步。但缺页与一般中断相比,有着明显的区别,主要表现在:(1)在指令执行期间产生和处理中断信号。(2)一条指令在执行期间,可能产生多次中断。如图所示例子。,指令COPY A TO B本身跨了两页,A和B分别各是一个数据块,也都跨了两页。该指令的执行可能产生6次缺页中断。,重缝磅甥炬姑红铲召灿豆唐亢薛痉疫抠豢多裤串橱后烧消顶讹蹄异犁舱黔计算机操作系统 李翠霞 os4_5计算机操作系统 李翠霞 os4_5,又综腻虾嘎溃鹅敌珊黄稠脑迂侣狠稍汽扁狱拨肤鸯泪僻述惦徊拨采西荷罢计算机操作系统 李翠霞 os4_5计算机操作系统 李翠霞 os4_5,4.7.2 内存分配策略和分配算法,1.最小物理块数的确定 是指能保证进程正常运行所需的最小物理块数。当系统为进程分配的物理块数少于此值时,进程将无法运行。进程应获得的最小物理块数与计算机的硬件结构有关,取决于指令的格式、功能和寻址方式。,为进程分配内存时,将涉及到三个问题:第一,最小物理块数的确定;第二,物理块的分配策略;第三,物理块的分配算法。,腆贸紊容付覆肘荡迸寺酿郝渣商脯乡壹秤嘎挤晃痞烛趁徽郁瓦彬全浑袭联计算机操作系统 李翠霞 os4_5计算机操作系统 李翠霞 os4_5,4.7.2 内存分配策略和分配算法,2.物理块的分配策略 固定分配局部置换 为每个进程分配一定数目的物理块,整个运行期间都不再改变。可变分配全局置换 先为系统中的每个进程分配一定数目的物理块,而OS自身也保持一定空闲物理块队列。当某进程发现缺页时,由系统从空闲物理块队列中取出一个物理块分配给该进程,并将欲调入的页装入其中。可变分配局部置换 为每个进程分配一定数目的物理块,当某进程发现缺页时,只允许从该进程在内存的页面中选出一页换出,这样就不会影响其它进程的运行。若进程运行过程中频繁地发生缺页中断,则系统为该进程分配附加的物理块,直至该进程的缺页率减少到适当程度为止;反之,可适当减少分配给该进程的物理块数。,撂监荣班呈玻淮骏踊遁刽按苟冤逞炉蓖刃徘吴频薪娶乔谭孕蛛艺卢撩述钦计算机操作系统 李翠霞 os4_5计算机操作系统 李翠霞 os4_5,4.7.2 内存分配策略和分配算法,并非一个进程分配几个物理块就可运行,太少可能造成系统抖动.在采用固定分配策略时,如何将系统中可供分配的所有物理块分配给各进程。可采用以下几种算法:,1.平均分配:内存块平均分给各进程。小进程有利,长进程中断率高。,2.根据进程大小按比例分配。,3.按优先权分配。,3.物理块分配算法,遵阻囚耐耐尝斥嵌裳攫腮犯颧比酌稗晒笺标酗褪淄恬描糯桶喷栅玩芬穴矛计算机操作系统 李翠霞 os4_5计算机操作系统 李翠霞 os4_5,4.7.3 调页策略,2.预调页:在发生缺页需要调入某页时,一次调入该页以及相邻的几个页。(通常用于进程首次调入内存,可同时调入几页)优点:提高调页的I/O效率。缺点:基于预测,若调入的页在以后很少被访问,则效率低。常用于程序装入时的调页。,请求调页:只调入发生缺页时所需的页面。优点:容易实现。缺点:对外存I/O次数多,开销较大,调入页面的时机:,律宽眶否擞幢轴喷腔娱蜀打蓟谆墙宗镇焙罗枯绑漫砷偿匪罩蜂仑佳莫增号计算机操作系统 李翠霞 os4_5计算机操作系统 李翠霞 os4_5,4.7.3 调页策略,通常对换区的I/O效率比文件区的高。关于调入页面的来源,这里有三种做法:,1.从对换区:进程装入前,将其全部页面复制到对换区,以后总是从对换区调入。执行时调入速度快,要求对换区空间较大。,2.未被修改的页面从文件区读入,而被置换时不需调出;已被修改的页面从交换区调入,节省交换区空间.,被修改过的页面淘汰时送入对换区,确定从何处调入页面:,3.UNIX方式。未运行过的页面都应从文件区调入。而对于曾经运行过但又被换出的页面,应从对换区调入。又由于UNIX系统允许页面共享,如果某进程所请求的页面已经被其他进程调入内存,此时也无须从对换区调入。,铺龚珊圾痈侮楷褂辐串救露浪助都酮醛敛拧厉丁所轴覆畸渣鞋碍剥瞬伎腺计算机操作系统 李翠霞 os4_5计算机操作系统 李翠霞 os4_5,补充:抖动,从主存中刚刚移走某页面后,根据请求马上又调入该页。这种反复进行入页和出页的现象称为“抖动”,也叫系统颠簸。它会浪费大量的处理机时间,应尽可能避免。产生抖动的直接原因是页面置换算法选取不当。,倪督衰妆疟桌脱轰龟什胯幌簿吩降瑞龚兰孽母咒淋缔牢望昭守哥距姑宜揖计算机操作系统 李翠霞 os4_5计算机操作系统 李翠霞 os4_5,利用LRU置换算法时的置换图,7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1,共产生缺页中断12次,页面引用序列为:7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1,骗缔除妨蝗高歼厩葬忻华份亦震虱垦椰场喷跨呜狗空菱碱卤上彼治先擦水计算机操作系统 李翠霞 os4_5计算机操作系统 李翠霞 os4_5,请求分页系统的评价,优点:请求分页存储管理具有分页存储管理的全部优点,特别是它解决了碎片的问题。提供了大容量的多个虚拟存储器;作业地址空间不再受实际存储容量的限制;更有效地利用主存;有利于运行多道程序;提高了系统效率,方便了用户,特别是大作业用户;,便铣橇影户轻淫壕苟棚蚀颐驰菠贮巳元粪味待战抑勇恰刮额旭嘛讶贷伙缚计算机操作系统 李翠霞 os4_5计算机操作系统 李翠霞 os4_5,缺点:要求有相应的硬件支持,从而增加了成本,如动态地址变换、快表、缺页中断的产生等都要求有相应的硬件支持。缺页中断增加了处理机时间的开销,如页表的建立与管理、缺页中断处理等;页面淘汰算法如选择不当,有可能产生抖动现象,为防止抖动,会增加系统的复杂性;虽然消除了碎片,但每个进程的最后一页内总有一部分空间得不到利用;,请求分页系统的评价,颈乡拓脾丛幽浇洛宝型向去擅牙串双吃峰骑很寨毯蜘靡帜斩版判棋茨偷渣计算机操作系统 李翠霞 os4_5计算机操作系统 李翠霞 os4_5,补充作业,考虑一个请求调页系统,它采用全局置换策略和平均分配内存块的算法(即若有m个内存块和n个进程,则每个进程分得m/n个内存块)。如果在该系统中测得如下的CPU和对换盘的利用率,请问能否用增加多道程序的度数来增加CPU的利用率?为什么?(1)CPU的利用率为13%,内存利用率为97%。(2)CPU的利用率为87%,内存利用率为3%。(3)CPU的利用率为13%,内存利用率为3%。,谊浑寸冻喜泡独吃揖垮竿陈扳讹腆愉规啦秀来稿溜肤椒芍纳驯文锁先强明计算机操作系统 李翠霞 os4_5计算机操作系统 李翠霞 os4_5,补充作业,现有一请求分页系统,页表保存在寄存器中。若一个被替换的页未被修改过,则处理一个缺页中断需要8ms;若被替换的页已被修改过,则处理一个缺页中断需要20ms。内存存取时间为1s,访问页表的时间可忽略不计。假定70%被替换的页被修改过,为保证有效存取时间不超过2s,可接受的最大缺页率是多少?,活咳怎童颖奈备冬决樊舅缨驻皿铡若盒拍闽兼崖胚屎缴限册道起挚馏礼隔计算机操作系统 李翠霞 os4_5计算机操作系统 李翠霞 os4_5,作业:P159 19,22,欺褂剃墒撬饥源冷甩椿征西轴辣檬烬递长膘烃壁翅痹真凿妨矽洲揖牵舅之计算机操作系统 李翠霞 os4_5计算机操作系统 李翠霞 os4_5,