动态存储管理(续)

动态存储管理

4. 伙伴系统

伙伴系统使操作系统的另一种动态存储管理方法。它和边界表示法类似,在用户提出申请使时,分配一块大小恰当的内存区给用户;反之在用户释放内存区时即回收。所不同的使:在伙伴系统中,无论使占用块还是空闲块其大小均为2的k次方

4.1 可利用空间表结构

#define m 16
typedef struct WORD_b {
<!--more-->
WORD_b *llink;
int tag;
int kval;
WORD_b *rlink;
OtherType other;
} WORD_b, head; //内存字类型,节点的第一个字页称为head
typedef struct HeadNode {
int nodesize;
WORD_b *first;
} FreeList[m+1];

4.2 分配算法

WORD_b* alloc_buddy (FreeList &avail, int n) {
// avail[0..m]为可利用空间表,n为申请分配量,若有不小于n的空闲块,
// 则分配相应的存储块,并返回其首地址;否则返回NULL
WORD_b *pa, *pre, *suc, *pi;
// 查找满足分配要求的子表
for (int k = 0; k <= m && (!avail[k].first || avail[k].nodesize<n+1); ++k);
if (k > m) return NULL; // 分配失败,返回NULL
else { // 进行分配
pa = avail[k].first; // 指向可分配子表的第一个结点
pre = pa->llink; suc = pa->rlink; // 分别指向前驱和后继
if (pa == suc) avail[k].first = NULL; // 分配后该子表变成空表
else { // 从子表删去*pa结点
pre->rlink = suc; suc->llink = pre; avail[k].first = suc;
}
for (int i=1; avail[k-i].nodesize>=n+1; ++i) {
pi = pa+(int)pow(2, (k-i)); pi->rlink = pi; pi->llink = pi;
pi->tag = 0; pi->kval = k-i; avail[k-i].first = pi;
} // 将剩余块插入相应子表
pa->tag = 1; pa->kval = k-(--i);
}
return pa;
}

4.3 回收算法

内存回收时同样有一个相邻的空闲块归并成大块的问题。但是在伙伴系统中仅考虑护卫伙伴的两个空闲块的归并。

伙伴:在分配时经常需要将一个大的空间块分裂成两个大小相等的存储区。这两个有统一个大块分裂出来的小块就称之为互为伙伴。例如起使地址p,大小2^k的内存块,其伙伴块的起始地址为:buddy(p,k) = p+2^k(若 p MOD 2^k+1 =0) 或 p-2^k(若p MOD 2^k+1 =2^k)

伙伴系统的有点是算法简单,速度快;缺点是由于只归并伙伴而容易产生碎片

5. 无用单元收集

本节讨论广义表节点的释放回收问题,解决这个问题有两条途径:

  • 使用访问计数器:在所有字表或广义表上增加一个表头节点,并设立一个计数域,它的值为指向该子表或广义表的指针数目,只有当该值为0时,此子表才从广义表中释放
  • 收集无用单元:程序运行过程中无论节点是否有用,系统均不对它进行回收,直到整个可以用空间表为空。此时中断执行程序,将不被使用的节点连成链表,而后开始执行程序

由此,收集无用单元分两部:

  • 对无用单元加标志
  • 对整个空间扫描,标志为0的节点连为链表

对上述的第一步标志的进行时极其困难的,我们讨论3种标志算法:

  • 递归算法:遍历广义表即可,但是它需要的存储空间非常大很可能由于递归栈溢出造成内存泄漏
  • 非递归算法:手动做栈进行广义表遍历,以避免内存泄漏
  • 利用表节点本身的指针域标记遍历路径算法

第3种算法如下:

void mark_list(GList GL) {
// 遍历非空广义表GL(GL!=NULL且GL->mark==0),
// 对表中所有未加标志的结点加标志
GList q = NULL, p = GL, t = NULL; // t指示p的母表
int finished = FALSE;
while (!finished) {
while (p->mark==0) {
p->mark = 1;
// MarkHead(p)的细化:
q = p->ptr.hp; // q指向*p的表头
if (q && q->mark==0) {
if (q->tag==ATOM) q->mark = 1; // ATOM,表头为原子结点
else { //继续遍历子表
p->ptr.hp = t; p->tag = ATOM; t = p; p = q;
}
}
} // 完成对表头的标志
q = p->ptr.tp; // q指向*p的表尾
if (q && q->mark==0) { // 继续遍历表尾
p->ptr.tp = t; t = p; p = q;
} else { // BackTrack(finished)的细化:
while (t && t->tag==LIST) { // LIST,表结点,从表尾回溯
q = t; t = q->ptr.tp; q->ptr.tp = p; p = q;
}
if (!t) finished = TRUE; // 结束
else { // 从表头回溯
q = t; t = q->ptr.hp; q->ptr.hp = p;
p = q; p->tag = LIST;
} // 继续遍历表尾
}
}
}

比较上述3种算法各有利弊,第3种算法在标志时不需要附加存储,使动态空间得到充分利用,但由于在算法中每个指针的作用要改变两次因此开销相当大,而且一旦中断则导致系统瘫痪无法重新启动。而非递归算法操作简单,时间上省得多,但是然而它需要占用一定的动态空间,使动态分配所用的存储量减少

5. 存储紧缩

在使用(空闲块为一段连续的地址)的系统中,由于系统的可利用空间始终是一个地址连续的存储块,因此回收时必须将所释放的空闲块合并到整个对上去才能重新使用,这就是存储紧缩的任务。

通常有两种做法:

  • 一旦有用户释放空间即进行存储紧缩
  • 直到可利用空间不够的时侯才进行存储紧缩

为实现存储紧缩首先要对占用块进行标志,标志算法和上节相同,其次需要进行一下4步:

  1. 计算占用块的新地址
  2. 修改用户的初始向量表,以便进行存储紧缩后用户的程序还能够运行
  3. 检查每个占用块中存储的数据,若有指向其他存储块的指针,则需做相应更改
  4. 将所有占用块迁移到新地址去,这实质上使作数据传送