动态分区存储管理

1《操作系统》大作业报告题目：动态分区存储管理学院理学院专业信息与计算科学班级信计1303学号1130113301学生姓名高月婷二〇一五年十二月《操作系统》大作业报告1一、需求分析、总体设计需求分析：动态分区管理方式预先不将主存划分成几个区域，而把主存除操作系统占区域外的空间看作一个大的空闲区。当作业要求装入主存时，根据作业需要的主存空间的大小查询主存内各个空闲区，当从主存空间中找到一个大于或等于该作业大小的主存空闲区时，选择其中一个空闲区，按作业需求量划出一个分区装入该作业。作业执行完后，它所占的主存分区被收回，成为一个空闲区。如果该空闲区的相邻分区也是空闲区，则需要将相邻空闲区合并成一个空闲区。实现动态分区的分配和回收，主要考虑的问题有三个：第一，设计记录主存使用情况的数据表格，用来记录空闲区和作业占用的区域；第二，在设计的数据表格基础上设计主存分配算法；第三，在设计的数据表格基础上设计主存回收算法。实验中主存分配算法采用“最优适应”算法。最优适应算法是按作业要求挑选一个能满足作业要求的最小空闲区，这样保证可以不去分割一个大的区域，使装入大作业时比较容易得到满足。但是最优适应算法容易出现找到的一个分区可能只比作业所要求的长度略大一点的情况，这时，空闲区分割后剩下的空闲区就很小，这种很小的空闲区往往无法使用，却影响了主存的使用。为了一定程度上解决这个问题，如果空闲区的大小比作业要求的长度略大一点，不再将空闲区分成已分分区和空闲区两部分，而是将整个空闲区分配给作业。在实现最优适应算法时，可把空闲区按长度以递增方式登记在空闲区表中。总体设计：1．采用动态分区管理方案实施内存分配和回收。能够处理以下的情形⑴能够输入给定的内存大小，进程的个数，每个进程所需内存空间的大小；⑵当某进程提出申请空间的大小后，显示能否满足申请，以及为该进程分配资源后有关内存空间使用的情况；⑶当某进程撤消时，显示内存回收后内存空间的使用情况。能够处理以下的情形：主存回收函数实现：有上邻空闲区和下邻空闲区，它们与回收区的合并；有上邻空闲区，无下邻空闲区，回收区与上邻空闲区的合并；无上邻空闲区，有下邻空闲区，回收区与下邻空闲区的合并。二．数据结构的定义及说明、算法思路和处理流程图1）数据结构的定义①数据结构是指相互有关联的数据元素的集合。②数据处理是指对数据集合中的各元素以各种方式进行运算，包括插入、删除、查找、更改等运算，也包括对数据元素进行分析。③数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。④数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（也称数据的物理结构）。常用的存储结构有顺序、链接、索引等存储结构。《操作系统》大作业报告2处理流程图：作业J申请xk大小的主存空间i=0;k=-1;i是空闲区表中一栏(i=m)?N是否找到满足需求的分区k？Y第k栏长度-作业需求≤minsize？N分配整个分区：第k栏状态为“空”ad=第k栏起始地址;xk=第k栏长度;切割空闲区：第k栏长度减去xk；ad=第k栏起始地址-第k栏长度；Yi=0第i栏标志为“未分配”且满足作业需求xk？NY主存分配失败结束第i栏空闲区为第一个满足需求的或第i栏空闲区长度小于第k栏空闲区长度？YYi=i+1k=iNN第i栏是已分配区表中一栏且第i栏状态不为空？第i栏是为已分分配表中一栏？Yi=i+1NYN填写已分配区表：第j栏起始地址=ad；第j栏长度=xk；第j栏状态=作业名J空闲区表第k栏状态为空？YN空闲区表状态未分配空闲区表第k栏长度加xk已分配区表长度不足,分配失败结束《操作系统》大作业报告3三、详细设计（含源程序关键代码）#includeiostreamusingnamespacestd;//#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;《操作系统》大作业报告4last-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.sizesize){//如果大于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){//bestfitalgorithmNode*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){《操作系统》大作业报告5fit=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.sizesize){//获取最佳位置if(cur-data.size-sizemin){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;//记录符合满足请求的最小空闲块大小《操作系统》大作业报告6Node*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.sizesize){//获取最佳位置if(cur-data.size-sizemax){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《操作系统》大作业报告7returnERROR;}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请输入区号:;cinid;coutendl请输入分区长度(KB):;cinsize;if(size=0){cout输入错误!endl;returnERROR;}if(choice==1)《操作系统》大作业报告8{if(FFA(id,size)==OK)cout分配成功！endl;elsecout分配失败！endl;}elseif(choice==2){if(BFA(id,size)==OK)cout分配成功！endl;elsecout分配失败！endl;}elseif(choice==3){if(WFA(id,size)==OK)cout分配成功！endl;elsecout分配失败！endl;}elsereturnERROR;}voidShow(){Node*cur=head-next;whil