实验2：存储器的分配与回收.doc

实验报告学院（系）名称：计算机与通信工程学院姓名学号专业班级实验项目实验二：存储器的分配与回收算法实现课程名称操作系统课程代码0668036实验时间实验地点批改意见成绩教师签字： 实验内容：1. 模拟操作系统的主存分配，运用可变分区的存储管理算法设计主存分配和回收程序，并不实际启动装入作业。2. 采用最先适应法、最佳适应法、最坏适应法分配主存空间。3. 当一个新作业要求装入主存时，必须查空闲区表，从中找出一个足够大的空闲区。若找到的空闲区大于作业需要量，这是应把它分成二部分，一部分为占用区，加一部分又成为一个空闲区。4. 当一个作业撤离时，归还的区域如果与其他空闲区相邻，则应合并成一个较大的空闲区，登在空闲区表中。5. 运行所设计的程序，输出有关数据结构表项的变化和内存的当前状态。实验要求：1 详细描述实验设计思想、程序结构及各模块设计思路；2 详细描述程序所用数据结构及算法；3 明确给出测试用例和实验结果；4 为增加程序可读性，在程序中进行适当注释说明；5 认真进行实验总结，包括：设计中遇到的问题、解决方法与收获等；6 实验报告撰写要求结构清晰、描述准确逻辑性强；7 实验过程中，同学之间可以进行讨论互相提高，但绝对禁止抄袭。【实验过程记录（源程序、测试用例、测试结果及心得体会等）】#includeusing namespace std;typedef struct Ramtable/内存表 结构体 int use;/是否被占用，=0未被占用，=1被占用 Ramtable;typedef struct FreeRamtable /空闲地址登记表 结构体 int FreeRamSize;/空闲占用内存大小 int FreeStartAdd;/空闲起始地址 int FreeEndAdd;/空闲结束地址 int FreeNumber;/按照顺序的空闲分区编号（由地址的从前到后） FreeRamtable;typedef struct UsedRamtable /已分配区地址登记表 结构体 int UsedRamSize;/已分配区地址占用大小 int UsedStartAdd;/已分配区起始地址 int UsedEndAdd;/已分配区结束地址 int UsedNumber;/按照作业占用的内存起始地址顺序的排序编号 string WorkName;/作业名称 UsedRamtable; Ramtable Ram100=0;/内存表 FreeRamtable FreeRam51;/空闲地址登记表UsedRamtable UsedRam100;/已分配区地址登记表int WorkNumber=0;/当前作业数 注意：全局变量只能计算一次，再次计算需先置零 int FreeWorkNumber=0;/当前空闲区数 注意：全局变量只能计算一次，再次计算需先置零int Choose;/选择三种算法的一种 string name;/作业的名字 int WorkSize;/作业所占内存大小 void CountWorkNumber()/计算当前作业数for(int i=0;i100;i+)if(UsedRami.WorkName=)break;elseWorkNumber+;void CountFreeWorkNumber()for(int i=0;i51;i+)if(FreeRami.FreeStartAdd!=-1)FreeWorkNumber+;elsebreak;void InitWorkName()/初始化已分配内存登记表的第一个记录，使其名字为空，方便计算 UsedRam0.WorkName=;FreeRam0.FreeRamSize=100;FreeRam0.FreeStartAdd=0;FreeRam0.FreeEndAdd=99;FreeRam1.FreeStartAdd=-1;void GetWork()coutnameWorkSize;coutEnter 1 using Quick arithmeticendl;coutEnter 2 using Best arithmeticendl;coutChoose;coutendl;int Quick()/最先适应算法 int i;for(i=0;i=WorkSize)break;if(i=51)coutERROR! No Enough FreeRam Lefe!endl;return -1;/找不到合适的空间时返回-1，方便进行下一步操作 return i;/返回值是指示第几个空闲区的下标 int Best()/最佳适应算法 int temp=-1;for(int i=0;i=WorkSize)if(tempFreeRami.FreeRamSize)temp=i;if(temp0)coutERROR! No Enough FreeRam Lefe!endl;return -1;return temp;int Worst()/最坏适应算法 int temp=-1;for(int i=0;i=WorkSize)if(temp0)temp=i;elseif(FreeRamtemp.FreeRamSizeFreeRami.FreeRamSize)temp=i;if(temp0)coutERROR! No Enough FreeRam Lefe!endl;return -1;return temp;void Moldification()WorkNumber=0;CountWorkNumber();for(int i=0;iWorkNumber;i+)for(int j=UsedRami.UsedStartAdd;j=UsedRami.UsedEndAdd;j+)Ramj.use=1;void Insert()int i;int k;/找到要插入的作业的所在已分配表中的位置WorkNumber=0;FreeWorkNumber=0;CountWorkNumber();/计算此时的作业数 CountFreeWorkNumber();/计算此时的空闲区数 if(Choose=1)i=Quick();for(int j=0;j100;j+)if(WorkNumber!=0)/这种情况可能会使k=0，在第一个作业的开始地址比较靠后，且前面是空闲分区 if(UsedRamj.WorkName=)/这个没有登记作业 k=j;break;else if(FreeRami.FreeEndAddk;j-)UsedRamj.UsedRamSize=UsedRamj-1.UsedRamSize;UsedRamj.UsedStartAdd=UsedRamj-1.UsedStartAdd;UsedRamj.UsedEndAdd=UsedRamj-1.UsedEndAdd;UsedRamj.WorkName=UsedRamj-1.WorkName;UsedRamk.UsedStartAdd=FreeRami.FreeStartAdd;UsedRamk.UsedEndAdd=FreeRami.FreeStartAdd+WorkSize-1;UsedRamk.UsedRamSize=WorkSize;UsedRamk.WorkName=name;UsedRamWorkNumber+1.WorkName=;if(FreeRami.FreeRamSizeWorkSize)FreeRami.FreeStartAdd=UsedRamk.UsedEndAdd+1;FreeRami.FreeRamSize=FreeRami.FreeEndAdd-FreeRami.FreeStartAdd+1;elsefor(int j=i;jWorkSize)FreeRami.FreeStartAdd=UsedRamk.UsedEndAdd+1;FreeRami.FreeRamSize=FreeRami.FreeEndAdd-FreeRami.FreeStartAdd+1;elsefor(int j=i;jWorkSize)FreeRami.FreeStartAdd=UsedRamk.UsedEndAdd+1;FreeRami.FreeRamSize=FreeRami.FreeEndAdd-FreeRami.FreeStartAdd+1;elsefor(int j=i;j0;j+)UsedRamj.UsedRamSize=UsedRamj-1.UsedRamSize;UsedRamj.UsedStartAdd=UsedRamj-1.UsedStartAdd;UsedRamj.UsedEndAdd=UsedRamj-1.UsedEndAdd;UsedRamj.WorkName=UsedRamj-1.WorkName;UsedRamWorkNumber+1.WorkName=;if(FreeRami.FreeRamSizeWorkSize)FreeRami.FreeStartAdd=UsedRamk.UsedEndAdd+1;FreeRami.FreeRamSize=FreeRami.FreeEndAdd-FreeRami.FreeStartAdd+1;elsefor(int j=i;jFreeWorkNumber-1;j+)FreeRamj.FreeRamSize=FreeRamj+1.FreeRamSize;FreeRamj.FreeStartAdd=FreeRamj+1.FreeStartAdd;FreeRamj.FreeEndAdd=FreeRamj+1.FreeEndAdd;FreeRamFreeWorkNumber-1.FreeStartAdd=-1; int x;x=1;else if(Choose=2)i=Best();for(int j=0;j100;j+)if(WorkNumber!=0)if(UsedRamj.UsedStartAdd=0&UsedRamj.UsedEndAdd=0)k=j;break;else if(FreeRami.FreeEndAddk;j-)UsedRamj.UsedRamSize=UsedRamj-1.UsedRamSize;UsedRamj.UsedStartAdd=UsedRamj-1.UsedStartAdd;UsedRamj.UsedEndAdd=UsedRamj-1.UsedEndAdd;UsedRamj.WorkName=UsedRamj-1.WorkName;UsedRamk.UsedStartAdd=FreeRami.FreeStartAdd;UsedRamk.UsedEndAdd=FreeRami.FreeStartAdd+WorkSize-1;UsedRamk.UsedRamSize=WorkSize;UsedRamk.WorkName=name;if(FreeRami.FreeRamSizeWorkSize)FreeRami.FreeStartAdd=UsedRamk.UsedEndAdd+1;FreeRami.FreeRamSize=FreeRami.FreeEndAdd-FreeRami.FreeStartAdd+1;elsefor(int j=i;jWorkSize)FreeRami.FreeStartAdd=UsedRamk.UsedEndAdd+1;FreeRami.FreeRamSize=FreeRami.FreeEndAdd-FreeRami.FreeStartAdd+1;elsefor(int j=i;jWorkSize)FreeRami.FreeStartAdd=UsedRamk.UsedEndAdd+1;FreeRami.FreeRamSize=FreeRami.FreeEndAdd-FreeRami.FreeStartAdd+1;elsefor(int j=i;jFreeWorkNumber-1;j+)FreeRamj.FreeRamSize=FreeRamj+1.FreeRamSize;FreeRamj.FreeStartAdd=FreeRamj+1.FreeStartAdd;FreeRamj.FreeEndAdd=FreeRamj+1.FreeEndAdd;FreeRamFreeWorkNumber-1.FreeStartAdd=-1;else if(Choose=3)i=Worst();for(int j=0;j100;j+)if(WorkNumber!=0)if(UsedRamj.UsedStartAdd=0&UsedRamj.UsedEndAdd=0)k=j;break;else if(FreeRami.FreeEndAddk;j-)UsedRamj.UsedRamSize=UsedRamj-1.UsedRamSize;UsedRamj.UsedStartAdd=UsedRamj-1.UsedStartAdd;UsedRamj.UsedEndAdd=UsedRamj-1.UsedEndAdd;UsedRamj.WorkName=UsedRamj-1.WorkName;UsedRamk.UsedStartAdd=FreeRami.FreeStartAdd;UsedRamk.UsedEndAdd=FreeRami.FreeStartAdd+WorkSize-1;UsedRamk.UsedRamSize=WorkSize;UsedRamk.WorkName=name;if(FreeRami.FreeRamSizeWorkSize)FreeRami.FreeStartAdd=UsedRamk.UsedEndAdd+1;FreeRami.FreeRamSize=FreeRami.FreeEndAdd-FreeRami.FreeStartAdd+1;elsefor(int j=i;jWorkSize)FreeRami.FreeStartAdd=UsedRamk.UsedEndAdd+1;FreeRami.FreeRamSize=FreeRami.FreeEndAdd-FreeRami.FreeStartAdd+1;elsefor(int j=i;jWorkSize)FreeRami.FreeStartAdd=UsedRamk.UsedEndAdd+1;FreeRami.FreeRamSize=FreeRami.FreeEndAdd-FreeRami.FreeStartAdd+1;elsefor(int j=i;jFreeWorkNumber-1;j+)FreeRamj.FreeRamSize=FreeRamj+1.FreeRamSize;FreeRamj.FreeStartAdd=FreeRamj+1.FreeStartAdd;FreeRamj.FreeEndAdd=FreeRamj+1.FreeEndAdd;FreeRamFreeWorkNumber-1.FreeStartAdd=-1;Moldification();void ShowUsed()coutendl;coutUsedRam information: endl;coutNo.xtNametSizetStAddtEndAddtendl;for(int i=0;i100;i+)if(UsedRami.UsedStartAdd=0&UsedRami.UsedEndAdd=0)break;elsecoutUsedRami.UsedNumbertUsedRami.WorkNamet;coutUsedRami.UsedRamSizetUsedRami.UsedStartAddt;coutUsedRami.UsedEndAddendl;void ShowFree()coutendl;coutFreeRam information: endl;coutNo.xtSizetStAddtEndAddtendl;for(int i=0;i51;i+)if(FreeRami.FreeStartAdd=-1)break;elsecoutFreeRami.FreeNumbertFreeRami.FreeRamSizet;coutFreeRami.FreeStartAddtFreeRami.FreeEndAddtendl; void Init()FreeRam0.FreeRamSize=3;FreeRam0.FreeStartAdd=4;FreeRam0.FreeEndAdd=6;FreeRam1.FreeRamSize=2;FreeRam1.FreeStartAdd=9;FreeRam1.FreeEndAdd=10;FreeRam2.FreeRamSize=4;FreeRam2.FreeStartAdd=14;FreeRam2.FreeEndAdd=17;FreeRam3.FreeRamSize=79;FreeRam3.FreeStartAdd=21;FreeRam3.FreeEndAdd=99;FreeRam4.FreeStartAdd=-1;UsedRam0.WorkName=A;UsedRam0.UsedRamSize=4;UsedRam0.UsedStartAdd=0;UsedRam0.UsedEndAdd=3;UsedRam1.WorkName=B;UsedRam1.UsedRamSize=2;UsedRam1.UsedStartAdd=7;UsedRam1.UsedEndAdd=8;UsedRam2.WorkName=C;UsedRam2.UsedRamSize=3;UsedRam2.UsedStartAdd=11;UsedRam2.UsedEndAdd=13;UsedRam3.WorkName=D;UsedRam3.UsedRamSize=3;UsedRam3.UsedStartAdd=18;UsedRam3.UsedEndAdd=20;UsedRam4.WorkName=;for(int j=0;j100;j+)UsedRamj.UsedNumber=j+1;for(int j=0;j51;j+)FreeRamj.FreeNumber=j+1;Moldification();void RecycleRam()int i;int m,n;coutendl;couti;i-;if(UsedRami.UsedStartAdd=0&UsedRami.UsedEndAdd!=0)/这个作业是内存中的从0地址开始的 FreeWorkNumber=0;CountFreeWorkNumber();if(UsedRami.UsedRamSize=100)for(int j=0;j100;j+)/全部置零 Ramj.use=0;UsedRam0.UsedEndAdd=0;UsedRam0.UsedRamSize=0;UsedRam0.UsedStartAdd=0;UsedRam0.WorkName=;FreeRam0.FreeNumber=1;FreeRam0.FreeRamSize=100;FreeRam0.FreeStartAdd=0;FreeRam0.FreeEndAdd=99;FreeRam1.FreeStartAdd=-1;elsefor(int j=UsedRami.UsedStartAdd;j0;k-)FreeRamk.FreeRamSize=FreeRamk-1.FreeRamSize;FreeRamk.FreeStartAdd=FreeRamk-1.FreeStartAdd;FreeRamk.FreeEndAdd=FreeRamk-1.FreeEndAdd;FreeRamFreeWorkNumber+1.FreeStartAdd=-1;FreeRam0.FreeStartAdd=UsedRami.UsedStartAdd;FreeRam0.FreeEndAdd=UsedRami.UsedEndAdd;FreeRam0.FreeRamSize=FreeRam0.FreeEndAdd-FreeRam0.FreeStartAdd+1;for(int j=0;jWorkNumber-1;j+)UsedRamj.UsedRamSize=UsedRamj+1.UsedRamSize;UsedRamj.UsedStartAdd=UsedRamj+1.UsedStartAdd;UsedRamj.UsedEndAdd=UsedRamj+1.UsedEndAdd;UsedRamj.WorkName=UsedRamj+1.WorkName;UsedRamWorkNumber-1.UsedRamSize=0;UsedRamWorkNumber-1.UsedStartAdd=0;UsedRamWorkNumber-1.UsedEndAdd=0;UsedRamWorkNumber-1.WorkName=;elseFreeRam0.FreeStartAdd=UsedRami.UsedStartAdd;/这一行应该定义结束地址的，由于本来就存储了，所以省略 FreeRam0.FreeRamSize=FreeRam0.FreeEndAdd-FreeRam0.FreeStartAdd+1;for(int j=0;jWorkNumber-1;j+)UsedRamj.UsedRamSize=UsedRamj+1.UsedRamSize;UsedRamj.UsedStartAdd=UsedRamj+1.UsedStartAdd;UsedRamj.UsedEndAdd=UsedRamj+1.UsedEndAdd;UsedRamj.WorkName=UsedRamj+1.WorkName;UsedRamWorkNumber-1.UsedRamSize=0;UsedRamWorkNumber-1.UsedStartAdd=0;UsedRamWorkNumber-1.UsedEndAdd=0;UsedRamWorkNumber-1.WorkName=;elseif(RamUsedRami.UsedStartAdd-1.use=0&RamUsedRami.UsedEndAdd+1.use=1)/作业区前面的为空闲区 ，后面为作业区 m=UsedRami.UsedStartAdd-1;FreeWorkNumber=0;CountFreeWorkNumber();for(int j=0;jFreeWorkNumber;j+)if(m=FreeRamj.FreeEndAdd)n=j;break; for(int j=UsedRami.UsedStartAdd;j=UsedRami.UsedEndAdd;j+)Ramj.use=0;WorkNumber=0;CountWorkNumber();FreeRamn.FreeEndAdd=UsedRami.UsedEndAdd;FreeRamn.FreeRamSize=FreeRamn.FreeEndAdd-FreeRamn.FreeStartAdd+1;for(int j=i;jWorkNumber-1;j+)UsedRamj.UsedRamSize=UsedRamj+1.UsedRamSize;UsedRamj.UsedStartAdd=UsedRamj+1.UsedStartAdd;UsedRamj.UsedEndAdd=UsedRamj+1.UsedEndAdd;UsedRamj.WorkName=UsedRamj+1.WorkName;UsedRamWorkNumber-1.UsedRamSize=0;UsedRamWorkNumber-1.UsedStartAdd=0;UsedRamWorkNumber-1.UsedEndAdd=0;Use