文档介绍：最佳适应算法实验报告
实验目的
了解首次适应算法、最佳适应方法、最差适应算法
实验方法
修改Minix操作系统的内存分配源码,实现最佳适应算法
实验任务
修改Minix操作系统中的内存分配源码,将首次适应算法更改为最佳适应算法。重新编译系统映像文件,观察实验结果。
实验要点
内存分配、首次适应算法、最佳适应算法。
实验内容
minix内存分配源码
安装好minix操作系统以后,minix系统的源码位于/usr/src目录中。其中,与内存分配的相关源码则在/usr/src/servers/pm/。minix系统初始的内存分配算法为首次适应算法。
在minix系统中,空闲的内存空间信息采用链表的信息储存起来,而操作系统分配内存空间的过程则是在这个链表中寻找一个合适空间,返回内存空间的地址,再更改链表中的内存空间信息。这就是minix系统分配内存的实质。
分析首次适应算法
首次适应算法,指的从空闲内存块链表的第一个结点开始查找,把最先找到的满足需求的空闲内存块分配出去。这种算法的优点是分配所需的时间较短,但这种算法会形成低地址部分形成很多的空间碎片,高地址区保留大量长度较长的空闲内存块。
内存分配的操作在/usr/src/servers/pm/。在函数的初始位置,定义了两个用于遍历链表的指针变量,两个指针变量的定义如下:
register struct hole *hp, *prev_ptr;
而hole结构体的定义如下:
PRIVATE struct hole {
struct hole *h_next;
phys_clicks h_base;
phys_clicks h_len;
} hole[NR_HOLES];
先分析这个结构体的定义,这个结构体中,有三个变量,h_next是一个指向链表下一个结点的指针变量;h_base则是指向这个链表所表示的空闲内存空间的地址,h_len则是这个空闲内存空间的长度;phys_clicks 的定义可以在
/usr/src/include/minix/,phys_clicks的定义为:
typedef unsigned int pyhs_clicks;
phys_clicks其实就是无符号的整数类型。
另外,在函数中,还有一个变量,old_base,数据类型为phys_clicks,用于保存找到的内存空间地址。
在寻找合适的内存空间之前,先初始化两个指针变量的值:
prev_ptr = NIL_HOLE;
hp = hole_head;
这两句代码把hp这个指针变量指向了储存空闲内存空间链表的头结点。而prev_ptr指针在指针遍历的过程中指向hp指针变量指向结点的前驱结点;此时,hp指针变量指向的是链表的头结点,所以prev_ptr的变量值为NIL_HOLE。
在为这两个指针变量赋值以后,是通过一个while循环,直到找到满足需要的内存大小块。循环代码如下:
while (hp != NIL_HOLE && hp->h_base < swap_base) {
…}
hp指针变量就是系统用于遍历链表的指针。操作系统运行的过程中也会占用部分内存