循环首次适应的动态分区分配算法模拟

1、课程设计报告课程设计题目：循环首次适应的动态分区分配算法模拟 专 业：计算机科学与技术班 级：10204102姓 名：谱学 号: 10204102指导教师: 高小辉 2013年 1 月 11 日目 录一循环首次适应算法 ·······························

2、3;···················3 1. 概述 ·····························&#

3、183;·································· 3 2需求分析··············

4、·················································3 二实验指

5、导··················································

6、;··············4 1.基本思想··································

7、83;···················42数据结构·····························

8、83;························4三运行环境························

9、83;······························6四流程图··················

10、3;················································6五循环首次适应算法

11、代码···········································5六调试结果·····

12、3;·················································11七、

13、总结·················································

14、3;········14八参考文献········································

15、83;··············14一 循环首次适应算法 1. 概述：该算法是由首次适应算法演变而成的。在为进程分配内存空间时，不再是每次都从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直至找到一个能满足要求的空闲分区，从中划出一块的请求大小相等的内存空间分配给作业。为实现该算法，应设置一起始查找指针，用于指示下一次起始查询的空闲分区，并采用循环查找方式，即如果最后一个（链尾）空闲分区的大小仍不能满足要求，则返回到第一个空闲分区，比较

16、大小是否满足，找到后，应调整起始查询指针。2. 需求分析了解动态分区分配中使用的数据结构和分配算法，并进一步加深对动态分区存储管理方式及其实现过程的理解。采用首次适应算法的动态分区分配过程alloc()和回收过程free()。空闲分区通过空闲分区链表来管理，在进行内存分配时，系统优先使用空闲区低端的空间，即每次分配内存空间是总是从低址部分开始进行循环，找到第一个合适的空间，便按作业所需分配的大小分配给作业。作业完成时，需要释放作业所占空间，此时要考虑到四种情况：(1)回收区与插入点的前一个空闲分区相邻接。此时将二者合并，修改前一分区的大小。(2)回收区与插入点的后一空闲分区相邻接，将二者合并，

17、用回收区的首址作为新空闲区的首址。(3)回收区同时与插入点的前后两个空闲分区相邻接，三者合并，使用前一空闲分区的表项和首址。(4)回收区单独存在。二、实验指导1基本思想动态分区是指系统不预先划分固定分区，而是在装入程序的时候划分内存区域，使得为程序分配的分区大小恰好等于该程序的需求量，且分区的个数是动态的。显然动态分区有较大的灵活性，较之固定分区能获得好的内存利用率。2数据结构动态分区管理可以用两种数据结构实现，一种是已分配区表和空闲区表，也就是用预先定义好的系统空间来存放空间分配信息。另一种也是最常用的就是空闲链表，由于对分区的操作是动态的，所以很难估计数据结构所占用的空间，而且空闲区表会占

18、用宝贵的系统空间，所以提出了空闲链表的概念。其特点是用于管理分区的信息动态生成并和该分区在物理地址上相邻。这样由于可以简单用两个空闲块之间的距离定位已分配空间，不仅节约了系统空间，而且不必维持已分配空间的信息。本实验是要做一个模拟程序，来模拟动态分区算法的分配和回收过程，并不是真正的去分配和回收内存。基本的模拟方法有两种：1、先从内存中申请一块存储区，对这块存储区进行模拟的分配和回收活动。2、不申请存储区，自己定义一块虚拟的存储区，对这块存储区进行模拟的分配和回收活动，分配和回收仅仅是对数据结构的修改而已。三运行环境： 1.操作系统 WINDOWS XP 2.编译软件 Microsoft Vi

19、sual C+ 3.电脑配置：主频3.0GHz 内存512MB 四流程图1程序结构如图： 主菜单创建新作业alloc（）；内存分配查看空闲分区链free（）；内存回收程序结束退出回收内存空间2.首次适应算法的结构如图：从链首开始顺序查找空闲分区链完否？返 回分区大小>所需大小？分区大小-所需大小<=不可再分割大小？从该分区中划出所需大小的新分区将该整个分区从空闲分区链中移出将该分区分配给相应的作业，修改有关数据返 回Y继续检索下一个表项YNNNY五循环首次适应算法代码#include <iostream> #include <stdlib.h> #inclu

20、de <stdio.h>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;/内存允许的最小空闲块的大小 void init(); /初始化内存块void exec();/执行相应算法

21、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; while(1) /选择算法 cout<<("n欢迎进入！"

22、;); cout<<("nPlease select a number(1,0)"); cout<<("n 循环首次适应算法"); cout<<" 0-中止程序"<<endl; cin>>i; if(i=1) /首次适应算法 cout<<("n以下为首次适应算法:n"); init();exec(); else exit(1); void init() /初始化内存容量 mem=new MEMORY; mem->size=640; mem

23、->former=0; mem->next=0; void exec()/执行算法 while(1) /选择申请或释放内存操作 cout<<"*"<<endl; cout<<"申请内存请输入作业号（1-6）"<<endl; cout<<"释放内存请输入数字8"<<endl; cout<<"中止程序请输入数字0"<<endl; cout<<"*"<<endl; int

24、 k;cin>>k; /根据k值选择相应的操作if(k>=1&&k<=7) F_F(k); if(k=8)int m; cout<<"请输入要释放的作业号：" cin>>m; /选择相应的回收算法 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

25、，不是作业 cout<<"请输入要作业所需的内存大小：" MEMORY *running; running=(MEMORY *)malloc(sizeof(MEMORY); if(running!=NULL) running->former=NULL; running->address=0; running->num=i; /i从1开始循环 running->size=worki; /指定作业大小 running->state=0; /作业未分配 running->next=NULL; /根据相应算法为作业分配内存，详见all

26、oc函数 alloc(mem,running); print(mem); cout<<endl; else cout<<"没有足够的内存空间"<<endl; void print(MEMORY *ptr) /打印显示内存情况 MEMORY *temp; temp=ptr->next; cout<<"n内存链的状态为："<<endl; while(temp!=NULL) if(temp->state=0) cout<<"内存 空闲 "<<&q

27、uot;起始地址为:"<<temp->address <<" 空闲空间大小为:"<<temp->size<<"k" else cout<<"内存已分配 "<<"起始地址为:"<<temp->address<<" 分配空间大小为:" <<temp->size<<"k" <<" 运行的作业号:"&

28、lt;<temp->num; cout<<endl; temp=temp->next; void free(MEMORY *ptr,int i) /首次适应算法 作业处理完后释放内存空间 MEMORY *previous,*current; previous=ptr; current=previous->next; while(current!=NULL) /循环直到找到需要释放的作业位置 if(current->state=1&&current->num=i) break; previous=current; current=c

29、urrent->next; if(current=NULL) cout<<"内存中没有任何作业！"<<endl; return; else if(current->next=NULL) /当前作业为内存中最后一个作业 if(previous->state=0) /与前一个相邻空闲区合并 previous->size=previous->size+current->size; previous->next=NULL; cout<<"作业 "<<(current->

30、;num)<<"释放 "<<(current->size)<<"k 的空间"<<endl; print(mem); else /将状态改为0，即为空闲区 current->state=0; cout<<"作业 "<<(current->num)<<"释放 "<<(current->size)<<"k 的空间"<<endl; print(mem); els

31、e if(current->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; /与下边else（其他情况的不同之处） cout<<

32、;"作业 "<<(current->num)<<"释放 "<<(current->size)<<"k 的空间"<<endl; print(mem); else if(previous->state=0) /p5 /释放的地址空间前面有空闲块则把它和前面的合并 previous->size=previous->size+current->size; (current->next)->former=previous; previou

33、s->next=current->next; cout<<"作业 "<<(current->num)<<"释放 "<<(current->size)<<"k 的空间"<<endl; print(mem); else if(current->next)->state=0) /p8 /释放的地址空间后面有空闲块则把它和后面的空闲块合并 current->size=current->size+(current->ne

34、xt)->size; current->state=0; current->next=NULL; /与下边else（其他情况的不同之处） cout<<"作业 "<<(current->num)<<"释放 "<<(current->size)<<"k 的空间"<<endl; print(mem); else /释放的地址空间前后都没有空闲块时直接把它的状态改为0 current->state=0; cout<<&quo

35、t;作业 "<<(current->num)<<"释放 "<<(current->size)<<"k 的空间"<<endl; print(mem); else /其他情况下（当前作业在链表中间） if(previous->state=0&&(current->next)->state=0) /p7 /所释放空间前后均为空闲区 previous->size=previous->size+current->size+(curr

36、ent->next)->size; (current->next)->next)->former=previous; previous->next=(current->next)->next; cout<<"作业 "<<(current->num)<<"释放 "<<(current->size)<<"k 的空间"<<endl; print(mem); else if(previous->state=

37、0) /p5 /释放的地址空间前面有空闲块则把它和前面的合并 previous->size=previous->size+current->size; (current->next)->former=previous; previous->next=current->next; cout<<"作业 "<<(current->num)<<"释放 "<<(current->size)<<"k 的空间"<<endl;

38、 print(mem); else if(current->next)->state=0) /p8 /释放的地址空间后面有空闲块则把它和后面的空闲块合并 current->size=current->size+(current->next)->size; current->state=0; (current->next)->next)->former=current; current->next=(current->next)->next; cout<<"作业 "<<(cu

39、rrent->num)<<"释放 "<<(current->size)<<"k 的空间"<<endl; print(mem); else /处理完的作业前后都没有空闲块时直接把它的状态改为0 current->state=0; cout<<"作业 "<<(current->num)<<"释放 "<<(current->size)<<"k 的空间"<<

40、;endl; print(mem); void alloc(MEMORY *ptr,MEMORY *assign) /根据算法分配内存（is_optimist状态） if(ptr->next=NULL) /内存没有作业运行 if(ptr->size>=assign->size) /内存空间大于作业所需空间，为内存分配空间 ptr->size=ptr->size-assign->size; assign->state=1; ptr->next=assign; assign->former=ptr; cout<<"作

41、业 "<<(assign->num)<<"申请"<<(assign->size)<<" "<<"k的内存空间"<<endl; else cout<<"没有足够的内存空间为作业"<<(assign->num)<<"分配"<<endl; delete assign; else /内存中如果已经分配了空间 MEMORY *previous,*current

42、; previous=ptr;/previous为链表中的第一个元素 current=previous->next; while(current!=NULL) /当前区间不为空（最后一个区间的next为空），即没有循环到最后 /如果当前内存空间大于作业所需空间并且内存没有被分配/则结束循环，当前current位置即为要插入的位置 if(current->size>=assign->size&&current->state=0) break; previous=current; /previous后移 current=current->next

43、; if(current=NULL) /空闲链中没有为作业分配所需的空间，即释放的空闲区间小于要分配的作业空间 /不够用，则在所有作业后边另外再申请空闲区，如作业4 if(ptr->size>=assign->size) /内存中还有足够没分配的空闲空间为此作业分配 /此时ptr指向内存上未分配空闲空间的起始地址 assign->address =640-(ptr->size); ptr->size=ptr->size-assign->size; assign->state=1; assign->former=previous; pr

44、evious->next=assign; cout<<"作业 "<<(assign->num)<<"申请"<<(assign->size)<<" "<<"k的内存空间"<<endl; else cout<<"没有足够的内存空间为作业"<<(assign->num)<<"分配"<<endl; else /释放的空闲链中有可为

45、此作业分配的空间 if(current->size-assign->size)<=size_min) /空闲链所具备的空间与作业所需空间大小差不多时 /直接把整个空闲块的空间分配给作业否则从空闲块中 current->num=assign->num; /划出与作业等同的空间 current->state=1; delete assign; cout<<"作业 "<<(current->num)<<"申请"<<(current->size)<<" "<<"k的内存间"<<e