Lab 3

功能实现

`sys_spawn`

参考 sys_fork 以及 sys_exec 的实现.

通过 MemorySet::from_elf 解析 elf 文件得到 memory_set, user_sp, entry_point, 查询得到 trap_cx_ppn.
在内核空间进行 pid_handle 与 kernel_stack 分配, 并参考 fork 的实现新建 TaskControlBlock.
将新建的 TaskControlBlock 设置为当前 TaskControlBlock 的子进程.
修改新建 TaskControlBlock 的 trap_cx 的值.

stride 调度算法

设置进程初始 stride 为 0, 初始 priority 为 16.
TaskManager::add 将 task 加入队列时, 按 stride 递增顺序选择插入位置.
TaskManager::fetch 获得队首 task 时, 按 priority 更新其 stride 值.

问答题

stride 算法原理非常简单, 但有一个比较大的问题. 例如两个 pass = 10 的进程, 使用 8bit 无符号整型储存 stride, p1.stride = 255, p2.stride = 250, 在 p2 执行一个时间片后, 理论上下一次应该 p1 执行.
1. 实际情况是轮到 p1 执行吗? 为什么?
  
  答: 不是, p2 执行并更新 stride 后, 溢出了 8bit 无符号整型的表示范围, p2.stride = 4, 因此下一次还是 p2 执行.

**之前要求进程优先级 $\ge 2$ 其实就是为了解决这个问题. 可以证明, 在不考虑溢出的情况下, 在进程优先级全部 $\ge 2$ 的情况下, 如果严格按照算法执行, 那么 `STRIDE_MAX – STRIDE_MIN` $\le$ `BigStride / 2`.**

2. **为什么? 尝试简单说明.**

    答: 进程优先级 $\ge 2$ 的情况下, stride 的更新值至多为 `BigStride / 2`. 若某次 stride 更新后 `STRIDE_MAX – STRIDE_MIN > BigStride / 2`, 说明在 stride 更新前被挑选的进程满足  `STRIDE – STRIDE_MIN > 0`, 即并未选择 stride 最小的进程进行调度, 与算法的选取原则矛盾.



3. **已知以上结论, 考虑溢出的情况下, 可以为 stride 设计特别的比较器, 让 `BinaryHeap<Stride>` 的 `pop` 方法能返回真正最小的 stride. 补全下列代码中的 `partial_cmp` 函数, 假设两个 stride 永远不会相等.**

    use core::cmp::Ordering;
struct Stride(u64);

impl PartialOrd for Stride {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        let cmp: u64 = self.0 - other.0; 
        if cmp > BigStride / 2 {
            Some(Ordering::Less)
        } else {
            Some(Ordering::Greater)
        }
    }
}

impl PartialEq for Stride {
    fn eq(&self, other: &Self) -> bool {
        false
    }
}