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

1、实习四主存储器空间的分配和回收一，实习题目本实习模拟在两种存储管理方式下的主存分配和回收。第一题：在可变分区管理方式下采用最先适应算法实现主存分配和实现主存回收。提示:可变分区方式是按作业需要的主存空间大小来分割分区的。当要装入一个作业时，根据作业需要的主存量查看是否有足够的空闲空间，若有，则按需要量分割一个分区分配给该作业；若无，则作业不能装入。随着作业的装入、撤离，主存空间被分成许多个分区，有的分 区被作业占用，而有的分区是空闲的。例如：为了下：说明哪些区是空闲的,可以用来装入新作业，必须要有一张空闲区说明表，格式如第一栏第二栏起址长度状态14 K12 K未分配32 K96 K未分配空表目

2、空表目其中,起址指出一个空闲区的主存起始地址。长度一一指出从起始地址开始的一个连续空闲的长度。状态一一有两种状态，一种是“未分配”状态，指出对应的由起址指出的某个长度的区域是空闲区；另一种是“空表目”状态，表示表中对应的登记项目是空白（无效），可用来登记新的空闲区（例如，作业撤离后，它所占的区域就成了空闲区，应找一个“空表目” 栏登记归还区的起址和长度且修改状态）。由于分区的个数不定，所以空闲区说明表中应有适量的状态为“空表目”的登记栏目，否则造成表格“溢出”无法登记。上述的这张说明表的登记情况是按提示（1）中的例所装入的三个作业占用的主存区域后填写的。(2) 当有一个新作业要求装入主存时，必

3、须查空闲区说明表，从中找出一个足够大的空 闲区。 有时找到的空闲区可能大于作业需要量， 这时应把原来的空闲区变成两部分： 一部分 分给作业占用；另一部分又成为一个较小的空闲区。为了尽量减少由于分割造成的空闲区， 而尽量保存高地址部分有较大的连续空闲区域， 以利于大型作业的装入。 为此， 在空闲区说 明表中，把每个空闲区按其地址顺序登记，即每个后继的空闲区其起始地址总是比前者大。 为了方便查找还可使表格“紧缩” ，总是让“空表目”栏集中在表格的后部。(3) 采用最先适应算法(顺序分配算法)分配主存空间。按照作业的需要量， 查空闲区说明表， 顺序查看登记栏， 找到第一个能满足要求的空闲 区。当空闲

4、区大于需要量时， 一部分用来装入作业， 另一部分仍为空闲区登记在空闲区说明 表中。由于本实习是模拟主存的分配， 所以把主存区分配给作业后并不实际启动装入程序装入 作业，而用输出“分配情况”来代替。最先适应分配算法如图4-1。(4) 当一个作业执行结束撤离时，作业所占的区域应该归还，归还的区域如果与其它空 闲区相邻，则应合成一个较大的空闲区，登记在空闲区说明表中。例如，在提示(1)中列举的情况下，如果作业 2 撤离， 归还所占主存区域时，应与上、下相邻的空闲区一起合成一 个大的空闲区登记在空闲区说明表中。归还主存时的回收算法如图4-2。(5) 请按最先适应算法设计主存分配和回收的程序。然后按(1

5、)中假设主存中已装入三个作业，且形成两个空闲区，确定空闲区说明表的初值。现有一个需要主存量为 6K 的作 业 4 申请装入主存； 然后作业 3 撤离；再作业 2 撤离。请你为它们进行主存分配和回收，把 空闲区说明表的初值以及每次分配或回收后的变化显示出来或打印出来。 二，本实验用到的一些数据结构有： typedef struct NODEchar n ame;/名称float start;/ 起始位置float end;/ 大小int flag;/ 是否分配的标志NODE;NODE OSCOUNT;/ 数组三，流程图是四，源代码#include vstdio.h#includevmath.h&

6、gt;#define COUNT 512 typ edef struct NODEchar name;/名称 float start;/ 起始位置 float end;/ 大小int flag;/是否分配的标志NODE;NODE OSCOUNT;/ 数组 int count;/被分成的块数统计 int apply free;float numb;char c;/先对数组进行初始化，使没有分配的名称为Pvoid init()count=1;OS0.name ='P'OS0.start =0;OS0.end =COUNT;OS0.flag =1; /对数组的插入操作void ins

7、ert(int m,float st,float en) int i;count+; for(i=count;i>m+1;i-) OSi=OSi-1;OSm.start =st; OSm.end =en;/移动操作，即对数组的删除操作 void move(int m)int i; for(i=m;i<count-1;i+) OSi=OSi+1;count-;/如果相邻块都没有分配，则要合并到一起 void rremove(int m,float st,float en) if(!OSm-1.flag &&!OSm+1.flag ) OS ='P&

8、#39;OSm.flag =1;if(OSm-1.flag )OSm-1.end =OSm-1.end +en; move(m); if(OSm+1.flag )OSm.end =OSm.end +OSm+1.end ;OS ='P'OSm.flag =1;move(m+1); /打印输出 void show() int i;printf(" 名称 标识 for(i=0;i<count;i+)起址 长度 状态 n");if(OSi.flag ) printf("P else printf("%c");"

9、;,OS );printf("%d %1.0f %1.0f ",i,OSi.start ,OSi.end ); if(OSi.flag )printf(" 未分配 n");else printf(" 已分配 n");/从键盘输入数据void putin()printf(" 请输入申请或者释放的进程名称及资源数量： rewind(stdin);scanf("%c",&c); scanf("%d",&applyfree); scanf("%f"

10、;,&numb);n");int apply()int i=0;int applyflag=0;int freeflag=0;if(applyfree)/ 提出申请资源 while(!applyflag&&i<count)if(OSi.end >=numb&&OSi.flag ) if(OSi.end =numb) OS =c;OSi.flag =0;elseinsert(i+1,OSi.start +numb,OSi.end -numb);OSi+1.flag =1;OSi+1.name ='P'OSi

11、.start =OSi.start ;OS =c;OSi.end =numb;OSi.flag =0; applyflag=1; i+;if(applyflag)printf(" 申请成功！ n"); return 1; elseprintf（" 申请失败！没有足够大的空闲空间。 n"）; return 0;else/提出释放资源while(!freeflag&&i<count)if(OS =c)if(OSi.end =numb)rremove(i,OSi.start ,OSi.end );elseif(OS

12、i.end >numb)insert(i+1,OSi.start +numb,OSi.end -numb);OSi+1.name ='P'OSi+1.flag =0;OSi.end =numb;OSi.flag =1;if(OSi-1.flag ) rremove(i,OSi.start ,OSi.end ); elsen");printf（" 释放失败，因为正使用的数量小于要求释放的数量。 return 0;freeflag=1;i+;if(freeflag)printf(" 释放成功！ n"); return 1; elsepr

13、intf（" 释放失败！未找到匹配的进程名称。 n"）; return 0;void main()init(); show(); while(1) putin(); appi y(); show();执行结果五，空闲区说明表的初始状态严輕识晋址轿鷄配 请输入申请或者释放的进程名称及资源数量.作业4的申请量以及为作业 4分配后的空闲区说明表状态起址0100长度412标识a12起址0 133112长庸106124W状态 b4配起址0100112262长度1061215B256苜弁配 己分配 未分配成功！ 标识B1234、 lH I* 户 + K 亠片hl、卄 Jg 缶卓起址10

14、0112a&a4GS长度1061215020650迖态 包配 已分配 已4配 a4配 未召配作业3和作业2的归还量以及回收作业3,作业2所占主存后的空闲区说明表 I 、+请输入申请或者釋放的进程名称及资洱数量;dQ二 00释放成功丄-标识01232名称abcP起址0 100 11Z 22衣度10012150250标识01Z起址B100 112长度10012400貢1;未分配蜃配未外配第二题：在分页式管理方式下采用位示图来表示主存分配情况，实现主存空间的分配和回收。提示:(1) 分页式存储器把主存分成大小相等的若干块，作业的信息也按块的大小分页，作业 装入主存时可把作业的信息按页分散存放

15、在主存的空闲块中， 占用，哪些块是尚未分配的空闲块， 成，其中每一位与一个物理块对应，用为了说明主存中哪些块已经被 位示图可由若干存储单元来构 /已占用。(2) 假设某系统的主存被分成大小相等的 一单元记录当前空闲块数。如果已有第 块被占用了，那么位示图情况如下：字号位 数0123456可用一张位示图来指出。0/1表示对应块为空闲则位示图可用8个字节来构成，另用6, 9，11，13，24，31,共 10 个主存64块,4, 5,0123456711001110010101000000000010000001000000000000000000000000000000000,1,7申请尬主五:I

16、I Q I f h=J + t Ift|f>xkBftT )-SE"7曇>di作亚不1或只II犠出分配低度*怏nt-寸I fijti-wt+iL!图4-1最先适应分配模拟算法W无上*S窒充S 空«'空冃'矿 Siettutr-s ifcarL 状恭，="未野le”T贏十T两闊&杞酊区上砂空谓联空m区盪朗«(O)祀下鼻空闲K住hi懸1J" Jn*. *1也炭*h上4P空AIR®记 社中fcfflKIL1图4-2主存回收算法fcT囲区聲无（3）当要装入一个作业时，根据作业对主存的需要量，先查当前空闲块数

17、是否能满足作 业要求，若不能满足则输出分配不成功。若能满足，则查位示图，找出为“0”的一些位,置上占用标志“ 1 ”，从“当前空闲块数”中减去本次占用块数。按找到的计算出对应的块号，其计算公式为：块号=j 8+i其中，j表示找到的是第n个字节，I表示对应的是第n位。根据分配给作业的块号，为作业建立一张页表，页表格式：页号块号012（4）当一个作业执行结束，归还主存时，根据该作业的页表可以知道应归还的块号，由块号可计算出在位示图中的对应位置，把对应位的占用标志清成“0”，表示对应的块已成为空闲块。归还的块数加入到当前空闲块数中。由块号计算在位示图中的位置的公式如下：字节号j=块号/8（表示取整）

18、位数 i=块号/8（ 表示取余）（5）设计实现主存分配和回收的程序。假定位示图的初始状态如（2）所述，现有一信（格式如4，5，6和31块，运行你息量为5页的作业要装入，运行你所设计的分配程序，为作业分配主存且建立页表（3）所述）。然后假定有另一作业执行结束，它占用的块号为第 所设计的回收程序，收回作业归还的主存块。对完成一次分配后还要显要求能显示和打印分配或回收前后的位示图和当前空闲块数，示或打印为作业建立的页表。二，源代码#in clude<stdio.h>#defi ne N 64/物理块数#defi ne M 100000/最多输入文件数struct file/文件结构体，包

19、含文件号，文件页长，页号，几页号对应的块号int file num;int yecha ng;int yenum;int kua inum;/输出位示图struct file flN;/文件结构体数组 void put(i nt a88)int i,j;for(i=0;i<8;i+)for(j=0;j<8;j+)printf("t%d",aij);printf("n");void huishou(int a88,int b)/回收规定的页面int c4=4,5,6,31;int i,j,k,empty;int h4; for(k=0;k<

20、;4;k+) hk=ck; i=ck/8; j=ck%8; aij=0;printf("n 需要回收的页号和块号分别为 :n"); printf(” 页号 t 块号 n”)； for(k=0;k<4;k+)printf("%dt%dn",k,hk)；printf(" 回收后的页表位示图为 :n")； put(a)；empty=0； for(i=0；i<8；i+) for(j=0；j<8；j+) if(aij=1) empty+=1； empty=64-empty;printf(" 剩余的块数 :%dn&qu

21、ot;,empty);void shixian(int a88,int b)/实现存储空间的分配与回收int i,j,k,x,y,m,empty,full,fileshu,kuainum,hN,gNN；int cishu=0,hang=0,lie=0,filenum=0,wenjianshu=0；int pM=-1;int jian=0; empty=b;beg:printf(" 请输入需要装入的文件的页数 :"); scanf("%d",&m);printf("n");cishu=0; if(empty<m)n&quo

22、t;);printf(" 需要装入的页数大于页表中的空闲页数，分配失败 elsewenjianshu+=1;for(i=1;i<=wenjianshu;i+) if(fli.yechang=0) filenum=i;else filenum+=1;hfilenum=m; flfilenum.filenum=filenum; for(i=0;i<m;i+)flfilenum.yenum=i;for(i=0;i<8;i+)for(j=0;j<8;j+)if(aij=0)aij=1;kuainum=i*8+j;cishu+=1;flfilenum.yenum=cis

23、hu;flfilenum.kuainum=kuainum; gfilenumcishu=kuainum;if(cishu>=m)break; if(cishu>=m) break; flfilenum.yechang=m; printf(" 文件号 :%dt 文件页长 :%dn",flfilenum.filenum, flfilenum.yechang);printf("页号 t 块号 n”)；for(i=0;i<m;i+)printf("%dt",flfilenum.yenum-m+i)； printf("%dn&

24、quot;,gfilenumi+1)；full=0；for(i=0；i<8；i+) for(j=0；j<8；j+)if(aij=1)full+=1； empty=64-full；printf(" 剩余的块数 :%dn",empty)；printf(" 分配后的页表位示图为 :n")； put(a)；printf(" 继续装入文件请输入1，回收页面请输入 2，输入其他键结束 :")；scanf("%d",&y)；if(y=1)goto beg；else if(y=2)goto aeg；elsego

25、to end；aeg:");0 且不在下列数集中的数 -t");printf(" 请输入需要回收的文件号大于 for(i=1;i<=jian;i+)if(pjian!=-1)printf("%dt",pjian);printf("n 输入的需要回收的页数为 scanf("%d",&fileshu);if(wenjianshu<fileshu)if(fileshu<=0)printf(" 你输入的文件号不存在 !n"); elsek=gfileshu1; filenum=

26、fileshu; for(x=0;x<hfileshu;x+) k=gfileshux+1;i=k/8;j=k%8;aij=0;printf(" 回收页面后的页表位示图为 :n");put(a);empty=0;/显示空闲页数for(i=0;i<8;i+)for(j=0;j<8;j+)if(aij=1)empty+=1; empty=64-empty;printf(" 剩余的块数 :%dn",empty);flfileshu.yechang=0;jian+=1;pjian=fileshu;printf(" 继续装入页面请输入 1，回收页面请输入 2，输入其他键结束 :"); scanf("%d",&y);if(y=1)goto beg;else if(y=2)goto aeg;elsegoto end;end:printf("n"); huishou(a,empty);void main()int i,j,b,m,n;int cN=0,1,4,5,6,9,11,13,24,31;int a88=0;for(m=0;m<10;m+)i=cm/8;j=cm%8;a