1.引言
伙伴系统(buddy system)是操作系统中用到的一种动态存储管理方法。它和边界
标识法类似,在用户提出申请时,分配一块大小“恰当”的内存区给用户;反之,在用户释
放内存区时即回收。所不同的是:在伙伴系统中,无论是占用块或空闲块,其大小均为 2
的 k 次幂(k 为某个正整数)。由此,在可利用空间表中的空闲块大小也只能是 2 的 k 次
幂。若总的可利用内存容量为 2m 个字,则空闲块的大小之可能为 20、21、…、2m。结
合之前学过的 c 程序设计和数据结构(C 语言)两门课程,通过 c 语言,对伙伴系统算法
进行了设计,下面就简单介绍一下。
2.需求分析
2.1 硬件需求
本系统适用于现用的各种类型的计算机,内存容量建议为 128MB 以上,不必配备外
部附加设备。
2.2 软件需求
Microsoft Visual C++ 6.0
2.3 设计需求
对于固定分区和动态分区方案都存在一定的缺陷。固定分区方案限制活跃进程的数目,
而且,可用分区的大小与进程大小非常不匹配,空间的利用率非常低。动态分区的维护十
分复杂,而且需要紧凑的开销。一个比较有吸引力的折衷方案是伙伴算法。在伙伴系统中,
内存块的大小为 2
k
,L≤K≤U,其中 2
L
为分配的最小块的尺寸。2
u
为分配的最大块的尺寸。
伙伴算法能够高效的分配和回收内存,并可以避免内存碎片的产生,从而提高了物理内存
的利用率。本次课程设计就是编程模拟实现伙伴系统算法。
3.概要设计
3.1 算法设计思想
伙伴算法一次分配和释放 2 的幂次方个页面。Free_area 数组中每一个元素都有一个 map 指
针指向其链表中内存块的位图(如图 3 所示)
[1]
,位图是伙伴算法最频繁的操作对象,它记
录了各内存块使用情况的重要情况(如图 1、2 所示)
[2]
。假如系统需要 4 个页面大小的内
存块,该算法就到 free_areal2]中查找,如果链表中有空闲块,就直接从中摘下并分配出去;
如果没有,算法将顺着数组向上查找 free_area[3]。如果 free_area[3]中有空闲块,将其从链
表中摘下,分成等大小的两部分,前 4 个页面作为一个块插入 free_area[2]的链表头部,后
4 个页面分配出去。Free_area[3]中也没有,就再向上查找,如果 free_area[4]中有,就将这
16(2 )个页面等分成两份,前一半挂如 free_area[3]的链表头部,后一半的 8 个页面再分成两
等份,前一半挂如 free_area[2]的链表中,后一半分配出去。假如 free_area[4]中也有
空闲块,则重复上面的过程,直至达到 free_area 数组的最后,如果还是没有可分配的块,
就放弃分配。内存的释放是分配的逆过程,也可以看作是伙伴的合并过程。当释放一个块
1