实 验 报 告
实验名称 动态分区分配方式的模拟
课程名称 计算机操作系统
专业班级：通信09K2 学生姓名： 宫旭飞
学 号： ************ 成 绩：
指导教师： 张铁峰 实验日期： 2011.10.28
一﹑实验目的：
了解动态分区分配方式中使用的数据结构和分配算法，并进一步加深对动态分区存储管理方式及其实现过程的理解。
二﹑实验内容：
（1）用C语言分别实现采用首次适应算法和最佳适应算法的动态分区分配过程alloc()和回收过程free()。其中，空闲分区通过分区链来管理；在进行内存分配时，系统优先使用空闲区低端的空间。
（2）假设初始状态下，可用内存空间为0K，并有下列请求序列：
◎作业1申请130KB。
◎作业2申请60KB。
◎作业3申请100KB。
◎作业2释放60KB。
◎作业4申请200KB。
◎作业3释放100KB。
◎作业1释放130KB。
◎作业5申请140KB。
◎作业6申请60KB。
◎作业7申请50KB。
◎作业6释放60KB。
请分别用首次适应算法和最佳适应算法进行内存块的分配和回收，要求每次分配和回收后显示出空闲内存分区链的情况。
四﹑设计思路和方法：
首次适应算法（First-fit）：当要分配内存空间时，就查表，在各空闲区中查找满足大小要求的可用块。只要找到第一个足以满足要球的空闲块就停止查找，并把它分配出去；如果该空闲空间与所需空间大小一样，则从空闲表中取消该项；如果还有剩余，则余下的部分仍留在空闲表中，但应修改分区大小和分区始址。
最佳适应算法（Best-fit）：当要分配内存空间时，就查找空闲表中满足要求的空闲块，并使得剩余块是最小的。然后把它分配出去，若大小恰好合适，则直按分配；若有剩余块，则仍保留该余下的空闲分区，并修改分区大小的起始地址。
内存回收：将释放作业所在内存块的状态改为空闲状态，删除其作业名，设置为空。并判断该空闲块是否与其他空闲块相连，若释放的内存空间与空闲块相连时，则合并为同一个空闲块，同时修改分区大小及起始地址。
五﹑主要数据结构和算法：
六﹑程序代码和输出
1 程序代码如下
//***************************************************************
//******** 动态分区分配方式的模拟 *********
//***************************************************************
#include #include #define Free 0 //空闲状态 #define Busy 1 //已用状态 #define OK 1 //完成 #define ERROR 0 //出错 #define MAX_length 0 //最大内存空间为0KB 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; //后继指针 }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->next=block_last; block_last->prior=block_first; block_last->next=NULL; block_last->data.address=0; block_last->data.size=MAX_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<<"分配大小不合适，请重试！"< } if(ch==2) //选择最佳适应算法 { if(Best_fit(ID,request)==OK) cout<<"分配成功！"< } else //默认首次适应算法 { if(First_fit(ID,request)==OK) cout<<"分配成功！"< } } //------------------ 首次适应算法 ----------------------- 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->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 && p->data.size>request) {//有空闲块能满足需求且有剩余" 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; //记录最小剩余空间 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.size>request || p->data.size==request) ) { q=p; ch=p->data.size-request; break; } p=p->next; } 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=p->data.size-request;//更新剩余最小值 q=p;//更新最佳位置指向 } } p=p->next; } if(q==NULL) return ERROR;//没有找到空闲块 else {//找到了最佳位置并实现分配 temp->prior=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->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"; cout<<"+++++++++++++++++++++++++++++++++++++++\\n"; DuLNode *p=block_first->next; while(p) { cout<<"分 区 号："; if(p->data.ID==Free) cout<<"Free"< if(p->data.state==Free) cout<<"空 闲"< } } //----------------------- 主 函 数--------------------------- void main() { 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<<"输入有误，请重试！"< } } } 2输入输出结果 （1）首次适应算法 +++++++++++++++++++++++++++++++++++++++ +++ 主 存 分 配 情 况 +++ +++++++++++++++++++++++++++++++++++++++ 分 区 号：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: 退 出 ** ******************************************** 请输入您的操作 ：0 Press any key to continue （2）最佳适应算法 +++++++++++++++++++++++++++++++++++++++ +++ 主 存 分 配 情 况 +++ +++++++++++++++++++++++++++++++++++++++ 分 区 号：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 +++++++++++++++++++++++++++++++++++++++ +++ 主 存 分 配 情 况 +++ +++++++++++++++++++++++++++++++++++++++ 分 区 号：Free 起始地址：0 分区大小：290 KB 状 态：空 闲 —————————————— 分 区 号：4 起始地址：290 分区大小：200 KB 状 态：已分配 —————————————— 分 区 号：5 起始地址：490 分区大小：140 KB 状 态：已分配 —————————————— 分 区 号：Free 起始地址：630 分区大小：10 KB 状 态：空 闲 —————————————— ******************************************** ** 1: 分配内存 2: 回收内存 ** ** 3: 查看分配 0: 退 出 ** ******************************************** 请输入您的操作 ：1 请输入作业(分区号)：6 请输入需要分配的主存大小(单位:KB)：60 分配成功！ ******************************************** ** 1: 分配内存 2: 回收内存 ** ** 3: 查看分配 0: 退 出 ** ******************************************** 请输入您的操作 ：3 +++++++++++++++++++++++++++++++++++++++ +++ 主 存 分 配 情 况 +++ +++++++++++++++++++++++++++++++++++++++ 分 区 号：6 起始地址：0 分区大小：60 KB 状 态：已分配 —————————————— 分 区 号：Free 起始地址：60 分区大小：230 KB 状 态：空 闲 —————————————— 分 区 号：4 起始地址：290 分区大小：200 KB 状 态：已分配 —————————————— 分 区 号：5 起始地址：490 分区大小：140 KB 状 态：已分配 —————————————— 分 区 号：Free 起始地址：630 分区大小：10 KB 状 态：空 闲 —————————————— ******************************************** ** 1: 分配内存 2: 回收内存 ** ** 3: 查看分配 0: 退 出 ** ******************************************** 请输入您的操作 ：1 请输入作业(分区号)：7 请输入需要分配的主存大小(单位:KB)：50 分配成功！ ******************************************** ** 1: 分配内存 2: 回收内存 ** ** 3: 查看分配 0: 退 出 ** ******************************************** 请输入您的操作 ：3 +++++++++++++++++++++++++++++++++++++++ +++ 主 存 分 配 情 况 +++ +++++++++++++++++++++++++++++++++++++++ 分 区 号：6 起始地址：0 分区大小：60 KB 状 态：已分配 —————————————— 分 区 号：7 起始地址：60 分区大小：50 KB 状 态：已分配 —————————————— 分 区 号：Free 起始地址：110 分区大小：180 KB 状 态：空 闲 —————————————— 分 区 号：4 起始地址：290 分区大小：200 KB 状 态：已分配 —————————————— 分 区 号：5 起始地址：490 分区大小：140 KB 状 态：已分配 —————————————— 分 区 号：Free 起始地址：630 分区大小：10 KB 状 态：空 闲 —————————————— ******************************************** ** 1: 分配内存 2: 回收内存 ** ** 3: 查看分配 0: 退 出 ** ******************************************** 请输入您的操作 ：2 请输入您要释放的分区号：6 ******************************************** ** 1: 分配内存 2: 回收内存 ** ** 3: 查看分配 0: 退 出 ** ******************************************** 请输入您的操作 ：3 +++++++++++++++++++++++++++++++++++++++ +++ 主 存 分 配 情 况 +++ +++++++++++++++++++++++++++++++++++++++ 分 区 号：Free 起始地址：0 分区大小：60 KB 状 态：空 闲 —————————————— 分 区 号：7 起始地址：60 分区大小：50 KB 状 态：已分配 —————————————— 分 区 号：Free 起始地址：110 分区大小：180 KB 状 态：空 闲 —————————————— 分 区 号：4 起始地址：290 分区大小：200 KB 状 态：已分配 —————————————— 分 区 号：5 起始地址：490 分区大小：140 KB 状 态：已分配 —————————————— 分 区 号：Free 起始地址：630 分区大小：10 KB 状 态：空 闲 —————————————— ******************************************** ** 1: 分配内存 2: 回收内存 ** ** 3: 查看分配 0: 退 出 ** ******************************************** 请输入您的操作 ：0 Press any key to continue七﹑遇到问题和体会
Copyright © 2019-2025 51dongshi.net 版权所有
违法及侵权请联系：TEL:177 7030 7066 E-MAIL:11247931@qq.com 本站由北京市万商天勤律师事务所王兴未律师提供法律服务
