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

1、实习六磁盘存储空间得分配与回收一、实习内容模拟磁盘空闲空间得表示方法，以及模拟实现磁盘空间得分配与回收、二、实习目得磁盘初始化时把磁盘存储空间分成许多块（扇区）,这些空间可以被多个用户共享。用户作业在执行期间常常要在磁盘上建立文件或把已经建立在磁盘上得文件删去,这就涉及到磁盘存储空间得分配与回收、一个文件存放到磁盘上，可以组织成顺序文件（连续文件卜链接文件（串联文件）、索引文件等，因此，磁盘存储空间得分配有两种方式，一种就是分配连续得存储空间，另一种就是可以分配不连续得存储空间、怎样有效地管理磁盘存储空间就是操作系统应 解决得一个重要问题，通过本实习使学生掌握磁盘存储空间得分配与回收算法。三、

2、实习题目本实习模拟三种磁盘存储空间得管理方法。第一题：连续得磁盘存储空间得分配与回收。提示:（1）要在磁盘上建立顺序文件时，必须把按序排列得逻辑记录依次存放在磁盘得连续存 储空间中。可假定磁盘初始化时，已把磁盘存储空间划分成若干等长得块（扇区），按柱面号与盘面号得顺序给每一块确定一个编号、随着文件得建立、删除、磁盘存储空间被分成许多区（每一区包含若干块），有得区存放着文件，而有得区就是空闲得。当要建立顺序文件时必须找 到一个合适得空闲区来存放文件记录，当一个文件被删除时，则该文件占用得区应成为空闲区。为此可用一张空闲区表来记录磁盘存储空间中尚未占用得部分，格式如下：序号起始空闲 块号空闲块个

3、数状态156未分配2143未分配32 130未分配4空表目M（2）要建立文件时，先查找空闲区表，从状态为“未分配”得登记栏目中找出一个块数能 满足要求得区，由起始空闲块号能依次推得可使用得其它块号、若不需要占用该区得所有块时，则剩余得块仍应为未分配得空闲块，这时要修改起始空闲块号与空闲块数、若占用了该区得所有块，则相应登记栏中得状态修改成“空表目”。删除一个文件时，从空闲区表中找一个状态为“空表目”得登记栏目，把归还得起始块号与块数填入对应得位置。磁盘存储空间得分配与回收算法类似于主存储器得可变分区方式得分配与回收。同学们可参考实习四得第一题。（3）当找到空闲块后，必须启动磁盘把信息存放到指定

4、得块中，启动磁盘必须给出由三个参数组成得物理地址：柱面号、磁道号与物理记录号。故必须把找到得空闲块号换算成磁盘得物理地址。为了减少移臂次数，磁盘上得信息按柱面上各磁道顺序存放。现假定一个盘组共有200个柱面，（编号0 199）每个柱面有2 0个磁道（编号0 19,同一柱面上得各磁道分布在各盘面 上,故磁道号即盘面号、），每个磁道被分成等长得 6个物理记录（编号0 5,每个盘面被分成若 干个扇区，故每个磁道上得物理记录号即为对应得扇区号。）。那么，空闲块号与磁盘物理地址得对应关系如下假设M=空闲块号,空闲块号6 6贝U 物理记录号 =m 磁道号=M 20柱面号=M :20(4) 删除一个文件时，

5、从文件目录表中可得到该文件在磁盘上得起始地址与逻辑记录个数,假定每个逻辑记录占磁盘上得一块，则可推算出归还后得起始空闲块号与块数，登记到空闲区表中。换算关系如下：起始空闲块号=(柱面号20+磁道号)6+物理记录号空闲块数=逻辑记录数(5) 请设计磁盘存储空间得分配与回收程序，要求把分配到得空闲块转换成磁盘物理地址，把归还得磁盘空间转换成空闲块号、假定空闲区表得初值如提示(1)中指出，现有一文件要占用1 0块，运行您所设计得分配程序，显示或打印分配后得空闲区表以及分配到得磁盘空间得起始物理地址。然后，有一文件被删除,它占用得磁盘空间为：1号柱面2号磁道，0号物理记录开始得4块，运行您所设计得回收

6、 程序，显示或打印回收后得空闲区表。第二题：用位示图管理磁盘存储空间提示:(1) 为了提高磁盘存储空间得利用率，可在磁盘上组织成链接文件、索引文件，这类文件可以把逻辑记录存放在不连续得存储空间、为了表示哪些磁盘空间已被占用，哪些磁盘空间就是空闲得，可用位示图来指出。位示图由若干字节构成，每一位与磁盘上得一块对应，“1 ”状态表示相应块已占用，“0"状态表示该块为空闲。位示图得形式与实习四中得位示图一样，但要注意，对于主存储空间与磁盘存储空间应该用不同得位示图来管理，绝不可混用、(2) 申请一块磁盘空间时，由分配程序查位示图，找出一个为“ 0”得位，计算出这一位对应块得磁盘物理地址，且

7、把该位置成占用状态“1”。假设现在有一个盘组共80个柱面，每个柱面有两个磁道，每个磁道分成4个物理记录、那么，当在位示图中找到某一字节得某一位为“ 0”时，这个空闲块对应得磁盘物理地址为：柱面号=字节号磁道号=:位数4物理记录号=位数4(3) 归还一块磁盘空间时，由回收程序根据归还得磁盘物理地址计算出归还块在位示图中得对应位，把该位置成“ 0"。按照(2)中假设得盘组，归还块在位示图中得位置计算如下：字节号=柱面号位数=磁道号4+物理记录号(4) 设计申请一块磁盘空间与归还一块磁盘空间得程序。要求能显示或打印程序运行前与运行后得位示图；分配时把分配到得磁盘空间得物理地址显示或打印出来

8、，归还时把归还块对应于位示图得字节号与位数显示或打印出来。(5 )假定已有如表 6-1得磁盘空间被占用了 ，现在要申请五块磁盘空间，运行分配程序， 按(4)中要求显示或打印运行得结果。然后再归还如表6- 2得空间，运行回收程序，按(4)中得要求显示或打印运行结果。柱面 号磁道 号物理记录号001002010013100112柱面 号磁道 号物理记录号002010101第三题：模拟UNIX系统得空闲块成组链接法，实现磁盘存储空间得管理。提示：(1)假定磁盘存储空间已被划分成长度为n得等长块，共有M块可供使用。UN I X系统中采用空闲块成组链接得方法来管理磁盘存储空间，将磁盘中得每N个空闲块(N

9、 M)分成一组，最后一组可以不足 N块，每组得第一块中登记了下一组空闲块得块数与块号，第一组得块数与块号登记在专用块中，登记得格式如下：当第一项内容为“ 0"时,则第二项起指出得空闲块就是最后一组。(2)现模拟U N I X系统得空闲块成组链接，假定共有8块可供使用，每3块为一组，则空闲 块成组链接得初始状态为：第一粗第二组那三齟开始时，空闲块号就是顺序排列得，但经若干次得分配与归还操作后，空闲块得链接就未 必按序排列了、用二维数组A :a r ray 0M-1 o f a rr a y 0n1来模拟管理磁盘空间，用A i表示第I块，第0块A 0作为专用块。(3 )成组链接得分组情况

10、记录在磁盘物理块中，为了查找链接情况，必须把它们读入主存，故当磁盘初始化后，系统先将专用块内容复制到主存中。定义一个数组MA存放专用块内容，即M A: =A 0。申请一块磁盘空间时，查MA,从中找出空闲块号，当一组得空闲块只剩 第一块时，则应把该块中指出得下一组得空闲块数与块号复制到专用块中，然后把该块分配给申请者。当一组得空闲块分配完后则把专用块内容(下一组链接情况)复制到主存，再为申请者分配。分配算法如图 6 1、图6-1采用成组链接得分配算法(4)归还一块时给出归还得块号，叵当前组不满规定块数时，将归还块登记入该组；若当前 组已满，则另建一新组，这时归还块作为新一组得第一块，应把主存中登

11、记得一组链接情况MA复制到归还块中，然后在MA重新登记一个新组、归还一块得算法如图6 2、图6 - 2 采用成组链接得回收算法(5 )设计分配与归还磁盘空间得程序，能显示或打印分配得磁盘空间得块号，在完成一次分配或归还后能显示或打印各空闲块组得情况(各组得空闲块数与块号)。本实习省去了块号与物理地址之间得转换工作，而在实际得系统中必须进行块号与物理地址得转换工作、(6) 运行您所设计得程序，假定空闲块链接得初始状态如提示(2)，现先分配4块，再依次归还第2块与第6块。把执行后分配到得块号依次显示或打印出来，且显示或打印空闲块组得情况。在上次执行得基础上继续分配3块，然后归还第1块,再申请5块，

12、显示或打印依次分配到得块号及空闲块组情况、四、相关数据结构及说明st r uct freeblock int FB b eg in;/起始空闲块号i nt num;空闲块数ch a r st a te;/状态struct fr ee bl o ck *ne xt; s t r uct ch a r na me10 ;/文件名int siz e ;/文件大小int ad d r_c yl inder;/装入磁盘得首地址 _柱面号i n t a d d r_ track;/装入磁盘得首地址 _磁道号in t a d d r_note;/装入磁盘得首地址 物理记录号s true t *nex t ;

13、 六、源代码及注释1、题一源代码：# i n clud e < st dlib.h>#include std io.h>int getmallo c ()/分配磁盘空间 int flag= 0 ;s t ruct freeblock 衣 p=F B head;str u ct *File;File = (st r uct *)mallo c (si z eo f(struc t );pr i ntf(”输入要装入得文件名：”)；sc an f (” %s",Fil e> name);p r in t f("输入所需得磁盘空间大小：")；sc

14、an f ("%d", &Fi le >s i z e);for(p=F B he a d> next;p ! =NULL;p= p> nex t)i f (File-> s iz e )<=(p > num)/分配空间fla g=1;F il e > a ddr cy li n der=(p- > FB b egin)/ 6 )/20;Fil e> addr_t rack=(p- > FBbeg i n)/6)% 2 0;Fil e - > ad dr _no te=(p- > FBb e g

15、 i n)%6;Fil e ->nex t=n ext ;/ /加入文件链表next=F il e;if (Files ize)(p> n u m) / /修改该快得起始地址与块数p- > FB b egi n=p> FBbegi n+Fil e -> siz e ;p-> num= p> num File>s i ze ;else p >s tate='U'break; if(fl a g= 0)pr int f(”抱歉！目前没有足够得磁盘空间分配给该文件、n”)；el se printf( ”分配磁盘成功！ n该文件得物

16、理地址：n柱面号t磁道号 t物理块号n );print f(” dt %dt d n” ,Fi le -addr _c ylinder,File -add r_tr ack, F ile- ad dr _no te); i nt d el e te lfr ee()/ 回收磁盘空间 char name10 ;int flag=0;st ruc t p;pr intf (输入要删除得文件名：);scanf(" s ” ,&na me );f o r( p =>next != N U LL;p=p > n e x t)if( str cmp( p>ne xt-&

17、gt; n am e,na me)= 0)/找到该文件flag=1;i nt fu ni on=0,nunion=0;int m =p>n ext-> a ddr_ cy linder ;int n=p >next>addr_track;int k=p >next>add r_note ;i nt a ddr=(m*20+n)*6+k;/ /起始空闲块号int tai l=p->next>s ize+a ddr;st ruc t f re eblo ck *p node ,qnod e,*tnod e,sno de ;pnod e=FBhea d

18、 ne xt;whil e (pn o de! =NUL L )/先考虑与后面得部分或许有合并得情况if(p n ode->F B b e gin) = =t ail )pnode> FBbe g i n =a d d r ;pnod e> num= pn ode-> n u m+ p> next > s i z e;nu n io n= 1;brea k;p no de=pnod e >next;q no de=FBhead >ne x t;w h i le(qnod e != NU LL)再考虑就是否与前面得可以合并if( q no de&g

19、t;FBbe g i n+ q no de- > num)= = a d d r)if(nunion=0)qn ode-> num=qno de>num+p>next->si ze ;fun io n = 1 ;bre a k;el s eqnode-> n um = qnode> num+pnod e >num;tnode=FBhead ;whil e ( tn ode-> n e xt! = p no de)tnode=tnode > nex t ;t no de >next= pno de>next;fr ee (

20、p node);funi on =1;break;qnod e=q node->next;if( f u n ion=0 & & nunion=0) / /若没有与前面得或后面得进行合并,则新建一个表 目snode = (s t ruct f re e b loc k 衣)m a l loc(si z eof(s t r u ct f ree b l o ck);sn ode>F Bbegin=a ddr;snod e-> num =p >next-> si ze;snode->stat e= F'if (FB h ead>ne

21、 xt= =NU L L)F Bhe ad>next=sno de;s node> nex t= NULL;elses no de ->n ext=FBhead> ne xt ;FB head>next=snod e ;s tru ct 衣 q;q =p>n ext;/除该文件p>n ext= p> next> ne xt;free(q);b r eak; i f(flag=0)p ri n tf(”没有该文件!n”)；else printf(”文件删除成功！ n”); int dispf r ee()显示磁盘空闲区表int i= 1 ;s

22、 truct free b l o ck *p =FBhead;p rintf( ” n 磁盘空闲区表 n");pr i nt f(”序号t起始空闲块号 t空闲块个数t状态n”)；fo r (p=FBhead >next;p!=NULL;p = p> nex t)if(p > stat e)='F')printf( ” d t %d、tt % dt、t 未分配 n ”，i+,p >FBbe g i n , p>num);els ep ri ntf (” % dt tt 空表目 n", i +); i nt dispfi 1 e(

23、)char n ame10 ;stru c t *p=; pr intf ("输入要查瞧得文件名：”)；scanf(” %s” ,&name);for(p =>nex t;p! = N ULL;p=p > next)if(strcmp(p- > nam e ,n a me)=0)p rin t f(”该文件得物理地址：n柱面号t磁道号t物理块号n );p ri n tf(" %d t % d t % d n", p ->addr cyl i nder,p-> a d dr_track,p >a d dr_n o t e)

24、;b rea k; if (p= N UL L )prin tf (没有该文件！ n” ); int main () i n t n,i,AM AX, B：M AX;/A: MAX 表示起始空闲块号 ,B : M AX表示空闲块个数char ch;s tru c t f reeblock *p new ;F Bh e a d =(str u ct fre e b 1 ock *) m alloc( s izeof( s truct fr eeb lo c k);FBhe a d >n e xt = NU L L ;prin tf(" 输入磁盘空闲区个数 ：);scanf(&qu

25、ot;%d” ,&n);f or ( i= 1;i =n; i +)pnew=(stru c t freebl o ck *)mallo c (sizeof(struct f reebloc k);pnew> next=NULL;pnew ->ne x t= FBh ead >nex t ;F Bhead ne xt=p new;pri ntf ("起始空闲块号 ：” );sc anf(”% d",& p newF Bbegin);pr int f(" 空闲块个数 ：” );s canf("%d",&p

26、 n ew >n um); pn e ws tate=' F; pnew =pn ew -> next; (struct *)m a lloc (si zeof(struct );n ext=NULL;do sys t em(” cl s” );printf( " n、t、t*、 t t -l、/,主菜单* * n n");prin tf (" t t1.新建文件 n"); p ri n tf ("ttt 2、删除文件 n”);p r i ntf tt t3。查瞧磁盘 n");pr int f (" tt

27、t4、查瞧文件 n ");p ri n t f(" t t 5.退出 n” );printf("请选择:");sea n f (” c”，& ch);swi t c h(ch )case ' 1':ge t malloc();s y stem("pause" );b r eak; c ase 2 / : del et e l f ree(); s ys t em ("pause");br e ak;ca s e '3' :dis p fr e e();syst e m(&qu

28、ot; paus e" );br e ak; c ase '4':dispfil e();s ystem("pause");brea k;ca se ' 5:exit(1);bre a k;defau l t:pr int f(”输入错误！请重新输入、n");pri n tf (” n” );g etchar(); while( ch！ =4);retu rn 0;2、题二源代码 : include s tdi o、 h# i n c lud e v proc e ss.hvoi d I n itb i tmap(int map8

29、8) i nt cylinde r ,t r ack ,secto r;char choi ce =' Y'p r in t f("初始化位视图.°n ");w h i le(choi c e= / y'| | choice= ' Y' )printf( "柱面号 :");scanf("%d",&cylinder);pr intf ("磁道号 :” );s canf(” %d", & tr ack );pr intf (”物理记录号 :” );sca

30、nf("%d",&sector);mapcy linder4trac k+sec tor =1; p ri n tf (”c ontiu ne？ ");getchar ();scanf(”c",& c ho ice ); vo id alloca te (i n t m a p8 8 ) in t i, j ;int flag = 0;i nt cylinder,track,secto r ;fo r ( i = 0 ; i <8;i+) f or(j=0;j v 8;j+)if( ma pi ： j = 0)mapi j=1;f

31、lag=1;b re ak;if(f la g= 1) br eak ;i f (flag=1)c yl ind er=i; trac k = j / 4 ; s ect or=j %4;prin t f("分配到得柱面号、磁道号、物理记录数" );pr i nt f(” d t% dt%d ",c y lind e r,track ,se ctor);p r in t f( ” n" ); e ls e printf(”空间不足，分配失败！”)； void reclai m (i n t map 8 8) int cyli nd er,t rac k,

32、 s ector;p rin tf (”柱面号 :");sea nf(" %d”，& cyl in d e r);p r in t f("磁道号:"); scanf(”% d” ,&t rac k); prin tf (”物理记录号 :"); s canf("%d",& s ector );if(map c ylinder4tr ack +s ector=0) p ri n tf("此块为未分配块！回收出错！ ");getc har(); el s e mapcy li nd er

33、 4track+s ec tor=0;printf(” 回收块对应得字节号：% 4dt 位数：% 4dn ",cyli n de r ,4 * tra c k+s e c tor); void m a in() in t b it m ap 88; i n t i , j ; int c h oi ce;o r ( i =0; i8 ;i+ ) fo r (j=0;j<8;j+ + )b i t map ij = 0; Initbi t map( b itm a p);while(1) p r in请输入选择：”)；p r int f (” 1-分配,2- 回收，3- 显示位示

34、图,0-退出 n");sca nf( ” d"，&cho ice ); swi t c h (choic e ) case 1：allocate (bitmap);b r eak;case 2:recl aim( b itmap);bre a k;case 3 :for(i=0;i<8;i+)for(j= 0 ;j 8; j+ )pri ntf(" % 8d" ,bitmap ij );printf(" n” );bre ak;case 0：exit(0);d efault :pri ntf(”错误选择!");b r e

35、a k; 3、第三题源程序 ：# inc l u d e<s t dio、h>int MA 4: ;/*空闲块数组*/in t A 9 : 4=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 ;/*磁盘空间* /i nt mark9 ;/*存放已分配得块 */int No=0; / *已分配得块数* /vo id disp lay 1() int i, j ,t emp,count ,No=0;if(MA 1!=0) i =MA0 ;printf( ” n

36、gro upl:"); for(j=1;j< = i; j +) P ri n tf( "%d”,MAj);mar k + No =MA j;tem p= MA 1 ;coun t = 2;w h i le (A temp 1 ! = 0) p r i n tf (” ngro u p%d:",co u nt);i =A temp0 ;for( j =1;j< =i ;j + +) p rintf( ” %d ” ,A t emp j :);mark+No = A t e mp j;c oun t +;tem p =Ate m p1 ;p ri ntf

37、("ngro u p%d: " ,count);i =At e mp 0 ;f or(j =2;j=i +1;j+)if(Atemp j 0) printf ("%d " ,Atemp j );mark +No=Atempj;e l se i = MA : 0;if(i=1)pr i n t f (" nTh e b l ocks are all assigned"); e lse p r intf( " ngroup 1 :");for(j=2; j < = i; j +) printf("%d

38、",MAj);mark +No =MAv oi d di splay () int i,j;i f( M A : 0 !=0)j;/显示分组情况d i splay1();el se i=MA 1 for(j=0;j<=3; j +) * 分配空闲块/* 若该组不止一个空闲块 */MA j =Ai j; d isplay1();voi d assign() int s ,i;if(M A 0 >1) i=MA0 ; s =MAi;MA 0-;p ri ntf(nn umber of th e bloc k:%d,s );else i f(MA 0=1)/*只剩一个空闲块 /

39、 if(M A 1！=0)/* 还有其它空闲块组 /s=MA1 for(i = 0 ;i= 3;i+)A 0 i = A sin num b er of t he b lock:% d ”,s);el se/*没有其它空闲块组*/retue lsMAprintf(” nThere i sn'tr n;efor (i=0;i<=3;i+ ) :i = A 0ign();an y spac e” ); / * 当前组已分配完assd isplay();vi ;/显示分组情况 */i d ca ll ba ck() int i ,j,tem p; rin t f( ” nin put

40、scan f (” d”，&j);g e t cha r ();for(temp = 1 ;temp<=Nbrea k;i f(tem pNo+1)if(MAelse0 =1 ;pri nt f( ” nThe0 <3)i=MA 0;fo r (i=0;idispl a y();vo id menu() in t choic e;/*回收空闲块 */the N o。 of the b lock you/得到待回收得空闲块; t e m p+)/若该空闲块已在bloc k is i n t he/已有=3;i+)MA1/ * 显示 */w an t t oca l1 bac

41、k:);号f(m aktem P = = j), 退出/disk");/当前组不满 3 块/MAi 1 =j;3 块 /return;char=j;A叮i/*功能选择函数 / judge;p r in tf(” ni n put y ou r choice:(1 a ssig n, 2 sc anf(”d"，&c h o igetcha r();if(ch oice =1)assign ();el s e if(ch o ic e = =2)c all back();c e);caelseprintf( ” nin val id com mand！");p

42、 ri ntf(” ncontinue o r not (y - Y es,n- No t):"); scan f( %c” ,& judge);MA0 ;=MAi :;llback):");els epr int f(” nNowt heg ra ph is:");displa y();printf( ” npres s a n ykeyt oquit );r();int main()int i;ge tchar();if (judge =' y) me nu();f or (i=0; i <=3; i +)MA i= A 0 i;di spl a y();men u(); 七、运行结果MAg e tch a1、题一运行结果护*半宰率邯半半*半半宰*屮半半*自 决适应阜土E头规王仔分配和 回 仅糸抚件林半*衬半林半半*祐导R1:查看磁盘位示国|尢申请分配磁盘空间|扫:申请回收磁盘空间|4:退出程序£ 十”""+&qu