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

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 NODE (char name;名称float start;/ 起始位置float end;/ 大小int flag;/是否分配的标志NODE;NODE OSCOUNT; 数组三，流程图开始四，源代码#include <stdio.h>#include<math.h>#define COUNT 512ty

6、pedef struct NODEchar name;/名称 float start;/ 起始位置 float end;/大小int flag;/是否分配的标志 NODE;NODE OSCOUNT;/ 数组 int count;/被分成的块数统计 int applyfree;float numb;char c;先对数组进行初始化，使没有分配的名称为void init()count=1;OS0.name ="P"OS0.start =0;OS0.end =COUNT;OS0.flag =1;/对数组的插入操作void insert(int m,float st,float e

7、n)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'OSm.flag =1;if(OSm-1.flag )OSm-1.

8、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("名称 标识起址长度状态n");for(i=0;i<count;i+)(if(OSi.flag )printf("P ");elseprintf("%c ",OS );printf("%d %1.0f%1.0f "

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

10、g=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; else(insert(i+1,OSi.start +numb,OSi.end -numb);OSi+1.flag =1;OSi+1.name ='P'OSi.start =OSi.start ;OS =c;OSi.end =numb;OSi.f

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

12、i.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 );) else(n");printf("释放失败，因为正使用的数量小于要求释放的数量。 return 0;)freeflag=1;)i+;)if(freeflag)(printf("释放成功！ n");return 1;)else(printf("释放失败！未找到匹配的进程名称。n");r

13、eturn 0;)void main()(init();show();while(1)(putin();apply()； show();)五，执行结果空闲区说明表的初始状态范标识起亚长度 状态P 00512 未分配请输入申请或者释放的进程名称及资源数量,作业4的申请量以及为作业4分配后的空闲区说明表状态作业3和作业2的归还量以及回收作业3,作业2所占主存后的空闲区说明表情输入申请虱者释放的迸程名称及资源数蔓(10haai觥成功亲识名称起址 0 100 112 Z8Z长度 100 12 150 2SW3费配 已分配 己婿己 未箍己清输入申请或者释放的进程名称及资源数量*150a h P标识01起

14、址 B 100 112长度 100 12 40Si未逛己请输久申请或者释放的进程名祢及资源数量.2舐失败!名称才AQ是名称H度/心0100已分配10012已殳配请输入申请或者释放的进程名称及资源数量.400_.未分配在分页式管理方式下采用位示图来表示主存分配情况，实现主存空间的分配和回收。提示:(1)分页式存储器把主存分成大小相等的若干块，作业的信息也按块的大小分页，作业装入主存时可把作业的信息按页分散存放在主存的空闲块中，为了说明主存中哪些块已经被占用，哪些块是尚未分配的空闲块， 可用一张位示图来指出。 位示图可由若干存储单元来构 成，其中每一位与一个物理块对应，用 0/1表示对应块为空闲/

15、已占用。(2)假设某系统的主存被分成大小相等的64块，则位示图可用 8个字节来构成，另用一单元记录当前空闲块数。如果已有第0, 1 ,4, 5, 6, 9, 11, 13, 24, 31,共10个主存块被占用了，那么位示图情况如下：八位 节、S号 、01234567011001110101010100200000000310000001400000000500000000600000000700000000甲谢或生存区4长度油就卜上长度，=归度-就fiifcr=JKjt + Tk施出分配/孔图4-1最先适应分配模拟算法图4-2 主存回收算法(3)当要装入一个作业时，根据作业对主存的需要量，先查

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

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

18、包含文件号，文件页长，页号，几页号对应的块号int filenum;int yechang;int yenum;int kuainum;struct file flN;/文件结构体数组void put(int 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<4;

19、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",empty);vo

20、id 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)printf("需要装入的页数大于页表

21、中的空闲页数，分配失败n");else wenjianshu+=1;for(i=1;i<=wenjianshu;i+)if(fli.yechang=0)filenum=i;elsefilenum+=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=cishu;flfilenum.kuainum=kua

22、inum;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",gfilenumi+1);)full=0;fo

23、r(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;elsegoto end;aeg:printf("请输入需要回收的文件号大于

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

25、(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",&