搜索
计算机操作系统实验报告姓名：班级:学号：题目：动态分区分配方式的模拟实习内容简要描述本次实验要完成两部分内容：一是用C语言实现对采用首次适应算法和最佳适应算法的动态分区分配过程ALLOC（）和回收过程FREE（），其中空闲分区由空闲分区链来管理，进行分配时，系统优先使用空闲区底端空间。二是假设初始状态下，可用内存空间为640KB。按照题目要求的作业顺序，以及各个作业分配和回收的内存空间。分别采用首次适应法和最佳适应法，对内存进行分配和回收，要求每次分配和回收后显示空闲内存分区链的情况。实验分析算法介绍本次实验通过用C语言进行编程并调试、运行，形象地表现出动态分区的分配方式，直观地展现了首次适应算法和最佳适应算法对内存的释放和回收方式之间的区别。加深了我们对两种算法优缺点的理解，帮助我们了解一些数据结构和分配算法，进一步加深我们对动态分区存储器管理方式及其实现过程的理解。主要的问题在于，如何解决两种算法对内存的释放和回收空间的表示。动态分区分配：又称为可变分区分配，这种分配方式并不事先先将主存划分成一块块的分区，而是在作业进入主存时，根据作业的大小动态地建立分区。并使分区的大小正好适应作业的需要。因此系统中分区的大小是可变的，分区的数目也是可变的。分区分配算法：（两者的空闲块链接方式不同）①首次适应法：为作业选择分区时总是按地址从高到低搜索，只要找到可以容纳该作业的空白块，就把该空白块分配给该作业。特点：优先利用内存中底地址部分的空闲分区(将所有空闲区,按其地址递增的顺序链接)②最佳适应算法：接到内存申请时，在空闲块表中找到一个不小于请求的最小空块进行分配;为作业选择分区时总是寻找其大小最接近于作业所要求的存储区域。特点：用最小空间满足要求(将所有空闲区,按其大小递增的顺序联接成空闲区链)结果分析（思考题解答；错误原因分析）运行结果分析：1、参考程序方法1中，用两个独立的程序分别实现首次适应算法和最佳适应算法的分配和回收过程。首次适应算法，在进行内存分配时，从空闲分区链首开始顺序查找，能满足其大小要求的空闲分区为止。然后，再按照作业大小，从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍然留在空闲分区链中。最佳适应算法，在进行内存分配时，从空闲分区链首开始顺序查找，直至找到第一个能满足其大小要求的空闲分区为止。如果给空闲分区大于作业的大小，则从该分区中划出一块内存空间分配给请求者，将剩余空闲区仍然留在空闲区分链中。当作业运行完成时，对已使用完的分区进行回收，系统根据回收分区的大小及首地址，在空闲分区链中检查是否有邻接的空闲区，如有相邻空闲区则合并成一个大的空闲区，然后修改有关的分区状态信息。2、参考程序方法2中，只用了一个程序来实现整个操作内容：首先确定内存空间分配表；然后编写主函数实现所需功能；最后分别采用首次和最佳适应算法完成内存空结果分析（思考题解答；错误原因分析）间的分配和回收。思考题解答：1、首次适应算法分配时从表头指针开始查找可利用空间表，将找到的第一个大小不小于“请求”的空闲块的一部分分配给用户。可利用空间表本身既不按节点的初始地址有序，也不按节点的大小有序。用户释放内存，回收时只是将空闲块插入在链表的表头即可。最佳适应算法将可利用空间表中一个大小不小于“请求”且最接近“请求”的空闲块的一部分分配给用户。分配与回收都需要对可利用空间表从头至尾查询一遍。为了避免每次分配都要查询整个链表，通常要求节点从大到小排序，由此只需找到第一个足够大的空闲块即可予以分配。但回收时，必须把回收的空闲块放置在符合大小顺序关系的链表位置。因此，首次适应算法分配和回收的速度更快，用时更少。2、经过一段时间的分配回收后，内存中存在很多很小的空闲块。它们每一个都很小，不足以满足分配要求；但其总和满足分配要求。这些空闲块被称为碎片。造成存储资源的浪费，我们可以通过紧凑技术来解决，即通过在内存移动程序，将所有小的空闲区域合并为大的空闲区域（紧缩技术，紧致技术，浮动技术，搬家技术）。错误原因：方法1：直接运行便可得到正确的结果。方法2：参考程序直接运行会出现11errors，需改正才能正常运行，其涉及错误有：①用getch();缺少头函数：#includeconio.h；②在程序一开始处缺少函数定义intwum(longreturn_pointer,longsize,charname[]);；③定义类型出错，应将long(*test_alloc)();改为long(*test_alloc)(longalloc_size,charname[]);。主要代码结构（附注释）/*首次适应算法*/#includestdlib.h#includestdio.h/*定义空闲分区链结构*/structNode{intnum;/*sequencenumberofwork序列号的工作*/intspace;/*spacetakenup占用空间*/structNode*next;//指向下一个节点的指针域，后向指针};typedefstructNodeNode;Node*head=NULL;//头指针，赋空Node*newNode(){return(Node*)malloc(sizeof(Node));}voidinit(){head=newNode();主要代码结构（附注释）head-next=NULL;//判断头指针的下个节点是否为空}/*内存分配*/voidALLOC(intnum,intspace){Node*p=newNode();//为p分配一个Node类型所占的空间，p指向所分配的内存的首地址Node*q=head-next;Node*s=newNode();Node*n=newNode();if(head-next==NULL)//如果指针指向的下个位置为空则分配{p-space=640;p-num=0;p-next=NULL;//插入尾最后一个结点head-next=p;if(p-space=space){s=newNode();s-space=space;//赋值数据s-num=num;p-space-=space;s-next=p;//把p链接到最后一个结点的nexthead-next=s;return;}printf(OutofMemory!\n);return;}if(q-num==0&&q-space=space){s=newNode();s-space=space;s-num=num;q-space-=space;s-next=q;//把q链接到最后一个结点的nexthead-next=s;return;}p=q-next;while(p!=NULL)主要代码结构（附注释）{if(p-num==0){if(p-space=space){n=newNode();n-space=space;n-num=num;p-space-=space;n-next=p;//把p链接到最后一个结点的nextq-next=n;//把n链接到最后一个结点的nextreturn;}}p=p-next;//下移q=q-next;//下移}printf(OutofMemory!\n);}/*内存回收*/voidFREE(intnum){Node*q=head;inti=1;Node*p=head;Node*t=newNode();while(q-num!=num){q=q-next;i++;}q-num=0;/*表示此段空间已经回收*//*查找有无连续空闲存储空间,如果有则回收*/while(p-next!=NULL){if(p-num==0&&p-next-num==0){t=p-next;p-next=t-next;p-space+=t-space;free(t);}主要代码结构（附注释）p=p-next;}}/*查看分配*/voidshow(){intaccount_space=0;Node*p=newNode();printf(Distributionofmemory:\n);for(p=head-next;p!=NULL;p=p-next){if(p-num==0)printf(free:%d\n,p-space);elseprintf(work%d:%d\n,p-num,p-space);account_space+=p-space;}printf(--------------------------------);}/*主函数*/intmain(){init();/*初始化,建立一个头指针指向内存区*/ALLOC(1,130);//作业1申请130KBshow();getchar();/*控制显示,运行时用户每从键盘上输入一次回车,内存分配变化一次*/ALLOC(2,60);show();getchar();ALLOC(3,100);show();getchar();FREE(2);//释放空间：FREE（p）show();getchar();ALLOC(4,200);show();getchar();FREE(3);show();getchar();主要代码结构（附注释）FREE(1);show();getchar();ALLOC(5,140);show();getchar();ALLOC(6,60);show();getchar();ALLOC(7,50);show();getchar();FREE(6);show();printf(\nTheend!\n);getchar();return0;}/*最佳适应算法*/#includestdlib.h#includestdio.h#includemalloc.h/*定义空闲分区链结构*/structNode{intnum;/*sequencenumberofwork序列号的工作*/intspace;/*spacetakenup占用空间*/structNode*next;//后向指针};typedefstructNodeNode;Node*head=NULL;//头指针，赋空Node*array[10];/*数组,用来存放num=0点的指针*/Node*before_array[10];/*存放array[i]对应的前一指针*/Node*newNode(){return(Node*)malloc(sizeof(Node));//返回带头结点的链表}主要代码结构（附注释）voidinit(){head=newNode();head-next=NULL;}/*内存分配*/voidALLOC(intnum,intspace){inti=0,j;Node*temp=newNode();Node*p=newNode();Node*q=head-next;Node*s=newNode();Node*r=newNode();if(head-next==NULL){p-space=640;p-num=0;p-next=NULL;head-next=p;if(p-space=space){s-space=space;s-num=num;p-space-=space;s-next=p;head-next=s;return;}printf(OutofMemory!\n);return;}p=head;q=p-next;while(q!=NULL){if(q-num==0&&q-space=space){array[i]=q;before_array[i]=p;i++;}主要代码结构（附注释）q=q-next;p=p-next;}if(i1){for(j=0;ji-1;j++){if(array[j]-space=array[j+1]-space)temp=before_array[j];elsetemp=before_array[j+1];}