操作系统实验四报告材料-主存空间分配和回收(含源码)

1、实用标准文案计算机 学院 计算机科学与技术 专业_班学号_姓名教师评定实验题目 主存空间的分配和回收一、实验目的熟悉主存的分配与回收。 理解在不同的存储管理方式下，如何实现主存空间的分配与回收。掌握动态分区分配方式中的数据结构和分配算法及动态分区存储管理方式及其实现过 程。二、实验内容和要求主存的分配和回收的实现是与主存储器的管理方式有关的。所谓分配，就是解决多道作业或多进程如何共享主存空间的问题。所谓回收，就是当作业运行完成时将作业或进程所占的主存空间归还给系统。可变分区管理是指在处理作业过程中建立分区，使分区大小正好适合作业的需求，并且分区个数是可以调整的。当要装入一个作业时，根据作业需要

2、的主存量查看是否有足够的空 闲空间，若有，则按需要量分割一个分区分配给该作业；若无，则作业不能装入，作业等待。随着作业的装入、完成， 主存空间被分成许多大大小小的分区，有的分区被作业占用，而有的分区是空闲的。实验要求使用可变分区存储管理方式，分区分配中所用的数据结构采用空闲分区表和空闲分区链来进行，分区分配中所用的算法采用首次适应算法、最佳适应算法、最差适应算法三种算法来实现主存的分配与回收。同时，要求设计一个实用友好的用户界面，并显示分配与回收的过程。同时要求设计一个实用友好的用户界面，并显示分配与回收的过程。三、实验主要仪器设备和材料实验环境硬件环境：旧M-PC或兼容机软件环境：VC+ 6

3、.0四、实验原理及设计分析某系统采用可变分区存储管理，在系统运行当然开始，假设初始状态下，可用的内存空间为640KB,存储器区被分为操作系统分区（40KB）和可给用户的空间区（600KB）。（作业1申请130KR 作业2申请60KB作业3申请100KB、作业2释放60KB、作业4申请200KB、作业3释放100KR 作业1释放130KB、作业5申请140KB、 作业6申请60KB、作业7申请50KB）当作业1进入内存后，分给作业 1 （130KB）,随着作业1、2、3的进入，分别分配 60KR 100KB,经过一段时间的运行后，作业 2运行完毕，释放所占内存。此时，作业 4进入系统， 要求分配

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

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

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

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

8、 free_table数据结构，里面包含分区序号（ num）、起始地址（address）、分区长度（length）和分区状态（state）。还用了线性表的双性链表存储结构 （struct Node）,里面包含前区指针（prior）和后继指针（next）。一开始定义一条（含有 first和end） 的链，用开始指针和尾指针开创空间链表。然后分别按三种算法进行分配和回收。在该程序中关键函数有，sort ()、allocation ()、recovery ()、和 First_fit ()、Best_fit()、Worst_fit ();其中sort ()函数是用来整理分区序号的，如在删序号3时，她

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

10、clude<stdlib.h>#define OK 1/完成#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;Lin

11、kList first; / 头结点LinkList end;/尾结点int flag;/记录要删除的分区序号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=60

12、0;end->data.state=0;return 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-&

13、gt;data.length=40;p->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("皿 空闲 nn");

14、else printf("皿已分配 nn");p=p->next;printf("*nn");首次适应算法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->

15、;data.length=request)/有大小恰好合适的空闲块p->data.state=1;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->

16、prior=temp;p->data.address=temp->data.address+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->d

17、ata.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-request;else if(q->data.length > p->data.length)q=p；ch=p->data.length-request;p=p->next;if(q=NULL) return

18、ERROR;/ 没有找到空闲块else if(q->data.length=request)q->data.state=1;return 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->dat

19、a.num+=1;return OK;return OK;最差适应算法Status Worst_fit(int request)int 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->da

20、ta.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.length=1;return OK;elsetemp->prior=q->prior;temp->n

21、ext=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 allocation(int a)int request;/申请内存大小printf("请输入申请分配的主存大小(单位:KB):");s

22、canf("%d",&request);if(request<0 |request=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*

23、分配成功！*");else printf("t* 内存不足，分配失败！ *");return 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.s

24、tate=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.num=flag-1;if(q->prior->data.state!=0&&q->next->data.state=0)q->data.length

25、+=q->next->data.length;q->next=q->next->next;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=

26、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 deal2(Node *p)/ 处理回收空间Node *q=first;for(;q!=NULL;q=q->next)if(q=p)if(q->prior->data.state=0&&q->next->d

27、ata.state!=0)q->prior->data.length+=q->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

28、=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.num=flag-1;)if(q->prior->data.state!=0&&q->next->data.state!=0)q->data.state=0;)r

29、eturn OK;)/主存回收Status recovery(int flag)Node *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-

30、>next;p->data.state=0;p->data.num=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(

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

32、;3)printf("输入错误，请重新输入所使用的内存分配算法：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();printf("t1:分配内存t2:回收内存t0:退出n&

33、quot;);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 退出程序 n");break; 退出else 输入操作有误printf("输入有误，请重试！")； continue;八、执行结果

34、和结果分析初始化首次适应算法:清输入所使用的内存分配算法:工*使用首次适应算法:*主存空间分配情况分区序号起始地址分区大小分区状态0040已分配140600空闲0 ：退出当作业1、2、3顺利分配内存空间后:1：%掣内存2=回收内存的摄信1信分屯己的正左大小单位工HBf时*吩配成功! *至存空间分配情况M：MXK：KM：ME>EXME>EM：ME>EXMEX<>XXM：X<M：<XM：>tM 球 XX 球 XX 球 XX 速 XXltXKMMiXltXXaCXXKXXJt分区序号起始地址分区大小分区状态Hg40已分配14B130已分配2170G3已

35、分配3230100已分配-4330310空闲XKMMEKXMEXMMEXXMEXMMEXMXMXXKXXJOEXXaCXXXXXatXXJEXiMaCXiMitNiMJfXWXiMJfXiMJE回收序号2里面的内存:2=回收内存0:退出曦存MEXXMEXXMEXXMEXXXKK 睡 KKXKKitKKXXKitHKitXKItMiKitMiKICMiXICMiXatMiXatMiXMMiXatMiXat分区序号起始地址分区大小分区状态040已分配140130已分配217065空闲3230100已分配433W310空闲XKKMEmMEXKMEXJKMEJitKMEXJKaiEXJKaiEXKai

36、EmaiEXKKXKaCXKKXXaCKXJCXiWiiWiWXiMaiEXXK分配作业4:王行空间分配情沉分区序号起始地址分区大小分区状态0040已分配14日130已分配217060空闲3230100已分配43302B0已分配5536110空闲已内存回收内存分区序号起始地址分区大小分区状态已分配已分配已分配JiW*王存空间分配情况回收序号3里面的内存（与上邻序号 2相连了）回收序号1里的内存（与下邻序号 2相连了）请己内存 2：回收内存 0：退出I蔷分配情况分区序号起始地址分区大小分区状态0040已分配143290空闲4330200已分配553H110空闲继续分配（会发现总是按顺序查找满足要

37、求的第一个空闲块，一旦发现就会分配）2：回收内存 0=退出大小 < 单位;KBX1的*分配成功！*噎存空间分配情况藕潞雌施分区序号起始地址分区大小分区状态回040已分配140140已分配2180150空闲433H200已分配5530110空闲1 ：箕鼻内存2=回收内存0=退出需入甯蓍舞酉颉玉本大小单位= «B>：60酉己成功!""""生存空间分配情况g分区序号起始地址分区大小分区状态M&已分配14014。已分配218060已分配32459M空闲433R200己分配5530110空闲1；方喧己内存2;回收内存0：圈翦箪甯患W商

38、 3 套大小 < 单位= KB> = 50酉己成功!"""">王存空间分配情况退出分区序号起始地址分区大小分区状态0040已分配140140已分配2180fa0己分配324050已分配429043空闲5330200已分配6530110空闲初始化最佳适应算法:请输入所使用的内存分配算法;2*使用最佳适应算法*主存空间分配情况产区序号起始地址分区大小分区状态040已分配140S00空闲小色翩己内存 2;回收内存 0:退出 僵需工国请温市点存大单位;KB二L*配成功! *王存空间分配情况分区序号起始地址分区大小分区状态W0已分配140130已

39、分配217060已分配3230100已分配4330310空闲1：分配内存2：回收内存 0：退出您的操伯2恩要释汆联笈屋号；2*回收成功*全存空间分配情况分区序号起始地址分区大小分区状态040已分配4013M已分配1706日空闲2301刖已分配33031H空闲,一二允配内存2：回收内存质退出扁人您要释成的鸡号回收成功* 王存空间分配情况分区序号起始地址分区大小分区状态0040已分配140290空闲4330200已分配b530110空闲继续分配（会发现总是查找满足要求的空闲块且其比其他空闲块长度小，一旦发现就会分 配）：1=维a内存2：回收内存 0：退出请领人蟹的噪有L 清输人苗请芬熙的四J大小单

40、位二HB）： 140*配成功! * 王存空间分配情况分区序号起始地址分区大小分区状态0040已分配140140已分配2180150空闲4330200已分配5530110空闲、，:杀己内存2：回收内存0=退出胃鹦嘴曾*酉说金大小单位丽：60*71配成功! * 王存空间分配情况分区序号起始地址分区大小分区状态3040已分配140140已分配218015W空闲4330200已分配55306目已分配b59050空闲WH±iiUUHjiUWHjiUUHjiUWHjiUUHjiUWHjiUUHjiUWHdiUUHjiUWHdiUUHjiUWHdiWUHjiUUHdiWUHjiUUHdiUUHji

41、UUHdiUUN单位口乂切! *王存空间分配情况0：退出分区序号起始地址分区大小分区状态日040已分配140140已分配21髓150空闲4330260已分配553060已分配65905目已分配初始化最坏适应算法:请输入所使用的内存分配算法：3用最坏适应算法：*«* MH舞鸳就空间分配,而巳内存 2：回收内存 0=退出 ：1分区序号起始地址分区大小分区状态U04M已分配140130已分配217W6购已分配3230100已分配4330310空闲额入份曲翻I己内存2=回收内存0：退出睡耳M X一的益筌号：2回收成功*王存空间分配情况主存空间分配情况HKIMKXlilCIHMKKMEHXHK

42、iMMiKiMMEMEiMMMiltMKiMMiHif Mi JCM MiM：iMMM：«：!<«：HMHK MH MIMI9区序号起始地址分区大小分区状态0040已分配140608空闲M H XU X K X M： MEN K KMHMHMHMHM： XML X MtMX HJtJC KOtH XXX KMX MX 芭 K MM MKK M XM M M： X K KM M X JC *分区序号起始地址分区大小分区状态0040已分配|40130已分配21706。空闲3230100已分配4333310空闲MKNXKJtXXMJKNHKKMNMMXKKMKMJtMHXM

43、KXMMItXMMNKMNJitJKKHJCNJCMJCXMJCJCMJCKK0：退出继续分配（会发现总是查找满足要求的空闲块且其比其他空闲块长度小，一旦发现就会分 配）：2：回收内存1： 己内存造装不婚的凰辰4修输人:愚要释汆的分三号,工*回收成功王存空间分配情况分区序号起史时也址分区大小分区状态0040已分配140290空闲433H200已分配553M110空闲1*«rlF 2=回收内存 0=退出存大小单位：KB：140f 功！ *王存空间分配情况分区序号|起始地址分区大小分区状态040已分配40140已分配180空闲33D200已分配53g1.1R空闲1：分配内存2=回收内存 0：退出请领入罐的探程：1、请输人$情芬配的主在人小单