操作系统课程设计内存管理含源代码.doc

课程设计说明书
（操作系统）

题目: 内存管理___

院 系：计算机科学与工程学院
专业班级：__信息安全13-2班___
学 号： __ ___
学生姓名： ___________
指导教师： ____ ______

2015年 11月21 日

安徽理工大学课程设计（论文）
安徽理工大学课程设计（论文）任务书
计算机科学与工程学院
学 号
2013302970
学生姓名
谷郁
专业（班级）
信息安全13-2
设计题目
内存管理
设
计
技
术
参
数
1、采用可变分区方式完成对存储空间的管理（即存储空间的分配与回收工作）。
2、设计用来记录主存使用情况的数据结构：已分区表和空闲分区表或链表。
3、在设计好的数据结构上设计一个主存分配算法。
4、在设计好的数据结构上设计一个主存回收算法。其中，若回收的分区有上邻空闲分区和（或）下邻空闲分区，要求合并为一个空闲分区登记在空闲分区表的一个表项里。

设
计
要
求
1、编写程序实现采用可变分区方法管理内存，通过实验加强对内存管理方法的理解和掌握；
2、在完成电子设计后，要求写一份详细的设计报告。

工
作
量
编写代码不少于200行；
程设计说明书不少于15页。
工
作
计
划

参
考
资
料

指导教师签字

教研室主任签字

安徽理工大学课程设计（论文）成绩评定表

学生姓名： 谷郁 学号： 2013302970 专业班级： 信息安全13-2

程序设计训练题目： 内存管理
评价单元
评价要素
评价内涵
满分
评分
知识水平
30%
文献查阅与
知识运用能力
能独立查阅文献资料，并能合理地运用到程序设计训练之中；能将所学课程（专业）知识准确地运用到程序设计之中，并归纳总结本程序设计训练所涉及的有关课程知识
20

程序设计方案设计能力
程序设计整体思路清晰，程序设计方案合理可行
10

说明书质量
50%
难度等级
与程序设计训练任务书题目难度等级相当
10

写作水平
整体思路清晰，结构合理，层次分明，语言表达流畅，综合概括能力强
30

写作规范
符合程序设计训练报告的基本要求，用语、格式、图表、数据及各种资料引用规范（符合标准）
10

学习表现
20%
工作量
程序设计训练工作量饱满，能按时完成程序设计训练规定的工作量
10

学习态度
学习态度认真，遵守程序设计阶段的纪律，作风严谨，按时完成程序设计规定的任务，按时上交程序设计训练有关资料
10

成绩：

指导教师：

年 月 日

摘要
存储器历来都是计算机系统的重要组成部分。近年来，随着计算机技术的发展更，系统软件和应用类软件在种类、功能上都急剧的膨胀，虽然存储器容量一直在不断扩大，但仍不能满足现代软件发展的需要。因此，存储器仍然是一种宝贵而又稀缺的资源。如果对他加以有效的管理，不仅直接影响到存储器的利用率，而且对系统性能也有重大影响。

关键词：存储器，存储器容量，存储器管理，利用率。

目录

1 系统分析 1
1.1目的和意义 1
1.2目标分析 1
2概要设计 2
2.1设计思路 2
2.1.1动态分区分配 2
2.1.2动态分区分配中的数据结构 2
2.1.3 动态分区分配算法 2
2.1.4 回收内存 2
2.2 流程图 3
2.3 主要参数 3
3 核心代码实现 4
3.1首次适应算法 4
3.2 最佳适应算法 5
3.3最差适应算法 6
3.4回收内存 7
3.3分配内存 11
3.4回收内存及合并分区 12
4 总结 14
5 参考文献 14
I

1 系统分析
1.1目的和意义
操作系统课程主要讲述的内容是多道操作系统的原理与技术，与其它计算机原理、编译原理、汇编语言、计算机网络、程序设计等专业课程关系十分密切。本课程设计的目的综合应用学生所学知识，建立系统和完整的计算机系统概念，理解和巩固操作系统基本理论、原理和方法，掌握操作系统开发的基本技能。
1.2目标分析

教师需求分析
1、采用可变分区方式完成对存储空间的管理（即存储空间的分配与回收工作）。
2、设计用来记录主存使用情况的数据结构：已分区表和空闲分区表或链表。
3、在设计好的数据结构上设计一个主存分配算法。
4、 在设计好的数据结构上设计一个主存回收算法。其中，若回收的分区有上邻空闲分区和（或）下邻空闲分区，要求合并为一个空闲分区登记在空闲分区表的一个表项里。

2概要设计
2.1设计思路
2.1.1动态分区分配
动态分区分配又称为可变分区分配，它是根据进程的实际需要，动态的为之分配内存空间。在实现动态分区分配时，将涉及到分区分配中所用的数据结构，分区分配算法和分区的分配与回收操作这样三方面的问题。

2.1.2动态分区分配中的数据结构
为了实现动态分区分配，系统中必须配置相应的数据结构，用以描述空闲分区和已分配分区的情况，为分配提供依据。常用的数据结构有以下两种形式:
（1）空闲分区表，在系统中设置一张空闲分区表，用于记录每个空闲分区的情况。每个空闲分区占一个表目，表目中包括分区号，分区大小和分区始址等数据项。
（2）空闲分区链，为实现对空闲分区的分配和链接，在每个分区的其实部分设置一些用于控制分区分配的信息，以及用于链接各分区所用的前向指针，在分区尾部则设置一后向指针。通过前后相链接指针，可将所有的空闲分区链接成一个双向链。
2.1.3 动态分区分配算法
（1） 首次适应算法（FF算法）：FF算法要求空闲分区链以地址递增的次序链接。在分配内存时，从链首开始顺序查找，直至找到一个大小能满足要求的空闲分区为止。然后再按照作业的大小，从该分区中划出一块内存空间，分配给请求者，余下的空闲分区仍留在空闲链中。若从链首直至链尾都不能找到一个能满足要求的分区，则表示系统中已没有足够大的内存分配给该进程，内存分配失败，返回。
（2） 最佳适应（BF算法）：BF算法是指，每次为作业分配内存时，总是把能满足要求、又是最小的空闲分区分配给作业，避免“大材小用”。为了加速寻找，该算法要求将所有的空闲分区按其容量以从大到小的顺序形成一空闲分区链。这样，第一次找到的能满足要求的空闲区必然是最佳的。
（3） 最坏适应算法（WF算法)：与最佳适应算法正好相反，在扫描整个空闲分区表或链表时，总是挑选一个最大的空闲区，从中分割一小部分存储空间给作业使用，以至于存储器中缺失大的空闲分区。该算法要求，将所有的空闲分区，按其容量以从大到小的顺序形成一空闲分区链，查找时，只要看第一个分区是否满足作业要求即可。
2.1.4 回收内存
当进程运行完毕释放内存时，系统根据回收的首址，从空闲区链表中找到相应的插入点，此时可能出线以下四种情况之一：
（1）回收区与插入点的前一个空闲分区F1相邻接，此时应将回收区与插入点的前一分区合并，不必为回收分区分配新表项，而只需修改其前一分区F1的大小。
（2）回收分区与插入点的后一空闲分区F2相邻接。此时也可将两分区合并，形成新的空闲分区，但用回收区的首址作为新空闲区的首址，大小为两者之和。
（3）回收区同时与插入点的前、后两个分区邻接，此时将三个分区合并，使用F1的表项和F1的首址，取消F2的表项，大小为三者之和。
（4）回收区既不与F1邻接，也不与F2邻接。这时应为回收区单独建立一个新表项，填写回收区的首址和大小，并根据其首址插入到空闲链表中的适当位置。
2.2 流程图
分配成功表头移动
错误退出
查找下一个
可用内存是否足够
设定内存
分配可用内存

回收内存

表头不变，区间
合并
表头移动至上领区间
并合并
是否含有上领或下领区间

2.3 主要参数

1、typedef struct free table{}定义空间区，说明空间区，包含以下参数
（1） sum 分区序号，整型；
（2） address 起始地址，长整型；
（3） length 分区大小，长整型；
（4） state 分区状态，整型；
2、typedef struct Node{}线性表的双向链表存储结构，包含以下参数
（1） *prior 前趋指针；
（2） *next 后继指针；
3、flag 记录要删除的分区序号，整型；
4、Linklist first 头结点；
5、Linklist end 尾结点；
6、Status Initblock() 开创带头节点的内存空间链表；
7、Void sort（） 分区序号重新排列函数；
8、Void show（） 显示主存分配函数；
9、Status First_fit(int requset) 首次适应算法；

2

10、Status Best_fit（int request）最佳适应算法；
11、Status Worst_fit（int request）最坏适应算法；
12、Status deal（Node *p）处理回收空间；
13、Void main（）主函数。

3 核心代码实现

3.1首次适应算法
Status First_fit(int request) {
Node *p=first->next;//为申请作业开辟新空间且初始化
LinkList temp=(LinkList)malloc(sizeof(Node));
temp->data.length=request;
temp->data.state=1;
p->data.num=1;
while(p)
{
if((p->data.state==0)&&(p->data.length==request))
{//有大小恰好合适的空闲块
p->data.state=1;
return OK;
break;}
else if((p->data.state==0) && (p->data.length>request))
{//有空闲块能满足需求且有剩余
temp->prior=p->prior;
temp->next=p;
temp->data.address=p->data.address;
temp->data.num=p->data.num;
p->prior->next=temp;
p->prior=temp;
p->data.address=temp->data.address+temp->data.length;
p->data.length-=request;
p->data.num+=1;
return OK;
break;
}

p=p->next;
}
return ERROR;}

3.2 最佳适应算法

Status Best_fit(int request)
{int ch;//记录最小剩余空间
Node *p=first;
Node *q=NULL;//记录最佳插入位置
LinkList temp=(LinkList)malloc(sizeof(Node));
temp->data.length=request;
temp->data.state=1;
p->data.num=1;
while(p)//初始化最小空间和最佳位置
{
if((p->data.state==0) && (p->data.length>=request) )
{
if(q==NULL)
{
q=p;
ch=p->data.length-request;
}
else if(q->data.length > p->data.length)
{
q=p;
ch=p->data.length-request;
}
}
p=p->next;
}

if(q==NULL) return ERROR;
//没有找到空闲块
else if(q->data.length==request)
{
q->data.state=1;
return OK;}
else
{
temp->prior=q->prior;
temp->next=q;
temp->data.address=q->data.address;
temp->data.num=q->data.num;
q->prior->next=temp;
q->prior=temp;
q->data.address+=request;
q->data.length=ch;
q->data.num+=1;
return OK;
}
return OK;}
3.3最差适应算法
Status Worst_fit(int request)
{
int ch;//记录最大剩余空间
Node *p=first->next;
Node *q=NULL;//记录最佳插入位置
LinkList temp=(LinkList)malloc(sizeof(Node));
temp->data.length=request;
temp->data.state=1;
p->data.num=1;
while(p)//初始化最大空间和最佳位置
{
if(p->data.state==0 && (p->data.length>=request) )
{
if(q==NULL)
{q=p;
ch=p->data.length-request;
}
else if(q->data.length<p->data.length)
{
q=p;
ch=p->data.length-request;
}
}
p=p->next;
}
if(q==NULL) return ERROR;//没有找到空闲块
else if(q->data.length==request)
{
q->data.length=1;
return OK;
}else
{
temp->prior=q->prior;
temp->next=q;
temp->data.address=q->data.address;
temp->data.num=q->data.num;
q->prior->next=temp;
q->prior=temp;
q->data.address+=request;
q->data.length=ch;
q->data.num+=1;
return OK;
} return OK;
}
3.4回收内存

Status deal1(Node *p)//处理回收空间
{
Node *q=first;
for(;q!=NULL;q=q->next)
{
if(q==p)
{
if(q->prior->data.state==0&&q->next->data.state!=0)
{q->prior->data.length+=q->data.length;
q->prior->next=q->next;
q->next->prior=q->prior;
q=q->prior;
q->data.state=0;
q->data.num=flag-1;
}
if(q->prior->data.state!=0&&q->next->data.state==0)
{q->data.length+=q->next->data.length;
q->next=q->next->next;
q->next->next->prior=q;
q->data.state=0;
q->data.num=flag;
}
if(q->prior->data.state==0&&q->next->data.state==0)
{
q->prior->data.length+=q->data.length;
q->prior->next=q->next;
q->next->prior=q->prior;
q=q->prior;
q->data.state=0;
q->data.num=flag-1;
}
if(q->prior->data.state!=0&&q->next->data.state!=0)
{
q->data.state=0;}
}
}
return OK;}
Status deal2(Node *p)//处理回收空间
{
Node *q=first;
for(;q!=NULL;q=q->next)
{
if(q==p)
{
if(q->prior->data.state==0&&q->next->data.state!=0)
{
q->prior->data.length+=q->data.length;
q->prior->next=q->next;
q->next->prior=q->prior;
q=p->prior;
q->data.state=0;
q->data.num=flag-1;
}
if(q->prior->data.state!=0&&q->next->data.state==0)
{q->data.state=0;}
if(q->prior->data.state==0&&q->next->data.state==0)
{
q->prior->data.length+=q->data.length;
q->prior->next=q->next;
q->next->prior=q->prior;
q=q->prior;
q->data.state=0;
q->data.num=flag-1;
}
if(q->prior->data.state!=0&&q->next->data.state!=0)
{
q->data.state=0;
}
}
}
return OK;
}//主存回收
Status recovery(int flag)
{
Node *p=first;
for(;p!=NULL;p=p->next)
{
if(p->data.num==flag)
{
if(p->prior==first)
{
if(p->next!=end)//当前P指向的下一个不是最后一个时
{
if(p->next->data.state==0)//与后面的空闲块相连
{
p->data.length+=p->next->data.length;
p->next->next->prior=p;
p->next=p->next->next;
p->data.state=0;
p->data.num=flag;
}
else p->data.state=0;
}
if(p->next==end)//当前P指向的下一个是最后一个时
{
p->data.state=0;
}}//结束if(p->prior==block_first)的情况
else if(p->prior!=first)
{
if(p->next!=end)
{
deal1(p);
}
else
{
deal2(p);}
}//结束if(p->prior!=block_first)的情况
}//结束if(p->data.num==flag)的情况
}
printf("\t****回收成功****");
return OK;
}
4 程序调试
以最佳适应算法为例进行程序调试，调试结果如下
4.1开始界面

4.2选择最佳适应算法
3.3分配内存

3.4回收内存及合并分区

4 总结
本次课程设计使我加深了请求页式存储管理中置换算法的理解，在这次设计中，我学到了许多知识，由于之前的C语言、数据结构等基础打的不好，分析算法程序时感到很吃力，在刚开始编程时很茫然，无从下手，所以先看了老师之前的程序，也到网上看了别人写的相似程序，这才对存储管理的各个算法的设计有一点眉目。
在这次课程设计中，我不仅学会了一些C++知识，还知道了一个道理：有些程序编写看起来很难，毫无头绪，一旦你尝试去写，最终你终能得到你想要的结果，不怕你不会，就怕你不做。 
通过各个置换算法的设计编程，使我在思维、看待问题的全面性等方面也有了很大的提高。让我对实验原理有更深的理解，通过把该算法的内容，算法的执行顺序在计算机上实现，知道和理解了该理论在计算机中是怎样执行的，对该理论在实践中的应用有深刻的理解。并且这次课程设计把各个学科之间的知识融合起来，把各门课程的知识联系起来，对计算机整体的认识更加深刻。我希望今后能在动手方面加强，多上机。虽然现在的我还不能独立的完成这样一个复杂的设计，但我相信经过这样一次又一次的设计，最终我能做得更好。

5 参考文献
[1].汤小丹．计算机操作系统（第三版）．西安：电子科技大学出版社
[2].张丽芬．操作系统实验教程．清华大学出版社
源代码

#include<stdio.h>
#include<stdlib.h>
#define OK 1 //完成
#define ERROR 0 //出错
typedef int Status;
typedef struct free_table//定义一个空闲区说明表结构
{int num; //分区序号
long address; //起始地址
long length;//分区大小
int state; //分区状态
}ElemType;
typedef struct Node//线性表的双向链表存储结构
{
ElemType data;
struct Node*prior;//前趋指针
struct Node *next;//后继指针
}Node,*LinkList;
LinkList first;//头结点
LinkList end;//尾结点
int flag;//记录要删除的分区序号

Status Initblock()//开创带头结点的内存空间链表
{first=(LinkList)malloc(sizeof(Node));
end=(LinkList)malloc(sizeof(Node));
first->prior=NULL;
first->next=end;
end->prior=first;
end->next=NULL;
end->data.num=1;
end->data.address=40;
end->data.length=600;
end->data.state=0;
return OK;}

void sort()//分区序号重新排序
{Node *p=first->next,*q;
q=p->next;
for(;p!=NULL;p=p->next)
{
for(q=p->next;q;q=q->next)
{

if(p->data.num>=q->data.num)
{
q->data.num+=1;
}
}
}
}//显示主存分配情况
void show()
{ int flag=0;//用来记录分区序号
Node *p=first;
p->data.num=0;
p->data.address=0;
p->data.length=40;
p->data.state=1;
sort();
printf("\n\t\t》主存空间分配情况《\n");
printf("**********************************************************\n\n");
printf("分区序号\t起始地址\t分区大小\t分区状态\n\n");
while(p)
{
printf("%d\t\t%d\t\t%d",p->data.num,p->data.address,p->data.length);
if(p->data.state==0)
printf("\t\t空闲\n\n");
else
printf("\t\t已分配\n\n");
p=p->next;
}
printf("**********************************************************\n\n"); }//首次适应算法
Status First_fit(int request) {//为申请作业开辟新空间且初始化
Node *p=first->next;
LinkList temp=(LinkList)malloc(sizeof(Node));
temp->data.length=request;
temp->data.state=1;
p->data.num=1;
while(p)
{
if((p->data.state==0)&&(p->data.length==request))
{//有大小恰好合适的空闲块
p->data.state=1;
return OK;
break;}
else if((p->data.state==0) && (p->data.length>request))
{//有空闲块能满足需求且有剩余
temp->prior=p->prior;
temp->next=p;
temp->data.address=p->data.address;
temp->data.num=p->data.num;
p->prior->next=temp;
p->prior=temp;
p->data.address=temp->data.address+temp->data.length;
p->data.length-=request;
p->data.num+=1;
return OK;
break;
}
p=p->next;
}
return ERROR;}//最佳适应算法
Status Best_fit(int request)
{int ch;//记录最小剩余空间
Node *p=first;
Node *q=NULL;//记录最佳插入位置
LinkList temp=(LinkList)malloc(sizeof(Node));
temp->data.length=request;
temp->data.state=1;
p->data.num=1;
while(p)//初始化最小空间和最佳位置
{
if((p->data.state==0) && (p->data.length>=request) )
{
if(q==NULL)
{
q=p;
ch=p->data.length-request;
}
else if(q->data.length > p->data.length)
{
q=p;
ch=p->data.length-request;
}
}
p=p->next;
}

if(q==NULL) return ERROR;
//没有找到空闲块
else if(q->data.length==request)
{
q->data.state=1;
return OK;}
else
{
temp->prior=q->prior;
temp->next=q;
temp->data.address=q->data.address;
temp->data.num=q->data.num;
q->prior->next=temp;
q->prior=temp;
q->data.address+=request;
q->data.length=ch;
q->data.num+=1;
return OK;
}
return OK;}//最差适应算法
Status Worst_fit(int request)
{
int ch;//记录最大剩余空间
Node *p=first->next;
Node *q=NULL;//记录最佳插入位置
LinkList temp=(LinkList)malloc(sizeof(Node));
temp->data.length=request;
temp->data.state=1;
p->data.num=1;
while(p)//初始化最大空间和最佳位置
{
if(p->data.state==0 && (p->data.length>=request) )
{
if(q==NULL)
{q=p;
ch=p->data.length-request;
}
else if(q->data.length<p->data.length)
{
q=p;
ch=p->data.length-request;
}
}
p=p->next;
}
if(q==NULL) return ERROR;//没有找到空闲块
else if(q->data.length==request)
{
q->data.length=1;
return OK;
}else
{
temp->prior=q->prior;
temp->next=q;
temp->data.address=q->data.address;
temp->data.num=q->data.num;
q->prior->next=temp;
q->prior=temp;
q->data.address+=request;
q->data.length=ch;
q->data.num+=1;
return OK;
} return OK;
}//分配主存
Status allocation(int a)
{

int request;//申请内存大小
printf("请输入申请分配的主存大小(单位:KB):");
scanf("%d",&request);
if(request<0 ||request==0)
{
printf("分配大小不合适，请重试！");
return ERROR;
}

switch(a)
{case 1://默认首次适应算法
if(First_fit(request)==OK)
printf("\t****分配成功！****");
else printf("\t****内存不足，分配失败！****");
return OK;
break;
case 2://选择最佳适应算法
if(Best_fit(request)==OK)
printf("\t****分配成功！****");
else printf("\t****内存不足，分配失败！****");
return OK;
break;
case 3://选择最差适应算法
if(Worst_fit(request)==OK)
printf("\t****分配成功！****");
else printf("\t****内存不足，分配失败！****");
return OK;
break;
}
}
Status deal1(Node *p)//处理回收空间
{
Node *q=first;
for(;q!=NULL;q=q->next)
{
if(q==p)
{
if(q->prior->data.state==0&&q->next->data.state!=0)
{q->prior->data.length+=q->data.length;
q->prior->next=q->next;
q->next-