操作系统实验（minix部分）
——内存分配
实验目的
一、加深操作系统存储器管理的理解；
二、分析各种内存分配策略的性能；
三、修改Minix系统的存储分配算法。
实验过程
首先我们来看看这次实验的具体内容，了解了我们的要做的方向再去考虑应该去着重看那些具体的理论知识。具体要求如下：
1、用fork（）、exec（）函数创建新进程时，需要对新进程分配内存。在现有Minix系统中，内存管理器采用首次适配算法对新创建进程进行内存分配。在本实验中，改存储分配算法为最佳匹配算法，分析系统性能。
2、修改后重新编译系统。
一、实验准备：
众所周知存储器是一种必须仔细管理的重要资源。在理想的情况下，我们都希望有无穷大、快速并且内容不易变的存储器，同时又希望它是廉价的。但目前的技术不能够提供这样的存储器，因此大部分计算机都有一个存储器层次结构，它由非常快速、昂贵、易失的高速缓存（cache），若干兆字节的中等速度、中等价格、易变的主存储器(RAM),以及数百兆或数千兆字节的低速、廉价、不易失的磁盘组成。操作系统的工作就是协调这些存储器的使用。操作系统中管理管理存储器的部分称为存储管理器（memory manage）。它的任务是跟踪正在使用哪些存储器，哪些存储器空闲，在进程需要时为它分配存储器，使用完毕后释放存储器，并且在主存无法容纳所有进程时管理主存和磁盘间的交换。我们大概的了解完基本的存储器概念，接着我们可以去看看具体的内容：
存储管理系统主要分两类：在运行期间将进程在主存和磁盘之间进行移动的系统（交换和分页）和不进行移动的系统。我们要做的minix系统的内存管理是非常简单的，既不用分页也不用交换，所以我们主要研究不进行移动的系统。但如果大家想更深层的了解操作系统的知识，就应该好好看看交换和分页，但我们也要清醒的认识到：交换和分页在很大程度上是由于缺少足够的主存以同时容纳所有的进程而引入的。随着主存越来越便宜，选择某种存储器管理方案的理由
也许会变得过时，除非程序变大的速度比存储器降价的速度还要快。
下面我们来讨论不进行移动的系统。可以分为两种：单道程序和固定分区
的多道程序。最简单的存储器管理方案是同一时刻只进行运行一道程序，应用程
序和操作系统共享存储器。这种方案可以分为3中变形：1、操作系统可以位于
主存最低端的随机存取存储器（RAM ）中；2、操作系统可以位于主存最高端的只
读存储器（ROM ）中；3、还可以将设备驱动程序位于内存最高端的ROM 中，而让
操作系统的其他部分位于低端的RAM 中。具体如下图：
这样组织系统时，同一时刻只能有一个进程在存储器中进行。一旦用户输
入一个命令，操作系统就把需要的程序从磁盘复制到存储器中并执行；在进程
运行结束后，操作系统显示提示符并等待新的命令。收到新的命令时，它把新
的程序加载到存储器中，覆盖掉原来的程序。
虽然单道程序常常用于带有简单操作系统的小型计算机，但我们往往希望
能有多个进程同时运行。在分时系统中，允许多个进程同时在存储器中，这意
味着当一个进程因为等待I/O 结束而阻塞时，其他的进程可以利用CPU ，因而
提高了CPU 的利用率。实现多道程序最容易的办法是把主存简单地划分成n 个
分区（可能不相等），分区的划分可以在系统启动时手工完成。
当一个作业到达时，可以把它放到能够容纳它的最小的分区输入队列中。
因为这种方案中分区大小是固定的，一个分区中未被作业使用的空间就白白浪
费了。把输入作业排成多个队列时，在大分区的队列为空而小分区的队列为满
的情况下，其缺点就变得很明显。这种由操作员设置好随后就不能在被改的固
定分区的系统，曾在IBM 大型机的OS/360中使用了很多年，被称为MFT （具有
固定数目任务的多道程序，或OS/MFT ）。它易于理解也易于实现:输入作业被送
入队列排队直到有适合的分区可用，随后作业被装入分区运行直到它结束。
有了上述的知识，我们再深入到minix 中，去了解minix 的内存管理。Minix
的存储管理器保存着一张按照内存地址排列的空洞链表。当由于执行系统调用
FORK 或EXEC 需要内存时，系统将用首次适配算法对空洞列表进行搜索找出一
个足够大的空洞。一旦一个程序被装入内存，它将一直保持在原来的位置直到
运行结束，它永远不会被换出或移动到内存的其他地方去，为它分配的空间也
不会增长或缩小。Minix 采用的这个方案是考虑了三个因素后的结果：（1）minix
是用于个人计算机的，而不是大型的分时系统；（2）希望minix 在所有的IBM PC
上运行；（3）希望系统的实现很直观以利于在其他小型机上实现。
Minix 另一个不同寻常的方面是它的内存管理方案实现方法。它不是内核 用户程序 位于RAM 中 的操作系统 位于ROM 中 的操作系统 用户程序 ROM 中的设 备驱动程序
用户程序 位于RAM 中 的操作系统
的部分，而是由一个运行在用户空间、使用标准的消息机构和内核通信的管理进程完成的。
Minix中有两种情况需要分配内存。第一种是在一个进程执行fork时，为子进程分配所需要的空间；第二种是在一个进程通过EXEC系统调用修改它的内存映象时，旧的映象被作为空洞送到空闲表，需要为新的映象分配内存。在内存中，新的映象的位置可能与已释放的内存位置不同，它的位置取决于在什么地方能找到合适的空洞。在进程因为退出或被信号杀死而结束时内存也将被释放。需要注意的一点是，用于子程序的旧内存是在新内存分配之前被释放的，因此新内存可以使用子进程的内存。这样，一系列的FORK和EXEC对（比如shell 设置一个管道）将会使所有的进程都是邻接的，中间没有空洞。如果我们在旧的内存被释放之前就分配新内存，就可能产生空洞。
内存管理器有两个关键数据结构：进程表和空洞表。
在minix中，操作系统的进程管理、内存管理和文件系统这三部分都有自己的进程表，每个部分的表仅包含了自己需要的域。为了保持同步，在进程创建或结束时，这三个部分都要更新它们的表反映新的情况。内存管理器的进程表叫做mproc，定义在/usr/src/mm/中。它包含了与进程内存分配有关的全部域和一些附加信息。
内存管理器另外一个主要的表是空洞表，定义在中。它按照内存地址递增的顺序列出了内存的各个空洞。数据和堆栈段之间的空隙不认为是空洞，它们已经被分配给进程了，所以它们没有包含在空洞表中。空洞有三个域：以块为单位的空洞的基地址、以块为单位的空洞的长度和一个指向表中下一个入口的指针。这个表是单向连结的，所以从任何一个空洞开始找到下一个空洞很容易，但是如果要找上一个空洞就必须从头开始搜索直到找到给定的空洞。在空洞表上的主要操作是分配一块指定大小的内存和归还一块指定已经分配的内存。在分配内存时，首先从最低的地址开始搜索空洞表，直到找到一个足够大的空洞（首次适配）。随后从空洞中减去段需要的空间，或在极少的大小相等的情况下从空洞表中删除空洞来为段分配空间。这个方案简单快速，但是存在着内零头（最后一个块可能会浪费多达255字节空间,因为分配的总是整数个数）和外零头的问题。
我们现在该研究一下该实验的内容了，minix自身是按首次适配法分配内存，我们的要求是将分配算法由首次适配法改为最佳适配法。它搜索整个链表以找出够用的最小空洞。最佳适配算法试图找出最接近实际需要的大小的空洞，而不是先使用一个以后可能会用到的大空洞。由于最佳适配法每次被调用时都要搜索整个链表，它要比首次适配法慢。有点出乎意料的是，它还会导致比首次适配算法更多的内存浪费，因为它倾向于生成大量没用的很小的空洞，而总的来说首次适配算法生成的空洞更大。但我们是为了实验要求达到，来编写程序改变算法，达到学习的目的。
程序的编写应该是比较容易，主要是要读懂文件。在此文件的基础上修改来改变算法。
二、代码编写：
在新的算法的设计中，我们首先找出一块足够大的内存空洞空间，用
temp_ptr 指针指向该空间地址，然后，继续移动指针，对后面的空洞进行遍历，
以图寻找出比当前存贮的指针空间小但大于所需空间的内存空洞，然后依次往
后，直到遍历完整个内存空洞链表，整个过程就是一个一步冒泡的排序，只是直
接将内存的空洞中满足要求的最小空洞找出并最终将该空洞分配给提出要求的
进程。文件是系统跟踪记录内存使用和空闲状况的地方，它有四个出口：
1、alloc_mem 请求一块给定大小的内存。
2、free_hole 归还不再需要的内存。
3、max_hole 计算最大可用的长度。
4、mem_init 在内存管理器开始运行时初始化空闲表。
alloc_mem 在按照内存地址排列的空洞表中使用首次适配法查找。我们也就
是要修改这部分代码，将首次适配法改为最佳匹配法。
流程图如下：
Y
N 没有足够内存
具体代码如下：
PUBLIC phys_clicks alloc_mem(clicks)
phys_clicks clicks; /* amount of memory requested */
{
表为空 找出第一个足 够大的空洞 再比较整个表找出最佳空洞 更新空闲表
/* Allocate a block of memory from the free list using first fit. The
* block consists of a sequence of contiguous bytes, whose length in clicks is given by 'clicks'. A pointer to the block is returned. The
block is always on a click boundary. This procedure is called when memory is needed for FORK or EXEC.
*/
register struct hole *hp, *prev_ptr;
struct hole *temp_ptr,*temp_ptr2; /*temp_ptr2 point to the node just
prev temp_ptr*/
phys_clicks old_base;
hp = hole_head;
temp_ptr=NIL_HOLE;
/*search the first hole which is big enough*/
while (hp!=NIL_HOLE)
{
if (hp->h_len>=clicks)
{
temp_ptr=hp;
temp_ptr2=prev_ptr;
break;
}
prev_ptr=hp;
hp=hp->h_next;
}
/*hp=temp_ptr;*/
/*
scan the whole hole list to find the best fit hole.
the best fit hole is identified by temp_ptr
*/
while (hp!=NIL_HOLE){
if (hp->h_len>=clicks && hp->h_len
{
temp_ptr=hp;
temp_ptr2=prev_ptr;
}
prev_ptr=hp;
hp=hp->h_next;
}
if (temp_ptr!=NIL_HOLE)
{
/* We found a hole that is big enough. Use it. */
old_base=temp_ptr->h_base;/* remember where it started */
temp_ptr->h_base+=clicks; /* bite a piece off */
temp_ptr->h_len-=clicks;/* ditto */
/* If hole is only partly used, reduce size and return. */
if (temp_ptr->h_len!=0) return(old_base);
/* The entire hole has been used up. Manipulate free list. */
del_slot(temp_ptr2,temp_ptr);
return(old_base);
}
else
return(NO_MEM);/*there is no enough memory*/
}
实验收获
通过实验的经历我们可以看到最重要的东西不是编写代码，而是编写前的准备工作。内存分配算法的代码比较简单，改写也是将链表的指针在每次分配内存时重新遍历一次。就本次实验来看，应该着重研究内存管理器的两个数据结构：进程表和空洞表。尤其是空洞表，我们本次要修改的部分也是和这个空洞表有十分密切的关连。
要说收获，编程上其实并没什么，主要是在准备期间去看的minix的内存分配策略，在研究一下源代码来更深层的理解minix的内存分配原理。这对对整个操作系统的学习都有很大的帮助，也只有亲身去体会才会有很深的印象和理解。虽然编码不难，但要去理解源代码中的每个变量的含义却需要去将实际代码的编写情况和实验原理结合起来。尤其是在释放空洞时如何判断这块新释放的内存能否与任何一方的邻居合并，如果能就要调用merge合并空洞更新空闲表，这个知识点也许只有通过实验才能真正的理解。
总之，收获是因人而异，大家作实验的目的也就是把自己熟悉的知识加深印象，通过实验去学习未懂的内容。
参考文献
操作系统设计与实现（第二版）（上下册） Andrew
——电子工业出版社
计算机操作系统
汤子瀛哲凤屏汤小丹——西安电子科技大学出版社