伙伴系统算法.doc

#includestdio.h #includestdlib.h #includemalloc.h #includemath.h # define M 21 //宏定义，最大可分配空间为1M字节，最小为1字节 //定义数据结构：用二叉树结点结构 struct buddynode { char name; //占用该空间的进程名称 int level; //表示等级数，即空间大小，用其幂级数表示，level表示2^(level)大小的空间 int idle; //空闲标志位，1表示空闲，0表示已分配 int lorr; //标志位（left or right）：0表示该结点是左孩子，1表示该结点是右孩子 //后继（用于空闲队列指针的操作）;左右孩子，双亲用于二叉树存储 buddynode *next; buddynode *lchild; buddynode *rchild; buddynode *parent; }; buddynode *idlepres[M]; //空间大小为2^M的空闲队列，相当于尾指针，指向空闲队列最后一个空闲区 buddynode *idlehead[M]; //各空闲队列头指针，与上面M个空闲队列相对应 buddynode *bs; //初始化时令其指向根结点，为每次遍历时使用 buddynode *bsp; //暂存结点信息 buddynode *bt; //定义初始化函数：0～Ｍ－２队列都为空，而Ｍ－１队列初始化为最大空间，即2^M void init_space() { int i; for(i=0;iM-1;i++) { idlehead[i]=(buddynode*)(malloc(sizeof buddynode)); idlepres[i]=NULL; idlehead[i]-next=NULL; } idlepres[M-1]=(buddynode*)(malloc(sizeof buddynode)); idlepres[M-1]-name=NULL; idlepres[M-1]-level=M-1; idlepres[M-1]-idle=1; idlepres[M-1]-lorr=NULL; //表示根结点 idlepres[M-1]-next=NULL; idlepres[M-1]-lchild=NULL; idlepres[M-1]-rchild=NULL; idlepres[M-1]-parent=NULL; idlehead[M-1]=(buddynode*)(malloc(sizeof buddynode)); idlehead[M-1]-next=idlepres[M-1]; bs=idlepres[M-1]; } //根结点作为源头，遍历的起始 //为进城分配空间函数，以进程名称和空间大小为行参 void req_space(char na,int m) { int k,sj,si; buddynode *pav; buddynode *pde; //delete,空闲区结点删除后暂存入pde k=m; si=0; //while循环，找到满足条件的si使得2^(si-1)m2^(si),si是需要分配的空间大小等级 while(k0){ k=k/2; si=si+1; } //判断是否存在大小为si的空闲区,若有si空闲区，分配给进程 if((idlehead[si]-next!=NULL)(idle