Unix成组链接策略的模拟实现

一、课程设计题目UNIX成组链接策略的模拟实现二、课程设计目的通过模拟UNIX成组链接策略的实现，理解UNIX管理磁盘空闲空间的方法三、课程设计内容实现UNIX管理磁盘空闲空间的方法——成组链接。系统初始化时先把专用块内容读到内存，当需要分配空闲块时，就直接在内存中可找到哪些块。但要把一组中的第一个空闲块分配出去之前应把登记在该块中的下一组的块号及块数保存到专用块中。当一组空闲块被分配完后，则再把专用块的内容读到内存，指出另一组可供分配的空闲块。当归还一块时，只要把归还块的块号登记到当前组中且空闲块数加1。如果当组已经满100块，则把内存中的内容写到归还的那块中，该归还块作为新组的第一块。本题目的简化假设是：1、设磁盘空闲块现有100块，块号就是[0,99]。每组有10块，因此盘块号栈容量也为10。2、申请和释放块的请求由自己随机产生（块数及假想的文件名），让你的程序循环，发生200次请求，在前半期以申请块请求居多，在后半期以释放块请求居多。3、如果万一发生100块都用完的情况，就报告，且保存新产生的申请请求，直到有新的释放请求发出。4、每次请求完成后，列出本次请求的简要情况。全部请求完成后，列出现在的磁盘空间状况（空闲或已分配给哪个“文件”）。四、设计思路1.原理：将若干个（如100）个空闲盘块规划在一个组，最后一组的空闲盘块号存入系统文件资源表的空闲盘块号栈中，某一组的第一个空闲盘块中存放上一组的所有空闲盘块号。按后进先出原则分配盘块。2.3.数据结构及各子程序：（1）structblock//成组链接的数据结构用链表来模拟组。{inta[10];intnum;structblock*next;};（2）structstack//堆栈的数据结构{int*base;int*top;intstacksize;};（3）structblock*creat(void)//创建100个编号0~99的块，10块为一组（4）voidprint(structblock*head)//打印块号（5）structblock*assign(structblock*head,structstack*s,intrecord[100],intfile[100][10],intn)分配块record[100]记录分配的文件号file[100][10]用来记录申请的文件号和申请到的块号n为分配块数（6）structblock*callback(structblock*head,structstack*s,intrecord[100],intfile[100][10])回收函数（7）堆栈的几个相关函数：voidinitstack(structstack*s)//栈的初始化voidpush(structstack*s,inte)//入栈intgettop(structstack*s)//获得栈顶元素intpop(structstack*s)//出栈intjudge(structstack*s)//判断栈是否为空voidtravelstack(structstack*s)//遍历栈五、课程设计总结与感想UNIX成组链接策略的模拟实现，为的就是能让我们理解UNIX管理磁盘空闲空间的方法——成组链接。所以这就要求我们一定要对这个课程有所一定的了解，然后通过编程模拟实现这个方法。#includestdio.h#includemalloc.h#includestdlib.h#includetime.h#definestack_init_size100//栈的初始化大小为100个单位#definestackincrement10structstack//堆栈的数据结构{int*base;int*top;intstacksize;};structblock//成组链接的数据结构{inta[10];intnum;structblock*next;};structblock*creat(void)//创建100个编号0~99的块，10块为一组{structblock*head;structblock*p1,*p2;intn=100,i;intm=0;//记录块号0~99p1=p2=(structblock*)malloc(sizeof(structblock));p1-num=m++;for(i=0;i10;i++)p1-a[i]=0;head=NULL;while(n!=0){if(n==100)head=p1;elsep2-next=p1;p2=p1;p1=(structblock*)malloc(sizeof(structblock));p1-num=m++;for(i=0;i10;i++)p1-a[i]=0;n--;}p2-next=NULL;p1=p2=head;m=1;while(p1-num90){//将下一组的10个块号存入上一组的块头中if(p1-num%10==0){for(i=0;i10;i++)p1-a[i]=m+9+i;}m++;p1=p1-next;};return(head);}voidprint(structblock*head)//打印块号{structblock*p;intn=0;p=head;if(head!=NULL){do{printf(%d,p-num);n++;if(n%10==0)printf(\n);p=p-next;}while(p!=NULL);}}//实现顺序栈的操作（栈空判断、出栈、入栈、读取栈顶元素,遍历栈）。voidinitstack(structstack*s)//栈的初始化{s-base=(int*)malloc(stack_init_size*sizeof(int));if(!s-base){printf(分配空间失败!);exit(0);}s-top=s-base;s-stacksize=stack_init_size;}voidpush(structstack*s,inte)//入栈{if(s-top-s-base=s-stacksize){s-base=(int*)realloc(s-base,(s-stacksize+stackincrement)*sizeof(int));if(!s-base){printf(存储分配失败!\n);exit(0);}s-top=s-base+s-stacksize;s-stacksize+=stackincrement;}*s-top++=e;}intgettop(structstack*s)//获得栈顶元素{inte;if(s-top==s-base){return0;}e=*(s-top-1);returne;}intpop(structstack*s)//出栈{inte;if(s-top==s-base)return0;elsereturne=*--s-top;}intjudge(structstack*s)//判断栈是否为空{if(s-top==s-base)return0;elsereturn1;}voidtravelstack(structstack*s)//遍历栈{inte;printf(栈中还有元素:\n);while(s-base!=s-top){e=*(--s-top);printf(%d,e);}printf(\n);}structblock*assign(structblock*head,structstack*s,intrecord[100],intfile[100][10],intn){//申请分配块structblock*p,*p1;structstack*ps;inti,e=10,t,j=0,r=0,m=0;ps=s;p1=p=head;for(i=0;i100;i++)if(record[i]==0)break;m=i;//记录分配的文件号record[m]=1;printf(分配file[%d]%d个：,m,n);while(n!=0){if(gettop(ps)==0){//若栈中没有元素，则将表中的一组入栈，每次入10块for(i=0;i10;i++){push(ps,p-num);p1=p;p=p-next;free(p1);//释放空间}push(ps,e);//栈顶放着栈中元素个数}else{//分配块t=pop(ps);file[m][r++]=pop(ps);//记录块分配给那个文件，哪几块分配给这个文件printf(%d,file[m][r-1]);if(t!=1)push(ps,t-1);elset=0;n--;}}printf(\n\n);returnp;}structblock*callback(structblock*head,structstack*s,intrecord[100],intfile[100][10]){structblock*p,*p1,*p2,*newhead=NULL;structstack*ps;inti,j,t,m=101,n=0;ps=s;p=head;for(i=0;i100;i++)if(record[i]==1)m=i;record[m]=0;//判断哪个文件分配了块，找最近的文件，将里面的块回收if(m==101)returnhead;//如果全部文件都还没有申请到块，回收失败，返回for(i=0;i10;i++)if(file[m][i]!=0)n++;printf(回收file[%d]%d个：,m,n);for(i=0;in;i++){if(gettop(ps)!=10)//若栈不是满的就入栈{t=pop(ps);push(ps,file[m][i]);//将文件m申请到的块号入栈，记录块号的file[m][i]置零printf(%d,file[m][i]);file[m][i]=0;t++;push(ps,t);}elseif(gettop(ps)==10){//栈满了就创建一个新链表，回收栈里面的块t=pop(ps);newhead=p1=p2=(structblock*)malloc(sizeof(structblock));p1-num=pop(ps);if(p!=NULL){for(j=0;j10;j++){p1-a[j]=p-num;p=p-next;}}while(t!=0){if(t==10)newhead=p1;elsep2-next=p1;p2=p1;p1=(structblock*)malloc(sizeof(structblock));p1-num=pop(ps);for(j=0;j10;j++)p1-a[j]=0;t--;}p2-next=NULL;push(ps,t);t=pop(ps);push(ps,file[m][i]);//将文件m申请到的块号入栈，记录块号的file[m][i]置零printf(%d,file[m][i]);file[m][i]=0;t++;push(ps,t);p1=newhead;//把新建立的表连到原来的表的前面p2=p1-next;while(p1-next!=NULL){p1=p2;p2=p1-next;}p1-next=head;head=newhead;}}printf(\n\n);return(head);}voidmain(){structstacks;structstack*ps;structblock*head,*p;intn,i,m=0;intfile[100][10]={0};//文件，用来记录申请的文件号和申请到的块号intrecord[100]={0};//记录，用来记录哪个文件申请了块ps=&s;initstack(ps);//初始化堆栈p=head=creat();printf(开始时空闲的块：\n\n);print(