操作系统原理课程设计报告-可变分区存储管理

1、.上海电力学院课程设计报告课程名称： 操作系统原理 题目名称： 可变分区存储管理 姓 名： 李鑫 学 号： 20103277 班 级： 2010251 同 组 姓 名： 无 课程设计时间： 2013.1.72013.1.11 评 语： 成 绩： 课程设计题目一、设计内容及要求 （要求注明小组分工情况）设计内容：可变分区存储管理。设计一个可变分区存储管理方案，模拟实现：主存的分配和回收，地址变换。输入：（1） 输入进程名称及使用内存的大小（创建进程）；（2） 结束某一个指定的进程。（3） 逻辑地址。输出：显示内存使用状况；每一个进程占据的内存；物理地址。使用的分配算法包括：（1）首次适应算法；（

2、2）最佳适应算法；（3）最差适应算法；二、详细设计1）原理概述内存分配有固定分区分配方式和动态分区分配方式，固定分区分配是最简单的一种可以运行多道程序的存储管理方式。它是将内存空间划分为若干个固定大小的区域，在每个分区中只装入一道作业，它把用户空间划分为几个分区，允许有多道作业并发运行。它的分区划分方法有两种：1、分区大小相等，即使所有的内存分区大小相同。2、分区大小不等。它的分配方式存在缺点，即缺乏灵活性，浪费内存，如果一个进程申请很少的一块内存，那么它会占据整个内存分区，即使还有大部分空闲，例如一个进程有5k，申请了分区号4的内存，虽然还有123k内存，但是其他进程也不可以利用，只有进程结

3、束了，其他进程才可以利用，内存十分浪费。分区号起始地址大小状态12012已分配23232已分配36464已分配4128128未分配在上边的基础上，便产生了可变分区分配方式。它是根据进程的实际需要，动态的为它分配内存空间，避免了上边的固定分区分配方式的缺点。它涉及到分区分配中所用的数据结构、分区分配算法和分区的分配与回收操作这三个问题。1、 分区分配中的数据结构在这里我使用了空闲分区表。在系统中设置一张空闲分区表，用于记录每个空闲分区的情况。每个空闲分区占一个表目，表中包括了分区号、分区始址、分区大小、和一个代表它是空闲的状态。在系统中还有一张已分配表，用于记录已经分配给相应进程的内存，它的表目

4、与空闲分区表一样，状态是已分配。2、 分区分配算法A首次适应算法(first fit)每次分配时，总是从未分配区表头顺序查找未分配表或链表，找到第一个能满足长度要求的空闲区为止。分割这个找到的未分配区，一部分分配给作业，另一部分仍为空闲区。这种分配算法优先利用主存低地址空闲分区，从而，保留了高地址的大的空闲区。但由于低地址空闲分区不断被分割，既可能将大的空间分割掉，也造成低地址部分有较多难以使用的“碎片”。作为改进，可把空闲区按地址从小到大排列在未分配表或链表中，因为，为作业分配主存空间时从低地址部分的空闲区开始查找，可使高地址部分尽可能少用，以保持一个大的空闲区，有利于大作业的装入。但是，这

5、给回收分区带来一些麻烦，每次收回一个分区后，必须搜索未分配区表或链表来确定它在表格或链表中的位置且要移动相应的登记项。B最佳适应算法(best fit)该算法要扫描整个未分配区表或链表，从空闲区中挑选一个能满足作业要求的最小分区进行分配。这种算法可保证不去分割一个更大的区域，使装入大作业时比较容易得到满足。采用这种分配算法时可把空闲区按长度以递增顺利排列，查找时总是从最小的一个区开始，直到找到一个满足要求的分区为止。按这种方法，在回收一个分区时也必须对分配表或链表重新排列。最优适应分配算法找出的分区如果正好满足要求则是最合适的了，如果比所要求的略大则分割后使剩下的空闲区就很小，以致无法使用。C

6、最坏适应算法(worst fit)最坏适应分配算法要扫描整个未分配区表或链表，总是挑选一个最大的空闲区分割给作业使用，其优点是可使剩下的空闲区不至于太小，对中、小作业有利。采用这种分配算法时可把空闲区按长度以递减顺序排列，查找时只要看第一个分区能否满足作业要求，这样使最坏适应分配算法查找效率很高。3、 分区分配操作它主要涉及到分区的分配内存和回收内存问题。A分配内存B回收内存内存回收有四种回收状态状态，比较复杂点。如下图：X为将要回收的内存，A、B为正在运行的进程，回收X有四种合并状态。黑色区域为回收后的空闲内存。2）主要数据结构定义了内存分区结构体，在此基础上定义了此结构体的对象free10

7、0和used100，分别表示空闲分区表和已分配的分区表，他们的最大值都是100，而且结构也相同。Procnum是全局变量，用于已分配的进程分区号，每个进程唯一。struct table int tablenum;/分区号int startaddr;/起始地址int length;/长度char state10;/分配状态;table free100;/空闲分区表table used100;/已分配分区表int freelength;/空闲分区表长度int usedlength;/已分配分区表长度int procnum=0;/进程分区号3）算法（流程图）可变分区存储管理系统显示内存空闲表和已分配

8、表的状态1创建进程进程名首次适应算法最佳适应算法最差适应算法2结束进程3地址转换逻辑地址到物理地址4退出 程序状态流程图从头开始查找空闲分区表解锁完毕？返回空闲>进程请求YN继续解锁下一个表项NY从该分区中划出进程请求的大小的内存空间将该分区分配各请求的进程修改相应的数据结构、空闲分区表、已分配分区表返回 内存分配流程图4）源程序文件名os课程设计1#include<iostream.h>#include <string.h>struct table int tablenum;/分区号int startaddr;/起始地址int length;/长度char st

9、ate10;/分配状态;table free100;/空闲分区表table used100;/已分配分区表int freelength;/空闲分区表长度int usedlength;/已分配分区表长度int procnum=0;/进程分区号void initial();/初始化分区void firstfit();/首次适应算法void bestfit();/最佳适应算法void worstfit();/最坏适应算法void terminal();/结束进程int transfer();/逻辑地址转换void print();/打印输出int main()cout<<"/可

10、变分区存储管理系统/"<<endl;initial();int s,n,x=1;print();while(x)cout<<"/"<<endl;cout<<"-1、创建进程（进程名 内存大小）；"<<endl<<"-2、结束进程（进程名）；"<<endl<<"-3、逻辑地址转换；"<<endl<<"-4、退出"<<endl<<"-&g

11、t;"cin>>n;switch (n)case 1:cout<<"-使用算法1、首次适应算法；2、最佳适应算法；3、最差适应算法"<<endl<<"->"cin>>s;switch (s)case 1:firstfit();break;case 2:bestfit();break;case 3:worstfit();break;print();break;case 2:terminal();print();break;case 3:transfer();break;case 4

12、:x=0;break;return 0;void initial()for (int i=0;i<100;i+)freei.tablenum=-1;freei.startaddr=-1;freei.length=0;strcpy(freei.state,"free ");usedi.tablenum=-1;usedi.startaddr=-1;usedi.length=0;strcpy(usedi.state,"used ");freelength=0;usedlength=0;free0.tablenum=0;free0.startaddr=0;

13、free0.length=50;free1.tablenum=1;free1.startaddr=50;free1.length=100;free2.tablenum=2;free2.startaddr=150;free2.length=80;free3.tablenum=3;free3.startaddr=230;free3.length=40;free4.tablenum=4;free4.startaddr=270;free4.length=200;free5.tablenum=5;free5.startaddr=470;free5.length=150;freelength=6;void

14、 print()cout<<"/"<<endl;cout<<"空闲分区表："<<endl<<"分区号/起始地址/大小/状态"<<endl;for (int i=0;i<freelength;i+)cout<<freei.tablenum<<'t'<<freei.startaddr<<'t'<<freei.length<<'t'<<

15、;freei.state<<endl;cout<<"已分配分区表："<<endl<<"分区号/起始地址/大小/状态"<<endl;for (i=0;i<usedlength;i+)cout<<usedi.tablenum<<'t'<<usedi.startaddr<<'t'<<usedi.length<<'t'<<usedi.state<<endl

16、;cout<<"/"<<endl;int transfer()int m;cout<<"输入要转换的分区号："<<endl<<"->"cin>>m;for (int i=0;i<usedlength;i+)if (usedi.tablenum=m)cout<<m<<"->(物理地址)"<<usedi.startaddr<<endl;return 1;cout<<&qu

17、ot;逻辑分区号输入错误。"<<endl;return 0;void firstfit()char procname20;int proclength;int i,j,flag,t;cout<<"输入进程的名称和大小:"<<endl<<"->" cin>>procname; cin>>proclength;for(i=0;i<freelength;i+) if(freei.length>=proclength) flag=1; if(flag=0) cou

18、t<<endl<<"无满足要求的空闲内存,请稍候再试"<<endl; else t=0; i=0; while(t=0) if(freei.length>=proclength) t=1; i+; i-; usedusedlength.startaddr=freei.startaddr; strcat(usedusedlength.state,procname); usedusedlength.length=proclength; usedusedlength.tablenum=procnum;usedlength+;procnum

19、+;if(freei.length>proclength) /空闲区域大于申请的区域freei.startaddr+=proclength; freei.length-=proclength; else /空闲区域等于申请的区域for(j=i;j<freelength-1;j+) freej=freej+1; freelength-; cout<<"内存空间分配成功"<<endl; void bestfit()/int procnum=0;char procname20;int proclength;int i,j,flag,t;cout

20、<<"输入进程的名称和大小:"<<endl<<"->" cin>>procname; cin>>proclength;flag=0; for(i=0;i<freelength;i+) if(freei.length>=proclength) flag=1; if(flag=0) cout<<endl<<"无满足要求的空闲内存,请稍候再试"<<endl; else t=0; i=0; while(t=0) if(freei.

21、length>=proclength) t=1; i+; i-; for(j=0;j<freelength;j+) if(freej.length>=proclength)&&(freej.length<freei.length) i=j; usedusedlength.startaddr=freei.startaddr; strcat(usedusedlength.state,procname); usedusedlength.length=proclength;usedusedlength.tablenum=procnum;usedlength+;

22、procnum+;if(freei.length>proclength) freei.startaddr+=proclength; freei.length-=proclength; else for(j=i;j<freelength-1;j+) freej=freej+1; freelength-; cout<<"内存空间分配成功"<<endl;void worstfit()/int procnum=0;char procname20;int proclength;int i,j,flag,t;cout<<"输入进

23、程的名称和大小:"<<endl<<"->" cin>>procname; cin>>proclength;flag=0; for(i=0;i<freelength;i+) if(freei.length>=proclength) flag=1; if(flag=0) cout<<endl<<"无满足要求的空闲内存,请稍候再试"<<endl; else t=0; i=0; while(t=0) if(freei.length>=procle

24、ngth) t=1; i+; i-; for(j=0;j<freelength;j+) if(freej.length>=proclength)&&(freej.length>freei.length) i=j; usedusedlength.startaddr=freei.startaddr; strcat(usedusedlength.state,procname); usedusedlength.length=proclength; usedusedlength.tablenum=procnum;usedlength+; procnum+;if(free

25、i.length>proclength) freei.startaddr+=proclength; freei.length-=proclength; else for(j=i;j<freelength-1;j+) freej=freej+1; freelength-; cout<<"内存空间分配成功"<<endl; void terminal()char procname20;int proclength;int i,j,flag,p=0;int start; int length;cout<<"输入要结束的进程名:"<<endl<<"->" cin>>procname;char buffer20;strcpy(buffer,"used ");strcat(buffer,procname);flag=-1; for(i=0;i<usedlength;i+) /寻找指定名称的作业if(!strcmp(u