可变分区存储管理实验报告程序设计思路和感悟

1、实验题目：可变分区存储管理一、实验目的可变分区存储管理方式是操作系统中存储管理的重要方式，其主要思想是用户作业进行连续存储，每次按照用户的请求，如果内存中有能满足用户作业大小的空闲区，就采用不同的算法分配给用户，否则，不分配，可变分区容易产生外零头。分区分配算法包括最佳适应算法、最坏适应算法、首次适应算法等。通过本实验可加深学生对存储器管理方式的把握以及分配算法的理解，并提高程序设计的能力。二、实验环境个人PC机WindowsXP操作系统 I5-2400CPU 3.10Ghz 2GB内存C-Free C语言程序设计软件三、实验的重点和难点可变分区的的收回四、实验内容利用C语言或C+语言或Jav

2、a语言实现可变分区存储管理，具体要求如下：1. 以一个一维数组模拟内存，数组类型为整型，共计1000个元素；2. 用一个单链表表示可变分区空闲表，链表每个结点表示一个空闲区，每个结点信息包括起始地址、大小。3. 分区分配算法采用最佳适应算法、首次适应算法，并将算法用函数实现。4. 自己假设几个作业，包括作业的名称、大小，进入系统的顺序。5. 初始内存中没有任何作业，随着用户输入的每一个作业的到来，动态为其分配内存。6. 使用的算法用户要能够随时更换。五、实验结果或实验代码(1) 可变式分区管理是指在处理作业过程中建立分区，使分区大小正好适合作业的需要，并且分区个数可以调整。当要装入一个作业时，

3、根据作业需要的内存量，查看是否有足够的空闲空间，若有，则按需求量分割一部分给作业；若没有，则作业等待。随着作业的装入、完成，内存空间被分割成许多大大小小的分区。有的分区被作业占用，有的分区空闲。例如，某时刻内存空间占用情况如图1所示。操作系统（10KB）作业1（10KB）空闲区2（146KB）作业4（25KB）空闲区1（20KB）作业2（45KB）图1 内存空间占用情况65K110K256K020K45K10K为了说明那些分区是空闲的，可以用来装入新作业，必须要有一张空闲区说明表，如表1所示。表1 空闲区说明表起始地址长度状态45K20K未分配110K146K未分配空表目空表目空表目其中，起始

4、地址指出个空闲区的内存起始地址，长度指出空闲区的大小。状态（未分配：该栏目记录的是有效空闲区）状态（空表目：没有登记信息）由于分区个数不定，所以空闲区说明表中应该有足够的空表目项。否则造成溢出，无法登记。同样，再设一个已分配表，记录作业或进程的内存占用情况。(2) 当有一个新作业要求装入内存时，必须查空闲区说明表，从中找出一个足够大的空闲区。有时找到的空闲区可能大于作业需求量，这时应将空闲区一分为二。一个分给作业，另外一个作为空闲区留在空闲区表中。为了尽量减少由于分割造成的碎片，尽可能分配低地址部分的空闲区，将较大空闲区留在高地址端，以利于大作业的装入。为此在空闲区表中，按空闲区首地址从低到高

5、进行登记。为了便于快速查找，要不断地对表格进行紧缩，即让“空表目”项留在表的后部。其分配框图如图2所示。开始申请XK内存J=0J=J+1查看第J个表目的登记项状态为“未分配”吗长度=XK？J为空闲区说明表的最后一个表目？置状态为“空表目”将空表目向后移长度=长度-XK始址=始址+XK登记已分配区表和空闲区表，输出系统中各数据结构的值。返回分配给作业的内存始址作业等待返回图2 首次适应算法分配框图YYNN小于大于等于(3) 当一个作业执行完成时，作业所占用的分区应归还给系统。在归还时要考虑相邻空闲区合并的问题。作业的释放区与空闲区的邻接分以下4种情况考虑：l 释放区下邻（低地址邻接）空闲区；l

6、释放区上邻（高地址邻接）空闲区；l 释放区上下都与空闲区邻接；l 释放区与空闲区不邻接。首次适应算法回收框图如图3所示。图3 首次适应算法回收框图有等待装入的作业吗？有与释放区下邻的空闲区吗？ L=L+上邻空闲区长度有与释放区下邻的空闲区吗？ 开始S=释放区始址L=释放区长度查空闲区说明表有与释放区的高地址邻接（上邻）的空闲区吗？在空闲区说明表中找一空表目登记：地址=S 长度=L状态=未分配按地址顺序调整和紧缩空闲区说明表把上邻空闲区登记栏中的状态置为“空表目”，且将空表目向后调整唤醒等待的作业并返回把上邻空闲区登记栏中的始址改为S，长度改为L把下邻空闲区登记栏中的长度改为：长度=长度+L返回

7、YYYYNNNN(4) 请按首次适应算法设计内存分配和回收程序。以表2当前使用的基础，初始化空闲区和已分配区说明表值。设计一个作业申请队列以及作业完成后的释放顺序，实现内存的分配与回收。把空闲区说明表的变化情况以及各作业的申请、释放情况显示或打印出来。表2 空闲区说明表起始地址长度状态20K 20KB180K50KB1150K100KB1300K30KB0(空表目) 600K100KB1空表目程序代码#include "iostream.h"#include "stdio.h"#include "stdlib.h"#include &

8、quot;conio.h"#define n 10 /假定系统允许的最大作业数量为n#define m 10 /假定系统允许的空闲区表最大为m#define minisize 1000structfloat address; /已分分区起始地址float length; /已分分区长度，单位为字节int flag; /已分分区表登记栏标志，用"0"表示空栏目，实验中只支持一个字符的作业名used_tablen; /已分分区表structfloat address; /空闲区起始地址float length; /空闲区长度，单位为字节int flag; /空闲区表登

9、记栏标志，用"0"表示空栏目，用"1"表示未分配free_tablem; /空闲区表int allocate(char J,float xk) /采用最有分配法分配xk大小的空间/char J;/float xk;int i,k;float ad;k=-1;for(i=0;i<m;i+) /寻找空间大于xk的最小空闲区登记项kif(free_tablei.length>=xk&&free_tablei.flag=1)if(k=-1|free_tablei.length<free_tablek.length)k=i;if(

10、k=-1) /未找到可用空闲区，返回cout<<"无可用空闲区"<<endl;return 0;/找到可用空闲区，开始分配：若空闲区大小与分配的空间差小于minisize，则空闲区全部分配：/若空闲区大小与要求分配的空间差大于minisize，则从空闲区划出一部分分配if(free_tablek.length-xk<=minisize)free_tablek.flag=0;ad=free_tablek.address;xk=free_tablek.length;elsefree_tablek.length=free_tablek.length-

11、xk;ad=free_tablek.address+free_tablek.length;/修改分配区表i=0;while(used_tablei.flag!=0&&i<n) /寻找空表目 i+; if(i>=n) cout<<"无表目填写已分分区，错误"<<endl; /修正空闲区表 if(free_tablek.flag=0) /前面找到的是整个空闲区 free_tablek.flag=1; else /前面找到的是某个空闲区的一部分 free_tablek.length=free_tablek.length+xk;

12、return 0; else used_tablei.address=ad; used_tablei.length=xk; used_tablei.flag=J; return 1;/内存分配函数结束int reclaim(char J) /回收作业名为J的作业所占内存空间/char J;int i,k,j,s,t;float S,L;/寻找已分分区表中对应登记项s=0;while(used_tables.flag!=J|used_tables.flag=0)&&s<n)s+;if(s>=n) /在已分分区表中找不到名字为J的作业cout<<"

13、找不到该作业"<<endl;return 0;/修改已分分区表used_tables.flag=0;/取得归还分区的起始地址S和长度LS=used_tables.address;L=used_tables.length;j=-1;k=-1;i=0;/寻找回收分区的上下邻空闲区，上邻表目k,下邻表目jwhile(i<m&&(j=-1|k=-1)if(free_tablei.flag=0)if(free_tablei.address+free_tablei.length=S)k=i; /找到上邻if(free_tablei.address=S+L)j=i

14、; /找到下邻i+;if(k!=-1)if(j!=-1) /上邻空闲区，下邻空闲区，三项合并free_tablek.length=free_tablej.length+free_tablek.length+L;free_tablej.flag=0;else /上邻空闲区，下邻非空闲区，与上邻合并free_tablek.length=free_tablek.length+L;elseif(j!=-1) /上邻非空闲区，下邻为空闲区，与下邻合并free_tablej.address=S;free_tablej.length=free_tablej.length+L;else /上下邻均为非空闲区，

15、回收区域直接填入 /在空闲区表中寻找空栏目t=0;while(free_tablet.flag=1&&t<m)t+;if(t>=m) /空闲区表满，回收空间失败，将已分分区表复原cout<<"内存空闲表没有空间，回收空间失败"<<endl;used_tables.flag=J;return 0;free_tablet.address=S;free_tablet.length=L;free_tablet.flag=1;return 1; /内存归还函数结束void main()int i,a;float xk;char J;

16、 /空闲区表初始化free_table0.address=10240;free_table0.length=102400;free_table0.flag=1;for(i=1;i<m;i+)free_tablei.flag=0; /已分分区表初始化for(i=0;i<n;i+)used_tablei.flag=0;while(1)cout<<"选择功能项(0-推出，1-分配内存，2-回收内存，3-显示内存)"<<endl;cout<<"选择功项(03):"cin>>a;switch(a)case

17、 0: exit(0); /a=0程序结束case 1: /a=1 分配内存空间cout<<"输入作业名J和作业所需长度xk："cin>>J>>xk;allocate(J,xk); /分配内存空间break;case 2: /a=2回收内存空间cout<<"输入要回收分区的作业名"cin>>J;reclaim(J); /回收内存空间case 3: /a=3显示内存情况，输出空闲区表和已分分区表cout<<"输出空闲区表："<<endl;cout<

18、<" 起始地址 分区长度 标志"<<endl;for(i=0;i<m;i+)cout<<free_tablei.address<<free_tablei.length<<free_tablei.flag<<endl;cout<<"按任意键，输出已分分区表"<<endl;getch();cout<<"输出已分分区表："<<endl;cout<<" 起始地址 分区长度 标志"<<endl;for(i=0;i<n;i+)if(used_tablei.flag!=0)cout<<used_tablei.a