磁盘存储空间地分配和回收

实习六 磁盘存储空间的分配和回收一、实习内容模拟磁盘空闲空间的表示方法，以及模拟实现磁盘空间的分配和回收。二、实习目的磁盘初始化时把磁盘存储空间分成许多块（扇区），这些空间可以被多个用户共享。用户作业在执行期间常常要在磁盘上建立文件或把已经建立在磁盘上的文件删去，这就涉及到磁盘存储空间的分配和回收。一个文件存放到磁盘上，可以组织成顺序文件（连续文件）、 链接文件（串联文件）、索引文件等，因此，磁盘存储空间的分配有两种方式，一种是分配 连续的存储空间，另一种是可以分配不连续的存储空间。怎样有效地管理磁盘存储空间是操作系统应解决的一个重要问题，通过本实习使学生掌握磁盘存储空间的分配和回收算法。三、实习题目本实习模拟三种磁盘存储空间的管理方法。第一题：连续的磁盘存储空间的分配和回收。提示:（1）要在磁盘上建立顺序文件时， 必须把按序排列的逻辑记录依次存放在磁盘的连续存 储空间中。可假定磁盘初始化时，已把磁盘存储空间划分成若干等长的块（扇区），按柱面 号和盘面号的顺序给每一块确定一个编号。随着文件的建立、删除、磁盘存储空间被分成许多区（每一区包含若干块），有的区存放着文件，而有的区是空闲的。当要建立顺序文件时 必须找到一个合适的空闲区来存放文件记录，当一个文件被删除时， 则该文件占用的区应成为空闲区。为此可用一张空闲区表来记录磁盘存储空间中尚未占用的部分，格式如下：序号起始空闲 块号空闲块个 数状态156未分配2143未分配32130未分配4空表目111133（2）要建立文件时，先查找空闲区表，从状态为“未分配”的登记栏目中找出一个块数能满足要求的区，由起始空闲块号能依次推得可使用的其它块号。若不需要占用该区的所有块时，则剩余的块仍应为未分配的空闲块，这时要修改起始空闲块号和空闲块数。若占用了该区的所有块，则相应登记栏中的状态修改成“空表目”。删除一个文件时，从空闲区表中 找一个状态为“空表目”的登记栏目，把归还的起始块号和块数填入对应的位置。磁盘存储空间的分配和回收算法类似于主存储器的可变分区方式的分配和回收。同学们可参考实习四的第一题。（3）当找到空闲块后，必须启动磁盘把信息存放到指定的块中，启动磁盘必须给出由三个参数组成的物理地址：柱面号、磁道号和物理记录号。故必须把找到的空闲块号换算成磁盘的物理地址。为了减少移臂次数，磁盘上的信息按柱面上各磁道顺序存放。现假定一个盘组共有 200个柱面，(编号 0-199)每个柱面有20个磁道(编号0-19，同一柱面上的各磁道分布在各 盘面上，故磁道号即盘面号。)，每个磁道被分成等长的6个物理记录(编号 0-5,每个盘面被分成若干个扇区，故每个磁道上的物理记录号即为对应的扇区号。)。那么，空闲块号 与磁盘物理地址的对应关系如下：m= 空闲块号 6假设M=厂空闲块号一6则物理记录号 =m -磁道号= M 20柱面号=M 20(4) 删除一个文件时，从文件目录表中可得到该文件在磁盘上的起始地址和逻辑记录个数，假定每个逻辑记录占磁盘上的一块，则可推算出归还后的起始空闲块号和块数，登记到 空闲区表中。换算关系如下:起始空闲块号=(柱面号 20+磁道号)6+物理记录号 空闲块数=逻辑记录数(5) 请设计磁盘存储空间的分配和回收程序，要求把分配到的空闲块转换成磁盘物理地址，把归还的磁盘空间转换成空闲块号。假定空闲区表的初值如提示(1)中指出，现有一文件要占用 10块，运行你所设计的分 配程序，显示或打印分配后的空闲区表以及分配到的磁盘空间的起始物理地址。然后，有一文件被删除，它占用的磁盘空间为： 1号柱面2号磁道，0号物理记录开始的 4块，运行你 所设计的回收程序，显示或打印回收后的空闲区表。第二题：用位示图管理磁盘存储空间提示:(1) 为了提高磁盘存储空间的利用率，可在磁盘上组织成链接文件、索引文件，这类文件可以把逻辑记录存放在不连续的存储空间。为了表示哪些磁盘空间已被占用，哪些磁盘空间是空闲的，可用位示图来指出。位示图由若干字节构成， 每一位与磁盘上的一块对应，“1状态表示相应块已占用，“0”状态表示该块为空闲。位示图的形式与实习四中的位示图一样，但要注意，对于主存储空间和磁盘存储空间应该用不同的位示图来管理，绝不可混用。(2) 申请一块磁盘空间时，由分配程序查位示图，找出一个为“0”的位，计算出这一位对应块的磁盘物理地址， 且把该位置成占用状态 “ 1”。假设现在有一个盘组共 80个柱面, 每个柱面有两个磁道， 每个磁道分成4个物理记录。那么，当在位示图中找到某一字节的某 一位为“ 0”时，这个空闲块对应的磁盘物理地址为：柱面号=字节号磁道号=位数 4物理记录号=位数4(3) 归还一块磁盘空间时，由回收程序根据归还的磁盘物理地址计算出归还块在位示图 中的对应位，把该位置成“ 0”。按照(2)中假设的盘组，归还块在位示图中的位置计算如 下：字节号=柱面号位数=磁道号4+物理记录号(4) 设计申请一块磁盘空间和归还一块磁盘空间的程序。要求能显示或打印程序运行前和运行后的位示图；分配时把分配到的磁盘空间的物理地址显示或打印出来，归还时把归还块对应于位示图的字节号和位数显示或打印出来。(5) 假定已有如表6-1的磁盘空间被占用了，现在要申请五块磁盘空间，运行分配程序，按(4)中要求显示或打印运行的结果。然后再归还如表 6-2的空间，运行回收程序，按(4)中的要求显示或打印运行结果。表6-1柱面 号磁道 号物理记录号00 1002010013100112表6-2柱面 号磁道 号物理记录号002010101第三题：模拟 UNIX系统的空闲块成组链接法，实现磁盘存储空间的管理。提示:(1) 假定磁盘存储空间已被划分成长度为n的等长块，共有M块可供使用。UNIX系统中采用空闲块成组链接的方法来管理磁盘存储空间，将磁盘中的每N个空闲块(NM )分成一组，最后一组可以不足N块，每组的第一块中登记了下一组空闲块的块数和块号，第一组的块数和块号登记在专用块中，登记的格式如下：当第一项内容为“ 0”时，则第二项起指出的空闲块是最后一组。(2) 现模拟UNIX系统的空闲块成组链接，假定共有8块可供使用，每3块为一组，则空闲块成组链接的初始状态为：第三组第二组开始时，空闲块号是顺序排列的，但经若干次的分配和归还操作后，空闲块的链接就未必按序排列了。用二维数组 A : array 0M-1 of array 0n-1来模拟管理磁盘空间，用Ai表示第I块，第0块A0作为专用块。(3) 成组链接的分组情况记录在磁盘物理块中，为了查找链接情况，必须把它们读入主 存，故当磁盘初始化后，系统先将专用块内容复制到主存中。定义一个数组MA存放专用块内容，即MA: =A0。申请一块磁盘空间时，查MA，从中找出空闲块号，当一组的空闲块只剩第一块时，则应把该块中指出的下一组的空闲块数和块号复制到专用块中，然后把该块分配给申请者。当一组的空闲块分配完后则把专用块内容(下一组链接情况)复制到主存，再为申请者分配。分配算法如图6-1。图6-1采用成组链接的分配算法i MAC & | MAf一门=11开始否MAC 0 1 = 3AlA M AE 0 :=MAE 1MACO+(4) 归还一块时给出归还的块号，叵当前组不满规定块数时，将归还块登记入该组；若 当前组已满，则另建一新组，这时归还块作为新一组的第一块，应把主存中登记的一组链接情况MA复制到归还块中，然后在 MA重新登记一个新组。归还一块的算法如图6-2。图6-2 采用成组链接的回收算法(5) 设计分配和归还磁盘空间的程序，能显示或打印分配的磁盘空间的块号，在完成一次分配或归还后能显示或打印各空闲块组的情况(各组的空闲块数和块号)。本实习省去了块号与物理地址之间的转换工作，而在实际的系统中必须进行块号与物理地址的转换工作。(6) 运行你所设计的程序，假定空闲块链接的初始状态如提示(2)，现先分配 4块,再依次归还第2块和第6块。把执行后分配到的块号依次显示或打印出来，且显示或打印空闲块组的情况。在上次执行的基础上继续分配3块，然后归还第1块，再申请5块，显示或打印依次分配到的块号及空闲块组情况。四、相关数据结构及说明struct freeblock int FBbegin;起始空闲块号int num;/空闲块数 char state;/状态 struct freeblock *n ext; struct filetowrite char n ame10; 文件名int size;/文件大小int addr_cylinder;/装入磁盘的首地址_柱面号 int addr_track;/装入磁盘的首地址 _磁道号 int addr_ note;/装入磁盘的首地址物理记录号 struct filetowrite *n ext; 六、源代码及注释1、题一源代码：#in clude#in cludeint getmalloc()分配磁盘空间 int flag=0;struct freeblock *p=FBhead;struct filetowrite *File;File=(struct filetowrite *)malloc(sizeof(struct filetowrite);printf(输入要装入的文件名：”)；scan f(%s,File- name);printf(”输入所需的磁盘空间大小：);sca nf(%d,&File-size);for(p=FBhead-n ext;p!=NULL;p=p-n ext) if(File-size)num)/ 分配空间flag=1;File-addr_cyli nder=(p-FBbegi n)/6)/20;File-addr_track=(p-FBbegi n)/6)%20;File-addr_ note=(p-FBbegi n)%6;File-next=Filehead-next;/ 加入文件链表Filehead-n ext=File;if(File-size)num)/修改该快的起始地址和块数p-FBbegi n=p-FBbegi n+File-size;p-num=p-num-File-size;else p-state=U;break; if(flag=0)printf(抱歉！目前没有足够的磁盘空间分配给该文件.n);else printf(分配磁盘成功！n该文件的物理地址：n柱面号t磁道号t物理块号n );prin tf( %dt %dt %dn,File-addr_cyli nder,File-addr_track,File-addr_ino te); int deletelfree()/ 回收磁盘空间char n ame10;int flag=0;struct filetowrite *p;printf(”输入要删除的文件名：);scan f(%s,&n ame);for(p=Filehead;p-n ext!=NULL;p=p-n ext)if(strcmp(p-next-name,name)=0)/ 找至U该文件flag=1;int funion=0,nunion=0;int m=p-n ext-addr_cyli nder;int n=p-n ext-addr_track;int k=p-n ext-addr_ no te;int addr=(m*20+n)*6+k; 起始空闲块号int tail=p-n ext-size+addr;struct freeblock *pno de,* qno de,*t no de,*s no de;pno de=FBhead-n ext;while(pnode!=NULL)先考虑和后面的部分或许有合并的情况if(p no de-FBbegi n)=tail)pno de-FBbegi n=addr;pno de-num=pno de-nu m+p-n ext-size;nunion=1;break;pno de=p no de-n ext;qno de=FBhead-n ext;while(qnode!=NULL)再考虑是否和前面的可以合并if(qno de-FBbegi n+qno de-num )=addr)if(nunion=0)qno de-num=qno de-nu m+p-n ext-size;funion=1;break;elseqno de-num=qno de-nu m+p no de-num;tnode=FBhead;while(t no de-n ext!=p no de)tno de=t no de-n ext;tno de-n ext=p no de-n ext;free(p no de);funion=1;break;qno de=qno de-n ext;if(funion=0&nun io n=0) 若没有和前面的或后面的进行合并，则新建一个表目 sno de=(struct freeblock *)malloc(sizeof(struct freeblock);sno de-FBbeg in=addr;sno de-num=p-n ext-size;sno de-state=F;if(FBhead- next=NULL)FBhead-n ext=s no de;sno de-n ext=NULL;elsesno de-n ext=FBhead-n ext;FBhead-n ext=s no de;struct filetowrite *q;q=p-next;/除该文件p-n ext=p-n ext- n ext;free(q);break; if(flag=0)printf(没有该文件!n);else printf(文件删除成功!n); int dispfree()/显示磁盘空闲区表int i=1;struct freeblock *p=FBhead;printf(n磁盘空闲区表n);printf(”序号t起始空闲块号t空闲块个数t状态n); for(p=FBhead-n ext;p!=NULL;p=p-n ext)if(p-state)=F)printf( %dt %dtt %dtt 未分配 n”,i+,p-FBbegin,p-num); elseprintf( %dttttt 空表目 n,i+); int dispfile()char n ame10;struct filetowrite *p=Filehead; prin tf( 输入要查看的文件名：”)；sca nf(%s, &n ame);for(p=Filehead-n ext;p!=NULL;p=p-n ext)if(strcmp(p-n ame ,n ame)=0)printf(该文件的物理地址：n柱面号t磁道号t物理块号n );printf(” %dt %dt %dn ,p-addr_cyli nder,p-addr_track,p-addr_ no te);break; - - -if(p=NULL)printf(没有该文件!n); int mai n() int n,i,AMAX,BMAX;/AMAX表示起始空闲块号，BMAX表示空闲块个数char ch;struct freeblock *pn ew;FBhead=(struct freeblock *)malloc(sizeof(struct freeblock);FBhead- next=NULL;printf(”输入磁盘空闲区个数：”)；scan f(%d,&n);for(i=1;in ext=NULL;pn ew-n ext=FBhead-n ext;FBhead-n ext=p new;printf(”起始空闲块号：);sca nf(%d,&pn ew-FBbegi n);printf(空闲块个数：);sca nf(%d,&pn ew-nu m);pn ew-state=F;pn ew=p new-n ext;Filehead=(struct filetowrite *)malloc(sizeof(struct filetowrite);Filehead- next=NULL;do system(cls);prin tf(ntt prin tf(ttt1.prin tf(ttt2.prin tf(ttt3. prin tf(ttt4.*新建文件n); 删除文件n); 查看磁盘n); 查看文件n);王采单*nn);printf(ttt5.退出 n); printf(请选择：);scan f(%c,&ch); switch(ch) case 1:getmalloc();system(pause);break;case 2:deletelfree();system(pause);break;case 3:dispfree();system(pause);break;case 4:dispfile();system(pause);break;case 5:exit(1);break;default:printf(输入错误!请重新输入.n);prin tf(n); getchar(); while(ch!=4); return 0;2、题二源代码:#in clude #i nclude void Initbitmap(int map88) int cyli nder,track,sector;char choice=Y;printf(初始化位视图.n);while(choice=y|choice=Y) printf(” 柱面号:”);scan f(%d,&cyli nder);printf(” 磁道号:);scan f(%d, &track);printf(物理记录号:);scan f(%d, §or);mapcyli nder4*track+sector=1;prin tf(co ntiu ne?);getchar();scan f(%c,&choice); void allocate(int map88) int i,j;int flag=0;int cyli nder,track,sector;for(i=0;i8;i+) for(j=0;j8;j+)if(mapij=0)mapij=1;flag=1;break;if(flag=1) break;if(flag=1)cyli nder=i;track=j/4; sector=j%4;printf(”分配到的柱面号、磁道号、物理记录数);prin tf(%dt%dt%d,cyli nder,track,sector);prin tf(n); else printf(空间不足，分配失败!); void reclaim(int map88) int cyli nder,track,sector;printf(” 柱面号:);scan f(%d,&cyli nder);printf(” 磁道号:);sca nf(%d, &track);printf(物理记录号:);scan f(%d, §or);if(mapcyli nder4*track+sector=0) printf(”此块为未分配块！回收出错！”)；getchar(); else mapcyli nder4*track+sector=0;printf(回收块对应的字节号 :%4dt 位数:4dn,cylinder,4*track+sector); void mai n() int bitmap88; int i,j; int choice;or(i=0;i8;i+) for(j=0;j8;j+)bitmapij=0; In itbitmap(bitmap);while(1) printf(n请输入选择:);printf(1-分配，2-回收，3-显示位示图，0-退出n);scan f(%d,&choice);switch(choice) case 1:allocate(bitmap);break;case 2:reclaim(bitmap);break;case 3:for(i=0;i8;i+)for(j=0;j8;j+)prin tf(%8d,bitmapij);prin tf(n);break;case 0:exit(0);default:printf(错误选择！ ”);break; 3、第三题源程序:#in cludeint MA4; int/*空闲块数组*/A94=3,1,2,3,3,4,5,6,0,0,0,0,0,0,0,0,3,0,7,8,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0;/*磁盘空间 */int mark9;/*存放已分配的块*/int No=0; /*已分配的块数*/ void display1()int i,j,temp,co unt,No=0;if(MA1!=0)i=MA0;prin tf(ngroup1:); for(j=1;j=i;j+)prin tf(%d,MAj);mark+No=MAj; temp=MA1;coun t=2;while(Atemp1!=0)prin tf(ngroup%d:,cou nt);i=Atemp0;for(j=1;j=i;j+)prin tf(%d,Atempj);mark+No=Atempj;coun t+;temp=Atemp1;prin tf(ngroup%d:,co un t); i=Atemp0;for(j=2;j0)prin tf(%d,Atempj);mark+No=Atempj;else i=MAO;if(i=1)prin tf(nThe blocks are all assig ned); elseprin tf(ngroup1:);for(j=2;j=i;j+)prin tf(%d,MAj);mark+No=MAj; void display() /*显示分组情况*/ int i,j; if(MA0!=0) display1();elsei=MA1;for(j=0;j1)/*若该组不止一个空闲块*/i=MA0;s=MAi;MA0-;prin tf(n nu mber of the block:%d,s);else if(MA0=1)/*只剩一个空闲块 */if(MA1!=0)/*还有其它空闲块组*/s=MA1;for(i=0;i=3;i+)A0i=Asi;MA0-;prin tf(nnu mber of the block:%d,s);else/*没有其它空闲块组*/ prin tf(nThere isnt any space);return;else/*当前组已分配完*/for(i=0;i=3;i+)/*显示分组情况*/*回收空闲块*/MAi=A0i; assig n(); display();void callback() int i,j,temp;prin tf(nin put the No. of the block you want to callback:);sca nf(%d,&j);getchar();/*得到待回收的空闲块号*/if(marktemp=j)for(temp=1;temp=No;temp+)break;if(tempNo+1)/*若该空闲块已在，退出*/prin tf(nThe block is in the disk);return;if(MA03)/*当前组不满 3块*/i=MA0;elseMAi+1=j;/*已有3块*/MA0+;for(i=0;i=3;i+)Aji=MAi;MA0=1;MA1=j;display();/*显示*/void menu()/*功能选择函数*/ int choice;char judge;prin tf(nin put your choice:(1-assig n, 2-callback):); scan f(%d,&choice);getchar(); if(choice=1)assig n();else if(choice=2)callback();elseprin tf(nin valid comma nd!);prin tf(ncontinue or no t (y-Yes ,n-Not):);sca nf(%c,&judge);getchar();if(judge=y)men u();else prin tf(nNow the graph is:);display(); prin tf(npress any key to quit);getchar();int mai n() int i;for(i=0;i=3;i+)MAi=A0i;display(); men u(); 七、运行结果1、题一运行结果:区区区区区区区区区区 扇扇扇扇扇扁扇扇扇扇 个个个个个个个个个个 2301200123 扌r?gr7gr7grggp&nmpgr?gr7占F72、题二运行结果:可妗化付现亂 拄面号汨 磁道号F 厠理记录号:丄 contiunB7(Y/N)y 柱面号：Q 遊這号;Q物理记杲号：2 contiune?(Y/N)y 柱面号：0 磁道号：1物理记录号：0 contiuna?(YZN)y 柱面号：0 赃道号：1物理记录号：3 c Dntiune ? (Y/N) y 柱面号；1 磁道号：。物理记录号：0 c onti une? (Y ZN) y IE面号：1 就道号 物理记录号煌 contiune?(Y/N)ri请输入选摄：1-芳配.2!-回收.3显示位示图，0退出30110100110000010000000000000000000000000000000000000000000000000青输入选择：1分6己，回收，3显示位示图，0退岀 *面号：0曲道号：0吻理记录号 2旦收块对应胡字节号：。位数：2靑输入选择:卜-分配2-回收，3显示位示图，Q-退岀J虫面号:0茲道号划理记录号0可收块对应曲字节号：0位数;：4諭入选择:1分配，A回收，2显示位示图，o-fi岀注面号:1兹道号:0珈理i己录号 1比块为未分赳块！回收岀错！青输入选择:1分0占2-回收，3显示位示图，Q退出3、题三运行结果:group 1:123group2:456group3：7 8input your choice：(1一一assign, 2一一callback?:1 nuinber of the block:3group 1：12group2:456group3:7 Scontinue or ncit (yYes, nN口t):yir)ut your choice: (1一一assign, 2一-callback) :2input the No. of the block you want to callback:2group1：122group2：456且t口up3:78continue or not (y一Yes, nMot):yinput your choice：(l-assign, 2一一callback):2input theNo.of the block you want to callback:6group 1:6group2:122group3:456group4:78