操作系统课程设计-内存管理

仲恺农业工程学院

课程设计报告

课程名称：操作系统 实验题目：内存管理

院 系：信息科学与技术学院 班 级： 姓 名： 学 号：

二○十五年十二月三十日

1 / 26

目录

1 系统分析.................................................................................................................... 3

1.1 目的和意义 .................................................................................................. 3 1.2 目标分析 ...................................................................................................... 3 2总体设计..................................................................................................................... 3

2.1 程序设计组成框图 ...................................................................................... 3 系统分为4个子模块：初始化模块，................................................................. 3 初始化模块：......................................................................................................... 4 2.2 流程图 .......................................................................................................... 5 3详细设计..................................................................................................................... 5

3.1 设计思路 ...................................................................................................... 5

3.1.1. 动态分区分配.................................................................................... 5 3.1.2. 动态分区分配中的数据结构............................................................ 5 3.1.3. 动态分区分配算法............................................................................ 6 3.1.4. 回收内存............................................................................................ 6 3.2 参数定义 ...................................................................................................... 7 3.3 数据结构 ...................................................................................................... 7 3.4 函数定义 ...................................................................................................... 7 3.5 算法分析 ...................................................................................................... 7 4 核心代码实现......................................................................................................... 8

4.1 首次适应算法 .............................................................................................. 8 4.2 最佳适应算法 .............................................................................................. 9 4.3 最差适应算法 ............................................................................................ 11 5 程序调试.................................................................................................................. 12

3.3分配内存......................................................................................................... 13 3.4回收内存及合并分区..................................................................................... 15 6 总结 ......................................................................................................................... 16 7参考文件................................................................................................................... 17 8源代码....................................................................................................................... 17

2 / 26

1 系统分析

1.1 目的和意义

操作系统课程主要讲述的内容是多道操作系统的原理与技术，与其它计算机原理、编译原理、汇编语言、计算机网络、程序设计等专业课程关系十分密切。

本课程设计的目的综合应用学生所学知识，建立系统和完整的计算机系统概念，理解和巩固操作系统基本理论、原理和方法，掌握操作系统开发的基本技能。

1.2 目标分析

1.2.1

采用可变分区方式完成对存储空间的管理（即存储空间

的分配与回收工作）。 1.2.2

设计用来记录主存使用情况的数据结构：已分区表和空

闲分区表或链表。 1.2.3 1.2.4

在设计好的数据结构上设计一个主存分配算法。 在设计好的数据结构上设计一个主存回收算法。其中，

若回收的分区有上邻空闲分区和（或）下邻空闲分区，要求合并为一个空闲分区登记在空闲分区表的一个表项里。

2总体设计

2.1 程序设计组成框图

系统分为4个子模块：初始化模块，首次适应算法模块、最佳适应算法模块、最差适应算法模块的四个算法模块。

3 / 26

初始化模块：allocation( )初始化函数，给每个相关的算法分配内存赋值。

首次适应算法模块，利用首次适应算法实现主存空间的分配并可以查看主存空间的分配情况和内存的回收。

最佳适应算法模块，利用首次适应算法实现主存空间的分配并可以查看主存空间的分配情况和内存的回收。

最差适应算法模块，利用首次适应算法实现主存空间的分配并可以查看主存空间的分配情况和内存的回收。

4 / 26

Main（） allocation( )初始化 首次适应算法最佳适应算法最差适应算法 分配内存 回收内存 分配内存 回收内存 分配内存 回收内存

2.2 流程图

设定内存 分配可用内存 可用内存是否足够

分配成功表头移动 查找下一个

错误退出

回收内存 是否含有上领或下领区间

表头移动至上领区间 并合并 表头不变，区间 合并 3详细设计

3.1 设计思路

3.1.1. 动态分区分配

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

3.1.2. 动态分区分配中的数据结构

5 / 26

}

4.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)//初始化最大空间和最佳位置 {

11 / 26

if(p->data.state==0 && (p->data.length>=request) ) { }

if(q==NULL) {

q=p;

ch=p->data.length-request;

}else if(q->data.lengthdata.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; }

5 程序调试

以最佳适应算法为例进行程序调试，调试结果如下 4.1开始界面

12 / 26

4.2选择最佳适应算法

3.3分配内存

13 / 26

14 / 26

3.4回收内存及合并分区

15 / 26

6 总结

本次课程设计使我加深了请求页式存储管理中置换算法的理解，在这次设计中，我学到了许多知识，由于之前的C语言、数据结构等基础打的不好，分析算法程序时感到很吃力，在刚开始编程时很茫然，无从下手，所以先看了老师之前的程序，也到网上看了别人写的相似程序，这才对存储管理的各个算法的设计有一点眉目。

在这次课程设计中，我不仅学会了一些C++知识，还知道了一个道理：有些程序编写看

16 / 26

起来很难，毫无头绪，一旦你尝试去写，最终你终能得到你想要的结果，不怕你不会，就怕你不做。

通过各个置换算法的设计编程，使我在思维、看待问题的全面性等方面也有了很大的提高。让我对实验原理有更深的理解，通过把该算法的内容，算法的执行顺序在计算机上实现，知道和理解了该理论在计算机中是怎样执行的，对该理论在实践中的应用有深刻的理解。并且这次课程设计把各个学科之间的知识融合起来，把各门课程的知识联系起来，对计算机整体的认识更加深刻。我希望今后能在动手方面加强，多上机。虽然现在的我还不能独立的完成这样一个复杂的设计，但我相信经过这样一次又一次的设计，最终我能做得更好。

7参考文件

1. 陆松华.操作系统.电子工业出版社

2. 李春葆.数据结构（第4版）.清华大学出版社 3. 石玉强.C语言程序设计. 电子工业出版社

8源代码

#include #include

#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;//记录要删除的分区序号

17 / 26

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\

printf(\ printf(\分区序号\\t起始地址\\t分区大小\\t分区状态\\n\\n\ while(p)

18 / 26

{ printf(\ if(p->data.state==0) printf(\空闲\\n\\n\ else printf(\已分配\\n\\n\ p=p->next; }

printf(\ }

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;//记录最小剩余空间

19 / 26

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;

20 / 26

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