计算机操作系统----伙伴系统


------解决方案--------------------
这不是内存管理中的伙伴法吗.

一大块内存按照2的k次方,一直分解下去,到一个合适的最小块,然后用另一的数组保存管理的块,标记他们是被使用,还是没被使用.
先假设:4~F单元都已经被分配出去.
分配时:
在申请内存时分配最小的2的整数个单元,
1. p1申请1kB,则分配1kB;单元[0]被标记为以分配 
2. p2申请2kB,则分配2kB;但是2kB的单元只能是[2,3]这个单元,所以[2,3]被分配,[1]被空闲
此时 0 2 3都被分配,1空闲
释放时
1. 释放p1,释放[0] 单元,然后查看他的伙伴,[1]单元,发现[1]单元空着,则合并成为[0,1]单元,标示为可用.
2. 释放p2,释放[2,3]单元,此时先查看1单元的伙伴单元,即0单元
     2.1: 释放[2,3]单元,并标记为空
     2.2: 查看[2,3]单元的伙伴单元[0,1] 此时发现[0,1]单元也是空的,合并成为更大一倍的单元[0,1,2,3]
     2.3: 查看[0,1,2,3]的伙伴单元 [4,5,6,7] 发现不为空.
 p2释放完毕.

伙伴法好处就是可以以线性级的空间管理指数级大小的空间.
     当然要牺牲一点:不是伙伴的连续空间不能合并的. 
     例如当前若只有[1]和[2]单元未被分配,他们一共有2kB,也是连续的,但是不是伙伴单元.
    此时若请求分配2kB的空间,则伙伴法会指示空间不够,因为2kB需要一个2kB的单元如[0,1] [2,3].而不仅仅是连续的2个1kB的单元,如[1]和[2]