1、基于伙伴堆算法的内存分配基于伙伴堆算法的内存分配/释释放的模拟实现放的模拟实现 功能要求(1)空闲页面分为10个块组，块组编号为0,1,2，8,9；(2)内存空间及其划分（界面）：内存物理空间大小可选择：256M bytes，512M bytes；每个页框的大小可选择：1K bytes，2K bytes，4K bytes；(3)设计对选择的内存空间进行划分管理模块，当所有内存为空闲时，显示其各块组空闲区链表的内容；(4)随机指定多个不连续占用的内存空间（每块占用空间包括2i个连续的页框），显示各块组空闲区链表的内容；(5)基于内存当前情况，随机产生申请的页框数m，显示满足m个页框的申请后，块组
2、空闲区链表的内容；(6)基于内存当前情况，随机产生被占用的（页框号，块组号）释放，显示释放后块组空闲区链表的内容。实现(1)定义空闲区块组链表数据结构；(2)依据块组伙伴的定义，产生空闲区块组链表的内容；(3)满足申请后，重新调整块组链表；(4)释放后，相邻空闲块组依据伙伴关系要合并成大的块组 Managing Physical MemorylAllocate ranges of physically-contiguous pages on request.（为进程分配连续存储区）（为进程分配连续存储区）lThe allocator uses a buddy-heap algorithm to
3、 keep track of available physical pages.(Buddy heap算法记载可用存储区）算法记载可用存储区）Each allocatable memory region is paired with an adjacent partner.（每个可用存储区有一个伙伴）（每个可用存储区有一个伙伴）Whenever two allocated partner regions are both freed up they are combined to form a larger region.（两个相邻的伙伴被释放时，（两个相邻的伙伴被释放时，合并为一个大空闲区）
4、合并为一个大空闲区）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.（小区域（小区域不能满足时，分割大区域）不能满足时，分割大区域）6432323216163216888321688-req(8)8req(8)-req(4)rel(8)32844164rel(8)8328883244888884432810
5、(29)9(28)8(27)4(23)3(22)2(21)1(20)数据结构：数据结构：组号（空闲块数组号（空闲块数）：链头指针）：链头指针249681632256相同长度的空闲块相同长度的空闲块构成一组构成一组51210(29)9(28)8(27)4(23)3(22)2(21)1(20)申请长度为申请长度为128，在第，在第8组中取一块。若组中取一块。若第第8组已空，在第组已空，在第9组取一块，分配其中组取一块，分配其中的的128页，并将剩余的页，并将剩余的128页记入第页记入第8组。组。若第若第9组也空，在第组也空，在第10组取一块，进行组取一块，进行两次分割，分配两次分割，分配128页，
6、剩余的页，剩余的128页页和和256页分别记入第页分别记入第8组和第组和第9组。组。释放是上述操作的逆过程，考虑伙伴的释放是上述操作的逆过程，考虑伙伴的合并。两个块为伙伴的条件是合并。两个块为伙伴的条件是:（1）两）两个块的大小相同，如个块的大小相同，如b个页面；（个页面；（2）两）两个块的物理地址连续；（个块的物理地址连续；（3）位于后面）位于后面块的最后页面编号必须是块的最后页面编号必须是2b的整数倍。的整数倍。I unit blockhead2 unit blockhead4 unit blockhead8 unit blockheadI6 unit blockhead32 unit b
7、lockhead.Problem:internal fragmentationeg:req(17)second memory allocationcarves slabs(small units)and manage them separatelythird memory allocationfor allocation of no-contiguous memory Physical memory managementl 页框页框:静态等长静态等长,4KB;l 块组块组:连续的连续的 2 i(i=0,1,2,9)个页框构成一个块组个页框构成一个块组;共共10个块组个块组,长度为长度为2 i
8、的块组叫作块组的块组叫作块组 i;l 空闲区表空闲区表:free_areai表示页框数为表示页框数为2 i的块组的块组,其结构为其结构为:l 分配分配/释放释放:Buddy heap algorithm 以以2 i 个页框个页框(块组块组)为分配为分配/释放单位释放单位(2 i-1fn2 i),fn为要申请的页框数为要申请的页框数;空闲块组指针空闲块组指针 块组位图指针块组位图指针1.伙伴堆存储分配算法伙伴堆存储分配算法n 块组位图块组位图:l 对于块组对于块组2 i 按前后顺序两两结合成一对按前后顺序两两结合成一对Buddy,如如:2 1块组的块组的0、1页框和页框和2、3页框是一对页框是一
9、对Buddy;l 块组位图的块组位图的 1 位表示对应的一对位表示对应的一对Buddy页框块组的使用情况页框块组的使用情况;l 对于一对对于一对buddy:若一个空闲若一个空闲,另一个全部或部分占用另一个全部或部分占用,则位图相应位置则位图相应位置1;当两个都空闲当两个都空闲,或都被全部或部分占用或都被全部或部分占用,则位图相应位置则位图相应位置0。n 伙伴条件伙伴条件:两个块大小相同两个块大小相同,即具有相同的页框数即具有相同的页框数b;两个块的物理地址相连两个块的物理地址相连;位于后面块组的最后页框编号位于后面块组的最后页框编号+1必须是必须是2b的整数倍。的整数倍。n 空闲区链表空闲区链
10、表 组织结构组织结构:假设假设6个块组个块组空闲块空闲块组指针组指针块组位块组位图指针图指针块组号块组号54 3210物理内存物理内存 页框号页框号151413121110987654321001000011110102104page1page12page3page4page14page8mapfree_areai Buddy heap algorithml 分配分配:申请申请 fn个页框个页框 找到相应的块组找到相应的块组 j;在块组在块组 j 的第一个空闲块分配的第一个空闲块分配 2 i个页框个页框(2 i-1fn2 i);调整块组调整块组 j 的空闲块链表的空闲块链表;若若 2 j 2
11、i,则把则把2 j-2 i 个空闲页框加入到相应块组空闲链中个空闲页框加入到相应块组空闲链中;(若若2 j-2 i不是不是2的整数次幂的整数次幂,则将其拆分成不同的整数次幂。则将其拆分成不同的整数次幂。)修改位图。修改位图。l 释放释放:释放释放 2 i个页框个页框 释放的释放的2 i个页框与相邻的空闲区按伙伴关系合并个页框与相邻的空闲区按伙伴关系合并,即两个相邻的伙伴合并为一个大的空闲区即两个相邻的伙伴合并为一个大的空闲区;把得到的空闲区加入到不同块组的空闲链中把得到的空闲区加入到不同块组的空闲链中;修改位图。修改位图。n 分配例分配例:申请页框数申请页框数fn=3空闲块空闲块组指针组指针块
12、组位块组位图指针图指针块组号块组号54 3210物理内存物理内存 页架号页架号151413121110987654321001000011110102104page1page12page3page4page14page8map 21fn22 在块组在块组2 的空闲块的空闲块 中分配中分配22个页框。个页框。块组块组2分配分配4个页框个页框(8,9,10,11)后后,空闲链空闲链及位图变化情况如图。及位图变化情况如图。空闲块空闲块组指针组指针块组位块组位图指针图指针块组号块组号54 3210物理内存物理内存 页架号页架号15141312111098765432100100001111010200
13、4page1page3page4page14mappage12page8n Buddy heap algorithm:l 问题问题:internal fragmentation.例如例如:申请申请17个页架个页架,由于由于2 4172 5,按按Buddy heap algorithm,要在块组要在块组5的空闲区分配的空闲区分配32个页框个页框,造成造成15个页框的浪费个页框的浪费,即即internal fragmentation.l 解决办法解决办法:second memory allocator 当实际申请页框数当实际申请页框数fn2 i时时,将将2 i-fn按按2的整数次幂切分的整数次幂切分(carves slabs),由由second memory allocator单独管理单独管理。third memory allocator 进程物理空间不要求连续时进程物理空间不要求连续时,内存分配由内存分配由third memory allocator完成。完成。
