这次比较尴尬，做完了忘记保存题目了，结果复盘的时候全程想不起来题目写的是啥

Exam

题干

我们提出了一种基于多个用户而平均分配的时间片轮转调度算法。对于每个进程来说，它的拥有者（用户，用 0 \sim 4 的数字表示）用一个新增字段 u_int env_user表示。我们要改进的这个调度算法，每次都会运行已经使用过的时间片最少的用户的进程（相同时取 id 小者），进程按在env_sched_list 中的顺序取出，每次运行该用户的第一个进程。

为了记录每个用户已经使用的时间片，我们设置了一个全局数组 static int user_time[]，当每次进程时间片耗尽时，对数组进行更新（对应用户加 pri即可）。例如对于如下的三个用户和三个进程，应该有这样的调度顺序（没保存所以只能上手绘图力！）

假装有图.jpg

请你按照这样的提示修改 schedule 函数，使其能满足刚才解释的按用户使用分配的时间片轮转算法。

void schedule(int yield) {
  static int count = 0; // remaining time slices of current env
  struct Env *e = curenv;
  static int user_time[5];
  
  if (需要更换 e 的条件) {
    if (e 不为 NULL && e 处在 ENV_RUNNABLE 状态) {
      移动 e 进程块
      修改 user_time 数组（加对应的 env_pri 即可）
    }
    if (无调度进程块) {
      panic
    }
遍历调度列表，查询列表中有哪些用户的进程块

遍历每个有进程块的用户，哪个用户用过的时间片最少（user_time 最小）

遍历调度列表，取出第一个该用户的进程块，e = env，count = env_pri

  }
  count--
  env_run
}
  • 教程组给出的伪代码大致如上，可惜这次没有把题目记下来，只能靠记忆来了
  • 给的解释实际上已经足够清晰了，只需要按着步骤走就行。

要注意额外声明变量时要考虑初始化的问题，有同学没初始化导致数组内的值反复横跳，根本没法debug（

一种可行的解答

贴一下我的做法，比较水，仅供参考

void schedule(int yield) {
  static int count = 0; // remaining time slices of current env
  struct Env *e = curenv;
  static int user_time[5];
  static int able[5];   // 额外声明了一个数组，当列表中存在该用户进程块时就置 1 ，否则保持 0
  for (int i = 0; i < 5; i++) { // 数组初始化
    able[i] = 0;
  }

  if (yield != 0  count == 0  e == NULL  e->env_status != ENV_RUNNABLE) {
    if (e != NULL) {
      TAILQ_REMOVE(&env_sched_list, e, env_sched_link);
    }
    if (e != NULL && e->env_status == ENV_RUNNABLE) {
      TAILQ_INSERT_TAIL(&env_sched_list, e, env_sched_link);
      // 记得 + env_pri，有笨比上来直接丢了这一句，根本调度不起来
      user_time[e->env_user] += e->env_pri;    
    }
    if (TAILQ_EMPTY(&env_sched_list)) {
      panic("schedule: no runnable envs");
    }
    e = TAILQ_FIRST(&env_sched_list);
    count = e->env_pri;
    struct Env *en = NULL;
      
    // 使用了 TAILQ_FOREACH 宏进行循环包装，循环查询有哪个用户在队列里，更新 able 数组
    TAILQ_FOREACH(en, &env_sched_list, env_sched_link) {
      if (able[en->env_user] == 0) {
        able[en->env_user] = 1;
      }
    }

    // 循环查看哪个用户使用的时间片最少（user_time 最小）
    int user = -1;
    u_int times = 111111111;
    for (int j = 0; j < 5; j++) {
      if (user_time[j] < times && able[j] == 1) {
        user = j;
        times = user_time[j];
      }
    }

    // 再循环调度链表，取出第一个目标用户的进程块，准备调度
    TAILQ_FOREACH(en, &env_sched_list, env_sched_link) {
      if (en->env_user == user) {
        e = en;               // 更换调度块
        count = e->env_pri;   // 重置时间片 count
        break;
      }
    }
  }
  count--;
  env_run(e);
}

Extra

题干

在 Lab3/4 中，我们已经处理了若干种异常，但在 CO 学习中经常出现的一种异常我们还没有处理，就是数值溢出（Ov）。在 R3000 中，硬件已经把溢出设置为 12 号异常，也就是说，只要设置对应的 handle 函数、异常向量与异常处理函数，我们就能顺利响应这个异常了。 Extra 的任务，就是响应 addi、add、sub 这三类指令可能产生的溢出异常。

这三类溢出的处理规则如下：

  • add：将指令修改为 addu，直接返回原 EPC
  • sub：将指令修改为 subu，直接返回原 EPC
  • addi：令 RF[rt]=RF[rs]/2+imm/2 ，返回至 EPC + 4 继续执行

下面还有很多提示，能想起来的就直接放下一部分了

思路

  • 首先需要明确我们需要做的有三件事：
  • 注册 handle 函数
  • 更新异常向量组，使其支持跳转至 Ov 的异常处理函数
  • 编写异常处理函数逻辑

前两步很简单，只要仿照对应文件中其他异常的处理方式来就可以了

注册 handle 函数

  • 在 kern/genex.S 中，增加处理 Ov 的 handle_ov ，可以命名其异常处理函数名为 do_ov
BUILD_HANDLER ov do_ov

更新异常向量组

  • 开始没看见直接写了溢出是12号异常，我直接当场下载 See Mips Run Linux 开始查（）
  • 在 kern/traps.c 中，更新异常向量：
void (*exception_handlers[32])(void) = {
    [0 ... 31] = handle_reserved,
    [0] = handle_int,
    [2 ... 3] = handle_tlb,
    [12] = handle_ov,        // 支持 handle_ov 以处理 ov
#if !defined(LAB)  LAB >= 4
    [1] = handle_mod,
    [8] = handle_sys,
#endif
};

异常处理函数 do_ov

  • 这个函数的核心就是分析 EPC 这条指令的内容并加以修改。

但由于一些我忘了的原因（有笨比），我们不能在内核态中直接通过用户态的虚拟地址获得地址上的值，所以如何访存就又成了一个问题。

题目提示：可以从 EPC 的 va 出发，找到它所对应的 pa，再将 pa 转换为 kseg0 区域的 va ，这样就能不通过页表之类的操作直接访问到了。所以大致的处理思路如下：

EPC(va)\to pa\to va(kseg0)\to *va(code)

许多同学在第一步转化物理地址时使用了宏 va2pa ，但是这玩意它只能找到 pa 所在页框的基地址，页内偏移它没有！然后好多人就绷了（）

还好我根本没想起来有这么个宏，还好我机智地使用了 page_lookup 老老实实地从页控制块出发找物理地址，这样就很轻松地记住了要加偏移，要不然直接用了 page2pa(p)，看过去就显然没有页内偏移（）

然后就很轻松地得到了目标指令。

  • 随后要分析指令类型进行异常处理

add 和 sub 两个指令修改太简单了，直接给指令值+1就能用了，在 addi 中要稍微多想一点。

addi 需要更新寄存器的值，同时也需要更新 EPC，这时就要从传入的用户栈中修改信息。修改过程中需要注意从指令里取出寄存器号之后要移动到最低位才能使用，有人 addi 了半天 0 号寄存器，才发现原来寄存器号还在高位呆着（）

最最后，调用一下 printk，异常统计变量自增，结束力！

一种可行的解答

直接上代码了，依然是一坨不可名状的东西

void do_ov(struct Trapframe *tf) {
  // printk("Got an ov\n");
  u_int badva = tf->cp0_epc;
  Pde *pgdir = curenv->env_pgdir;
  Pte **ppte = NULL;
  struct Page *p = page_lookup(pgdir, badva, ppte);
  // pgdir_walk(pgdir, badva, 0, &p);
  u_int badpa = page2pa(p) + (badva & 0xfff);
  u_int *badk0va = 0x80000000  badpa;
  u_int code = *badk0va;
  // printk("got code %x\n", code);
  if (code & 0x20000000) { // addi
    u_int s = (code & 0x3e00000) >> 21;
    u_int t = (code & 0x1f0000) >> 16;
    u_int svalue = tf->regs[s];
    u_int imm = code & 0xffff;
    tf->regs[t] = svalue / 2 + imm / 2;
    tf->cp0_epc += 4;
    // printk("inform:%x %d %d %x %x\n", code, s, t, svalue, tf->regs[t]);
    printk("addi ov handled\n");
  } else if ((code & 0x1f) == 0) { // add
    printk("add ov handled\n");
    *badk0va = code + 1;
  } else { // sub
    printk("sub ov handled\n");
    *badk0va = code + 1;
  }
  curenv->env_ov_cnt++;
}

debug 思路

在第一次写完之后，测试很华丽地给我返回了错误值：$v0 = 0xffffffff（-1），这是测试程序提示处理有误的返回值。想要de出来bug在哪出现的，自然需要回到那个返回错误值的地方看一眼。所以我就在函数里打了几个 printk，现在还在注释里（）。 同时把三个会 return -1 的地方修改成了返回不同的值，然后看看到底是哪里寄了。

/* tests/lab3_ov/test_ov.c */

int main() {
  unsigned int src1, src2, dst;
    
  /*
   * 测试 add, code here
   */
  if (dst != (src1 + src2)) {
    return -1; // 如果异常处理结果不正确进程将运行结束并返回-1
  }

  /*
   * 测试 sub, code here
   */
  if (dst != (src1 - src2)) {
    return -2; // change the return value to figure the error place
  }

  /*
   * 测试 addi, code here
   */
  if (dst != (src1 / 2 + 10)) {
    return -3; // change too
  }
  return dst;
}

最后一看，哈哈 return -3 ，addi 我来辣（×）