计算机操作系统内存分配实验报告

1、、实验目的熟悉主存的分配与回收。理解在不同的存储管理方式下，如何实现主存空间的分配与回收。掌握动态分区分配方式中的数据结构和分配算法及动态分区存储管理方式及其实现过程。二、实验内容和要求主存的分配和回收的实现是与主存储器的管理方式有关的。所谓分配，就是解决多道作业或多进程如何共享主存空间的问题。所谓回收，就是当作业运行完成时将作业或进程所占的主存空间归还给系统。可变分区管理是指在处理作业过程中建立分区，使分区大小正好适合作业的需求，并且分区个数是可以调整的。当要装入一个作业时，根据作业需要的主存量查看是否有足够的空闲空间，若有，则按需要量分割一个分区分配给该作业；若无，则作业不能装入，作业等待

2、。随着作业的装入、完成，主存空间被分成许多大大小小的分区，有的分区被作业占用，而有的分区是空闲的。实验要求使用可变分区存储管理方式，分区分配中所用的数据结构采用空闲分区表和空闲分区链来进行，分区分配中所用的算法采用首次适应算法、最佳适应算法、最差适应算法三种算法来实现主存的分配与回收。同时，要求设计一个实用友好的用户界面，并显示分配与回收的过程。同时要求设计一个实用友好的用户界面, 并显示分配与回收的过程。三、实验主要仪器设备和材料实验环境硬件环境：PC或兼容机软件环境：VC+ 6.0四、实验原理及设计分析某系统采用可变分区存储管理，在系统运行当然开始，假设初始状态下，可用的内存空间为640K

3、B， 存储器区被分为操作系统分区（ 40KB） 和可给用户的空间区（600KB） 。（作业 1 申请130KB、 作业 2 申请60KB、作业 3 申请 100KB 、 作业 2 释放 60KB 、作业 4 申请 200KB、 作业 3 释放100KB、 作业 1 释放 130KB 、 作业 5 申请 140KB 、作业 6 申请 60KB 、作业 7 申请50KB）当作业 1 进入内存后，分给作业1（ 130KB） ，随着作业1、 2、 3 的进入，分别分配60KR 100KB经过一段时间的运行后，作业 2运行完毕，释放所占内存。止匕 时，作业4进入系统，要求分配200KB内存。作业3、1运

4、行完毕，释放所占内存。 此时又有作业 5申请140KB,作业6申请60KB,作业7申请50KR为它们进行主 存分配和回收。1、采用可变分区存储管理，使用空闲分区链实现主存分配和回收。空闲分区链：使用链指针把所有的空闲分区链成一条链，为了实现对空闲分区的分配和链接，在每个分区的起始部分设置状态位、分区的大小和链接各个分区的前向指针，由状态位指示该分区是否分配出去了；同时，在分区尾部还设置有一后向指针，用来链接后面的分区；分区中间部分是用来存放作业的空闲内存空间，当该分区分配出去后，状态位就由“0”置为“1 ”。设置一个内存空闲分区链，内存空间分区通过空闲分区链来管理，在进行内存分配时，系统优先使

5、用空闲低端的空间。设计一个空闲分区说明链，设计一个某时刻主存空间占用情况表，作为主存当前使用基础。初始化空间区和已分配区说明链的值，设计作业申请队列以及作业 完成后释放顺序，实现主存的分配和回收。要求每次分配和回收后显示出空闲内存分区链的情况。把空闲区说明链的变化情况以及各作业的申请、释放情况显示打印出来。2. 采用可变分区存储管理，分别采用首次适应算法、最佳适应算法和最坏适应算法实现主存分配和回收。3、主存空间分配（ 1）首次适应算法在该算法中，把主存中所有空闲区按其起始地址递增的次序排列。在为作业分配存储空间时，从上次找到的空闲分区的下一个空闲分区开始查找，直到找到第一个能满足要求的空闲区

6、，从中划出与请求的大小相等的存储空间分配给作业，余下的空闲区仍留在空闲区链中。（2）最佳适应算法在该算法中，把主存中所有空闲区按其起始地址递增的次序排列。在为作业分配存储空间时，从上次找到的空闲分区的下一个空闲分区开始查找，直到找到一个能满足要求的空闲区且该空闲区的大小比其他满足要求的空闲区都小，从中划出与请求的大小相等的存储空间分配给作业，余下的空闲区仍留在空闲区链中（3）最坏适应算法在该算法中，把主存中所有空闲区按其起始地址递增的次序排列。在为作业分配存储空间时，从上次找到的空闲分区的下一个空闲分区开始查找， 直到找到一个能满足要求的空闲区且该空闲区的大小比其他满足要求的空 闲区都大，从中

7、划出与请求的大小相等的存储空间分配给作业，余下的空闲 区仍留在空闲区链中。4、主存空间回收当一个作业执行完成撤离时，作业所占的分区应该归还给系统。归还的分 区如果与其它空闲区相邻，则应合成一个较大的空闲区，登记在空闲区说明链中, 此时，相邻空闲区的合并问题，要求考虑四种情况：(1)释放区下邻空闲区(低地址邻接)(2)释放区上邻空闲区(高地址邻接)(3)释放区上下都与空闲区邻接(4)释放区上下邻都与空闲区不邻接五、程序流程图main函数里的流程图分配空间里的流程图回收空间里的流程图本程序采用了一个 struct free_table数据结构，里面包含分区序号（nunrj）、起始地址（addres

8、s）、分区长度（length ）和分区状态（state ）。还用了线性表struct Node ） ，里面包含前区指针（prior ）和后继指针（next）。一开始定义一条（含有 first 和end）的链，用开始指针和尾指针开创 空间链表。然后分别按三种算法进行分配和回收。在该程序中关键函数有，sort （）、 allocation （）、 recovery（）、 和 First_fit（）、 Best_fit （）、 Worst_fit （） ；其中 sort （）函数是用来整理分区序号的，如在删序号3 时，她与前面序号2 相连在一起了，然后序号2 中的长度总满足申请的内存大小，就会在序号

9、2 中分配，然后序号在2 的基础上加1 ，一直加，加到与原本序号3 的下一个序号也就是4 相等， 这时 sort （） 就开始有明显的工作了；allocation （）是分配空间的，也是过渡到三个算法中的，当三个算法中满足或者不满足分配请求，都会又返回值给allocation （）； recovery （）是用来回收内存的，里面包含了四种情况相连结果，即释放区上与空闲区邻接、释放区下与空闲区邻接、释放区上下都与空闲区邻接、释放区上下都与空闲区不邻接这四种情况的结果。七、源代码#include<stdio.h>#include<stdlib.h>#define OK 1

10、/ 完成#define ERROR 0 / 出错typedef int Status;typedef struct free_table/ 定义一个空闲区说明表结构int num; / 分区序号long address; /起始地址long length; /int state; /ElemType;typedef struct Node/ElemType data;struct Node *prior; /struct Node *next; / Node,*LinkList;LinkList first; /LinkList end; /int flag;/分区大小分区状态线性表的双向链表

11、存储结构前趋指针后继指针头结点尾结点记录要删除的分区序号Status Initblock()/开创带头结点的内存空间链表first=(LinkList)malloc(sizeof(Node);end=(LinkList)malloc(sizeof(Node);first->prior=NULL;first->next=end;end->prior=first;end->next=NULL;end->data.num=1;end->data.address=40;end->data.length=600;end->data.state=0;retu

12、rn OK;void sort()/ 分区序号重新排序Node *p=first->next,*q;q=p->next;for(;p!=NULL;p=p->next)for(q=p->next;q;q=q->next)if(p->data.num>=q->data.num)q->data.num+=1;/ 显示主存分配情况void show() int flag=0;/用来记录分区序号Node *p=first;p->data.num=0;p->data.address=0;p->data.length=40;p->

13、data.state=1;sort();printf("ntt 主存空间分配情况n");printf(”*nn);printf(" 分区序号t 起始地址t 分区大小t 分区状态nn");while(p) printf("%dtt%dtt%d",p->data.num,p->data.address,p->data.length);if(p->data.state=0) printf("tt空闲 nn");else printf("tt已分配 nn");p=p->ne

14、xt;”*");/ 首次适应算法Status First_fit(int request)/ 为申请作业开辟新空间且初始化Node *p=first->next;LinkList temp=(LinkList)malloc(sizeof(Node);temp->data.length=request;temp->data.state=1;p->data.num=1;while(p)if(p->data.state=0)&&(p->data.length=request)/ 有大小恰好合适的空闲块p->data.state=1;

15、return OK;break;else if(p->data.state=0) && (p->data.length>request)/ 有空闲块能满足需求且有剩余temp->prior=p->prior;temp->next=p;temp->data.address=p->data.address;temp->data.num=p->data.num;p->prior->next=temp;p->prior=temp;p->data.address=temp->data.address

16、+temp->data.length;p->data.length-=request;p->data.num+=1;return OK;break;p=p->next;return ERROR;/ 最佳适应算法Status Best_fit(int request)int ch; / 记录最小剩余空间Node *p=first;Node *q=NULL; / 记录最佳插入位置LinkList temp=(LinkList)malloc(sizeof(Node);temp->data.state=1;p->data.num=1;while(p) / 初始化最小

17、空间和最佳位置if(p->data.state=0) && (p->data.length>=request) )if(q=NULL)q=p;ch=p->data.length-request;else if(q->data.length > p->data.length)q=p;ch=p->data.length-request;p=p->next;if(q=NULL) return ERROR;/ 没有找到空闲块else if(q->data.length=request)q->data.state=1;re

18、turn OK;elsetemp->prior=q->prior;temp->next=q;temp->data.address=q->data.address;temp->data.num=q->data.num;q->prior->next=temp;q->prior=temp;q->data.address+=request;q->data.length=ch;q->data.num+=1;return OK;return OK;/ 最差适应算法Status Worst_fit(int request)int

19、ch; /记录最大剩余空间Node *p=first->next;Node *q=NULL; / 记录最佳插入位置LinkList temp=(LinkList)malloc(sizeof(Node);temp->data.length=request;temp->data.state=1;p->data.num=1;while(p) / 初始化最大空间和最佳位置if(p->data.state=0 && (p->data.length>=request) )if(q=NULL)q=p;ch=p->data.length-requ

20、est;else if(q->data.length < p->data.length)q=p;ch=p->data.length-request;p=p->next;if(q=NULL) return ERROR;/ 没有找到空闲块else if(q->data.length=request)q->data.length=1;return OK;elsetemp->prior=q->prior;temp->next=q;temp->data.address=q->data.address;temp->data.nu

21、m=q->data.num;q->prior->next=temp;q->prior=temp;q->data.address+=request;q->data.length=ch;q->data.num+=1;return OK;return OK;/ 分配主存Status allocation(int a)int request;/ 申请内存大小printf(" 请输入申请分配的主存大小(单位 :KB):");scanf("%d",&request);if(request<0 |request=

22、0)printf(" 分配大小不合适，请重试！");return ERROR;switch(a)case 1: / 默认首次适应算法if(First_fit(request)=OK) printf("t*分配成功！*");else printf("t*内存不足，分配失败！*");return OK;break;case 2: / 选择最佳适应算法if(Best_fit(request)=OK) printf("t*分配成功！*");else printf("t*内存不足，分配失败！*");ret

23、urn OK;break;case 3: / 选择最差适应算法if(Worst_fit(request)=OK) printf("t*分配成功！*");else printf("t*内存不足，分配失败！*");return OK;break;Status deal1(Node *p)/ 处理回收空间Node *q=first;for(;q!=NULL;q=q->next)if(q=p)if(q->prior->data.state=0&&q->next->data.state!=0)q->prior-&

24、gt;data.length+=q->data.length;q->prior->next=q->next;q->next->prior=q->prior;q=q->prior;q->data.state=0;q->data.num=flag-1;)if(q->prior->data.state!=0&&q->next->data.state=0)(q->data.length+=q->next->data.length;q->next=q->next->ne

25、xt;q->next->next->prior=q;q->data.state=0;q->data.num=flag;)if(q->prior->data.state=0&&q->next->data.state=0)(q->prior->data.length+=q->data.length;q->prior->next=q->next;q->next->prior=q->prior;q=q->prior;q->data.state=0;q->data

26、.num=flag-1;)if(q->prior->data.state!=0&&q->next->data.state!=0)(q->data.state=0;)return OK;)Status deal2(Node *p)/处理回收空间(Node *q=first;for(;q!=NULL;q=q->next)(if(q=p)(if(q->prior->data.state=0&&q->next->data.state!=0)(q->prior->data.length+=q->

27、data.length;q->prior->next=q->next;q->next->prior=q->prior;q=p->prior;q->data.state=0;q->data.num=flag-1;if(q->prior->data.state!=0&&q->next->data.state=0)(q->data.state=0;)if(q->prior->data.state=0&&q->next->data.state=0)(q->p

28、rior->data.length+=q->data.length;q->prior->next=q->next;q->next->prior=q->prior;q=q->prior;q->data.state=0;q->data.num=flag-1;)if(q->prior->data.state!=0&&q->next->data.state!=0)(q->data.state=0;)return OK;)/主存回收Status recovery(int flag)Node *

29、p=first;for(;p!=NULL;p=p->next)if(p->data.num=flag)if(p->prior=first)if(p->next!=end)/ 当前P指向的下一个不是最后一个时if(p->next->data.state=0) /与后面的空闲块相连p->data.length+=p->next->data.length;p->next->next->prior=p;p->next=p->next->next;p->data.state=0;p->data.num=

30、flag;else p->data.state=0;if(p->next=end)/ 当前P指向的下一个是最后一个时p->data.state=0;/ 结束 if(p->prior=block_first) 的情况else if(p->prior!=first)if(p->next!=end)deal1(p);elsedeal2(p);/ 结束 if(p->prior!=block_first) 的情况/ 结束 if(p->data.num=flag) 的情况printf("t* 回收成功*");return OK;/ 主函数

31、void main()int i; / 操作选择标记int a;/ 算法选择标记printf("*n");printf("tt 用以下三种方法实现主存空间的分配n");printf("t(1) 首次适应算法t(2) 最佳适应算法t(3) 最差适应算法n");n");printf("n");printf(" 请输入所使用的内存分配算法:");scanf("%d",&a);while(a<1|a>3)printf(" 输入错误，请重新输入所

32、使用的内存分配算法:n");scanf("%d",&a);switch(a)case 1:printf("nt* 使用首次适应算法：*n");break;case 2:printf("nt*使用最佳适应算法：*n");break;case 3:printf("nt*使用最坏适应算法：*n");break;Initblock(); / 开创空间表while(1)show();退出 n");printf("t1:分配内存t2: 回收内存t0:printf(" 请输入您的操作：");scanf("%d",&i);if(i=1)allocation(a); /分配内存else if(i=2) /内存回收printf("请输入您要释放的分区号：");scanf("%d",&flag);recovery(flag);else if(i=0)printf("n