试验三最佳适应算法试验报告

1、最佳适应算法实验报告一、实验目的了解首次适应算法、最佳适应方法、最差适应算法二、实验方法修改 Minix 操作系统的内存分配源码，实现最佳适应算法三、实验任务修改 Minix 操作系统中的内存分配源码，将首次适应算法更改为最佳适应算 法。重新编译系统映像文件，观察实验结果。四、实验要点内存分配、首次适应算法、最佳适应算法。五、实验内容5.1 minix 内存分配源码安装好 minix 操作系统以后， minix 系统的源码位于 /usr/src 目录中。其中， 与内存分配的相关源码则在 /usr/src/servers/pm/alloc.c 中。 minix 系统初始的内 存分配算法为首次适应

2、算法。在 minix 系统中，空闲的内存空间信息采用链表的信息储存起来，而操作系 统分配内存空间的过程则是在这个链表中寻找一个合适空间，返回内存空间的 地址，再更改链表中的内存空间信息。这就是 minix 系统分配内存的实质。5.2 分析首次适应算法首次适应算法，指的从空闲内存块链表的第一个结点开始查找，把最先找 到的满足需求的空闲内存块分配出去。这种算法的优点是分配所需的时间较 短，但这种算法会形成低地址部分形成很多的空间碎片，高地址区保留大量长 度较长的空闲内存块。内存分配的操作在 /usr/src/servers/pm/alloc.c 源文件中的 alloc_mem 函数中 完成。在函数

3、的初始位置，定义了两个用于遍历链表的指针变量，两个指针变 量的定义如下：registerstruct hole *hp, *prev_ptr;而 hole 结构体的定义如下：PRIVATE struct hole struct hole *h_next;phys_clicksh_base;phys_clicksh_len; holeNR_HOLES;先分析这个结构体的定义，这个结构体中，有三个变量， h_next 是一个指 向链表下一个结点的指针变量； h_base 则是指向这个链表所表示的空闲内存空 间的地址，h_len则是这个空闲内存空间的长度；phys_clicks的定义可以在 /usr

4、/src/include/minix/type.h 中找至U, phys_clicks 的定义为：typedef unsigned intpyhs_clicks;phys_clicks其实就是无符号的整数类型。另外，在函数中，还有一个变量，old_base,数据类型为phys_clicks用于 保存找至的内存空间地址。在寻找合适的内存空间之前,先初始化两个指针变量的值：prev_ptr = NIL_HOLE;hp = hole_head;这两句代码把 hp 这个指针变量指向了储存空闲内存空间链表的头结点。而 prev_ptr指针在指针遍历的过程中指向hp指针变量指向结点的前驱结点；此 时, h

5、p 指针变量指向的是链表的头结点,所以 prev_ptr 的变量值为 NIL_HOLE。在为这两个指针变量赋值以后，是通过一个 while 循环，直到找到满足需要 的内存大小块。循环代码如下：while (hp != NIL_HOLE &hp-h_baseh_baseh_le n= clicks) prev_ptr=hp;hp=hp-h_next;结合上面对结构体的分析，如果hp指向的链表结点中，空闲空间的长度大于或等于请求分配的大小，则进入if代码块；否则，prev_ptr和hp指向下一个 结点。如果找到操作系统找到了符合条件的空闲内存块，进入if代码块；if代码块中的代码，简单来说可以分成

6、两部分，第一部分是修改储存空闲内存块信息 的链表；另外一部分就是把找到的地址返回。其中，第一部分的代码如下：old_base = hp-h_base;hp-h_base += clicks;hp-h_len -= clicks;if (hp-h_len = 0)del_slot(prev_ptr, hp);第一行代码，使用一个变量，把分配出去的内存块的首地址记录下来；第 二行代码，因为要把首地址为 hp-h_base,大小为clicks的内存空间分配出去，所以要把这个空闲内存块的起始地址往后移动clicks，即对hp-h_base变量进行加法运算；第三行代码，更改空闲内存块的大小，即对hp-h

7、_len变量进行减法操作。最后，进行一个简单的判断。如果长度为 0，即表示这个链表结点表示的 空闲内存块已经全部被分出去，要在链表中删除这个结点。第二部分的代码只有一句：return (old_base)把找到的满足条件的内存块的首地址返回。上面整个的内存块寻找过程是放在一个dowhile循环中。循环语句为do while (swap_out()swap_out 函数的作用是寻找一个可以被从内存中转移到磁盘中的进程，并 把它转移到磁盘之中以腾出相应的内存空间。也就是说，如果找不到合适的储 存空间，系统会先尝试把部分的进程从内存移动到磁盘中；如果找不到合适的 内存空间，而且也没有可以被移动到磁盘

8、的进程时，整个函数就会返回NO_MEM,表示系统找不到合适的内存空间。5.3 改写为最佳适应算法最佳适应算法是从所有适合的空闲内存块找出最小的空闲内存块，这种方 法的优点是产生的空闲内存块碎片最小。缺点是搜索合适内存块的空闲时间比 首次适应算法长，效率低。跟首次适应算法不一样的是，最佳适应算法中，需要有一个变量，在查找 过程中记录找到最小空闲内存块的大小和地址，如果刚好找到一个大小等于所 需要大小的空闲内存块，则立即返回，不再寻找。在函数的起始位置声明一些变量，代码如下：registerstruct hole *hp, *prev_ptr, *min_hp;phys_clicksold_bas

9、e, min_size, found = 0;其中， hp, prev_ptr 和 old_base 的变量含义与首次适应算法中这些变两个的 含义相同。 min_hp 是用于记录储存有大小最小并满足需要的空闲内存块信息的 链表结点， min_size 则表示到目前为止找到的空闲内存块的最小的大小值，用 于查找过程中的大小比对。 found 则是一个标记位，表示是否已经找到了合适的 空闲内存块。修改以后，跟首次适应算法一样，查找空闲内存块的代码放在一个dowhile循环中，其意义在于当不能找到合适的空闲内存块时，操作系统先进 行交换，再寻找空闲的内存地址块；如果对内存空间进行交换以后仍然没有合

10、适的空闲内存块，则会返回一个内存不足的错误信息。在进行寻找前，需要对一些变量进行赋初值变量，赋初值的语句为：prev_ptr=NIL_HOLE;hp=hole_head;min_hp=NIL_HOLE;min_size=0xFFFF;found = 0;上面两句代码的意义与首次适应算法中的语句意义相同，都是为了设置链 表遍历操作的起点位置。把指向最小内存块对应的链表结点的指针变量设置为 NIL_HOLE同时将标记位设置为0,表示没有找到满足条件的空闲内存块。把 min_size的值设置为0xFFFF(unsigned in能够表示的最大整数)，以确保第一个空 闲的链表结点能够始终满足比 min

11、_size小的条件。用于寻找空闲内存块的代码跟首次适应算法一样，都是通过while循环实现,代码如下：while (hp != NIL_HOLE &hp-h_baseh_len=clicks) old_base=hp-h_base;del_slot(prev_ptr, hp);return (old_base); else if (hp-h_lenclicks &hp-h_lenh_len;found = 1;prev_ptr=hp;hp=hp-h_next;如果 hp 指向链表结点内存块大小刚好与所请求的大小相等，这种是最佳适 应算法最好的情况。把这个内存块的地址储存起来，在链表中删除这个结

12、点， 然后把这个地址返回。如果链表结点表示的空闲内存块大小比需要的大小大，但是比目前找到最 小的空闲内存块还要小，则把当前这个结点记录下来，再把标记为置1，表示已经找到可以分配出去的内存空间。然后在通过移动 prev_ptr 和 hp 两个指针变量 和 while 循环，遍历整个链表。在整个链表遍历完成以后， min_hp 则会指向满 足需要内存块之中大小最小的内存块。第二部分的代码是根据第一部分找到的内存块信息修改链表并把这个内存 块地址返回，这部分的代码为：if (found = 1) old_base = min_hp-b_base;min_hp-h_base += clicks;min

13、_hp-h_len -= clicks;retur n （old_base）;这部分代码先判断标记位，如果已经找到了内存块，先把 内存块的地址记录下来，然后把空闲地址往后移动clicks，长度减clicks。然后再把内存块的地址返回，这些操作与首次适应算法是一样的。5.4 minix 系统映像文件的编译对代码进行修改以后，需要对代码进行编译，再构建映像文件。5.4.1 代码的编译代码的编译通过 make工具进行编译。make工具会根据Makefile文件，自 动编译代码文件。make工具可以避免了编译过程中大量命令的输入；同时，也 不需要程序员手动理清各个代码文件和各个模块之间的依赖关系，大大提高开 发效率。退出编辑器，定位到目录 /usr/src/servers/pm 下，输入 make， make 工 具会自动编译源码，当没有错误以后，开始重新编译系统映像文件。5.4.2 映像文件编译与代码的编译类似，映像文件的编译同样是通过make工具实现。用于编译系统映像文件的 Makefile在/usr/src/tools中