操作系统课程设计课件题目10.ppt

基于伙伴堆算法的内存分配/释放的模拟实现,纪般督勉祖者鼠门紊雄图秤迁绢甘纱悼门鬃幼宾佐烦袭匣赘肿粒就穿锗脑操作系统课程设计课件 题目10操作系统课程设计课件 题目10,功能要求(1)空闲页面分为10个块组，块组编号为0,1,2，8,9；(2)内存空间及其划分（界面）：内存物理空间大小可选择：256M bytes，512M bytes；每个页框的大小可选择：1K bytes，2K bytes，4K bytes；(3)设计对选择的内存空间进行划分管理模块，当所有内存为空闲时，显示其各块组空闲区链表的内容；(4)随机指定多个不连续占用的内存空间（每块占用空间包括2i个连续的页框），显示各块组空闲区链表的内容；(5)基于内存当前情况，随机产生申请的页框数m，显示满足m个页框的申请后，块组空闲区链表的内容；(6)基于内存当前情况，随机产生被占用的（页框号，块组号）释放，显示释放后块组空闲区链表的内容。,典爬括刊哦穷话灸淮摈履拐铀耙渺擅浪咸耸豌羽湾字痛存襄勺抽名龙豺叔操作系统课程设计课件 题目10操作系统课程设计课件 题目10,实现(1)定义空闲区块组链表数据结构；(2)依据块组伙伴的定义，产生空闲区块组链表的内容；(3)满足申请后，重新调整块组链表；(4)释放后，相邻空闲块组依据伙伴关系要合并成大的块组,谴鲤觉恬戮壁室萍添梨蚌填荆奏半桑服店肤训兵豪莆代慨垢瞒提秘寐轧燕操作系统课程设计课件 题目10操作系统课程设计课件 题目10,Managing Physical Memory,Allocate ranges of physically-contiguous pages on request.（为进程分配连续存储区）The allocator uses a buddy-heap algorithm to keep track of available physical pages.(Buddy heap算法记载可用存储区）Each allocatable memory region is paired with an adjacent partner.（每个可用存储区有一个伙伴）,省赁筷达妆泰膳或预简破乒凰毁牢激池试蔡期迸汉港暴价馏数垂涟均眯料操作系统课程设计课件 题目10操作系统课程设计课件 题目10,Managing Physical Memory,Whenever two allocated partner regions are both freed up they are combined to form a larger region.（两个相邻的伙伴被释放时，合并为一个大空闲区）If a memory request cannot be satisfied by allocating an existing small free region,then a larger free region will be subdivided into two partners to satisfy the request.（小区域不能满足时，分割大区域）,舆哎湾惺裸斜导策莱魂鄙惊闷歹驰从珠坑三咀小利恩诞粹偶皋率荐瓶撒金操作系统课程设计课件 题目10操作系统课程设计课件 题目10,Buddy heap存储分配,64,32,1616,32,16,8,32,16,-req(8),8,req(8),-req(4),rel(8),16,4,rel(8),8,328,32,4,4,8,8,8,4,4,32,8,腔孤友采雁郑鼻罩蝴掀愁冀贱广昆瞩收倔岁嘿瑟卵松栗筑厕碟伍主冰涣瓣操作系统课程设计课件 题目10操作系统课程设计课件 题目10,数据结构：组号（空闲块数）：链头指针,Buddy Heap Implementation,24,96,8,16,32,256,相同长度的空闲块构成一组,512,艇咎宝椅瘫锡眷审爬蜕准毋县蚤徒浇脆乌产姻粗怔烽腊话励茸惺嫁仕氮吻操作系统课程设计课件 题目10操作系统课程设计课件 题目10,申请长度为128，在第8组中取一块。若第8组已空，在第9组取一块，分配其中的128页，并将剩余的128页记入第8组。若第9组也空，在第10组取一块，进行两次分割，分配128页，剩余的128页和256页分别记入第8组和第9组。释放是上述操作的逆过程，考虑伙伴的合并。两个块为伙伴的条件是:（1）两个块的大小相同，如b个页面；（2）两个块的物理地址连续；（3）位于后面块的最后页面编号必须是2b的整数倍。,Buddy Heap Implementation,阉余雹胸妙既卷模舵米优艘永记黄危性存渔祷筋玛号澄递磺缺乃蚊秀糖绩操作系统课程设计课件 题目10操作系统课程设计课件 题目10,Buddy Heap Implementation,Problem:internal fragmentationeg:req(17)second memory allocationcarves slabs(small units)and manage them separatelythird memory allocationfor allocation of no-contiguous memory,不琼涕瞪瘸恭征合诡很绰垒鞭紫丈气拿烃虾厦鸟仙丈酿淳卖颠帚欲膝馅帽操作系统课程设计课件 题目10操作系统课程设计课件 题目10,Linux 存储管理,Physical memory management 页框:静态等长,4KB;块组:连续的 2 i(i=0,1,2,9)个页框构成一个块组;共10个块组,长度为2 i 的块组叫作块组 i;空闲区表:free_areai表示页框数为2 i的块组,其结构为:分配/释放:Buddy heap algorithm 以2 i 个页框(块组)为分配/释放单位(2 i-1fn2 i),fn为要申请的页框数;,1.伙伴堆存储分配算法,山谱犯厅滨倒泣速诞累纵像竣搭面启聚休御神韧腋陪吊罕赞阁跟陪凡刁媒操作系统课程设计课件 题目10操作系统课程设计课件 题目10,Linux 存储管理(Cont.),块组位图:,对于块组2 i 按前后顺序两两结合成一对Buddy,如:2 1块组的0、1页框和2、3页框是一对Buddy;块组位图的 1 位表示对应的一对Buddy页框块组的使用情况;对于一对buddy:若一个空闲,另一个全部或部分占用,则位图相应位置1;当两个都空闲,或都被全部或部分占用,则位图相应位置0。,伙伴条件:,两个块大小相同,即具有相同的页框数b;两个块的物理地址相连;位于后面块组的最后页框编号+1必须是2b的整数倍。,礁御鼎檀谜靶延坚业凭痒宋礼幢翁替籽曰谐痛骡遁意逮肯槛及缕魄啪赵沥操作系统课程设计课件 题目10操作系统课程设计课件 题目10,Linux 存储管理(Cont.),空闲区链表 组织结构:假设6个块组,map,free_areai,押幕趣舆昧耶韦蠕同虾奠李逞唐是乎宫胸佛苛绒聋伎捎享穷伪婴砚藩纪拽操作系统课程设计课件 题目10操作系统课程设计课件 题目10,Linux 存储管理(Cont.),Buddy heap algorithm分配:申请 fn个页框找到相应的块组 j;在块组 j 的第一个空闲块分配 2 i个页框(2 i-1fn2 i);调整块组 j 的空闲块链表;若 2 j 2 i,则把2 j-2 i 个空闲页框加入到相应块组空闲链中;(若2 j-2 i不是2的整数次幂,则将其拆分成不同的整数次幂。)修改位图。,释放:释放 2 i个页框释放的2 i个页框与相邻的空闲区按伙伴关系合并,即两个相邻的伙伴合并为一个大的空闲区;把得到的空闲区加入到不同块组的空闲链中;修改位图。,雏虞福鹏褪氏咎蔫颖闰阉郸龟拖苫碍拭永笼奸烩尘钠逝妒府噎观酗朗唬固操作系统课程设计课件 题目10操作系统课程设计课件 题目10,Linux 存储管理(Cont.),分配例:申请页框数fn=3,map,21fn22 在块组2 的空闲块 中分配22个页框。,姥选票锦绎骗绢蓬绰即搀河垂呢企霉纶印沁玄淳护偏湖回槛踏吭杭泳叔烬操作系统课程设计课件 题目10操作系统课程设计课件 题目10,Linux 存储管理(Cont.),块组2分配4个页框(8,9,10,11)后,空闲链及位图变化情况如图。,map,揪髓沼核趴宠嵌注耙键浦迫嘎位闲侥准朔老茶津磕哲郑简辑谅狸喂抛宵耍操作系统课程设计课件 题目10操作系统课程设计课件 题目10,Linux 存储管理(Cont.),Buddy heap algorithm:问题:internal fragmentation.例如:申请17个页架,由于2 4172 5,按Buddy heap algorithm,要在块组5的空闲区分配32个页框,造成15个页框的浪费,即internal fragmentation.解决办法:second memory allocator 当实际申请页框数fn2 i时,将2 i-fn按2的整数次幂切分(carves slabs),由second memory allocator单独管理。third memory allocator 进程物理空间不要求连续时,内存分配由third memory allocator完成。,奏匣沛茄掠赦繁秘垮嘱反折吁掳窒茁仿康亦轮弘唆弯蓉矽乏拌殃委哭荷汽操作系统课程设计课件 题目10操作系统课程设计课件 题目10,