操作系统-主存储器空间的分配和回收.docx

实习四主存储器空间的分配和回收一，实习题目本实习模拟在两种存储管理方式下的主存分配和回收。第i题：在可变分区管理方式下采用最先适应算法实现主存分配和实现主存回收。提示:可变分区方式是按作业需要的主存空间大小来分割分区的。当要装入一个作业时，根据作业需要的主存量查看是否有足够的空闲空间，假设有，那么按需要量分割个分区分配给该作业；假设无，那么作业不能装入。随着作业的装入、撤离，主存空间被分成许多个分区，有的分区被作业占用，而有的分区是空闲的。例如：O5k操作系统IOk作业114k作业326k空闲区32k作业2128k空闲区为了说明哪些区是空闲的，可以用来装入新作业，必须要有一张空闲区说明表，格式如下:起址长度状态14K12K未分配32K96K未分配空表目空表目；其中，起址一一指出一个空闲区的主存起始地址。长度一一指出从起始地址开始的一个连续空闲的长度。状态一一有两种状态，一种是“未分配”状态，指出对应的由起址指出的某个长度的区域是空闲区；另一种是“空表目”状态，表示表中对应的登记工程是空白(无效)，可用来登记新的空闲区(例如I,作业撤离后，它所占的区域就成了空闲区，应找一个“空表目”栏登记归还区的起址和长度且修改状态)。由于分区的个数不定，所以空闲区说明表中应有适量的状态为“空表目”的登记栏目，否那么造成表格“溢出”无法登记。上述的这张说明表的登记情况是按提示(1)中的例所装入的三个作业占用的主存区域后填写的。(2)当有一个新作业要求装入主存时，必须查空闲区说明表，从中找出一个足够大的空闲区。有时找到的空闲区可能大于作业需要量，这时应把原来的空闲区变成两局部：一局部分给作业占用；另一局部又成为一个较小的空闲区。为了尽量减少由于分割造成的空闲区，而尽量保存高地址局部有较大的连续空闲区域，以利于大型作业的装入。为此，在空闲区说明表中，把每个空闲区按其地址顺序登记，即每个后继的空闲区其起始地址总是比前者大。为了方便查找还可使表格“紧缩”，总是让“空表目”栏集中在表格的后部。(3)采用最先适应算法(顺序分配算法)分配主存空间。按照作业的需要量，查空闲区说明表，顺序查看登记栏，找到第一个能满足要求的空闲区。当空闲区大于需要量时，一局部用来装入作业，另一局部仍为空闲区登记在空闲区说明表中。由于本实习是模拟主存的分配，所以把主存区分配给作业后并不实际启动装入程序装入作业，而用输出“分配情况”来代替。最先适应分配算法如图4/。(4)当一个作业执行结束撤离时，作业所占的区域应该归还，归还的区域如果与其它空闲区相邻，那么应合成一个较大的空闲区，登记在空闲区说明表中。例如，在提示(1)中列举的情况下，如果作业2撤离，归还所占主存区域时，应与上、下相邻的空闲区一起合成一个大的空闲区登记在空闲区说明表中。归还主存时的回收算法如图42。(5)请按最先适应算法设计主存分配和回收的程序。然后按(1)中假设主存中已装入三个作业，且形成两个空闲区，确定空闲区说明表的初值。现有一个需要主存量为6K的作业4申请装入主存；然后作业3撤离；再作业2撤离。请你为它们进行主存分配和回收，把空闲区说明表的初值以及每次分配或回收后的变化显示出来或打印出来。二，本实验用到的一些数据结构有：typcdefstructNODECharname;名称floatStart;/起始位置floatend;大小intflag;是否分配的标志(NODE;NODEOSCOUNT;数组三，流程图四，源代码#include<stdio.h>#include<math.h>#defineCOUNT512typedefstructNODE(Charname;名称floatStart;起始位置floatend，大小intflag;是否分配的标志NODE;NODEOSCOUNT;数组intcount;被分成的块数统计intapplyfree;floatnumb;charc;先对数组进行初始化，使没有分配的名称为Pvoidinit()(count=l;OS(0.name-P':OSIO.start=0;OS0.end=COUNT;OS0.flag=l;)对数组的插入操作voidinsert(intm,floatst,floaten)(inti;count+;fbr(i=count;i>m+1;i)(OSIiI=OSIi-11;)0Sm.start=st;0S(m.end=en:)移动操作，即对数组的删除操作voidmove(intm)(inti;for(i=m;i<count-l;i+)(OSi=OSi+l;)count;)如果相邻块都没有分配，那么要合并到一起voidrremove(intm,floatst,floaten)(if(!OSm-Il.flag&&!OS|m+l.flag)(0Sm.name=P;OSm.flag=1;)if(OSm-l.flag)(0Sm-lLend=0S(m-l.end+en;move(m);)if(OSm+l.flag)(OSm.end=OSIm.end+0Sm+l.end;0Sm.name-P);OSm.flag=1;move(m+l);)打印输出voidshow()(inti;Printf("名称标识起址长度状态);fbr(i=0;i<count;i+)(if(OSiJ.flag)printf("P");elseprintf("%c",OS(i.name);printf(',%d%LOf%LOf,1,i,OSi.start,OSi).end);if(OSiJ.flag)PrintfC未分配n");elsePrintfC已分配n");从键盘输入数据voidputin()(Printf("请输入申请或者释放的进程名称及资源数量：n');rewind(stdin);scanf("%c",&c);scanf("%d",&applyfree);scanf("%f',<fenumb);intapply()(inti=0;intapplyflag=O;intfreeflag=O;if(applyfree)提出申请资源(while(!applyflag&&i<count)(if(OSi.end>=numb&&OS(i|.flag)(if(OSi.end=numb)(OSi.name=c;OSi.flag=0;)elseinsert(i+l.OSi.start+numb,OSi.end-numb);OSli+l.flag=l;OSi+l.name='P'OSi.start=OSi.start:OSi.name=c;OSi.end=numb;OSi.flag=0;)applyflag=l;)i+；)if(applyflag)(Primfc申请成功!ntt);return1;JelsePrintf（"申请失败！没有足够大的空闲空间。n"）;return0;)else提出释放资源(while(!freeflag&&i<count)(if(OSi.name=c)(if(OSi.end=numb)(rremove(i,OSi.sUrt,OS11.end);)else(if(OSi.end>numb)insert(i+l,OSi.start+numb,OSi.end-numb);OSi+I.name="P'OSi+l.flag=0;OS(i.end=nb;OSi.flag=1;if(OSi-l.flag)(rremove(i,OSi.start,OS(i.end);else（Printf（"释放失败，因为正使用的数量小于要求释放的数量。n"）;return0;freeflag=l;）i+；Jif（freeflag）（PrintfC释放成功!n"）;return1;）else（Printf（"释放失败！未找到匹配的进程名称。n"）;return0;voidmain()(init();show();while(l)putin();apply();show();)五，执行结果空闲区说明表的初始状态作业4的申请量以及为作业4分配后的空闲区说明表状态作业3和作业2的归还量以及回收作业3,作业2所占主存后的空闲区说明表请输入申请或者释放的进程名称及资源数量：d0200释放成功！名称标识起址长度a00100b110012c2112150P3262250省分配已分配已贫配未久配请输入申请或者释放的进程名称及资源数量：C0150舜瑟成功L4-X名称标识起址长度a00100b110012P2112400ft未於配请输入申请或者释放的进程名称及资源数量：2c名度00e101240已止i02三起01011梆识!012磐U12释«-abP己己己酉酉西态父R<刀状已已未请输入申请或者释放的进程名称及资源数量：第二题:在分页式管理方式下采用位示图来表示主存分配情况，实现主存空间的分配和回收。提示:(1)分页式存储器把主存分成大小相等的假设十块，作业的信息也按块的大小分页，作业装入主存时可把作业的信息按页分散存放在主存的空闲块中，为了说明主存中哪些块已经被占用，哪些块是尚未分配的空闲块，可用一张位示图来指出。位示图可由假设干存储单元来构成，其中每一位与一个物理块对应，用0/1表示对应块为空闲/已占用。(2)假设某系统的主存被分成大小相等的64块，那么位示图可用8个字节来构成，另用一单元记录当前空闲块数。如果已有第0,1,4,5,6,9,11,13,24,31,共10个主存块被占用了，那么位示图情况如下:位0淤012345670110011101010101002000000003I0000001400000000500000000600000000700000000图4-1最先适应分配模拟算法(3)当要装入一个作业时，根据作业对主存的需要量，先查当前空闲块数是否能满足作业要求，假设不能满足那么输出分配不成功。假设能满足，那么查位示图，找出为“0”的一些位，置上占用标志“1”，从“当前空闲块数”中减去本次占用块数。按找到的计算出对应的块号，其计算公式为：块号=j8+i其中，j表示找到的是第n个字节，I表示对应的是第n位。根据分配给作业的块号，为作业建立张页表，页表格式:页号块号012(4)当一个作业执行结束，归还主存时，根据该作业的页表可以知道应归还的块号，由块号可计算出在位示图中的对应位置，把对应位的占用标志造成“0”，表示对应的块已成为空闲块。归还的块数参加到当前空闲块数中。由块号计算在位示图中的位置的公式如下：字节号j=块号/8(表示取整)位数i=块号/8(表示取余)(5)设计实现主存分配和回收的程序。假定位示图的初始状态如(2)所述，现有一信息量为5页的作业要装入，运行你所设计的分配程序，为作业分配主存且建立页表(格式如(3)所述然后假定有另一作业执行结束，它占用的块号为第4,5,6和31块，运行你所设计的回收程序，收回作业归还的主存块。要求能显示和打印分配或回收前后的位示图和当前空闲块数，对完成一次分配后还要显示或打印为作业建立的页表。二，源代码#include<stdio.h>#defineN64物理块数#defineM100000最多输入文件数structfile文件结构体，包含文件号，文件页长，页号，几页号对应的块号(intfilenum;intyechang;intyenum;intkuainum;；structfileflN;文件结构体数组voidput(inta88)输出位示图(inti,j;for(i=0;i<8;i+)for(j=0y<8y+)printf("t%d",aij);printf("n'');voidhuishou(inta88,intb)回收规定的页面intc4=4,5,6,311；intij,k,empty;inth4;for(k=0;k<4;k+)(hk=ck;i=ck8;j=ck%8;aij=;printf("n需要回收的页号和块号分别为:n");Printf("页号t块号n")；for(k=0;k<4;k+)printf("%dt%dn,k,hk);)PrintfC回收后的页表位示图为:n")；put(a);empty=0;for(i=0;i<8;i+)(for(j=0;j<8;j+)(if(aij=l)empty+=1;)1empty=64-empty;Printf(”剩余的块的dn*empty);)voidshixian(inta88,intb)实现存储空间的分配与回收(intij,k,x,y,m,empty,full,fileshu,kuainum,hN,gNN;intcishu=O,hang=O,lie=O,filenum=O,wenjianshu=O;i11tpM=-l);intjian=O;empty=b;beg:Printf("请输入需要装入的文件的页数巧；scanf("%d",<fem);printf("n");cishu=O;if(empty<m)Printfe需要装入的页数大于页表中的空闲页数，分配失败n”);else(wenjianshu+=l;for(i=1;i<=wenjianshu;i+)(if(fli.yechang=O)filenum=i;elsefilenum+=1;1hfilenum=m;flfilenum.filenum=filenum;for(i=0;i<m;i+)(flflenum.yenum=i;)for(i=0;i<8;i+)(for(j=OJ<8y+)(if(aij=O)(aij=l;kuainum=i*8+j;cishu+=l;flfilenum.yenum=cishu;flfilenum.kuainum=kuainum;gfilenumcishu=kuainum;1if(cishu>=m)break;if(cishu>=m)break;)flfilenum.yechang=m;Printf("文件号:dt文件页长:dn”,flf11enum.filenum,flfilenum.yechang);PrintfC页号t块号n")；for(i=0;i<m;i+)printf("%dt",flfilcnum.yenum-m+i);printf("%dn",gfilcnumi+1);full=O;for(i=0;i<8;i+)(for(j=0;j<8;j+)if(aijl)full+=l;empty=64-full;Printf("剩余的块数:dn",empty);Printfe分配后的页表位示图为:n")；put(a);)Printf(“继续装入文件请输入1,回收页面请输入2,输入其他键结束:");scanf("%d',<fcy);if(y=l)gotobeg;elseif(y=2)gotoaeg;elsegotoend;aeg:Printf(”请输入需要回收的文件号大于0且不在以下数集中的数t")；for(i=l;i<=jian;i+)if(pjian!=-l)printf("%dt",pjian);Iprintf("n输入的需要回收的页数为:")；scanf("%d,(fefileshu);if(wenjianshu<fileshu)Printf("你输入的文件号不存在!n");if(fileshu<=)Printf("你输入的文件号不存在!n");else(k=gfileshul;filenum=fileshu;for(x=0;x<hfileshu;x+)k=gfileshux+l;i=k8;j=k%8;aij=O;)PrintfC回收页面后的页表位示图为:n")；put(a);empty=0;显示空闲页数for(i=0;i<8;i+)(for(j=0;j<8;j+)if(aijl)empty+=1;)1empty=64-empty;Printf("剩余的块数:dn*empty);flfileshu.yechang=0;jian+=l;pjian=fileshu;IPrintfC继续装入页面请输入1,回收页面请输入2,输入其他键结束:");scanf("%d,<fey);if(y=l)gotobeg;elseif(y=2)gotoaeg;elsegotoend;end:printf("n");huishou(a,empty);)voidmain()intij,b,m,n;intcN=0,1,4,5,611,13,2431);inta88=0);for(m=0;m<10;m+)i=cm8;j=cm%8;aij=l;Printf("初始化的位示图是:n");put(a);b=0;for(i=0;i<8;i+)(for(j=0<8)(if(ai皿=1)b=b+l;11n=64-b;Printf("剩余的块数:%dn,',n);shixian(a,n);三，执行结果初始化的位示图是：11001110010101000000000010000001000000000000000000000000000剩余的块数居4请输入需要装入的文件的页数二.00000