实践作业1

进程创建

大家一定好奇过为啥进程创建要用fork + execve这么一个奇怪的系统调用，就不能直接搞一个新进程吗？思而不学则殆，我们就来试一试！这章的编程练习请大家实现一个完全 DIY 的系统调用 spawn，用以创建一个新进程。

spawn 系统调用定义( 标准spawn看这里 )：

fn sys_spawn(path: *const u8) -> isize

  • syscall ID: 400

  • 功能：新建子进程，使其执行目标程序。

  • 说明：成功返回子进程id，否则返回 -1。

    • 可能的错误：

      无效的文件名。进程池满/内存不足等资源错误。

TIPS：虽然测例很简单，但提醒读者 spawn 不必 像 fork 一样复制父进程的地址空间。

实验练习2

实践作业

stride 调度算法

ch3 中我们实现的调度算法十分简单。现在我们要为我们的 os 实现一种带优先级的调度算法：stride 调度算法。

算法描述如下:

  1. 为每个进程设置一个当前 stride，表示该进程当前已经运行的“长度”。另外设置其对应的 pass 值（只与进程的优先权有关系），表示对应进程在调度后，stride 需要进行的累加值。
  2. 每次需要调度时，从当前 runnable 态的进程中选择 stride 最小的进程调度。对于获得调度的进程 P，将对应的 stride 加上其对应的步长 pass。
  3. 一个时间片后，回到上一步骤，重新调度当前 stride 最小的进程。

可以证明，如果令 P.pass = BigStride / P.priority 其中 P.priority 表示进程的优先权（大于 1），而 BigStride 表示一个预先定义的大常数，则该调度方案为每个进程分配的时间将与其优先级成正比。证明过程我们在这里略去，有兴趣的同学可以在网上查找相关资料。

其他实验细节：

  • stride 调度要求进程优先级 ≥2，所以设定进程优先级 ≤1 会导致错误。
  • 进程初始 stride 设置为 0 即可。
  • 进程初始优先级设置为 16。

为了实现该调度算法，内核还要增加 set_prio 系统调用

// syscall ID：140
// 设置当前进程优先级为 prio
// 参数：prio 进程优先级，要求 prio >= 2
// 返回值：如果输入合法则返回 prio，否则返回 -1
fn sys_set_priority(prio: isize) -> isize;

tips: 可以使用优先级队列比较方便的实现 stride 算法，但是我们的实验不考察效率，所以手写一个简单粗暴的也完全没问题。

我的实现

简述

spawn

​ 这里的spawn需要我们生成一个进程，并且将这个进程加入到队列中, 和fork不同的点在于它不会赋值父进程的空间，和exec不同的点在于它不会替换进程的执行流。这里实现的过程为在TaskControlBlock中新加入一个函数，它会直接根据path由elf生成一个地址空间，同时将这个进程加入到父进程下，在生成自己的trap上下文后，这个block会被加入到调度队列中。

stride调度

​ 这里需要为每一个control block添加两个新的成员stride和priority，前一个初始值为0，后一个为16。这里我们将Manager中的队列替换为BinaryHeap, 还要为TaskControlBlock实现Eq，PartialEq, Ord和PartialOrd，我们通过比较stride获取到关系。修改外fetch等方法后，每一次获取的都是stride最小的任务。最后我们在run_task中每一调度一个新的任务时，更新我们的stride值，注意这里不要把BIG_STRIDE设置太大，否则会溢出。

具体代码

impl TaskControlBlock {
	pub fn spawn(self: &Arc<Self>, elf_data: &[u8]) -> Arc<Self> {
        let mut parent_inner = self.inner_exclusive_access();
        let (memory_set, user_sp, entry_point) = MemorySet::from_elf(elf_data);
        let trap_cx_ppn = memory_set
            .translate(VirtAddr::from(TRAP_CONTEXT).into())
            .unwrap()
            .ppn();
        let pid_handle = pid_alloc();
        let kernel_stack = KernelStack::new(&pid_handle);
        let kernel_stack_top = kernel_stack.get_top();
        let task_control_block = Arc::new(TaskControlBlock {
            pid: pid_handle,
            kernel_stack,
            inner: unsafe {
                UPSafeCell::new(TaskControlBlockInner {
                    trap_cx_ppn,
                    base_size: user_sp,
                    task_cx: TaskContext::goto_trap_return(kernel_stack_top),
                    task_status: TaskStatus::Ready,
                    memory_set,
                    parent: Some(Arc::downgrade(self)),
                    children: Vec::new(),
                    exit_code: 0,
                    stride: 0,
                    priority: 16,
                })
            },
        });
        let trap_cx = task_control_block.inner_exclusive_access().get_trap_cx();
        *trap_cx = TrapContext::app_init_context(
            entry_point,
            user_sp,
            KERNEL_SPACE.exclusive_access().token(),
            kernel_stack_top,
            trap_handler as usize,
        );
        parent_inner.children.push(task_control_block.clone());
        task_control_block

    }
}

​ 这里依次解析elf文件，获取了pid和内核栈，创建控制块，设置trap上下文，最后返回这个控制块，这个控制块会被加入到队列中。

impl PartialEq for TaskControlBlock {
    fn eq(&self, other: &Self) -> bool {
        let self_control_block = self.inner_exclusive_access();
        let other_control_block = other.inner_exclusive_access();
        let self_stride = self_control_block.stride;
        let other_stride = other_control_block.stride;
        
        drop(self_control_block);
        drop(other_control_block);

        self_stride == other_stride
    }
}

impl Eq for TaskControlBlock {}

impl Ord for TaskControlBlock {
    fn cmp(&self, other: &Self) -> Ordering {
        let self_control_block = self.inner_exclusive_access();
        let other_control_block = other.inner_exclusive_access();
        let self_stride = self_control_block.stride;
        let other_stride = other_control_block.stride;
        drop(self_control_block);
        drop(other_control_block);
        other_stride.cmp(&self_stride)
    }
}

impl PartialOrd for TaskControlBlock {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

​ 这里会有一些繁琐，实际上可以直接将drop任务交给编译器。需要注意的是由于是大根堆，所以如果要最小值排在最前面，我们需要将比较对象的位置互换。

impl TaskManager {
    pub fn new() -> Self {
        Self {
            ready_queue: BinaryHeap::new(),
        }
    }
    pub fn add(&mut self, task: Arc<TaskControlBlock>) {
        self.ready_queue.push(task);
    }
    pub fn fetch(&mut self) -> Option<Arc<TaskControlBlock>> {
        self.ready_queue.pop()
    }
}

​ 同时可以看到，我们将数据结构替换了堆。