分配算法

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

导读：当用户申请空间时，系统可以采用 3 种分配方法中的任何一种。但在不断地分配的过程中，会产生一些容量极小以至无法利用的空闲块，这些不断生成的小内存块就会减慢遍历分配的速度。

选定一个常量 e，每次分配空间时

当用户申请空间时，系统可以采用 3 种分配方法中的任何一种。但在不断地分配的过程中，会产生一些容量极小以至无法利用的空闲块，这些不断生成的小内存块就会减慢遍历分配的速度。

选定一个常量 e，每次分配空间时，判断当前内存块向用户分配空间后，如果剩余部分的容量比 e 小，则将整个内存块全部分配给用户。

采用头部拟合法进行分配时，如果每次都从 pav 指向的结点开始遍历，在若干次后，会出现存储量小的结点密集地分布在 pav 结点附近的情况，严重影响遍历的时间。解决办法就是：在每次分配空间后，让 pav 指针指向该分配空间结点的后继结点，然后从新的 pav 指向的结点开始下一次的分配。

分配算法的具体实现代码为（采用首部拟合法）

纯文本复制
Space AllocBoundTag(Space *pav,int n){
Space p,f;
int e=10;//设定常亮 e 的值
//如果在遍历过程，当前空闲块的在存储容量比用户申请空间 n 值小，在该空闲块有右孩子的情况下直接跳过
for (p=(*pav); p&&p->size<n&&p->rlink!=(*pav); p=p->rlink);
//跳出循环，首先排除p为空和p指向的空闲块容量小于 n 的情况
if (!p ||p->size<n) {
return NULL;
}else{
//指针f指向p空闲块的foot域
f=FootLoc(p);
//调整pav指针的位置，为下次分配做准备
(*pav)=p->rlink;
//如果该空闲块的存储大小比 n 大，比 n+e 小，负责第一种情况，将 p 指向的空闲块全部分配给用户
if (p->size-n <= e) {
if ((*pav)==p) {
pav=NULL;
}
else{
//全部分配用户，即从可利用空间表中删除 p 空闲块
(*pav)->llink=p->llink;
p->llink->rlink=(*pav);
}
//同时调整head域和foot域中的tag值
p->tag=f->tag=1;
}
//否则，从p空闲块中拿出大小为 n 的连续空间分配给用户，同时更新p剩余存储块中的信息。
else{
//更改分配块foot域的信息
f->tag=1;
p->size-=n;
//f指针指向剩余空闲块 p 的底部
f=FootLoc(p);
f->tag=0; f->uplink=p;
p=f+1;//p指向的是分配给用户的块的head域，也就是该块的首地址
p->tag=1; p->size=n;
}
return p;
}
}

（编辑：汽车网）

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