回收算法

发布时间：2023-05-23 12:49:55 所属栏目：语言来源：

导读：在用户活动完成，系统需要立即回收被用户占用的存储空间，以备新的用户使用。回收算法中需要解决的问题是：在若干次分配操作后，可利用空间块中会产生很多存储空间很小以致无法使用的空闲块。但是经过回收用户释放的

在用户活动完成，系统需要立即回收被用户占用的存储空间，以备新的用户使用。回收算法中需要解决的问题是：在若干次分配操作后，可利用空间块中会产生很多存储空间很小以致无法使用的空闲块。但是经过回收用户释放的空间后，可利用空间表中可能含有地址相邻的空闲块，回收算法需要将这些地址相邻的空闲块合并为大的空闲块供新的用户使用。

合并空闲块有 3 种情况：
该空闲块的左边有相邻的空闲块可以进行合并；
该空闲块的右边用相邻的空闲块可以进行合并；
该空闲块的左右两侧都有相邻的空闲块可以进行合并；

判断当前空闲块左右两侧是否为空闲块的方法是：对于当前空闲块 p ，p-1 就是相邻的低地址处的空闲块的 foot 域，如果 foot 域中的 tag 值为 0 ，表明其为空闲块； p+p->size 表示的是高地址处的块的 head 域，如果 head 域中的 tag 值为 0，表明其为空闲块。

如果当前空闲块的左右两侧都不是空闲块，而是占用块，此种情况下只需要将新的空闲块按照相应的规则（头部拟合法随意插入，其它两种方法在对应位置插入）插入到可利用空间表中即可。实现代码为：

//设定p指针指向的为用户释放的空闲块
p->tag=0;
//f指针指向p空闲块的foot域
Space f=FootLoc(p);
f->uplink=p;
f->tag=0;
//如果pav指针不存在，证明可利用空间表为空，此时设置p为头指针，并重新建立双向循环链表
if (!pav) {
pav=p->llink=p->rlink=p;
}else{
//否则，在p空闲块插入到pav指向的空闲块的左侧
Space q=pav->llink;
p->rlink=pav;
p->llink=q;
q->rlink=pav->llink=p;
pav=p;
}
如果该空闲块的左侧相邻的块为空闲块，右侧为占用块，处理的方法是：只需要更改左侧空闲块中的 size 的大小，并重新设置左侧空闲块的 foot 域即可。

实现代码为：
//常量 n 表示当前空闲块的存储大小
int n=p->size;
Space s=(p-1)->uplink;//p-1 为当前块的左侧块的foot域，foot域中的uplink指向的就是左侧块的首地址，s指针代表的是当前块的左侧存储块
s->size+=n;//设置左侧存储块的存储容量
Space f=p+n-1;//f指针指向的是空闲块 p 的foot域
f->uplink=s;//这是foot域的uplink指针重新指向合并后的存储空间的首地址
f->tag=0;//设置foot域的tag标记为空闲块

如果用户释放的内存块的相邻左侧为占用块，右侧为空闲块，处理的方法为：将用户释放掉的存储块替换掉右侧的空闲块，同时更改存储块的 size 和右侧空闲块的 uplink 指针的指向。

实现代码为：
Space t=p+p->size;//t指针指向右侧空闲块的首地址
p->tag=0;//初始化head域的tag值为0
//找到t右侧空闲块的前驱结点和后继结点，用当前释放的空闲块替换右侧空闲块
Space q=t->llink;
p->llink=q; q->rlink=p;
Space q1=t->rlink;
p->rlink=q1; q1->llink=p;
//更新释放块的size的值
p->size+=t->size;
//更改合并后的foot域的uplink指针的指向
Space f=FootLoc(t);
f->uplink=p;

如果当前用户释放掉的空闲块，物理位置上相邻的左右两侧的内存块全部为空闲块，需要将 3 个空闲块合并为一个更大的块，操作的过程为：更新左侧空闲块的 size 的值，同时在可利用空间表中摘除右侧空闲块，最后更新合并后的大的空闲块的 foot 域。

此情况和只有左侧有空闲块的情况雷同，唯一的不同点是多了一步摘除右侧相邻空闲块结点的操作。

实现代码为：
纯文本复制
int n=p->size;
Space s=(p-1)->uplink;//找到释放内存块物理位置相邻的低地址的空闲块
Space t=p+p->size;//找到物理位置相邻的高地址处的空闲块
s->size+=n+t->size;//更新左侧空闲块的size的值
//从可利用空间表中摘除右侧空闲块
Space q=t->llink;
Space q1=t->rlink;
q->rlink=q1;
q1->llink=q;
//更新合并后的空闲块的uplink指针的指向
Space f=FootLoc(t);
f->uplink=s;

（编辑：汽车网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!