操作系统内存管理的实现

孙温稳

（郑州师范学院　信息科学与技术学院，河南　郑州　450044）



操作系统内存管理的实现

孙温稳

（郑州师范学院信息科学与技术学院，河南郑州450044）

摘要：在操作系统课程中的实验教学中，针对如何设计管理内存的实验，通过介绍具体的函数编写（使用C语言）来引导学生如何实现手工编写管理内存，其中包括如何初始化内存，如何使用最先适应法分配内存，如何释放内存，以及如何显示内存。

关键词：内存管理；C语言编程；分区分配算法

操作系统属于计算机专业的专业基础课程之一，是一门理论与实践并重的课程，也是一门教师难教、学生难学的课程。其教学难点集中表现在：内容十分庞杂，涉及面广，与计算机软、硬件及用户都有着密切的交互；实践性强，与实际运行着的各类操作系统有着密切的联系。所以，在教学过程中要理论结合实践，设计出一些相应的实验，来激发学生学习的积极性。内存管理是操作系统课程学习中的难点、重点之一，也是计算机编程最为基本的领域之一。对实际编程来说，理解内存管理器的能力与局限性至关重要。该文将介绍如何用C语言设计一些函数来引导学生用手工实现内存的管理，从而加深对内存管理的理解［1］。

1　操作系统内存管理概述

通常将已分配给用户使用的一段连续的内存空间称为“占用块”，将未分配给任何用户的一段连续的内存空间称为“可利用空间块”或者“空闲块”。可以为学生设计一些编程过程当中用到的一些常量和变量：①设置常量HEAP_SIZE为 内 存 区 域 总 的 尺寸，如：#define HEAP_SIZE 1048576；②设置指定内存区域指针struct fb{size_t size;struct fb*next;}。需要说明的是，size_t 在C语言中是一种“整型”类型，里面保存的是一个整数，如int、long。这种整数用来记录一个大小（size）。size_t的全称应该是size type，就是说“一种用来记录大小的数据类型”。其中，‘size’字段包括所指定内存块的总的大小，‘next’字段包括下一个内存块的地址，如果没有下一个内存块，则为空。并且内存块的排列是以地址的大小顺序递增排列的。

2　内存管理的算法

实现内存管理的算法建立于内存空闲块所在的链表的分配原理。对每一个空闲块都有其相关的描述包括块的大小和相连的下一个空闲块。换句话说，内存的管理也就是实现内存分配和释放的管理。目前已经有了3种算法关于实现内存的管理，分别是最先适应法、最佳适应法和最差适应算法。而每一种算法实现都包含4个函数，需要学生完成下面4个函数的编写工作。2.1void mem_init():（内存初始化）

mem_init是初始化内存分配程序的函数，其要完成以下两件事：找到系统中有效内存区域，并将它们初始化，这些初始化内存块的尺寸为内存区域的总尺寸减去该结构体变量所占用空间的字节数，即taille_libre= HEAP_SIZE-sizeof(struct fb)。然后建立起指向我们管理的内存的指针。

void mem_init(){size_t taille_libre;//初始化空闲内存块;//初始化占用块内存指针}

2.1void*mem_alloc(size_t size)（分配内存）

该函数带有一个入口参数为被分配内存块的大小，且返回一个指向被分配内存块的指针，若没有可分配的内存块，则返回NLUU。目前实现分区分配有3种算法：最先适应法、最佳适应法和最坏适应法。运行时可任选一种算法。系统均能显示内存分配的状态和参数变化情况。最先适应法是分配时从表头指针开始查找可利用空间表，将找到的第一个大小不小于“请求”的空闲块的一部分分配给用户。最先适应算法要求可用表或自由链接按起始地址递增的次序排列。该算法的最大特点是一旦找到大于或等于所要求内存长度的分区，则搜索结束。最佳适应算法将可利用空间表中一个大小不小于“请求”且最接近“请求”的空闲块的一部分分配给用户。最差适应算法将可利用空间表中一个大小不小于“请求”且是链表中最大的空闲块的一部分分配给用户。该函数主要实现第一种算法，当某用户请求N字节内存，分配器遍历空闲块链表以寻找一块足够大的内存块。如果内存块的内存部分与请求的内存大小相同，则将此内存块从链表中移除同时返回一个指向此内存块内存部分的指针。如果内存部分的大小大于所需要的内存，分割此块内存为两部分，一个是申请的大小，另一个是剩余的大小。然后将分配给用户的那块内存传给用户，并将剩下的那块（如果有的话）返回到链表上。可将最先适应法定义为0，最坏适应法定义为1，最佳适应法定义为2。

#define FIRST_FIT 0

#define WORST_FIT 1

#define BEST_FIT 2

void*mem_alloc(size_t size)

{switch(choix_algo){用 switch选择合适的算法

case FIRST_FIT:

case WORST_FIT:

case BEST_FIT:......}}在实际的算法实现当中，还应考虑在回收用户释放的内存块后对内存空间的重新组织，合并连续的内存块，即“节点合并”的问题。因为系统在不断的分配和回收过程中，使得大的空闲块逐渐被分割成小的占用块，然后又重新成为空闲块被系统回收，如此反复，地址相邻的两块空闲块却分别作为链表中的节点存在，导致出现较大的用户“请求”时，虽然有足够的空闲空间，但是他们分布在多个空闲块内，分配无法进行。为了使内存空间得到更有效的利用，就要求在回收内存块后对内存空间进行重新组织，合并连续的内存空间，最大限度地满足将来的分配需求。下面就来看一下如何来实现这一功能。

2.2Void mem_free(void*zone,size_t size)（释放内存）

这个函数带有2个入口参数，zone为将要释放内存块的地址，size为将要释放内存块的大小。当用户释放一个内存块，将遍历占用块的链表（记住，链表是有序的），然后根据内存块的地址搜索其位置，找到后并从链表中删除。同时将被释放块加入到空闲块的链表中，将此内存块与其相邻块合并。若其正好处于其他两个空闲块的中间位置，将把它们合并成一个尺寸更大的空闲块。

void mem_free(void*zone,size_t size)

{//可设计一些需要的指针变量;//寻找在占用块链表中要释放的内存块;//将要释放的内存块从占用块的链表中删除;//插入新的空闲块到空闲块链表中，同时要进行适当的合并://1.前面是否有空闲可合并://2.合并后面的空闲块:}

2.3Void mem_show(void(*print)(void*zone, size_t size))（显示内存）

这个函数有一个入口参数是一个指针指向一个过程print，这个过程本身带有2个参数，一个参数是内存地址，一个参数是内存块的大小。Print这个过程被用于在屏幕上显示特定的空闲块。显示的方式可分为3种情况：第一种传统的显示方式，主要用于显示空闲块链表；第二种增长的显示方式，主要用于显示占有块链表；第三种个人的显示方式，主要用于显示所有内存块的状态、分配情况，并且内存块按升序排列。

3　验证（如何运行所编写的函数）

在一步骤中，需要编写主函数main()函数以及其他一些所需要的函数，如帮助函数aide()。为了减轻学生的负担，这些函数可由老师给出。

动态存储管理的算法是操作系统设计的一个重要问题，学习和研究它们能够为在操作系统等方面的深入研究提供一定的理论依据和实践感知。通过了解诸多算法的基本思想和应用环境，也使得学生更加深入地了解软件在运行时计算机内存资源如何高效、快速地分配，并且在适当的时候释放和回收内存资源。

参考文献：

［1］Jonathan Bartlett.Inside memory management［EB/OL］. （2004-10-16）[2016-01-15].http://www-128.ibm.com/developer⁃works/linux/library/l-memory.

中图分类号：TP31

文献标识码：A

文章编号：1003-5168（2016）02-0062-02

收稿日期：2016-01-16

作者简介：孙温稳（1974-），女，硕士，研究方向：人工智能。

Implementation of Memory Management in Operating System

Sun Wenwen
（Information Science&Technology College，Zhengzhou Normal University，Zhengzhou Henan 450044）

Abstract:This paper provided an experiment on how to design and manage memory in experimental teach⁃ing of operating system course,by specific examples(using C language)to guide students how to manage memory manual,including how to initialize the memory,how to allocate memory by using the first fit algo⁃rithm,how to release the memory,as well as how to display memory.

Keywords:memory management；C language programming；partition allocation algorithms