动态分区管理的主存分配模拟设计方案最优适应法、最差适应法

PAGEPAGE14学号：0１2１0103４08０8课程设计题目动态分区管理的主存分配模拟设计--最优适应法、最差适应法学院计算机科学与技术学院专业计算机科学与技术专业班级计算机１０02班姓名刘浪浪指导教师杨克俭2013年１月2０日课程设计任务书学生姓名：刘浪浪专业班级:计科1002班指导教师:杨克俭工作单位:计算机科学与技术学院题目：动态分区管理的主存分配模拟设计-—最优适应法、最差适应法初始条件:１．预备内容:阅读操作系统的内存管理章节内容，理解动态分区的思想,并体会各分配算法的具体实施方法。２。实践准备:掌握一种计算机高级语言的使用。要求完成的主要任务:(包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）1。采用指定算法模拟动态分区管理方式的主存分配。能够处理以下的情形：⑴随机出现的进程ｉ申请jKＢ内存,程序能判断是否能分配，如果能分配,要求输出分配的首地址Fａddrｅss,并要求输出内存使用情况和空闲情况。内存情况输出的格式为：Fadｄreｓｓ该分区的首地址；Ｅａddrｅｓs该分区的尾地址Ｌｅn分区长度；Ｐｒｏcesｓ如果使用，使用的进程号,否则为０⑵主存分配函数实现寻找空闲区、空闲区表的修改、已分配区表的修改功能；２。设计报告内容应说明：⑴课程设计目的与功能;⑵需求分析，数据结构或模块说明(功能与框图)；⑶源程序的主要部分；⑷运行结果与运行情况分析；⑸自我评价与总结：=１\＊roｍani)你认为你完成的设计哪些地方做得比较好或比较出色;=２\*romaｎii）什么地方做得不太好,以后如何改正;=3＼＊romaniｉi）从本设计得到的收获(在编写,调试,执行过程中的经验和教训);=4＼*ｒoｍanｉv)完成本题是否有其他的其他方法(如果有，简要说明该方法);=5\*ｒomaｎv）对实验题的评价和改进意见，请你推荐设计题目。时间安排:设计安排一周：周1、周2：完成程序分析及设计。周2、周３:完成程序调试及测试.周４、周５：验收、撰写课程设计报告。（注意事项：严禁抄袭，一旦发现，抄与被抄的一律按0分记）ﻩ指导教师签名：年月日系主任（或责任教师)签名：年月日一、题目动态分区管理的主存分配模拟设计—－最优适应法、最差适应法二、主要任务１．采用指定算法模拟动态分区管理方式的主存分配.能够处理以下的情形:⑴随机出现的进程ｉ申请ｊKB内存,程序能判断是否能分配，如果能分配，要求输出分配的首地址Ｆaddress，并要求输出内存使用情况和空闲情况。内存情况输出的格式为:Faｄｄress该分区的首地址；Ｅadｄreｓs该分区的尾地址Len分区长度;Procesｓ如果使用,使用的进程号，否则为0⑵主存分配函数实现寻找空闲区、空闲区表的修改、已分配区表的修改功能；2.设计报告内容应说明：⑴课程设计目的与功能；⑵需求分析,数据结构或模块说明(功能与框图）;⑶源程序的主要部分;⑷运行结果与运行情况分析;⑸自我评价与总结:＝1\＊romanｉ）你认为你完成的设计哪些地方做得比较好或比较出色;＝2\＊ｒｏmａniｉ）什么地方做得不太好，以后如何改正；=３＼*roｍａniiｉ）从本设计得到的收获(在编写,调试，执行过程中的经验和教训);=4\＊romａnｉv）完成本题是否有其他的其他方法(如果有,简要说明该方法)；＝5\*romanｖ）对实验题的评价和改进意见，请你推荐设计题目。三、原理1.最佳适应算法:ﻩ它从全部空闲区中找出能满足作业要求的、且大小最小的空闲分区,这种方法能使碎片尽量小。为适应此算法,空闲分区表(空闲区链）中的空闲分区要按从小到大进行排序,自表头开始查找到第一个满足要求的自由分区分配。该算法保留大的空闲区，但造成许多小的空闲区。2。最坏适应算法：ﻩ最坏适应分配算法要扫描整个空闲分区或链表，总是挑选一个最大的空闲分区分割给作业使用.该算法要求将所有的空闲分区按其容量从大到小的顺序形成一空闲区链，查找时只要看第一个分区能否满足作业要求。四、实验分析 分区管理是把内存划分为若干大小不等的区域,除操作系统占用一个区域外，其余由多道环境下的各并发进程共享。动态分区法在作业执行前并不建立分区，分区的建立是在作业的处理过程中进行的，且大小可随作业或进程对内存的要求而改变。采用动态分区法，在系统初启时,除了操作系统中常驻的内存部分外，只有一个空闲区。随后，分配的程序将该区依次划给调度选中的作业或进程。下图给出了ＦＩＦO调度方式时内存的初始分配情况:进程Ａ1Ｋ进程B２Ｋ进程C4K进程D8K。。..．．。.OS进程A进程B进程Ｃ进程DOS进程Ａ进程B进程COS进程A进程ＢOS进程A五、实验功能设计1．数据结构说明本实验用到了结构体和类两种数据结构：结构体定义如下：sｔrｕctarｅa{iｎtｓtarｔ;ｉnｔｌeｎgｔh；inｔｓtate；struｃtarｅa*ｎeｘt;｝其中定义了四个数据成员，其中ｓtaｒt是内存块开始地址，ｌengｔh是内存块长度,sｔate是内存块使用状态,next是指向下一个内存块的指针。２程序函数模块说明主函数：intmａｉｎ（){inｔCｈｏice；／／开始循环ｗhilｅ(1）｛ﻩ systｅｍ（＂cls");ﻩﻩinit（）；ﻩﻩPrｉｎｔMeｍoryＳｔａte（ｈead）;ｐｒiｎtｆ(＂１.最优适应法\n”）； ｐｒiｎｔf(＂2.最差适应法＼n"）；ﻩﻩprｉntf(”3。退出程序\n”);ﻩﻩｐrintｆ(”选择分区管理方式：＂）;scaｎf（"％d”，&Choice）；//输入你所要的选项。为cｈoice的值sｗｉtch(Chｏice）{ﻩﻩ ｃasｅ1:BestFit(ｈｅad)；PｒintＭemorｙＳtaｔe(head);/／最优适应法ﻩﻩﻩ bｒeak； ﻩ ｃａsｅ2:ＷorstFiｔ（ｈeaｄ);ﻩﻩ ﻩPrｉntＭemoryStatｅ（hｅａd);/／最差适应法ｂreａk；ﻩﻩﻩｃase3:ﻩ ﻩﻩｐrintf（"正在退出程序．..\ｎ"）;ﻩ ﻩexｉｔ（0）； ﻩﻩﻩbreａk；ｄeｆault：pｒｉｎｔf（"Pleaseｉｎｐｕtarigｈtnuｍｂｅr！\ｎ”）；bｒeak；｝ﻩﻩｓystem（”pausｅ”）；}rｅｔurn０;｝最佳适应算法：voiｄBestFit（Arｅａ＊heａｄ）//装入作业,最优适应法｛ｉｎtflag=０;ｉnｔｌeｎgtｈtｅｍp；ﻩiｎtａ［3］；Ａrea＊lａsｔ=NULＬ;Area＊newＦrｅe＝NＵLL；ﻩAｒea＊Ｈ=NＵLL;ﻩinｔi；ﻩpｒｉｎｔｆ("请分别输入需要分配内存的3个作业内存长度\n”); ｆor（ｉ=1；ｉ＜=3；ｉ＋+） ｛ﻩﻩprｉｎtf（＂进程：％ｄ＂,i)；ﻩﻩｓcａｎｆ（"%ｄ”，＆a［ｉ-1]);ﻩ｝ﻩfｏr（i＝0;ｉ＜3;ｉ＋+)ﻩ{ﻩﻩiｎｔsｕm；ｉｎｔn＝0；ｉnｔb［1０］=｛－1，－１,—1，-１，-１，－1，—1，－１,-１，—1}；ﻩ intｄ＝0;ﻩＡｒｅa*Ｔasｋ＝ＮULL；ﻩﻩArea＊p=ＮＵLL;ﻩﻩlａst=hｅad-〉nｅxt;ﻩﻩｐ＝ｈeａd—>neｘt；ﻩﻩＨ=ｈead—〉nｅxｔ; whilｅ（H！＝NULL）ﻩﻩ{ﻩﻩﻩｉf（H－〉staｔe〉0）ﻩﻩﻩ{ﻩﻩﻩﻩＨ=H->nｅxt；ﻩ ﻩ}ﻩ ﻩｅlｓeﻩ ﻩ｛ﻩﻩﻩﻩb［ｎ］=H->leｎgth； ﻩﻩﻩH=Ｈ－＞next； ﻩﻩ ｎ++;ﻩ ﻩﻩ ﻩﻩ}ﻩﻩ} ﻩsum=ｂ[0］; fｏr（intｊ=1;ｊ＜n;ｊ＋+）ﻩﻩ{ ﻩﻩｉf(sｕm＜b[j]）ﻩﻩﻩﻩsuｍ=b[ｊ］;ﻩﻩ}/／ｓum取Ｂ［n］中的最大值ﻩﻩ ﻩﻩｉｆ(a［i]＞sｕｍ)ﻩﻩ{ ﻩﻩpriｎtf("a［％ｄ]作业过长,无法装入\n”，ｉ）； ﻩ｝ﻩ ｅlsｅﻩﻩ｛ﻩﻩﻩwhｉｌｅ(lａst！=NUＬL) ﻩﻩ{ﻩﻩﻩﻩiｆ(last－＞sｔate>0) ﻩﻩ ｌast=laｓt-〉ｎext； ﻩﻩﻩelseﻩﻩﻩﻩ｛ ﻩﻩﻩﻩiｆ(a[i］＞last—〉ｌｅnｇｔh）ﻩﻩﻩﻩﻩﻩｌａst=last-〉next； ﻩﻩﻩ elseif（a[ｉ］=＝ｌast－>leｎgth)ﻩ ﻩ ﻩ{ﻩﻩﻩ ﻩﻩTask=last； ﻩﻩﻩﻩﻩＴａsk－＞state=i;ﻩﻩﻩﻩﻩ bｒeaｋ;ﻩﻩﻩ ﻩ}ﻩ ﻩ ﻩelseiｆ（ａ［ｉ］＜laｓt—＞ｌengtｈ）ﻩﻩﻩﻩ {ﻩ ﻩﻩ ﻩif(Task==NＵＬＬ)ﻩﻩﻩﻩﻩﻩ｛ ﻩﻩ ﻩﻩﻩTaｓｋ＝ｌast;ﻩﻩﻩﻩﻩﻩ｝ﻩﻩﻩ ﻩelseif（Ｔasｋ—〉lengtｈ>ｌasｔ—>leｎgｔh） ﻩ ﻩﻩﻩ{ﻩﻩﻩﻩﻩﻩﻩTask＝lasｔ;ﻩ ﻩ }ﻩﻩﻩ ﻩｌast=ｌaｓt—>next；ﻩ ﻩﻩ｝ﻩﻩﻩ ｝ﻩﻩﻩ｝ﻩ ﻩiｆ（Task－〉lengｔh〉a［i］）ﻩﻩﻩ{ﻩﻩ leｎgtｈteｍp=Ｔask—＞leｎgth； ﻩﻩTask—＞ｌeｎgtｈ=ａ［i］；ﻩﻩﻩ Taｓk-＞staｔｅ=ｉ+1;ﻩﻩ ﻩnｅwFrｅｅ=(Arｅａ＊)malｌｏc（siｚeof(Ａrｅa）);ﻩ ﻩﻩnewＦree->ｎeｘt＝Task－>nｅxt；ﻩﻩﻩ ｎeｗＦｒee—>ｓtａrｔ=Ｔasｋ—〉start+Task-〉lｅngth;ﻩ ﻩｎeｗFｒeｅ—〉lengｔh=lengthｔeｍｐ—Ｔasｋ－>lｅngｔh； ﻩﻩﻩnｅｗＦreｅ－＞state=0;ﻩﻩ Tａsk—〉ｎｅｘｔ＝ｎewＦｒee;//成功插入nｅwFｒee节点ﻩ ﻩ} } ｝}最差适应算法:voｉdWorsｔＦｉt（Aｒea＊hｅaｄ）//装入作业,最差适应法{ｉnｔleｎgｔhtemｐ；ﻩiｎｔａ[３]；Aｒeａ*laｓt＝NＵLL；Areａ＊nｅwＦree＝ＮＵLL；ﻩinti； ｉｎtｎａmｅ=0；ﻩpｒｉntf（"请分别输入需要分配内存的3个作业内存长度\ｎ");ﻩfｏr(i=1;i<=3;i++）ﻩ｛ﻩﻩprintｆ（＂进程:％d”，ｉ）；ﻩ ｓcａnｆ（"%d"，&a[i－1]）；ﻩ｝ﻩfor（i=0;i〈３;i++)ﻩ｛ﻩAｒea＊Ｔａｓｋ＝ＮUＬL;ﻩﻩlast=ｈｅaｄ—＞next； ﻩTasｋ=NUＬL; ﻩwhｉlｅ（last！=NULＬ)ﻩ {ﻩﻩﻩｉｆ（lａsｔ-＞ｓｔａｔe〉０)ﻩﻩ ﻩlａsｔ=laｓt－>neｘt；ﻩﻩ elseﻩﻩﻩ{ﻩﻩﻩ if(Tａsk＝＝NＵLL）ﻩ ﻩﻩ Taｓk=lａst;ﻩ ﻩﻩｉf(lasｔ-〉lengｔｈ>Tａsk－>ｌeｎｇtｈ)ﻩﻩﻩﻩﻩTasｋ=lａst;ﻩﻩﻩﻩlasｔ=last-〉ｎｅxｔ；ﻩﻩﻩ}／/tａsk指向lengｔh最大的那块 ｝ﻩﻩif（a[ｉ]>Tａｓk—＞leｎgｔh） ｛ ﻩﻩprｉnｔｆ(”a[％d］作业过长,无法装入\n",i）；ﻩﻩ}ﻩ ｅｌｓeﻩﻩ｛ﻩﻩﻩif(Task-＞leｎgｔh==a［i］)ﻩﻩﻩ｛ﻩ ﻩTask—>sｔate=ｉ＋1；ﻩ ﻩ｝//等于的话直接装入ﻩﻩ if(Tasｋ-〉ｌengｔh>a［i]）ﻩﻩﻩ｛ﻩ lengtｈtｅｍp＝Ｔａsk—>lｅngth；ﻩﻩﻩﻩＴaｓｋ—〉ｌengｔh=ａ［i］;ﻩﻩﻩﻩTａsk—〉ｓtaｔｅ=i+1;ﻩﻩﻩ ｎeｗFrｅｅ=（Ａrea*)maｌｌoc（sｉｚeof（Areａ））;ﻩ ﻩﻩｎewＦree－＞next=Ｔａｓｋ—>next; ﻩﻩｎｅwＦｒee－〉starｔ=Task-＞sｔart+Task－〉lengtｈ； ﻩﻩﻩｎｅｗFree－>length=ｌｅngthteｍｐ—Taｓk—＞leｎｇtｈ；ﻩﻩﻩﻩneｗＦree-〉ｓtaｔe=0；ﻩﻩ ﻩＴasｋ—〉next=ｎeｗFree；/／成功插入neｗＦrｅe节点ﻩﻩﻩ｝ ﻩ}ﻩ}}3.程序的流程图最优适应法和最差适应法的流程图一样,如下:请求SIZE大小的分区从空闲区表第一表目顺序查找从空闲区表第一表目顺序查找表目查完？表目查完？是无法分配否无法分配该空闲区的该空闲区的长度≥SIZE？取下一表项否取下一表项是该空闲区的长度=该空闲区的长度=SIZE？从该空闲表中截取所需大小，修改调整可用表否从该空闲表中截取所需大小，修改调整可用表是从可用表中移去该表目，调整可用表从可用表中移去该表目，调整可用表返回分配起始地址返回分配起始地址六、开发平台开发平台:wｉndoｗｓ7开发软件：ｖｉsｕalstuｄio201０开发语言:C＋＋七、运行结果与运行情况分析运行源程序得到以下运行结果：输入1,选择最优程序法，并输入作业需要的内存块大小，运行结果如下:输入2之后，选择最差适应法，并输入相应作业需要的内存块的大小，运行结果如下：当输入作业内存块大于最大内存块时，得到以下结果：八、自我评价与总结ﻩ本次的课程设计我做的题目是动态分区式管理的模拟设计中，采用的是最佳适应算法和最差适应算法,其实最差适应法和最优适应法的原理很相近,一个是先把内存块按照从小到大的顺序进行排列,另一个正好相反，在理解上没什么障碍。因此在进行课程设计的时候少了更多的困难，在原理上有个正确的认识，在做程序设计的时候就得心应手了。ﻩ在程序设计的过程中遇到