《循环首次适应的动态分区分配算法模拟.doc》由会员分享，可在线阅读，更多相关《循环首次适应的动态分区分配算法模拟.doc（17页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、课程设计报告课程设计题目：循环首次适应的动态分区分配算法模拟 专 业：计算机科学与技术班 级：10204102姓 名：谱学 号: 10204102指导教师: 高小辉 2013年 1 月 11 日目 录一循环首次适应算法 3 1. 概述 3 2需求分析3 二实验指导4 1.基本思想42数据结构4三运行环境6四流程图6五循环首次适应算法代码5六调试结果11七、总结14八参考文献14一 循环首次适应算法 1. 概述：该算法是由首次适应算法演变而成的。在为进程分配内存空间时，不再是每次都从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直至找到一个能满足要求的空闲分区，从中划出一块的请
2、求大小相等的内存空间分配给作业。为实现该算法，应设置一起始查找指针，用于指示下一次起始查询的空闲分区，并采用循环查找方式，即如果最后一个（链尾）空闲分区的大小仍不能满足要求，则返回到第一个空闲分区，比较大小是否满足，找到后，应调整起始查询指针。2. 需求分析了解动态分区分配中使用的数据结构和分配算法，并进一步加深对动态分区存储管理方式及其实现过程的理解。采用首次适应算法的动态分区分配过程alloc()和回收过程free()。空闲分区通过空闲分区链表来管理，在进行内存分配时，系统优先使用空闲区低端的空间，即每次分配内存空间是总是从低址部分开始进行循环，找到第一个合适的空间，便按作业所需分配的大小
3、分配给作业。作业完成时，需要释放作业所占空间，此时要考虑到四种情况：(1)回收区与插入点的前一个空闲分区相邻接。此时将二者合并，修改前一分区的大小。(2)回收区与插入点的后一空闲分区相邻接，将二者合并，用回收区的首址作为新空闲区的首址。(3)回收区同时与插入点的前后两个空闲分区相邻接，三者合并，使用前一空闲分区的表项和首址。(4)回收区单独存在。二、实验指导1基本思想动态分区是指系统不预先划分固定分区，而是在装入程序的时候划分内存区域，使得为程序分配的分区大小恰好等于该程序的需求量，且分区的个数是动态的。显然动态分区有较大的灵活性，较之固定分区能获得好的内存利用率。2数据结构动态分区管理可以用
4、两种数据结构实现，一种是已分配区表和空闲区表，也就是用预先定义好的系统空间来存放空间分配信息。另一种也是最常用的就是空闲链表，由于对分区的操作是动态的，所以很难估计数据结构所占用的空间，而且空闲区表会占用宝贵的系统空间，所以提出了空闲链表的概念。其特点是用于管理分区的信息动态生成并和该分区在物理地址上相邻。这样由于可以简单用两个空闲块之间的距离定位已分配空间，不仅节约了系统空间，而且不必维持已分配空间的信息。本实验是要做一个模拟程序，来模拟动态分区算法的分配和回收过程，并不是真正的去分配和回收内存。基本的模拟方法有两种：1、先从内存中申请一块存储区，对这块存储区进行模拟的分配和回收活动。2、不
5、申请存储区，自己定义一块虚拟的存储区，对这块存储区进行模拟的分配和回收活动，分配和回收仅仅是对数据结构的修改而已。三运行环境： 1.操作系统 WINDOWS XP 2.编译软件 Microsoft Visual C+ 3.电脑配置：主频3.0GHz 内存512MB 四流程图1程序结构如图： 主菜单创建新作业alloc（）；内存分配查看空闲分区链free（）；内存回收程序结束退出回收内存空间2.首次适应算法的结构如图：从链首开始顺序查找空闲分区链完否？返 回分区大小所需大小？分区大小-所需大小=不可再分割大小？从该分区中划出所需大小的新分区将该整个分区从空闲分区链中移出将该分区分配给相应的作业，
6、修改有关数据返 回Y继续检索下一个表项YNNNY五循环首次适应算法代码#include #include #include using namespace std; struct memory struct memory *former; /前向指针 int address;/地址 int num;/作业号 int size;/分配内存大小 int state;/状态0表示空闲1表示已分配 struct memory *next; /后向指针; typedef struct memory MEMORY; MEMORY *mem; const int size_min=10;/内存允许的最小空闲
7、块的大小 void init(); /初始化内存块void exec();/执行相应算法void F_F(int); /依次初始化每个作业,并根据相应算法对作业分配内存void alloc(MEMORY *,MEMORY *);/分配内存算法（包括两种不同算法）void free(MEMORY *,int);/首次适应算法回收内存void sort(MEMORY *);/对内存链进行排序 void insert(MEMORY *,MEMORY *); /按空间大小将作业顺序插入到内存链void print(MEMORY *);/打印内存链 void main() /主函数 int i=0; w
8、hile(1) /选择算法 cout(n欢迎进入！); cout(nPlease select a number(1,0); cout(n 循环首次适应算法); cout 0-中止程序i; if(i=1) /首次适应算法 coutsize=640; mem-former=0; mem-next=0; void exec()/执行算法 while(1) /选择申请或释放内存操作 cout*endl; cout申请内存请输入作业号（1-6）endl; cout释放内存请输入数字8endl; cout中止程序请输入数字0endl; cout*k; /根据k值选择相应的操作if(k=1&k=7) F_
9、F(k); if(k=8)int m; coutm; /选择相应的回收算法 free(mem,m); else if(k=0) /回滚到选择算法的步骤break;void F_F(int i) /依次初始化每个作业,并根据相应算法对作业分配内存 int work=130,60,100,200,160,60,50;/作业序列，i从1开始（与作业号对应），因此从第一个开始存放作业值，第0个值为0，不是作业 coutformer=NULL; running-address=0; running-num=i; /i从1开始循环 running-size=worki; /指定作业大小 running-s
10、tate=0; /作业未分配 running-next=NULL; /根据相应算法为作业分配内存，详见alloc函数 alloc(mem,running); print(mem); coutendl; else cout没有足够的内存空间next; coutn内存链的状态为：state=0) cout内存 空闲 起始地址为:address 空闲空间大小为:sizek; else cout内存已分配 起始地址为:address 分配空间大小为: sizek 运行的作业号:num; coutnext; void free(MEMORY *ptr,int i) /首次适应算法 作业处理完后释放内存空
11、间 MEMORY *previous,*current; previous=ptr; current=previous-next; while(current!=NULL) /循环直到找到需要释放的作业位置 if(current-state=1¤t-num=i) break; previous=current; current=current-next; if(current=NULL) cout内存中没有任何作业！next=NULL) /当前作业为内存中最后一个作业 if(previous-state=0) /与前一个相邻空闲区合并 previous-size=previous-
12、size+current-size; previous-next=NULL; cout作业 num)释放 size)k 的空间state=0; cout作业 num)释放 size)k 的空间next)-next=NULL)/p6 /当前作业为倒数第二个作业(此种情况还是要单列出来讨论的否则会出现错误) if(previous-state=0&(current-next)-state=0) /p7 /释放的地址空间前后均为空闲区 previous-size=previous-size+current-size+(current-next)-size; previous-next=NULL; /
13、与下边else（其他情况的不同之处） cout作业 num)释放 size)k 的空间state=0) /p5 /释放的地址空间前面有空闲块则把它和前面的合并 previous-size=previous-size+current-size; (current-next)-former=previous; previous-next=current-next; cout作业 num)释放 size)k 的空间next)-state=0) /p8 /释放的地址空间后面有空闲块则把它和后面的空闲块合并 current-size=current-size+(current-next)-size; c
14、urrent-state=0; current-next=NULL; /与下边else（其他情况的不同之处） cout作业 num)释放 size)k 的空间state=0; cout作业 num)释放 size)k 的空间state=0&(current-next)-state=0) /p7 /所释放空间前后均为空闲区 previous-size=previous-size+current-size+(current-next)-size; (current-next)-next)-former=previous; previous-next=(current-next)-next; cou
15、t作业 num)释放 size)k 的空间state=0) /p5 /释放的地址空间前面有空闲块则把它和前面的合并 previous-size=previous-size+current-size; (current-next)-former=previous; previous-next=current-next; cout作业 num)释放 size)k 的空间next)-state=0) /p8 /释放的地址空间后面有空闲块则把它和后面的空闲块合并 current-size=current-size+(current-next)-size; current-state=0; (curre
16、nt-next)-next)-former=current; current-next=(current-next)-next; cout作业 num)释放 size)k 的空间state=0; cout作业 num)释放 size)k 的空间next=NULL) /内存没有作业运行 if(ptr-size=assign-size) /内存空间大于作业所需空间，为内存分配空间 ptr-size=ptr-size-assign-size; assign-state=1; ptr-next=assign; assign-former=ptr; cout作业 num)申请size) k的内存空间en
17、dl; else cout没有足够的内存空间为作业num)分配next; while(current!=NULL) /当前区间不为空（最后一个区间的next为空），即没有循环到最后 /如果当前内存空间大于作业所需空间并且内存没有被分配/则结束循环，当前current位置即为要插入的位置 if(current-size=assign-size¤t-state=0) break; previous=current; /previous后移 current=current-next; if(current=NULL) /空闲链中没有为作业分配所需的空间，即释放的空闲区间小于要分配的作业空
18、间 /不够用，则在所有作业后边另外再申请空闲区，如作业4 if(ptr-size=assign-size) /内存中还有足够没分配的空闲空间为此作业分配 /此时ptr指向内存上未分配空闲空间的起始地址 assign-address =640-(ptr-size); ptr-size=ptr-size-assign-size; assign-state=1; assign-former=previous; previous-next=assign; cout作业 num)申请size) k的内存空间endl; else cout没有足够的内存空间为作业num)分配size-assign-size
19、)num=assign-num; /划出与作业等同的空间 current-state=1; delete assign; cout作业 num)申请size) k的内存间size=current-size-assign-size; assign-state=1; assign-address=current-address+current-size; if(current-next=NULL) /此要分配的空间是空闲链的最后一个元素 assign-former=current; current-next=assign; else assign-next=current-next; (curre
20、nt-next)-former=assign; assign-former=current; current-next=assign; cout作业 num)申请size) k的内存空间endl; 六调试结果1输入条件 作业1申请130KB； 作业2申请60KB；作业3申请100KB； 作业2释放60KB；作业4申请200 KB； 作业3释放100 KB；作业1释放130 KB； 作业5申请140 KB；作业6申请60 KB； 作业7申请50KB；作业6释放60 KB 2运行结果： 七总结本次操作系统课程设计让我掌握了动态分区分配的实质：动态分区分配是根据进程的实际需要，动态地为之分配内存空间
21、。分区管理是满足多道程序运行的最简单的存储管理方式，为了实现对内存空间的有效管理，需要采取一些方法和策略，用以实现对内存空间的分配或回收。在实现可变分区分配时，将涉及到分区分配中所用的数据结构、分区分配算法和分区的分配和回收操作这样三个问题。并从根本上掌握了分区分配算法，分区分配算法就是系统在寻找空闲的分区分配给某一用户作业,具体可采用首次适应算法、循环首次适应算法和最佳适应算法等。八参考文献1任满杰等操作系统原理实用教程 电子工业出版社 20062汤子瀛 计算机操作系统（修订版）西安电子科技大学出版社 20013张尧学 史美林计算机操作系统教程实验指导 清华大学出版社 2000 4罗宇等 操
22、作系统课程设计机械工业出版社 20055曾平，曾林 操作系统清华大学出版社 2006东华理工大学信息工程学院课程设计评分表学生姓名：吴良谱 班级：10204102 学号：1020410206课程设计题目：循环首次适应的动态分区分配算法模拟项目内容满分实 评选题能结合所学课程知识、有一定的能力训练。符合选题要求（5人一题）10工作量适中，难易度合理10能力水平能熟练应用所学知识，有一定查阅文献及运用文献资料能力10理论依据充分，数据准确，公式推导正确10能应用计算机软件进行编程、资料搜集录入、加工、排版、制图等10能体现创造性思维，或有独特见解10成果质量总体设计正确、合理，各项技术指标符合要求。10说明书综述简练完整，概念清楚、立论正确、技术用语准确、结论严谨合理；分析处理科学、条理分明、语言流畅、结构严谨、版面清晰10设计说明书栏目齐全、合理，符号统一、编号齐全。格式、绘图、表格、插图等规范准确，符合国家标准10有一定篇幅，字符数不少于500010总 分100指导教师评语： 指导教师签名： 年 月 日