第八章 动态存储管理

第八章 动态存储管理 8.11 typedef struct                   char *start;                  int size;               fmblock; /空闲块类型 char *Malloc_Fdlf(int n)/遵循最后分配者最先释放规则的内存分配算法  while(Gettop(S,b)&&b.size<n)      Pop(S,b);    Push(T,b); /从栈顶逐个取出空闲块进行比较    if(StackEmpty(S) return NULL; /没有大小足够的空闲块  Pop(S,b);  b.size-=n;  if(b.size) Push(S,b.start+n,b.size);/分割空闲块  while(!StackEmpty(T)      Pop(T,a);    Push(S,a);   /恢复原来次序  return b.start;/Malloc_Fdlf mem_init()/初始化过程  .  InitStack(S);InitStack(T); /S和T的元素都是fmblock类型  Push(S,MemStart,MemLen); /一开始,栈中只有一个内存整块  ./main 8.12 void Free_Fdlf(char *addr,int n)/与上一题对应的释放算法  while(Gettop(S,b)&&b.start<addr)      Pop(S,b);    Push(T,b);   /在按地址排序的栈中找到合适的插入位置  if(Gettop(T,b)&&(b.start+b.size=addr) /可以与上邻块合并      Pop(T,b);    addr=b.start;n+=b.size;    if(Gettop(S,b)&&(addr+n=b.start) /可以与下邻块合并      Pop(S,b);    n+=b.size;    Push(S,addr,n); /插入到空闲块栈中  while(!StackEmpty(T)      Pop(T,b);    Push(S,b);   /恢复原来次序/Free_Fdlf 8.13 void Free_BT(Space &pav,Space p)/在边界标识法的动态存储管理系统中回收空闲块p  n=p->size;  f=p+n-1; /f指向空闲块底部  if(p-1)->tag&&(f+1)->tag) /回收块上下邻块均为占用块      p->tag=0;f->tag=0;    f->uplink=p;    if(!pav)          p->llink=p;      p->rlink=p;        else          q=pav->llink;      p->llink=q;p->rlink=pav;      q->rlink=p;pav->llink=p;        pav=p;  /if  else if(!(p-1)->tag&&(f+1)->tag) /上邻块为空闲块      q=(p-1)->uplink;    q->size+=n;    f->uplink=q;    f->tag=0;    else if(p-1)->tag&&!(f+1)->tag) /下邻块为空闲块      q=f+1;    s=q->llink;t=q->rlink;    p->llink=s;p->rlink=t;    s->rlink=p;t->llink=p;    p->size+=q->size;    (q+q->size-1)->uplink=p;    p->tag=0;    else /上下邻块均为空闲块      s=(p-1)->uplink;    t=f+1;    s->size+=n+t->size;    t->llink->rlink=t->rlink;    t->rlink->llink=t->llink;    (t+t->size-1)->uplink=s;  /Free_BT,该算法在课本里有详细的描述. 8.14 void Free_BS(freelist &avail,char *addr,int n)/伙伴系统的空闲块回收算法  buddy=addr%(2*n)?(addr-n):(addr+n); /求回收块的伙伴地址  addr->tag=0;  addr->kval=n;  for(i=0;availi.nodesize<n;i+); /找到这一大小的空闲块链  if(!availi.first) /尚没有该大小的空闲块     addr->llink=addr;   addr->rlink=addr;   availi.first=addr; /作为唯一一个该大小的空闲块    else      for(p=availi.first;p!=buddy&&p!=availi.first;p=p->rlink);/寻找伙伴    if(p=buddy) /伙伴为空闲块,此时进行合并          if(p->rlink=p) availi.first=NULL;/伙伴是此大小的唯一空闲块      else              p->llink->rlink=p->rlink;        p->rlink->llink=p->llink;       /从空闲块链中删去伙伴      new=addr>p?p:addr; /合并后的新块首址      Free_BS(avail,new,2*n); /递归地回收新块    /if    else /伙伴为占用块,此时插入空闲块链头部          q=p->rlink;      p->rlink=addr;addr->llink=p;      q->llink=addr;addr->rlink=q;      /else/Free_BS 8.15 FBList *MakeList(char *highbound,char *lowbound)/把堆结构存储的的所有空闲块链接成可利用空间表,并返回表头指针  p=lowbound;  while(p->tag&&p<highbound) p+; /查找第一个空闲块  if(p>=highbound) return NULL; /没有空闲块  head=p;  for(q=p;p<highbound;p+=cellsize) /建立链表    if(!p->tag)          q->next=p;      q=p;    /if  p->next=NULL;  return head; /返回头指针/MakeList 8.16 void Mem_Contract(Heap &H)/对堆H执行存储紧缩  q=MemStart;j=0;  for(i=0;i<Max_ListLen;i+)    if(H.listi.stadr->tag)          s=H.listi.length;      p=H.listi.stadr;      for(k=0;k<s;k+) *(q+)=*(p+); /紧缩内存空间      H.listj.stadr=q;      H.listj.length=s; /紧缩占用空间表      j+;    /Mem_Contract本文来自中国信息网,您身边的一站式生活专家！中国信息网 中国信息网返利频道中国信息网论坛频道中国信息网分类信息频道中国信息网美女频道