武汉轻工大学 数学与计算机学院
计算机系统与系统软件 课程设计说明书
题 目： 可变分区存储管理 专 业： 信息管理与信息系统 班 级： 信息管理1201 学 号： 姓 名： 指导老师：
年 月 日
1
武汉轻工大学
可变分区存储管理
1．目的和要求
在熟练掌握计算机分区存储管理方式的原理的基础上，利用一种程序设计语言模拟实现操作系统的可变分区存储管理的功能，一方面加深对原理的理解，另一方面提高学生通过编程根据已有原理解决实际问题的能力，为学生将来进行系统软件开发和针对实际问题提出高效的软件解决方案打下基础。
2．设计内容
设计合理的数据结构来描述存储空间：对于未分配出去的部分，可以用空闲分区队列或空闲分区链表来描述，对于已经分配出去的部分，由装入内存的作业占据，可以将作业组织成链表或数组。
实现分区存储管理的内存分配功能，要求选择至少两种适应算法（首次适应算法和循环首次适应算法至少选一，最佳适应算法和最坏适应算法至少选一）。
实现分区存储管理的内存回收算法：要求能够正确处理回收分区与空闲分区的四种邻接关系。
当碎片产生时，能够进行碎片的拼接。
3．设计环境
Windows操作系统、VC++6.0 C语言
4．详细设计
（1）基础知识
分区存储管理是操作系统进行内存管理的一种方式。现代操作系统广泛采用多道程序设计的技术来提高系统吞吐量和内存的利用率。由于可变分区存储管理将一个连续的作业装入一片大小与作业恰好相等的内存中，因而地址变换的算法简单，需要的硬件支持少，变换效率高。但是最大的缺点是随着作业不断地进出内存，会将内存逐渐分割成一些大小
2
武汉轻工大学
很小而数目较多的小块，而且一块中仅能容纳一道作业，导致内存利用率较低。分区存储管理的另一个缺点是由于必须将整个作业的逻辑地址空间全部装入内存作业才可以开始运行，因而这种存储管理的方式无法实现内存的扩充。 （2）数据结构
要模拟实现可变分区存储管理，有如下一些对象需要用相关的数据结构来描述： 内存中没有被存储管理程序分配给作业的部分，属于空闲内存，要求以分区为单位进行统一管理以合理分配。包括对分区的描述（结构体）和对多个分区的组织（表格或链表）。
对于内存中已经分配给作业的那部分内存，当作业完成后应该将占据的内存归还给系统，以便进行再分配。因此必须对已分配分区进行描述和组织，以便进行内存的回收。 （3）功能模块划分
大体上可以将整个程序的模块划分成如下几个部分：
1）主模块：主要是初始化（设置物理内存的用户区的大小，选取适应算法）和界面，界面参考如下：
2）内存分配算法（首次适应算法和最佳适应算法） 3）内存回收算法
a. 回收区与插入点的前一个分区相邻接，此时可将回收区与插入点的前一分区合并，不再为回收分区分配新表项，而只修改前邻接分区的大小；
b. 回收分区与插入点的后一分区相邻接，此时合并两区，然后用回收区的首址作为新空闲区的首址，大小为两者之和；
c. 回收区同时与插入点的前后两个分区邻接，此时将三个分区合并，使用前邻接分区的首址，大小为三区之和，取消后邻接分区的表项；
d. 回收区没有邻接空闲分区，则应为回收区单独建立一个新表项，填写回收区的首址和大小，并根据其首址，插入到空闲链中的适当位置。
4）碎片拼接算法
3
武汉轻工大学
5）空闲分区队列显示 6）作业队列显示
5.设计原理
（1）首次适应算法
分配：当进程申请大小为SIZE的内存时，系统从空闲区表的第一个表目开始查询，直到首次找到等于或大于SIZE的空闲区。从该区中划出大小为SIZE的分区分配给进程，余下的部分仍作为一个空闲区留在空闲区表中。
注意：每次分配和回收后空闲区表都要按首址递增的次序排序。 （2）最佳适应算法
分配：当进程申请一个存储区时，系统从表头开始查找，当找到第一个满足要求的空闲区时，停止查找，并且这个空闲区是最佳的空闲区。所谓最佳即选中的空闲区是满足要求的最小空闲区。 （3）回收内存：
按释放区的首址，查询空闲区表，若有与释放区相邻的空闲区，则合并到相邻的空闲区中，并修改该区的大小和首址，否则，把释放区作为一个空闲区插入空闲区表。分配和回收后要对空闲区表重新排序。
6、主要数据结构
typedef struct freea //定义一个空闲区说明表的结构 { int ID; //分区号 int size; //分区大小 int address; //分区起始地址 int state; //状态 }FREEA;
typedef struct dub // 定义一个双向链表存储结构 { FREEA data; struct dub *left; //定义一个前驱指针
4
武汉轻工大学
struct dub *next; //定义一个后继指针 }DUB;
DUB* head; //定义一个头结点指针变量 DUB* last; //定义一个尾节点 int First() //初始化
int Firstfit(int ID,int need) //首次适应算法 int Bestfit(int ID,int need) //最佳适应算法 int sub(int ch) //分配作业函数 int relet(int ID) //内存回收函数 void show() //显示主存分配情况
7、流程图
首次适应算法
5
武汉轻工大学
最佳适应算法
6
武汉轻工大学
8、实验结果
初始化
首次适应算法
7
武汉轻工大学
内存回收
首次适应算法
8
武汉轻工大学
9、设计总结
我做的是第三个实验：可变分区存储管理。本程序要求实现对内存的动态分配与回收，同时，在内存的分配时还必须使用首次适应算法和最佳适应算法。最后，还要显示内存块分配和回收后空闲内存分区链的情况。
要实现对作业的内存分配，首先要有一个对作业进行创建和分配内存的模块，其中，该模块在分配内存时要使用首次适应算法和最佳适应算法；要实现对内存的回收，要有一个内存回收的模块，其中，该模块在回收内存时要考虑内存回收的情况；最后，还要有一个能显示内存空闲分区链的情况的模块。
此次课程设计不但加深我对操作系统的理论知识的理解，更增强了我的实际编程能力，丰富了编程经验，锻炼了自己动手解决实际问题的能力，促进了和同学沟通合作的能力。总之经过这次课程设计使我学到了很多在课堂上无法学到知识，增强了编程的实践经验，使把实际问题转换成抽象算法的能力增强，为我以后工作学习奠定了坚实的基础。同时十分感谢教师的指点，在老师的细心指点下使我对问题的理解更加的透彻，对编程起了至关重要的作用。并且本次课程设计更加锻炼了我的学习能力和自己收集资料的能力。总之，此次实习让我获益匪浅，希望在以后的学习中有更多的这样的锻炼机会。
附：实验源码
#include # define Free 0 //标记空闲状态 # define Use 1 //标记已用状态 # define OK 1 //标记完成 # define ERROR 0 //标记出错 # define MAXSIZE 1000 typedef struct freea //定义一个空闲区说明表的结构 { int ID; //分区号 int size; //分区大小 int address; //分区起始地址 int state; //状态 }FREEA; typedef struct dub // 定义一个双向链表存储结构 9 武汉轻工大学 { FREEA data; struct dub *left; //定义一个前驱指针 struct dub *next; //定义一个后继指针 }DUB; DUB* head; //定义一个头结点指针变量 DUB* last; int First() //开创带头接点的内存空间链表 { head=(DUB*)malloc(sizeof(DUB));//开辟内存空间 last=(DUB*)malloc(sizeof(DUB)); head->left=NULL; head->next=last; head->data.state=-1; head->data.ID=-1; head->data.size=0; head->data.address=0; last->left=head; last->next=NULL; last->data.address=0; last->data.size=MAXSIZE; last->data.ID=0; last->data.state=Free; printf(\"--------------初始化完成------------------\\n\"); return OK; } //首次适应算法 int Firstfit(int ID,int need) //接受进程名及申请量 { DUB *t=(DUB*)malloc(sizeof(DUB)); //为进程开辟新的空间及初始化 t->data.ID=ID; t->data.size=need; t->data.state=Use; DUB *p=head->next;//定义p为指向头结点的后继指针的指针变量 while(p) { if(p->data.state==Free && p->data.size==need)//有大小刚好合适的空闲块 { p->data.state=Use; p->data.ID=ID; printf(\"分区号: %d\\n\ printf(\"起始地址: %d\\n: \ printf(\"分区大小: %d\\n\ 10 武汉轻工大学 printf(\"状态: 已分配\"); return OK; break; } if(p->data.state==Free && p->data.size>need) //有比申请空间大的空闲块 { t->left=p->left; t->next=p; t->data.address=p->data.address; p->left->next=t; p->left=t; p->data.address=t->data.address+t->data.size; p->data.size-=need; printf(\"分区号: %d\\n\ printf(\"起始地址: %d\\n\ printf(\"分区大小: %d\\n\ printf(\"状态: 已分配\"); return OK; break; } p=p->next; } return ERROR; } //最佳适应算法 int Bestfit(int ID,int need) { int minsize;//标记最小剩余空间 DUB *t=new DUB; t->data.ID=ID; t->data.size=need; t->data.state=Use; DUB *p=head->next; DUB *q=NULL;//记录最佳插入位置 while(p)//初始化最小空间和最佳位置 { if(p->data.state==Free && (p->data.size>need||p->data.size==need)) { q=p; minsize=p->data.size-need; break; } p=p->next; } while(p) { 11 武汉轻工大学 if(p->data.state==Free && p->data.size==need)//有和申请空间大小刚好一样的空闲块 { p->data.ID=ID; p->data.state= Use; printf(\"分区号: %d\\n\ printf(\"起始地址: %d\\n\ printf(\"分区大小: %d\\n\ printf(\"状态: 已分配\\n\"); return OK; break; } if(p->data.state==Free && p->data.size>need)//有比申请空间大的空闲块 { if(p->data.size-need p=p->next; } if(q==NULL) return ERROR;//没有找到适合的空闲块 else //找到了最佳位置并实现分配 { t->left=q->left; t->next=q; t->data.address=q->data.address; q->left->next=t; q->left=t; q->data.address+=need; q->data.size=minsize; printf(\"分区号: %d\\n\ printf(\"起始地址: %d\\n\ printf(\"分区大小: %d\\n\ printf(\"状态: 已分配\\n\"); return OK; } return 0; } //分配主存函数 int sub(int ch) { int ID,need; printf(\"请输入进程(分区号): \\n\"); scanf(\"%d\ 12 武汉轻工大学 printf(\"请输入需要分配的主存大小(单位:KB): \\n\"); scanf(\"%d\ if(ch==1)//选择首次适应算法 { if(Firstfit(ID,need)==OK) printf(\"分配成功!\\n\"); else printf(\"内存不足,分配失败!\\n\"); return OK; } if(ch==2)//选择最佳适应算法 { if(Bestfit(ID,need)==OK) printf(\"分配成功!\\n\"); else printf(\"内存不足,分配失败!\\n\"); return OK; } return OK; } //内存回收函数 int relet(int ID) { DUB *p=head; while(p!=NULL) { if(p->data.ID==ID) { p->data.state=Free; p->data.ID=Free; if(p->left->data.state==Free)//与前面的空闲块相连 { p->left->data.size+=p->data.size; p->left->next=p->next; p->next->left=p->left; } else if(p->next->data.state==Free)//与后面的空闲块相连 { p->next->data.address=p->data.address; p->next->data.size+=p->data.size; p->left->next=p->next; p->next->left=p->left; } 13 武汉轻工大学 else if(p->left->data.state==Free && p->next->data.state==Free)//与前后的空闲块相连 { p->next->data.address=p->left->data.address; p->next->data.size+=p->left->data.size; p->left->left->next=p->next; p->next->left=p->left->left; } break; } p=p->next; } printf(\"回收成功\\n\"); return OK; } //显示主存分配情况函数 void show() { printf(\"主 存 分 配 情 况\\n\"); DUB *p=head->next; while(p) { printf(\"分区号: \"); if(p->data.ID==Free) printf(\"Free\\n\"); else printf(\"%d\\n\ printf(\"起始地址: %d\\n\ printf(\"分区大小: %d\\n\ printf(\"状态: \"); if(p->data.state==Free) printf(\"空闲\\n\"); else printf(\"已分配\\n\"); p=p->next; } return; } //主函数 int main() { int choice; //操作选择标记 do { printf(\" 可变分区存储管理\\n\"); printf(\"1、初始化 \\n\" ); 14 武汉轻工大学 printf(\"2、查看内存分配情况 \\n\"); printf(\"3、回收内存空间 \\n\"); printf(\"4、首次适应算法 \\n\"); printf(\"5、最佳适应算法 \\n\"); printf(\"0、退出 \\n\"); printf(\"请输入选择\\n\"); scanf(\"%d\ switch(choice) { case 1: { First(); break; } case 2: show(); break; case 3: { int ID; printf(\"请输入要回收的分区号: scanf(\"%d\ relet(ID); break; } case 4: { int ch = 1; sub(ch); break; } case 5: { int ch = 1; sub(ch); break; } case 0: break; } } while(choice!=0); return 0; } 15\\n\"); 因篇幅问题不能全部显示，请点此查看更多更全内容