操作系统课程设计动态分区分配存储管理

1、冬芯N帝火子操作系统课程设计设动态分区分配存储管理学生姓名 吕霆学 号专业班级 计算机10-01班指导教师第一章课程设计概述1.1设计任务：动态分区分配存储管理1.2设计要求建立描述内存分配状况的数据结构；建立描述进程的数据结构；使用两种方式产生进程：（a）自动产生，（b）手工输入；在屏幕上显示内存的分配状况、每个进程的执行情况；建立分区的分配与回收算法，支持紧凑算法；时间的流逝可用下面几种方法模拟：（a）按键盘，每按一次可认为过一个时间单位；（b）响应 WM_TIMER；将一批进程的执行情况存入磁盘文件，以后可以读出并重放；支持算法：首次适应算法、循环首次适应算法、最佳适应算法：最坏适应算法

2、。1.3设计目的旨在让我们更好的了解动态分区管理方面的知识.第二章原理及算法描述2-1动态分区分配算法原理首次适应算法*算法概述：分配内存时，从链首开始顺序查找，找到满足的空闲分区则划出空 间分配，余下的空闲空间仍保留在空闲链表中*实现方法：分配时从数组第一个元素开始比较，若符合条件则将该元素减去对 应作业的值循环首次适应算法*算法概述：由首次适应算法演变，只是每次分配改为由上一次找到的空闲分区 开始查找*实现方法：在首次适应算法的基础上增加一个值用于记录找到的空闲分区的位最佳适应算法*算法概述：每次为作业分配内存时，总是把能满足要求、又是最小的空闲分区分配给作业*实现方法：我们决定每次分配先

3、把空闲分区按从小到大的顺序排列，然后将第 一个匹配分区分配给作业最坏适应算法*算法概述：每次为作业分配内存时，总是挑选一个最大的空闲分区分割给作业 使用*实现方法：算法与最佳适应算法几乎相同，仅在排序时把空闲分区表按从大到 小的顺序排列，所以未作详细注释回收分区当进程运行完毕释放内存时，系统根据回收区的首址，从空闲区链（表）中找到相应的插入 点,此时可能出现以下四种情况之一；1）回收区与插入点的前一个空闲分区F1相邻接，此时应将回收区与插入点的前一分 区合并，不必为回收区分配新表项，而只需修改其前一分区F1的大小.2）回收分区与插入点的后一空闲分区F2相邻接，此时也可将两分区合并，形成新的 空

4、闲分区，但用回收区的首址作为新空闲区的首址，大小为两者之和.3）回收区同时与插入点的前，后两个分区邻接,此时将三个分区合并，使用F1的表项 和F1的首址，取消F2的表项，大小为三者之和.4）回收区既不与F1相邻接，又不与F2邻接.这时应为回收区单独建立一新表项，填 写回收区的首址和大小，并根据其首址插入到空闲链中的适当位置.紧凑算法通过移动内存中的作业的位置,以把原来多个分散的小分区拼接成一个大分区的方法.第三章开发环境此程序是本人利用C+语言在VS2012的开发环境中实现的第四章程序实现一数据结构#include #include #include using namespace std;o

5、fstream stream;/输出流对象int ary1204;/内存分配状态int ary2203;/空闲分区状态int ary310;/进程分配状态int recycle;/需要回收的盘块序号 int idl;/算法选择号int m;/内存区数int n;/空闲区数int q;/进程数int r=0;/循环首次适应算法：对应的这次查找到的空闲分区序号/打印输出函数void vision()int i;int j;if(id1=1)stream.open(first_fit.txt”, ios:app);if(id1=2)stream.open(nextfirst_fit.txt”, io

6、s:app);if(id1=3)stream.open(best_fit.txt”,ios:app);if(id1=4)stream.open(worst_fit.txt”, ios:app);if(id1=5)stream.open(compact.txt”,ios:app);if(id1=6)stream.open(huishou.txt”,ios:app);cout1内存分配状态endl;cout分区号大小/KB 始址/KB 状态endl;stream1内存分配状态endl;stream ”分区号大小/KB 始址/KB 状态endl;for(j=0;jm;j+) TOC o 1-5 h

7、z cout ary1j0;streamary1j0;cout ary1j1;streamary1j1;cout ary1j2;streamary1j2;if(ary1j3=2)cout巳分配；stream巳分配;elsecout未分配；stream未分配；cout endl;streamendl;cout endl;cout空闲分区链endl;cout分区号大小/KB起址/KBendl;stream”空闲分区链endl;stream分区号大小/KB 起址/KBendl; for(i=0;in;i+) TOC o 1-5 h z coutary2i0”;streamary2i0;coutary

8、2i1”;streamary2i1;coutary2i2;streamary2i2;coutendl;streamendl;coutendl;streamendl;coutendl;stream.close();/作业信息的自动产生void create_pro()int i;for(i=0;iq;i+)ary3i=rand()%100;if(ary3i=0)i-;ary30=42;ary31=86;cout产生q”个随机进程endl;cout大小分别是:；for(i=0;iq;i+)cout”ary3i”;cout endl;作业的手动生成void create_zuoye()int j;i

9、nt choice2;int id3=rand()%10;m=id3;/内存区数量coutchoice2;q=choice2;cout输入想创建的作业请求大小endl;for(int i=0;ij;ary3i=j;cout你创建了 choice2个进程;for(int i=0;ichoice2;i+)coutary3i”;coutendl;/内存信息的自动产生void create_apply()int i;for (i=0;im;i+)ary1i0=i+1;ary1i1=rand()%100;if(i=0)ary1i2=0;elseary1i2=ary1i-12+ary1i-11;ary1i

10、3=rand()%3;/cout iendl;if(ary1i1=0)i-;int k=0;/空闲区数量for (i=0;im;i+)if(ary1i3!=2)ary2k0=ary1i0;ary2k1=ary1i1;ary2k2=ary1i2;k+;n=k;/空闲块数量/内存信息的手动生成int create_fenqu()int k,x,y,o=0;int a=0;coutk;cout输入k”个内存分区块大小endl;for(int i=0;ix;ary1i1=x;/大小cout输入内存块的分配状态endl;for(int i=0;iy;if(y=2)n+;ary1i3=y;/状态ary10

11、2=0;ary112=ary101;for(int i=2;ik;i+)ary1i2=ary1i-12+ary1i-11;/起始地址m=k;for (int i=0;ik;i+)if(ary1i3!=2)ary2a0=ary1i0;ary2a1=ary1i1;ary2a2=ary1i2;a+;n=a;return m,n;/首次适应算法void first_fit()vision();int i;int j;int k;int l;int d;/用来保存第k个的值int id2=0;for(i=0;iq;i+)/为每个进程分配空间for(j=0;j=ary3i)/进程占用空间小于等于其中一个空

12、闲区的大小cout”ary3i与”ary2j1相匹配endl;stream.open(first_fit.txt”, ios:app);stream”ary3i与”ary2j1相匹配endl;stream.close();if(ary2j1=ary3i)/进程占用空间等于其中一个空闲区块大小ary1ary2j0-13=2;for(k=j+1;kary2j0+1;k)ary1k-10=ary1k-20+1;ary1k-11=ary1k-21;ary1k-12=ary1k-22;ary1k-13=ary1k-23;l=ary2j0;ary1l0=l+1;ary1l1=d-ary3i;ary1l2=

13、ary1l-11+ary1l-12;ary1l3=0;k=0;for(id2=0;id2m;id2+)if(ary1id23!=2)ary2k0=ary1id20;ary2k1=ary1id21;ary2k2=ary1id22;k+;n=k;break;elsecout”ary3i与”ary2j1不匹配endl;stream.open(first_fit.txt”, ios:app);stream”ary3i与”ary2j1不匹配endl; stream.close();vision();首次循环适应算法void next_fit()vision();int i;int j;int k;int

14、 s;int d;int id2;for(i=0;iq;i+)/对每一个进程队列中的进程分配资源for(j=r;jn;j+)if(ary3i=ary2j1)cout”ary3i与”ary2j1相匹配endl;stream.open(nextfirst_fit.txt”, ios:app);stream”ary3i与”ary2j1相匹配endl;stream.close();if(ary3i=ary2j1)/-改变内存分配-k=ary2j0;/得到对应空闲块对应内存块的序号k-;ary1k3=2;/把对应内存块标志位上改成巳分配/-改变空闲块表：把从这块空闲块以下的所有空闲块向上移一格一n-;f

15、or(k=j;kk;s-)ary1s0=ary1s-10+1;ary1s1=ary1s-11;ary1s2=ary1s-12;ary1s3=ary1s-13;/改变第k+1块内容：对应的数组是ary1kary1k0=ary1k-10+1;ary1k1=d-ary1k-11;ary1k2=ary1k-11+ary1k-12;/改变空闲表分配情况一一k=0;for(id2=0;id2m;id2+)if(ary1id23!=2)ary2k0=ary1id20;ary2k1=ary1id21;ary2k2=ary1id22;k+;n=k;/vision();break;elsecout”ary3i与”

16、ary2j1不匹配endl;stream.open(nextfirst_fit.txt”, ios:app);stream”ary3i与”ary2j1不匹配endl; stream.close();思路：先把空闲列表检索一遍，选出最佳答案，进行分配void best_fit()/最佳算法一按顺序检索，把与进程要求内存大小最接近的快分配给进程int i;int s;int j=-9999;/用来保存最接近的答案int e;/用来存放进行比较时的中间结果int k;int 1:int d;int id2:vision ();for(i=0;iq;i+)e=9999;j=-9999;for(s=0;

17、s=ary3i)&(eary2s 1)/满足分配要求e=ary2 s 1;j=s；if(j0)cout，ary3i”与所有空闲盘块不匹配”endl;stream, open(best_fit. txt”, ios: :app);stream，ary3 i”与所有空闲盘块不匹配”endl;stream, close (); elsecout，ary3i”与 ”ary2 j 1”最佳相匹配”endl; stream, open(best_fit. txt”, ios:app);stream，/ ，ary3 i”与 ，ary2 j 1”最佳相匹配”endl;stream, close ();if(a

18、ry2jl=ary3 i)k=ary2j0;arylkl3=2;for (l=k;lary2j0+1;l)ary1l-10=ary1l-20+1;ary1l-11=ary1l-21;ary1l-12=ary1l-22;ary1l-13=ary1l-23;k=ary2j0;ary1k0=k+1;ary1k1=d-ary1k-11;ary1k2=ary1k-11+ary1k-12;ary1k3=0;k=0;for(id2=0;id2m;id2+)if(ary1id23!=2)ary2k0=ary1id20;ary2k1=ary1id21;ary2k2=ary1id22;k+;n=k;for(k=j

19、+1;kn;k+)ary2k0+;vision(); /最坏适应算法 void worst_fit() int s:int j=-9999;/用来保存最接近的答案int e=-9999; 用来存放进行比较时的中间结果int k;int 1:int d;int id2:vision ();for(i=0;iq;i+)j=-9999;e=-9999;for (s=0;s=ary3 i)&(eary2s 1)/满足分配要求e=ary2s1;j=s;if(j0)cout，ary3i”与所有空闲盘块不匹配”endl;stream, open(worst_fit. txt”, ios:app);strea

20、m，ary3 i”与所有空闲盘块不匹配”endl;stream, close (); elsecout，,，ary3i”与 ”ary2 j 1最差相匹配，endl; stream, open(worst_fit. txt”, ios:app);stream，, ，ary3 i”与 ，ary2 j 1最差相匹配”endl;stream, close ();if(ary2jl=ary3 i)k=ary2j 0;arylk-l3=2;for (l=k;lary2j0+1;l)ary1l-10=ary1l-20+1;ary1l-11=ary1l-21;ary1l-12=ary1l-22;ary1l-1

21、3=ary1l-23;k=ary2j0;ary1k0=k+1;ary1k1=d-ary1k-11;ary1k2=ary1k-11+ary1k-12;ary1k3=0;k=0;for(id2=0;id2m;id2+)if(ary1id23!=2)ary2k0=ary1id20;ary2k1=ary1id21;ary2k2=ary1id22;k+;n=k;for(k=j+1;kn;k+)ary2k0+;vision();回收内存算法：/*有共计八种情况，1. (1)回收区上邻接着空闲盘块，下连接着巳分配盘块回收区下邻接着空闲盘块，上邻接着巳分配盘块回收区上下连接的都是空闲盘块空闲区上下邻接的都是巳

22、分配盘块要回收的盘块就是第一个盘块，并且向下邻接着空闲盘块要回收的盘块就是第一个盘块，但是向下邻接着巳分配盘块要回收的盘块就是最后一个盘块，并且向上邻接的是空闲盘块要回收的盘块就是最后一个盘块，但是向上邻接的是巳分配盘块*/void apply_recycle()int i;int j;int k;if(m=1)ary103=0;n+;ary200=1;ary201=ary101;ary202=ary102;vision();elseif(recycle=1) /coutary1if(ary113!=2)cout要回收的盘块就是第一个盘块，并且向下邻接着空闲盘块endl;stream.open

23、(huishou.txt”, ios:app);stream 要回收的盘块就是第一个盘块，并且向下邻接着空闲盘块endl; stream.close();ary101=ary101+ary111;ary103=0;for(i=1;im;i+)ary1i0=ary1i+10-1;ary1i1=ary1i+11;ary1i2=ary1i+12;ary1i3=ary1i+13;/coutary1i3ary1i3endl;m;/ coutk=0;vision();/coutary103ary103endl;/coutary113ary113endl;/coutary123ary123endl;/cou

24、tary133ary133endl;for(j=0;jm;j+)coutary1j3ary1j3endl;if(ary1j3!=2)ary2k0=ary1j0;ary2k1=ary1j1;ary2k2=ary1j2;k+;n=k;vision();elsecout要回收的盘块就是第一个盘块，但是向下邻接着巳分配盘块endl;stream.open(huishou.txt”, ios:app);stream要回收的盘块就是第一个盘块，但是向下邻接着巳分配盘块endl; stream.close();ary103=0;k=0;for(j=0;jm;j+)/coutary1j3ary1j3endl;

25、if(ary1j3!=2)ary2k0=ary1j0;ary2k1=ary1j1; ary2k2=ary1j2;k+;n=k;vision();else if(recycle=m)if(ary1recycle-23!=2)cout要回收的盘块就是最后一个盘块，并且向上邻接的是空闲盘块endl;stream.open(huishou.txt”, ios:app);stream要回收的盘块就是最后一个盘块，并且向上邻接的是空闲盘块endl; stream.close();ary1recycle-23=0;ary1recycle-21=ary1recycle-21+ary1recycle-11;m-

26、;k=0;for(j=0;jm;j+)/coutary1j3ary1j3endl;if(ary1j3!=2)ary2k0=ary1j0;ary2k1=ary1j1;ary2k2=ary1j2;k+;n=k;vision();elsecout要回收的盘块就是最后一个盘块，但是向上邻接的是巳分配盘块endl;stream.open(huishou.txt”, ios:app);stream要回收的盘块就是最后一个盘块，但是向上邻接的是巳分配盘块endl; stream.close();ary1recycle-13=0;k=0;for(j=0;jm;j+)/coutary1j3ary1j3endl;

27、if(ary1j3!=2)ary2k0=ary1j0;ary2k1=ary1j1;ary2k2=ary1j2;k+;n=k;vision();else/剩下比较复杂的四种情况if(ary1recycle-23!=2)&(ary1recycle3=2)/回收区上邻接着空闲盘块，下连接着 巳分配盘块cout”回收区上邻接着空闲盘块，下连接着巳分配盘块endl;stream.open(huishou.txt”, ios:app);stream回收区上邻接着空闲盘块，下连接着巳分配盘块endl;stream.close();ary1recycle-21=ary1recycle-21+ary1recyc

28、le-11;for(i=recycle-1;im;i+)ary1i0=ary1i+10-1;ary1i1=ary1i+11;ary1i2=ary1i+12;ary1i3=ary1i+13;m-;k=0;for(j=0;jm;j+)/coutary1j3ary1j3endl;if(ary1j3!=2)ary2k0=ary1j0;ary2k1=ary1j1;ary2k2=ary1j2;k+;n=k;vision();if(ary1recycle3!=2)&(ary1recycle-23=2)/回收区下邻接着空闲盘块，上邻接着 巳分配盘块cout”回收区下邻接着空闲盘块，上邻接着巳分配盘块endl;

29、stream.open(huishou.txt”, ios:app);stream回收区下邻接着空闲盘块，上邻接着巳分配盘块endl;stream.close();ary1recycle-23=0;ary1recycle-21=ary1recycle-21+ary1recycle-11;for(i=recycle-1;im;i+)ary1i0=ary1i+10-1;ary1i1=ary1i+11;ary1i2=ary1i+12;ary1i3=ary1i+13;m-;k=0;for(j=0;jm;j+)/coutary1j3ary1j3endl;if(ary1j3!=2)ary2k0=ary1j

30、0;ary2k1=ary1j1;ary2k2=ary1j2;k+;n=k;vision();if(ary1recycle-23!=2)&(ary1recycle3!=2)/ 回收区上下连接的都是空闲盘块cout回收区上下连接的都是空闲盘块endl;stream.open(huishou.txt”, ios:app);stream回收区下邻接着空闲盘块，上邻接着巳分配盘块endl;stream.close();ary1recycle-21=ary1recycle-21+ary1recycle-11+ary1recycle1;cout回收区上下连接的都是空闲盘块endl;coutrecycle-2

31、endl;for(i=recycle+1;im;i+)ary1recycle-10=ary1recycle+10-2;ary1recycle-11=ary1recycle+11;ary1recycle-12=ary1recycle+12;ary1recycle-13=ary1recycle+13;m=m-2;k=0;for(j=0;jm;j+)/coutary1j3ary1j3endl;if(ary1j3!=2)ary2k0=ary1j0;ary2k1=ary1j1;ary2k2=ary1j2;k+;n=k;vision();if(ary1recycle-23=2)&(ary1recycle3

32、=2)/空闲区上下邻接的都是巳分配盘块ary1recycle-13=0;k=0;for(j=0;jm;j+)/coutary1j3ary1j3endl;if(ary1j3!=2)ary2k0=ary1j0;ary2k1=ary1j1;ary2k2=ary1j2;k+;n=k;vision();紧凑算法void compact()int id1=0;/记录巳经分配的内存数量int id2;/循环量int num_avl;/记录空闲盘块数量int sum_avl=0;/总共空闲区大小int num_apl=0;统计总共空闲区有多大vision();for(id2=0;id2n;id2+)sum_a

33、vl=sum_avl+ary2id21;for(id2=0;id2m;id2+)if(ary1id23=2)ary1num_apl0=num_apl+1;ary1num_apl1=ary1id21;if(num_apl=0)ary1num_apl2=0;elseary1num_apl2=ary1num_apl-11+ary1num_apl-12;ary1num_apl3=2;num_apl+;/coutnum_aplnum_aplendl;最后一块空闲块ary1num_apl0=num_apl+1;ary1num_apl1=sum_avl;ary1num_apl2=ary1num_apl-11