OS Lab3 Report

OS Lab3 实验报告

实现功能

本次实验我首先在 sys_mmap 中加入了对 p->max_page 的更新维护；然后增加了 sys_spawn 系统调用，调用 allocproc 创建子进程，并调用 loader 加载目标程序，将子进程加入任务队列中，返回子进程 PID；最后在进程调度中引入 stride 调度算法，为进程增加 prio 和 stride 两个字段，在调度任务 pop_queue 时扫描得到 stride 最小的任务弹出执行并更新 stride。

问答题

  1. 不是，因为 250 + 10 = 260 > 255 溢出了 8bit 无符号整数的最大表示值 255，实际存储的值为 260 - 256 = 4，由于 4 < 255，导致下一次被调度的又是 p2；
  2. 可用归纳法证明。在题设条件下，进程每次 pass <= BIG_STRIDE / 2。
    初始各进程 stride 相同，均为 0，经过第 1 次调度后：STRIDE_MAX(1) – STRIDE_MIN(1) = pass(1) - 0 <= BIG_STRIDE / 2；
    设经过第 k 次调度后满足 STRIDE_MAX(k) – STRIDE_MIN(k) <= BIG_STRIDE / 2，第 k + 1 次调度时会选择 STRIDE_MIN(k) 的进程执行，STRIDE_MIN(k) + pass(k) <= STRIDE_MIN(k) + BIG_STRIDE / 2，新的 STRIDE_MIN(k+1) > STRIDE_MIN(k)，STRIDE_MAX(k+1) = max{STRIDE_MAX(k), STRIDE_MIN(k) + pass(k)}，有：
    1. 若 STRIDE_MAX(k) >= STRIDE_MIN(k) + pass(k)，则 STRIDE_MAX(k+1) - STRIDE_MIN(k+1) = STRIDE_MAX(k) - STRIDE_MIN(k+1) < STRIDE_MAX(k) – STRIDE_MIN(k) <= BIG_STRIDE / 2；
    2. 若 STRIDE_MIN(k) + pass(k) > STRIDE_MAX(k)，则 STRIDE_MAX(k+1) - STRIDE_MIN(k+1) = STRIDE_MIN(k) + pass(k) - STRIDE_MIN(k+1) <= STRIDE_MIN(k) + BIG_STRIDE / 2 – STRIDE_MIN(k) = BIG_STRIDE / 2；
      由归纳法命题得证。
  3. 如下，如果两者差值超过 BIG_STRIDE / 2 说明发生了溢出，要将直接比较的结果取反。 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    typedef unsigned long long Stride_t;
    const Stride_t BIG_STRIDE = 0xffffffffffffffffULL;
    int cmp(Stride_t a, Stride_t b) {
        // YOUR CODE HERE
        // return 1 if a > b
        // return -1 if a < b
        // return 0 if a == b
        if (a == b) return 0;
        else if(((a > b) && (a - b <= BIG_STRIDE / 2))
                || (a < b) && (b - a > BIG_STRIDE / 2))
            return 1;
        else return -1;
    }