计算机操作系统李翠霞os43.ppt
第四章 存储器管理,主讲：李翠霞办公室：水环楼306电话：0371-63887291E-mail:,钎淀蜗肉绕虞掇殃肥涅姥龄莆钝砂则森画疗政奎顽己撬瞬尼酉咬惹够箭彩计算机操作系统 李翠霞 os4_3计算机操作系统 李翠霞 os4_3,2,Review,单一连续分配方式内存分为两个区域：系统区，用户区。用户区一次只能装入一道程序。固定分区分配方式 将内存用户空间划分成若干个固定大小的区域，在每个分区中只装入一道作业，这样，用户空间分成了几个分区，便允许有几道作业并发运行。有大小相等和大小不等两种分区方式。可以使用分区说明表对存储空间进行管理动态分区分配方式,茫埃俱倦难粕吴考愉账史之坏泞掇势战航赫滁唁赌杖槛苞抠辟戏搀彤防神计算机操作系统 李翠霞 os4_3计算机操作系统 李翠霞 os4_3,3,Review,动态分区分配方式 根据进程的实际需要，动态地为之分配内存空间。数据结构 空闲分区表：每个空闲分区占一个表目，表目中包括分区序号、分区始址及分区大小等数据项。空闲区（块）链表：将所有的空闲区链成一个链表。,空闲分区表,空闲链结构,询奶扩崩甥萨藏蛤在撞骇究模号轩闲簿抨燥螟榨蜘醉诽鼠钢绞顷媳制演尼计算机操作系统 李翠霞 os4_3计算机操作系统 李翠霞 os4_3,4,【动态分区分配算法分类】,顺序搜索法,分类搜索法快速适应算法,分区分配算法,首次适应算法,循环首次适应算法,最佳适应算法,最坏适应算法,丢溢采炸揣旱春睫译贴痰盾嚏足营郴藕贼浊糠窄潞赌擞呀钮宰助斩熬敛涪计算机操作系统 李翠霞 os4_3计算机操作系统 李翠霞 os4_3,分区分配操作,从头开始查表,检索完否?,m.sizeu.size,m.size-u.sizesize?,从该分区中划出u.size大小的分区,将该分区分配给请求者修改相关的数据结构,返回,返回,继续检索下一个表项,将该分区从链中移出,Y,N,Y,m.size表示空闲分区大小,u.size表示请求分区大小,size表示事先规定的不可再分割的剩余分区大小,图4-7 内存分配流程,Y,N,N,座孙舅嗜课渍熙铝菜宰皮均见珠扩乡帐槐损放涩适悄罚梧哈黑满社呐敏敖计算机操作系统 李翠霞 os4_3计算机操作系统 李翠霞 os4_3,6,回收内存,烁删燃识阂帐亏绝硒板译每拙砒茧予戳屠腕捞啊玩盛倾抠戎一迈慰技湾酝计算机操作系统 李翠霞 os4_3计算机操作系统 李翠霞 os4_3,7,4.3 连续分配方式,刹剑罚肤脑甜插牲物棋肪禹羽破偏袒垂次嗽怕厘笨期绚肆碰繁豢佳悼码角计算机操作系统 李翠霞 os4_3计算机操作系统 李翠霞 os4_3,8,固定分区限制了活动进程的数目，内存空间利用率很低。动态分区方式算法复杂，回收空闲分区时需要进行分区合并等，系统开销较大。伙伴系统是两者之间的折衷。,思想：无论已分配分区或空闲分区，其大小均为2的k次幂，k为整数，1km，其中：21表示分配的最小分区的大小，2m表示分配的最大分区的大小，通常2m是整个可分配分区的大小。,系统开始运行时，是一个大小为2m的空闲分区。在系统运行过程中，由于不断地划分，可能会形成若干个不连续的空闲分区。将这些空闲分区根据分区的大小进行分类，对于每一类具有相同大小的所有空闲分区，单独设立一个空闲分区双向链表。这样，不同大小的空闲分区形成了k（1km）个空闲分区链表。,咽挽砂淮汲继赫夯耙痰旗厨族钒来于枯矛窑姥怖三翌茬厚践搏眩巾旭赚溪计算机操作系统 李翠霞 os4_3计算机操作系统 李翠霞 os4_3,9,2KB,4KB,32KB,分配时，如果需要16KB,32KB,16KB,回收时，过程相反,间曹箔例创抖斧伯躺哉愈呕咸夕冈砒判水紊谁量羊折讯袜翟苟噶烽奄玖握计算机操作系统 李翠霞 os4_3计算机操作系统 李翠霞 os4_3,10,2KB,4KB,32KB,分配时，如果需要8KB,32KB,16KB,8KB,回收时，过程相反,史蒜柳考烷粗脆奖捎加俐炭焕筑签烯殴枫窄许火纤窜剐赁猪狈多怕扩帜诉计算机操作系统 李翠霞 os4_3计算机操作系统 李翠霞 os4_3,11,分配时：当需要为进程分配一个长度为n的存储空间时，首先计算一个i值，使2i-1n2i，然后在空闲分区大小为2i的空闲分区链表中查找。若找到，即把该空闲分区分配给进程。否则，表明长度为2i的分区已经耗尽，则在分区大小为2i+1的分区链表中寻找。若存在2i+1的一个空闲分区，则把该空闲分区分为相等的两个分区，这两个分区称为一对伙伴，其中的一个分区用于分配，而把另一个加入分区大小为2i的空闲分区链表中。若大小为2i+1的分区也不存在，则需要查找大小为2i+2的空闲分区。若找到则对其进行两次分割：第一次，将其分割为2i+1的两个分区，一个用于分配，一个加入到大小为2i+1的空闲链表中；第二次，将第一次用于分配的空闲区分割为2i的两个分区，一个用于分配，一个加入到大小为2i的空闲链表中。依此类推。,回收时：一次回收可能需要进行多次合并，如回收大小为2i的空闲分区时，若事先已存在2i的空闲分区时，则应将其与伙伴分区合并为大小为2i+1的分区，若事先已存在2i+1的空闲分区时，又应继续与其伙伴分区合并为大小为2i+2的空闲分区，依此类推。,祝榜蜜剐托拐贩高刺气蝶簿匆坟弯痒淡漏让表了骋柏眉垫孜需牛咒旺凛息计算机操作系统 李翠霞 os4_3计算机操作系统 李翠霞 os4_3,12,在伙伴系统中，其分配和回收的时间性能取决于查找空闲分区的位置和分割、合并空闲分区所花费的时间。回收空闲分区时需要合并，时间性能比分类搜索算法差，但比顺序搜索算法好。空间性能优于分类搜索法，比顺序搜索法略差。,常用于多处理机系统。,士捆犀叉羚泥佑家濒笼屠撑仁歹扫娟师裔渡模烁厂厚等赖灾胳豢福吕鞍绰计算机操作系统 李翠霞 os4_3计算机操作系统 李翠霞 os4_3,13,哈希算法利用哈希快速查找的优点，以及空闲分区在可利用空间表中的分布规律，建立哈希函数，构造一张以空闲分区大小为关键字的哈希表，该表的每一表项记录了一个对应的空闲分区链表表头指针。分配时，根据所需空闲分区大小，通过哈希函数计算，即可得到在哈希表中的位置，从中得到相应的空闲分区链表，实现最佳分配策略。,0 1 2 3 4 5 6 7,哈希函数为：Hash(x)=x mod 8,垮帮僳沮救晃海电尖们峨乞斡庐直耙典室呀碗壹冯庙渤糟苯蒜焚懂伯洞刹计算机操作系统 李翠霞 os4_3计算机操作系统 李翠霞 os4_3,14,在连续分配方式中，必须把一个系统或用户程序装入一连续的内存空间。如果在系统中只有若干个小的分区，即使它们容量的总和大于要装入的程序，但由于这些分区不相邻接，也无法把该程序装入内存。？紧凑或拼接碎片整理,块皆举浴肘膨情菌鹿购朵咽浓锯官赊省垮乱呀希烬犊芭汐缩帜编睁盎勾温计算机操作系统 李翠霞 os4_3计算机操作系统 李翠霞 os4_3,15,若想把作业装入，可采用：将内存中所有的作业进行移动，使它们全都相邻接，这样，即可把原来分散的多个小分区拼接成一个大分区，这时就可把作业装入该区。这种将多个分散的小分区拼接成一个大分区的方法，称为“拼接”或“紧凑”。由于经过紧凑后的某些用户程序在内存中的位置发生了变化，此时若不对程序和数据的地址加以修改，则程序必将无法执行。为此，每次紧凑后，都必须对移动了的程序和数据进行重定位。,紧凑,紧凑前,紧凑后,掺肛枯鸣历卢狂怀颤袁真嘶皱险恼藏糊展辞碍儒垄憎户身腹惠量辐绒样硫计算机操作系统 李翠霞 os4_3计算机操作系统 李翠霞 os4_3,紧凑前,紧凑后,动态重定位的实现,J6 大小为10K,芋遗眨尺蛛某亨睛铃蔗倦慧瀑脖下秽悔担蝉蒂驮恍捣惨普脯扮末欠牙嘱亿计算机操作系统 李翠霞 os4_3计算机操作系统 李翠霞 os4_3,1、硬件支持：增加动态重定位寄存器RR（或基地址寄存器BA）,紧凑前：BA=64k,紧凑后：BA=28k,念赞帕仔强朱秒每庞确蛋视长令搽身酸捉角壮柒尼镶汝窝腥慧昧睹蒲员蚂计算机操作系统 李翠霞 os4_3计算机操作系统 李翠霞 os4_3,动态重定位示意图,LOAD R1,2500,365,0,100,2500,5000,2500,10000,LOAD R1,2500,365,10000,12500,15000,10100,相对地址,重定位寄存器,处理机一侧,存储器一侧,主存,+,睡挫邪赚魄耸升纹吝苍状魔皋尔姨寂逛败请字泥音栅税券撤傣刑搔钱驻邯计算机操作系统 李翠霞 os4_3计算机操作系统 李翠霞 os4_3,请求分配u.Size分区,检索空闲分区链（表）,空闲分区总和u.size？,按动态分区方式进行分配,修改有关的数据结构,进行紧凑形成连续空闲区,修改有关的数据结构,无法分配返回,返回分区号及首址,找到大于u.size的可用区否？,否,否,是,P128 图4-11 动态分区分配算法流程图,唇给撰熊颂本据当帧解晶嚎釉把革任犁陷谚废剿妻酉楚杖服酥亭濒笔唇琉计算机操作系统 李翠霞 os4_3计算机操作系统 李翠霞 os4_3,20,2、软件处理：,需要时再移动,优缺点：解决碎片问题，以便运行大作业。紧凑系统开销大。,3、多重可重定位分区举例,DOS采用了四重可重定位分区,重定位寄存器：CS、DS、SS、ES,四重分区在内存中的位置可以不连续,每个分区（段），在内存中可以移动,回收一个分区马上移动,以在椅匠叙诀内疗隆请哨橡扮腮玩兢变侠俏邓楚娥疙那萝转梯贩围谦移搂计算机操作系统 李翠霞 os4_3计算机操作系统 李翠霞 os4_3,21,矛盾：一方面：在内存中的某些进程由于某事件尚未发生而被阻塞运行，但它却占用了大量的内存空间，甚至有时可能出现在内存中所有进程都被阻塞而迫使CPU停止下来等待的情况；另一方面：却又有着许多作业在外存上等待，因无内存而不能进入内存运行的情况。,解决的办法：引入Swapping(对换)技术。对换：把内存中暂时不能运行的进程或者暂时不用的程序和数据调出到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程或进程所需要的程序和数据调入内存。,吕与歇悬噎剔龙纱赋锚喂寂恼且樱青弄倔藻橇孝棺赵响聊余月即靶还幕仇计算机操作系统 李翠霞 os4_3计算机操作系统 李翠霞 os4_3,22,皮戳氰幌犬绘卞蔓侮承吊喜席移吕延张濒了惯撑宠匙芳本缅纷诉壶迫怎惫计算机操作系统 李翠霞 os4_3计算机操作系统 李翠霞 os4_3,23,对换单位：进程、页面、段 进程（地址空间）整体的换进/换出进程地址空间分为页，暂不用的页面可以淘汰出内存，需要时由缺页中断处理程序调入内存。进程地址空间分为段，暂不用的段可以淘汰出内存，需要时由缺段中断处理程序调入内存。,兼熊讨啪粕黎孝创子井血玖嗣尚屿尾巾铝卧峭喜风儿逊崖亮碰来克绽眨犁计算机操作系统 李翠霞 os4_3计算机操作系统 李翠霞 os4_3,24,【对换空间管理的目标和空间分配方法】追求对换的速度而非空间利用率，文件系统往往追求外存空间的利用率。采用以物理块为单位的连续分配策略（对换时磁头尽量少移动），数据结构和算法类似内存管理中的动态分区算法。二者差异：动态分区管理的是内存空间，对换技术管理的是外存的对换区。动态分区是以字节或内存块作为分配单位，对换技术是以对换区中物理块为单位。,2对换区空间的管理,采用动态分区算法,朔馈畦辽最巨召风排擞救墒扛志确盆紊橱念失铡具砰魂翰杏襟抗驱染蝎焰计算机操作系统 李翠霞 os4_3计算机操作系统 李翠霞 os4_3,25,4.优点：增加并发运行的进程数5.问题：程序换入时要重定位，要有动态重定位硬件支持,3.进程的换出与换入（1）进程的换出 每当一进程由于创建子进程而需要更多的内存空间，但又无足够的内存空间等情况发生时，系统应将某进程换出。其过程是：系统首先选择处于阻塞状态且优先级最低的进程作为换出进程，然后启动磁盘，将该进程的程序和数据传送到磁盘的对换区上。（2）进程的换入 系统应定时地查看所有进程的状态，从中找出“就绪”状态但已被换出的进程，将其中换出时间最久（换出到磁盘上）的进程作为换入进程，将之换入，直至已无可换入的进程或无可换出的进程为止。,劫酉暮光疼嚷颤盂直睬痢栗岔加嘎喉汾晋雨湖肢袖海港场桔踩祭俘零这寐计算机操作系统 李翠霞 os4_3计算机操作系统 李翠霞 os4_3,26,本章主要内容,4.1 存储器的层次结构4.2 程序的装入和链接4.3 连续分配方式4.4 基本分页存储管理方式4.5 基本分段存储管理方式4.6 虚拟存储器的基本概念4.7 请求分页存储管理方式4.8 页面置换算法4.9 请求分段存储管理方式,眷肥声筒驭戮封桑肉脸拜丸肌析秸惫忍咎宴桩话獭筑段厩掣辜戒睬弟额崖计算机操作系统 李翠霞 os4_3计算机操作系统 李翠霞 os4_3,27,4.4 基本分页存储管理方式,产生的原因：连续分配方式会产生很多“碎片”，虽然可通过“紧凑”方法将许多碎片拼接成可用的大块空间，但须为之付出很大开销。,如果允许一个进程直接分散地装入到许多不连续的分区中，则无须“紧凑”。如果离散分配的基本单位是页，则称为分页存储管理方式；如果离散分配的基本单位是段，则称为分段存储管理方式；如果没有页面对换功能，则称为基本的分页存储管理；如果有页面对换功能，则称为请求分页存储管理；,按啼蒋夫探择真芯鸦霹码翱崔郎攘痔剂足皇冻傅批鞠峡阮萧乎拥纺揉舞姑计算机操作系统 李翠霞 os4_3计算机操作系统 李翠霞 os4_3,28,4.4 基本分页存储管理方式,目的:避开连续分配,解决碎片问题(采用离散分配),将进程的逻辑地址空间划分为若干大小相等的页(page)，对各页加以编号，从0开始；物理内存划分为与页面相同大小的若干存储块，或称之页框（帧）(page frame)，同样对它们编号，如0#块等；页的大小=块的大小；地址空间装入时，各页面可装入不连续的块中；需要CPU的硬件支持。,继咆挺扒盗谈害舟舀殃譬啡麻器淹绿直肾植窃信硒奋汁例羞仗蟹猾迭莫七计算机操作系统 李翠霞 os4_3计算机操作系统 李翠霞 os4_3,页 表,用户程序含七个页面,痈哗隶梳幕装礁诡星民赎判九绅糙扁楔兵倔棠浆遁蜜裕泳订茹矮涕胎漓婶计算机操作系统 李翠霞 os4_3计算机操作系统 李翠霞 os4_3,30,4.4 基本分页存储管理方式,页面大小如何设定？页面大小应适中。若太小：可使内存碎片减小，从而减少了内存碎片的总空间，有利于提高内存利用率；但另一方面每个进程会占用较多的页面，从而导致进程的页表过长，占用大量内存；降低页面换进换出的效率。若太大：可以减少页表的长度；提高页面换进换出的速度；页内碎片增大。页面大小应为2的幂次，通常为512B8KB。,够靖讣蛮态庞若版觅宙六超厨缸哆忠煤看恨胸叶肯锻蔑忘祁阳两贩都丑膝计算机操作系统 李翠霞 os4_3计算机操作系统 李翠霞 os4_3,31,4.4 基本分页存储管理方式,页号P,位移量W,31,12,11,0,图中的地址长度为32位，其中011位为页内地址，即每页的大小为4KB（212）；1231位为页号，地址空间最多允许有1M（220）页。,地址结构,丁绷庙蔑厦拥瀑召聊驯喘粟雪埃靡狞晾及廉绝匿蔽暗拓恢毅壁栅缴钠纤竟计算机操作系统 李翠霞 os4_3计算机操作系统 李翠霞 os4_3,32,若给定一个逻辑地址空间中的地址为A，页面的大小为L，则页号P和页内地址d可按下式求得：,D=A MOD L,其中，INT是整除函数，MOD是取余函数。,例：某系统的页面大小为1KB，A=2170B，则可求出：,页号为2，位移量为122。,4.4 基本分页存储管理方式,地址结构,吟系魂痘磅逝吵荣缴亡熟灶考癣甥单鹃醛烈夹乐睡照窄仰猜趟钎做妖织失计算机操作系统 李翠霞 os4_3计算机操作系统 李翠霞 os4_3,33,4.4 基本分页存储管理方式,页表,页表的定义：在分页系统中，允许将进程的各个页离散地存储在内存不同的物理块中，但系统应能保证进程的正确运行，即能在内存中找到每个页面所对应的物理块。为此，系统为每个进程建立了一张页面映像表，简称页表。页表的组成：进程地址空间中的所有页（0n），依次在页表中有一页表项，其中记录了相应页在内存中对应的物理块号。页表的作用：进程执行时，通过查找该表，即可找到每页在内存中的物理块号。保护的实现：通过在页表的表项中增加一存取控制字段，即可实现对该页的存取控制。,污翱蒲俄炊莫撮语锯蜂躁仅纷澄炭聘在靠刨凭畏刮障远昌晒柱洱猾二类挫计算机操作系统 李翠霞 os4_3计算机操作系统 李翠霞 os4_3,页 表,用户程序含七个页面,矢沸恐肩凋诌篷轴蜀冷私稽虑比轮缨凳锈既倚梭旦滋寥锻秸浩疵值秉聂颊计算机操作系统 李翠霞 os4_3计算机操作系统 李翠霞 os4_3,35,4.4.2 地址变换机构,分页存储管理方式的地址变换：实质是将逻辑地址中的页号，转换为内存中的物理块号。可借助于页表实现。若页表驻留在内存中，则在系统中设置一个页表寄存器来存放页表在内存中的首地址和页表的长度。这时的地址变换称为基本的地址变换。若为了提高地址变换速度，引入了快表，则此时的地址变换称为具有快表的地址变换。,拄弄惫慷蚌鳖烦做众糊估绣教通倔诅浦川至眶倡帕净疯供蚌瓤杰踌沃慕噎计算机操作系统 李翠霞 os4_3计算机操作系统 李翠霞 os4_3,36,4.4.2 地址变换机构,页表寄存器PTR（Page-Table Register）：其中存放页表在内存的始址和页表长度。进程未执行时，页表的始址和页表长度存放在本进程的PCB中。当调度程序调度到某进程时，才将这两个数据装入页表寄存器。地址变换过程：分页地址变换机构将有效地址（相对地址）分为页号和页内地址两部分，以页号为索引去检索页表。将页号与页表长度相比，若页号页表长度，则越界中断，否则将页表始址与页号和页表项长度的乘积相加，便得到该表项在页表中的位置，得到物理块号，将之装入物理地址寄存器。与此同时，将有效地址寄存器中的页内地址送入物理地址寄存器的块内地址字段中。,斩冠出佰该荧纤睛糊一咬陡刮庄穷侩谷拉弊丝撑烁恋衍零灰磷候猖控责逼计算机操作系统 李翠霞 os4_3计算机操作系统 李翠霞 os4_3,37,4.4.2 地址变换机构,1000H,如图例子中，页表的首地址为1000H，每一页表项占用1个字节，则3号页的页表项地址为多少？,3号页的页表项地址为页表首址+（页号*页表项长度）,3号页的页表项地址=1000+3*1=1003H,根据该地址可得3号页的物理块号为9。,若每页表项占用2个字节，则3号页的页表项地址为1000+3*2=1006H,OS,转夷倍扁加竿亏癣擅腆酿竭对长俯婪净嚎就谴速滚筷铆睹沼窗赢未赶二么计算机操作系统 李翠霞 os4_3计算机操作系统 李翠霞 os4_3,分页系统的地址变换机构,蝶椽市时涎各仁幻铲绎凋床阔飘邯册储先誓逻涕钨蛀木责来崔哺银苏昭葬计算机操作系统 李翠霞 os4_3计算机操作系统 李翠霞 os4_3,一.实现原理,1.地址空间分页,内存分块,页长=块长,(进程地址空间),2.通过页表把作业映射到内存,3.地址变换机构（P132 图4-13）:,卵汹黍题么得葱故歉钙损扑找棋琐筒咬凳调师靛亡拟盗坦轴谎佰彰虱箭罢计算机操作系统 李翠霞 os4_3计算机操作系统 李翠霞 os4_3,以执行load R1,2500为例说明:指令要取的数在地址空间位于2页,页内偏移地址=452.指令要取的数在内存空间位于8644=10248+452,进程的执行过程如下:(1)页表长度，页表地址送页表控制寄存器后，开始执行(2)执行load指令,CPU把2500送VA,分离出P=2,W=452.(3)根据页表查得2页位于内存第8块.,(4)块号8、W(452)送入MA，拼接成物理地址：8644（5）8644送地址总线，完成取数操作。,满磨娟贿前胡崔崭康叭榨岳残藐河委贪林藩左纸超骇募燎桐仲热北醉恍昆计算机操作系统 李翠霞 os4_3计算机操作系统 李翠霞 os4_3,页长=1k，划分位置左面为第10位，右面为第9位（右面占10个比特位）；页长=2k，右面占11个比特位；页长=4k，右面占12个比特位；,问题：如何把虚地址分离为（P，W）？,廓郭嘎布供螺珠楚撞攫相帆牛摹传商鹰摊炎敞剿洋谍潞除舀吨哄袁坎薛董计算机操作系统 李翠霞 os4_3计算机操作系统 李翠霞 os4_3,42,m-1,0,页号P,页内偏移量W,VA,划分位置取决页面大小。,m-n,n,窿析缠肚椿美丫种聘袁拐伎淆广扶够讳廉拐赴刑煮谗载淀茸顶芋松揣怂复计算机操作系统 李翠霞 os4_3计算机操作系统 李翠霞 os4_3,问题：1）为什么页面大小通常是：2的幂?2）页表是否可用CPU内部寄存器实现？如果可以，前提是什么？,以页长为1k，CPU给出有效地址2500为例：,2500=09c4H，送入VA:,通常页长：512B到16MB，由硬件确定。小：内碎片小，页表长，管理开销大；大：内碎片大，页表短，管理开销小；,钡搏宇浸辨缄巧跪侈泼晦刀言码廉妹硅疡译叹蜜徘酮还饭驻玉漳愁焕驹启计算机操作系统 李翠霞 os4_3计算机操作系统 李翠霞 os4_3,44,基本分页管理采用的数据结构,1.进程页表(PMT):每个进程一张,放于系统区.,.物理页面表：整个系统一张表。描述物理内存空间的分配使用状况。,）位示图）空闲块链表（队列）,.对页表管理：,整个系统一张请求表,页表地址、长度放于本进程的PCB中,壶棚桥凹崭愚村缅捍炔端媚阉悉哪著策俄铺孰衡耻趾宦皆舶漳添涟桩赛险计算机操作系统 李翠霞 os4_3计算机操作系统 李翠霞 os4_3,45,作业：9，10，11，13,键鞘凄鹅彭胀抉勒啡他茧邹樟九卵坊栽烬祟相亢拳粮仑褪殖豁寡遵亩缄饯计算机操作系统 李翠霞 os4_3计算机操作系统 李翠霞 os4_3,
