主存储器空间的分配和回收一、实验题目：（1）在可变分区管理方式下采用最先适应算法实现主存分配和实现主存回收（2）在分页式管理方式下采用位示图来表示主存分配情况，实现主存空间的分配和回收二、实验目的：通过本实习帮助理解在不同的存储管理方式下应怎样实现主存空间的分配和回收。三、实验原理：第一题： 在可变分区管理方式下采用最先适应算法实现主存分配和实现主存回收(1) 可变分区方式是按作业需要的主存空间大小来分割分区的。当要装入一个作业时，根据作业需要的主存量查看是否有足够的空闲空间，若有，则按需要量分割一个分区分配给该作业；若无，则作业不能装入。随着作业的装入、撤离，主存空间被分成许多个分区，有的分区被作业占用，而有的分区是空闲的。例如：为了说明哪些区是空闲的，可以用来装入新作业，必须要有一张空闲区说明表，格式如下：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 16 页（2）当有一个新作业要求装入主存时，必须查空闲区说明表，从中找出一个足够大的空闲区。有时找到的空闲区可能大于作业需要量，这时应把原来的空闲区变成两部分：一部分分给作业占用；另一部分又成为一个较小的空闲区。为了尽量减少由于分割造成的空闲区，而尽量保存高地址部分有较大的连续空闲区域，以利于大型作业的装入。为此，在空闲区说明表中，把每个空闲区按其地址顺序登记，即每个后继的空闲区其起始地址总是比前者大。为了方便查找还可使表格“紧缩”，总是让“空表目”栏集中在表格的后部。（3）采用最先适应算法（顺序分配算法）分配主存空间。按照作业的需要量，查空闲区说明表，顺序查看登记栏，找到第一个能满足要求的空闲区。当空闲区大于需要量时，一部分用来装入作业，另一部分仍为空闲区登记在空闲区说明表中。最先适应分配算法如图：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 16 页（4）当一个作业执行结束撤离时，作业所占的区域应该归还，归还的区域如果与其它空闲区相邻，则应合成一个较大的空闲区，登记在空闲区说明表中。例如，在提示(1)中列举的情况下，如果作业2 撤离，归还所占主存区域时，应与上、下相邻的空闲区一起合成一个大的空闲区登记在空闲区说明表中。归还主存时的回收算法如图：（5）请按最先适应算法设计主存分配和回收的程序。然后按（1）中假设主存中已装入三个作业，且形成两个空闲区，确定空闲区说明表的初值。现有一个需要主存量为6K 的作业 4 申请装入主存；然后作业3 撤离； 再作业 2 撤离。为它们进行主存分配和回收，把空闲区说明表的初值以及每次分配或回收后的变化显示出来或打印出来：第二题： 在分页式管理方式下采用位示图来表示主存分配情况，实现主存空间的分配和回收。(1) 分页式存储器把主存分成大小相等的若干块，作业的信息也按块的大小分页，作业装入主存时可把作业的信息按页分散存放在主存的空闲块中，为了说明主存中哪些块已经被占用， 哪些块是尚未分配的空闲块，可用一张位示图来指出。位示图可由若干存储单元来构成，其中每一位与一个物理块对应，用0/1 表示对应块为空闲/已占用。(2) 假设某系统的主存被分成大小相等的64 块，则位示图可用8个字节来构成，另用一单元记录当前空闲块数。如果已有第0，1，4，5，6，9，11，13，24，31，共 10 个主存块被占用了，那么位示图情况如下图：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 16 页(3) 当要装入一个作业时，根据作业对主存的需要量，先查当前空闲块数是否能满足作业要求，若不能满足则输出分配不成功。若能满足，则查位示图，找出为“0” 的一些位，置上占用标志“1” ，从“当前空闲块数”中减去本次占用块数。按找到的计算出对应的块号，其计算公式为：块号= j 8+I 其中， j 表示找到的是第n个字节， i 表示对应的是第n 位。根据分配给作业的块号，为作业建立一张页表，页表格式：(4) 当一个作业执行结束，归还主存时，根据该作业的页表可以知道应归还的块号，由块号可计算出在位示图中的对应位置，把对应位的占用标志清成“0” ，表示对应的块已成为空闲块。 归还的块数加入到当前空闲块数中。由块号计算在位示图中的位置的公式如下：字节号j=块号 /8 （ 表示取整）位数i=块号 /8 （ 表示取余）(5)设计实现主存分配和回收的程序。假定位示图的初始状态如（2）所述，现有一信息量为 5 页的作业要装入，运行所设计的分配程序，为作业分配主存且建立页表（格式如（ 3）所述）。然后假定有另一作业执行结束，它占用的块号为第4，5，6 和 31 块，运行所设计的回收程序，收回作业归还的主存块。要求能显示和打印分配或回收前后的位示图和当前空闲块数，对完成一次分配后还要显示或打印为作业建立的页表。四、数据结构：数组、链表精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 16 页五、程序代码：第一题：package可变分区管理 ; class Node1 / 用Node来模拟内存的当前状态intstart; intsize ; booleanstate ; intjobNo ; public Node1() public Node1( int start,int size,boolean state,int jobNo) this. start = start; this. size = size; this. state = state; this. jobNo = jobNo; publicvoid print()/ 打印Node类if ( this != null) System.out .println( +this. start+t+this . size +t+this. state +t+this . jobNo ); /Link.javaclass Link / 用Link 类来模拟连接各个内存，并添加作业publicvoid addJob(int size,int jobNo,Node1 a) for ( int i=0;ia.length;i+) if (ai!=null ) / 当前内存有内容时if (sizeai.size &ai.state=false) / 判断是否符合条件ai.size =ai.size -size; / 当前内存分配大小给作业if (ai+1=null) / 当下一块内存还没有使用时 ai+1=newNode1(size+ai.start,size,true ,jobNo);/ 使用该内存 else / 当下一块内存已被使用，那么继续寻找一块还没被使用的内存精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 16 页for ( int j=i+1;ja.length-1;j+) if (aj=null) aj=newNode1(size+aj-1.start,size,true ,jobNo); break ; / 当找到未被使用的内存及填入内容后跳出循环 ai.print();/ 打印输出当前 Link 中各个内存块的使用情况 publicvoiddelete(Node1 a,int jobNo)/ 删除某一个进程，当该进程被删除后，进程所在内存的状态变为falsefor ( int i=0;ia.length;i+) if (ai!=null ) if (ai.jobNo =jobNo) /ai.size=0;ai.state=false; ai.jobNo =0; if (ai!=null) ai.print(); publicvoid back(Node1 a) / 进行状态为 false的内存的回收删除内存状态为 false 的内存节点。并将该节点与起始点结合for ( int i=1;ia.length;i+) if (ai!=null ) if (ai.state=false) a0.size =a0.size +ai.size ; ai=null; for ( int j=0;ja.length;j+) if (aj!=null ) aj.print(); 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 16 页 /OSJob.javapublicclass Job publicstaticvoid main(String args) Node1 jobArray=new Node170; jobArray0=new Node1(0,25,false,0); Link l = new Link(); System. out .println(-最初的内存-); System.out .println( 起始位置 +t+ 大小 +t+ 状态 +t+ 工作号 ); jobArray0.print(); System. out .println(-增加第 1个作业后-); System.out .println( 起始位置 +t+ 大小 +t+ 状态 +t+ 工作号 ); l.addJob(4,1,jobArray); System. out .println(-增加第二个作业后-); System.out .println( 起始位置 +t+ 大小 +t+ 状态 +t+ 工作号 ); l.addJob(10,2,jobArray); System. out .println(-增加第三个作业后-); System.out .println( 起始位置 +t+ 大小 +t+ 状态 +t+ 工作号 ); l.addJob(10,3,jobArray); System. out .println(-删除作业 2后-); System.out .println( 起始位置 +t+ 大小 +t+ 状态 +t+ 工作号 ); l.delete(jobArray,2); System. out .println(-添加作业 4后-); System.out .println( 起始位置 +t+ 大小 +t+ 状态 +t+ 工作号 ); l.addJob(5,4,jobArray); 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 16 页第二题：#include #include #include #include #include #include int bitmap88= /初始化位图1,1,0,0,1,1,1,0, 0,1,0,1,0,1,0,0, 0,0,0,0,0,0,0,0, 1,0,0,0,0,0,0,1, 0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0 ; int freecount=54; /初始时空闲页块数typedef struct yebiao /页表结构体 int yehao; / 页号int kuaihao; /块号struct yebiao *next; /指向下一个页表项的指针YEBIAO; typedef struct progress /进程结构体 char name30; /进程名int size; /进程所需内存大小struct progress *next; /指向下一个页表项的指针struct yebiao *yb; /为其分配内存建立的页表首地址PROGRESS; /* 分配内存函数，为进程分配所需要的内存并建立页表*/ YEBIAO *allocation(int size) 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 16 页 YEBIAO *head; YEBIAO *tem; int n=0; tem=(YEBIAO *)malloc(sizeof(YEBIAO); head=tem; for(int i=0;i+) /遍历位图找到空闲的页块 if(bitmapi/8i%8=1) continue; /如果页会已被占用直接查下一个页块if(bitmapi/8i%8=0) bitmapi/8i%8=1; /将空闲的位图标识置为一tem-yehao=n; /建立一个页表项的页号tem-kuaihao=i; /对应的块号tem-next=NULL; n+; if(n=size) break; /如果已经分配了需要的页块直接退出查找else tem-next=(YEBIAO *)malloc(sizeof(YEBIAO); tem=tem-next; return head; /* 回收内存 */ void recovery(YEBIAO *a) YEBIAO *b; while(a-next!=NULL) bitmapa-kuaihao/8a-kuaihao%8=0; /将页块对应的标识位图对应标志置0 b=a-next; /指向下一个页表项free(a); /释放页表项精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 16 页占用的空间a=b; bitmapa-kuaihao/8a-kuaihao%8=0; free(a); void outputyebiao(YEBIAO *a) /输出页表的内容 cout-endl; do coutyehaosetw(4)kuaihaosetw(4)next; while(a!=NULL); /遍历页表链表逐行输出页表项cout-endl; void outputbit() /输出主存分配位视图 cout 主存分配位视图如下 :endl; cout-endl; for(int i=0;i8;i+) for(int j=0;j8;j+) coutbitmapijsetw(4); /双重循环输出标识位图的内容 coutendl; cout-next=NULL; else /定位到链表的队尾将要插入的进程插入到队尾 tem=head; while(tem-next!=NULL) tem=tem-next; tem-next=b; return head; PROGRESS *getprosess(PROGRESS *head) /输入进程为进程分配空间 PROGRESS *a; char na30; int size; coutna; coutsize; /上面是输入进程的名称和所用内存空间大小if(sizefreecount) /如果进程 cout 进程所需内存的大小大于空闲的内存，无法添加进程。name,na); a-size=size; /初始化进程的基本信息freecount-=size; /将可用的页块数减去进程要用的页块数a-yb=allocation(size); /为进程创建页表精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 11 页，共 16 页cout 进程创建成功！ next=NULL; return insert(head,a); /将进程插入进程链表中 void outputprosess(PROGRESS *head) /输出进程信息 if(head=NULL) /判断进程队列是否为空 cout 当前没有进程 !endl; return; do /进程队列不为空， 先输出进程的名称和所占内存的大小。再输出进程的页表队列 cout 进程名为 :name 进程所占内存的大小为:size页endl; cout 进程的页表如下 :yb); head=head-next; while(head!=NULL); PROGRESS * delecteprosess(PROGRESS *head) /删除进程 char na30; PROGRESS *a,*b; coutna; if(head=NULL) /如果进程为空，退出函数 cout 进程链表为空，没有进程可删除。name,na)=0) /如果找到要删除的进程 recovery(head-yb); /先删除进精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 12 页，共 16 页程的页表并释放所占的页freecount+=head-size; /将可用的内存数加上进程所占的内孙a=head-next; free(head); /释放进程信息所占得内存空间cout 进程na 删除成功 !next; b=head; while(a!=NULL) /遍历链表找到要删除的进程 if(strcmp(a-name,na)=0) recovery(a-yb); freecount+=a-size; b-next=a-next; free(a); cout 进程na 删除成功 !next; cout 您输入的进程名不对，删除进程失败。endl; return head; void outbiaoti() coutttt主存空间的分配与回收模拟endl; cout您可进行如下操作 : 1.查看内存分配情况 ; 2.查看进程 ; 3. 添加进程 4.删除进程 endl; couttt 可用内存为 freecountn; switch(n) case 1: outputbit();outbiaoti();break; case 2: system(cls);outputprosess(head);outbiaoti();break; case 3: system(cls);head=getprosess(head); outbiaoti();break; case 4: system(cls);head=delecteprosess(head); outbiaoti();break; default: break; 六、运行结果：第一题：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 14 页，共 16 页第二题：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 15 页，共 16 页七、实验心得：这次的实验相对来说较难，之前对内存那块知识也不是很清楚，但通过实验， 也参考了很多资料解释，但是还是对内存分配与回收有了更深入更清楚的了解，以后的程序编写不论是实验还是项目开发，无论大小， 都应该把程序的整体框架构建好，提高重用性，再进行一步步实现。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 16 页，共 16 页