动态分区分配算法要点.pdf
《动态分区分配算法要点.pdf》由会员分享,可在线阅读,更多相关《动态分区分配算法要点.pdf(15页珍藏版)》请在三一文库上搜索。
1、动态分区分配算法 一实验内容与要求 内容:动态分区分配是根据进程的实际需要,动态地为之分配内存空间, 而在分配时, 须按照一定的分配算法, 从空闲分区表或空闲分区链中选出一分区 分配给该作业。在本实验中运用了三种分配算法,分别是1. 首次适应算法, 2. 循环首次适应算法, 3. 最佳适应算法。 要求:动态分区算法也称为可变分区分配算法,常见的空闲区查找算法有 首次适应算法,循环首次适应算法,最佳适应算法。特别注意分区回收时,相邻 空闲分区需要合并。 (1) 参考操作系统教材理解这3 种分配算法以及回收算法。 (2) 实现 3 种分配算法以及回收算法。 (3) 已知作业申请内存和释放内存的序列
2、,给出内存的使用情况。 (4) 作业申请内存和释放内存的序列可以存放在文本文件中。 (5) 设计简单的交互界面,演示所设计的功能。( 可以使用 MFC 进行界面的设计 ) (6)可根据自己能力,在完成以上基本要求后,对程序功能进行适当扩充。 二、需求分析 本次实验通过用 C语言进行编程并调试、 运行,形象地表现出动态分区的分 配方式,直观地展现了首次适应算法和最佳适应算法对内存的释放和回收方式之 间的区别。 加深了我们对两种算法优缺点的理解,帮助我们了解一些数据结构和 分配算法, 进一步加深我们对动态分区存储器管理方式及其实现过程的理解。主 要的问题在于,如何解决两种算法对内存的释放和回收空间
3、的表示。 动态分区分配:又称为可变分区分配,这种分配方式并不事先先将主存划分 成一块块的分区,而是在作业进入主存时,根据作业的大小动态地建立分区。并 使分区的大小正好适应作业的需要。因此系统中分区的大小是可变的,分区的数 目也是可变的。 分区分配算法: 1. 首次适应法: 为作业选择分区时总是按地址从高到低搜索,只要找到可以容纳该作业的空 白块,就把该空白块分配给该作业。 特点:优先利用内存中底地址部分的空闲分区 ( 将所有空闲区 , 按其地址递增的 顺序链接 ) 2. 循环首次适应算法 该算法是由首次适应算法演变而成,在为进程分配内存空间时, 不再是每次都从 第一个空间开始查找,而是从上次找
4、到的空闲分区的下一个空闲分区开始查找, 直至找到第一个能满足要求的空闲分区,从中划出一块与请求大小相等的内存空 间分配给作业,为实现本算法,设置一个全局变量f , 来控制循环查找,当 f%N=0 时,f=0;若查找结束都不能找到一个满足要求的分区,则此次内存分配失败。 3. 最佳适应算法: 接到内存申请时,在空闲块表中找到一个不小于请求的最小空块进行分配; 为作业选择分区时总是寻找其大小最接近于作业所要求的存储区域。 三、概要设计 动态分区常用的数据结构有空闲分区表和空闲分区链,用来记录内存的使用 情况,此题中我采用的是空闲分区链的结构,用链指针将所有的分区链接成一条 链,每个分区的结构如下所
5、示: typedef struct freearea/定义一个空闲区说明表结构 int ID; /分区号 long size; /分区大小 long address; /分区地址 int state; /状态 ElemType; typedef struct DuLNode /double linked list ElemType data; struct DuLNode *prior; /前趋指针 struct DuLNode *next; /后继指针 DuLNode,*DuLinkList; 前向指针和后向指针分别用于与当前分区的前后分区相链接,address 用于 说明当前分区的起始地址
6、, 状态字为 0 时表示当前分区空闲, 为 1 时表示已分配, id 为分配的作业号, size表示分配的内存大小。 流程图: 开始 读入文件 选择算 法 首次 循环 最佳 选择 根据选择算法做 出相应操作 显示 结果 到达文件尾 部 显示结果 选择 根据要求, 请求释 放内存空进 显示 结果 结束 四、详细设计 #include #include #include #include using namespace std; #define Free 0 /空闲状态 #define Busy 1 / 已用状态 #define OK 1 /完成 #define ERROR 0 / 出错 #def
7、ine MAX_length 640 / 最大内存空间为640KB typedef int Status; typedef struct freearea/定义一个空闲区说明表结构 int ID; /分区号 long size; /分区大小 long address; /分区地址 int state; /状态 ElemType; /- 线性表的双向链表存储结构- typedef struct DuLNode /double linked list ElemType data; struct DuLNode *prior; /前趋指针 struct DuLNode *next; /后继指针 Du
8、LNode,*DuLinkList; DuLinkList block_first; /头结点 DuLinkList block_mid; DuLinkList block_last; /尾结点 Status alloc(int);/ 内存分配 Status alloc2(int);/ 内存分配2 Status free(int); / 内存回收 Status First_fit(int,int); /首次适应算法 Status CycleFirst_fit(int,int);/ 循环首次适应算法 Status Best_fit(int,int); /最佳适应算法 void show();/
9、查看分配 Status Initblock();/ 开创空间表 int ID,request; long adds=0; Status Initblock()/ 开创带头结点的内存空间链表 block_first=(DuLinkList)malloc(sizeof(DuLNode); block_last=(DuLinkList)malloc(sizeof(DuLNode); block_mid=(DuLinkList)malloc(sizeof(DuLNode); block_first-prior=NULL; block_first-next=block_mid; block_mid-ne
10、xt=block_last; block_mid-prior=block_first; block_last-prior=block_mid; block_last-next=NULL; block_mid-data.address=0; block_mid-data.size=MAX_length; block_mid-data.ID=0; block_mid-data.state=Free; return OK; /- 分 配 主 存 - Status alloc(int ch) if(requestID; coutrequest; if(requestdata.ID=ID; temp-d
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 动态 分区 分配 算法 要点
链接地址:https://www.31doc.com/p-5206735.html