模拟可变分区内存管理的内存分配策略

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

2、适应算法（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 #include #include #include

5、 /系统时间使用#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_quantity与occupy_quantity是全局变

6、量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可以自己手动写入需要的相应文本内容，也可以通过程序运行后输入的内容信息系统自动生成。系统自动生成文本前或是手动建立文本前，选择1便会

7、提示出错现在我们选择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傅秀芬.操作系统实验指导书.广东工业大学出版科.5中山大学.oscai.http:/

11、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; /空闲job occupysmaxjob;/定义已分配区

12、表 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; int choose;cout=endl; cout

13、setw(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);return 1;break;case 2:if(fp=f

14、open(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.length);/输入数据读入文本free_quantit

15、y+;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=freesfree_quantity; void view()

16、 /显示函数 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; cout起始地址 长度 进程名 进入系统时间 退出

17、系统时间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;/输出系统时间退出时间coutendl按任意键继续.endl;

18、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=0;i=job_length)/有长度够的自由块

19、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_quantity.timer=job_timer;

20、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() /下次适配算法 char job_name20; int job_

21、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+;if(2=t)break; i+; /i-;

22、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; freesi.length-=job_leng

23、th; 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(1)coutjob_time;coutjob_t

24、imer;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_length; else for(j=i;jfree_qua

25、ntity-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(job_timer=job_time)cout你输入的

26、时间错误，请重新输入!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,job_name); occupysoccupy_

27、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内存空间分配成功:)!endl; coutendl按任

28、意键继续.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没有这个进程名endl; else/加入空闲表 for(i=0;i

29、free_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=(start+length) freesi.st

30、art=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() /显示版权信息函数 coutendlendl; coutt

31、t 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; c

32、out 可变分区存储管理模拟系统endl; cout=endl; cout 1.申请空间 2.撤消作业 3.显示空闲表和分配表 0.退出endl; coutchioce; switch(chioce) case 1: int count;coutttt请输入你需要的内存分配算法endl;coutttt1:最先适应分配算法:endl;coutttt2:下次适应分配算法:endl;coutttt3:最优适应分配算法:endl;coutttt4:最坏适应分配算法:count;if(1=count)headmost();else if(2=count)nexttime();else if(3=coun

33、t)optimization();else if(4=count)worst();break; case 2: repeal(); break; case 3: view(); break; case 0: flag=0; break; default: cout选择错误!endl; 09/08 20:02 3kn微型装载机设计09/20 15:09 45t旋挖钻机变幅机构液压缸设计08/30 15:32 5吨卷扬机设计10/30 17:12 c620轴拨杆的工艺规程及钻2-16孔的钻床夹具设计09/21 13:39 ca6140车床拨叉零件的机械加工工艺规程及夹具设计83100308/30

34、15:37 cpu风扇后盖的注塑模具设计09/20 16:19 gdc956160工业对辊成型机设计08/30 15:45 ls型螺旋输送机的设计10/07 23:43 ls型螺旋输送机设计09/20 16:23 p-90b型耙斗式装载机设计09/08 20:17 pe10自行车无级变速器设计10/07 09:23 话机机座下壳模具的设计与制造09/08 20:20 t108吨自卸车拐轴的断裂原因分析及优化设计09/21 13:39 x-y型数控铣床工作台的设计09/08 20:25 yd5141syz后压缩式垃圾车的上装箱体设计10/07 09:20 zh1115w柴油机气缸体三面粗镗组合机

35、床总体及左主轴箱设计09/21 15:34 zxt-06型多臂机凸轮轴加工工艺及工装设计10/30 16:04 三孔连杆零件的工艺规程及钻35h6孔的夹具设计08/30 17:57 三层货运电梯曳引机及传动系统设计10/29 14:08 上盖的工工艺规程及钻6-4.5孔的夹具设计10/04 13:45 五吨单头液压放料机的设计10/04 13:44 五吨单头液压放料机设计09/09 23:40 仪表外壳塑料模设计09/08 20:57 传动盖冲压工艺制定及冲孔模具设计09/08 21:00 传动系统测绘与分析设计10/07 23:46 保护罩模具结构设计09/20 15:30 保鲜膜机设计10

36、/04 14:35 减速箱体数控加工工艺设计10/04 13:20 凿岩钎具钎尾的热处理工艺探索设计09/08 21:33 分离爪工艺规程和工艺装备设计10/30 15:26 制定左摆动杠杆的工工艺规程及钻12孔的夹具设计10/29 14:03 前盖板零件的工艺规程及钻8-m16深29孔的工装夹具设计10/07 08:44 加油机油枪手柄护套模具设计09/20 15:17 加热缸体注塑模设计10/07 09:17 动模底板零件的工艺规程及钻52孔的工装夹具设计10/08 20:23 包缝机机体钻孔组合机床总体及夹具设计09/21 15:19 升板机前后辅机的设计09/09 22:17 升降式止回阀的设计09/22 18:52 升降杆轴承座的夹具工艺规程及夹具设计09/09 16:41 升降杠杆轴承座零件的工艺规程及夹具设计08/30 15:59 半自动锁盖机的设计（包装机机械设计）08/30 15:57 半轴零件的机械加工工艺及夹具设计10/29 13:31 半轴零件钻6-14孔的工装夹具设计图纸09