操作系统课程设计报告动态分区分配

1、青岛理工大学操作系统课程设计报告院(系):计算机工程学院专业：计算机科学弓技术专业学生姓名：牛利利班级：计算073 学号：200707106题目：动态分区分配模拟起迄日期：-2010年7月5日至7月16日设计地点：2号实验楼402室指导教师:李 2009201 ()年度 第2学期完成日期：2010年7月16日一、课程设计目的操作系统是昙重要的计算机系统软件，同时也是最活跃的学科之一。计算机系统由硬件 和软件两部分组成。操作系统是配直在计算机硬件上的第一层软件，是对硬件的首次扩充。 本次课程设计的主要目的是在学习操作系统理论知识的基础上，对操作系统整体的一个模 拟。也是对本学期所学知识的一个总体

2、的检测，使理论知识应用到实际的编程中，根据理论 的算法来实现具体的编程操作。同时通过本次课程设计加深对操作系统理论知识各个部分管 理功能的感性认识，进一步分析和理解各个部分之间的联系和功能，最后达到对完整系统的 理解。同时，可以提高运用操作系统知识和解决实际问题的能力；并且锻炼自己的编程能力、 创新能力以及开发软件的能力；还能提高自己的调査研究、査阅文献、资料以及编写软件设 计文档的能力并提高分析问题的能力。操作系统课程设计的主要任务是研究计算机操作系统的墓本原理和算法,拿握操作系统的 存储器管理、设杳管理、文件管理和进程管理的基本原理和算法。使学生李握墓本的原理和 方法，最后达到对完整系统的

3、理解。二、课程设计内容仿真实现动态可变分区存储管理模拟系统。内存调度策路可采用首次适应算法、循环首次 适应算法和最佳适应法尊，并对各种算法进行性能比较。为了实现分区分配，系统中必须配 直相应的数据结构，用来描述空闲区和已分配区的情况，为分配提供依据。常用的数据结构 有两种形式：空闲分区表和空闲分区链。为把一个新作业装入内存，狈按照一定的算法，从 空闲分区表或空闲分区链中选出一个分区分配给该作业。三、系统分析与设计1、系统分析：动态分区分配是根据进程的实际需要，动态地为之分配内存空间。在实现可变分区分配 时，将涉尺到分区分配中所用的数据结构、分区分配算法和分区的分配和回收操作这样三个 问题。为丁

4、实现分区分配，系统中必须配叠相应的数据结构，用来描述空闲区和巳分配区的 情况，为分配提供依据。常用的数据结构有两种形式：空闲分区表和空闲分区链。为把一个 新作业装入内存，须按照一定的算法，从空闲分区表或空闲分区链中选出一个分区分配给该 作业。目前常用的分配算法有：首次适应算法、循环首次适应算法、最佳适应算法、最坏适 应算法和快速适应算法。在动态分区存储管理方式中，主要操作是分配内存和回收内存。2、系统设计：系统利用某种分配算法，从空闲分区表中找到所需大小的分区。设请求分区的大小为U- size,表中每个空闲分区的大小可表示为m.sizc,若m.sizu-u.sizusizu （SiZU为事先规

5、定的不 再切割的剩余分区的大小）成立，则说明多余部分太小，可不再切割，将整个分区分配给请 求者；否则，从该分区中按请求的大小划分出一块内存空间分配出去，余下的部分留在空闲 区表中，然后将分配区的首址返回给调用者。当进程运行完毕释放内存时，系统根据回收区 的首址，从空闲区表中找到相应的插入点，并且按照四种情况进行插入。3、模块设计：空闲区说明表结构：把空闲区定义为结构体变長，包括空闲区始址，空闲区大小和空闲 区状态，用O表示空表目，1为可用空闲块。StrUCt FrCCarCaint startaddress;/* 空闲区始址 */ int sizc*空闲区大小*/int state;/*空闲区

6、状态:0为空表目，1为可用空闲块*/frccbk)ckN= l,20,20,l,2,80,50,l,3,150,30,1,4,300,30,1,5,500,10,1; 为作业分配 主存空间的函数allocO,三个算法分别对应三个分配主存空间的算法。aplyarca为作业申请 長、mg为检査是否有满足作业雲要的空闲区的标志。首次适应算法：检査空闲区说明表是否有满足作业要求的空闲区时,如果大于作业要求,则分配绐作业, 修改地址和空闲区大小,并将Mg晝“1”，表示有满足作业要求的空闲区,返回为作业分配 主存的地址程序如下所示：if(frccblock 0 .state=1&frccblocki .s

7、izcapplyarca)frccblockf.startaddrcss=frccbl()cki.strtaddrcss+applyarca; frccbk)cki.sizc=frccbl()cki.sizc-aplyarca;tag=;return FrCCbIockp.startaddrcss-aplyarca;如果空闲区等于作业要求，则分配给作业修改地址和空闲区大小,并将吨直 T ,表示 有满足作业要求的空闲区,返回为作业分配主存的地址if(frccblock PJ-Statc=1& frccblockp.sizc=aplyarca)frccblocki.statc=0;Iag= 1;r

8、eturn frccblock0.startaddress;如果没有满足条件的空闲区，分配不成功，返回-1if(tag=0)rctx循环首次适应算法的abcO函数与首次适应算法的山疋0函教区别在于从哪里开始找是否 有满足作业要求的空闲区，它是从上次找到的空闲区的下一个空闲分区开始找，只雲要 改变缺循环的条件即可。for(i=s;iN;i+)黒佳适应算法：该算法总是把满足要求、又是最小的空闲区分配给作业。检査空闲区说明表是否有满足作业要求的空闲区，也分为三种情况：大于，等于，小于。若检査到有 “等于”的情况，就可以直接分配，若没有，则继续检査是否有“大于”的情况： if(frccbkrkp.st

9、ate=1& frccblr(i=0;i applyarea)a Q+=i;再从数组中挑出最小的那个：果敌组中的元素大干一个，则雷要一个个比较过去，然后取出最小的那个分配给作业:if(jl)h=a0;min= frccbkck h;f()r(k=l;kj;k+)h=ak;if(frccbl0ckh.sizcmin.si2c)mid.size=& CCbloCk l.size;mid.statc=frccblockp.statc;mid.startaddrcss=frccblockh.startaddrcss; frccblockh.sizc=min.sizc;frccblockh.statc=

10、min.statc;frccblockh.startaddrcss=mi.startaddrcss;min.si2c=mid.sizc;min.statc=mid.state； mi.startaddrcss=mid.startaddrcss;mi.startaddrcss=mi.startaddrcss+applyarca; mi.sizc=mi.sizc-aplyarca;tag=l;return min.starddrcss-applyarca;如果数组中只有一个元素，则直接分配绐作业：if(i=i)h=aO;min= frccbl)ck h;mi.startaddrcss=mi.sta

11、rtaddrcss+applyarca; mi.sizc=mi.si2c-alyarca;Iag= 1；return m in. S tar tadd res S- apply area;如果没有满足条件的空闲区，分配不成功，返回-1if(tag=O)rclurn -1; 主存回收函数sctfrccO： Sgl代表释放区的高地址是否邻接一个空闲区，mg2代表释放 区的高低地址是否都邻接一个空闲区，1慫3代表释放区的低地址是否邻接一个空闲区。 分为四种情况：回收分区的上邻和下邻分区都不是空闲的，则直接将回收区的相关信息记录在空闲区表中。if(tag3=0)for(j=0;jck.Startadd

12、rcss=S; frccblockO.sizc=l; FrCCbk)Ck 0.StatC= 1; break;0回收分区的上邻分区是空闲的，需要将这两个相邻的空闲区台并成一个较大的空闲区，然后修改空闲区表。if(frccblocki.startaddrcss=s+l&frccbkcki.statc= 1)l=l+frccblocki.sizc;Iagl = 1;回收分区的下邻分区是空闲区，雷要将这两个相邻的空闲区台并成一个空闲区，并修改闲区表。ifr(& CCbk)Cki.startaddrcssfrccblocki.sizc=s& frccblocki.state= 1)FrCCbIocki

13、.sizc=frccbkrki.sizc+l;Mg3=l;break;回收分区的上邻和下邻都是空闲区，则雷要将这三个空闲区台并成一个更大的空闲区，然后修改空闲区表。先判断有上邻空闲区(如所示)，再判断有下邻空闲区(如所示)，若都有，则将ug2l0(4)对空闲区表中的空闲区调整的函数adjust。：使空闲区按始地址从小到大排列，空表目放 在舅后EI O打印空闲区说明表函数：Prinlo首次适应算法函数FirSt_乩0：若有作业雷要分配内存，则对空闲区表中的空闲区进行调 整，调用调整函数“djustO,再将其打印出来；输入作业申请長，调用毗CO函数为作业 分配空间，分配结束后，要进行主存回收，再次

14、调整空闲区表后，打印出来。循环执行 直到没有作业为止。循环首次适应算法NCXL-fiO首次适应算法不同的是，循环首次适应算法要记录上次找到的空闲区地址，并在下次分配时从这个地址开始。最佳时应算法Bcst-fitO：该算法在分配内存时，把所有满足要求的空闲区中最小的那个空 闲区分配给请求迸程。(9)主函数mai0 :主要用于调用各个函数来实现各项功能和显示主界面。4、数据结构说明：空闲区说明表结构SlTUCI frCCarea：把空闲区定义为结构体变長，包括空闲区始址，空闲 区大小和空闲区状态，用0表示空表目，1为可用空闲块。为作业分配主存空间的函数allocO ,三个算法分别对应三个分配主存空

15、间的算法。 applyarca为作业申请長，Mg为检査是否有满足作业需要的空闲区的标志。 主存回收函SCtfrCCO: MgI代表释放区的高地址是否邻接一个空闲区，Ug2代表释放区 的高低地址是否都邻接一个空闲区，吨3代表释放区的低地址是否邻接一个空闲区。分 为四种情况。(4)对空闲区表中的空闲区调整的函adjUSt0：使空闲区按始地址从小到大排列，空表目放 在星!后IsI O打印空闲区说明表函数：Prinlo首次适应算法函数FirSt港有作业雷要分配内存，则对空闲区表中的空闲区进行调 整，调用调整函数ndjust,再将其打印出来；输入作业申请長，调用叔c函数为作业 分配空间，分配结束后，要迸

16、行主存回收，再次调整空闲区表后，打印出来。循环执行 直到没有作业为止。G)循环首次适应算法NCXL-fio首次适应算法不同的是，循环首次适应算法要记录上次找 到的空闲区地址，并在下次分配时从这个地址开始。最佳时应算法Bcst-fitO：该算法在分配内存时，把所有满足要求的空闲区中晟小的那个空闲区分配给请求迸程。主函数main。：主要用于调用各个函数来实现各项功能和显示主界面。5、算法流程图内存分配流程主函数流程图四、模块调试与系统测试1、模块调试 输入的形式和输入值的范围首先打开主界面输入整形常数选择所要使用的算法,再根据界面上的提示内容进行输 入整形常数选择所要进行的操作，主要包括作业的申请

17、是、释放的起始地址、释放区的 大小。输出的形式输出形式主要包括空闲区表的状态、申请作业的起始地址和作业的申请長=程序所能达到的功能程序所能达到的功能主要包括：初始化空闲区表的状态，按照首次适应算法、循环首 次适应算法和杲佳适应算法对内存空间进行分配,对内存空间进行回收并输出进行各项 操作后的空闲区表的状态。2、系统测试测试方法本系统采用黑盒测试方法进行测试。测试数据及测试擢吿试用例数据预测结果实际结果是否相符合法： 输入1-3进行 算法选择成功迸入下一步成功进入下一步相符非法：输入13以外 的数据显示出错提示“有 误，请重新输入”显示出错提示“有误， 请重新输入”相符合法：输入03选择 操作成

18、功选择所要迸行 的操作成功选择所要进行的 操作相符非法： 输入13以外 的数据显示“输入有误， 请重试”显示“输入有误，请 重试”相符台法：输入分配内存 操作下的申请 長为20显示：申请作业的 起始地址、申谙長 和内存分配成功显示：申请作业的起 始地址、申请長和内 存分配成功相符非法：输入内存分配 操作下的申请 呈为60显示：作业申谙昱 过大，分配失败显示：作业申请長过 大，分配失败相符3、调试分析：在调试过程中定义为作业分配主存的空间函教11x20时程序出现错误，主要原因是由 于for循环的编写出现错误，由于alloc2()与albc()的主要差异就在于for循环，昱终经过査阅 课本从根本上

19、理解丁首次适应算法和循环首次适应算法的本质区别,最终使错误得以解决程 序正确运行。在编写alc30时，引入数组将总体情况分为大的两种，并在数组中又分为两 种小的情况。但是在誇虑所有大于所要求的空闲区放入数组时,落拉了只有一个数组的情况, 最终经过自己的仔细检査和同学的帮助使错误得以解决。在编写主存回收函SCLfrCCo时由于对在空闲表中的适当位直迸行插入时的情况誇虑不 全面，使得其中一种情况落拉导致编程出现错误，最后经过仔细阅读课本和同学的帮助并在网上收索相关的知识使得错误得以解决。在编写对空闲区表中的空闲区调整旳函教adjust () 时也多次出现错误，是终经过同学的帮助和在网上收索相关知识

20、，借鉴别人的算法使得第 误得以解决。五、用户手册本系统是用C+语言编写的，使用MiCroSt)FI ViSUal C+平台开发，不雲要安装。经运 行验证本程序可正常运行。具体使用步骤如下：(I) 经过编译.链接无误后便可正常运行，出现主界面根据主界面上的显示选择所要使用的动态分区分配算法。(2) 选择所要使用的算法之后就会显示所要迸行的各项操作如下 若选择1分配内存则根据界面提示输入作业的申清星则会弹出申请作业的起 始地址和作业的申请長CC *C: VDociiBeiits and SettingsVAdainiStratOr桌面Debugwo. exe*Jnl 操的起量功 的业的请击 e作业

21、申配 、店分 请 若选择2回收内存则界面提示输入释放区的起始地址和释放区的大小，输入 之后则会自动显示空闲区表的状态c *C : VDocuBents and SettingsVAdaini StratOr桌面Debugwo. exe*-InlX请jfe的操宦:2请W放区的起始地址：20请输入释放区的大小：38I 若选择3査看空闲区表则输入3之后界面就会自动显示当前的空闲区表的状 态 若选择O退出则系统会回到刚开始的初始界面状态重褊先择动态分区分配的 算法-ll jnc *C : Bocuents and SettingsYdainiStratorMJebugVro. eze* 请输入您的操作

22、；0动态分区分配方式的模拟P 1首次适应算法2循环首次适应算法3最佳适应算法 卞W)(MM)()(呉)()()(Xx帧軸呉)G)G)G)G)C)C XXXXXXXXMXMXXMXXX 请选择分配算法；m程序清单/車动态分区的分配与回收演示程序*/#includc #includc #dcfinc N 5it Stait;存放首址StrUCt frccarca *te义一个空闲区说明表结构，并初始化变長int ID;/*分区号*7int startaddress;/*空闲区始址*/int size；/*空闲区大小*/int state;/*空闲区状态:0为空表目，1为可用空闲块*/febk)ck

23、(N=1r2020J ,2,80,50,350,30,4,300,30,1,5,500,10;/*定义为作业分配主存空间的函数allocO,首次适应算法调用*/int alloc(int alyarca)int i,lag=O;*aplyarca为作业申谙昱,tag为检査是否有满足作业需要的空闲区的标志*/for(i=0;i applyarca)& Ucrbh)Cki.startddwss=frcxbh)ckisMr 匕 KidrcrSS+applyarc; frccbk)cki.si2c=frccbl0cki.sizc-aplyarca;tag=l; 严有满足条件的空闲区时，tag I*/r

24、eturn frccblock0.startaddress-applyarea; /*返回为作业分配的主存地址*7if(frccblocki.state=1& frccblock i.sizc=applyarca)frccblocki S tatc=0;Iag= 1；/*有满足条件的空闲区时，Mg貫I*/return FrCCbk)Cki.Startaddrcss;/琢返回为作业分配的主存地址3*7 if(lag=O)return -1;广没有满足条件的空闲区，分配不成功，返回-1*/广定义为作业分配主存空间的函数alloc20,循环首次适应算法调用*/ int aoc2(int applya

25、rca,int S) *applyarea 为作业申 1*/int i,tag=O;*tag为检査是否有满足作业雲要的空闲区的标志玫/for(i=s;icki.sizcapplyarca)frccblocki.startaddress=frccbl()cki.startaddrcss+alarca; frccbl()cki.si2c=frccbl0cki.sizc-aplyarca;Iag= 1;广有满足条件的空闲区时，tag 1*/Start= frccblocki.s tartaddrcss-applyarca;return i;CISCif(frccblocki.state=1&frcc

26、blocki.sizc=applyarca)frccbkcki.statc=0;Iag= 1；/*有满足条件的空闲区时，tag 1*/StarI=frccblocki.startaddress;/返回为作业分配的主存地址*/return i;if(tag=O)return -1;/球没有满足条件的空闲区，分配不成功，返回屮/球定义为作业分配主存空间的函数alk)c30,佳适应算法调用*/int alloc3(int applyarea)*applyarea 为作业申请县*7int i,k,h,fMg=0j=0;*tag为检査是否有满足作业需要的空闲区的标志*/int aN;StrUCt frc

27、carca min;StrUCt frccarca mid;for(i=0;il*/return frccblockp.startaddress；/球返回为作业分配的主存地址j17for(i=0;iaplyarca)aj+=i;h=a0;mill= FrCCbloCk h;/min.startaddrcss=& UCrblQCk h. StarUiddruss;/min.sizc=frccblockh.sizc;/min.statc=frccbk)ckl.statf()r(k=l;kj;k+)h=ak;if(frccblockl).sizctagl =0,tag2=0,tag3=0,j;Pri

28、nlff请输入释放区的起始地址:”)；SCanF(”d”,&s);/*输入释放区的开始地址*/PrimF(M请输入释放区的大小:H);SCanF(”广输入释放区的大小a7PrintfC*回收内存后空闲区表的状态如下*n);for(i=0;iN;i+)if(frccblocki.startaddrcss=s+l& &frccblock0.State=I)l=l+frccblocki.sizc;IagI = 1；/*有与释放区高地址邻接的空闲区，UgI直1*/for(j=0;jckj.statc=l)frccblocki.statc=O;frccblockj.sizc=frccbk)ckj.siz

29、c+l;tag2=l;/*有与释放区上下都邻接的空闲区，tag2 1*/break;if(tag2=0)/*无与释放区高低地址邻接的空闲区*/FrCCbIocki.Startaddrcss=S;FrCCbIocki.sizc=l;break;if(iagl=O)厂无与释放区高地址邻接的空闲区，并检査是否低地址有邻接空闲区巧 for(i=0r(j=O;jN；i+)if(frccblocki.staic=0)/*找一个空表目,将释放区放入表中球/ frccblockj.Startaddrcss=S;frccblockj.sizc=l;frccblockj.statc=1;break;厂定义对空闲区

30、表中的空闲区调整的函数adjust,使空闲区按始地址从小到大排列，空表目放在最后面V(Md adj ustiiit i,j;StrUCt frccarca middata;for(i=0;iN3+)/*将空闲区按始地址顺序在表中排列*/for(j=0;jfrccbl)ckj+l.startaddress) middata.startaddrcss=frccblockj.startaddrcss; middata.sizc=frccblockj.sizc;middata.statc=frccblockj .state; frccblockj.startaddrcss=frccbk)ckj+l.s

31、tartaddress； frccbl0ckj.sizc=frccbl()ckj+l.si2c;frccblockj.statc=frccbl()ckj+l.statc; frccblockj+l.staruddrcss=middata.startaddrcss; frccblockj+l.sizc=middata.sizc;frccblockj+l.statc=middata.statc;for(i=0;iN;i+)*将空表目放在表后面*/for(j=0;jN;j+)if(frccblockj.stale=()&frccblock j+1 . state=1)middata.startadd

32、rcss=& UUbl(Xkj. StarMddruss; middata.sizc = & CCbk)Ck j.size;middata.statc=fr CXblockjsmtc:; frccblocki.startaddrcss=frccbk)ckj+l.startaddress；frccbk)ckj.sizc=frccbl()ck+l.sizc; frccblockj.statc=frccblockj+l.state;frccblockj+l.startaddrcss=middata.startaddrcss;frccblockj+l.sizc=middata.sizc; frccbl

33、ockj+l.statc=middata.statc;/定义打印空闲区说明表函数：RrintO*/ttfctfc呎 nnn Itri 口 -HPPPVoid Print0n*);IDStartSiZCStatC n);n);for(i=0;icki.startaddress, &uubbcki.si2cr,frcxbl()di .state)；Prjntf(”I1 n);/首次Void FirsCfitQint applyarca,start;PrintfetiW输入作业的申请呈:”)；scanf(,t%d1l,capplyarca);/* 输入作业的申请星 */Start=alloc(app

34、lyarca);/*调用alloc()函数为作业分配空间,Start为返回的始地址琢/if(start=-l)*;IlIQCo分配不成功时，返卧 1*/Printf(”作业申谙長过大，空闲区表中的存储空间无法满足，分配失败n”)；CISCadjust();PrintfC申请作业的起始地址为start);Printfc 作业的申谙長为 %dn,aplyarca);PrintfC内存分配成功护);/循环首次VOid Ncxt_fitQint applyarca3=0;Printf(”请输入作业的申请長：”)；SCiUlf(n%dH,&applyarca);/*输入作业的申请星球/ if(i=N-l

35、)i=alloc2(applyarca,i);if(i=-l)i=O;CISC if(iut*动态分区分配方式的模拟n;CoUt,* cout* 1)首次适应算法2)循环首次适应算法3)舅佳适应算法*n,t;CoUtch;int choice; /操作选择标记CoUtm*1:分配內存couichoicc;if(choicc=l) / 分配内存int ch;if(ch=l)First_fitO；if(ch=2)Ncxl_fkO；CISCBusi;ClSC if(choicc=2) / 回收内存sctfrccO；adjust。;Print0；ClSC if(choicc=3) Print0；/显示空闲分区表CISC if(choicc=0) goto loop; /退出ClSC /输入操作有误COUtVV”输入有误，请重试Wmdl; continue;七、体会与自我评价本次操作系统课程设计让我学握了动态分区分配的实质:动态分区分配是根据进程的实 际需要,动态地为之分配内存空间。分区管理是满足多道程序运行的最简单的存储管理方式, 为了实现对内存空间的有效管理，雷要采取一些方法和策路，用以实现对内存空间的分配或 回收。在实现可变分区分配时，将涉及