可变式分区分配.doc

1、阳光学院操作系统课程设计 操作系统课程设计题 目：模拟可变分区内存管理的内存分配策略 姓 名： 学 号： 专 业： 2008年1月1日第 30 页 共 31 页模拟可变分区内存管理的内存分配策略 摘 要：模拟可变分区内存管理的模式下的各种内存分配策略，根据输入的各进程的信息（进程名，需要内存大小，进入内存时间，退出内存时间，发生动态申请内存的时间，动态申请的内存大小等），输出各个时间段上系统中的内存分布情况（各个空闲区位置和大小，各个进程空间的位置和大小）。关键词：最先适配，下次适配，最优适配，最差适配，在各种策略下允许进程的动态申请内存空间。 前言 一.设计的背景1.1介绍相关概念，相关算法

2、可变分区模式的基本工作工程：内存分配策略（1）最先适应算法（First Fit）：从空闲分区表的第一个表目起查找该表，把最先能够满足要求的空闲区分配给作业，这种方法目的在于减少查找时间。为适应这种算法，空闲分区表（空闲区链）中的空闲分区要按地址由低到高进行排序。该算法优先使用低址部分空闲区，在低址空间造成许多小的空闲区，在高地址空间保留大的空闲区。优点：简单，快捷，查找次数较小。缺点：经常把大分区分配给小作业（2）下次适配：即顺序扫描自由块表，直至第二次找到一个足够大的自由块为止，该块即为被选中的块。（3）最佳适应算法（Best Fit）： 它从全部空闲区中找出能满足作业要求的、且大小最小的空

3、闲分区，这种方法能使碎片尽量小。为适应此算法，空闲分区表（空闲区链）中的空闲分区要按大小从小到大进行排序，自表头开始查找到第一个满足要求的自由分区分配。该算法保留大的空闲区，但造成许多小的空闲区。优点: 总是找到与分配长度最接近的自由存储块，同时也就产生最小的剩余块。缺点:a. 查找效率低，需要扫描整个自由块表，但在按自由块长度排序时，与最先适配一样快。b.导致许多很小的空闲块，造成空间浪费，称为外部存储碎片。c.动态扩充余地小（4）最差适应算法（Best Fit）： 它从全部空闲区中找出能满足作业要求的、且大小最大的空闲分区，从而使链表中的结点大小趋于均匀，适用于请求分配的内存大小范围较窄的

4、系统。为适应此算法，空闲分区表（空闲区链）中的空闲分区要按大小从大到小进行排序，自表头开始查找到第一个满足要求的自由分区分配。该算法保留小的空闲区，尽量减少小的碎片产生。 1.2设计环境与工具：Windows xp平台，Visual C+6.0。二.设计思路和总体流程图2.1设计思路：1) 声明基本的结构体跟头文件。2) 初始化内存状态。3) 读数据并申请自由块数量及各自由块长度。4) 对自由块进行地址排序并选择算法申请作业所需内存空间大小。5) 被调度的作业一直运行到完成，把完成的结果输出。6) 最后撤消作业，释放内存空间，以免造成空间浪费。2.2数据结构定义和头文件定义#include #

5、include #include #include /系统时间使用#include #include /清屏函数使用#include const int MAXJOB=100;/定义表最大记录数 typedef struct node int start; /开始地址int length; /自由块长度char tag20; /自由块状态char time64;/进入系统时间job; job freesMAXJOB;/定义空闲区表 int free_quantity; /空闲job occupysMAXJOB;/定义已分配区表 int occupy_quantity; /使用中free_qua

6、ntity与occupy_quantity是全局变量2.3总体流程图如图12.4模块分割、模块间接口函数1) void initial() /初始化函数 2) int readData()/读数据3) void sort() /排序整理自由块4) void view() /显示各空间表及各内存分配情况5) void repeal() /撤消作业所占内存空间6) void copyright() /显示版权信息7) void main()/主函数，主要在这里选择调用算法三.算法的实现3.1功能实现fname.txt可以自己手动写入需要的相应文本内容，也可以通过程序运行后输入的内容信息系统自动生成

7、。系统自动生成文本前或是手动建立文本前，选择1便会提示出错现在我们选择2重新输入文本内容并选择输入4个自由块空间，每个空间起始地址与长度自己定义，输入完选择3显示空闲表和分配表返回选择界面，选择1申请空间，在此选择4做的是最差适配算法，此时申请的是作业所需的内存空间大小，进入系统时间跟该作业要运行的时间都是由自己定义，来模拟动态分配。申请完毕后选择3可查看分配情况跟此时自由块的空闲跟占用情况完成作业后撤消作业撤消完作业后再来查看此时自由块情况，会发现作业空间释放后，自由块恢复原本大小3.2 程序编译及使用说明1.把程序代码装进visual c+6.0的编程环境中，经过编译，连接，执行产生可执行

8、文件。执行界面上出现命令提示,提示你输入相应的操作命令,此时,你可以输入相关命令,系统将根据你选择的操作自动执行。2. 最差适应算法（Best Fit）： 它从全部空闲区中找出能满足作业要求的、且大小最大的空闲分区，从而使链表中的结点大小趋于均匀，适用于请求分配的内存大小范围较窄的系统。为适应此算法，空闲分区表（空闲区链）中的空闲分区要按大小从大到小进行排序，自表头开始查找到第一个满足要求的自由分区分配。该算法保留小的空闲区，尽量减少小的碎片产生。结论设计取得的成果:最差适应算法：它从全部空闲区中找出能满足作业要求的、且大小最大的空闲分区，从而使链表中的结点大小趋于均匀，适用于请求分配的内存大

9、小范围较窄的系统。为适应此算法，空闲分区表（空闲区链）中的空闲分区要按大小从大到小进行排序，自表头开始查找到第一个满足要求的自由分区分配。该算法保留小的空闲区，尽量减少小的碎片产生。设计中存在的问题:1）由于C语言编程能力不够扎实，在编程方面出现很多问题，使程序设计达不到完整，经过多方询问才得到解题的方法。2）动态申请内存概念有点模糊，不是很明确，是指在已有的自由块中再分配一个任意长度的内存空间还是其他。设计心得体会:在这次课程设计中，我们小组通过从各个方面查找资料过程中暴露的自己很多问题，C语言掌握的不够熟练，也使我对操作系统的知识有了进一步的了解，也巩固了C语言的知识。设计中，我们对程序代

10、码段设计比较困难，但是也就是通过这次的设计，让我更加的了解如何设计代码，我觉得课程设计能提高我们的知识水平和动手能力。我们组成员深感我们平时的编程习惯与良好的编程习惯相差甚远，小组成员决定在以后的编程过程中养成良好的编程习惯，这样有助于自己所编的程序清晰明了便于该错还有助于别人来立解你的程序。同时通过这次课程设计我们形成了通过从各方面查找资料来丰富自己的知识的能力。参考文献1孟静.操作系统教程.北京.高等教育出版社.2002.154-160.2谭浩强.C程序设计.北京.清华大学出版.1995年第四版.3吴企渊和梁燕.计算机操作系统.清华大学出版社.2002.4傅秀芬.操作系统实验指导书.广东工

11、业大学出版科.5中山大学.OSCAI.http:/i-附完整程序：#include #include #include #include /系统时间使用#include #include /清屏函数使用#include const int MAXJOB=100;/定义自由块最大记录数 typedef struct node int start; /开始地址int length; /自由块长度char tag20; /自由块状态int time;/进入系统时间int timer;/退出系统的时间job; job freesMAXJOB;/定义空闲区表 int free_quantity; /空闲

12、job occupysMAXJOB;/定义已分配区表 int occupy_quantity; /使用中void initial() /初始化函数 int i; for(i=0;iMAXJOB;i+) freesi.start=-1; freesi.length=0; strcpy(freesi.tag,free); occupysi.start=-1; occupysi.length=0; strcpy(occupysi.tag,); free_quantity=0; occupy_quantity=0; /读数据函数 int readData() int count;FILE *fp; i

13、nt choose;cout=endl; coutsetw(40)1:直接打开文本内容endl;coutsetw(40)2:重新输入文本内容endl;cout=endl; coutchoose;switch(choose)case 1:if(fp=fopen(fname.txt,r)=NULL)cout错误,文件打不开,请检查文件名endl;elsewhile(!feof(fp)fscanf(fp,%d,%d,&freesfree_quantity.start,&freesfree_quantity.length);/从文本中读出数据free_quantity+;fclose(fp);retu

14、rn 1;break;case 2:if(fp=fopen(fname.txt,w)=NULL)cout错误,文件打不开,请检查文件名endl;elsecout输入自由块的数量(0-100)count;if(count100)cout输入错误,请重新输入!endl;elsebreak;while(1)coutplease input start & length!freesfree_quantity.startfreesfree_quantity.length;fprintf(fp,t%d,%dn,freesfree_quantity.start,freesfree_quantity.leng

15、th);/输入数据读入文本free_quantity+;if(free_quantity=count)break;fclose(fp);return 1;break;return 0; void sort() /排序整理自由块 int i,j,p; for(i=0;ifree_quantity-1;i+) p=i; for(j=i+1;jfree_quantity;j+) if(freesj.startfreesp.start)/开始位置比较 p=j; if(p!=i)/进行位置交换 freesfree_quantity=freesi; freesi=freesp; freesp=freesf

16、ree_quantity; void view() /显示函数 int i; coutendl-endl; cout当前空闲表:endl; /空闲表情况cout起始地址 长度 状态endl; for(i=1;ifree_quantity;i+)/开始的 cout.setf(2); cout.width(12); coutfreesi.start; /输出开始地址cout.width(10); coutfreesi.length; /输出自由块长度cout.width(8); coutfreesi.tagendl;/输出自由块状态 coutendl-endl; cout当前已分配表:endl;

17、cout起始地址 长度 进程名 进入系统时间 退出系统时间endl; for(i=0;ioccupy_quantity;i+)/运行中的. cout.setf(2); cout.width(12); coutoccupysi.start;/ 输出开始地址cout.width(10); coutoccupysi.length; /输出自由块长度cout.width(12); coutoccupysi.tag; /输出自由块状态cout.width(15);coutoccupysi.time;/输出系统开始时间cout.width(20);coutoccupysi.timerendl;/输出系统时

18、间退出时间coutendl按任意键继续.endl;getch();/按任意键fflush(stdin);/清空缓冲区 void headmost() /最先适应分配算法 char job_name20; int job_length;int job_time;int job_timer;int i,j,flag,t; coutjob_name; coutjob_length; while(1)coutjob_time;coutjob_timer;if(job_timer=job_time)cout你输入的时间错误，请重新输入!endlendl;elsebreak; flag=0; for(i=

19、0;i=job_length)/有长度够的自由块 flag=1; if(flag=0) coutendlSorry,当前没有能满足你申请长度的空闲内存,请稍候再试=job_length) t=1; i+; /*把输入的值赋值到运行块中i-;occupysoccupy_quantity.start=freesi.start; strcpy(occupysoccupy_quantity.tag,job_name); occupysoccupy_quantity.length=job_length;occupysoccupy_quantity.time=job_time;occupysoccupy_

20、quantity.timer=job_timer;occupy_quantity+; if(freesi.lengthjob_length) freesi.start+=job_length; /自由块的开始地址增加freesi.length-=job_length; /自由块的长度减少 else for(j=i;jfree_quantity-1;j+) freesj=freesj+1; free_quantity-; cout内存空间分配成功:)!endl; coutendl按任意键继续.endl;getch();fflush(stdin); void nextTime() /下次适配算法

21、char job_name20; int job_length;int job_time;int job_timer;int i,j,flag,t; coutjob_name; coutjob_length; while(1)coutjob_time;coutjob_timer;if(job_timer=job_time)cout你输入的时间错误，请重新输入!endlendl;elsebreak;flag=0; for(i=0;i=job_length) flag=1; if(flag=0) coutendlSorry,当前没有能满足你申请长度的空闲内存,请稍候再试=job_length) t

22、+;if(2=t)break; i+; /i-; occupysoccupy_quantity.start=freesi.start; strcpy(occupysoccupy_quantity.tag,job_name); occupysoccupy_quantity.length=job_length;occupysoccupy_quantity.time=job_time;occupysoccupy_quantity.timer=job_timer;occupy_quantity+; if(freesi.lengthjob_length) freesi.start+=job_length

23、; freesi.length-=job_length; else for(j=i;jfree_quantity-1;j+) freesj=freesj+1; free_quantity-; cout内存空间分配成功:)!endl; coutendl按任意键继续.endl;getch();fflush(stdin); void optimization() /最优适应分配算法 char job_name20; int job_length;int job_time;int job_timer;int i,j,flag,t; coutjob_name; coutjob_length; while

24、(1)coutjob_time;coutjob_timer;if(job_timer=job_time)cout你输入的时间错误，请重新输入!endlendl;elsebreak;flag=0; for(i=0;i=job_length) flag=1; if(flag=0) coutendlSorry,当前没有能满足你申请长度的空闲内存,请稍候再试=job_length) t=1; i+; i-; for(j=0;j=job_length)&(freesj.lengthjob_length) freesi.start+=job_length; freesi.length-=job_lengt

25、h; else for(j=i;jfree_quantity-1;j+) freesj=freesj+1; free_quantity-; cout内存空间分配成功:)!endl; coutendl按任意键继续.endl;getch();fflush(stdin); void worst() /最坏适应算法 char job_name20; int job_length;int job_time;int job_timer;int i,j,flag,t; coutjob_name; coutjob_length; while(1)coutjob_time;coutjob_timer;if(jo

26、b_timer=job_time)cout你输入的时间错误，请重新输入!endlendl;elsebreak;flag=0; for(i=0;i=job_length) flag=1; if(flag=0) coutendlSorry,当前没有能满足你申请长度的空闲内存,请稍候再试=job_length) t=1; i+; i-; for(j=0;j=job_length)&(freesj.lengthfreesi.length) i=j; occupysoccupy_quantity.start=freesi.start; strcpy(occupysoccupy_quantity.tag,

27、job_name); occupysoccupy_quantity.length=job_length;occupysoccupy_quantity.time=job_time;occupysoccupy_quantity.timer=job_timer;occupy_quantity+; if(freesi.lengthjob_length) freesi.start+=job_length; freesi.length-=job_length; else for(j=i;jfree_quantity-1;j+) freesj=freesj+1; free_quantity-; cout内存

28、空间分配成功:)!endl; coutendl按任意键继续.endl;getch();fflush(stdin); void repeal() /撤消作业 char job_name20; int i,j,flag,p=0; int start; int length; coutjob_name; flag=-1; for(i=0;ioccupy_quantity;i+) if(!strcmp(occupysi.tag,job_name) flag=i; start=occupysi.start; length=occupysi.length; if(flag=-1) cout没有这个进程名e

29、ndl; else/加入空闲表 for(i=0;ifree_quantity;i+) if(freesi.start+freesi.length)=start) if(i+1)free_quantity)&(freesi+1.start=start+length) freesi.length=freesi.length+freesi+1.length+length; for(j=i+1;jfree_quantity;j+) freesj=freesj+1; free_quantity-; p=1; else freesi.length+=length; p=1; if(freesi.start

30、=(start+length) freesi.start=start; freesi.length+=length; p=1; if(p=0) freesfree_quantity.start=start; freesfree_quantity.length=length; free_quantity+; for(i=flag;ioccupy_quantity;i+)/删除分配表中的该作业 occupysi=occupysi+1; occupy_quantity-; coutendl按任意键继续.endl;getch();fflush(stdin); void copyright() /显示版

31、权信息函数 coutendlendl; couttt endl; couttt 可变分区存储管理模拟系统 endl; couttt endl; couttt 10#616 weilong endl; couttt 2332426 copyright 2008 endl; couttt endl; coutendlendl; void main() int flag=0; int t=1; int chioce=0; int i=0,j=0,k=0,m=0;copyright(); initial(); flag=readData(); while(flag=1) sort(); system(cls);coutendlendl=endl; cout 可变分区存储管理模拟系统endl; cout=endl; cout 1.申请空间 2.撤消作业 3.显示空闲表