存储管理动态分区分配算法的模拟

1、课程设计书第 页第 页、设计任务完成存储器动态分区分配算法的模拟实现。二、设计思想在对数据结构有一定掌握程度的情况下设计合理的数据结构来描述存储空间，实现分区存储管理的内存分配功能，应该选择最合适的适应算法(首次适应算法，最佳适应算法，最后适应算法，最坏适应算法)，实现分区存储管理的内存回收算法，在这些存储管理中间必然会有碎片的产生，当碎片产生时，进行碎片的拼接，等等相关的内容。三、预期目的让我们了解操作系统的基本概念，理解计算机系统的资源如何组织，操作系统如何有效地管理这些系统资源，用户如何通过操作系统与计算机系统打交道。通过课程设计，我们可以进一步理解在计算机系统上运行的其它各类操作系统，

2、并懂得在操作系统的支持下建立自己的应用系统。操作系统课程设计，对于训练学生掌握程序设计、熟悉上机操作和程序调试技术都有重要作用。重点培养学生的思维能力、设计能力、创新能力和排错能力。四、设计方案首先是对相关知识的掌握，例如数据结构，计算方法，组成原理以及操作系统等。在这些基本知识的基础上进行扩展，用语言的形式从函数，数据结构原代码，原程序等方面来达到自己想要的目的。该设计就是要达到对各个细节的问题的解决将各个数据块连接起来，最终达到存储器动态分区分配算法的模拟实现。五、数据结构1设计合理的数据结构来描述存储空间：对于未分配出去的部分，用空闲分区链表来描述。structfreeListintst

3、artAddress;/*分区起始地址*/intsize;/*分区大小*/structfreeList*next;/*分区链表指针*/对于已经分配出去的部分，由装入内存的作业占据。structusedList/*分区起始地址*/*分区中存放作业ID*/*分区链表指针*/intstartAddress;intjobID;structusedList*next;将作业组织成链表。structjobListintid;/*作业ID*/intsize;/*作业大小（需要的存储空间大小）*/intstatus;/*作业状态0:newjob,1:inthememory,2:finished.*/struc

4、tjobList*next;/*作业链表指针*/以上将存储空间分为空闲可占用两部分，在usedlist中设joblD而不设size，可以在不增加空间复杂度（与freelist相比）的同时更方便的实现可变分区存储管理（从后面的一些函数的实现上可以得出这个结论）。尽管设置joblist增加了空间复杂度，但它的存在，使得该程序可以方便的直接利用D盘中的JOB文件。该文件可以认为是一个和其他进程共享的资源。通过这个文件，其他进程写入数据供读取。这中思想在操作系统设计中体现的很多。2实现分区存储管理的内存分配功能，选择适应算法（首次适应算法，最佳适应算法，最后适应算法，最坏适应算法）。基本原理分析：1）

5、Bestfit：将空闲分区按大小从小到大排序，从头找到大小合适的分区。2）Worstfit：将空闲分区按大小从大到小排序，从头找到大小合适的分区。3）Firstfit：将空闲分区按起始地址大小从小到大排序，4）Lastfit：将空闲分区按起始地址大小从大到小排序，由此，可将空闲分区先做合适的排序后用对应的适应算法给作业分配存储空间。排序函数order（bySize为零则按分区大小排序，否则按分区起始地址；inc为零从小到大排序，否则从大到小排序；通过empty指针返回结果）。voidorder（structfreeList*empty,intbySize,intinc）structfreeLi

6、st*p,*q,*temp;intstartAddress,size;for(p=(*empty)-next;p;p=p-next)/*按bySize和inc两个参数寻找合适的节点，用temp指向它*/for(temp=q=p;q;q=q-next)switch(bySize)case0:switch(inc)case0:if(q-sizesize)temp=q;break;default:if(q-sizetemp-size)temp=q;break;break;default:switch(inc)case0:if(q-startAddressstartAddress)temp=q;bre

7、ak;default:if(q-startAddresstemp-startAddress)temp=q;break;break;/*交换节点的成员值*/if(temp!=p)startAddress=p-startAddress;size=p-size;p-startAddress=temp-startAddress;p-size=temp-size;temp-startAddress=startAddress;temp-size=size;3实现分区存储管理的内存回收算法。voidinsertFreeNode(structfreeList*empty,intstartAddress,int

8、size)插入回收的空节点分区，处理回收分区与空闲分区的四种邻接关系。structfreeList*p,*q,*r;for(p=*empty;p-next;p=p-next);/*处理链表尾部的邻接情况*/if(p=*empty|p-startAddress+p-sizenext=p-next;/*插入独立的空闲节点*/p-next=r;return;if(p-startAddress+p-size=startAddress)/*与尾部上邻*/p-size+=size;/*合并尾部节点*/return;q=(*empty)-next;/*处理链表首节点的邻接情况*/if(startAddres

9、s+size=q-startAddress)/*与首节点下邻*/q-startAddress=startAddress;/*合并首节点*/q-size+=size;elseif(startAddress+sizestartAddress)/*与首节点不相邻*/makeFreeNode(&r,startAddress,size);r-next=(*empty)-next;(*empty)-next=r;else/*处理链表中间的邻接情况*/while(q-next&q-startAddressnext;if(p-startAddress+p-size=startAddress&q-startAd

10、dress=startAddress+size)/*上下邻，合并节点*/p-size+=size+q-size;p-next=q-next;程设计书程设计书第 页第 #页/*删除多余节点*/课free(q);elseif(p-startAddress+p-size=startAddress&q-startAddress!=startAddress+size)/*上邻，增加节点的大小*/p-size+=size;elseif(p-startAddress+p-size!=startAddress&q-startAddress=startAddress+size)/*下邻*/q-startAddr

11、ess=startAddress;/*修改节点起始地址*/q-size+=size;/*修改节点的大小*/else/*上下不相邻*/makeFreeNode(&r,startAddress,size);r-next=p-next;p-next=r;4当碎片产生时，进行碎片的拼接。voidmoveFragment(structjobList*jobs,structfreeList*empty,structusedList*used)intsize,status;structusedList*p;intaddress=memoryStartAddress;/*全局变量，初始化时分配存储空间始址*/

12、if(*empty)-next=NULL)/*空闲分区链表为空，提示并返回*/printf(nThememorywasusedoutatall.nMaybeyoushouldfinishsomejobsfirstorpressanykeytotryagain!);getch();return;for(p=(*used)-next;p;p=p-next)/*循环的修改占用分区的始址*/p-startAddress=address;课程设计书课程设计书第 页第 页getjoblnfo(jobs,p-joblD，&size，&status);/*由作业ID获得作业大小*/address+=size;

13、(*empty)-next-startAddress=address;/*修改空闲分区的首节点始址、大小*/(*empty)-next-size=memorySize-(address-memoryStartAddress);(*empty)-next-next=NULL;/*删除首节点后的所有节点*/5空闲分区队列显示：intshowFreeList(structfreeList*empty)6作业占用链表显示intshowUsedList(structjobList*jobs,structusedList*used)从头到尾显示used链，同时通过其中的作业ID在jobs中查对应的大小。7

14、从键盘输入作业到D盘的JOB文件：voidinputjob(void)8从JOB文件中读出作业并创建作业链表：intmakejobList(structjobList*jobs)9显示作业链表：intshowjobList(structjobList*jobs)更新作业链表中作业的状态：intupdatejobFile(structjobList*jobs)根据作业链表更新JOB文件：intupdatejobFile(structjobList*jobs)为作业分配存储空间、状态必须为0：intallocate(structfreeList*empty,intsize)结束一个作业号为id的作

15、业，释放存储空间(由*startAddress返回空间的起始地址)：intfinishjob(struetusedList*used,intid,int*startAddress)插入释放的空间到used链表中(作业号为id,startAddress由函数13返回)：voidinsertUsedNode(struetusedList*used,intid,intstartAddress)15.获取作业的信息：voidgetJobInfo(structjobList*jobs,intid,int*size,int*status)16.初始化存储空间起始地址、大小：voidiniMemory(vo

16、id)17.选择适应算法：charselectFitMethod(void)18根据参数startAddress、size创建空闲节点，由empty指针返回：voidmakeFreeNode(structfreeList*empty,intstartAddress,intsize)19.以要求的方式打开文件：voidopenFile(FILE*fp,char*filename,char*mode)20.出现严重错误时显示信息并结束程序；voiderrorMessage(void)六、算法流程1、DynamicZonalMemoryManagement其中1、Initializiation.按顺

17、序利用了openFile()、iniMemory()、makeFreeNode()、inputjob()(选择利用D盘JOB文件时提供作业信息)、makeJobList()、allocate()、insertUsedNode()(选择利用D盘JOB文件时先将状态为1的作业放到存储空间中，以恢复上次的模拟实验，或使本次模拟时不出错)selectFitMethod(等自编函数。2、Putjobintomemory(allocatememory)按顺序利用了showJobList()(选手动逐个为作业分配存储空间时)、openFile()、order()、allocate()、errorMessag

18、e()、insertUsedNode()、updateJobStatus()updateJobFile()函数3、Finishjob(reusememory)按顺序利用了openFile()、showUsedList()、getJobInfo()、insertFreeNode()、updateJobStatus()、updateJobFile()、errorMessage()等自编函数。4、Showcurrentfreelist按顺序利用了openFile()、showFreeList()函数。5、Showcurrentmemoryusedbyjobs按顺序利用了openFile()、show

19、UsedList()函数。6、Movefragmenttogether按顺序利用了openFile()、moveFragment()函数。7、Exit按顺序利用了openFile()、exit(0)函数。七、程序清单1、原程序#include#include#includeintmemoryStartAddressintmemorySizestructjobListintintint/*id;size;status;作业状态0-1;=-1;/*作业ID*/*作业大小（需要的存储空间大小）*/:newjob*next;structjobList;structfreeListintstartAdd

20、ress;intsize;,1:inthememory,2:finished.*/*作业链表指针*/structfreeList*next;/*分区起始地址*/*分区大小*/*分区链表指针*/课程设计书课程设计书第 页第 页;structusedList/*分区起始地址*/*分区中存放作业ID*/*分区链表指针*/*出现严重错误时显示信息并结束程序*/intstartAddress;intjobID;structusedList*next;voiderrorMessage(void)printf(ntError!a);printf(nPressanykeytoexit!);getch();ex

21、it(1);voidopenFile(FILE*fp,char*filename,char*mode)/*以要求的方式打开文件*/if(*fp=fopen(filename,mode)=NULL)printf(nCantopen%sinmode%s.,filename,mode);errorMessage();voidmakeFreeNode(structfreeList*empty,intstartAddress,intsize)/*根据参数startAddress、size创建空闲节点，由empty指针返回*/if(*empty=malloc(sizeof(structfreeList)=

22、NULL)printf(nNotenoughtoallocateforthefreenode.);errorMessage();(*empty)-startAddress=startAddress;(*empty)-size=size;(*empty)-next=NULL;voidiniMemory(void)/*初始化存储空间起始地址、大小*/charMSA10,MS10;printf(nPleaseinputthestartaddressofthememory!);scanf(%s,MSA);memoryStartAddress=atoi(MSA);printf(nPleaseinputt

23、hesizeofthememory!);scanf(%s,MS);memorySize=atoi(MS);charselectFitMethod(void)/*选择适应算法*/FILE*fp;charfitMethod;doprintf(nnPleaseinputacharasfallowtoselectthefitmethod!n1(Bestfit)n2(Worstfit)n3(Firstfit)n4(Lastfit)n)fitMethod=getche();while(fitMethod4);openFile(&fp,d:result.cl,a);switch(fitMethod)，1，c

24、ase1:fprintf(fp,nnnntBestfit);fprintf(fp,n*);break;case2:fprintf(fp,nnnntWorstfit);fprintf(fp,n*);break;，o5case3:fprintf(fp,nnnntFirstfit);fprintf(fp,n*);break;case4:fprintf(fp,nnnntLastfit);fprintf(fp,n*);break;fclose(fp);returnfitMethod;voidinputJob(void)/*从键盘输入作业到D盘的JOB文件*/int/*id,size,*/status=0

25、,jobnum=0;FILE*fp;charid10,size10;openFile(&fp,d:job.cl,w);fprintf(fp,job_IDtsizetstatus);printf(nnnnPleaseinputthejobsasfallow!nEnteraintegersmallerthan1toquit.njob_IDtsizen);do/*scanf(%d%d,&id,&size);*/scanf(%st%s,id,size);if(atoi(id)0&atoi(size)0)fprintf(fp,n%st%st%d,id,size,status);/*fprintf(fp,

26、n%dt%dt%d,id,size,status);*/jobnum+;elsebreak;while(1);if(jobnum)printf(nFinishedtoinputthejobs!);elseprintf(nNojobwasgiven.);errorMessage();intfclose(fp);makeJobList(structjobList*jobs)/*从JOB文件中读出作业并创建作业链表*/charjobID10,size10,status10;structjobList*rear;FILE*fp;openFile(&fp,d:job.cl,r);fscanf(fp,%s

27、%s%s,jobID,size,status);if(*jobs=malloc(sizeof(structjobList)=NULL)printf(nNotenoughtoallocateforthejob.);fclose(fp);errorMessage();rear=*jobs;(*jobs)-next=NULL;while(!feof(fp)structjobList*p;fscanf(fp,%s%s%s,jobID,size,status);if(p=malloc(sizeof(structjobList)=NULL)printf(nNotenoughtoallocateforthe

28、job.);fclose(fp);errorMessage();next=rear-next;-next=p;rear-next;id=atoi(jobID);size=atoi(size);status=atoi(status);-prearrear-rearrearrearfclose(fp);return0;intupdateJobFile(structjobList*jobs)/*更新作业链表中作业的状态*/FILE*fp;structjobList*p;openFile(&fp,d:job.cl,w);fprintf(fp,job_IDtsizetstatus);for(p=jobs

29、-next;p;p=p-next)fprintf(fp,n%dt%dt%d,p-id,p-size,p-status);fclose(fp);return0;intshowFreeList(structfreeList*empty)/*空闲分区队列显示*/FILE*fp;structfreeList*p=empty-next;intcount=0;openFile(&fp,d:result.cl,a);fprintf(fp,nnNowshowthefreelist.);printf(nnNowshowthefreelist.);if(p)fprintf(fp,nnumbertsizetstar

30、tAddress);printf(nnumbertsizetstartAddress);for(;p;p=p-next)fprintf(fp,n%dt%dt%d,+count,p-size,p-startAddress);printf(n%dt%dt%d,count,p-size,p-startAddress);fclose(fp);return1;elsefprintf(fp,nThememorywasusedout!);printf(nThememorywasusedout!);fclose(fp);return0;voidgetJobInfo(structjobList*jobs,int

31、id,int*size,int*status)/*获取作业的信息*/structjobList*p=jobs-next;while(p&p-id!=id)p=p-next;if(p=NULL)printf(nCantfindthejobwhichidis:%d.,id);errorMessage();else*size=p-size;*status=p-status;voidupdateJobStatus(structjobList*jobs,intid,intstatus)structjobList*p=(*jobs)-next;while(p&p-id!=id)p=p-next;if(p=

32、NULL)printf(nCantfindthejobwhichidis:%d.,id);errorMessage();elsep-status=status;intshowUsedList(structjobList*jobs,structusedList*used)/*作业占用链表显示*/FILE*fp;structusedList*p=used-next;intcount=0,size,status;openFile(&fp,d:result.cl,a);fprintf(fp,nnNowshowtheusedlist.);printf(nnNowshowtheusedlist.);if(

33、p)fprintf(fp,nnumbertjobIDtsizetstartAddress);printf(nnumbertjobIDtsizetstartAddress);for(;p;p=p-next)getJobInfo(jobs,p-jobID,&size,&status);fprintf(fp,n%dt%dt%dt%d,+count,p-jobID,size,p-startAddress);printf(n%dt%dt%dt%d,count,p-jobID,size,p-startAddress);fclose(fp);return1;elsefprintf(fp,nNojobinth

34、ememory!Youshouldinputsomejobstoit.);printf(nNojobinthememory!Youshouldinputsomejobstoit.);fclose(fp);return0;intshowJobList(structjobList*jobs)/*显示作业链表*/structjobList*p;p=jobs-next;if(p=NULL)printf(nNojobinthelist!Tryagainnexttime.);return0;printf(nnThejoblistisasfallow:njob_IDtsizetstatus);while(p

35、)printf(n%dt%dt%d,p-id,p-size,p-status);p=p-next;return1;voidmoveFragment(structjobList*jobs,structfreeList*empty,structusedList*used)intsize,status;structusedList*p;intaddress=memoryStartAddress;/*全局变量，初始化时分配存储空间始址*/if(*empty)-next=NULL)/*空闲分区链表为空，提示并返回*/printf(nThememorywasusedoutatall.nMaybeyoush

36、ouldfinishsomejobsfirstorpressanykeytotryagain!);getch();return;for(p=(*used)-next;p;p=p-next)/*循环的修改占用分区的始址*/p-startAddress=address;getJobInfo(jobs,p-jobID,&size,&status);/*由作业ID获得作业大小*/address+=size;(*empty)-next-startAddress=address;/*修改空闲分区的首节点始址、大小*/(*empty)-next-size=memorySize-(address-memory

37、StartAddress);(*empty)-next-next=NULL;/*删除首节点后的所有节点*/voidorder(structfreeList*empty,intbySize,intinc)structfreeList*p,*q,*temp;intstartAddress,size;for(p=(*empty)-next;p;p=p-next)/*按bySize和inc两个参数寻找合适的节点，用temp指向它*/for(temp=q=p;q;q=q-next)switch(bySize)case0:switch(inc)case0:if(q-sizesize)temp=q;brea

38、k;default:if(q-sizetemp-size)temp=q;break;break;default:switch(inc)case0:if(q-startAddressstartAddress)temp=q;break;default:if(q-startAddresstemp-startAddress)temp=q;break;break;/*交换节点的成员值*/if(temp!=p)startAddress=p-startAddress;size=p-size;p-startAddress=temp-startAddress;p-size=temp-size;temp-star

39、tAddress=startAddress;temp-size=size;intallocate(structfreeList*empty,intsize)/*为作业分配存储空间、状态必须为0*/structfreeList*p,*prep;intstartAddress=-1;p=(*empty)-next;while(p&p-sizenext;if(p!=NULL)if(p-sizesize)startAddress=p-startAddress;p-startAddress+=size;p-size-=size;elsestartAddress=p-startAddress;prep=*

40、empty;while(prep-next!=p)prep=prep-next;prep-next二p-next;free(p);elseprintf(nMaybeyoushouldmovethefragmenttogether.);/*Unsuccessful!*/returnstartAddress;voidinsertUsedNode(structusedList*used,intid,intstartAddress)/*插入释放的空间到used链表中(作业号为id,startAddress由函数13返回)*/structusedList*q,*r,*prer;if(q=malloc(s

41、izeof(structusedList)=NULL)printf(nNotenoughtoallocatefortheusednode.);errorMessage();q-startAddress=startAddress;q-jobID=id;prer=*used;r=(*used)-next;while(r&r-startAddressnext;q-next=prer-next;prer-next=q;intfinishJob(structusedList*used,intid,int*startAddress)/*结束一个作业号为id的作业,释放存储空间(由*startAddress

42、返回空间的起始地址)*/structusedList*p,*prep;prep=*used;p=prep-next;while(p&p-jobID!=id)prep=p;p=p-next;if(p=NULL)printf(nThejobwhichidis:%disnotinthememory!,id);return0;else*startAddress=p-startAddress;prep-next=p-next;free(p);return1;voidinsertFreeNode(structfreeList*empty,intstartAddress,intsize)/*插入回收的空节点

43、分区，处理回收分区与空闲分区的四种邻接关系。*/structfreeList*p,*q,*r;for(p=*empty;p-next;p=p-next);/*处理链表尾部的邻接情况*/if(p=*empty|p-startAddress+p-sizenext=p-next;/*插入独立的空闲节点*/p-next=r;return;if(p-startAddress+p-size=startAddress)/*与尾部上邻*/p-size+=size;/*合并尾部节点*/return;q=(*empty)-next;/*处理链表首节点的邻接情况*/if(startAddress+size=q-st

44、artAddress)/*与首节点下邻*/q-startAddress=startAddress;/*合并首节点*/q-size+=size;elseif(startAddress+sizestartAddress)/*与首节点不相邻*/makeFreeNode(&r,startAddress,size);r-next=(*empty)-next;(*empty)-next=r;else/*处理链表中间的邻接情况*/while(q-next&q-startAddressnext;if(p-startAddress+p-size=startAddress&q-startAddress=start

45、Address+size)/*上下邻，合并节点*/p-size+=size+q-size;p-next=q-next;free(q);/*删除多余节点*/elseif(p-startAddress+p-size=startAddress&q-startAddress!=startAddress+size)/*上邻，增加节点的大小*/p-size+=size;elseif(p-startAddress+p-size!=startAddress&q-startAddress=startAddress+size)/*下邻*/q-startAddress=startAddress;/*修改节点起始地址

46、*/q-size+=size;/*修改节点的大小*/else/*上下不相邻*/makeFreeNode(&r,startAddress,size);r-next=p-next;p-next=r;voidmain(void)charfitMethod;FILE*fp;structjobList*jobs;structfreeList*empty;structusedList*used;if(used=malloc(sizeof(structusedList)=NULL)printf(nNotenoughtoallocatefortheusednode.);errorMessage();used-

47、next=NULL;remove(d:result.cl);makeFreeNode(&empty,0,0);while(1)charch,step;intid,size,startAddress,status;structjobList*q;printf(n1Initializiation.n2Putjobintomemory(allocatememory).n3Finishjob(reusememory).n4Showcurrentfreelist.n5Showcurrentmemoryusedbyjobs.n6Movefragmenttogether.n7Exit.);printf(nP

48、leaseselectadigittocontinue.n);step=getche();printf(n);switch(step)，1，case1:openFile(&fp,d:result.cl,a);fprintf(fp,nntInitializiation:);used-next=NULL;empty-next=NULL;iniMemory();makeFreeNode(&(empty-next),memoryStartAddress,memorySize);fprintf(fp,nnnDoyouwanttouseyourjobfiledirectly?nDefaultisN.Y/N

49、:);printf(nnnDoyouwanttouseyourjobfiledirectly?nDefaultisN.Y/N:n);课程设计书课程设计书第 页第 页ch=getche();fprintf(fp,n%c,ch);fclose(fp);if(ch!=Y&ch!=y)inputJob();makeJobList(&jobs);if(ch=Y|ch=y)for(q=jobs-next;q;q=q-next)if(q-status=1)startAddress=allocate(&empty,q-size);if(startAddress!=-1)insertUsedNode(&used

50、,q-id,startAddress);fitMethod=selectFitMethod();break;case2:if(memoryStartAddress0|memorySizenext;q;q=q-next)if(q-status=0)switch(fitMethod)case1:order(&empty,0,0);break;case2:order(&empty,0,1);break;case3:order(&empty,1,0);break;case4:order(&empty,1,1);break;startAddress=allocate(&empty,q-size);if(

51、startAddress!=-1)insertUsedNode(&used,q-id,startAddress);updateJobStatus(&jobs,q-id,1);updateJobFile(jobs);elseshowJobList(jobs);openFile(&fp,d:result.cl,a);fprintf(fp,nPleaseinputajobidfromabove.);printf(nPleaseinputajobidfromabove.);scanf(%d,&id);fprintf(fp,%dn,id);getJobInfo(jobs,id,&size,&status

52、);switch(status)case0:printf(nOk!Thejobsstatusiscorrect!);fprintf(fp,nOk!Thejobsstatusiscorrect!);fclose(fp);break;case1:printf(nThejobwasinthememory!);fprintf(fp,nThejobwasinthememory!);fclose(fp);gotolabel;case2:printf(nThejobwasfinished!);fprintf(fp,nThejobwasfinished!);fclose(fp);gotolabel;default:printf(nUnexpectedjobstatus.Pleasecheckyoujobfile.);fprintf(fp,nUnexpectedjobstatus.Pleasecheckyoujobfile.);fclose(fp);errorMessage();switch(fitMethod)case1:order(&empty,0,0);break;case2:order(&empty,0,1);break;case3:order(&empty,1,0);break;case4:order(&empty,1,