内存分配算法实验报告

成 绩 评 定 表

学生姓名 专 业 班级学号 内存分配算法 计算机科学课程设计题目 与技术 评 语 组长签字： 成绩 日期

1

2015 年 12月 10 日 课程设计任务书

学 院 学生姓名 课程设计题目 实践教学要求与任务: 模拟分区内存管理的模式下的各种分配策略，根据输入的各进程的信息（进程名，需要内存大小，进入内存时间，退出内存时间，发生申请内存的时间，申请内存的大小等），输出各个时间段上系统中的内存分配情况（各个空闲区位置和大小，各个进程空间的位置和大小）。 任务：利用静态链表，模拟实现内存分配（分页，分区） 要求： 1. 设计数据结构，存储结构； 2. 在c兼容环境完成上述题目的代码编写与调试； 3. 程序运行及诶按交互性好； 4. 软件运行，给出测试数据。 信息学院 专 业 计算机科学与技术 班级学号 内存分配技术 工作计划与进度安排: 第14周：布置课程设计任务，查阅资料，分组设计，程序调试。 第15周：程序调试，编写课程设计报告，验收，答辩。 指导教师： 2015年11月 28日 专业负责人： 2015年11月 28日 学院教学副院长： 2015年11月 28日 2

目 录

一、题目概述（内容及要求） ............................... 4 二、功能分析 ............................ 错误！未定义书签。 三、设计 ................................................. 6 四、运行与测试 ........................................... 7 五、总结 ................................................ 17 参考文献 ................................................ 18

3

1．设计目的

1) 了解多道程序系统中，多个进程并发执行的内存资源分配； 2) 模拟可变分区内存储管理算法实现分区管理的最佳适应分配算法； 3) 通过实现最佳算法来进一步了解静态分区模式的优缺点；

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

2．总体设计

4

3．关键技术

allocate（）： 实现内存分配，并当中调用display（pbc），以及display（S）两个函数

显示内存分配完成后的空闲块链表和进程链表情况。

requireback（）：实现内存回收，在满足情况的条件下调动allocate（）对用户社情的内

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

callback（）： 按内存回收时的四种情况对内存进行回收。

display（pbc）： 对空闲块链表中的空闲快惊醒从小到大排序并显示空闲链情况。 display（S): 对进程链表中的进程进行从小到大排序并显示进程链情况。 main（）： 创建并初始化空闲块链表和进程链链表，用户选择操作功能。

4．程序流程

图4-1

5

图4-2

5．主要源代码

#include #include #include #include

const int MAXJOB=100; //定义表最大记录数

typedef struct node{

int start; //空闲分区的起始地址 int length; //空闲分区的长度 char tag[20]; //分区信息是否已分配 }job;

job frees[MAXJOB]; //定义空闲区表 int free_quantity; //空闲区的个数

6

job occupys[MAXJOB];//定义已分配区表 int occupy_quantity; //已分配区的个数

//初始化函数 void initial() { int i;

for(i=0;i

frees[i].start=-1; frees[i].length=0;

strcpy(frees[i].tag,\

occupys[i].start=-1; occupys[i].length=0;

strcpy(occupys[i].tag,\free_quantity=0; occupy_quantity=0; }

//读数据函数 int readData() { FILE *fp; char fname[20];

cout<>fname;

if((fp=fopen(fname,\读文件

cout<

while(!feof(fp)) //文件结束

7

《 \ 《 {

fscanf(fp,\ fscanf(fp,\ free_quantity++; } return 1; } return 0; }

//sort选择——排序 void sort() { int i,j,p;

for(i=0;i

for(j=i+1;j

frees[free_quantity]=frees[i]; frees[i]=frees[p];

frees[p]=frees[free_quantity]; } } }

//显示函数 void view() { int i;

cout<

cout<<\起始地址 长度 状态\for(i=0;i

8

cout.setf(2); cout.width(12); cout<

cout<

cout<

cout<<\起始地址 长度 占用作业名\for(i=0;i

cout<

cout<

//最先适应分配算法 void earliest() {

//空闲分区按地址递增的顺序排列 char job_name[20]; int job_length; int i,j,flag,t;

cout<>job_name; //输入作业的名称 cin>>job_length; //输入作业的长度

9

flag=0; //分配成功与否信号 for(i=0;i=job_length) { flag=1; //可以分配 } } if(flag==0) {

cout<

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 //刚好分配则空闲分区数减一

10

{ for(j=i;j

cout<

//最优适应分配算法 void excellent() {

//空闲分区按大小递增的顺序排列 char job_name[20]; int job_length; int i,j,flag,t;

cout<>job_name; cin>>job_length; flag=0;

for(i=0;i=job_length){ flag=1; } }

if(flag==0){

cout<

if(frees[i].length>=job_length){

11

t=1; } i++; } i--;

for(j=0;j

if((frees[j].length>=job_length)&&(frees[j].length

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

cout<

//最坏适应算法 void worst() {

//空闲分区按大小递减的顺序排列 char job_name[20]; int job_length;

12

int i,j,flag,t;

cout<>job_name; cin>>job_length; flag=0;

for(i=0;i=job_length) flag=1; }

if(flag==0)

cout<

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

13

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<

//撤消作业 void finished() { char job_name[20]; int i,j,flag,p=0; int start; int length;

cout<>job_name;

flag=-1;

for(i=0;i

14

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

15

frees[free_quantity].length=length; free_quantity++; }

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

for(i=flag;i

void main() { int flag=0; int t=1; int chioce=0; initial();

flag=readData();

while(flag==1){ sort();

cout<

cout<<\cout<<\主存储器空间的分配与回收模拟\cout<<\cout<<\首次适应算法申请空间\cout<<\最佳适应算法申请空间\cout<<\最坏适应算法申请空间\cout<<\撤消作业\

cout<<\显示空闲表和分配表 \cout<<\退出\

16

cout< 请选择:\cin>>chioce;

switch(chioce){

case 1: earliest(); break; case 2: excellent() ;break; case 3: worst() ;break; case 4: finished(); break; case 5: view(); break; case 0: flag=0; break;

default: cout<<\选择错误!\}

//文件 fname

6. 运行结果及结论

图6-1

经验总结：程序设计时，最好将不同的功能用不同的函数实现。在本程序中，就将排序动能

17

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

7.参考文献

《数据结构》（c语言版） 严蔚敏、吴伟良编著； [美]巴斯.计算机算法：《设计和分析引论》 朱洪等译； 《数据库系统基础》 姚诗斌编著；

18

本文来源：https://www.bwwdw.com/article/449o.html