模拟设计动态分区存储管理的分配与回收

学号：课程设计题目模拟设计动态分区存储管理的分配与回收学院计算机科学与技术学院专业计算机科学与技术班级姓名指导教师2011年01月20日课程设计任务书学生姓名：专业班级：计算机指导教师：工作单位：计算机科学与技术学院题目:模拟设计动态分区存储管理的分配与回收初始条件：1．预备内容：阅读操作系统的内存管理章节内容，理解动态分区的思想，并体会动态分区主存的分配的具体实施方法。2．实践准备：掌握一种计算机高级语言的使用。要求完成的主要任务:〔包括课程设计工作量及其技术要求，以及说明书撰写等具体要求〕1．采用动态分区管理方案实施内存分配和回收。能够处理以下的情形⑴能够输入给定的内存大小，进程的个数，每个进程所需内存空间的大小；⑵当某进程提出申请空间的大小后，显示能否满足申请，以及为该进程分配资源后有关内存空间使用的情况；⑶当某进程撤消时，显示内存回收后内存空间的使用情况。能够处理以下的情形：主存回收函数实现：有上邻空闲区和下邻空闲区，它们与回收区的合并；有上邻空闲区，无下邻空闲区，回收区与上邻空闲区的合并；无上邻空闲区，有下邻空闲区，回收区与下邻空闲区的合并。2．设计报告内容应说明：⑴课程设计目的与功能；⑵需求分析，数据结构或模块说明(功能与框图)；⑶源程序的主要局部；⑷测试用例，运行结果与运行情况分析；⑸自我评价与总结：=1\*romani〕你认为你完成的设计哪些地方做得比拟好或比拟出色；=2\*romanii〕什么地方做得不太好，以后如何改正；=3\*romaniii〕从本设计得到的收获〔在编写，调试，执行过程中的经验和教训〕；=4\*romaniv〕完成此题是否有其他的其他方法〔如果有，简要说明该方法〕；=5\*romanv〕对实验题的评价和改良意见，请你推荐设计题目。时间安排：设计安排一周：周1、周2：完成程序分析及设计。周2、周3：完成程序调试及测试。周4、周5：验收、撰写课程设计报告。〔考前须知：严禁抄袭，一旦发现，抄与被抄的一律按0分记〕指导教师签名：年月日系主任〔或责任教师〕签名：年月日模拟设计动态分区存储管理的分配与回收1.课程设计目的与功能1.1课程设计的目的深入了解动态分区存储管理方式的主存分配回收的实现。1.2课程设计的功能1.能够输入给定的内存大小，进程的个数，每个进程所需内存空间的大小；2.当某进程提出申请空间的大小后，显示能否满足申请，以及为该进程分配资源后有关内存空间使用的情况；3.当某进程撤消时，显示内存回收后内存空间的使用情况。能够处理以下的情形：主存回收函数实现：有上邻空闲区和下邻空闲区，它们与回收区的合并；有上邻空闲区，无下邻空闲区，回收区与上邻空闲区的合并；无上邻空闲区，有下邻空闲区，回收区与下邻空闲区的合并。2.需求分析，数据结构或模块说明2.1需求分析动态分区管理方式预先不将主存划分成几个区域，而把主存除操作系统占区域外的空间看作一个大的空闲区。当作业要求装入主存时，根据作业需要的主存空间的大小查询主存内各个空闲区，当从主存空间中找到一个大于或等于该作业大小的主存空闲区时，选择其中一个空闲区，按作业需求量划出一个分区装入该作业。作业执行完后，它所占的主存分区被收回，成为一个空闲区。如果该空闲区的相邻分区也是空闲区，那么需要将相邻空闲区合并成一个空闲区。实现动态分区的分配和回收，主要考虑的问题有三个：第一，设计记录主存使用情况的数据表格，用来记录空闲区和作业占用的区域；第二，在设计的数据表格根底上设计主存分配算法；第三，在设计的数据表格根底上设计主存回收算法。实验中主存分配算法采用“最优适应”算法。最优适应算法是按作业要求挑选一个能满足作业要求的最小空闲区，这样保证可以不去分割一个大的区域，使装入大作业时比拟容易得到满足。但是最优适应算法容易出现找到的一个分区可能只比作业所要求的长度略大一点的情况，这时，空闲区分割后剩下的空闲区就很小，这种很小的空闲区往往无法使用，却影响了主存的使用。为了一定程度上解决这个问题，如果空闲区的大小比作业要求的长度略大一点，不再将空闲区分成已分分区和空闲区两局部，而是将整个空闲区分配给作业。在实现最优适应算法时，可把空闲区按长度以递增方式登记在空闲区表中。2.2结构说明分区说明表structPST{//partitionspecificationtableintid;//分区号intaddr;//起始地址intsize;//分区长度Statusstate;//状态};2.1.2双向链structNode{//双向链表结点PSTdata;Node*back;//前驱Node*next;//后继Node(){back=NULL;next=NULL;} Node(intid,intsize) { data.ID=id; data.size=size; back=NULL; next=NULL; }};2.1.3StatusFFA(intid,intsize){//headfitalgorithm Node*temp=newNode(id,size); temp->data.state=BUSY; Node*cur=head->next; while(cur) { if(cur->data.state==FREE&&cur->data.size==size) {//如果空闲块大小刚好与请求大小相等,直接分配 cur->data.ID=id; cur->data.state=BUSY; returnOK; break; } if(cur->data.state==FREE&&cur->data.size>size) {//如果大于 temp->back=cur->back; temp->next=cur; cur->back->next=temp; temp->data.addr=cur->data.addr; cur->back=temp; cur->data.addr=cur->data.addr+size; cur->data.size=cur->data.size-size; returnOK; break; } cur=cur->next; } returnERROR;}2.1.4StatusBFA(intid,intsize){//bestfitalgorithm Node*temp=newNode(id,size); temp->data.state=BUSY; intmin;//记录符合满足请求的最小空闲块大小 Node*fit;//指向采用最正确适应算法的插入位置 Node*cur=head->next; while(cur) {//取得第一个可以分配的位置〔不一定是最正确位置〕 if(cur->data.state==FREE&&cur->data.size>=size) { fit=cur; min=cur->data.size-size; break; } cur=cur->next; } while(cur) { if(cur->data.state==FREE&&cur->data.size==size) {//如果相等直接分配 cur->data.state=BUSY; cur->data.ID=id; returnOK; break; } if(cur->data.state==FREE&&cur->data.size>size) {//获取最正确位置 if(cur->data.size-size<min) { min=cur->data.size-size; fit=cur; } } cur=cur->next; } if(fit) {//假设最正确，插入 temp->back=fit->back; temp->next=fit; fit->back->next=temp; temp->data.addr=fit->data.addr; fit->back=temp; fit->data.addr=fit->data.addr+size; fit->data.size=fit->data.size-size; returnOK; } else returnERROR;}2.1.5StatusWFA(intid,intsize){//worstfitalgorithm Node*temp=newNode(id,size); temp->data.state=BUSY; intmax;//记录符合满足请求的最小空闲块大小 Node*fit;//指向采用最坏适应算法的插入位置 Node*cur=head->next; while(cur) {//取得第一个可以分配的位置〔不一定是最正确位置〕 if(cur->data.state==FREE&&cur->data.size>=size) { fit=cur; max=cur->data.size-size; break; } cur=cur->next; } while(cur) {/* if(cur->data.state==FREE&&cur->data.size==size) {//如果相等直接分配 cur->data.state=BUSY; cur->data.ID=id; returnOK; break; } */ if(cur->data.state==FREE&&cur->data.size>size) {//获取最正确位置 if(cur->data.size-size>max) { max=cur->data.size-size; fit=cur; } } cur=cur->next; } if(fit) {//假设最正确，插入 temp->back=fit->back; temp->next=fit; fit->back->next=temp; temp->data.addr=fit->data.addr; fit->back=temp; fit->data.addr=fit->data.addr+size; fit->data.size=fit->data.size-size; returnOK; } else returnERROR;}2.3结构框图图13.源程序#include<iostream>usingnamespacestd;//#defineMAX_LEN1024//定义内存大小，1024字节enumStatus{FREE,BUSY,OK,ERROR};structPST{//partitionspecificationtableintID;//分区号 intaddr;//起始地址intsize;//分区长度 Statusstate;//状态};structNode{//双向链表结点 PSTdata;Node*back;//前驱Node*next;//后继Node() { back=NULL; next=NULL;} Node(intid,intsize) { data.ID=id; data.size=size; back=NULL; next=NULL; }};intarea;//输入内存空间Node*head,*last;voidInit(intarea){ head=newNode();last=newNode(); head->next=last; last->back=head; last->data.addr=0; last->data.ID=0; last->data.size=area;last->data.state=FREE;}StatusFFA(intid,intsize){//headfitalgorithmNode*temp=newNode(id,size); temp->data.state=BUSY; Node*cur=head->next;while(cur){if(cur->data.state==FREE&&cur->data.size==size){//如果空闲块大小刚好与请求大小相等,直接分配cur->data.ID=id;cur->data.state=BUSY;returnOK;break; } if(cur->data.state==FREE&&cur->data.size>size) {//如果大于temp->back=cur->back;temp->next=cur;cur->back->next=temp;temp->data.addr=cur->data.addr;cur->back=temp;cur->data.addr=cur->data.addr+size;cur->data.size=cur->data.size-size;returnOK;break;} cur=cur->next;} returnERROR;}StatusBFA(intid,intsize){//bestfitalgorithm Node*temp=newNode(id,size);temp->data.state=BUSY;intmin;//记录符合满足请求的最小空闲块大小Node*fit;//指向采用最正确适应算法的插入位置Node*cur=head->next;while(cur){//取得第一个可以分配的位置〔不一定是最正确位置〕if(cur->data.state==FREE&&cur->data.size>=size){fit=cur;min=cur->data.size-size;break; }cur=cur->next; }while(cur) { if(cur->data.state==FREE&&cur->data.size==size) {//如果相等直接分配cur->data.state=BUSY;cur->data.ID=id;returnOK;break; } if(cur->data.state==FREE&&cur->data.size>size){//获取最正确位置if(cur->data.size-size<min){min=cur->data.size-size;fit=cur;} } cur=cur->next; }if(fit) {//假设最正确，插入 temp->back=fit->back; temp->next=fit; fit->back->next=temp; temp->data.addr=fit->data.addr; fit->back=temp;fit->data.addr=fit->data.addr+size; fit->data.size=fit->data.size-size; returnOK; }elsereturnERROR;}StatusWFA(intid,intsize){//worstfitalgorithmNode*temp=newNode(id,size); temp->data.state=BUSY;intmax;//记录符合满足请求的最小空闲块大小 Node*fit;//指向采用最坏适应算法的插入位置 Node*cur=head->next; while(cur) {//取得第一个可以分配的位置〔不一定是最正确位置〕if(cur->data.state==FREE&&cur->data.size>=size){fit=cur;max=cur->data.size-size;break;} cur=cur->next; }while(cur){/*if(cur->data.state==FREE&&cur->data.size==size) {//如果相等直接分配cur->data.state=BUSY;cur->data.ID=id;returnOK;break;}*/if(cur->data.state==FREE&&cur->data.size>size){//获取最正确位置if(cur->data.size-size>max){max=cur->data.size-size;fit=cur;}}cur=cur->next; } if(fit) {//假设最正确，插入 temp->back=fit->back;temp->next=fit; fit->back->next=temp; temp->data.addr=fit->data.addr; fit->back=temp; fit->data.addr=fit->data.addr+size;fit->data.size=fit->data.size-size; returnOK;} elsereturnERROR;}voidFree(intid){Node*cur=head;while(cur){if(cur->data.ID==id){cur->data.state=FREE;cur->data.ID=FREE;if(cur->back->data.state==FREE)//与前面的空闲块相连{cur->back->data.size+=cur->data.size;cur->back->next=cur->next;cur->next->back=cur->back;}if(cur->next->data.state==FREE)//与后面的空闲块相连{cur->data.size+=cur->next->data.size;cur->next->next->back=cur->back;cur->back->next=cur->next;}break;}cur=cur->next;}}StatusAssign(intchoice){ intid,size; cout<<"请输入区号:"; cin>>id; cout<<endl<<"请输入分区长度(KB):"; cin>>size; if(size<=0) { cout<<"输入错误!"<<endl; returnERROR; } if(choice==1) { if(FFA(id,size)==OK) cout<<"分配成功！"<<endl; else cout<<"分配失败！"<<endl; } elseif(choice==2) { if(BFA(id,size)==OK) cout<<"分配成功！"<<endl; else cout<<"分配失败！"<<endl; } elseif(choice==3) { if(WFA(id,size)==OK) cout<<"分配成功！"<<endl; else cout<<"分配失败！"<<endl; } else returnERROR;}voidShow(){ Node*cur=head->next; while(cur) { cout<<"***********************************"<<endl; cout<<"区号:"; if(cur->data.ID==FREE) cout<<"无"<<endl; else cout<<cur->data.ID<<endl; cout<<"起始地址:"<<cur->data.addr<<endl; cout<<"分区长度:"<<cur->data.size<<endl; cout<<"状态:"; if(cur->data.state==BUSY) cout<<"已分配"<<endl; else cout<<"未分配"<<endl; cur=cur->next; }}intmain(){ cout<<"动态分区分配方式的模拟"<<endl; cout<<"********************************************"<<endl; cout<<"请输入内存大小(KB):"; cin>>area; while(area<=0) { cout<<"输入错误，请重新输入内存大小(KB)"; cin>>area; } while(1) { cout<<"********************************************"<<endl; cout<<"**1.FFA2.BFA3.WFA0.EXIT**"<<endl; cout<<"********************************************"<<endl; cout<<"请选择:"; intch; cin>>ch; if(ch==0) { break; } Init(area); intchoice; while(1) { cout<<"********************************************"<<endl; cout<<"**1.分配2.回收3.查看0.退出**"<<endl; cout<<"********************************************"<<endl; cout<<"请输入您的操作："; cin>>choice; if(choice==1) { cout<<"请输入进程个数"; intnum; cin>>num; for(;num>0;num--) {