logo一只豆腐
  • HangX-Ma
  • Jul 07, 2023
  • Total 12579 words
  • About 35 mins
  • 0 views

rCore OS Note - Chapter 5

第五章：进程， 阅读 rCore tutorial book v3 的笔记以及实践部分的实现与记录。

Process OS 强化了以往用以调度应用的 task 的概念， 在这一层抽象的基础上发展出 process， 弱化了 CPU 与任务之间的耦合关系， 所以单从操作系统结构的角度分析其实并没有太大的变化。

Process OS details, rCore
Process OS Details, rCore

0. 资料汇总

1. 进程概念

进程 就是操作系统选取某个可执行文件并对其进行一次动态执行的过程， 对于可执行文件中给出的需求能相应对 硬件/虚拟资源 进行 动态绑定和解绑。 进程的引入让开发者能够控制程序的运行， 操作系统能够面向用户进行交互。 rCore 增添了操作系统中最为关键的几个系统调用： sys_fork， sys_waitpid， sys_exec， 以及 sys_read。 同样的， 通过引入 buddy_system_allocator 提供动态内存分配支持， 结合这些系统调用， 在用户态 rCore 提供了一个用户初始程序 initproc， 这让 rCore 具备了与应用层的交互能力， 但其背后则需依托 rCore 的进程管理。

2. 进程管理的组成结构

rCore 为增添了 struct PidHandle 作为每个进程的标识， 其实现与上一章的 Physical Frame 非常类似。 另外 rCore 改造了 build.rs 和 loader.rs 以使 rCore 能够支持应用名而非 task id 加载应用。

// os/src/task/pid.rs
pub struct PidHandle(pub usize);

2.1 应用的内核栈

由于引入了进程标识 PID， 之前用 task id 进行应用区分的方式需要用 PID 替代， 所有应用的内核栈的创建就与以往有所不同。 rCore 从 TaskControlBlock 中分离了 KernelStack 用以初始化与管理每个应用的内核栈。

// os/src/task/pid.rs
pub struct KernelStack {
    pid: usize,
}

2.2 进程控制块

在内核中，每个进程的执行状态、资源控制等元数据均保存在一个被称为 进程控制块 (PCB, Process Control Block) 的结构中，它是内核对进程进行管理的单位。 对于 rCore 而言， PCB 其实是对原来的 TCB 的扩展， 并区分 immutable 与 mutable 两类数据 （ Inner 块使用 UPSafeCell<T> 管理可变数据）。 第五章新增的是 parent， children， 以及 exit_code 这几个可变量， 使用 Weak 智能指针能确保不影响父进程的引用计数， 而 Arc 则提供了对子进程的引用计数， 这两者的配合可以保证父子进程的双向关系以及控制子进程的资源回收了。

// os/src/task/task.rs
pub struct TaskControlBlock {
    // immutable
    pub pid: PidHandle,
    pub kernel_stack: KernelStack,
    // mutable
    inner: UPSafeCell<TaskControlBlockInner>,
}

pub struct TaskControlBlockInner {
    ...
    pub parent: Option<Weak<TaskControlBlock>>,
    pub children: Vec<Arc<TaskControlBlock>>,
    pub exit_code: i32,
}

另外我认为解决了上一章痛点问题的是关于任务控制模块的访问方式， rCore 的第五章提供了 inner_exclusive_access 方法， 此前我也尝试过类似的返回引用的方式避免直接拷贝一整个 TaskControlBlock 以避免巨大的开销， 但当时没有考虑到可以在外层包裹一层 UPSafeCell<T>。 另外相应的， 增加了外增 Wrapper 以及 PID 后， 原来的 任务控制块创建 也要转变为 进程控制块创建， 其实主要差异就是 Kernel Stack 的创建以及新增的变量的初始化。

// os/src/task/task.rs
impl TaskControlBlock {
    pub fn inner_exclusive_access(&self) -> RefMut<'_, TaskControlBlockInner> {
        self.inner.exclusive_access()
    }
    ...
}

除此之外就是在 TaskControlBlock 中实现几个关键的系统调用了。

需要一提的是， 由于增添了 wrapper， os/src/task/mod.rs 中的代码对 TaskControlBlockInner 中数据访问发生了变化， 这一块需要大改。

2.3 进程管理器

任务管理器 或称 进程管理器 TaskManager 将 CPU 的监控职能拆分到处理器管理结构 Processor 中， 其自身仅负责管理所有进程， 这种分离有助于后续实现多核环境的拓展。 这里比较关键的设计是将 TaskControlBlock 用 Arc 智能指针管理， 并将其存储在堆上， 不仅减少开销也方便维护。

// os/src/task/manager.rs
pub struct TaskManager {
    ready_queue: VecDeque<Arc<TaskControlBlock>>,
}

2.4 CPU 管理器

处理器管理结构 Processor 负责维护 CPU 相关的状态。 其中 current 表示当前处理器上执行的进程任务， 而 idle_task_cx 则是 idle 控制流的任务上下文。 这个 idle 控制流运行在 CPU 启动栈上， 它会从 TaskManager 中选择一个进程任务放在当前的 CPU 核上运行。

// os/src/task/processor.rs
pub struct Processor {
    current: Option<Arc<TaskControlBlock>>,
    idle_task_cx: TaskContext,
}

idle 控制流的设计目的在于分离进程调度与 Trap， 换入/换出进程仅需要调用 schedule 函数， 通过 __switch 保存自身进程的上下文， 之后程序流会换回 idle_task_cx_ptr 中的内容重新回到 run_tasks 的 loop 循环中查找下一个待运行的进程。 这点设计和 xv6 如出一辙， 在 rCore 中则是会持续运行 run_tasks 用以进程的调度。 引用我自己在 rCore 留言板上的 回答 能帮助理解它的作用：

idle 控制流的设计和 xv6 的很像， rCore 让 run_tasks 始终保持运行， 可以把这个函数想象成一个游戏机，它的作用就是不断挑选可运行的游戏卡（进程）， 然后放到 CPU 这个卡槽中。 一定时间后这个 CPU 卡槽要给别的游戏卡（进程）用了就把这个当前的卡弹出来（这里就用了 schedule 函数弹出）， 然后游戏机又开始选下一张能用的游戏卡（进程）了。

游戏卡（进程）只知道自己被插上要运行， 以及到某个点自己要弹出来， 它不知道游戏机的存在， 这样就做到了任务调度的透明。

// os/src/task/processor.rs
pub fn run_tasks() {
    loop {
        let mut processor = PROCESSOR.exclusive_access();
        if let Some(task) = fetch_task() {
            let idle_task_cx_ptr = processor.get_idle_task_cx_ptr();
            // access coming task TCB exclusively
            let mut task_inner = task.inner_exclusive_access();
            let next_task_cx_ptr = &task_inner.task_cx as *const TaskContext;
            task_inner.task_status = TaskStatus::Running;
            // stop exclusively accessing coming task TCB manually
            drop(task_inner);
            processor.current = Some(task);
            // stop exclusively accessing processor manually
            drop(processor);
            unsafe {
                __switch(
                    idle_task_cx_ptr,
                    next_task_cx_ptr,
                );
            }
        }
    }
}

pub fn schedule(switched_task_cx_ptr: *mut TaskContext) {
    let mut processor = PROCESSOR.exclusive_access();
    let idle_task_cx_ptr = processor.get_idle_task_cx_ptr();
    drop(processor);
    unsafe {
        __switch(
            switched_task_cx_ptr,
            idle_task_cx_ptr,
        );
    }
}

3. 进程管理的实现机制

3.1 初始进程创建

可以先看一下 rCore 在第五章的 main.rs 做的事情， 可以看到在内存管理模块初始化完成后， 会调用 task 子模块提供的 add_initproc 将初始进程 ch5b_initproc 加入进程任务管理器。 因而在 task 子模块中需要初始化进程控制块 INITPROC。 另外， TaskControlBlock::new 相较之前有所变更。

// os/src/main.rs
#[no_mangle] // avoid compiler confusion
fn rust_main() {
    clear_bss();
    kernel_log_info();

    println!("[kernel] Hello, world!");
    mm::init();
    println!("[kernel] back to world!");
    // mm tests
    mm::heap_test();
    mm::frame_allocator_test();
    mm::remap_test();

    task::add_initproc();
    println!("after initproc!");

    trap::init();
    trap::enable_timer_interrupt();
    timer::set_next_trigger();
    loader::list_apps();
    task::run_tasks();
    panic!("Unreachable in rust_main!");
}

3.2 进程调度机制

进程调度一方面是 CPU 分给当前进程的时间片用尽触发 SupervisorTimer 中断需要调度， 另一方面是进程主动让出 CPU 的占用权， 都需要用到 suspend_current_and_run_next 这个函数。 在引入进程的抽象之后， 调度不需要进程本身更新关于 __switch 函数相关的内容， 只需要获取当前进程的控制块 TCB 并将其加入 task 队列中后使用 schedule 即可。 这也是前述引入 idle 控制流的好处之一， 对进程调度的解耦让整个代码流都干净了很多。

3.3 进程的生成机制

这块相较而言就会显得复杂一些， 在内核中唯一的初始化进程是 initproc， 后续的进程都需要通过 fork/exec 这两个系统调用提供的进程生成机制实现。

  • fork

    fork 需要对除了返回值外的父进程所有信息的完全复制， 这甚至要求地址空间的映射方式， 映射页的权限， 映射范围， 以及数据都需要与父进程一致， 不同的是最终映射到的具体的物理地址页 PPN。 在 rCore 中管理这部分信息的是 memory_set.rs， 为了复制这些信息新增了 from_another 函数拷贝一个 逻辑段 的上述数据。

      // os/src/mm/memory_set.rs
  impl MapArea {
      pub fn from_another(another: &MapArea) -> Self {...}
      ...
  }

    这之后真正对整个地址空间进行完全复制的是， MemorySet 中新增的 from_existed_user 函数。 该函数将生成一个新的 tranmpoline 并遍历当前用户态虚拟地址空间中所有的逻辑段并拷贝这些数据到目标地址空间。

      // os/src/mm/memory_set.rs
  impl MemorySet {
      pub fn from_existed_user(user_space: &MemorySet) -> MemorySet {...}
      ...
  }

    可以看到 TaskControlBlock::fork 的代码和 new 基本一致， 只是它的数据来源于它的父进程， 子进程的地址空间通过 MemorySet::from_existed_user 建立。 另外， sys_fork 的实现中需要更改 TrapContext 中的 a0 寄存器， trap_handler 部分需要配合做出微调， 以保证能够通过返回值区分子进程和父进程。

  • exec

    exec 系统调用是载入一个新的 ELF 的代码和数据替换当前进程的应用地址空间中的内容并执行。 它要做的事情其实和 TaskControlBlock::new 也很像， 但我们不需要重新生成进程的 PID 以及分配新的 KernelStack， 这些信息原有的进程已经提供了， 仅需要将我们所需要的 memory_set， user_sp， entry_point 这些信息进行更新即可， 之后我们仅需要完善 sys_exec 系统调用的实现。

    最为关键的还是 translated_str 这个函数， sys_exec 需要对输入的 path 参数进行解析， 这个 path 的内容来自应用的虚拟地址空间。 因而 translated_str 就需要在该应用空间中通过查找 Page Table 的方式逐个拷贝字符串信息到当前 kernel 中的 string 变量中。

      // os/src/mm/page_table.rs
  pub fn translated_str(token: usize, ptr: *const u8) -> String {
      let page_table = PageTable::from_token(token);
      let mut string = String::new();
      let mut va = ptr as usize;
      loop {
          let ch: u8 = *(page_table
              .translate_va(VirtAddr::from(va))
              .unwrap()
              .get_mut());
          if ch == 0 {
              break;
          } else {
              string.push(ch as char);
              va += 1;
          }
      }
      string
  }

    在 kernel 中获取到了这个应用信息后就能通过 loader.rs 提供的 get_app_data_by_name 在指定的内存地址空间加载应用了。

  • read

    最后的 sys_read 实现还没有涉及到文件系统， 因而需要调用 SBI 提供的接口以获取用户的键盘输入。

3.4 进程资源回收机制

资源回收涉及到进程的退出， 在此之前 task 中实现此功能的是 exit_current_and_run_next 函数， 但相比之前的章节， ch5 需要该函数传入一个退出码， 这个退出码会写入到当前进程的进程控制块 TCB 中。 这里比较关键的一步操作是将当前进程的所有子进程的父进程更改为 INITPROC， 这样当前进程被回收后其子进程仍能被管理而不至于进入一种无法定义的状态。

// os/src/task/mod.rs
pub fn exit_current_and_run_next(exit_code: i32) {
    ...
    // ++++++ access initproc TCB exclusively
    {
        let mut initproc_inner = INITPROC.inner_exclusive_access();
        for child in inner.children.iter() {
            child.inner_exclusive_access().parent = Some(Arc::downgrade(&INITPROC));
            initproc_inner.children.push(child.clone());
        }
    }
    // ++++++ stop exclusively accessing parent PCB
    ...
}

父进程的资源回收操作详见 sys_waitpid 系统调用。

4. 修复 syscall

4.1 sys_task_info

该系统调用主要是这几个 get_* 函数需要对应新的 TaskControlBlockInner 的获取方式， 关键需要注意要用 current_task 获取当前的进程的 TCB 以免获取进程信息时所有权转移。

// os/src/syscall/process.rs
pub fn sys_task_info(ti: *mut TaskInfo) -> isize {
    ...
    let ref task_info = TaskInfo {
        status: get_current_task_status(),
        syscall_times: get_current_task_syscall_times(),
        time: get_current_task_time_cost(),
    };
    ...
}

另外， 记录内核态和用户态的进程开销需要用到一个 checkpoint 记录时刻点， 这个变量也要放入 TaskControlBlockInner， 通过 update_checkpoint 函数更新时刻点并获取时间变化量。 不过在 TaskControlBlock::fork 函数中的初始化和 TaskControlBlock::new 有所不同， 前者需要将 checkpoint 的值通过 get_time_ms 更新为进程创建的时刻点， 否则新的子进程的计时仍会以 OS 运行的第一个程序为起始时刻点， 这样我们无法通过 ch3_taskinfo.rs 时间相关的测试。

// os/src/task/task.rs
pub struct TaskControlBlockInner {
    pub user_time: usize,
    pub kernel_time: usize,
    checkpoint: usize, // record time point
    ...
}

impl TaskControlBlockInner {
    ...
    /// update checkpoint and return the diff time
    pub fn update_checkpoint(&mut self) -> usize {
        let prev_point = self.checkpoint;
        self.checkpoint = get_time_ms();
        return self.checkpoint - prev_point;
    }
}

对 ch3_taskinfo.rs 修改就是将其放入了子进程， 不做这个更改应该也不影响最终的结果。 另外 user_time_start 和 user_time_end 这一对记录用户态时间开销的函数接口和位置都没有变， update_task_syscall_times 亦是如此。 更新内核时间开销同样只用在 exit_current_and_run_next 以及 suspend_current_and_run_next 这两个临界态函数中调用 update_checkpoint 更新即可。

具体实现可参考 commit#e887b13

4.2 sys_mmap 与 sys_munmap

这个比较简单， 只用根据 TaskControlBlock 变更后对 TaskControlBlockInner 的获取方式修改 get_current_task_page_table， create_new_map_area， unmap_consecutive_area 即可。

具体实现可参考 commit#d8e4b55

5. 课后练习

5.1 编程练习

  • TODO: 这部分回头再说

5.2 实验练习

实现 spawn 系统调用

这部分实验要求使用 fork 和 exec， 但是可以借鉴这二者的写法， path 部分获取就是模仿 exec 写的。 实现该系统调用的主要想法是给新的应用数据 elf_data 建立一个新的进程模块， 这意味着我们需要以 exec 的角度去改编 fork。 一直到 TrapContext 这部分， 前面的内容和 fork 基本一致， 但是我们需要运行一个新的应用， 因而不能像 fork 那样沿用与其父进程一致的配置， 而需要创建一个全新的 TrapContext 以容纳 entry_point， user_sp， kernel_stack_top 这几个依托当前应用数据生成的信息。 最后也是最关键的， 我们需要返回子进程的 pid， 并且将这个子进程的进程控制模块加入到 task 队列中， 以使得操作系统能够分配资源执行该应用。

/// HINT: fork + exec =/= spawn
/// ALERT: Don't fork parent process address space
pub fn sys_spawn(path: *const u8) -> isize {
    let task = current_task().unwrap();
    let mut parent_inner = task.inner_exclusive_access();
    let token = parent_inner.memory_set.token();
    let path = translated_str(token, path);
    if let Some(elf_data) = get_app_data_by_name(path.as_str()) {
        let (memory_set, user_sp, entry_point) = MemorySet::from_elf(elf_data);
        let trap_cx_ppn = memory_set
            .translate(VirtAddr::from(TRAP_CONTEXT_BASE).into())
            .unwrap()
            .ppn();
        // alloc a pid and a kernel stack in kernel space
        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 {
                    task_status: TaskStatus::Ready,
                    task_cx: TaskContext::goto_trap_return(kernel_stack_top),
                    syscall_times: [0; MAX_SYSCALL_NUM],
                    user_time: 0,
                    kernel_time: 0,
                    checkpoint: get_time_ms(), // give the new process a new start point
                    memory_set,
                    trap_cx_ppn,
                    base_size: parent_inner.base_size,
                    heap_bottom: parent_inner.heap_bottom,
                    program_brk: parent_inner.program_brk,
                    parent: Some(Arc::downgrade(&task)),
                    children: Vec::new(),
                    exit_code: 0,
                })
            },
        });
        // add child
        parent_inner.children.push(task_control_block.clone());
        // prepare TrapContext in user space
        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,
        );
        let pid = task_control_block.pid.0 as isize;
        add_task(task_control_block);
        pid
    } else {
        -1
    }
}

具体实现可参考 commit#74015ec

stride 调度算法

stride 调度需要存储两个变量， 一个是 stride， 表示当前的进程已经运行的 “长度”， 这个长度是以 pass 为单位进行更新的。 那么第二个变量就是 priority， 表示调度的优先级， 于是有公式成立：

\[pass = BIG\_STRIDE/priority\]

其中 BIG_STRIDE 被定义为一个预定义的极大常数， 则该调度方案为每个进程分配的时间将与其优先级成正比。 实验中对这些变量还有以下的规约：

  • stride 调度要求进程优先级 \(\ge{2}\) ，所以设定进程优先级 \(\le{1}\) 会导致错误。
  • 进程初始 stride 设置为 0。
  • 进程初始优先级设置为 16。

由于 priority \(\ge\) 2， 因而 pass \(\le\) BIG_STRIDE/2， 在不考虑溢出的情况下， STRIDE_MAX – STRIDE_MIN ≤ BigStride / 2， 始终成立， 这一点用反证法可以证明。 但现实中必然需要考虑溢出， 那么这里可以利用符号整数的特性， 避免在溢出后某些本应延后调度的进程因为 stride 值溢出后从小值开始的缘故被优先调度。 所以， 可以将 BIG_STRIDE 设置为 u64 类型最大值， 结合 STRIDE_MAX – STRIDE_MIN ≤ BigStride / 2 亦会有 STRIDE_MIN – STRIDE_STRIDE >= -BigStride / 2， 这个与 i64 的表示方式非常相似， 因而可以这样设计 stride 的比较方式：

use core::cmp::Ordering;

struct Stride(u64);

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

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

我自己尝试了去实现 BinaryHeap 进行调度， 但是程序会卡死在 initproc 中， 作为一个 Rust 新手以及确实很久没接触算法了， 不知道什么地方除了问题， 于是就用了最简单的思路， 在每次 fetch 下一个 task 之前对这个队列中的 task 做检查， 找到最小的 stride。 这里每次将初始最小值设定为 0x7FFF_FFFF 是为了解决前述的溢出问题， 本质上利用有符号整数的思想就是把大于 MAX/2 等价为负数。 这样 TIPs 中说明的 使用 8 bits 存储 stride, BIG_STRIDE = 255, 则: (125 < 255) == false, (129 < 255) == true 就好理解了。

// os/src/task/manager.rs
/// A simple FIFO scheduler.
impl TaskManager {
    ...
    /// Take a process out of the ready queue
    pub fn fetch(&mut self) -> Option<Arc<TaskControlBlock>> {
        let mut min_index = 0;
        let mut min_stride = 0x7FFF_FFFF;
        for (idx, task) in self.ready_queue.iter().enumerate() {
            let inner = task.inner.exclusive_access();
            if inner.get_status() == TaskStatus::Ready {
                if inner.stride < min_stride {
                    min_stride = inner.stride;
                    min_index = idx;
                }
            }
        }

        if let Some(task) = self.ready_queue.get(min_index) {
            let mut inner = task.inner.exclusive_access();
            inner.stride += BIG_STRIDE / inner.priority;
        }
        self.ready_queue.remove(min_index)
    }
}

具体实现可参考 commit#5abe01a

Search