实验四主存空间的分配和回收
专业：商业软件工程 班级：商软2班 姓名：甘佳萍 学号：201406114207
一. 目的和要求
1.1. 实验目的
用高级语言完成一个主存空间的分配和回收程序，以加深对动态分区分配方式及其算法的理解。
1.2. 实验要求
采用连续分配方式之动态分区分配存储管理，使用首次适应算法、循环首次适应算法、最佳适应算法和最坏适应算法4种算法完成设计。
（1）**设计一个作业申请队列以及作业完成后的释放顺序，实现主存的分配和回收。采用分区说明表进行。
（2）或在程序运行过程，由用户指定申请与释放。
（3）设计一个空闲区说明表，以保存某时刻主存空间占用情况。
把空闲区说明表的变化情况以及各作业的申请、释放情况显示。
二. 实验内容
第一步：
完成程序数据结构的创建，初始化内存分配情况，创建空闲分区表和已分配分区表。
第二步：
完成为某作业分配内存空间。
- 用户输入作业名称；
- 判断作业名称是否已经存在，如果存在则要求用户重新输入；
- 用户输入作业所占空间大小；
- 判断是否能够在剩余的空闲区域中找到一块放置该作业，如果不行则要求用户重新输入；
- 显示菜单，由用户选择使用哪一种分配算法：
1) 首次适应算法
2) 循环首次适应算法
3) 最佳适应算法
4) 最坏适应算法
6.为该作业分配内存空间，分配处理流程图如下（size的值设定为1K）
7.屏幕显示分配后的内存分区情况。
第三步：
完成内存空间回收；
- 由用户输入作业的ID，决定所要终止的作业；
- 判断是否存在用户所输入的ID，如果存在则进行终止，否则提示作业不存在；
- 判断即将终止的作业前后是否有空闲区域，如果没有则作业所占的空间独立成为一个空闲块，在未分配区表中增加一项；
（思考：如何判断前后是否有空闲块？）
4.即将终止作业所占空间前后有空闲块的情况：（X代表即将被终止的作业，黑色代表内存中的空闲块）
所以，判断某个即将被终止的作业所占空间前面是否有空闲块的方法是：作业空间的起始地址A.begin是否等于某个空闲块的结束地址B.end，若相等，则前面有空闲块，则需要合并；若不相等则再判断后面是否有空闲块。
回答：如何判断？
5.进行四种情况的判断，然后分别做出相应的区块回收操作。
回答：如何处理回收？
6.显示回收后的内存使用情况。
根据指定的实验课题，完成设计、编码和调试工作，完成实验报告。
三、 实验方法、步骤及结果测试
1. 源程序名：压缩包文件（rar或zip）中源程序名OS.c
可执行程序名：OS.exe
2. 原理分析及流程图
主要总体设计问题。
(包括存储结构，主要算法，关键函数的实现等)
存储结构：
typedef struct free_table//定义一个空闲区说明表结构 { int num; //分区序号 long begin; //起始地址 long size; //分区大小 int status; //分区状态 }ElemType; typedef struct Node// 线性表的双向链表存储结构 { ElemType data; struct Node *prior; //前趋指针 struct Node *next; //后继指针 }Node,*LinkList; LinkList 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.begin=40; end->data.size=600; end->data.status=0; return SIZE; }
主要算法：
关键函数：
Status allocation(int a)
Status Best_fit(int request)
Status deal1(Node *p)
Status deal2(Node *p)
Status First_fit(int request)
Status Initblock()
Status recovery(int flag)
void show()
void sort()
Status Worst_fit(int request)
3. 主要程序段及其解释：
实现主要功能的程序段，重要的是程序的注释解释。
源程序:
#include<stdio.h> #include<conio.h> #include<string.h> #include<stdlib.h> #define SIZE 1 #define ERROR 0 //出错 typedef int Status; typedef struct free_table//定义一个空闲区说明表结构 { int num; //分区序号 long begin; //起始地址 long size; //分区大小 int status; //分区状态 }ElemType; typedef struct Node// 线性表的双向链表存储结构 { ElemType data; struct Node *prior; //前趋指针 struct Node *next; //后继指针 }Node,*LinkList; LinkList 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.begin=40; end->data.size=600; end->data.status=0; return SIZE; } //菜单 void menu() { printf(" |*************内存分配和回收***********| "); printf(" |======================================| "); printf(" | 0.退出 | "); printf(" | 1.首次适应算法 | "); printf(" | 2.最佳适应算法 | "); printf(" | 3.最坏适应算法 | "); printf(" |======================================| "); } 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.begin=0; p->data.size=40; p->data.status=1; sort(); printf(" 》主存空间分配情况《 "); printf("********************************************************** "); printf("分区序号 起始地址 分区大小 分区状态 "); while(p) { printf("%d %d %d",p->data.num,p->data.begin,p->data.size); if(p->data.status==0) printf(" 空闲 "); else printf(" 已分配 "); p=p->next; } printf("********************************************************** "); } //首次适应算法 Status First_fit(int request) { //为申请作业开辟新空间且初始化 Node *p=first->next; LinkList temp=(LinkList)malloc(sizeof(Node)); temp->data.size=request; temp->data.status=1; p->data.num=1; while(p) { if((p->data.status==0)&&(p->data.size==request)) { //有大小恰好合适的空闲块 p->data.status=1; return SIZE; break; } else if((p->data.status==0) && (p->data.size>request)) { //有空闲块能满足需求且有剩余 temp->prior=p->prior; temp->next=p; temp->data.begin=p->data.begin; temp->data.num=p->data.num; p->prior->next=temp; p->prior=temp; p->data.begin=temp->data.begin+temp->data.size; p->data.size-=request; p->data.num+=1; return SIZE; 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.size=request; temp->data.status=1; p->data.num=1; while(p) //初始化最小空间和最佳位置 { if((p->data.status==0) && (p->data.size>=request) ) { if(q==NULL) { q=p; ch=p->data.size-request; } else if(q->data.size > p->data.size) { q=p; ch=p->data.size-request; } } p=p->next; } if(q==NULL) return ERROR;//没有找到空闲块 else if(q->data.size==request) { q->data.status=1; return SIZE; } else { temp->prior=q->prior; temp->next=q; temp->data.begin=q->data.begin; temp->data.num=q->data.num; q->prior->next=temp; q->prior=temp; q->data.begin+=request; q->data.size=ch; q->data.num+=1; return SIZE; } return SIZE; } //最差适应算法 Status Worst_fit(int request) { int ch; //记录最大剩余空间 Node *p=first->next; Node *q=NULL; //记录最佳插入位置 LinkList temp=(LinkList)malloc(sizeof(Node)); temp->data.size=request; temp->data.status=1; p->data.num=1; while(p) //初始化最大空间和最佳位置 { if(p->data.status==0 && (p->data.size>=request) ) { if(q==NULL) { q=p; ch=p->data.size-request; } else if(q->data.size < p->data.size) { q=p; ch=p->data.size-request; } } p=p->next; } if(q==NULL) return ERROR;//没有找到空闲块 else if(q->data.size==request) { q->data.size=1; return SIZE; } else { temp->prior=q->prior; temp->next=q; temp->data.begin=q->data.begin; temp->data.num=q->data.num; q->prior->next=temp; q->prior=temp; q->data.begin+=request; q->data.size=ch; q->data.num+=1; return SIZE; } return SIZE; } //分配主存 Status allocation(int a) { int request;//申请内存大小 printf("请输入申请分配的主存大小(单位:KB):"); scanf("%d",&request); if(request<0 ||request==0) { printf("分配大小不合适，请重试！"); return ERROR; } switch(a) { case 1: //默认首次适应算法 if(First_fit(request)==SIZE) printf(" ****分配成功！****"); else printf(" ****内存不足，分配失败！****"); return SIZE; break; case 2: //选择最佳适应算法 if(Best_fit(request)==SIZE) printf(" ****分配成功！****"); else printf(" ****内存不足，分配失败！****"); return SIZE; break; case 3: //选择最差适应算法 if(Worst_fit(request)==SIZE) printf(" ****分配成功！****"); else printf(" ****内存不足，分配失败！****"); return SIZE; break; } } Status deal1(Node *p)//处理回收空间 { Node *q=first; for(;q!=NULL;q=q->next) { if(q==p) { if(q->prior->data.status==0&&q->next->data.status!=0) { q->prior->data.size+=q->data.size; q->prior->next=q->next; q->next->prior=q->prior; q=q->prior; q->data.status=0; q->data.num=flag-1; } if(q->prior->data.status!=0&&q->next->data.status==0) { q->data.size+=q->next->data.size; q->next=q->next->next; q->next->next->prior=q; q->data.status=0; q->data.num=flag; } if(q->prior->data.status==0&&q->next->data.status==0) { q->prior->data.size+=q->data.size; q->prior->next=q->next; q->next->prior=q->prior; q=q->prior; q->data.status=0; q->data.num=flag-1; } if(q->prior->data.status!=0&&q->next->data.status!=0) { q->data.status=0; } } } return SIZE; } Status deal2(Node *p)//处理回收空间 { Node *q=first; for(;q!=NULL;q=q->next) { if(q==p) { if(q->prior->data.status==0&&q->next->data.status!=0) { q->prior->data.size+=q->data.size; q->prior->next=q->next; q->next->prior=q->prior; q=p->prior; q->data.status=0; q->data.num=flag-1; } if(q->prior->data.status!=0&&q->next->data.status==0) { q->data.status=0; } if(q->prior->data.status==0&&q->next->data.status==0) { q->prior->data.size+=q->data.size; q->prior->next=q->next; q->next->prior=q->prior; q=q->prior; q->data.status=0; q->data.num=flag-1; } if(q->prior->data.status!=0&&q->next->data.status!=0) { q->data.status=0; } } } return SIZE; } //主存回收 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.status==0) //与后面的空闲块相连 { p->data.size+=p->next->data.size; p->next->next->prior=p; p->next=p->next->next; p->data.status=0; p->data.num=flag; } else p->data.status=0; } if(p->next==end)//当前P指向的下一个是最后一个时 { p->data.status=0; } } //结束if(p->prior==block_first)的情况 else if(p->prior!=first) { if(p->next!=end) { deal1(p); } else { deal2(p); } }//结束if(p->prior!=block_first)的情况 }//结束if(p->data.num==flag)的情况 } printf(" ****回收成功****"); return SIZE; } void main() { int i; //操作选择标记 int a;//算法选择标记 while(1) { menu(); printf("请选择输入所使用的内存分配算法 (0~3):"); scanf("%d",&a); while(a<0||a>3) { printf(" 输入错误，请重新选择输入所使用的内存分配算法 (0~3):"); scanf("%d",&a); } switch(a) { case 1:printf(" ****使用首次适应算法：**** "); break; case 2:printf(" ****使用最佳适应算法：**** "); break; case 3:printf(" ****使用最坏适应算法：**** "); break; case 0:printf(" ****退出内存分配与回收**** "); return; } Initblock(); //开创空间表 while(1) { show(); printf(" 1: 分配内存 2: 回收内存 0: 退出当前内存分配算法 "); printf("请输入您的操作："); scanf("%d",&i); if(i==1) allocation(a); // 分配内存 else if(i==2) // 内存回收 { printf("请输入您要释放的分区号："); scanf("%d",&flag); recovery(flag); } else if(i==0) { printf(" 退出当前内存分配算法，返回主菜单 "); break; //退出 } else //输入操作有误 { printf("输入有误，请重新输入！"); continue; } } } }
4. 运行结果及分析
一般必须配运行结果截图，结果是否符合预期及其分析。
（截图需根据实际，截取有代表性的测试例子）
运行结果：
四、 实验总结
总之，编写主存空间的分配和回收的过程有（如解决实际问题）。从解决实际问题的角度，我们可以这样来看：首先要了解这个问题的基本要求，即输入、输出、完成从输入到输出的要求是什么；其次，从问题的要害入手，从前到后的解决问题的每个方面，即从输入开始入手，着重考虑如何从输入导出输出。在这个过程中，可确定所需的变量、数组、函数，然后确定处理的过程－－算法。可得出最后的结论，进而完成程序的编写。经过这次实验，我对主存空间的分配和回收有了深一步的了解，同时也初步了解了内存空间的工作原理。总的来说这个实验不是很难，还有这个实验很有趣。