内存分配算法实验报告.docx

内存分配算法实验报告.docx

《内存分配算法实验报告.docx》由会员分享，可在线阅读，更多相关《内存分配算法实验报告.docx（18页珍藏版）》请在冰点文库上搜索。

内存分配算法实验报告

成绩评定表

学生

班级学号

专业

计算机科学与技术

课程设计题目

存分配算法

评

语

组长签字：

成绩

日期

2015年12月10日

课程设计任务书

学院

信息学院

专业

计算机科学与技术

学生

班级学号

课程设计题目

存分配技术

实践教学要求与任务:

模拟分区存管理的模式下的各种分配策略，根据输入的各进程的信息（进程名，需要存大小，进入存时间，退出存时间，发生申请存的时间，申请存的大小等），输出各个时间段上系统中的存分配情况（各个空闲区位置和大小，各个进程空间的位置和大小）。

任务：

利用静态链表，模拟实现存分配（分页，分区）

要求：

1.设计数据结构，存储结构；

2.在c兼容环境完成上述题目的代码编写与调试；

3.程序运行及诶按交互性好；

4.软件运行，给出测试数据。

工作计划与进度安排:

第14周：

布置课程设计任务，查阅资料，分组设计，程序调试。

第15周：

程序调试，编写课程设计报告，验收，答辩。

指导教师：

2015年11月28日

专业负责人：

2015年11月28日

学院教学副院长：

2015年11月28日

一、题目概述（容及要求）4

二、功能分析4

三、设计6

四、运行与测试7

五、总结17

参考文献18

1．设计目的

1）了解多道程序系统中，多个进程并发执行的存资源分配；

2）模拟可变分区存储管理算法实现分区管理的最佳适应分配算法；

3）通过实现最佳算法来进一步了解静态分区模式的优缺点；

4）掌握最佳适应分配算法，深刻了解各进程在存中的具体分配策略。

2．总体设计

3．关键技术

allocate（）：

实现存分配，并当中调用display（pbc），以及display（S）两个函数显示存分配完成后的空闲块链表和进程链表情况。

requireback（）：

实现存回收，在满足情况的条件下调动allocate（）对用户社情的存块进行回收并在当中调用display（pbc），以及display（S）两个函数显示存分配完成后的空闲块链表和进程链表情况。

callback（）：

按存回收时的四种情况对存进行回收。

display（pbc）：

对空闲块链表中的空闲快惊醒从小到大排序并显示空闲链情况。

display（S）:

对进程链表中的进程进行从小到大排序并显示进程链情况。

main（）：

创建并初始化空闲块链表和进程链链表，用户选择操作功能。

4．程序流程

图4-1

图4-2

5．主要源代码

#include

#include

#include

#include

constintMAXJOB=100;//定义表最大记录数

typedefstructnode{

intstart;//空闲分区的起始地址

intlength;//空闲分区的长度

chartag[20];//分区信息是否已分配

}job;

jobfrees[MAXJOB];//定义空闲区表

intfree_quantity;//空闲区的个数

joboccupys[MAXJOB];//定义已分配区表

intoccupy_quantity;//已分配区的个数

//初始化函数

voidinitial（）{

inti;

for（i=0;i

frees[i].start=-1;

frees[i].length=0;

strcpy（frees[i].tag,"free"）;

occupys[i].start=-1;

occupys[i].length=0;

strcpy（occupys[i].tag,""）;}

free_quantity=0;

occupy_quantity=0;

}

//读数据函数

intreadData（）{

FILE*fp;

charfname[20];

cout<

cout<

";

cin>>fname;

if（（fp=fopen（fname,"r"））==NULL）//读文件

cout<

"<

else{

while（!

feof（fp））//文件结束

{

fscanf（fp,"%d",&frees[free_quantity].start）;

fscanf（fp,"%d",&frees[free_quantity].length）;

free_quantity++;}

return1;}

return0;

}

//sort选择——排序

voidsort（）{

inti,j,p;

for（i=0;i

p=i;

for（j=i+1;j

{if（frees[j].start

{p=j;}

}

if（p!

=i）{

frees[free_quantity]=frees[i];

frees[i]=frees[p];

frees[p]=frees[free_quantity];}

}

}

//显示函数

voidview（）{

inti;

cout<

cout<<"当前空闲表:

"<

cout<<"起始地址长度状态"<

for（i=0;i

cout.setf

（2）;

cout.width（12）;

cout<

cout.width（10）;

cout<

cout.width（8）;

cout<

}

cout<

cout<<"当前已分配表:

"<

cout<<"起始地址长度占用作业名"<

for（i=0;i

cout.setf

（2）;

cout.width（12）;

cout<

cout.width（10）;

cout<

cout.width（8）;

cout<

}

//最先适应分配算法

voidearliest（）{

//空闲分区按地址递增的顺序排列

charjob_name[20];

intjob_length;

inti,j,flag,t;

cout<

";

cin>>job_name;//输入作业的名称

cin>>job_length;//输入作业的长度

flag=0;//分配成功与否信号

for（i=0;i

if（frees[i].length>=job_length）{

flag=1;//可以分配

}}

if（flag==0）

{

cout<

}

else{

t=0;

i=0;

while（t==0）

{

if（frees[i].length>=job_length）

//从空闲分区表顺序查找，直到找到第一能满足其大小要求的空闲分区为止

{t=1;}

i++;

}

i--;

occupys[occupy_quantity].start=frees[i].start;//修改已分区的相关信息

strcpy（occupys[occupy_quantity].tag,job_name）;

occupys[occupy_quantity].length=job_length;

occupy_quantity++;

if（frees[i].length>job_length）

{

frees[i].start+=job_length;

frees[i].length-=job_length;

}

else//刚好分配则空闲分区数减一

{for（j=i;j

frees[j]=frees[j+1];}

free_quantity--;

cout<

"<

}

}

//最优适应分配算法

voidexcellent（）{

//空闲分区按大小递增的顺序排列

charjob_name[20];

intjob_length;

inti,j,flag,t;

cout<

";

cin>>job_name;

cin>>job_length;

flag=0;

for（i=0;i

if（frees[i].length>=job_length）{

flag=1;

}

}

if（flag==0）{

cout<

"<

}

else{

t=0;

i=0;

while（t==0）{

if（frees[i].length>=job_length）{

t=1;

}

i++;

}

i--;

for（j=0;j

if（（frees[j].length>=job_length）&&（frees[j].length

{i=j;}

}

occupys[occupy_quantity].start=frees[i].start;

strcpy（occupys[occupy_quantity].tag,job_name）;

occupys[occupy_quantity].length=job_length;

occupy_quantity++;

if（frees[i].length>job_length）{

frees[i].start+=job_length;

frees[i].length-=job_length;}

else{

for（j=i;j

{frees[j]=frees[j+1];}

free_quantity--;

cout<

"<

}

}

//最坏适应算法

voidworst（）{

//空闲分区按大小递减的顺序排列

charjob_name[20];

intjob_length;

inti,j,flag,t;

cout<

";

cin>>job_name;

cin>>job_length;

flag=0;

for（i=0;i

if（frees[i].length>=job_length）

flag=1;

}

if（flag==0）

cout<

"<

else{

t=0;

i=0;

while（t==0）{

if（frees[i].length>=job_length）

t=1;

i++;}

i--;

for（j=0;j

if（（frees[j].length>=job_length）&&（frees[j].length>frees[i].length））

i=j;

}

occupys[occupy_quantity].start=frees[i].start;

strcpy（occupys[occupy_quantity].tag,job_name）;

occupys[occupy_quantity].length=job_length;

occupy_quantity++;

if（frees[i].length>job_length）

{

frees[i].start+=job_length;

frees[i].length-=job_length;

}

else

{

for（j=i;j

{

frees[j]=frees[j+1];

}

free_quantity--;

cout<

"<

}

}

}

//撤消作业

voidfinished（）{

charjob_name[20];

inti,j,flag,p=0;

intstart;

intlength;

cout<

";

cin>>job_name;

flag=-1;

for（i=0;i

if（!

strcmp（occupys[i].tag,job_name））{

flag=i;

start=occupys[i].start;

length=occupys[i].length;}

}

if（flag==-1）{

cout<<"没有这个作业名"<

else

{

//加入空闲表

for（i=0;i

if（（frees[i].start+frees[i].length）==start）//上空

{if（（（i+1）

{//上空且下空，不为最后一个

frees[i].length=frees[i].length+frees[i+1].length+length;

for（j=i+1;j

frees[j]=frees[j+1];

free_quantity--;

p=1;

}

else{

frees[i].length+=length;//上空且下不空

p=1;}

}

if（frees[i].start==（start+length））{//下空

frees[i].start=start;

frees[i].length+=length;

p=1;}

}

//空闲中没有

if（p==0）{

frees[free_quantity].start=start;

frees[free_quantity].length=length;

free_quantity++;

}

//删除分配表中的该作业

for（i=flag;i

occupys[i]=occupys[i+1];

occupy_quantity--;}

}

voidmain（）

{intflag=0;

intt=1;

intchioce=0;

initial（）;

flag=readData（）;

while（flag==1）{

sort（）;

cout<

cout<<"==========================================="<

cout<<"主存储器空间的分配与回收模拟"<

cout<<"==========================================="<

cout<<"1.首次适应算法申请空间"<

cout<<"2.最佳适应算法申请空间"<

cout<<"3.最坏适应算法申请空间"<

cout<<"4.撤消作业"<

cout<<"5.显示空闲表和分配表"<

cout<<"0.退出"<

cout<请选择:

";

cin>>chioce;

switch（chioce）{

case1:

earliest（）;break;

case2:

excellent（）;break;

case3:

worst（）;break;

case4:

finished（）;break;

case5:

view（）;break;

case0:

flag=0;break;

default:

cout<<"选择错误!

"<

}

//文件fname

6.运行结果及结论

图6-1

经验总结：

程序设计时，最好将不同的功能用不同的函数实现。

在本程序中，就将排序动能单独放在了显示函数中，这样在用最佳适应算法实现存分配与回收时，就能只要调用该函数即可，二不必再考虑链表的排序

7.参考文献

《数据结构》（c语言版）严蔚敏、吴伟良编著；

[美]巴斯.计算机算法：

《设计和分析引论》朱洪等译；

《数据库系统基础》诗斌编著；