动态分区存储管理.docx

动态分区存储管理.docx

《动态分区存储管理.docx》由会员分享，可在线阅读，更多相关《动态分区存储管理.docx（18页珍藏版）》请在冰点文库上搜索。

动态分区存储管理

《操作系统》大作业报告

题目：

动态分区存储管理

学院理学院

专业信息与计算科学

班级信计1303

学号1130113301

学生姓名高月婷

二〇一五年十二月

1、需求分析、总体设计

需求分析：

动态分区管理方式预先不将主存划分成几个区域，而把主存除操作系统占区域外的空间看作一个大的空闲区。

当作业要求装入主存时，根据作业需要的主存空间的大小查询主存内各个空闲区，当从主存空间中找到一个大于或等于该作业大小的主存空闲区时，选择其中一个空闲区，按作业需求量划出一个分区装入该作业。

作业执行完后，它所占的主存分区被收回，成为一个空闲区。

如果该空闲区的相邻分区也是空闲区，则需要将相邻空闲区合并成一个空闲区。

实现动态分区的分配和回收，主要考虑的问题有三个：

第一，设计记录主存使用情况的数据表格，用来记录空闲区和作业占用的区域；第二，在设计的数据表格基础上设计主存分配算法；第三，在设计的数据表格基础上设计主存回收算法。

实验中主存分配算法采用“最优适应”算法。

最优适应算法是按作业要求挑选一个能满足作业要求的最小空闲区，这样保证可以不去分割一个大的区域，使装入大作业时比较容易得到满足。

但是最优适应算法容易出现找到的一个分区可能只比作业所要求的长度略大一点的情况，这时，空闲区分割后剩下的空闲区就很小，这种很小的空闲区往往无法使用，却影响了主存的使用。

为了一定程度上解决这个问题，如果空闲区的大小比作业要求的长度略大一点，不再将空闲区分成已分分区和空闲区两部分，而是将整个空闲区分配给作业。

在实现最优适应算法时，可把空闲区按长度以递增方式登记在空闲区表中。

总体设计：

1．采用动态分区管理方案实施内存分配和回收。

能够处理以下的情形

⑴能够输入给定的内存大小，进程的个数，每个进程所需内存空间的大小；

⑵当某进程提出申请空间的大小后，显示能否满足申请，以及为该进程分配资源后有关内存空间使用的情况；

⑶当某进程撤消时，显示内存回收后内存空间的使用情况。

能够处理以下的情形：

主存回收函数实现：

有上邻空闲区和下邻空闲区，它们与回收区的合并；有上邻空闲区，无下邻空闲区，回收区与上邻空闲区的合并；无上邻空闲区，有下邻空闲区，回收区与下邻空闲区的合并。

2．数据结构的定义及说明、算法思路和处理流程图

1）数据结构的定义 

①数据结构是指相互有关联的数据元素的集合。

②数据处理是指对数据集合中的各元素以各种方式进行运算，包括插入、删除、查找、更改等运算，也包括对数据元素进行分析。

③数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。

④数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（也称数据的物理结构）。

常用的存储结构有顺序、链接、索引等存储结构。

处理流程图：

三、详细设计（含源程序关键代码）

#include

usingnamespacestd;

//#defineMAX_LEN1024//定义内存大小，1024字节

enumStatus{FREE,BUSY,OK,ERROR};

structPST

{//partitionspecificationtable

intID;//分区号

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）

{//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;

}

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=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;

}

StatusWFA（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;

}

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<

";

cin>>size;

if（size<=0）

{

cout<<"输入错误!

"<

returnERROR;

}

if（choice==1）

{

if（FFA（id,size）==OK）

cout<<"分配成功！

"<

else

cout<<"分配失败！

"<

}

elseif（choice==2）

{

if（BFA（id,size）==OK）

cout<<"分配成功！

"<

else

cout<<"分配失败！

"<

}

elseif（choice==3）

{

if（WFA（id,size）==OK）

cout<<"分配成功！

"<

else

cout<<"分配失败！

"<

}

else

returnERROR;

}

voidShow（）

{

Node*cur=head->next;

while（cur）

{

cout<<"***********************************"<

cout<<"区号:

";

if（cur->data.ID==FREE）

cout<<"无"<

else

cout<data.ID<

cout<<"起始地址:

"<data.addr<

cout<<"分区长度:

"<data.size<

cout<<"状态:

";

if（cur->data.state==BUSY）

cout<<"已分配"<

else

cout<<"未分配"<

cur=cur->next;

}

}

intmain（）

{

cout<<"动态分区分配方式的模拟"<

cout<<"********************************************"<

cout<<"请输入内存大小（KB）:

";

cin>>area;

while（area<=0）

{

cout<<"输入错误，请重新输入内存大小（KB）";

cin>>area;

}

while

（1）

{

cout<<"********************************************"<

cout<<"**1.FFA2.BFA3.WFA0.EXIT**"<

cout<<"********************************************"<

cout<<"请选择:

";

intch;

cin>>ch;

if（ch==0）

{

break;

}

Init（area）;

intchoice;

while

（1）

{

cout<<"********************************************"<

cout<<"**1.分配2.回收3.查看0.退出**"<

cout<<"********************************************"<

cout<<"请输入您的操作：

";

cin>>choice;

if（choice==1）

{

cout<<"请输入进程个数";

intnum;

cin>>num;

for（;num>0;num--）

{

Assign（ch）;//分配内存

}

}

elseif（choice==2）//内存回收

{

intID;

cout<<"请输入您要释放的分区号：

";

cin>>ID;

Free（ID）;

}

elseif（choice==3）Show（）;//显示主存

elseif（choice==0）break;

else//输入操作有误

{

cout<<"输入有误，请重试！

"<

continue;

}

}

}

return0;

四、运行结果与分析

开始运行

内存分配

可用表

归还区有上临空闲区

归还区下临空闲区

归还区有下临空闲区

5、设计体会

经过本一次的课程设计从编写程序直至最后运行，自己对于编程的理解自然是更进一步，对于一个题目的研究及思考方面都有了长足进步，我觉得最重要的是学习到了一种思考的方式，从不同的角度多个方面的来看这个问题，尝试着处理各种有可能发生的情况，从中收获良多。

我觉得以后应设计开放的题目，对于学生要求要用开放思想来解决、对待这个问题。

其中帮助或许更大。

6、参考文献

《计算机操作系统》第四版