动态分区分配方式的模拟实验报告模板.docx

1、华北电力大学实验报告实验名称动态分区分配式的模拟课程名称计算机操作系统专业班级：学生姓名：学号：成绩：指导教师：实验日期：专业资料一实验目的：了解动态分区分配式中使用的数据结构和分配算法， 并进一步加深对动态分区存储管理式及其实现过程的理解。二实验容：（1）用 C 语言分别实现采用首次适应算法和最佳适应算法的动态分区分配过程alloc() 和回收过程 free() 。其中，空闲分区通过分区链来管理；在进行存分配时，系统优先使用空闲区低端的空间。（2）假设初始状态下，可用存空间为640K ，并有下列请求序列：作业 1 申请 130KB。作业 2 申请 60KB。作业 3 申请 100KB。作业

2、2 释放 60KB。作业 4 申请 200KB 。作业 3 释放 100KB。作业 1 释放 130KB。作业 5 申请 140KB。作业 6 申请 60KB。作业 7 申请 50KB。作业 6 释放 60KB。请分别用首次适应算法和最佳适应算法进行存块的分配和回收，要求每次分配和回收后显示出空闲存分区链的情况。四设计思路和法：首次适应算法（First-fit ）：当要分配存空间时，就查表，在各空闲区中查找满足大小要求的可用块。只要找到第一个足以满足要球的空闲块就停止查找，并把它分配出去；如果该空闲空间与所需空间大小一样，则从空闲表中取消该项；如果还有剩余，则余下的部分仍留在空闲表中，但应修改

3、分区大小和分区始址。最佳适应算法（Best-fit ）：当要分配存空间时，就查找空闲表中满足要求的空闲块，并使得剩余块是最小的。然后把它分配出去，若大小恰好合适，则直按分配；若有剩余块，则仍保留该余下的空闲分区，并修改分区大小的起始地址。存回收： 将释放作业所在存块的状态改为空闲状态，删除其作业名，设置为空。并判断该空闲块是否与其他空闲块相连，若释放的存空间与空闲块相连时，则合并为同一个空闲块，同时修改分区大小及起始地址。五主要数据结构和算法：主要数据结构：专业资料定义一个空闲区说明表结构struct freearea int ID;/ 分区号long size;/ 分区大小long addr

4、ess; / 分区地址int state;/ 状态ElemType;线性表的双向链表存储结构struct DuLNode /double linked listElemType data;struct DuLNode *prior; /前趋指针struct DuLNode *next;/ 后继指针DuLNode,*DuLinkList;算法：首次适应算法： 是在分配存时， 从链首开始顺序查找， 直到找到一个大小能够满足要求的分区，即进行分配。最佳适应算法：是在分配存时，从链首开始顺序查找，查找到链尾，并记录一个大小不小于要求的分区的最小分区，在查找完毕后进行分配。六程序代码和输出1 程序代码如

5、下/*/*动态分区分配式的模拟*/*#include#include#define Free 0 / 空闲状态#define Busy 1 / 已用状态#define OK 1/ 完成#define ERROR 0 / 出错#define MAX_length 640 /最大存空间为 640KBtypedef int Status;typedef struct freearea/ 定义一个空闲区说明表结构int ID;/ 分区号专业资料long size;/ 分区大小long address; / 分区地址int state;/ 状态ElemType;/-线性表的双向链表存储结构-typede

6、f struct DuLNode /double linked listElemType data;struct DuLNode *prior; /前趋指针struct DuLNode *next;/ 后继指针DuLNode,*DuLinkList;DuLinkList block_first; / 头结点DuLinkList block_last;/ 尾结点Status alloc(int);/ 存分配Status free(int); / 存回收Status First_fit(int,int);/首次适应算法Status Best_fit(int,int); / 最佳适应算法void s

7、how();/查看分配Status Initblock();/ 开创空间表Status Initblock()/ 开创带头结点的存空间链表block_first=(DuLinkList)malloc(sizeof(DuLNode);block_last=(DuLinkList)malloc(sizeof(DuLNode);block_first-prior=NULL;block_first-next=block_last;block_last-prior=block_first;block_last-next=NULL;block_last-data.address=0;block_last-

8、data.size=MAX_length;block_last-data.ID=0;block_last-data.state=Free;return OK;/- 分 配 主 存 -Status alloc(int ch)int ID,request;coutID;专业资料coutrequest;if(request0 |request=0)cout 分配大小不合适，请重试！endl;return ERROR;if(ch=2) /选择最佳适应算法if(Best_fit(ID,request)=OK) cout 分配成功！ endl; else cout 存不足，分配失败！ endl; retu

9、rn OK;else /默认首次适应算法if(First_fit(ID,request)=OK) cout 分配成功！ endl; else cout 存不足，分配失败！ data.ID=ID;temp-data.size=request;temp-data.state=Busy;DuLNode *p=block_first-next;while(p)if(p-data.state=Free & p-data.size=request)/ 有大小恰好合适的空闲块p-data.state=Busy;p-data.ID=ID;return OK;break;if(p-data.state=Free

10、 & p-data.sizerequest)/ 有空闲块能满足需求且有剩余temp-prior=p-prior;temp-next=p;专业资料temp-data.address=p-data.address;p-prior-next=temp;p-prior=temp;p-data.address=temp-data.address+temp-data.size;p-data.size-=request;return OK;break;p=p-next;return ERROR;/-最佳适应算法-Status Best_fit(int ID,int request)int ch; / 记录最

11、小剩余空间DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode); temp-data.ID=ID;temp-data.size=request;temp-data.state=Busy;DuLNode *p=block_first-next;DuLNode *q=NULL; /记录最佳插入位置while(p) / 初始化最小空间和最佳位置if(p-data.state=Free &(p-data.sizerequest | p-data.size=request) )q=p;ch=p-data.size-request;break;p=p-nex

12、t;while(p)if(p-data.state=Free & p-data.size=request)/ 空闲块大小恰好合适p-data.ID=ID;p-data.state=Busy;return OK;break;if(p-data.state=Free & p-data.sizerequest)/ 空闲块大于分配需求专业资料if(p-data.size-requestdata.size-request;/更新剩余最小值q=p;/ 更新最佳位置指向p=p-next;if(q=NULL) return ERROR;/没有找到空闲块else/ 找到了最佳位置并实现分配temp-prior=

13、q-prior;temp-next=q;temp-data.address=q-data.address;q-prior-next=temp;q-prior=temp;q-data.address+=request;q-data.size=ch;return OK;/-主 存 回 收-Status free(int ID)DuLNode *p=block_first;while(p)if(p-data.ID=ID)p-data.state=Free;p-data.ID=Free;if(p-prior-data.state=Free)/与前面的空闲块相连p-prior-data.size+=p-

14、data.size;p-prior-next=p-next;p-next-prior=p-prior;if(p-next-data.state=Free)/与后面的空闲块相连p-data.size+=p-next-data.size;p-next-next-prior=p;p-next=p-next-next;专业资料break;p=p-next;return OK;/-显示主存分配情况-void show()cout+n;cout+主 存 分 配 情 况+n;coutnext;while(p)coutdata.ID=Free) coutFreeendl;else coutdata.IDend

15、l;cout 起始地址： data.addressendl;cout 分区大小： data.size KBendl;coutdata.state=Free) cout 空 闲 endl; else cout 已分配 endl;cout next;/- 主函数 -void main()int ch;/ 算法选择标记cout动态分区分配式的模拟n;cout*n;cout* 1)首次适应算法2)最佳适应算法*n;cout*n;coutch;Initblock(); / 开创空间表int choice;/ 操作选择标记while(1)cout*n;专业资料cout*1: 分配存2: 回收存*n;cou

16、t*3: 查看分配0: 退出*n;cout*n;coutchoice;if(choice=1) alloc(ch); /分配存else if(choice=2)/存回收int ID;coutID;free(ID);else if(choice=3) show();/显示主存else if(choice=0) break; /退出else / 输入操作有误cout 输入有误，请重试！ endl;continue;2 输入和输出结果（ 1）首次适应算法动态分区分配式的模拟* 1) 首次适应算法2) 最佳适应算法*请选择分配算法：1*1:分配存2: 回收存*3:查看分配0: 退出*请输入您的操作 ：

17、1请输入作业 (分区号 )：1请输入需要分配的主存大小(单位 :KB) ： 130分配成功！*1: 分配存2: 回收存*3:查看分配0: 退出*请输入您的操作 ：3+主存分配情况+分区号：1起始地址： 0分区大小： 130 KB状态：已分配分 区 号： Free专业资料起始地址： 130分区大小： 510 KB状态：空闲*1:分配存2:回收存*3:查看分配0: 退出*请输入您的操作 ：1请输入作业 (分区号 )：2请输入需要分配的主存大小(单位 :KB) ： 60分配成功！*1: 分配存2:回收存*3:查看分配0: 退出*请输入您的操作：3+主存分配情况+分区号：1起始地址： 0分区大小： 1

18、30 KB状态：已分配分区号：2起始地址： 130分区大小： 60 KB状态：已分配分 区 号： Free起始地址： 190分区大小： 450 KB状态：空闲*1: 分配存2:回收存*3: 查看分配0: 退出*请输入您的操作：1请输入作业 (分区号 )：3请输入需要分配的主存大小(单位 :KB) ： 100分配成功！*1: 分配存2:回收存*3: 查看分配0: 退出*请输入您的操作：3+主存分配情况+分区号：1起始地址： 0分区大小： 130 KB状态：已分配分区号：2起始地址： 130分区大小： 60 KB专业资料状态：已分配分区号：3起始地址： 190分区大小： 100 KB状态：已分配分

19、 区 号： Free起始地址： 290分区大小： 350 KB状态：空 闲*1: 分配存2: 回收存*3: 查看分配0: 退出*请输入您的操作 ：2请输入您要释放的分区号：2*1: 分配存2: 回收存*3: 查看分配0: 退出*请输入您的操作 ：3+主存分配情况+分区号：1起始地址： 0分区大小： 130 KB状态：已分配分 区 号： Free起始地址： 130分区大小： 60 KB状态：空闲分区号：3起始地址： 190分区大小： 100 KB状态：已分配分 区 号： Free起始地址： 290分区大小： 350 KB状态：空 闲*1: 分配存2: 回收存*3: 查看分配0: 退出*请输入您的

20、操作 ：1请输入作业 (分区号 )：4请输入需要分配的主存大小(单位 :KB) ： 200分配成功！*1: 分配存2: 回收存*3: 查看分配0: 退出*请输入您的操作：3专业资料+主存分配情况+分区号：1起始地址： 0分区大小： 130 KB状态：已分配分 区 号： Free起始地址： 130分区大小： 60 KB状态：空闲分区号：3起始地址： 190分区大小： 100 KB状态：已分配分区号：4起始地址： 290分区大小： 200 KB状态：已分配分 区 号： Free起始地址： 490分区大小： 150 KB状态：空 闲*1: 分配存2: 回收存*3: 查看分配0: 退出*请输入您的操作

21、 ：2请输入您要释放的分区号：3*1: 分配存2: 回收存*3: 查看分配0: 退出*请输入您的操作 ：3+主存分配情况+分区号：1起始地址： 0分区大小： 130 KB状态：已分配分 区 号： Free起始地址： 130分区大小： 160 KB状态：空闲分区号：4起始地址： 290分区大小： 200 KB状态：已分配分 区 号： Free起始地址： 490专业资料分区大小： 150 KB状态：空闲*1:分配存2: 回收存*3:查看分配0: 退出*请输入您的操作 ：2请输入您要释放的分区号：1*1: 分配存2: 回收存*3:查看分配0: 退出*请输入您的操作 ：3+主存分配情况+分 区 号：

22、Free起始地址： 0分区大小： 290 KB状态：空 闲分区号：4起始地址： 290分区大小： 200 KB状态：已分配分 区 号： Free起始地址： 490分区大小： 150 KB状态：空 闲*1: 分配存2: 回收存*3:查看分配0: 退出*请输入您的操作 ：1请输入作业 (分区号 )：5请输入需要分配的主存大小(单位 :KB) ： 140分配成功！*1: 分配存2: 回收存*3:查看分配0: 退出*请输入您的操作 ：3+主存分配情况+分区号：5起始地址： 0分区大小： 140 KB状态：已分配分 区 号： Free起始地址： 140分区大小： 150 KB状态：空闲分区号：4专业资料

23、起始地址： 290分区大小： 200 KB状态：已分配分 区 号： Free起始地址： 490分区大小： 150 KB状态：空闲*1: 分配存2: 回收存*3: 查看分配0: 退出*请输入您的操作： 1请输入作业 (分区号 )：6请输入需要分配的主存大小(单位 :KB) ： 60分配成功！*1: 分配存2: 回收存*3: 查看分配0: 退出*请输入您的操作：3+主存分配情况+分区号：5起始地址： 0分区大小： 140 KB状态：已分配分区号：6起始地址： 140分区大小： 60 KB状态：已分配分 区 号： Free起始地址： 200分区大小： 90 KB状态：空闲分区号：4起始地址： 290

24、分区大小： 200 KB状态：已分配分 区 号： Free起始地址： 490分区大小： 150 KB状态：空闲*1: 分配存2:回收存*3: 查看分配0: 退出*请输入您的操作：1请输入作业 (分区号 )：7请输入需要分配的主存大小(单位 :KB) ： 50分配成功！*专业资料*1:分配存2: 回收存*3:查看分配0: 退出*请输入您的操作：3+主存分配情况+分区号：5起始地址： 0分区大小： 140 KB状态：已分配分区号：6起始地址： 140分区大小： 60 KB状态：已分配分区号：7起始地址： 200分区大小： 50 KB状态：已分配分 区 号： Free起始地址： 250分区大小： 40 KB状态：空闲分区号：4起始地址： 290分区大小： 200 KB状态：已分配分 区 号： Free起始地址： 490分区大小： 150 KB状态：空闲*1: 分配存2:回收存*3: 查看分配0: 退出*请输入您的操作：2请输入您要释放的分区号：6*1: 分配存2:回收存*3: 查看分配0: 退出*请输入您的操作：3+主存分配情况+分区号：5起始地址： 0分区大小： 140 KB状态：已分配分 区 号： Free起始地址： 140分区大小： 60 KB专业资料状态：空闲分区号：7起始地址： 200分区大小： 50 KB状态：已分配分 区 号：