进程管理的核心数据结构¶
本节导读¶
为了更好实现进程管理，我们需要设计和调整内核中的一些数据结构，包括：
基于应用名的应用链接/加载器
进程标识符
PidHandle以及内核栈KernelStack任务控制块
TaskControlBlock任务管理器
TaskManager处理器管理结构
Processor
基于应用名的应用链接/加载器¶
在实现 exec 系统调用的时候，我们需要根据应用的名字而不仅仅是一个编号来获取应用的 ELF 格式数据。
因此，在链接器 os/build.rs 中，我们按顺序保存链接进来的每个应用的名字：
1 // os/build.rs
2
3 for i in 0..apps.len() {
4 writeln!(f, r#" .quad app_{}_start"#, i)?;
5 }
6 writeln!(f, r#" .quad app_{}_end"#, apps.len() - 1)?;
7
8 writeln!(f, r#"
9 .global _app_names
10_app_names:"#)?;
11 for app in apps.iter() {
12 writeln!(f, r#" .string "{}""#, app)?;
13 }
14
15 for (idx, app) in apps.iter().enumerate() {
16 ...
17 }
第 8~13 行，各个应用的名字通过 .string 伪指令放到数据段中，注意链接器会自动在每个字符串的结尾加入分隔符
\0 ，它们的位置由全局符号 _app_names 指出。
而在加载器 loader.rs 中，我们用一个全局可见的 只读 向量 APP_NAMES 来按照顺序将所有应用的名字保存在内存中：
// os/src/loader.rs
lazy_static! {
static ref APP_NAMES: Vec<&'static str> = {
let num_app = get_num_app();
extern "C" { fn _app_names(); }
let mut start = _app_names as usize as *const u8;
let mut v = Vec::new();
unsafe {
for _ in 0..num_app {
let mut end = start;
while end.read_volatile() != '\0' as u8 {
end = end.add(1);
}
let slice = core::slice::from_raw_parts(start, end as usize - start as usize);
let str = core::str::from_utf8(slice).unwrap();
v.push(str);
start = end.add(1);
}
}
v
};
}
使用 get_app_data_by_name 可以按照应用的名字来查找获得应用的 ELF 数据，而 list_apps
在内核初始化时被调用，它可以打印出所有可用应用的名字。
// os/src/loader.rs
pub fn get_app_data_by_name(name: &str) -> Option<&'static [u8]> {
let num_app = get_num_app();
(0..num_app)
.find(|&i| APP_NAMES[i] == name)
.map(|i| get_app_data(i))
}
pub fn list_apps() {
println!("/**** APPS ****");
for app in APP_NAMES.iter() {
println!("{}", app);
}
println!("**************/")
}
进程标识符和内核栈¶
进程标识符¶
同一时间存在的所有进程都有一个自己的进程标识符，它们是互不相同的整数。这里将其抽象为一个 PidHandle
类型，当它的生命周期结束后，对应的整数会被编译器自动回收：
// os/src/task/pid.rs
pub struct PidHandle(pub usize);
类似之前的物理页帧分配器 FrameAllocator ，我们实现一个同样使用简单栈式分配策略的进程标识符分配器
PidAllocator ，并将其全局实例化为 PID_ALLOCATOR ：
// os/src/task/pid.rs
struct PidAllocator {
current: usize,
recycled: Vec<usize>,
}
impl PidAllocator {
pub fn new() -> Self {
PidAllocator {
current: 0,
recycled: Vec::new(),
}
}
pub fn alloc(&mut self) -> PidHandle {
if let Some(pid) = self.recycled.pop() {
PidHandle(pid)
} else {
self.current += 1;
PidHandle(self.current - 1)
}
}
pub fn dealloc(&mut self, pid: usize) {
assert!(pid < self.current);
assert!(
self.recycled.iter().find(|ppid| **ppid == pid).is_none(),
"pid {} has been deallocated!", pid
);
self.recycled.push(pid);
}
}
lazy_static! {
static ref PID_ALLOCATOR: UPSafeCell<PidAllocator> =
unsafe { UPSafeCell::new(PidAllocator::new()) };
}
PidAllocator::alloc 将会分配出去一个将 usize 包装之后的 PidHandle 。
我们将其包装为一个全局分配进程标识符的接口 pid_alloc：
// os/src/task/pid.rs
pub fn pid_alloc() -> PidHandle {
PID_ALLOCATOR.exclusive_access().alloc()
}
同时我们也需要为 PidHandle 实现 Drop Trait 来允许编译器进行自动的资源回收：
// os/src/task/pid.rs
impl Drop for PidHandle {
fn drop(&mut self) {
//println!("drop pid {}", self.0);
PID_ALLOCATOR.exclusive_access().dealloc(self.0);
}
}
内核栈¶
从本章开始，我们将应用编号替换为进程标识符来决定每个进程内核栈在地址空间中的位置。
在内核栈 KernelStack 中保存着它所属进程的 PID ：
// os/src/task/pid.rs
pub struct KernelStack {
pid: usize,
}
它提供以下方法：
1// os/src/task/pid.rs
2
3/// Return (bottom, top) of a kernel stack in kernel space.
4pub fn kernel_stack_position(app_id: usize) -> (usize, usize) {
5 let top = TRAMPOLINE - app_id * (KERNEL_STACK_SIZE + PAGE_SIZE);
6 let bottom = top - KERNEL_STACK_SIZE;
7 (bottom, top)
8}
9
10impl KernelStack {
11 pub fn new(pid_handle: &PidHandle) -> Self {
12 let pid = pid_handle.0;
13 let (kernel_stack_bottom, kernel_stack_top) = kernel_stack_position(pid);
14 KERNEL_SPACE.exclusive_access().insert_framed_area(
15 kernel_stack_bottom.into(),
16 kernel_stack_top.into(),
17 MapPermission::R | MapPermission::W,
18 );
19 KernelStack {
20 pid: pid_handle.0,
21 }
22 }
23 pub fn push_on_top<T>(&self, value: T) -> *mut T where
24 T: Sized, {
25 let kernel_stack_top = self.get_top();
26 let ptr_mut = (kernel_stack_top - core::mem::size_of::<T>()) as *mut T;
27 unsafe { *ptr_mut = value; }
28 ptr_mut
29 }
30 pub fn get_top(&self) -> usize {
31 let (_, kernel_stack_top) = kernel_stack_position(self.pid);
32 kernel_stack_top
33 }
34}
第 11 行，
new方法可以从一个PidHandle，也就是一个已分配的进程标识符中对应生成一个内核栈KernelStack。 它调用了第 4 行声明的kernel_stack_position函数来根据进程标识符计算内核栈在内核地址空间中的位置， 随即在第 14 行将一个逻辑段插入内核地址空间KERNEL_SPACE中。第 25 行的
push_on_top方法可以将一个类型为T的变量压入内核栈顶并返回其裸指针， 这也是一个泛型函数。它在实现的时候用到了第 32 行的get_top方法来获取当前内核栈顶在内核地址空间中的地址。
内核栈 KernelStack 用到了 RAII 的思想，具体来说，实际保存它的物理页帧的生命周期被绑定到它下面，当
KernelStack 生命周期结束后，这些物理页帧也将会被编译器自动回收：
// os/src/task/pid.rs
impl Drop for KernelStack {
fn drop(&mut self) {
let (kernel_stack_bottom, _) = kernel_stack_position(self.pid);
let kernel_stack_bottom_va: VirtAddr = kernel_stack_bottom.into();
KERNEL_SPACE
.exclusive_access()
.remove_area_with_start_vpn(kernel_stack_bottom_va.into());
}
}
为 KernelStack 实现 Drop Trait，一旦它的生命周期结束，就将内核地址空间中对应的逻辑段删除，为此在 MemorySet
中新增了一个名为 remove_area_with_start_vpn 的方法，感兴趣的读者可以查阅。
进程控制块¶
在内核中，每个进程的执行状态、资源控制等元数据均保存在一个被称为 进程控制块 (PCB, Process Control Block) 的结构中，它是内核对进程进行管理的单位。在内核看来，它就等价于一个进程。
承接前面的章节，我们仅需对任务控制块 TaskControlBlock 进行若干改动，让它直接承担进程控制块的功能：
1// os/src/task/task.rs
2
3pub struct TaskControlBlock {
4 // immutable
5 pub pid: PidHandle,
6 pub kernel_stack: KernelStack,
7 // mutable
8 inner: UPSafeCell<TaskControlBlockInner>,
9}
10
11pub struct TaskControlBlockInner {
12 pub trap_cx_ppn: PhysPageNum,
13 pub base_size: usize,
14 pub task_cx: TaskContext,
15 pub task_status: TaskStatus,
16 pub memory_set: MemorySet,
17 pub parent: Option<Weak<TaskControlBlock>>,
18 pub children: Vec<Arc<TaskControlBlock>>,
19 pub exit_code: i32,
20}
任务控制块中包含两部分：
在初始化之后就不再变化的作为一个字段直接放在任务控制块中。这里将进程标识符
PidHandle和内核栈KernelStack放在其中；在运行过程中可能发生变化的则放在
TaskControlBlockInner中，将它再包裹上一层UPSafeCell<T>放在任务控制块中。 在此使用UPSafeCell<T>可以提供互斥从而避免数据竞争。
TaskControlBlockInner 中包含下面这些内容：
trap_cx_ppn指出了应用地址空间中的 Trap 上下文被放在的物理页帧的物理页号。base_size的含义是：应用数据仅有可能出现在应用地址空间低于base_size字节的区域中。借助它我们可以清楚的知道应用有多少数据驻留在内存中。task_cx保存任务上下文，用于任务切换。task_status维护当前进程的执行状态。memory_set表示应用地址空间。parent指向当前进程的父进程（如果存在的话）。注意我们使用Weak而非Arc来包裹另一个任务控制块，因此这个智能指针将不会影响父进程的引用计数。children则将当前进程的所有子进程的任务控制块以Arc智能指针的形式保存在一个向量中，这样才能够更方便的找到它们。当进程调用 exit 系统调用主动退出或者执行出错由内核终止的时候，它的退出码
exit_code会被内核保存在它的任务控制块中，并等待它的父进程通过 waitpid 回收它的资源的同时也收集它的 PID 以及退出码。
注意我们在维护父子进程关系的时候大量用到了智能指针 Arc/Weak ，当且仅当它的引用计数变为 0 的时候，进程控制块以及被绑定到它上面的各类资源才会被回收。
TaskControlBlockInner 提供的方法主要是对于它内部字段的快捷访问：
// os/src/task/task.rs
impl TaskControlBlockInner {
pub fn get_trap_cx(&self) -> &'static mut TrapContext {
self.trap_cx_ppn.get_mut()
}
pub fn get_user_token(&self) -> usize {
self.memory_set.token()
}
fn get_status(&self) -> TaskStatus {
self.task_status
}
pub fn is_zombie(&self) -> bool {
self.get_status() == TaskStatus::Zombie
}
}
而任务控制块 TaskControlBlock 目前提供以下方法：
// os/src/task/task.rs
impl TaskControlBlock {
pub fn inner_exclusive_access(&self) -> RefMut<'_, TaskControlBlockInner> {
self.inner.exclusive_access()
}
pub fn getpid(&self) -> usize {
self.pid.0
}
pub fn new(elf_data: &[u8]) -> Self {...}
pub fn exec(&self, elf_data: &[u8]) {...}
pub fn fork(self: &Arc<TaskControlBlock>) -> Arc<TaskControlBlock> {...}
}
inner_exclusive_access尝试获取互斥锁来得到TaskControlBlockInner的可变引用。getpid以usize的形式返回当前进程的进程标识符。new用来创建一个新的进程，目前仅用于内核中手动创建唯一一个初始进程initproc。exec用来实现exec系统调用，即当前进程加载并执行另一个 ELF 格式可执行文件。fork用来实现fork系统调用，即当前进程 fork 出来一个与之几乎相同的子进程。
new/exec/fork 的实现我们将在下一小节再介绍。
任务管理器¶
在前面的章节中，任务管理器 TaskManager 不仅负责管理所有的任务，还维护着 CPU 当前在执行哪个任务。
由于这种设计不够灵活，我们需要将任务管理器对于 CPU 的监控职能拆分到处理器管理结构 Processor 中去，
任务管理器自身仅负责管理所有任务。在这里，任务指的就是进程。
1// os/src/task/manager.rs
2
3pub struct TaskManager {
4 ready_queue: VecDeque<Arc<TaskControlBlock>>,
5}
6
7/// A simple FIFO scheduler.
8impl TaskManager {
9 pub fn new() -> Self {
10 Self {
11 ready_queue: VecDeque::new(),
12 }
13 }
14 pub fn add(&mut self, task: Arc<TaskControlBlock>) {
15 self.ready_queue.push_back(task);
16 }
17 pub fn fetch(&mut self) -> Option<Arc<TaskControlBlock>> {
18 self.ready_queue.pop_front()
19 }
20}
21
22lazy_static! {
23 pub static ref TASK_MANAGER: UPSafeCell<TaskManager> =
24 unsafe { UPSafeCell::new(TaskManager::new()) };
25}
26
27pub fn add_task(task: Arc<TaskControlBlock>) {
28 TASK_MANAGER.exclusive_access().add(task);
29}
30
31pub fn fetch_task() -> Option<Arc<TaskControlBlock>> {
32 TASK_MANAGER.exclusive_access().fetch()
33}
TaskManager 将所有的任务控制块用引用计数 Arc 智能指针包裹后放在一个双端队列 VecDeque 中。
使用智能指针的原因在于，任务控制块经常需要被放入/取出，如果直接移动任务控制块自身将会带来大量的数据拷贝开销，
而对于智能指针进行移动则没有多少开销。其次，允许任务控制块的共享引用在某些情况下能够让我们的实现更加方便。
TaskManager 提供 add/fetch 两个操作，前者表示将一个任务加入队尾，后者则表示从队头中取出一个任务来执行。
从调度算法来看，这里用到的就是最简单的 RR 算法。全局实例 TASK_MANAGER 则提供给内核的其他子模块 add_task/fetch_task 两个函数。
处理器管理结构¶
处理器管理结构 Processor 负责维护从任务管理器 TaskManager 分离出去的那部分 CPU 状态：
// os/src/task/processor.rs
pub struct Processor {
current: Option<Arc<TaskControlBlock>>,
idle_task_cx: TaskContext,
}
包括：
current表示在当前处理器上正在执行的任务；idle_task_cx_ptr表示当前处理器上的 idle 控制流的任务上下文的地址。
在单核环境下，我们仅创建单个 Processor 的全局实例 PROCESSOR ：
// os/src/task/processor.rs
lazy_static! {
pub static ref PROCESSOR: UPSafeCell<Processor> = unsafe { UPSafeCell::new(Processor::new()) };
}
正在执行的任务¶
1// os/src/task/processor.rs
2
3impl Processor {
4 pub fn take_current(&mut self) -> Option<Arc<TaskControlBlock>> {
5 self.current.take()
6 }
7 pub fn current(&self) -> Option<Arc<TaskControlBlock>> {
8 self.current.as_ref().map(|task| Arc::clone(task))
9 }
10}
11
12pub fn take_current_task() -> Option<Arc<TaskControlBlock>> {
13 PROCESSOR.take_current()
14}
15
16pub fn current_task() -> Option<Arc<TaskControlBlock>> {
17 PROCESSOR.current()
18}
19
20pub fn current_user_token() -> usize {
21 let task = current_task().unwrap();
22 let token = task.inner_exclusive_access().get_user_token();
23 token
24}
25
26pub fn current_trap_cx() -> &'static mut TrapContext {
27 current_task()
28 .unwrap()
29 .inner_exclusive_access()
30 .get_trap_cx()
31}
第 4 行的
Processor::take_current可以取出当前正在执行的任务。Option::take意味着current字段也变为None。第 7 行的
Processor::current返回当前执行的任务的一份拷贝。。current_user_token和current_trap_cx基于current_task实现，提供当前正在执行的任务的更多信息。
任务调度的 idle 控制流¶
每个 Processor 都有一个 idle 控制流，它们运行在每个核各自的启动栈上，功能是尝试从任务管理器中选出一个任务来在当前核上执行。
在内核初始化完毕之后，核通过调用 run_tasks 函数来进入 idle 控制流：
1// os/src/task/processor.rs
2
3impl Processor {
4 fn get_idle_task_cx_ptr(&mut self) -> *mut TaskContext {
5 &mut self.idle_task_cx as *mut _
6 }
7}
8
9pub fn run_tasks() {
10 loop {
11 let mut processor = PROCESSOR.exclusive_access();
12 if let Some(task) = fetch_task() {
13 let idle_task_cx_ptr = processor.get_idle_task_cx_ptr();
14 // access coming task TCB exclusively
15 let mut task_inner = task.inner_exclusive_access();
16 let next_task_cx_ptr = &task_inner.task_cx as *const TaskContext;
17 task_inner.task_status = TaskStatus::Running;
18 drop(task_inner);
19 // release coming task TCB manually
20 processor.current = Some(task);
21 // release processor manually
22 drop(processor);
23 unsafe {
24 __switch(idle_task_cx_ptr, next_task_cx_ptr);
25 }
26 }
27 }
28}
调度功能的主体在 run_tasks 中实现。它循环调用 fetch_task 直到顺利从任务管理器中取出一个任务，然后获得
__switch 两个参数进行任务切换。注意在整个过程中要严格控制临界区。
当一个应用交出 CPU 使用权时，进入内核后它会调用 schedule 函数来切换到 idle 控制流并开启新一轮的任务调度。
// os/src/task/processor.rs
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);
}
}
切换回去之后，我们将跳转到 Processor::run 中 __switch 返回之后的位置，也即开启了下一轮循环。