2023年操作系统实验报告4.pdf

《2023年操作系统实验报告4.pdf》由会员分享，可在线阅读，更多相关《2023年操作系统实验报告4.pdf（34页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、计算机科学与应用系课程设计报告操作系统原理姓名学号指导教师专业计算机科学与技术S日期20 23年 6 月5 日成 绩题目动态分区分派算法的模拟指导教师评语目录1题 目 简 述.错误!未定义书签。2需求分析.错误!未定义书签。2.1设计思想。错误!未定义书签。2.2规定.错误!未定义书签。2.3任务.2.4运营环境.2.5开发工具.3概要设计与具体设计错误!未定义书签。错误!未定义书签。错误!未定义书签。错误!未定义书签。3.1 系统流程图。错误!未定义书签。3.2算法流程图。错误!未定义书签。4编码与实现.错误!未定义书签。4.1 数据结构和算法设计。错误!未定义书签。4.2程序调试与截图.错

2、误!未定义书签。5课程设计总结18。参考文献.错误!未定义书签。附录。错误!未定义书签。动态分区分派算法的模拟1题目简述动态分区分派是根据进程的实际需要，动态地为之分派内存空间。在实现可变分区分派时，将涉及到分区分派中所用到的数据结构、分派算法和分区的分派与回收操作。常用的数据结构有空闲分区表和空闲分区链两种，分区分派算法重要有初次适应算法、最佳适应算法、最坏适应算法等。本次实验通过C 语言进行编程调试并运营，形象地表现出动态分区分派方式，直观地展示了初次适应算法、最佳适应算法、最坏适应算法对内存的释放和回收方式之间的区别。加深了我对三种算法优缺陷的理解,帮助我了解一些数据结构和分派算法，进一

3、步加深我对动态分区存储器管理方式及其实现过程的理解。重要问题在于，如何解决三种算法对内存的释放和回收空间的表达。动态分区分派又称为可变分区分派，这种分派方式并不是事先将主存划提成一块块的分区，而是在作业进入主存时，根据作业的大小动态地建立分区，并使分区的大小正好适适应作业的需要。因此，分区中的大小是可变的，分区的数目也是可变的。2需求分析2.1设计思想(1)初次适应算法(First f i t)空闲分区链以地址递增的顺序连接。在分派内存时，从联手开始顺序查找，直到找到一个大小能满足规定的空闲分区为止；然后再按照作业大小，从该分区划出一块内存空间给请求者,余下的空闲分区仍然留在空闲链中。若从链首

4、直至链尾都找不到一个能满足规定的分区，则本次内存分派失败。(2)最佳适应算法(Be s tf i t)它从所有空闲区中找出能满足作业规定的、且大小最小的空闲分区，这种方法能使碎片尽量小。为适应此算法，空闲分区表(空闲区链)中的空闲分区要按从小到大进行排序，自表头开始查找到第一个满足规定的自由分区分派。该算法保存大的空闲区，但导致许多小的空闲区。(4)最坏适应算法(W o r s t f i t )最坏适应分派算法要扫描整个空闲分区或链表，总是挑选一个最大的空闲分区分割给作业使用。该算法规定将所有的空闲分区按其容量从大到小的顺序形成一空闲分区链，查找时只要看第一个分区能否满足作业规定。优点是可使

5、剩下的空闲分区不至于太小，产生碎片的几率最小，对中、小作业有利,同时该算法查找效率很高。(4 )内存回收(F r e e )将释放作业所在内存块若改为空闲状态，删除其作业名，变为空。然后判断该空闲块是否与其他空闲块相连,若释放的内存空间与空闲块相连时，则合并其为同一个空闲链表，同时修改开始地址及分区大小。2.2 规定(I)用 C+语言实现程序设计；(2)运用结构体进行相关信息解决；(3)画出查询模块的流程图；(4)界面和谐(良好的人机互交)，程序要有注释。2.3 任务(1)掌握为实现多道程序并发执行，操作系统是如何通过作业调度选择作业进入内存；(2)系统如何为进入内存的作业分派内存空间，实现多

6、道作业同时驻留内存，就绪进程队列中的多个进程是如何以分式方式共享C P U,作业运营完毕离开系统时，系统如何进行内存回收，计算进程周转时间；(3)画出所有模块的流程图；编写代码；(5)程序分析与调试。2.4 运营环境(l)WINDOW S20 2 3/X P 系统(2)M i c r oso f t V i s u a l C+6.0 编译环境2.5 开发工具C+语言本程序采用C语言编写，在 Window s 下的V i sual C+环境下编译,模拟可变分区存储管分派与回收。计与具体设计程图系统流程图图3.1.1系统流程图3.2算法流程图3.2.1 内存分派流程图图 3.2.1 内存分派流程

7、图3.2.2.初次适应算法流程图图3.2.2 初次适应算法流程图3.2.3 最佳适应算法流程图图 3.2.3 最佳适应算法流程图3.2.4 最坏适应算法流程图图 3.2.4 最坏适应算法流程图3.2.5 内存回收流程图图 3.2.5 内存回收流程图4编码与实现4.1数据结构和算法设计相关数据结构定义：空闲分区结构：t y pe d e f s t r u c t f r e earea 0线性链表结构：t y p e d ef st r u c t Du LN o d e()带头结点内存空间链表结构：St a t us Initb 1 ock()内存分派：S t atus a 1 1 oc()

8、显示主存:vo i d show()测试类(主函数类):c 1 a ss T e s t Fo r MemMana g e4.2程序调试与截图1)首界面二 二 二m 懑 懑 熊 籁 懑1)首次适应算法2)最佳适应算法(3 最坏适应算法卜 青 选 容 分 者 己 算 法：.2)初次适应算法测试数据：为作业申请空闲区8 0 0KB。作 业 1 申请资源lOOkb,作业2 申请资源12 0 k b,作业3 申请资源1 3 O kb,作业4 申请资源1 4 0 k b,释放作业1 和作业3,作业5 申请资源160 k b,这时,按照表从头开始查询，第一个找到满足条件的就停止查找,并分派资源。运营结果如

9、下图所示：2：哂收内存。：退 出 1首 次 适 应 算 法 2最 佳 适 应 算 法 3最坏适应算法号 变 垮 啰 漫 空1,请簸入.好臊祚一请输入器业区号，1请输入需要分配的主存大小（单位:KB：100分配成功!02北内收划退202次:存:1盘存栏区晅炳W嘉业要！/普你需需功1:3:入入人成配请请请分1：分配内存 2:回收内存3：查看分配 0：退 出版人祥业区号M 3隔人需要分配的主存大小（单位:KB,130刻成功!内收回退内森篇H分1戳翳内收回退20:1盘存用区珀讷W篇业要/幺你常需功1:3:入人人成配一一请请刀二1:3:入入人成配请请请分S内收回退203主 存 分 配 情 况:区 楼10

10、100 KBa已分配又_地大2100120 KBts已分配区地大区始区3220130 KB已分配54X地大区始区4350140 KB已分配2始地昴；4902：0：1哂收内存退由主H十月1:3:人入3）最佳适应算法测试数据:为作业申请空闲区800KBo作 业 1 申请资源10 5 k b,作业2 申请资源1 1 5k b,作业3 申请资源1 25kb,作业4 申请资源1 3 5 k b,释放作业2 和作业4,作业5 申请资源145kb,这时,在每次的分派内存中，总是找到既满足规定又是最小空闲分区,然后分派资源，这样,就避免了 “大材小用”的问题。运营结果如下图所示：1首 次 适 应 算 法 2最

11、 佳 适 应 算 法 3最坏适应算法青选择分配算法：21:3:入入入成配主0E主BE至0E个内翻翕”翳存一回退KK缶单工知.存1:3:入入入成一H里里R分田/翁你崔需功21S.存回退1:3:入入入成配主星星可介鬻的业要in回退回退世鳌冬酉潘日也医鲁铲程需功1:3:入入入成配青生R青介鬻的业要！宗.你律需功1:3:入入入成配青主呈R分回退内收内收202内收20内收20S内收3大5次201：至尊内存 2:增收内存3：查看分配。：退 出青 输 入 您 赫 根：3H+4）最坏适应算法测试数据：为作业申请空闲区8 0 0 K B。作 业 1申请资源8 0 k b ,作 业 2申请资源1 0 O k b,

12、作业 3申请资源1 2 0 k b，作业4申请资源1 4 0 k b ,释放作业1 和作业3,作业5申请资源1 6 0 k b,这时，在扫描整个空闲分区链表时，总是找到既满足规定又是最大空闲分区，然后把它分割给作业。运营结果如下图所示：回退号一BK081内收鬻的业要！小1:3:入入入成i青青青分d208内收回退202大盘WF保备需功窜内收回退鬻的业要！1_你崔需功203次1:3:入入入成M1:3:入入入成配2青青青分Y8内收回退204:号一存栏区的业要！/冬一体很需功1:3:入人入成配2配青青青分0青青青分苴内收回退BK位单酱的业要！你番需功1:3:入入入成配青青青分201:3：查第青输入您的

13、;2：哂收内存0：退 出3+O心+*+区始区主 存 分 配 情 况次尘X地大区始区心谕区分也底心区地大区始区,尘区地大区始区:主 存 分 配 情 况Free080 KB空 闲区 号：2始地址：80区大小：100 KB急 已 分 配4区 号：Free坝台地址：180:区大尘：120 KB，匕、：空 闲又一地大区始区4300140 KB已分配440160 KB已分配,区 号：Free始 地 址：600,区大小：200 KB恚：空 闲5课程设计总结为期五周的课程设计，对于我个人来说是相称有难度的。在设计的过程中，有很多问题不是很清楚,所以做起来就就很困难，刚开始的时候都有点无从下手的感觉。很多时候在

14、碰到问题时，基本知识都了解，但是就不知道怎么才干把它们都整合到一块，也就是说知识都是很零散的，没有一个完整的系统。并且，又由于基础知识不牢固，使得我在这次的课程设计中感到更加力不从心。在设计的过程中，每走一步就会发现，思绪想出来很容易，但涉及到实现的时候，总是有点手无足措。对于本次的课程设计，里面尚有很多需要改善的地方。一个程序的顺利出炉，少不了反复地调试和修改。在调试的过程中，总是会发生很多错误，但在解决这些错误的时候，开始很模糊的概念就会变得越来越清楚。其实很多错误都是很类似的，只要解决了一个，其余的就会迎刃而解了。“千里之行，始于足下”，通过这次课程设计,我深深体会到这句千古名言的真正含

15、义，我今天认真的进行课程设计，学会脚踏实地迈开这一步，就是为明天能稳健地在社会大潮中奔跑打下坚实的基础。这次的课程设计,使我树立了对的的设计思想，培养实事求是、严厉认真、高度负责的学习作风，加强操作能力的训练和培养严谨求实的科学作风更尤为重要。在这次设计过程中,充足体现出自己单独设计课程的能力以及综合运用知识的能力，体会了学以致用、突出自己劳动成果的喜悦心情，从中发现自己平时学习的局限性和薄弱环节，从而加以填补。通过本次实验，我掌握了实现多道程序并发执行，操作系统是如何通过作业调，选择作业进入内存以及系统是如何为进入内存的作业分派内存空间，实现多道作业同时驻留内存，就绪进程队列中的多个进程是如

16、何以分式方式共享CPU,作业运营完毕离开系统时，系统如何进行内存回收。最后，感谢我们的荆立夏老师，老师严谨细致、一丝不苟的作风将会一直是我工作、学习中的楷模；老师循循善诱的教导和不拘一格的教学思绪给予我无尽的启迪;这次课程设计的每个实验细节和每个数据，都离不开老师您的细心指导。而您开朗的个性和宽容的态度，帮助我可以很顺利的完毕了这次课程设计。祝愿老师您在以后的工作和生活中继续保持健康的身体和快乐的心情,再次感谢!同时，也很感谢对我帮助过的同学们，谢谢你们对我的帮助和支持，让我感受到同学的友谊和温暖。参考文献1 李 玲 玲.C语言程序设计 M .辽宁大学出版社，2 0 2 3.1谭浩强.程序设计

17、基础与C语 言.沈 阳：辽宁大学出版社,20 2 3.1 3 严蔚敏、吴伟民等.数据结构（C语言版）.北京:清华大学出版社，202 3.4汤子瀛、梁 红 兵 等.计算机操作系统第三版.北京:西安电子科技大学出版社,2 0 23.附录源代码#i n c l u de#i nc l u d e#d efine F r ee 0/空闲状态#defi n e Bu s y 1 /己用状态 define OK 1 完毕#d e f i ne E R R OR 0/犯错#d e fine MA X_ 1 eng t h 800 最大内存空间为 800K Bt yp e def i n t S t a t

18、u s;t ype d e f s t r u c t fr eea r ea/定义个空闲区说明表结构(i n t I D;分区号Io n g s i z e;/分区大小I o ng a d d r es s;分区地址i nt s t a t e;状态 E l e mT ype；/-线性表的双向链表存储结构-t ypedef s t r u c t D u L N o de/d o u b 1 e l in k e d l is t(E 1 emT yp e da t a ；s t r u c t D u L N o de*pr io r;前趋指针s t r u c t Du LN o de*

19、n e xt;后继指针 Du LN o de,*Du Link Li s t；Du L ink Li s t b 1 o c k _ fir s t;/头结点Du Link L i s t b l o c k _ l a s t；/尾结点S t a t u s a l l o c(int)；内存分派S t a t u s fr eed nt)；内存回收S t a t u s F i r s t f it (i nt,i n t );初次适应算法S t a t u s B e s t _ f i t(i n t,i n t);/最佳适应算法S t a t u s W o r s t _ fit

20、(in t ,int);/最坏适应算法v o i d s h o w();查看分派S t a t u s I n it b l o c k()；/开创空间表/-开创带头结点的内存空间链表-S t a t u s Init b l o c k()(b l o c k _ fir s t=(D u Li n k Li s t)ma l l o c(s izeo f(Du LNo de);b l o c k _ l a s t=(Du L i n k L i s t )ma l l o c (s i z e o f(Du LNo d e);b 1 o c k _ f i r s t-pr i o r

21、 =N UL L ;b l o c k f ir s t-n e xt=b l o c k _ 1 a s t；b l o c k _ l a s t-pr i o r =b l o c k _ f i r s t ;b l o c k _ l a s t -next=NU LL;b io c k _ l a s t da t a.a ddr e s s=0;b l o c k _ l a s t da t a.s i z e=MA X_ l eng t h；b l o c k 1 a s t da t a.I D =0；b l o c k _ l a s t-da t a.s t a t e

22、=F r e e;r et u r n OK;S t a t u s a l 1 o c (i n t c h)i n t ID,r e q u es t ;c o u t vv请输入作业（分区号）：”c i n I D ；c o u t V C”请输入需要分派的主存大小（单位:K B）c inr e q u es t ;i f(r eq u es t 0|r e q u e s t=0)c o u tV分派大小不合适，请重试！e n d l;r et u r n E R R O R;if(c h=2)/选择最佳适应算法(if(Bes t _ fit (ID,r e q u es t)OK)。

23、c o u t V 分派成功!e n d 1 ;e Is e。o c o u t V”内存局限性，分派失败！endl;r e t u r n OK;)el s e/默认初次适应算法(if(F ir s t _ fit(l D,r eq u e s t )=0 K)c 分派成功！“V endl;el s e次:o u t V“内存局限性，分派失败!H e n d 1；r e t u r n O K;)if(c h=3)/选择最坏适应算法(i f(Wo r s t _ fit(ID,r e q u es t )0 K)c o u t 分派成功!”e n d 1;e 1 s ec o u t内存局限

24、性,分派失败！endl;r e t u r n O K ;)el s e 默认初次适应算法(i f(F i r s t f i t (ID,r eq u e s t)=0 K )*c o u t 分派成功！endl；el s ec o u t ”内存局限性,分派失败！da t a .ID=ID;t emp-d a t a .s i z e=r e q u es t;t e m p d a t a.s t a t e=B u s y;D uL No de*p=b l o c k fir s t-next；w h i 1 e(p)(if(p-da t a.s t a t e=F r ee&p-d

25、a t a .s ize=r e q u e s t)(。/有大小恰好合适的空闲块p-d a t a.s t a t e=Bu s y;p da t a .I D=I D;r et u r n OK;b r ea k；)i f(p-da t a .s t a t e=F r ee&p-da t a.s i zer e q u e s t )(有空闲块能满足需求且有剩余”t em p-p r i o r=p-pr io r;t emp-next =p；t e mp-d a t a.a d d r es s =p d a t a.a d d r es s;p-pr i o r-next=t emp

26、;p-pr io r =t emp；p-d a t a.a d d r es s=t emp-d a t a.a ddr e s s+t emp d a t a.s ize；p-da t a.s i z e=r eq u es t;r et u r n OK；b r ea k；p=p-ne x t;r e t u r n E R R O R ；1/-最佳适应算法-S t a t u s B e s t _ f it (i nt ID,int r e q u e s t)i nt c h;记录最小剩余空间Du Lin k L is t t emp=(Du Link Lis t )m a l l

27、o c(s i z eo f(Du L N o de);t emp da t a.ID=I D;t emp-da t a .s iz e=r e q u es t;t emp d a t a.s t a t e=Bu s y;D u LN o de*p=b 1 o c k _ f i r s t n e xt;D u L N o d e*q=N U L L;记录最佳插入位置w h i 1 e(p)初始化最小空间和最佳位置i f(p-da t a.s t a t e=F r ee&(p-d a t a.s i z e r eq u es t|I p d a t a.s i z e=r e q u

28、 e s t)q 二 P；c h=p-d a t a.s izer eq u es t;b r ea k ;)p=p-n e xt;)w h i 1 e(p)(i f(p-da t a.s t a t e=F r ee&p-da t a.s iz e=r e q u e s t)。/空闲块大小恰好合适p-da t a.I D=I D;p-d a t a.s t at e=B u s y;r e t u r n OK;b r e a k;)if(p-da t a.s t a t e=F r e e&p-da t a.s i z er e q u e s t)(/空闲块大于分派需求i f(p-d

29、a t a.s ize-r e q u es t da t a .s i z e-r eq u es t ;/更新剩余最小值q=P；更新最佳位置指向)p=p-ne x t ；)if(q=NU LL)r e t u r n E R R O R;没有找到空闲块e Is e(“/找到了最佳位置并实现分派t emp-pr io r=q-pr io r ；t emp-n e xt=q;t emp-da t a.a d d r e s s=q -d a t a .a d dr e s sq-p ri or-n e x t =t emp;q-p r i o r=t emp;q da t a .a ddr e

30、s s d-=r e q u es t ;q-d a t a.s ize=c h;re t u r n O K;)/-最坏适应算法-S t a t u s Wo r s t _ f it (int ID,i nt r eq u es t )(int c h;记录最大剩余空间D u L ink Lis t t e m p=(D u L in k Li s t )m a 1 l o c (s it e mp-d a t a.I D=I D；t emp-d a t a .s iz e=r e q u es t ;z e o f(Du LNo d e);t e mp-d a t a.s t a t e

31、=B u s y;D u LNo de*p=b l o c k _fir s t -n e x t;Du LNo d e*q=NU LL;记录最佳插入位置w h i 1 e(p)初始化最大空间和最佳位置(i f(p-d a t a.s t a t e=F r e e&(p-d a t a.s i z er eq u es t|I p-da t a.s ize=r eq u es t)q=P;c h =p-da t a.s i z e-r eq u es t；b r ea k；)p=p-n e x t;)w h il e(p)(i f(p-d a t a.s t a t e=F r e e&p-

32、da t a.size=r eq u es t)8 空闲块大小恰好合适p d a t a.I D=I D；p-da t a.s t a t e=B u s y；r et u r n O K ；b r e a k;)if(p-d a t a.s t a t e=F r e e&p-d a t a.s izer eq u es t)/空闲块小于分派需求if(p-d a t a.s i z e-r eq u e s t c h)/剩余空间比初值还大c h=p da t a.s i z e-r e q u e s t；更新剩余最大值q=P；/更新最佳位置指向)p=p-next;)if(q=NU LL)

33、r e t u r n E R R OR;没有找到空闲块el s e(M/找到了最佳位置并实现分派t emp-p r io r =q pr io r；t emp-next=q;t e m p-d a t a.a d d r es s=q d a t a.a ddr e s s;q-p r i o r-next=t emp;q-pr io r =t emp;q -da t a.a ddr es s+=r e q u es t；q da t a.s ize=c h；r e t u r n OK;)/-内 存 回 收S t a t u s fr e e(i nt I D)Du LNo d e*p=b

34、 l o c k _ fir s t;w h il e(p)(if(p d a t a.I D=ID)(p-da t a .s t a t e二F r ee;p da t a.ID=F r e e;i f(p-pr io r-da t a.s t a t e=F r ee)与前面的空闲块相连Ip-p r io r -d a t a.s ize+=p-d a t a,s iz e;p-pr i o i next=pne x t;p-ne x t -pr io r =p-p r i o r ;)i f(p-next-da t a.s t a t e 二 二F r ee)/与后面的空闲块相连p-da

35、 t a.s ize+=p-ne x t-da t a.s ize;p n ex t -n e x t-p r io r=p；p next=p-next next;b r ea k;)p=p-n e x t;r et u r n OK;/-显示主存分派情况-v o i d s h o w ()c o u t V “+n”;c o u t +主存 分 配 情 况+n;c o u t nex t ;w h il e(p)c o u t da t a.I D=F r ee)c o u t?，F r e e*en d 1;e Is e c o u t da t a,ID en d 1 ;c o u t

36、 V ”起始地址：d a t a.a d d r es s e nd 1 ;c o u t da t a.s iz e K B，Z d a t a.s t a t e=F r ee)c o u t 空 闲 V e nd 1 ；el s e c o u t E l 分派e n d l；c o u t V next;)v o i d ma i n()i n t c h;算法选择标记c o u t 动态分区分派算法的模拟coutV *、n ；cou t H次 大 (1)初次适应算法(2)最佳适应算法(3)最坏适应算法*n”；cout c h；I ni tb lockO；/开创空间表i n t c h

37、 o i c e ；操作选择标记wh i le (1)(cout X*n”；cout *1:分派内存 2:回收内存*n；c out *3:查看分派 0:退 出 *n”;c O U t c h o i ce;i f (ch o i ce=l)a lloc(ch);/分派内存e lse i f (c h o i ce=2)/内存回收i n t I D;cout-请输入您要释放的分区号:“；c i n I D；f re e(I D);)e 1 se i f (ch oi ce=3)s h o w()；/显示主存e ls e i f (c ho i ce 二 二 0)b re a k：退出e lse /输入操作有误cout X 输入有误，请重试！e nd l;co n ti n u e ;)