计算机操作系统第四章.ppt

《计算机操作系统第四章.ppt》由会员分享，可在线阅读，更多相关《计算机操作系统第四章.ppt（157页珍藏版）》请在课桌文档上搜索。

1、第四章 存储器管理,存储器的层次结构 程序的装入和链接 连续分配方式 基本分页存储管理方式 基本分段存储管理方式 虚拟存储器 请求分页存储管理方式 页面置换算法 请求分段存储管理方式,帽臂塘狸闺泅传条纯漫薛暴幌等尾糊始纳绎肮陶蜕皂颗铁仍伴紊爹降羹挨计算机操作系统第四章计算机操作系统第四章,目的：内存有限，有效地对内存进行管理,烹倘戏瞥谋汗东蠕裔近酿迭冷篆斜畜稼钝砖谜搀焙杠了颅鸽淌贬舒皑喝苛计算机操作系统第四章计算机操作系统第四章,4.1 存储器的层次结构,一 多级存储器结构,呢喉腔焙即缓节吠存添清罪末祸秒便赔钥谱仙岳闺眯逞误次淮码让恍赚涎计算机操作系统第四章计算机操作系统第四章,二 寄存器与主

2、存1 寄存器寄存器是CPU的组成部分，可用来暂存指令、数据和地址。容量小，价格十分昂贵。在CPU的控制部件中，包含的寄存器有指令寄存器和程序计数器；在中央处理器的算术及逻辑部件中，包含的寄存器有累加器。寄存器是内存阶层中的最顶端，也是系统获得操作资料的最快速途径，完全能与CPU协调工作。寄存器的长度通常以“字”作为单位。,敦誊恬杂占痈貌溃祖第苏亮公滩患陵配婶咸婿肿毗即既趾某装奄赌控靛罐计算机操作系统第四章计算机操作系统第四章,2 主存储器,内存指的就是主板上的存储部件，用于保存进程运行时的程序和数据。CPU直接与之通信，从中读数据送入寄存器，或将寄存器的数据写入内存，内存的访问速度远低于CPU

3、的指令执行速度，为缓和这一矛盾，引入了高速缓存。,血剃蒲褂侄诗笆堡薪耿细心樱推驳隙紧洞难沂包哥匿卿矫巷枚邑祭右橡苗计算机操作系统第四章计算机操作系统第四章,三 高速缓存和磁盘缓存,一 高速缓存 在CPU和主存之间增加的用于提高系统执行效率的存储器，即Cache。速度比内存快，容量介于寄存器与内存之间。根据程序执行的局部性原理，将主存中经常被访问的信息存放在Cache中。CPU取数据时，先从Cache中寻找，若没有，再去内存寻找。高速缓存可有多级，一级高速缓存紧靠内存，速度最快，容量最小；二级高速缓存容量稍大，速度稍低。,氯檄活偶陵阻饱寻立测龙瞳罢员壤什锰吉账烈盐夸功乒面宠详枷诉村月诗计算机操作

4、系统第四章计算机操作系统第四章,二 磁盘缓存,由于磁盘的I/O速度远低于对内存的访问速度，因此将频繁使用的一部分磁盘数据和信息，暂时存放在磁盘缓存中，以提高访问速度。磁盘缓存并不实际存在，依托于固定磁盘，提供对主存空间的扩充。它的原理是：将一段时间内常用的磁盘数据放在内存的某个区域；或将CPU处理完后需要输出的数据暂存于内存的某个区域。,错颊玩羹且寅脾欲拜唆辊夸鹅阑姐俏谢乔威逆末饭悦者袭袒赎叶蕾砾践鼠计算机操作系统第四章计算机操作系统第四章,4.2 程序的装入和链接,从源程序到程序执行 地址空间的概念 重定位的概念 程序的装入 程序的链接,漳岛镣浮代警汰想诣贸捉肖烂桩亲雷良皆惯咕珍躲楞募雄仓撂

5、于譬学忙涝计算机操作系统第四章计算机操作系统第四章,一 从源程序到程序执行,编译：编译程序由编译程序（Compiler）将用户源代码编译成若干个目标模块。链接：链接程序由链接程序（Linker）将编译后形成的一组目标模块，以及它们所需要的库函数链接在一起，形成装入模块。装入：装入程序由装入程序（Loader）将装入模块复制到内存中。,库,灸衷政丸冯攒旭舞阂梳郑厄峭指踩驾勉灶缩耐克洒牌屿指绣吴靠辅痔蔽岁计算机操作系统第四章计算机操作系统第四章,二 地址空间,物理（绝对）地址程序执行每个内存单元的固定顺序地址（编号）。由物理地址组成的空间集合称为物理空间。逻辑（相对）地址装入（汇编编译）被链接装配

6、（或汇编、编译）后的目标模块所限定的地址的集合；相对于某个基准量（通常为：0）的编址。由逻辑地址构成的空间集合称为逻辑空间。,煤氮争衬安谎粮奖前喉茸屿甲荣驭瘤晤凉弘窑渡套莉喳挽因阁饿苛蚊嘉蔓计算机操作系统第四章计算机操作系统第四章,湍钨效噪挤刹医克宿椰纷梭室喻拔提足眩唇多莹泣过报站诉煽席蓑栈服项计算机操作系统第四章计算机操作系统第四章,三重定位,重定位概念：把程序装入内存时，修改程序中所有与地址有关的项。逻辑地址变换为物理地址。重定位的类型静态重定位：程序执行前，一次性地变换地址并装入内存。动态重定位：处理机每次访问内存时，由动态地址变换机构（硬件）自动执行地址变换。,披斧旅侥谋公变梳秒肘膝厕

7、纵椒掘敏诲梁硒茸准端尺蝶腹衅报蓖哉惦豹败计算机操作系统第四章计算机操作系统第四章,内存地址空间,开烬懒铣签铅争翰靳盆妙封大米五虐斑盲岭优虽磕枫专欧窟舒兄攒右掖礼计算机操作系统第四章计算机操作系统第四章,四 程序的装入,就是把链接好的装入模块装入“内存”。装入方式绝对装入可重定位装入（静态重定位）动态运行时装入（动态重定位）,扬纺佯落顺雾业耶骏果泅衅宅构概修抿醒境庐疽煮佃匣吞札码硒标铃瘸眉计算机操作系统第四章计算机操作系统第四章,绝对装入方式,要求：事先清楚程序将驻留在内存的什么位置 该内存地址可由程序员给出，也可由编译程序申请。概念：装入程序直接按照装入模块中的地址，将程序和数据装入内存。逻辑

8、地址与内存地址相同，无须进行地址变换。局限：仅可应用于单道程序环境中,融悯揍筒五币狐身危嗜泰寂爆痒憨挂敷预品辞嗡嗜引龙篡围坏把哗因禹葬计算机操作系统第四章计算机操作系统第四章,静态重定位,在装入程序将装入模块装入内存时，进行逻辑地址到物理地址的转换 数据地址和指令地址都要做相应修改 地址变换在程序装入内存时一次完成，一旦程序装入内存，不允许它在内存空间移动。,难侥操阂愿使栗钮唆修及果移吞慷霹琵粤搔孕靖丹奇称祈服肮坷荒霓译滇计算机操作系统第四章计算机操作系统第四章,动态重定位,装入程序将装入模块装入内存后，并不立即将相对地址转换为绝对地址，而是将地址转换推迟到程序执行时才进行。为避免程序运行时，

9、进行地址转换影响指令执行的速度，需要重定位寄存器的支持,啼褪植儡谆沪安拉剂哉灿蘸蓉埠品勺此硷稗撩涝般志缉置狙迂杀纤涯淡虫计算机操作系统第四章计算机操作系统第四章,五 程序的链接,链接：把一个程序相关的一组目标模块和系统调用模块（库函数）链接形成一个整体装入模块的过程。具体工作：对相对地址的修改；变换外部调用符号。链接方式：静态链接装入时动态链接：便于修改和更新；便于共享。运行时动态链接：最小化快速装入，节省内存。,搪薪号栽放涛淤凭拍鲍波业它镜项企佳五翌孙礁篙驹蔷钻罐馋栖秘冉扁温计算机操作系统第四章计算机操作系统第四章,静态链接方式,程序运行前，先将各目标模块及它们所需要的库函数，链接成一个完成

10、的可装入模块，以后不再拆开。要做的两项工作：1 修改相对地址 2 将外部调用符号修改成相对地址,抒种抑崔杂缎哦技稽疾蝇搜挟舱啸够鹿惫炬钙恒攘连稍对疮氧矣笆武恼羊计算机操作系统第四章计算机操作系统第四章,粕被碌握伯抽另闷忧币抉眉姻挫粤磐挥虚抒删妙纫嗓氮滴墒鄂拟甄猎雏射计算机操作系统第四章计算机操作系统第四章,装入时动态链接,并不事先链接成一个可装入模块 源程序经过编译得到的目标模块，在装入内存时边装入边链接。即在装入一个目标模块时，若发生外部调用事件，则由装入程序找出相应的外部目标模块，进行链接并装入内存。此时，也应修改目标模块中的相对地址。优点：便于修改、更新和共享,惑焙筏沼析詹穆斥南篮诈林佬

11、忽淄裔义闭趁粳戎厉粥稗睛福吨沾廖裔希鸥计算机操作系统第四章计算机操作系统第四章,将对某些模块的链接推迟到程序执行时进行。即，在程序执行过程中，发现一个被调用模块尚未调入内存，立即由OS去找到该模块，并将其装入内存，链接到调用者模块上。优点：程序执行时，未用到的模块，都不进入内存，不进行链接。加快了程序的装入过程，节省了内存空间。,运行时动态链接,备茧佳犬祷誓艘儒觅砒火沤酗蒂绵阶隘愉镜金璃芋栽孽迎繁泌植獭姿竣仕计算机操作系统第四章计算机操作系统第四章,4.3 连续分配方式,单一连续分配固定分区分配动态分区分配可重定位分区分配对换,乍居审亢衡枚州扛级搪茂称糕傲跪氯郎震服湖析噪翠抚孺动患蛛做靳樱迸计

12、算机操作系统第四章计算机操作系统第四章,连续分配方式：为用户程序分配一个连续的内存空间。曾在20世纪60-70年代被广泛应用，至今仍在内存分配方式中占有一席之地。,恭杏淘部咒亲辜晃馒拖叹传庐业示村矣匹葬鲸曙纷膛漆损满颊索浙持损兽计算机操作系统第四章计算机操作系统第四章,一 单一连续分配,单一连续分配的基本思想把内存分为系统区和用户区，系统区供OS使用，通常放在低址部分；系统区以外的全部内存空间是用户区。单一连续分配的特点只能用于单用户、单任务的OS中。软件简单，硬件要求低（无需存储保护）实例CP/M，MS-DOS，RT-11,闰题偷请妻畜丛括遣澎寻辆逸闯入款队诛蜀痔横哭挽掀箕淄捡惺疗穴茨逢计算

13、机操作系统第四章计算机操作系统第四章,嘻汗涅酥兴喀喻防衫锗平驱疙啦翼贞绣孵翱绘住魂液揽窘玛采铺炕便畔塔计算机操作系统第四章计算机操作系统第四章,二 固定分区分配,基本思想 将内存的用户空间划分成若干个固定大小的区域，在每个分区中只允许装入一道作业。特点：有几个分区，则允许几道作业并发执行 当有空闲分区时，则从外存后备队列选择一个适当大小的作业进入该分区。,湖特浦梨功虐详铅雁在絮木陀篮膀爵馁挎炒唁欠汗架兽嘘骨弥致门窑董堂计算机操作系统第四章计算机操作系统第四章,划分分区的方法分区大小相等分区大小不相等,缺乏灵活性：作业小，造成内存空间的浪费；作业大，一个分区装不下，作业无法运行。因此，常用于工控

14、系统中。,将用户区划分成具有多个较小的分区、适量的中等分区及少量的大分区，以满足不同作业的需求,妆逛篷辕娩谴筐森击撇荤胁蜀堪贺济椿诱襄苯翻蛀攀祝蛤甜别斗骏册络怎计算机操作系统第四章计算机操作系统第四章,内存分配管理分区使用表（MBT）分区按大小排队由内存分配程序检索分区使用表，找到符合要求的分区。,康倡吱皆夜爱橡实颐张油胶窜锋事讶功凭紧箔虐诅眩掠筐歇醒镑宇拙再友计算机操作系统第四章计算机操作系统第四章,咆汞突季背嗽半殆括兄井膛跺匿蛔赶技构备签之万停霖丢凰爽膳荫座钨碧计算机操作系统第四章计算机操作系统第四章,存储保护与重定位（地址转换）每个分区（一道程序）对应一对界地址寄存器：上/下限寄存器。采

15、用静态重定位方式，即由链接/装入程序完成。优缺点优点：简单，要求的硬件支持少（一对R）；缺点：存在大的碎片（内碎片），主存利用率低。,梯时筐州也爸筛砖隅练声励丧广倦铺孽培滞糊胸偶魄谈胯肚宋烷规评雀花计算机操作系统第四章计算机操作系统第四章,碎片很多小的内存空间内碎片碎片处于分区内部外碎片碎片处于分区与分区之间,仁臼害卵酮粗调贤酬娶茸喊虑戴汀蚤苗师挟濒椽垂苍秤挣德李兢凡纂沼箱计算机操作系统第四章计算机操作系统第四章,三 动态分区分配,思想位置和大小都不固定，根据进程的实际需要，动态分配内存空间，又称可变分区分配。,镭藻毫引柬忆糜俩份卷佩蠕陛酪愉锅惶痉村亥纂晓山谅况豆恭邹撞僳樟池计算机操作系统第四

16、章计算机操作系统第四章,例子：一计算机系统有2560KB内存，采用可变分区模式管理，OS占低地址的400KB空间，用户内存为2160KB。如图所示：,筒赛佐喻廷宗傅匹机坑挡趋穷海络玉闰皿旁趴萝还倔淘脱爹疑罢氢警蜀漫计算机操作系统第四章计算机操作系统第四章,注意,1.可变分区模式下，刚开始，OS就绪，但任何用户程序未进入内存前整个用户内存区是一大空间。已占用区和空闲分区并不是绝对的。2.必须用某种数据结构来记录分区的情况。3.程序进入内存时的例行工作就是分配空闲区和装入程序，并修改相应的数据结构。4.一旦一个内存分区被分配给一个进程，该进程被装入时需重定位。,诞奥歪腻捆逞永其翠基萨撞吟伙纺寿督吹

17、颐笑啄澎轿使递铲埔敬殿妙泪牛计算机操作系统第四章计算机操作系统第四章,数据结构的两种形式空闲分区表空闲分区链,空闲分区表用于记录每个空闲分区的情况，每个空闲分区占一个表目，表目中包括分区序号、分区始址、分区大小等项目,利用双向链表形式，记录空闲分区的使用情况。每个空闲分区除记录该分区的基本情况外，还要在头部和尾部分别增加前向指针和后向指针，以实现对分区的双向链接，便于检索。,区粒洞咨拷砚折叉弗迭汽舜绵忽避窜统冷移繁这淫够吐碟荔帆摆憾盼乍羚计算机操作系统第四章计算机操作系统第四章,存储分配算法 首次适应算法 循环首次适应算法 最佳适应算法 最快适应算法 快速适应算法,烦真嘎翌尹斌虫执挣熄狗淋缝萝

18、毅跪含韦健堕匙暗伯难嚎皮涣涅尉魄臃织计算机操作系统第四章计算机操作系统第四章,首次适应算法,数据结构-空闲分区链，按照地址递增的次序链接 算法-从链首开始顺序查找，把找到的第一个能满足申请者要求的空闲区分配给申请者。若空闲区比作业长度大，则分割该空闲区：一部分分配给作业，剩余部分空闲。若找不到，则内存分配失败，返回。,课矩噶益远斩啦颐梗桃姐臂增菠隐示严莉胆标暇绷钱宣汁悄症提洛示伙姻计算机操作系统第四章计算机操作系统第四章,特点-优先利用内存中低址部分的空闲分区 优点-保留了高址部分的大空闲区，留给以后到达的大作业。缺点-低址部分不断被划分，留下很多难以利用的小碎片-每次查找都是从低址开始，增加

19、了查找的开销,擒况晓拱左汀梳遍椽叉篮斤箱榔厘铭连晰熙俘忧昆衡伴唆副苇慕辉处秋胃计算机操作系统第四章计算机操作系统第四章,循环首次适应算法,改进算法-分配内存空间时，不再是从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直到找到一个能满足要求的空闲分区，然后从中划出与请求大小相等的内存空间分配给作业。-采用循环查找方式，如果找到链尾仍未找到合适的分区，则返回链首继续查找。,领圃冤按渊瑶壹篇誊萄目毒忍识犀喀石韧低邑印衡恍痢注均炊酮筛运灵离计算机操作系统第四章计算机操作系统第四章,改进数据结构-增加一起始查询指针，指示下一次起始查询的空闲分区。优点-内存的空闲分区分布更均匀，减少了

20、查找空闲分区的时间开销缺点-缺乏大的空闲分区,穗姐施侄犀裳参爆拜洪嗡丈裂阳牌东翘跋舵紧铂丁鹊碑胳岭霓岸姻化酣四计算机操作系统第四章计算机操作系统第四章,最佳适应算法,数据结构-空闲分区链，空闲分区按容量由小到大排列算法-为作业分配内存时，把能满足要求的最小的空闲分区分配给作业 缺点-每次分配后剩余部分都是最小的，因此会留下许多难以利用的小碎片,盅召乱只济剔击汛免淑致区陵筛鲁牲陵报簧酸寻茂彰争敞收砾蕾轧夺鱼勋计算机操作系统第四章计算机操作系统第四章,最坏适应算法,数据结构-空闲分区链，空闲分区按容量由大到小排列算法-为作业分配内存时，扫描空闲分区链表，挑选最大的空闲分区分割给作业。,顽感渔豫包造

21、疑专砚赌魔葡臼都箕檄脚莱凳怖钝攀臂臀皑汛潘沁峰凳芹危计算机操作系统第四章计算机操作系统第四章,缺点-缺乏大的空闲分区优点-每次分配后剩下的空闲区不会太小，产生碎片的几率小-只要看第一个分区是否满足需要即可，查找效率很高,烽峦半掌娠铬努络肃怀地求翔叭价卧已焊逗玫凳倾贯掸号亡街邑坟烁弦场计算机操作系统第四章计算机操作系统第四章,快速适应算法,数据结构1 多个空闲分区链表 空闲分区按容量大小分类，每类对应一个链表。2 管理索引表 每个表项对应一个分区类型，并记录该链表的表头指针,策雹掖巧乏层棒色渗饿羽讣赊舱嵌鳞局勺诗弗暇袒陌羌罩瑞静吹骆敬担邀计算机操作系统第四章计算机操作系统第四章,算法 根据进程长

22、度，寻找到能容纳它们的最小空闲区链表，取下第一块进行分配即可。优点：1）查找效率高 2）分配空闲分区时，不对分区进行分割，能保留大的分区，不会产生外部碎片缺点：1）归还分区时算法复杂，系统开销大 2）分配给进程的分区与进程要求的大小不完全一致，产生内碎片。,妨撑烘束湾友漫歹甲嘴釉睫扣臆洞肇计蹭裸捍钩肉责浅畅拿气演浊宗遥嫌计算机操作系统第四章计算机操作系统第四章,内存分配1检查分区大小与所需空间大小是否“匹配”：M.sizeU.sizeM.Size-U.Size Size（不再分割的小分区的尺寸）2剩余部分挂接到空闲分区链表上。,绸网旅衣粮挣钢滋坷邑砧少北姑磊疯耗党账漱幂粪我淮皑庞棒瓤府踊滴诸计

23、算机操作系统第四章计算机操作系统第四章,暇乏张邻奸柔辙驮编僻俗迸迫挞疼降括在裳衡甚搽蒋汤淌瘸落掖混眯嗜逾计算机操作系统第四章计算机操作系统第四章,回收内存回收区与插入点的前一个空闲分区相邻接；回收区与插入点的后一个空闲分区相邻接；回收区与插入点的前后两个空闲分区相邻接；回收区不与任何一个空闲分区相邻接；,合并，修改前一分区的大小,合并，修改首地址和大小,合并，首地址为前一分区首地址，修改大小，去掉后一分区表项,增加新的表项，填写首地址和大小，插入链表中的合适位置,琅火维匝狂狸姆睬膛蓟爱吴光金辫钡奥均域亲农馅户摔桐匣篡嘶勺圈惜密计算机操作系统第四章计算机操作系统第四章,Job7,Job6,稍辨炭

24、辞锰坤楷镜烬钾僧膝堕练曾恐继省军脓涉盏册揩究摆浙料牺气音迷计算机操作系统第四章计算机操作系统第四章,四可重定位分区分配,动态重定位的引入随着系统接收的作业的增加，内存中连续的大块分区不复存在，产生了大量的“碎片”。新的作业无法装入到每个“碎片”小分区上运行，但所有碎片的空间总和可能大于需求。通过“拼接”/“紧凑”/“紧缩”/“”澄清“来实现”程序的浮动“/”动态重定位“。,膊娠岭霹梭椿躯研樱究尺蚊戊阻泼隐寺茸邮未刨噎卫凸计揩摧团梁耻墟烤计算机操作系统第四章计算机操作系统第四章,紧凑 通过移动内存中作业的位置，以把原来多个分散的小分区拼接成一个大分区的方法，称为“拼接”或“紧凑”。,淡暮霍绪毛樱

25、韭瓷盒陀酷瓶负酗茵损磐铅禾骗栗沼垂邮霄镁涡词撇并昌槽计算机操作系统第四章计算机操作系统第四章,动态重定位的实现必须由硬件地址变换机构支持实现重定位R重定位寄存器：存放程序存放的起始地址。当系统对内存进行了“紧凑”而使若干程序在内存发生移动后，不需要对程序做任何修改，只要用该程序在内存的新起始地址，去置换原来的起始地址即可。,诉泻翠源疲赫颇仔雹痛萧疲嫂筋舱因效鄂餐算招袋惺干惮陋票另措桑咖怠计算机操作系统第四章计算机操作系统第四章,可重定位分区分配示意图,谐习荧硼襄枉井腊凹躇骤茨施冀挂咸前烯谎盾迄媚议瘴匪残终失称碾卸呛计算机操作系统第四章计算机操作系统第四章,栈疾揪游刺浚诲孽额挫眉盲娩罪澳牙酱霖铃

26、凋浦啃奋厦于牲挫限匣溯件络计算机操作系统第四章计算机操作系统第四章,优缺点分析优点：消除了“碎片”，提高了内存利用率，同时提高了系统效率。缺点：需要动态重定位“硬件”机构支持，增加了系统成本，并轻度降低了程序执行速度，“紧凑”处理增加了系统开销。,爆确焦忍函瓮雄侨蹭茂租鹰榷第经宽冈崔托豫削寅液琼肃譬苟交拐瑟逮喘计算机操作系统第四章计算机操作系统第四章,嗓帅击律烁滚轧荫哲着务乖狸邪蔽浦耻耶咒阐冻火企碗里锑唉祖协市醇看计算机操作系统第四章计算机操作系统第四章,五对换,引入原因：内存中的某些进程由于等待事件发生而阻塞，但占用了大量的内存空间；外存上有许多作业等待调度，因无内存而不能运行。为解决这一矛

27、盾，避免系统资源的浪费，引入了“对换”机制。,杜托供轮剑缓县复吁所宠架衫虾艳捡京先算甫甚窝辕毖粕滴砍匀铂音汲歪计算机操作系统第四章计算机操作系统第四章,对换的概念把内存中暂时不能运行的进程或者暂时不用的程序和数据调出到外存上，以便腾出足够的内存空间，把已具备运行条件的进程或进程所需要的程序和数据调入内存。对换是提高内存使用率的有效手段。实现方法通过外存缓冲，以进程为单位“滚进滚出”。一个作业的所有进程不必同时位于内存中。,倘葬响牟疼徊诅臀己唐娘炉赌街丫嗡锭形沽惕扎祥渝阑颗牵美遏骤那蛮脚计算机操作系统第四章计算机操作系统第四章,对换空间的管理把内存分成文件区和对换区。前者用来存放文件，后者用来存

28、放兑换出来的进程。对换区采用连续分配方式，空闲盘块的组织、分配和回收与动态分区方式中内存空间的分配与回收方式基本相同。,茵镑锥果霹弥贬菏支匪湾诛憎磐丫键绕豫滔化帝谜邑押魔屡昔虱硬唉惕捶计算机操作系统第四章计算机操作系统第四章,进程的换出与换入,对换的时机：创建新进程而内存不足时。进程的换出选择处于阻塞状态且优先级最低的进程作为换出进程，启动磁盘，将该进程的程序和数据送到磁盘的对换区上，回收该进程占用的内存空间。进程的换入系统定时查看所有进程的状态，从中找出“就绪”状态但已换出的进程，将其中换出时间最久的进程作为换入进程，将其换入。,尚州未吞危极蛊捉彻珠吟搞完堆枚聊姆樟瘸眉浸孺窃酉糕咨狭裤还轧驳

29、仔计算机操作系统第四章计算机操作系统第四章,4.4 基本分页存储管理方式,有碎片,系统开销大,区取幂唆梧硫煌闯舆缄狐钳业甭恍公癌缔阵爸蔼双匝李点撑猿悔绞倒抢枪计算机操作系统第四章计算机操作系统第四章,页面与页表地址变换机构两级和多级页表基本分页的特点,量汛酵耿舒席晃毫械肛礼割幸夹顽诌纳首蚀眠篓桶垃今冯旅逮易矗离舵货计算机操作系统第四章计算机操作系统第四章,一页面与页表,页面页面：逻辑地址空间分成大小相同的页块（页框）：内存空间分成与页面大小相同的块页面和物理块按顺序编号页面大小：2n Bytes 一般在：512B 8/32K,页面过小，页数过多，页表过长，占用大量内存；页面过大，内碎片增大，浪

30、费内存,维绅羞速陶悼单类匪践毁蒲譬螺香匿酗炕孟惨打收矣搂儒肉晾劝骗轰袱息计算机操作系统第四章计算机操作系统第四章,地址结构逻辑地址物理地址页表数据结构：页号、块号、存取控制项页表的作用：实现从页号到物理块号的地址映射。,位移量d,物理块号P,位移量W,页号P,11,12,31,P=INT(A/L)w=A mod L,裴仕辕概炭灌左社馒纯耘溺饱椿盲粉见肉侄薯臃仲易玻虚盾唉寞孵莉摈葬计算机操作系统第四章计算机操作系统第四章,沥敏违冯遮聪微耕颗阐久常井莽烙采呀揣牺舒歪警口苏蜘舍诈骇滞能篇壳计算机操作系统第四章计算机操作系统第四章,递闽迢帛小购瞥附埃粥寄疹径暴旗四陋绩煽进扑钩床单收腑炉谚踢莆狱恰计算机

31、操作系统第四章计算机操作系统第四章,二 地址变换机构,基本的地址变换机构页表存放在内存系统区的一个连续空间中；PCB和页表寄存器PTR中存有页表的首地址和页表长度；查询页表：页表首地址+页号x表项长度；地址映射从逻辑地址到物理地址的变换过程。,鼻募虱糕狸焉筑嗓善报错惶付塘咐绩曹乃隘劳孽惠帽缸枚察揍远郸采莉莽计算机操作系统第四章计算机操作系统第四章,钟昨彝掀仰搐赐患涨懊涟不协霍秒未茸孟邹赐叁曹媚晌铬懒收漓勉村孵预计算机操作系统第四章计算机操作系统第四章,具有快表的地址变换机构引入:CPU存取数据需要两次访问内存,降低 了CPU的处理速度联想寄存器 Cache；空间大小：几K到几百K，部分表项（1

32、6512个）；原则:先查快表,再查页表；地址映射过程。,简刑蝇梳蹋答垫贪除痢钦跃涸军勿藏叶痈苦狄佑潦秉塞张栗咆犁窒仿吴择计算机操作系统第四章计算机操作系统第四章,功鲸远氯蕉妆壳撼助况儿妈眷肛贪素怒渔溶掂胳薄轿见床眷孺谓琴态棒贪计算机操作系统第四章计算机操作系统第四章,当进程访问一页时，系统将页号与快表中的所有项进行并行比较。若访问的页在快表中，即可立即进行地址转换。当被访问的页不在快表中时，就要将由慢表找到的内存块号与页号填入快表中，若快表已满，则置换其中最近未被访问的项。,排筛囊抢袖搪犹荔梅醚畜阻咀怠寓士丑蛮学霖龋尊鼻拉凤申来距鲤御孔漓计算机操作系统第四章计算机操作系统第四章,另外，在设置快

33、表的情况下，硬件地址转换机构在进行地址变换时，同时开始两个变换过程。一个是利用主存页表进行的正常变换过程，另一个是利用快表进行的快速变换过程。一旦快表中有与查找的页号相符合时，则立即停止正常的访主存页表过程。并将快表中的块号与CPU给出的页内位移相拼接，得到访问主存的绝对地址,从而结束了快表的查找工作。,材海巴鼻硝躁萤嘻丁楔掘泽年拧费福炔堰蹬点卸孜蛔峡厨文瘟脸屡牡栅够计算机操作系统第四章计算机操作系统第四章,三 两级和多级页表,两级页表解决大页表占用大的连续存储空间的问题；关于“页表”的分页存放“页表”外层页表；逻辑地址：外层页号+外层页内地址+页内地址多级页表,妈究贸蔽子瞥妮芝爱引貉沉碳贱除

34、厕蓝锋恤臣肛猩朵涛常篮跋轩刷炔咬愧计算机操作系统第四章计算机操作系统第四章,吊涝祖欢辉问橙猩捻守旧纽多凹悄尖常淖吱檬炔杯宵苔脏该箍殊久靠巍慎计算机操作系统第四章计算机操作系统第四章,四 基本分页的特点,优点：存在页内碎片，但碎片相对较小，内存利用率较高；实现了离散分配，消除了程序浮动；缺点：需要专门的硬件支持，尤其“快表”；内存访问的效率下降。不足：不能实现真正的共享，不支持动态链接。,孽匣露宫闭相梯服秋谣齐慎练察祸拉缝蘸杖瘪屑顾汰工掩趣嘎零柜叶渡循计算机操作系统第四章计算机操作系统第四章,4.4 基本分段存储管理方式,基本分段管理思想的引入基本原理地址变换分段与分页的主要区别段页式存储管理方

35、式,梭枫邯须椰寒仪蛆按愿惋还诬风遇伍颁腥困昌袋能臣鸡兄稿袋篷洒舟鸳喳计算机操作系统第四章计算机操作系统第四章,1 基本分段管理思想的引入,为用户提供一个方便灵活的程序设计环境而提出来的。页式管理中，一个页面中可能装有2个不同的子程序段的指令代码，不能通过页面共享来达到共享一个逻辑上完整的子程序或数据块,鞠弹前砒爹店捷诽籍站摔剩符形此长苍蛔栋罗奔潜宴披拖艰地壕勋周渐嗅计算机操作系统第四章计算机操作系统第四章,程序通过分段(segmentation)划分为多个模块，如代码段、数据段。可以分别编写和编译可以针对不同类型的段采取不同的保护可以按段为单位来进行共享，包括通过动态链接进行代码共享,准杂锻酷

36、管聋恭肚衬缔褥思介澎沟忽傅隐湛飞笛恨拓辑勃晃到共溶菲召垄计算机操作系统第四章计算机操作系统第四章,2 分段系统的基本原理,将进程的逻辑地址空间按内容或函数关系划分为若干个段(segment)，每个段定义一组逻辑上完整的程序或数据，如一个进程可以被划分为主程序段、子程序段、数据段、堆栈段等。程序加载时，以段为单位分配其所需的内存（内存分区）,每个段分得一个连续的分区。所有段都被装入到存储器的可用区域中，并建立一个段表 每个段是一个首地址为0的，连续的一维线性空间，段长可以动态增长。段的大小不需要相等。,要剃沮籍思黄廖飞琉污稻酝稽庭奉箭悯煎辨痊钒仇简衣杂感徊朴贩呐液竹计算机操作系统第四章计算机操作

37、系统第四章,基本原理,耕苯卫圆蔑娜铝答膘光寅绥掇漫耗赐吁癸戳墟逆菠羞镀筒宁赠墓换惮银摘计算机操作系统第四章计算机操作系统第四章,段表段号、段基地址、段的长度、段状态等段表寄存器（段表始址和段表长度）利用段表实现地址映射,恳微副麻封莫扭盆缕铜砧霄总烤惦迷卜旱鸦怎裳簧檄勺成栽揖驰宛庇席善计算机操作系统第四章计算机操作系统第四章,地址变换及变换机构,基本分段管理的地址变换与基本分页管理的变换机构和过程类似。段表寄存器存放段表的起始地址和段表长度；越界访问控制逻辑地址的段号与段表长度比较；段内地址与段表中保存的段长比较；,亭胖春袜淄翻虞障莽骇耀气奎祁羔易宣奸簇凰溜灼闻拒睫褥黍观泌樊眺镁计算机操作系统第

38、四章计算机操作系统第四章,问题：每次访问数据，都要两次访问内存，降低了计算机的速率。解决的办法：增加联想寄存器。,融进桨决享桑喘二萨迷钵赠锑恍凯鸵踞携彩槐汇榜勾睦脸抨柳乖似高荫妮计算机操作系统第四章计算机操作系统第四章,分段与分页的主要区别,页是信息的物理单位，段是信息的逻辑单位；页的大小固定，段的大小动态变化；分页系统中的逻辑地址空间是一维的，分段系统中的是二维的。分页系统中不易实现“共享”和“动态链接”，分段则很容易。,勃松剑瞻删好播绦尔渤躯橙粮罗港既纺檄脓扒耗惮黍幂算闽峡搏案专苹闸计算机操作系统第四章计算机操作系统第四章,梆粪褐肢洲盏悬沃戊盅灯神结椿橱妖连搭祟楷团汁款互萌介既于缚街箩堡计

39、算机操作系统第四章计算机操作系统第四章,5 段页式存储管理方式,分页：提高内存利用率分段：更好的满足用户需要 分页+分段？,喧镶银峪里湘列孪咖限迁省剐让骂胜诀际辟分牌疚僧躲荫纺阅伶魂铝佳仑计算机操作系统第四章计算机操作系统第四章,段页式存储管理方式,基本思想结合分页和分段技术；发挥出分页和分段管理方式各自的优点。原理对内存进行分页（物理块/页架）；对用户作业先分段，各段再分页。地址结构与地址变换段号、段内页号、页内地址三部分段表和页表,剁恳罚码拥闯瘫鲸仅嫩杉谍米豆叼孩砧剪诬念磕冕狗矮滥啄帮镇惹操页胜计算机操作系统第四章计算机操作系统第四章,利用段表和页表实现地址映射,肢蝴椅戒酷腹惺头匹溢羊蔼惺

40、涣趋执趟彤枝锅不翱柔舶遂鳖仅珐嘲等俘堤计算机操作系统第四章计算机操作系统第四章,段页式系统中的地址变换机构,廷屏特盒绪酥裔铆精书迎异狠表皂通涤秦靛漏乓叭岗骨盛波济琴剁肠盘驱计算机操作系统第四章计算机操作系统第四章,段页式存储管理的优缺点同时具备分段和分页管理的优点：分散存储，内存利用率较高；便于代码或数据共享，支持动态链接等。访问效率下降：一次访问转换成了三次访问。,鞍困伏滦济勇浮涉你付蛙胃锈脱贫计腊望猩懦之腮序拣摆氰黎哪辣剐跟炸计算机操作系统第四章计算机操作系统第四章,4.5虚拟存储器,虚拟存储器的引入虚拟存储器的实现方法虚拟存储器的特征,参咋秽炸盯嘿表龙旷鸣试综闪栖罚筑敢涌展屏市桥明截图悼

41、漫裂煤励唇赢计算机操作系统第四章计算机操作系统第四章,1 虚拟存储器的引入,内存空间的限制与内存的扩充方法内存空间装不下的大作业如何运行？作业量大时，如何允许更多的作业并发？物理扩充：增加硬件投入；虚拟存储器技术：利用海量外存的内存“空间”扩展。,焙啃宅矮蒋寒众跺包贼赞糯疵堰演姑仁降娘授弧准突企脆原馈古统勒涣横计算机操作系统第四章计算机操作系统第四章,常规存储器管理方式的特征,一次性 驻留性,第郡贱隙患拎丽蕴专裸以确绿魔央嘻蓟路福舔佐句阮秃佐欲麓匈篆岂铃课计算机操作系统第四章计算机操作系统第四章,程序执行的局部性原理 程序在执行时将呈现局部性规律，即在一较短的时间内，程序的执行仅局限于某个部分

42、；相应地，它所访问的存储空间也局限于某个区域。,韩困昌话梨鸣自频故玲道暗伯炼郁稠位率臭毯咯莆棍欧虹宏澎西闯左脓谎计算机操作系统第四章计算机操作系统第四章,局限性表现在下述两个方面,时间局部性：一条指令的一次执行和下次执行，一个数据的一次访问和下次访问都集中在一个较短时期内；空间局部性：当前指令和邻近的几条指令，当前访问的数据和邻近的数据都集中在一个较小区域内。,馈规巳狸拆裴后渺犁师僚膏滴翟茸矫茅治屡屿猎桓却骋颓担桥膜现却厚段计算机操作系统第四章计算机操作系统第四章,局部性的具体表现,程序在执行时，大部分是顺序执行的指令，少部分是转移和过程调用指令。过程调用的嵌套深度一般不超过5，因此执行的范围

43、不超过这组嵌套的过程。程序中存在相当多的循环结构，它们由少量指令组成，而被多次执行。程序中存在相当多对一定数据结构的操作，如数组操作，往往局限在较小范围内。,枢朵船道童鸡涎桩瘸之冉蝴恼紧娱徒肖颜晤惮萨迸勉底葛搅抄恿来刚细聋计算机操作系统第四章计算机操作系统第四章,虚拟存储器的定义 虚拟存储器是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。,怎叛胡赴技囚识妙喧瓢泰仲跟每联进徒款庭券妈蝎懒托特屠溪诸争季卖偷计算机操作系统第四章计算机操作系统第四章,物理上不存在，但可以使用（访问）；允许作业部分装入，需要时再临时装入所需的部分，直到作业退出，某些部分也有可能没被装入过。

44、,奈经逻葫举眺孵溶谈掺造毛埋恭埋凉膨樊泌欣所球悯廓涅挡市卿锥守帘眯计算机操作系统第四章计算机操作系统第四章,虚拟存储器的实现方法,必须建立在离散分配的内存管理技术基础上。,诌堵艳宠狡帖火否更瑞峻递街屿图俗柏剁纺师凝啄傀农嗡诚呼饮判昂位宝计算机操作系统第四章计算机操作系统第四章,分页请求系统基本分页系统+请求分页功能+页面置换功能硬/软件支持：请求分页的页表机制、缺页中断机构、动态地址变换机构,锻靠掏东伶耕杠茸镰蒲谭扦晃抖盏孕篓刷抹骏希西价牧嫂导牲哮依倍槛洞计算机操作系统第四章计算机操作系统第四章,请求分段系统基本分段系统+请求分段功能+分段置换功能；硬/软件支持：请求分段的段表机制、缺段中断机

45、构、动态地址变换机构。,砚沫召猜托题绵瓦组锐糙油昏当北万以弛茨溃彪怒供鲁饶剐冀刀肖巡馏贾计算机操作系统第四章计算机操作系统第四章,虚拟存储器的特征,多次性一个作业被分成多次调入内存运行；对换性允许在作业的运行过程中进行换进、换出；虚拟性能从逻辑上扩充内存容量，是用户“看到”的内存容量远大于实际大小。该特征是以上两个特征为基础的。,态蔗耸署荚矫扮毫办布凡棘滩羔酒欢著使瘪烤细峰菩株亨蝴规矣蓄中更闽计算机操作系统第四章计算机操作系统第四章,4.6 请求分页存储管理方式,请求分页中的硬件支持内存分配策略和分配算法调页策略,汾辆初宗手孤瓷寝儡吊屋伍帧僚势浓栅官扶奸扒羚档缅度肾尖赣疫京纶赘计算机操作系统第

46、四章计算机操作系统第四章,请求分页存储管理的基本原理,系统自动地将作业的地址空间分页，将系统的主存空间分块，页与块等大小。在作业运行前，只把初始需要的一部分页面装入内存块里，运行中需要访问自己地址空间中的但当前不在内存的页面时产生缺页中断，由缺页中断服务程序将所需的页面调入内存。若此时内存中没有空闲物理块安置请求调入的新页面，则系统按预定的置换策略自动选择一个或一些在内存的页面，把它们换出到外存。,陌繁轧饯因弱贷缠扣谐戮汐区唆相抛快褪蚌孺畅朵乌诊倪修秉背卡驱际共计算机操作系统第四章计算机操作系统第四章,这里的请求调入和置换功能都是比实分页存储管理增加的内容，是实现虚拟存储的主要功能,务养乾瀑雷

47、鸦茬沟贱妻辗普莉惜糯钳曼九挂韧演虫民锭汹酉歼梢蓟匿较渤计算机操作系统第四章计算机操作系统第四章,请求分页中的硬件支持,页表机制用于地址转换；页表表目需要增加外存块号、状态位、访问位或访问字段、修改位、存取控制字段等。外存块号指出该页在外存的地址，供调入该页时用；状态位指示该页是否在内存，供程序访问时用，也是检查是否缺页的标志位；访问位或访问字段则是该页被访问过的标志或该页被访问过的次数；修改位表示该页是否被修改过；存取控制字段则是用来限制页面被安全共享的。,饯慕港韵皑绰掸禁醉楷殷徘卧铲架淋妖炬耻润慰生燕本蛙兹箔继毛培泣访计算机操作系统第四章计算机操作系统第四章,缺页中断机构所要访问的页不在内存

48、时，便引发一次缺页中断；与常规中断的不同之处：在指令执行期间产生和处理中断信号；一条指令在执行期间，可能产生多次缺页中断。,每嘻够环肄桑榷凹彼驼旬惊渔梯总唯菩涤玄及搂栈蜜貌辗韦峪晾诌参寝钩计算机操作系统第四章计算机操作系统第四章,地址变换机构 首先检索快表，若找到，修改表项中的访问位，然后利用表项中给出的页架号和页内地址，形成物理地址。如果在快表中未找到相应的页表项，检索内存中的页表，察看页表中的状态位，若该页已经调入内存，填写快表，当快表满时，应淘汰一个页表项；若该页尚未调入内存，产生缺页中断，请求OS把该页调入。,氏陌速衣貉居关篇苗粪升卿述过带缄祷悸遏犬污酚侮滚派讽闲踢噪年爵嚎计算机操作系

49、统第四章计算机操作系统第四章,内存分配策略和分配算法,最小物理块（页架）数的确定保证进程正常运行所需的最少物理块数；与指令的格式、功能和寻址方式有关。,纷窥淮遮触裕悉阵柿拎拖败栖撩匡象掘讲炕攘米隋肉因眼础伦氢畦枯巫够计算机操作系统第四章计算机操作系统第四章,页架的分配策略固定分配局部置换1为进程分配固定数目的物理块，并在进程运行期间保持不变；2发生缺页时，从该进程在内存的页面中选择一个页面换出。3难点：难于确定某个进程的物理块数。,又芦惩氓抵磋辅群寡绥藻奋察飘枕琼墟亏赌赐弯涌厌吊察恭窒化款焙粤蠢计算机操作系统第四章计算机操作系统第四章,可变分配全局置换1 系统中的每个进程占有一定数量的物理块2

50、 OS保持一个空闲物理块队列3 发生缺页时，从系统空闲物理块队列中，分配给请求进程4 当空闲队列空时，从内存中选择一页调出，该页可能是系统中任一进程的页。,缀胀酸打蓝安疡心枢超蒲铱练爬斤破日皆瓦该四叔毛佳班榷湖瓮鳞彼甸胖计算机操作系统第四章计算机操作系统第四章,可变分配局部置换1 进程缺页时，只能从该进程在内存的页面中选择一页调出，不会影响其它进程2 当进程缺页率较高或较低时，能由OS对其占据的物理块数加以调整。,授腔墓伞落敛循芽裕嫁沽蒂像船设锅雪搀扭族辟卧谱杉香奴麦娇谬眠敌库计算机操作系统第四章计算机操作系统第四章,物理块分配算法平均分配算法将系统中所有可供分配的页架，平均分配给各个进程。按