内容与设计思想

修改Minix3.1.2a的进程管理器，改进brk系统调用的实现，使得分配给进程的数据段栈段空间耗尽时，brk系统调用给该进程分配一个更大的内存空间，并将原来空间中的数据复制至新分配的内存空间，释放原来的内存空间，并通知内核映射新分配的内存段。

实验过程

MINIX3.1.2安装

下载镜像文件

https://wiki.minix3.org/doku.php?id=www:download:previousversions
新建虚拟机
修改虚拟机设置
启动虚拟机并安装

修改网络模式、安装软件包

mv /etc/rc.daemons.dist  /etc/rc.daemons

ssh远程连接
```
passwd root
```

修改内存匹配为最佳匹配

修改思路：MINIX中用链表管理空闲内存段，其中链表结点hole定义如下：

默认的内存匹配方式为first-hit，若修改为best-fit，则需要先遍历链表来寻找最佳匹配段

修改代码：

/*===========================================================================*
 *              alloc_mem                    *
 *===========================================================================*/
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.  Swap other processes out if needed.
 */
  register struct hole *hp, *prev_ptr, *best, *prev_best;
  phys_clicks old_base;
  best = NULL;
  do {
        prev_ptr = NIL_HOLE;
    hp = hole_head;
    while (hp != NIL_HOLE && hp->h_base < swap_base) {
        if (hp->h_len >= clicks && (best == NULL || best->h_len < hp->h_len)) {
            best = hp;
            prev_best = prev_ptr;
        }
        prev_ptr = hp;
        hp = hp->h_next;
    }
    if (best != NULL) {
        old_base = best->h_base;    /* remember where it started */
        best->h_base += clicks; /* bite a piece off */
        best->h_len -= clicks;  /* ditto */

        /* Remember new high watermark of used memory. */
        if(best->h_base > high_watermark)
            high_watermark = hp->h_base;

        /* Delete the hole if used up completely. */
        if (best->h_len == 0) del_slot(prev_best, best);

        /* Return the start address of the acquired block. */
        return(old_base);
    }
  } while (swap_out());     /* try to swap some other process out */
  return(NO_MEM);
}

修改brk()系统调用，当内存不足时申请新的内存

修改思路：

MINIX中的内存布局如下：

默认的adjust()函数会计算增长后的数据段指针gap_base和栈段指针lower，若发现lower<gap_base则说明空间不足，不会对数据段进行增长。需要修改的就是出现这种情况时，不直接返回ENOMEM，而是先调用alloc_new_mem()，尝试利用alloc_mem()申请一个更大的内存段来存放进行内存，若分配成功，则能确保数据段增加后不会与栈段发生冲突，再执行增加数据段长度。

于是当数据段和栈段发生冲突时，我们先确定新分配的内存段大小为多少。我的计算方法是，先计算至少要多少空间才能装下增长后的进程，再乘以1.5，留出给栈段增长的内存空间：

if (lower < gap_base) {
    alloc_clicks = (vir_clicks) ((mem_sp->mem_vir + mem_sp->mem_len - mem_dp->mem_vir + gap_base - lower) * 1.5);
    if (alloc_new_mem(rmp, alloc_clicks) == -1)
      return(ENOMEM); /* data and stack collided */
  }

在alloc_new_mem()中，需要先用alloc_mem()方法申请内存并写0清空，记录旧的数据段和栈段的物理地址，并计算新的数据段和栈段的物理地址，通过sys_abscopy()将内存复制到新申请的空间上，最后修改数据段和栈段的内存映射（物理地址和虚拟地址）。

如下图，进程的mp_seg数组记录了虚拟地址和物理地址的映射关系，因此不需要修改数据段的虚拟地址，只要把虚拟地址看成相对偏移量，修改栈段的虚拟地址，以及两者的物理地址即可。

还需要注意的是，大多数内存计算是以clicks为单位的，但sys_abscopy()和sys_memset()中的参数是以bytes为单位的，所以需要将所有clicks左移CLICK_SHIFT位进行click到byte的单位转换。

修改代码：

/*===========================================================================*
 *        alloc_new_mem              *
 *===========================================================================*/
PUBLIC int alloc_new_mem(rmp, new_clicks)
register struct mproc *rmp;
vir_clicks new_clicks;
{
  register struct mem_map *mem_sp, *mem_dp;
  vir_clicks old_clicks, new_phys, new_data_clicks, new_stack_clicks, old_data_clicks, old_stack_clicks, data_len, stack_len;
  int r;
  mem_dp = &rmp->mp_seg[D]; /* pointer to data segment map */
  mem_sp = &rmp->mp_seg[S]; /* pointer to stack segment map */
  old_clicks = mem_sp->mem_vir + mem_sp->mem_len - mem_dp->mem_vir;
  if ((new_phys = alloc_mem(new_clicks)) == 0)
    return -1;
  if ((r = sys_memset(0, new_phys << CLICK_SHIFT, new_clicks << CLICK_SHIFT)) != OK) {
    panic(__FILE__, "memset error.", r);
  }
  old_data_clicks = mem_dp->mem_phys;
  old_stack_clicks = mem_sp->mem_phys;
  new_data_clicks = new_phys;
  new_stack_clicks = new_phys + new_clicks - mem_dp->mem_vir;
  if ((r = sys_abscopy(old_data_clicks << CLICK_SHIFT, new_data_clicks << CLICK_SHIFT, mem_dp->mem_len << CLICK_SHIFT)) < 0)
    panic(__FILE__, "abscopy error.", r);
  if ((r = sys_abscopy(old_stack_clicks << CLICK_SHIFT, new_stack_clicks << CLICK_SHIFT, mem_sp->mem_len << CLICK_SHIFT)) < 0)
    panic(__FILE__, "abscopy error.", r);
  free_mem(old_data_clicks, old_clicks);

  mem_dp->mem_phys = new_phys;
  mem_sp->mem_phys = new_phys + new_clicks - mem_sp->mem_len;
  mem_sp->mem_vir = mem_dp->mem_vir + mem_sp->mem_phys - mem_dp->mem_phys;
  return 0;
}

测试：

修改之前的测试结果，最多只能增加到64kb就不能再增加：

修改后的测试结果，可以增加到16MB：

总结

在修改alloc_mem_new()函数时出现了一个问题，运行测试程序会报错core dumped

搜索资料后发现，这是由于申请完内存空间后没有写0清空导致的，也就是每次调用alloc_mem()后都要用sys_memset()清空空间。
```
if ((new_phys = alloc_mem(new_clicks)) == 0)
    return -1;
  if ((r = sys_memset(0, new_phys << CLICK_SHIFT, new_clicks << CLICK_SHIFT)) != OK) {
    panic(__FILE__, "memset error.", r);
  }
```
由于编译器比较老旧，对于每个函数都需要把局部变量的定义放在函数首部，定义完毕后在进行计算。