修改brk的实现方式，将内存块的分配方式从首次适配更改为最佳适配

# alloc.c

修改 /usr/src/servers/pm/alloc.c 中的 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 best 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_ptr, * temp;
  phys_clicks old_base;
  int flag = 0;
  do {
    prev_ptr = NIL_HOLE;
    hp = hole_head;
    while (hp != NIL_HOLE && hp->h_base < swap_base) {
      if (hp->h_len >= clicks && ((hp->h_len < best_ptr->h_len) || (flag ==
        0))) {
        best_ptr = hp;
        temp = prev_ptr;
        flag = 1;
      }
      prev_ptr = hp;
      hp = hp->h_next;
    }
  } while (swap_out()); /* try to swap some other process out */
  if (flag == 1) {
    old_base = best_ptr->h_base;
    best_ptr->h_base += clicks;
    best_ptr->h_len -= clicks;
    /* Remember new high watermark of used memory. */
    if (best_ptr->h_base > high_watermark)
      high_watermark = best_ptr->h_base;
    /* Delete the hole if used up completely. */
    if (best_ptr->h_len == 0) del_slot(temp, best_ptr);
    /* Return the start address of the acquired block. */
    return(old_base);
  }
  return(NO_MEM);
}

# 修改 brk 中的 adjust 函数

修改 adjust 函数，计算程序当前的空闲空间是否足够分配：若足够，则调整数据段指针，堆栈指针；若不够，调用 allocate_new_mem 函数申请新的足够大的内存空间

Stack Frame

	/* Compute size of gap between stack and data segments. */
	delta = (long) mem_sp->mem_vir - (long) sp_click;
	lower = (delta > 0 ? sp_click : mem_sp->mem_vir);
#define SAFETY_BYTES (384 * sizeof(char *))
#define SAFETY_CLICKS ((SAFETY_BYTES + CLICK_SIZE - 1) / CLICK_SIZE)
	gap_base = mem_dp->mem_vir + data_clicks + SAFETY_CLICKS;
	if (lower < gap_base){ /* data and stack collided */
	if(allocate_new_mem(rmp, (phys_clicks)(mem_sp->mem_vir + mem_sp->mem_len
- mem_dp->mem_vir)) == ENOMEM)
	return(ENOMEM);
}

被调用的 allocate_new_mem 函数要完成三件事情：

申请一段足够大的内存空间： alloc_mem(new_mem_clicks)
将程序现有的数据段和堆栈段的内容分别拷贝至新内存区： sys_abscopy(old_data_addr, new_data_addr, databytes)
释放原空间： free_mem(old_data_base, old_mem_clicks)

PUBLIC int allocate_new_mem(rmp, old_mem_clicks)
register struct mproc* rmp;
phys_clicks old_mem_clicks;
{
  register struct mem_map* mem_sp, * mem_dp;
  phys_clicks new_mem_clicks, new_data_base, old_data_base, old_stack_base,
    new_stack_base;
  phys_bytes new_data_addr, old_data_addr, new_stack_addr, old_stack_addr;
  phys_bytes databytes, stackbytes;
  mem_dp = &rmp->mp_seg[D];
  mem_sp = &rmp->mp_seg[S];
  new_mem_clicks = old_mem_clicks * 2;
  new_data_base = alloc_mem(new_mem_clicks);
  if (new_data_base == NO_MEM)
    return (NO_MEM);
  old_data_base = mem_dp->mem_phys, old_stack_base = mem_sp->mem_phys;
  new_stack_base = new_data_base + new_mem_clicks - mem_sp->mem_len;
  new_data_addr = (phys_bytes)(new_data_base << CLICK_SHIFT);
  old_data_addr = (phys_bytes)(old_data_base << CLICK_SHIFT);
  new_stack_addr = (phys_bytes)(new_stack_base << CLICK_SHIFT);
  old_stack_addr = (phys_bytes)(old_stack_base << CLICK_SHIFT);
  databytes = (phys_bytes)(mem_dp->mem_len << CLICK_SHIFT);
  stackbytes = (phys_bytes)(mem_sp->mem_len << CLICK_SHIFT);
  if (sys_abscopy(old_data_addr, new_data_addr, databytes) < 0 ||
    sys_abscopy(old_stack_addr, new_stack_addr, stackbytes) < 0)
    panic(__FILE__, "do_fork can't copy", -1);
  rmp->mp_seg[D].mem_phys = new_data_base;
  rmp->mp_seg[S].mem_phys = new_stack_base;
  rmp->mp_seg[S].mem_vir = mem_dp->mem_vir + new_mem_clicks - mem_sp -
    > mem_len;
  free_mem(old_data_base, old_mem_clicks);
  return (OK);
}

# 测试结果

Test2

ECNU DaSE2020 OS_HW4 内存管理

MINIX3内存管理

# alloc.c

# 修改 brk 中的 adjust 函数

# 测试结果