实验报告-动态分区分配算法.doc

大学实验报告【实验要求】1、编程实现首次适应算法和最正确适应算法的动态分区分配的分配过程和回收过程。其中，空闲分区通过分区链来管理；在进展存分配时，系统优先使用空闲区低端的空间。2、假设初始状态下，可用存空间为640K，并依次有以下请求序列：1) 作业1申请130KB。2) 作业2申请60KB。3) 作业3申请100KB。4) 作业2释放60KB。5) 作业4申请200KB。6) 作业3释放100KB。7) 作业1释放130KB。8) 作业5申请140KB。9) 作业6申请60KB。10) 作业7申请50KB。11) 作业6释放60KB。请分别用首次适应算法和最正确适应算法进展存块的分配和回收，要求每次分配和回收后显示出空闲存分区链的情况【可参考后文的实验提示】。3、上机时认真的进展测试，输入不同的资源分配请求，写出实验结果；4、具体要求：1对你的程序关键代码处进展注释。2给出实验数据，对结果进展分析，说明对相关知识点的理解。【实验目的】了解动态分区分配方式中使用的数据构造和分配算法，并进一步加深对动态分区存储管理方式及其实现过程的理解。【实验思路】首次适应算法First-fit：当要分配存空间时，就查表，在各空闲区中查找满足大小要求的可用块。只要找到第一个足以满足要球的空闲块就停顿查找，并把它分配出去；如果该空闲空间与所需空间大小一样，则从空闲表中取消该项；如果还有剩余，则余下的局部仍留在空闲表中，但应修改分区大小和分区始址。最正确适应算法Best-fit：当要分配存空间时，就查找空闲表中满足要求的空闲块，并使得剩余块是最小的。然后把它分配出去，假设大小恰好适宜，则直按分配；假设有剩余块，则仍保存该余下的空闲分区，并修改分区大小的起始地址。存回收：将释放作业所在存块的状态改为空闲状态，删除其作业名，设置为空。并判断该空闲块是否与其他空闲块相连，假设释放的存空间与空闲块相连时，则合并为同一个空闲块，同时修改分区大小及起始地址。【实验结果分析】【实验提示】你的动态分区的分配与回收，程序运行结果要可视化。可参考如下运行结果的模式。请分析如下这个结果来自于哪一种动态分配算法.实现可变分区的分配和回收，主要考虑的问题有三个：第一，设计记录存使用情况的数据表格，用来记录空闲区和作业占用的区域；第二，在设计的数据表格根底上设计存分配算法；第三，在设计的数据表格根底上设计存回收算法。首先，考虑第一个问题，设计记录存使用情况的数据表格，用来记录空间区和作业占用的区域。由于可变分区的大小是由作业需求量决定的，故分区的长度是预先不固定的，且分区的个数也随存分配和回收变动。总之，所有分区情况随时可能发生变化，数据表格的设计必须和这个特点相适应。由于分区长度不同，因此设计的表格应该包括分区在存中的起始地址和长度。由于分配时空闲区有时会变成两个分区：空闲区和已分分区，回收存分区时，可能会合并空闲分区，这样如果整个存采用一表格记录己分分区和空闲区，就会使表格操作繁琐。分配存时查找空闲区进展分配，然后填写己分配区表，主要操作在空闲区；*个作业执行完后，将该分区变成空闲区，并将其与相邻的空闲区合并，主要操作也在空闲区。由此可见，存的分配和回收主要是对空闲区的操作。这样为了便于对存空间的分配和回收，就建立两分区表记录存使用情况，一表格记录作业占用分区的"己分分区表；一是记录空闲区的"空闲区表。这两表的实现方法一般有两种：一种是链表形式，一种是顺序表形式。在实验中，采用顺序表形式，用数组模拟。由于顺序表的长度必须提前固定，所以无论是"已分分区表还是"空闲区表都必须事先确定长度。它们的长度必须是系统可能的最大项数。+ 主 存 分 配 情 况 +分 区 号：1起始地址：0分区大小：130 KB状 态：已分配分 区 号：Free起始地址：130分区大小：60 KB状 态：空 闲分 区 号：3起始地址：190分区大小：100 KB状 态：已分配分 区 号：Free起始地址：290分区大小：350 KB状 态：空 闲* 1: 分配存 2: 回收存 * 3: 查看分配 0: 退 出 *请输入您的操作 ：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: 退 出 *请输入您的操作 ：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+ 主 存 分 配 情 况 +分 区 号：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起始地址：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分区大小：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状 态：已分配分 区 号：Free起始地址：250分区大小：40 KB状 态：空 闲分 区 号：4起始地址：290分区大小：200 KB状 态：已分配分 区 号：Free起始地址：490分区大小：150 KB状 态：空 闲* 1: 分配存 2: 回收存 * 3: 查看分配 0: 退 出 *请输入您的操作 ：0Press any key to continue【首次适应算法】1.作业1申请130KB。作业2申请60KB。作业3申请100KB。具体分配情况如下：2.作业2释放60KB。3.作业4申请200KB。4. 作业3释放100KB。5. 作业1释放130KB。6. 作业5申请140KB。作业6申请60KB。作业7申请50KB。7. 作业6释放60KB。【最正确适应算法】1.作业1申请130KB。作业2申请60KB。作业3申请100KB。2.作业2释放60KB。作业4申请200KB。3.作业3释放100KB。4.作业1释放130KB。5.作业5申请140KB。作业6申请60KB。作业7申请50KB。6.作业6释放60KB。【代码实现】/*/* 动态分区分配方式的模拟 */* 制 马江涛 */* *： 8000612091 */* 班级：计算机软件121班 */*include<iostream.h>*include<stdlib.h>*define Free 0 /空闲状态*define Busy 1 /已用状态*define OK 1 /完成*define ERROR 0 /出错*define MA*_length 640 /最大存空间为640KBtypedef int Status;typedef struct freearea/定义一个空闲区说明表构造int ID; /分区号long size; /分区大小long address; /分区地址int state; /状态ElemType;/- 线性表的双向链表存储构造 -typedef struct DuLNode /double linked listElemType data; struct DuLNode *prior; /前趋指针struct DuLNode *ne*t; /后继指针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 show();/查看分配Status Initblock();/开创空间表Status Initblock()/开创带头结点的存空间链表block_first=(DuLinkList)malloc(sizeof(DuLNode);block_last=(DuLinkList)malloc(sizeof(DuLNode);block_first->prior=NULL;block_first->ne*t=block_last;block_last->prior=block_first;block_last->ne*t=NULL;block_last->data.address=0;block_last->data.size=MA*_length;block_last->data.ID=0;block_last->data.state=Free;return OK;/- 分 配 主 存 -Status alloc(int ch)int ID,request;cout<<"请输入作业(分区号)：" cin>>ID;cout<<"请输入需要分配的主存大小(单位:KB)：" cin>>request;if(request<0 |request=0) cout<<"分配大小不适宜，请重试！"<<endl;return ERROR;if(ch=2) /选择最正确适应算法if(Best_fit(ID,request)=OK) cout<<"分配成功！"<<endl;else cout<<"存缺乏，分配失败！"<<endl;return OK;else /默认首次适应算法if(First_fit(ID,request)=OK) cout<<"分配成功！"<<endl;else cout<<"存缺乏，分配失败！"<<endl;return OK;/- 首次适应算法 -Status First_fit(int ID,int request)/传入作业名及申请量/为申请作业开辟新空间且初始化DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode); temp->data.ID=ID; temp->data.size=request;temp->data.state=Busy;DuLNode *p=block_first->ne*t;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 && p->data.size>request)/有空闲块能满足需求且有剩余"temp->prior=p->prior;temp->ne*t=p; temp->data.address=p->data.address;p->prior->ne*t=temp; p->prior=temp;p->data.address=temp->data.address+temp->data.size;p->data.size-=request;return OK;break;p=p->ne*t;return ERROR;/- 最正确适应算法 -Status Best_fit(int ID,int request)int ch; /记录最小剩余空间DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode); temp->data.ID=ID; temp->data.size=request;temp->data.state=Busy;DuLNode *p=block_first->ne*t;DuLNode *q=NULL; /记录最正确插入位置while(p) /初始化最小空间和最正确位置if(p->data.state=Free &&(p->data.size>request | p->data.size=request) )q=p;ch=p->data.size-request;break;p=p->ne*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.size>request)/空闲块大于分配需求if(p->data.size-request<ch)/剩余空间比初值还小ch=p->data.size-request;/更新剩余最小值q=p;/更新最正确位置指向p=p->ne*t;if(q=NULL) return ERROR;/没有找到空闲块else/找到了最正确位置并实现分配temp->prior=q->prior;temp->ne*t=q;temp->data.address=q->data.address;q->prior->ne*t=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->data.size;p->prior->ne*t=p->ne*t;p->ne*t->prior=p->prior;if(p->ne*t->data.state=Free)/与后面的空闲块相连 p->data.size+=p->ne*t->data.size;p->ne*t->ne*t->prior=p;p->ne*t=p->ne*t->ne*t;break;p=p->ne*t;return OK;/- 显示主存分配情况 -void show()cout<<"+n"cout<<"+ 主 存 分 配 情 况 +n"cout<<"+n"DuLNode *p=block_first->ne*t;while(p)cout<<"分 区 号："if(p->data.ID=Free) cout<<"Free"<<endl;else cout<<p->data.ID<<endl;cout<<"起始地址："<<p->data.address<<endl;cout<<"分区大小："<<p->data.size<<" KB"<<endl;cout<<"状 态："if(p->data.state=Free) cout<<"空 闲"<<endl;else cout<<"已分配"<<endl;cout<<"-"<<endl;p=p->ne*t;/- 主 函 数-void main()system("color 79");int ch;/算法选择标记cout<<" 动态分区分配方式的模拟 n"cout<<"*n"cout<<"* 1)首次适应算法 2)最正确适应算法 *n"cout<<"*n"cout<<"请选择分配算法："cin>>ch;Initblock(); /开创空间表int choice; /操作选择标记while(1) cout<<"*n" cout<<"* 1: 分配存 2: 回收存 *n" cout<<"* 3: 查看分配 0: 退 出 *n" cout<<"*n" cout<<"请输入您的操作 ：" cin>>choice;if(choice=1) alloc(ch); / 分配存else if(choice=2) / 存回收int ID;cout<<"请输入您要释放的分区号："cin>>ID;free(ID);else if(choice=3) show();/显示主存else if(choice=0) break; /退出else /输入操作有误cout<<"输入有误，请重试！"<<endl;continue;【实验总结与分析】通过本次实验，我掌握为实现多道程序并发执行，操作系统是如何通过作业调度选择作业进入存以及系统是如何为进入存的作业分配存空间，实现多道作业同时驻留存，就绪进程队列中的多个进程是如何以分式方式共享CPU，作业运行完成离开系统时，系统如何进展存回收。1回收分区的上邻分区是空闲的，需要将这两个相邻的空闲区合并成一个更大的空闲区，修改空闲区表。2回收分区的下邻分区是空闲的，需要将这两个相邻的空闲区合并成一个更大的空闲区，修改空闲区表。3回收分区的上邻分区和下邻分区是空闲的，需要将这三个相邻的空闲区合并成一个更大的空闲区，修改空闲区表。4回收分区的上邻和下邻分区都不是空闲的，则直接将空闲区记录在空闲区表中!还加深理解了双向链表的一些操作！