引言

NUDT-OS是由国防科技大学操作系统教学团队带领开发的、从零实现的面向X86架构的实验性操作系统,使用Rust开发。NUDT-OS的设计目标是从类UNIX系统出发,吸收学习微内核的设计原则和优点,设计实现一种新型的混合内核架构,以实现系统安全可靠与性能的平衡。同时,探索无栈异步协程等新型技术在OS中的应用。

NUDT-OS采用了一种融合宏内核与微内核特点和优点的融合内核架构。(将在 内核架构中详细说明)。在内核模块中,具有任务管理、内存管理、文件系统、异步管理等模块。支持管道、命令行参数、重定向;支持信号量、互斥锁。下面的表格简要概述了各个模块的功能和特点。

NUDT-OS借助Rust的协程处理机制,采用多对一线程模型,一个协程执行器内核线程服务多个用户线程。类似宏内核,每个进程拥有独立的虚拟地址空间,但借鉴了微内核思想,将一些关键的内核服务运行于内核服务线程,各个内核服务线程保持相对独立,单个内核服务线程崩溃时,系统整体不会崩溃。

项目主要借鉴参考了下面的开源项目:

模块功能和特点
任务管理具有进程、内核线程、用户线程三种对象
内核统一调度内核线程和用户线程
采用多对一线程模型,一个协程执行器内核线程服务多个用户线程
支持互斥锁、信号量
内存管理每个进程有独立的地址空间
切换进程时切换地址空间
文件系统一个简易的文件系统
一切皆文件,将多种对象都抽象为文件
实现管道,命令行参数,重定向
异步管理实现异步系统调用
利用协程实现多对一线程模型

内核文件结构说明:

kernel/src
├── drivers                     // 设备驱动
│   ├── ahci.rs                 
│   ├── mod.rs
│   └── pci.rs
├── fs                          // 虚拟文件系统抽象
│   ├── inode.rs                // 虚拟文件系统的inode
│   ├── mod.rs
│   ├── pipe.rs                 // 管道
│   └── stdio.rs                // 标准输入输出
├── future                      // 协程处理模块
│   ├── executor.rs             // 协程执行器
│   ├── futures                 // 定义各类协程任务
│   └── mod.rs                  
├── ipc                         // 进程间通信的结构
│   └── mod.rs
├── kthread                     // 内核线程执行的任务或服务
│   ├── executor.rs             // 协程执行器线程的任务函数
│   └── mod.rs
├── lib.rs                      
├── linker.ld                   // 内核编译链接脚本
├── main.rs                     // 内核入口
├── mm                          // 内存管理模块
│   ├── frame_allocator.rs      // 内存帧分配器
│   ├── heap_allocator.rs       // 内存堆分配器
│   ├── memory_set.rs           // 虚拟地址空间抽象
│   ├── mod.rs
│   └── page_table.rs           // 页表抽象
├── sync                        // 互斥同步模块
│   ├── mod.rs  
│   ├── mutex.rs                // 互斥锁
│   └── sem.rs                  // 信号量
├── syscall                     // 系统调用模块
│   ├── fs.rs                   // 文件相关系统调用
│   ├── mod.rs          
│   ├── sync.rs                 // 同步互斥相关系统调用
│   ├── task.rs                 // 任务管理相关系统调用
│   ├── uaccess.S               // 用户和内核数据交换
│   └── uaccess.rs              // 用户和内核数据交换
├── task                        // 任务管理模块
│   ├── kthread.rs              // 内核线程
│   ├── manager.rs              // 用户线程管理器
│   ├── mod.rs                  
│   ├── process.rs              // 进程
│   ├── scheduler.rs            // 内核统一调度器
│   ├── sleep.rs                // 实现阻塞睡眠
│   ├── switch.S                // 线程切换
│   └── thread.rs               // 用户线程
├── trap                        // 中断处理模块
│   ├── handler.rs              // 中断处理函数
│   ├── mod.rs          
│   ├── trap.S                  // 中断入口
│   └── vector.S                // 中断向量
└── utils                       // 辅助工具
    ├── console.rs              // 实现串口输入输出
    ├── mod.rs      
    ├── my_x86_64.rs            // 一些体系结构相关操作
    └── pic.rs                  // 中断初始化

内核架构

本章首先简要介绍传统操作系统宏内核和微内核架构的设计理念和优劣,再介绍NUDT-OS的内核架构设计。

一、传统宏内核架构

以Linux为代表的宏内核架构将所有功能模块(文件系统、网络栈、设备驱动等)都集成在内核态中运行。宏内核的优势在于其性能极好,软硬件生态丰富。但缺点也十分明显:一是可靠性问题,由于用户服务与内核服务都运行在内核态中,且内核各个组建的高度耦合性,任何一个模块的缺陷都可能导致整个系统的崩溃;二是内核的可维护性和可拓展性差,这同样是源于内核模块的高度耦合。

二、传统微内核架构

以Minix、seL4、Zircon等为代表的微内核架构则采用与宏内核完全不同的设计原则,将内核中的各个功能模块尽可能从内核中剥离,并作为独立的服务进程运行在用户态。相比于宏内核,微内核更小,高度模块化,具有更高的可靠性与安全性,单一模块的缺陷无法传播至其他模块,但缺点同样显著:内核外组件间的基于进程间通信的交互方式显著会影响系统性能。

三、混合内核架构

以Windows NT、macOS\IOS、鸿蒙系统为代表的混合内核融合多种内核特性。试图寻找系统性能与安全可靠性之间的折衷。 Windows NT融合了宏内核的性能、生态优势,以及微内核的可靠性优势,将部分与性能、安全相关的功能模块下沉到内核中,以内核线程的形式解决性能问题; macOS因兼容性问题保留了微内核,但为了提高系统性能增加宏内核,用户可通过不同的系统调用决定使用哪个内核; 鸿蒙为适配不同硬件平台特性,支持在不同硬件平台选择不同内核。

四、NUDT-OS内核架构

NUDT-OS旨在从类UNIX宏内核出发,吸收学习微内核设计思想,以追求系统性能与可靠安全之间的平衡。

  • 针对传统宏内核的安全性问题,NUDT-OS将非核心的系统服务放在相互独立的内核线程中运行以增强系统安全可靠性,所有内核线程共享地址空间,由Rust语言特性保证线程间的访存隔离性。

  • 针对微内核频繁IPC导致的性能问题,NUDT-OS的内核线程共享地址空间,不同线程间可以直接通信,避免了IPC开销。

总体内核架构图如下:

内核架构图

如上图所示,NUDT-OS中存在多个用户线程和多个内核线程,内核主线程负责处理系统调用和分发用户线程的请求,内核中存在多个内核服务线程为用户提供文件系统、设备驱动等服务,另外还存在一个内核协程执行线程。利用Rust无栈异步协程机制,NUDT-OS采用多对一线程服务模型,由内核协程执行线程来统一调度用户请求,具体来说,用户线程通过系统调用申请内核服务线程的服务,内核主线程负责处理用户线程的系统调用和分发请求,每收到一个请求,内核主线程就向内核协程执行线程添加一个等待协程,并向内核服务线程请求服务,当内核服务线程完成服务时,唤醒协程执行线程中的协程。

任务管理

本章介绍NUDT-OS的任务管理模块。

一、用户线程、内核线程、进程的关系

NUDT-OS中共有三种任务相关的数据结构:

  • 用户线程:一个用户进程中可能包含多个用户线程,每个用户线程共享进程的地址空间,有自己的独立的栈和线程函数

  • 内核线程:内核中有多个内核线程,包括内核服务线程、内核主线程和协程执行线程

  • 进程:用户态的每个进程拥有独立的地址空间和资源,每个进程加载一个elf文件执行,可以在进程中创建多个用户线程;内核态只有一个root进程,其只包含一个主线程,无限循环回收僵死进程

进程是内核资源分配的最小单位,每个进程拥有独立的地址空间和资源。线程是内核调度的最小单位,内核统一调度用户线程和内核线程(具体策略是有内核服务线程有未完成的服务时,优先执行内核服务线程,无需服务时才调度用户线程)。

二、进程相关系统调用

pub fn sys_fork() -> isize

复制当前线程所在进程,父进程返回子进程的pid,而子进程返回0

pub fn sys_exec(path: *const u8, args: *const *const u8) -> isize

当前线程所在进程入口设置为elf文件入口

pub fn sys_waitpid(pid: isize, exit_code_p: *mut u32) -> isize

回收子进程

三、用户线程相关的系统调用

pub fn sys_exit(exit_code: i32) -> !

当前线程主动退出

pub fn sys_yield() -> isize

当前线程主动放弃CPU

pub fn sys_getpid() -> isize

获取当前线程所在进程的pid

pub fn sys_waitpid(pid: isize, exit_code_p: *mut u32) -> isize

等待一个线程结束(同一进程中的主线程使用)

pub fn sys_thread_create(entry: usize, arg: usize)

创建一个线程,返回线程tid

四、内核线程相关系统调用

pub fn sys_kthread_req(kthread: Arc<Kthread>, ctrl_ptr: usize, buf_ptr: usize) -> isize

向内核线程发送请求

进程管理

进程是OS资源分配的最小单位,NUDT-OS中使用Process结构体表示进程。每个用户进程拥有独立的地址空间,进程拥有的资源包括:文件、互斥锁、信号量。

一、数据结构

// kernel/src/task/process.rs
pub struct Process {
    /// 进程id
    pub pid: usize,
    /// 此进程已退出但还没被回收
    pub zombie: bool,
    /// 退出码
    pub exit_code: i32,
    /// 进程地址空间
    pub vm: Option<MemorySet>,
    /// 父进程
    pub parent: Option<ProcPtr>,
    /// 子进程队列
    pub children: Vec<ProcPtr>,
    /// 线程队列
    pub threads: Vec<Box<Thread>>,
    /// 打开的文件表
    pub files: Vec<Option<Rc<dyn File>>>,
    /// 持有的互斥锁
    pub mutexes: Vec<Box<dyn Mutex>>,
    /// 持有的信号量
    pub sems: Vec<Sem>,
}

由于目前内核尚不支持多核,任意时刻只有单线程运行,故未添加Arc或Mutex处理,后续将会进行改进。

这里并没有为进程区分自己的状态,这是因为进程的状态是由其包含的线程状态决定的。只要进程中有运行的线程,则进程就应该处于运行态,在Process结构体中,我们只需要添加一个zombie标志,当线程中的主线程(0号线程)退出时,进程的zombie标志置为true,表示进程已退出但还未被回收,而父进程使用waitpid方法时,若子进程的zombie标记为true,则回收进程资源。

二、关键方法

下面给出进程的重要方法:即fork、exec、waitpid三个经典的方法,将他们结合使用就可以实现多进程例如用户态的shell程序。

2.1 fork()

// impl Process
/// 复制当前进程
///
/// 目前只支持单线程进程
pub fn fork(&mut self) -> ProcPtr {
    assert_eq!(self.threads.len(), 1);
    let child = Box::leak(Box::new(Process {
        pid: new_id(),
        // 复制父进程的地址空间
        vm: self.vm.clone(),
        // 复制父进程的文件表
        files: self.files.clone(),
        ..Process::default()
    }));
    // 为子进程创建自己的主线程
    let t = unsafe {
        let child = child as *mut Process;
        PID2PROC.get().insert((*child).pid, &mut *child);
        self.add_child(&mut *child);
        Thread::new(&mut *child, user_task_entry, 0).0
    };
    let f = t.syscall_frame();
    // 复制父进程根线程的syscall_frame
    *f = *self.threads[0].syscall_frame();
    // 设置子进程的返回值为0
    f.caller.rax = 0;
    child
}

fork函数将会复制当前进程的一些重要资源如地址空间、文件表等。另外,子进程创建自己的主线程,子进程主线程将会复制父进程主线程的syscall_frame,这里的syscall_frame中存放的是线程在用户态中的上下文,子进程在进入用户态之前会从syscall_frame中取出通用寄存器的值和rip的值(详细说明可以参考系统调用)。

这样当子进程的主线程被调度执行时将会从父进程主线程进行系统调用前的上下文开始执行,下面给出了一个用户程序使用fork()的简单示例

// An example in user program
let pid = fork();
if pid == 0 {
    // 子进程
    println!("I am child {}", i);
    exit(0);
} else {
    // 父进程
    println!("I am parent, forked child pid = {}", pid);
}

2.2 exec()

/// 将当前进程的进程入口设置为elf文件入口
///
/// 将命令行参数放在用户栈上(用户程序的main函数不是使用call指令
/// 调用的,而是手动修改rip跳转的,因此需要手动设置rdi和rsi参数)
///
/// 目前只支持单线程的进程
pub fn exec(&mut self, path: &str, args: Vec<String>) -> isize {
    assert_eq!(self.threads.len(), 1);
    if let Some(file) = open_file(path, OpenFlags::RDONLY) {
        let elf_data = file.read_all();
        let (entry, vm) = mm::load_app(&elf_data);
        vm.activate();
        let mut top = (USTACK_TOP - (args.len() + 1) * size_of::<usize>()) as *mut u8;
        let argv = top as *mut usize;
        unsafe {
            for (i, arg) in args.iter().enumerate() {
                top = top.sub(arg.len() + 1);
                core::ptr::copy_nonoverlapping(arg.as_ptr(), top, arg.len());
                // '\0'
                *top.add(arg.len()) = 0;
                *argv.add(i) = top as _;
            }
            // Set argv[argc] = NULL
            *argv.add(args.len()) = 0;
        }
        self.vm = Some(vm);
        let f = self.threads[0].syscall_frame();
        // 进入用户态的sysretq指令会从rcx中恢复ip
        // 从r11中恢复rflags
        f.caller.rcx = entry;
        f.caller.r11 = my_x86_64::RFLAGS_IF;
        f.callee.rsp = top as usize & !0xF;
        f.caller.rdi = args.len();
        f.caller.rsi = argv as _;
        0
    } else {
        -1
    }
}

exec()从文件系统中加载一个elf文件,将其装载到进程的地址空间中。可以将这个过程分成三个部分:

  • 读取elf文件,并为进程创建地址空间
  • 命令行参数处理,将其放在用户栈上
  • 初始化进程的syscall_frame结构,将程序入口点,栈顶,参数等写入其用户态上下文中,进程进入用户态之前就会取出这些上下文恢复寄存器

结合使用fork和exec就可以实现用户态的shell程序,下面是一个简易的结构示意:

// An example of shell
let pid = fork();
// 子进程
if pid == 0 {
    // 执行应用程序
    if exec(args_copy[0].as_str(), args_addr.as_slice()) == -1 {
        println!("Error when executing!");
        return -4;
    }
    unreachable!();
// 父进程
} else {
    children.push(pid);
}

2.3 waitpid()

///  回收一个子进程,返回(子进程号,子进程退出码)
    ///
    /// 未找到子进程-> -1; 找到未回收-> -2;
    pub fn waitpid(&mut self, pid: isize) -> (isize, i32) {
        let mut found_pid = false;
        for (idx, p) in self.children.iter().enumerate() {
            // 若pid为-1,表示回收任一子进程
            if pid == -1 || p.pid == pid as usize {
                found_pid = true;
                if p.zombie {
                    let child = self.children.remove(idx);
                    let ret = (child.pid as _, child.exit_code);
                    unsafe {
                        // drop it
                        drop(Box::from_raw(child));
                    }
                    return ret;
                }
            }
        }
        (if found_pid { -2 } else { -1 }, 0)
    }

waitpid()由父进程调用,回收其子进程,可以指定子进程的pid,也可以令pid为-1,将会回收第一个僵死的子进程。僵死子进程在上面已说明,表示已经退出但是还没有被回收的进程,父进程使用waitpid时将回收僵死子进程的资源并释放内存。

这里以内核主线程的线程函数为例进行说明:

Thread::new(
    root,
    |_| {
        let cur = current();
        // 回收已退出子进程
        loop {
            my_x86_64::disable_interrupts();
            cur.proc.waitpid(-1);
            my_x86_64::enable_interrupts_and_hlt();
        }
    },
    0,
);

内核主线程无限循环回收僵死进程。

用户线程管理

线程是OS进行调度的最小单位,每个线程都有自己的指令执行流。NUDT-OS使用Thread结构体表示用户线程(其实内核中存在也存在一个thread实例用于回收僵死进程)。每个用户线程都有自己的内核栈,发生中断异常或系统调用时,线程将上下文保存在自己的内核栈上,然后调用中断/系统调用处理程序,返回内核态前从内核栈中恢复寄存器和rip。

一、数据结构

// kernel/src/task/thread.rs
pub enum ThreadState {
    /// 可运行
    Runnable,
    /// 阻塞,等待被唤醒
    Blocking,
    /// 异步等待
    Waiting,
    /// 已退出,但尚不能回收
    Zombie,
    /// 已退出, 可以被回收
    Waited,
}

线程具有五种状态,状态转移图如下所示:

异步等待状态发生在异步系统调用时,用户线程使用系统调用向内核服务线程请求服务时,内核主线程将会创建一个协程将其添加到协程执行线程中,用户线程转为异步等待状态,当内核服务线程完成服务时,唤醒用户线程,转为可运行态。

/// 线程抽象
#[repr(C)]
pub struct Thread {
    /// 对齐
    _align: ThreadAlign,
    /// 线程id
    pub tid: usize,
    /// 线程所属进程的指针
    pub proc: ProcPtr,
    /// 线程状态
    pub state: ThreadState,
    /// 结束后的退出码
    pub exit_code: i32,
    /// 线程执行上下文
    pub ctx: Context,
    /// 线程独立内核栈
    kstack: [u8; THREAD_SIZE - size_of::<usize>() * 3 - size_of::<Context>()],
}

每个用户线程都有自己的内核栈,发生中断异常或系统调用时,线程将上下文保存在自己的内核栈上,然后调用中断/系统调用处理程序,返回内核态前从内核栈中恢复寄存器和rip。ctx用于在内核态进行线程切换时保存线程切换前一时刻的内核栈顶位置rsp、指令寄存器rip和被调用者保存的寄存器现场。发生线程调度时,取出下一个就绪线程,从其ctx恢复寄存器现场并执行。

二、关键方法

线程的关键方法包括创建一个新线程new(),线程退出exit()以及从线程自己的内核栈获取用户态上下文syscall_frame(),下面给出介绍

2.1 new()

// kernel/src/task/thread.rs
// impl Thread

/// 创建一个新的线程
///
/// 返回(线程指针,是否需要栈)
pub fn new(proc: &mut Process, entry: fn(usize) -> usize, arg: usize) -> (ThreadPtr, bool) {
    // 线程入口函数
    fn kernel_thread_entry() -> ! {
        let cur = current();
        let entry: fn(usize) -> usize = unsafe { transmute(cur.ctx.regs.rbx) };
        let arg = cur.ctx.regs.rbp;
        let ret = entry(arg);
        // 若是用户态线程,则不会执行下面的exit,需要手动在线程函数中exit
        cur.exit(ret as _);
    }
    let (t, need_stack);
    unsafe {
        let mut it = proc.threads.iter_mut();
        // 寻找当前进程是否有已退出可回收的线程
        loop {
            // 有可回收线程,不需要栈
            if let Some(t1) = it.next() {
                if t1.state == ThreadState::Waited {
                    t = transmute(t1);
                    need_stack = false;
                    break;
                }
            // 遍历结束,没有Waited状态的线程,需要栈
            } else {
                let mut t1 = Box::<Thread>::new_uninit();
                t = &mut *t1.as_mut_ptr();
                t.tid = proc.threads.len();
                proc.threads.push(transmute(t1));
                need_stack = true;
                break;
            }
        }
        // 将新线程加入就绪线程队列
        THREAD_MANAGER.get().enqueue(&mut *(t as *mut _));
        t.proc = &mut *(proc as *mut _);
    }
    t.state = ThreadState::Runnable;
    t.ctx.rip = kernel_thread_entry as _;
    t.ctx.regs.rsp =
        t.kstack.as_ptr_range().end as usize - size_of::<usize>() - size_of::<SyscallFrame>();
    t.ctx.regs.rbx = entry as _;
    t.ctx.regs.rbp = arg;
    (t, need_stack)
}

创建线程可以分为三个主要部分:

  • 总是先寻找进程是否存在waited状态(已被回收但还未释放资源)的线程,若存在,则不需要为其分配用户栈空间(使用之前分配的空间),否则需要为其分配独立的用户栈空间。

  • 总是将线程(内核主线程和所有用户线程)的入口函数设置为kernel_thread_entry(),这是一个封装,它从线程上下文的几个寄存器中读出线程真正的执行函数和参数并执行,然后调用exit()退出线程。

  • 设置线程内核栈栈顶,下图为线程内核栈布局图:

利用new()方法,即可实现创建线程sys_thread_create系统调用。可见若需要栈则为其分配栈空间,并初始线程进入用户态时的上下文(初始化syscall_frame),最终线程通过系统调用处理函数的返回代码片段(参加系统调用)syscall_return返回用户态,从syscall_frame中取出上下文并开始执行。

// src/task/thread.rs
// impl Thread

/// 创建一个线程,若需要则为其分配栈空间
///
///返回线程tid
pub fn sys_thread_create(entry: usize, arg: usize) -> isize {
    let t = current();
    let (t1, need_stack) = Thread::new(t.proc, user_task_entry, 0);
    let stack = USTACK_TOP - t1.tid * USTACK_SIZE;
    // 为线程分配栈空间
    if need_stack {
        t.proc.vm.as_mut().unwrap().insert(MapArea::new(
            VirtAddr(stack - USTACK_SIZE),
            USTACK_SIZE,
            PageTableFlags::PRESENT | PageTableFlags::WRITABLE | PageTableFlags::USER_ACCESSIBLE,
        ));
    }
    let f = t1.syscall_frame();
    f.caller.rcx = entry;
    f.caller.r11 = my_x86_64::RFLAGS_IF;
    f.callee.rsp = stack;
    f.caller.rdi = arg;
    t1.tid as _
}

2.2 exit()

// src/task/thread.rs
// impl Thread

/// 线程退出
///
/// 在每个内核线程的入口函数中,执行完线程函数后调用
pub fn exit(&mut self, exit_code: i32) -> ! {
    println!(
        "[kernel] Process {} Thread {} exited with code {}",
        self.proc.pid, self.tid, exit_code
    );
    // 为根线程,这时释放进程所有线程资源
    if self.tid == 0 {
        let p = &mut self.proc;
        PID2PROC.get().remove(&p.pid).unwrap();
        p.vm = None;
        p.zombie = true;
        p.exit_code = exit_code;
        for ch in &mut p.children {
            root_proc().add_child(ch);
        }
        p.children.clear();
        for t in &mut p.threads {
            t.state = ThreadState::Zombie;
        }
        THREAD_MANAGER.get().clear_zombie();
        // 清理除了0号线程的所有线程. 内核代码在0号进程中,故不能清理
        p.threads.drain(1..);
        p.files.clear();
    }
    self.exit_code = exit_code;
    self.state = ThreadState::Zombie;
    THREAD_MANAGER.get().resched();
    unreachable!("task exited");
}
  • exit函数接受线程的tid,只有当tid为0(主线程)时,其回收进程中所有线程(除了0号线程)的资源,并将进程的zombie标志置为true,但当前进程可能还有未终止的子进程,这时将其所有子进程的父进程都设置为内核中的root进程,root进程通过无限循环waitpid(-1)回收所有终止的子进程。

  • 若tid不为0,则只是将这个线程状态设置为Zombie(已终止但未被回收),当主线程使用waittid系统调用时,其状态变为waited(已回收可复用),则可以在new中被重复利用了。

// syscall/task.rs

/// 等待一个线程结束
///
/// 若回收自己,返回-1
///
/// 若未能回收符合的线程,返回-2
pub fn sys_waittid(tid: usize) -> isize {
    let t = current();
    // 线程不能回收自己
    if t.tid == tid {
        return -1;
    }
    let t1 = try_!(t.proc.threads.get_mut(tid), -1);
    if t1.state == ThreadState::Zombie {
        t1.state = ThreadState::Waited;
        t1.exit_code as _
    } else {
        -2
    }
}

2.3 syscall_frame()

// src/task/thread.rs
// impl Thread

/// 从当前线程栈最高地址获取SyscallFrame
pub fn syscall_frame(&mut self) -> &mut SyscallFrame {
    unsafe { &mut *(self.kstack.as_ptr_range().end as *mut SyscallFrame).sub(1) }
}

syscallframe函数简单地从内核栈最高地址往下取出数据并解析为SyscallFrame结构体,其即为线程用户态上下文。

三、用户程序多线程示例

// user/src/bin/thread.rs
pub fn thread_a() -> ! {
    for _ in 0..1000 {
        print!("a");
    }
    exit(1)
}

pub fn thread_b() -> ! {
    for _ in 0..1000 {
        print!("b");
    }
    exit(2)
}

pub fn thread_c() -> ! {
    for _ in 0..1000 {
        print!("c");
    }
    exit(3)
}

#[no_mangle]
pub fn main() -> i32 {
    let v = vec![
        thread_create(thread_a as usize, 0),
        thread_create(thread_b as usize, 0),
        thread_create(thread_c as usize, 0),
    ];
    for tid in v.iter() {
        let exit_code = waittid(*tid as usize);
        println!("thread#{} exited with code {}", tid, exit_code);
    }
    println!("main thread exited");
    0
}

用户态程序编写线程函数,使用thread_create创建线程,使用waittid回收线程即可

内核线程管理

结合宏内核与微内核的优点,追求内核效率与安全可靠性的平衡,NUDT-OS引入了内核线程,目前的实现中内核线程分为两种:内核服务线程、内核协程执行线程。内核服务线程借助Rust语言的内存安全特性保持独立,任何一个内核服务线程故障不会影响内核整体;利用Rust异步协程机制,NUDT-OS采用多对一线程模型,内核协程执行线程统一处理所有用户线程的异步请求。

一、数据结构

/// 内核线程
#[repr(C)]
pub struct Kthread {
    /// 内核线程ID
    ktid: usize,
    /// 内核线程名称
    name: String,
    /// 运行状态
    state: RwLock<KthreadState>,
    /// 内核线程需要处理的请求队列
    req_queue: Arc<Mutex<VecDeque<Request>>>,
    /// 内核线程请求ID
    req_id: AtomicUsize,
    /// 内核线程已完成请求的ID
    res_id: Arc<Mutex<usize>>,
    /// 请求事件的唤醒器队列
    req_wakers: Mutex<Vec<(Waker, usize)>>,
    /// 上下文
    ctx: Context,
}

每个内核线程运行一种独立的用户服务,其维护一个自身需要处理的请求队列,这些请求是以异步协程的方式由内核协程执行线程来调度处理的,内核线程中维护了自己需要处理的请求协程的唤醒器,当处理完成后,即唤醒协程。

/// 内核线程状态
#[derive(Default, Debug, Clone, Copy, Eq, PartialEq)]
pub enum KthreadState {
    /// 繁忙
    Busy,
    #[default]
    /// 空闲
    Idle,
}

不同于用户线程,内核线程只有繁忙和空闲两种状态,这是因为内核线程在系统中是不会退出的,其在内核初始化时创建,无限循环处理用户线程的请求。处于繁忙状态时,会被调度执行,否则不会被调度执行。

二、关键方法

内核线程的关键方法包括创建新内核线程new(),向内核线程请求队列中添加一个请求add_req(),通知请求队列中一个请求处理完毕response_req()。

2.1 new()

/// 创建内核线程
pub fn new(name: String, entry: usize) -> Arc<Kthread> {
    let ktid = KTHREAD_ID.fetch_add(1, Ordering::Relaxed);

    // 两个线程栈之间空余一小段空间
    let stack_base = KERNEL_STACK_ADDRESS + ktid * KERNEL_STACK_SIZE * 2;

    // 设置sp,ip
    let mut ctx = Context::default();
    ctx.rip = entry;
    ctx.regs.rsp = stack_base;

    // 创建新内核线程
    let kthread = Arc::new(Kthread {
        ktid: ktid,
        name: name,
        state: RwLock::new(KthreadState::Idle),
        req_queue: Arc::new(Mutex::new(VecDeque::new())),
        req_id: AtomicUsize::new(0),
        res_id: Arc::new(Mutex::new(0)),
        req_wakers: Mutex::new(Vec::new()),
        ctx: ctx,
    });

    // 将内核线程放入全局线程队列
    let mut kthread_dequeue = KTHREAD_DEQUEUE.lock();
    kthread_dequeue.push_back(kthread.clone());

    kthread
}

每个内核线程都有自己的内核栈空间,两个内核栈之间空余了一小段空间,这是防止栈溢出时破坏其他线程的栈。内核线程同样包含Context结构保存上下文,创建新内核线程时,初始化线程入口点和栈基地址。

2.2 add_req()

/// 向请求队列添加请求
///
/// 返回请求ID
pub fn add_req(&self, req: Control, client_buffer: Arc<DataBuffer>) -> usize {
    // 计算当前请求ID,从1开始算
    let req_id = self.req_id.fetch_add(1, Ordering::Relaxed);

    // 添加请求
    let req_deque = self.req_queue.clone();
    let mut req_deque_lock = wait_lock_or_yield(&req_deque);
    req_deque_lock.push_back((req_id, req, client_buffer));

    req_id
}

add_req()向内核线程的请求队列中添加一个新的请求。

2.3 response_req()

/// 通知请求队列中一个请求处理完毕
pub fn response_req(&self, new_res_id: usize) {
    // 保存当前完成请求ID,失败时调度
    let mut res_id = wait_lock_or_yield(&self.res_id);
    *res_id = new_res_id;

    let mut req_wakers = wait_lock_or_yield(&self.req_wakers);
    req_wakers.retain(|req_waker| {
        let (waker, req_id) = req_waker;
        // 根据响应的请求id唤醒响应协程
        if *req_id != new_res_id {
            return true;
        }
        // 唤醒协程
        waker.wake_by_ref();
        false
    });
}

response_req()由内核线程中运行的服务代码使用,当一个请求处理完成时,response_req()使用内核线程唤醒器队列中的相应waker唤醒协程。

三、用户线程请求内核线程服务示例

下面给出一个用户线程请求内核服务的实例过程中的控制流说明

3.1 用户线程请求服务

/// 向内核线程发送请求
pub fn sys_kthread_req(kthread: Arc<Kthread>, ctrl_ptr: usize, buf_ptr: usize) -> isize {
    let thread = current();
    let process = &thread.proc;
    // 构造Vec<u8>类型control参数
    let ctrl = unsafe { (*(ctrl_ptr as *const &[u8])).to_vec() };

    // 构造&[u8]类型buf
    let buf = unsafe { *(buf_ptr as *const &[u8]) };

    // 构造DataBuffer
    let buffer = DataBuffer::new(process.root_pa().0, buf.as_ptr() as usize, buf.len());

    // 发送消息
    let req_id = kthread.add_req(ctrl, buffer);

    // 创建协程后等待
    thread.state = ThreadState::Waiting;
    executor::spawn(async_kthread_req(thread, kthread.clone(), req_id));
    1
}

用户线程通过sys_kthread_req()系统调用发送一个请求,这时内核主线程将用户线程设置为异步等待状态(不会被调度执行),然后创建一个async_kthread_req异步协程,将其添加到内核协程执行线程的任务队列中去,等待执行。

/// sys_kthread_req函数的协程任务
async fn async_kthread_req(thread: Arc<Thread>, kthread: Arc<Kthread>, req_id: usize) {
    let kthread_req_future = KthreadReqFuture::new(thread.clone(), req_id, kthread.clone());
    kthread_req_future.await;
    thread.state = ThreadState::Runnable;
}

async_kthread_req()函数创建一个KthreadReqFuture,并等待。当KthreadReqFuture就绪后(此时内核服务线程服务完成),将用户线程状态置为就绪(可调度)。

3.2 协程执行线程轮询KthreadReqFuture协程

impl Future for KthreadReqFuture {
    type Output = ();
    fn poll(self: Pin<&mut Self>, cx: &mut Context) -> Poll<Self::Output> {
        // maybe question here
        let kthread = self.kthread.clone();
        let req_id = self.req_id;
        let res_id_lock = kthread.res_id();
        // 加锁保证不被中断
        let res_id = wait_lock_or_yield(&res_id_lock);

        // 根据res_id和req_id判断请求是否完成
        let ret = if *res_id >= req_id {
            // 完成请求
            Poll::Ready(())
        } else {
            // 未完成请求
            kthread.add_req_waker(cx.waker().clone(), self.req_id);
            Poll::Pending
        };
        return ret;
    }
}

通过内核线程已完成请求id和当前请求id的大小关系判断当前请求是否已完成,若未完成则将当前协程的唤醒器waker添加到内核线程的waker队列中去,并返回pending。

3.3 内核服务线程完成服务并使用waker唤醒协程

下面是一个内核服务线程的代码实例

pub fn entry(ktid: usize) {
    // 无限循环处理请求,请求队列为空时进入睡眠
    loop {
        // 保证所有堆上内存释放完毕,再进入IDEL状态
        {
            // 获取队首请求,不能带锁放弃CPU,否则无法向队列中添加请求
            ...

            // 设置状态为繁忙
            kthread.set_state(KthreadState::Busy);

            // 完成服务
            ...
            
            // 服务完成,唤醒协程
            kthread.response_req(id);
        }

        kthread.set_state(KthreadState::Idle);
    }
}

response_req已在前面说明,唤醒协程后,协程执行线程再次轮询KthreadReqFuture时即返回Ready,async_kthread_req中将用户线程状态设置为就绪(可调度),这样就完成了用户线程从发起请求到完成请求的整个过程。

任务调度

NUDT-OS是分时多任务系统,目前的实现采用简单的时间片轮转调度算法,用户线程有两种时机将会被调度:(1)时间片用完,由内核中断处理程序调度 (2)线程主动放弃CPU,这种情况发生在线程运行结束或者阻塞资源时。

线程是CPU调度的最小单位,NUDT-OS中存在用户线程和内核线程两种线程,内核线程为用户线程提供服务,理论上应该具有更高的优先级。内核必须统一调度内核线程和用户线程两种线程。目前采用的调度算法是当任意内核服务线程需要提供服务时,都优先执行内核线程,所有内核线程空闲时,执行用户线程。

这一节首先介绍线程上下文切换的代码片段,再给出几个典型线程调度时机。

一、调度代码片段

/// 执行用户态程序
pub fn start_user_loop() {
    loop {
        if has_ready_kthread() {
            // 有内核线程,调度其它内核线程
            yield_current_kthread();
            continue;
        }
        // 调度用户线程
        if set_current_thread() {
            // 运行当前线程
            run_current_thread();
            // 清理当前线程
            clear_current_thread();
            continue;
        }
    }
}

主内核线程统一调度内核线程和用户线程,当任意内核服务线程需要提供服务时,都优先执行内核线程,所有内核线程空闲时,执行用户线程。

.text
.global context_switch
context_switch: # (cur: &mut Context, nxt: &Context)
  # Save cur's registers
  mov rax, [rsp] # return address
  mov [rdi + 56], rax # 56 = offsetof(Context, rip)
  mov [rdi + 0], rsp
  mov [rdi + 8], rbx
  mov [rdi + 16], rbp
  mov [rdi + 24], r12
  mov [rdi + 32], r13
  mov [rdi + 40], r14
  mov [rdi + 48], r15
  # Restore nxt's registers
  mov rsp, [rsi + 0]
  mov rbx, [rsi + 8]
  mov rbp, [rsi + 16]
  mov r12, [rsi + 24]
  mov r13, [rsi + 32]
  mov r14, [rsi + 40]
  mov r15, [rsi + 48]
  mov rax, [rsi + 56] # restore return address
  mov [rsp], rax # for stack balance, must use mov instead of push
  ret

切换内核线程或用户线程时,都将线程的现场保存在自己的Context结构中,取出要切换线程的Context恢复寄存器跳转到响应指令地址去执行。

二、几个调度时机

2.1 时钟中断时调度

#[no_mangle]
pub extern "C" fn trap_handler(f: &'static mut TrapFrame) {
    match f.id {
        ... => {
            ...
        }
        // 时钟中断时调度
        TIMER => {
            pic::ack();
            *pic::TICKS.get() += 1;
            task::current_yield();
        }
        ...
    }
}

采用时间片轮转调度算法,每个时钟中断时调度切换线程。

2.2 阻塞系统资源时主动调度

impl File for Stdin {
    ...

    /// 从串口读取一个字符到buf中
    fn read(&self, buf: &mut [u8]) -> usize {
        loop {
            if let Some(c) = console::receive() {
                buf[0] = c as _;
                return 1;
            } else {
                // 当前不能立即读取,则当前线程主动放弃CPU
                task::current_yield();
            }
        }
    }

当线程阻塞系统资源时(不能立刻得到资源),主动调度放弃CPU。

2.3 线程退出时主动调度

/// 线程退出
pub fn exit(&mut self, exit_code: i32) -> ! {
    ...
    // 释放所有线程资源
    self.exit_code = exit_code;
    self.state = ThreadState::Zombie;
    THREAD_MANAGER.get().resched();
    unreachable!("task exited");
}

内存管理

NUDT-OS使用地址空间来显式地保证进程的隔离性,同一进程中的多个线程共享地址空间,但是具有独立的用户栈和内核栈。多个内核线程共享内核地址空间。一个地址空间包含两个部分:

  • 一个连续内存区域的队列:一个地址空间中包含多个连续的虚拟内存区域

  • 一张页表:页表中存储了进程自己的虚拟内存到物理内存的映射关系

借助于x86的页式内存管理机制,cr3寄存器中存放了四级页表的起始物理地址。进程切换时,将cr3寄存器载为进程自己的四级页表起始物理地址,即实现了地址空间的切换。

/// 将自己的页表写入cr3寄存器
pub fn activate(&self) {
    my_x86_64::set_cr3(self.pt.root_pa.0);
}

由于每个进程都有自己的映射关系,所以不同的进程可以使用相同的虚拟地址,例如每个用户进程的用户栈地址都相同:

/// 用户栈顶虚地址
pub const USTACK_TOP: usize = 0x8000_0000_0000;

下面分别介绍内存分配器、页表、和地址空间抽象。

内存分配器

本节介绍堆内存分配器和物理页帧分配器

物理页帧分配

/// 使用bitmap_allocator库定义全局BIT_ALLOCATOR
static BIT_ALLOCATOR: Mutex<BitAlloc256M> = Mutex::new(BitAlloc256M::DEFAULT);

/// 初始化页帧分配器
pub fn init(memory_regions: &'static mut MemoryRegions) {
    let mut ba = BIT_ALLOCATOR.lock();
    println!("[Kernel] Memory regions:");
    for region in memory_regions.into_iter() {
        println!("    {:x?}", region);
        if region.kind == MemoryRegionKind::Usable {
            let start = region.start as usize;
            let end = region.end;
            let start_frame = start as usize / PAGE_SIZE;
            let end_frame = end as usize / PAGE_SIZE;
            ba.insert(start_frame..end_frame);
        }
    }
}

NUDT-OS使用了一个基于位图实现的物理页帧分配器,利用bootloader启动后传入的内存区域信息初始化位图。

/// 物理页帧
#[derive(Debug)]
#[repr(transparent)]
pub struct PhysFrame(usize);

一个物理页帧大小为4096字节,#[repr(transparent)]保证PhysFrame结构体与usize具有相同的内存布局。

impl PhysFrame {
    /// 分配一个物理页帧
    pub fn alloc() -> Option<Self> {
        let mut bitmap_allocator = BIT_ALLOCATOR.lock();
        let paddr = bitmap_allocator.alloc().map(|id| id * PAGE_SIZE).unwrap();
        Some(PhysFrame(paddr))
    }

    /// 回收一个物理页帧
    pub fn dealloc(pa: usize) {
        BIT_ALLOCATOR.lock().dealloc(pa)
    }
    ...
}

impl Drop for PhysFrame {
    /// 页帧结构体声明周期结束时,由编译器调用释放其使用的位
    fn drop(&mut self) {
        BIT_ALLOCATOR.lock().dealloc(self.0);
    }
}

物理页帧由内核显示地分配,需要一个新的页帧时使用alloc()方法分配,但是是由编译器隐式地释放的,释放时调用drop()方法,释放掉页帧对应的bit。

堆内存分配

use buddy_system_allocator::Heap;


struct LockedHeap(Cell<Heap<32>>);
#[global_allocator]
static HEAP_ALLOCATOR: LockedHeap = LockedHeap(Cell::new(Heap::new()));

我们使用了一个带伙伴系统的堆内存分配器(来自第三方库),使用#[global_allocator]将其注册为全局堆内存分配器。

unsafe impl GlobalAlloc for LockedHeap {
    unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
        self.0
            .get()
            .alloc(layout)
            .ok()
            .map_or(0 as _, |p| p.as_ptr())
    }

    unsafe fn dealloc(&self, ptr: *mut u8, layout: Layout) {
        self.0.get().dealloc(NonNull::new_unchecked(ptr), layout)
    }
}

为其实现了GlobalAlloctrait后,内核中即可使用动态内存结构,而具体内存分配和释放是由Rust编译器实现的。

页表

本节介绍NUDT-OS中的页表抽象。

页表项

/// 页表项
#[derive(Clone, Copy)]
#[repr(transparent)]
pub struct PageTableEntry(usize);

impl PageTableEntry {
    /// 1111..._0000_0000_0000
    const PHYS_ADDR_MASK: usize = !(PAGE_SIZE - 1);

    /// 将一个物理地址和flags填入一个页表项中
    pub const fn new_page(pa: PhysAddr, flags: PageTableFlags) -> Self {
        Self((pa.0 & Self::PHYS_ADDR_MASK) | flags.bits() as usize)
    }

    ...
}

每个页表项中存放一个物理地址(下一级页表的起始物理地址),这个地址是关于4096字节对齐的,故低十二位用来存放页表项可能的标记。new_page方法将一个物理地址和一组flags写入一个页表项中。

页表

/// 页表
pub struct PageTable {
    /// 4级页表的起始物理地址
    pub root_pa: PhysAddr,
    /// 页表包含的一组物理页帧
    tables: Vec<PhysFrame>,
}

页表结构体PageTable中包含了四级页表首地址和一个物理页帧的队列。每个物理页帧存放一张大小为4096字节的某级页表。

内核运行时,cr3寄存器中存放四级页表的起始物理地址,硬件的MMU模块寻址虚拟地址时会从cr3寄存器中取出页表地址并查询,最终转换得虚拟地址的物理地址。进程切换时,将cr3寄存器载入自己的页表的起始物理地址即实现了地址空间切换。

x64架构中虚拟地址的各字段含义和地址翻译过程见下图:

/// 从虚拟地址获取四级页表索引,cr3中存四级页表首地址
///
/// 按这个索引取出的是三级页表首地址
const fn p4_index(va: VirtAddr) -> usize {
    (va.0 >> (12 + 27)) & (ENTRY_COUNT - 1)
}

/// 从虚拟地址获取三级页表索引
const fn p3_index(va: VirtAddr) -> usize {
    (va.0 >> (12 + 18)) & (ENTRY_COUNT - 1)
}

/// 从虚拟地址获取二级页表索引
const fn p2_index(va: VirtAddr) -> usize {
    (va.0 >> (12 + 9)) & (ENTRY_COUNT - 1)
}

/// 从虚拟地址获取一级页表索引
const fn p1_index(va: VirtAddr) -> usize {
    (va.0 >> 12) & (ENTRY_COUNT - 1)
}

/// 获取一个虚拟地址的物理地址,可能创建低级页表
fn get_entry_or_create(&mut self, va: VirtAddr) -> Option<&mut PageTableEntry> {
    let p4 = table_of(self.root_pa);
    let p4e = &mut p4[p4_index(va)];
    let p3 = next_table_or_create(p4e, || self.alloc_table())?;
    let p3e = &mut p3[p3_index(va)];
    let p2 = next_table_or_create(p3e, || self.alloc_table())?;
    let p2e = &mut p2[p2_index(va)];
    let p1 = next_table_or_create(p2e, || self.alloc_table())?;
    let p1e = &mut p1[p1_index(va)];
    Some(p1e)
}

将上图中的地址翻译过程用Rust表示如上。

/// 映射一个虚拟地址到一个物理地址,写入页表
impl PageTable {
    pub fn map(&mut self, va: VirtAddr, pa: PhysAddr, flags: PageTableFlags) {
        let entry = self.get_entry_or_create(va).unwrap();
        if !entry.is_unused() {
            panic!("{:#x?} is mapped before mapping", va);
        }
        *entry = PageTableEntry::new_page(pa.align_down(), flags);
    }

    /// 取消映射一个虚拟地址,清除页表
    pub fn unmap(&mut self, va: VirtAddr) {
        let entry = get_entry(self.root_pa, va).unwrap();
        if entry.is_unused() {
            panic!("{:#x?} is invalid before unmapping", va);
        }
        entry.0 = 0;
    }
}

最终实现页表的mapunmap方法

地址空间

本节介绍虚拟地址空间和虚拟内存区域,虚拟地址空间由一张页表和若干虚拟内存区域组成。虚拟内存区域指的是在虚拟地址上连续的一段区域。

虚拟内存区域

/// 一段连续的内存区域
pub struct MapArea {
    /// 起始虚地址
    pub start: VirtAddr,
    /// 区域大小
    pub size: usize,
    /// 映射标志
    pub flags: PageTableFlags,
    /// 虚地址到物理地址的映射
    pub mapper: BTreeMap<VirtAddr, PhysFrame>,
}

一段区域共用同一组映射标记。mapper存放了这段区域中所有虚拟页面到物理页帧的映射关系。

impl MapArea {
    /// 获取一个虚拟地址的物理地址,若没有映射则为其分配一个物理页帧
    ///
    /// 返回虚地址的物理地址
    pub fn map(&mut self, va: VirtAddr) -> PhysAddr {
        assert!(va.is_aligned());
        match self.mapper.entry(va) {
            Entry::Occupied(e) => e.get().start_pa(),
            Entry::Vacant(e) => e.insert(PhysFrame::alloc_zero().unwrap()).start_pa(),
        }
    }

    /// 取消映射一个虚拟地址,物理页帧会由编译器drop释放位
    pub fn unmap(&mut self, va: VirtAddr) {
        self.mapper.remove(&va);
    }

    /// 克隆一段内存区域
    pub fn clone(&self) -> Self {
        let mut mapper = BTreeMap::new();
        for (&va, old_pa) in &self.mapper {
            // 分配一个新的物理页帧
            let new = PhysFrame::alloc().unwrap();
            new.as_slice().copy_from_slice(old_pa.as_slice());
            mapper.insert(va, new);
        }
        Self {
            start: self.start,
            size: self.size,
            flags: self.flags,
            mapper,
        }
    }

映射虚拟内存时,可能会分配物理页帧。取消映射时,编译器会自动帮我们调用物理页帧的drop方法,释放之前分配的位。在使用fork时,子进程复制父进程地址空间,这会复制地址空间中的所有内存区域,clone方法简单的复制所有已经映射的虚拟地址,但是为他们分配新的物理页帧。

/// 映射一段虚拟内存区域,映射关系写入页表
impl PageTable{
    pub fn map_area(&mut self, area: &mut MapArea) {
        assert!(area.start.0 + area.size < PHYS_OFFSET);
        let mut va = area.start.0;
        let end = va + area.size;
        while va < end {
            let pa = area.map(VirtAddr(va));
            self.map(VirtAddr(va), pa, area.flags);
            va += PAGE_SIZE;
        }
    }
}

当使用页表的map_area方法时,将映射关系写入页表。

虚拟地址空间

/// 一个地址空间
pub struct MemorySet {
    /// 页表
    pub pt: PageTable,
    /// 内存区域起地址到内存区域的映射
    areas: BTreeMap<VirtAddr, MapArea>,
}

地址空间包含一张页表和若干内存区域。

impl MemorySet {
    /// 创建一个新的虚拟地址空间
    pub fn new() -> Self {
        Self {
            pt: PageTable::new(),
            areas: BTreeMap::new(),
        }
    }

    /// 地址空间中插入一段内存区域
    pub fn insert(&mut self, area: MapArea) {
        if area.size > 0 {
            if let Entry::Vacant(e) = self.areas.entry(area.start) {
                // 映射关系写入页表
                self.pt.map_area(e.insert(area));
            } else {
                panic!(
                    "MemorySet::insert: MapArea starts from {:#x?} is existed!",
                    area.start
                );
            }
        }
    }

    /// 从页表中清除地址空间中所有内存区域的映射关系
    pub fn clear(&mut self) {
        for area in self.areas.values_mut() {
            self.pt.unmap_area(area);
        }
        self.areas.clear();
    }

    /// 将自己的页表首地址写入cr3寄存器
    pub fn activate(&self) {
        my_x86_64::set_cr3(self.pt.root_pa.0);
    }
}

向内存区域插入insert一个内存区域时,将映射关系写入页表。clear方法清除地址空间中所有内存区域的映射关系,并清除页表中所有对应的页表项。

impl Drop for MemorySet {
    /// 释放时清除所有内存区域
    ///
    /// 从页表中清除映射关系
    fn drop(&mut self) {
        self.clear();
    }
}

impl Clone for MemorySet {
    /// 克隆地址空间,即克隆其包含的所有连续内存区域
    fn clone(&self) -> Self {
        let mut ms = Self::new();
        for area in self.areas.values() {
            ms.insert(area.clone());
        }
        ms
    }
}

MemorySet释放时,不仅要回收其内存,还需要调用clear方法清除页表项,释放分配的物理页帧对应的位。克隆地址空间时,首先克隆原地址空间的所有内存区域,再插入到新的地址空间中。

文件系统

由于文件系统较为复杂且时间有限,目前NUDT-OS采用的文件系统结构和实现借鉴于rcore-tutorial-rsicv。其给出了详细的说明easy-fs本章我们对文件系统做不做详细介绍,只是简要给出一个综合描述,然后给出内核中对easy-fs库的使用和接口。

easy-fs是一个简化后的文件系统模型,后续我们将自行完善实现一个功能更加完善的文件系统(比如Ext2)。

easy-fs是一个简化的文件系统模型,但是具有完整的功能,下面是一个从rcore-tutorial中截取的文件系统描述:

  • 扁平化:仅存在根目录 / 一个目录,剩下所有的文件都放在根目录内。在索引一个文件的时候,我们直接使用文件的文件名而不是它含有 / 的绝对路径。

  • 权限控制:我们不设置用户和用户组概念,全程只有单用户。同时根目录和其他文件也都没有权限控制位,即完全不限制文件的访问方式,不会区分文件是否可执行。

  • 不记录文件访问/修改的任何时间戳。

  • 不支持软硬链接。

磁盘布局如下图(图片来自rcore-tutotial):

layout

下面的部分给出内核对easy-fs的使用和内核中的多种文件类型。

内核接入easy-fs

/// OS里操作的索引节点类型,封装了easy-fs中的Inode
pub struct OSInode {
    /// 是否可读
    readable: bool,
    /// 是否可写
    writable: bool,
    /// 偏移
    offset: Cell<usize>,
    /// 封装easy-fs中的Inode
    inode: Cell<Arc<Inode>>,
}

内核中封装了easy-fs中的Inode,使用OSInode结构来对单个文件进行操作。

/// 全局变量:根节点的索引节点
pub static ROOT_INODE: Cell<Arc<Inode>> = unsafe { transmute([1u8; size_of::<Arc<Inode>>()]) };

/// 文件系统初始化,创建root inode
pub fn init() {
    let efs = EasyFileSystem::open(BLOCK_DEVICE.clone());
    unsafe {
        (ROOT_INODE.get() as *mut Arc<Inode>).write(Arc::new(EasyFileSystem::root_inode(&efs)));
    }
    println!("/****APPS****/");
    for app in ROOT_INODE.ls() {
        println!("{}", app);
    }
    println!("**************/");
}

为根节点创建Inode后,我们使用全局变量ROOT_INODE来创建或打开文件

/// 根据OpenFlags打开根节点下的文件
pub fn open_file(name: &str, flags: OpenFlags) -> Option<Rc<OSInode>> {
    let (readable, writable) = flags.read_write();
    if flags.contains(OpenFlags::CREATE) {
        if let Some(inode) = ROOT_INODE.find(name) {
            inode.clear();
            Some(Rc::new(OSInode::new(readable, writable, inode)))
        } else {
            // create file
            ROOT_INODE
                .create(name)
                .map(|inode| Rc::new(OSInode::new(readable, writable, inode)))
        }
    } else {
        ROOT_INODE.find(name).map(|inode| {
            if flags.contains(OpenFlags::TRUNC) {
                inode.clear();
            }
            Rc::new(OSInode::new(readable, writable, inode))
        })
    }
}

由于easy-fs为扁平化结构,所有文件都在根目录下,所以现在我们可以在文件系统中打开所有用户程序了,exec打开文件并执行。

/// 将当前进程的进程入口设置为elf文件入口
///
/// 将命令行参数放在用户栈上(用户程序的main函数不是使用call指令
/// 调用的,而是手动修改rip跳转的,因此需要手动设置rdi和rsi参数)
///
/// 目前只支持单线程的进程
pub fn exec(&mut self, path: &str, args: Vec<String>) -> isize {
    assert_eq!(self.threads.len(), 1);
    if let Some(file) = open_file(path, OpenFlags::RDONLY) {
        let elf_data = file.read_all();
        ...
    } else {
        -1
    }
}

文件类型

在UNIX系统中,一个重要的设计哲学是一切皆文件,通过将硬件设备、普通文件、管道等多种对象都抽象为文件,OS只将他们作为字节流处理,从而大大简化了OS的设计逻辑。在Rust中,通过泛型编程模型可以方便地实现文件读写接口:

/// OS看到的文件抽象,只关心字节流的读写
pub trait File {
    fn readable(&self) -> bool;
    fn writable(&self) -> bool;
    fn read(&self, buf: &mut [u8]) -> usize;
    fn write(&self, buf: &[u8]) -> usize;
}

为多种对象分别实现File trait,在内核中便可以以统一的方式操作文件。本节简要说明已经实现的文件类型。

标准输入输出

/// 标准输入
pub struct Stdin;
/// 标准输出
pub struct Stdout;

impl File for Stdin {
    /// 从串口读取一个字符到buf中
    fn read(&self, buf: &mut [u8]) -> usize {
        assert_eq!(buf.len(), 1);
        loop {
            if let Some(c) = console::receive() {
                buf[0] = c as _;
                return 1;
            } else {
                // 当前不能立即读取,则当前线程主动放弃CPU
                task::current_yield();
            }
        }
    }
}

impl File for Stdout {
    // 打印到串口(输出到主机屏幕)
    fn write(&self, buf: &[u8]) -> usize {
        if let Ok(str) = core::str::from_utf8(buf) {
            print!("{}", str);
            buf.len()
        } else {
            0
        }
    }
}

标准输入输出结构体没有实体,他们的readwrite接口都是从串口输入输出。在qemu环境下,串口就是我们宿主机上的终端。另外值得注意的是从串口读取时若不能立刻读取,则需要主动调度放弃CPU。

普通文件

impl File for OSInode {
    fn read(&self, buf: &mut [u8]) -> usize {
        let (offset, inode) = (self.offset.get(), self.inode.get());
        let n = inode.read_at(*offset, buf);
        *offset += n;
        n
    }

    fn write(&self, buf: &[u8]) -> usize {
        let (offset, inode) = (self.offset.get(), self.inode.get());
        let n = inode.write_at(*offset, buf);
        *offset += n;
        n
    }
}

对于普通文件,使用easy-fs提供的读写块缓存接口来实现。

管道

/// 管道的一端
pub struct Pipe {
    /// 是否是写端
    writable: bool,
    /// 缓冲区
    buf: Rc<Cell<PipeBuffer>>,
}

/// 管道缓冲区
pub struct PipeBuffer {
    /// 缓冲区
    buf: VecDeque<u8>,
    /// 写端的一个弱引用
    write_end: Weak<Pipe>,
}

管道其实就是一个缓冲区的封装,用于进程间通信。一个进程的输出可以通过管道重定向到另一个进程的输入。具体来说,每个进程创建时都默认打开了三个文件:

  • 标准输入
  • 标准输出
  • 标准错误

重定向时,将需要输出的进程的标准输出文件替换为一个管道文件的写端,输出写入到管道的缓冲器中;将需要输入进程的标准输入文件替换为管道文件的读端即可,从管道缓冲区读出字节。(这个过程实现在user_shell中)

impl File for Pipe {
    /// 从管道的缓冲区读取到buf中
    fn read(&self, buf: &mut [u8]) -> usize {
        assert!(self.readable());
        let mut buf = buf.into_iter();
        let mut n = 0;
        let pipe_buf = self.buf.get();
        loop {
            if pipe_buf.buf.is_empty() {
                // 管道对应的所有写端都已关闭
                if pipe_buf.write_end.upgrade().is_none() {
                    return n;
                }
                // 尚不能读取,当前线程主动放弃CPU
                task::current_yield();
            }
            // 将管道中的字节读出写入buf中
            while let Some(&x) = pipe_buf.buf.front() {
                if let Some(b) = buf.next() {
                    *b = x;
                    pipe_buf.buf.pop_front();
                    n += 1;
                } else {
                    return n;
                }
            }
        }
    }

    /// 拓展管道的缓冲区
    fn write(&self, buf: &[u8]) -> usize {
        assert!(self.writable());
        self.buf.get().buf.extend(buf.iter().copied());
        buf.len()
    }
}

中断处理和系统调用

NUDT-OS是x64架构的,由于采用了syscall快速系统调用指令,系统调用控制流和中断控制流不同。本章分别介绍中断和系统调用的控制流和处理过程。

根据X64调用约定,可以将通用寄存器分为调用者保存和被调用者保存两个部分:

#[derive(Debug, Default, Clone, Copy)]
#[repr(C)]
pub struct CallerRegs {
    pub rax: usize,
    pub rcx: usize,
    pub rdx: usize,
    pub rsi: usize,
    pub rdi: usize,
    pub r8: usize,
    pub r9: usize,
    pub r10: usize,
    pub r11: usize,
}

#[derive(Debug, Default, Clone, Copy)]
#[repr(C)]
pub struct CalleeRegs {
    pub rsp: usize,
    pub rbx: usize,
    pub rbp: usize,
    pub r12: usize,
    pub r13: usize,
    pub r14: usize,
    pub r15: usize,
}

我们知道,CPU使用特权级机制来隔离用户态和内核态,x64中3表示用户特权级,0表示内核特权级,当发生特权级的切换时,CPU要切换栈。每个用户线程都有自己的内核栈,系统调用发生时,其切换到内核栈,将自己用户态现场保存在内核栈上,调用系统调用总控函数,完成后从内核栈恢复用户态现场,返回用户态。

用户态中断时类似系统调用处理流程。内核线程中断时不需要切换栈,在当前栈保存现场调用中断处理函数再恢复现场并返回即可。

下面两节将上面描述的控制流用代码表示。

中断处理

中断处理是由CPU和操作系统协作完成的,当中断发生时,CPU会根据中断号在系统数据结构IDT(中断描述符表)中取出中断处理例程对应的gate descriptor(中断描述符),gate descriptor指向GDT(全局描述符表)中的一个段描述符。段描述符和gate descriptor中的段选择子被载入cs(代码段)寄存器,最后CPU执行特权级的检查,如果目标代码段特权级比当前特权级高,将会从TSS中取出对应的栈指针rsp,切换栈(例如用户态发生中断,中断处理程序的目标代码段处于0特权级,这时从TSS中取出内核栈rsp并切换到内核栈)。最终CPU压入一些寄存器,跳转到中断号对应的中断向量去执行。

上述过程涉及大量x86体系结构的处理细节,若不能完全看懂也没关系,知道中断发生到中断处理例程中间的部分是由CPU完成的,并且可能涉及栈的切换即可。可以宏观上理解,TSS只是内存中的一个数据结构,但是其与CPU交互,其中偏移量为4的字段存放了当前线程的内核栈位置,当发生系统调用或中断从用户态进入内核时,需要手动(系统调用)或是CPU自动(用户态发生中断)地从TSS中取出内核栈并切换栈。

/// 中断处理程序的参数
/// 
/// 同时也是调用中断处理程序前保存的现场
#[derive(Debug, Default, Clone, Copy)]
#[repr(C)]
pub struct TrapFrame {
    pub regs: CallerRegs,
    // Pushed by Vector[i]
    pub id: usize,
    pub err: usize,
    // Pushed by CPU
    pub rip: usize,
    pub cs: usize,
    pub rflags: usize,
    pub rsp: usize,
    pub ss: usize,
}

中断发生时,忽略上面第一段描述的CPU复杂处理过程,系统程序员关注的动作是:

  • 切换栈(用户态中断时)
  • ss、rsp、rflags、cs、rip五个寄存器压栈
  • 根据中断号跳转到中断向量执行

中断向量

为了统一处理,我们在中断向量中将中断号和错误码压栈,然后统一跳转到汇编代码片段__trap_entry中执行,256个中断向量中的内容如下:

.section .text
vector0:
	push 0
	push 0
	jmp __trap_entry
vector1:
	push 0
	push 1
	jmp __trap_entry
vector2:
	push 0
	push 2
	jmp __trap_entry
...

中断入口

__trap_entry代码片段如下:

.macro save
  push r11
  push r10
  push r9
  push r8
  push rdi
  push rsi
  push rdx
  push rcx
  push rax
.endm

.macro restore
  pop rax
  pop rcx
  pop rdx
  pop rsi
  pop rdi
  pop r8
  pop r9
  pop r10
  pop r11
.endm

.global __trap_entry
__trap_entry:
  save
  mov rdi, rsp
  call trap_handler
  mov rax, [rsp + 96] # 96 = offsetof(TrapFrame, cs)
  and rax, 0x3
  jz __from_kernel


__from_user:
  lea rax, [rsp + 128] # prepare new TSS.sp0, 128 = sizeof(TrapFrame)
  mov [TSS + rip + 4], rax


__from_kernel:
  restore
  add rsp, 16 # skip TrapFrame.err and id
  iretq

saverestore宏分别保存和恢复调用者保存寄存器:

首先将调用者保存寄存器保存在栈(内核栈)上,这时栈顶从低地址到高地址正好构成一个TrapFrame结构,将其指针(rsp)作为参数,调用trap_handler函数,这就是内核中真正的中断处理函数。

中断返回时,从TrapFrame中取出中断发生前的cs寄存器,其第0、1比特表示了当前CPU特权级,利用cs寄存器,如果是从用户态触发的中断,将内核栈恢复为中断发生前的地址,内核态中断原本没有切换栈,无须处理,接下来不管是哪种中断,都恢复调用者保存寄存器,使用ireq指令返回对应的特权级。

内核中断处理函数

#[no_mangle]
pub extern "C" fn trap_handler(f: &'static mut TrapFrame) {
    match f.id {
        ...
        TIMER => {
            pic::ack();
            *pic::TICKS.get() += 1;
            task::current_yield();
        }
        _ => {
            println!("trap {:x?}", f);
            task::current().exit(-1);
        }
    }
}

中断处理函数根据中断号进行分别处理。

系统调用

在32位操作系统中,常常使用int 0x80指令来完成系统调用处理。但是在x64中,引入了syscall指令,称为快速系统调用,其不触发中断,而是有自己的一套控制流,在用户态使用syscall指令后,CPU会执行以下动作:

  • 从CPU特殊寄存器STAR MSR中加载cs、ss寄存器
  • 将当前的rflags存入r11寄存器,从CPU特殊寄存器RFMASK MSR中加载rflags
  • 将当前rip存入rcx,从CPU特殊寄存器LSTAR MSR中加载rip

借助快速系统调用机制,我们在系统初始化时将几个MSR寄存器中载入我们期望的系统调用处理入口即可,这样用户态使用syscall指令后,会跳转到syscall_entry代码片段执行

set_msr(LSTAR_MSR, syscall_entry as _);
set_msr(SFMASK_MSR, 0x47700); // TF|DF|IF|IOPL|AC|NT

类似于Trapframe结构,我们使用SyscallFrame结构来保存系统调用发生前用户态的上下文,且它是系统调用处理函数的参数。

/// 系统调用处理程序的参数
/// 
/// 同时也是调用系统调用处理函数前保存的现场
#[derive(Debug, Default, Clone, Copy)]
#[repr(C)]
pub struct SyscallFrame {
    pub caller: CallerRegs,
    pub callee: CalleeRegs,
}

系统调用入口

.global syscall_entry
syscall_entry:
  # syscall instruction do:
  # - load cs, ss from STAR MSR
  # - r11 <- rflags, mask rflags from RFMASK MSR
  # - rcx <- rip, load rip from LSTAR MSR

  # temporarily store user rsp into TSS.sp0 and load kernel rsp from it.
  xchg rsp, [TSS + rip + 4]
  push r15
  push r14
  push r13
  push r12
  push rbp
  push rbx
  push [TSS + rip + 4] # store user rsp into SyscallFrame.rsp
  save
  mov rdi, rsp
  call syscall_handler
  mov [rsp], rax # CallerRegs.rax is at offset 0
  jmp __syscall_return

首先从TSS中取出内核栈加载rsp,并暂时将用户栈rsp存在TSS中。接下来保存调用者保存寄存器和被调用者保存寄存器,这时内核栈顶构成一个SyscallFrame结构体,将其指针作为参数,调用syscall_handler函数。这就是内核中的系统调用总控函数,其根据系统调用号分发并处理系统调用。这个函数有一个返回值,存放在rax中,将其写入SyscallFrame中。

内核系统调用分发

#[no_mangle]
pub extern "C" fn syscall_handler(f: &'static mut SyscallFrame) -> isize {
    let r = &f.caller;
    syscall::syscall(r.rax, [r.rdi, r.rsi, r.rdx])
}

/// 系统调用总控函数
pub fn syscall(syscall_id: usize, args: [usize; 3]) -> isize {
    let ret = match syscall_id {
        SAYSCALL_DUP => sys_dup(args[0] as _),
        SYSCALL_OPEN => sys_open(args[0] as _, args[1] as _),
        SYSCALL_CLOSE => sys_close(args[0]),
        SYSCALL_PIPE => sys_pipe(args[0] as _),
        SYSCALL_READ => sys_read(args[0], args[1] as _, args[2]),
        SYSCALL_WRITE => sys_write(args[0], args[1] as _, args[2]),
        SYSCALL_EXIT => sys_exit(args[0] as i32),
        SYSCALL_SLEEP => sys_sleep(args[0]),
        SYSCALL_YIELD => sys_yield(),
        SYSCALL_GET_TIME => *pic::TICKS as _,
        SYSCALL_GETPID => sys_getpid(),
        SYSCALL_FORK => sys_fork(),
        SYSCALL_EXEC => sys_exec(args[0] as _, args[1] as _),
        SYSCALL_WAITPID => sys_waitpid(args[0] as _, args[1] as _),
        SYSCALL_THREAD_CREATE => sys_thread_create(args[0], args[1]),
        SYSCALL_GETTID => sys_gettid(),
        SYSCALL_WAITTID => sys_waittid(args[0]),
        SYSCALL_MUTEX_CREATE => sys_mutex_create(args[0] == 1),
        SYSCALL_MUTEX_LOCK => sys_mutex_lock(args[0]),
        SYSCALL_MUTEX_UNLOCK => sys_mutex_unlock(args[0]),
        SYSCALL_SEMAPHORE_CREATE => sys_semaphore_create(args[0]),
        SYSCALL_SEMAPHORE_UP => sys_semaphore_up(args[0]),
        SYSCALL_SEMAPHORE_DOWN => sys_semaphore_down(args[0]),
        _ => {
            println!("Unsupported syscall: {}", syscall_id);
            crate::task::current().exit(-1);
        }
    };
    ret
}

rax、rdi、rsi、rdx分别为用户系统调用传入的四个参数,其中rax为系统调用号。这也解释了为什么在系统调用时我们不是像中断一样只保存被调用者保存寄存器,因为我们需要调用者保存的rax、rdi作为参数。

系统调用返回

.global syscall_return
syscall_return: # (SyscallFrame *)
  mov rsp, rdi
__syscall_return:
  # sysretq instruction do:
  # - rip <- rcx
  # - rflags <- r11
  # - cs, ss <- STAR MSR
  
  lea rax, [rsp + 128] # prepare new TSS.sp0, 128 = sizeof(SyscallFrame)
  mov [TSS + rip + 4], rax
  restore
  mov rbx, [rsp + 8]
  mov rbp, [rsp + 16]
  mov r12, [rsp + 24]
  mov r13, [rsp + 32]
  mov r14, [rsp + 40]
  mov r15, [rsp + 48]
  mov rsp, [rsp + 0]
  sysretq

系统调用返回时,恢复TSS中存放的内核栈为之前的地址,从SyscallFrame中恢复通用寄存器,最后使用sysretq指令返回用户态,这条指令相当于syscall指令的逆过程。

用户态syscall

#[inline(always)]
fn syscall(id: usize, arg0: usize, arg1: usize, arg2: usize) -> isize {
    let ret;
    unsafe {
        asm!(
          "syscall",
          in("rax") id, in("rdi") arg0, in("rsi") arg1, in("rdx") arg2,
          out("rcx") _, out("r11") _, // clobbered by syscall
          lateout("rax") ret
        );
    }
    ret
}

用户态使用内联汇编来实现系统调用,将rax、rdi、rsi、rdx作为参数,rax存放系统调用号,最终返回值存放在rax中。用户态使用不同系统调用的方法如下:

pub fn sys_dup(fd: usize) -> isize {
    syscall(SYSCALL_DUP, fd, 0, 0)
}

pub fn sys_open(path: &str, flags: u32) -> isize {
    syscall(SYSCALL_OPEN, path.as_ptr() as _, flags as _, 0)
}
...

异步管理

对于异步系统调用,利用Rust异步协程采用多对一线程模型。内核中有多个内核服务线程,一个内核协程执行器线程。用户线程以异步的形式向内核服务线程请求服务。用户线程通过异步系统调用的形式请求服务。通过内核主线程、内核服务线程、内核协程执行线程协作完成这一过程。本章介绍异步系统调用相关的异步协程管理。

内核线程管理中给出了一个用户线程向内核线程发送请求直到请求完成的控制流实例。这里再次给出简述,本章围绕这个过程进行展开。

下面给出一个用户线程请求内核服务的实例过程中的控制流说明

用户线程请求服务

/// 向内核线程发送请求
pub fn sys_kthread_req(kthread: Arc<Kthread>, ctrl_ptr: usize, buf_ptr: usize) -> isize {
    // 向内核服务线程发送请求
    ...

    // 创建协程后等待
    thread.state = ThreadState::Waiting;
    executor::spawn(async_kthread_req(thread, kthread.clone(), req_id));
    1
}

用户线程通过sys_kthread_req()系统调用发送一个请求,之后用户线程被置为异步等待状态(不会被调度执行),然后创建一个async_kthread_req异步协程,将其添加到内核协程执行线程的任务队列中去,等待执行。

/// sys_kthread_req函数的协程任务
async fn async_kthread_req(thread: Arc<Thread>, kthread: Arc<Kthread>, req_id: usize) {
    let kthread_req_future = KthreadReqFuture::new(thread.clone(), req_id, kthread.clone());
    kthread_req_future.await;
    thread.state = ThreadState::Runnable;
}

协程人物创建一个KthreadReqFuture,并等待。当KthreadReqFuture就绪后(此时内核服务线程服务完成),将用户线程状态置为就绪(可调度)。

协程执行线程轮询KthreadReqFuture协程

impl Future for KthreadReqFuture {
    type Output = ();
    fn poll(self: Pin<&mut Self>, cx: &mut Context) -> Poll<Self::Output> {
        ...
        let res_id = wait_lock_or_yield(&res_id_lock);

        // 根据res_id和req_id判断请求是否完成
        let ret = if *res_id >= req_id {
            // 完成请求
            Poll::Ready(())
        } else {
            // 未完成请求
            kthread.add_req_waker(cx.waker().clone(), self.req_id);
            Poll::Pending
        };
        return ret;
    }
}

通过内核线程已完成请求id和当前请求id的大小关系判断当前请求是否已完成,若未完成则将当前协程的唤醒器waker添加到内核线程的waker队列中去,并返回pending。

内核服务线程完成服务并使用waker唤醒协程

下面是一个内核服务线程的代码实例

pub fn entry(ktid: usize) {
    // 无限循环处理请求,请求队列为空时进入睡眠
    loop {
        // 保证所有堆上内存释放完毕,再进入IDEL状态
        {
            // 获取队首请求,不能带锁放弃CPU,否则无法向队列中添加请求
            ...

            // 设置状态为繁忙
            kthread.set_state(KthreadState::Busy);

            // 完成服务
            ...
            
            // 服务完成,唤醒协程
            kthread.response_req(id);
        }

        kthread.set_state(KthreadState::Idle);
    }
}

response_req已在前面说明,唤醒协程后,协程执行线程再次轮询KthreadReqFuture时即返回Ready,async_kthread_req中将用户线程状态设置为就绪(可调度),这样就完成了用户线程从发起请求到完成请求的整个过程。

下面的各部分将具体介绍异步协程和协程执行器

异步协程

想要使用协程,可以使用Rust中提供的Futuretrait,其代表一个可能尚未就绪的值,我们需要为一个实现Future trait的对象实现poll方法,这个方法查询Future是否准备好,准备好时返回一个Poll::Ready类型,否则返回Poll::Pending.

fn poll(self: Pin<&mut Self>, cx: &mut Context<'_>) -> Poll<Self::Output>;

协程执行器中的协程任务

/// 协程任务
pub struct Task {
    /// 协程执行器
    executor: Weak<Executor>,
    /// 任务协程
    future: Mutex<Pin<Box<dyn Future<Output = ()> + Send + Sync>>>,
    /// 任务状态
    ready: AtomicBool,
}

将一个实现了Future的对象封装起来,作为协程执行器中的一个协程任务。它还包含了协程执行器的一个弱指针,和自身任务的状态(就绪和未就绪)。

impl Task {
    /// 获取任务所属执行器
    pub fn executor(&self) -> Arc<Executor> {
        self.executor.upgrade().unwrap()
    }

    /// 获取任务状态
    pub fn ready(&self) -> bool {
        self.ready.load(Ordering::SeqCst)
    }

    /// 设置任务状态
    pub fn set_ready(&self, ready: bool) {
        self.ready.store(ready, Ordering::SeqCst)
    }

    /// 执行当前任务
    pub fn poll(&self, cx: &mut Context<'_>) -> Poll<()> {
        self.future.lock().as_mut().poll(cx)
    }
}

轮询Task时调用其中内部future对象的poll方法进行轮询。

/// 为协程任务实现唤醒器
impl Woke for Task {
    fn wake_by_ref(task: &Arc<Self>) {
        // 设置执行器状态繁忙
        task.executor().set_state(ExecutorState::Ready);
        // 唤醒当前任务
        task.set_ready(true);
    }
}

wake_by_ref方法将协程任务状态设置为就绪,并将协程执行器状态设置为就绪。在内核线程中我们已经看到,内核线程中有一个唤醒器的队列。当内核线程服务完成时,就会使用wake_by_ref方法唤醒协程。

KthreadReqFuture

/// 向内核线程发送请求协程
pub struct KthreadReqFuture {
    // 发送请求线程
    thread: Arc<Thread>,
    // 请求ID
    req_id: usize,
    // 内核线程
    kthread: Arc<Kthread>,
}

用户线程向内核线程发送请求的时候就会创建一个KthreadReqFuture对象,其包含的req_id代表了自己的请求在内核服务线程中的id。

impl Future for KthreadReqFuture {
    type Output = ();
    fn poll(self: Pin<&mut Self>, cx: &mut Context) -> Poll<Self::Output> {
        // maybe question here
        let kthread = self.kthread.clone();
        let req_id = self.req_id;
        let res_id_lock = kthread.res_id();
        // 加锁保证不被中断
        let res_id = wait_lock_or_yield(&res_id_lock);

        // 根据res_id和req_id判断请求是否完成
        let ret = if *res_id >= req_id {
            // 完成请求
            Poll::Ready(())
        } else {
            // 未完成请求
            kthread.add_req_waker(cx.waker().clone(), self.req_id);
            Poll::Pending
        };
        return ret;
    }
}

对其轮询时,根据自己的id和内核线程中已完成请求的id来判断是否完成了请求。若未完成请求,则不会再轮询,将自己的Waker添加到内核线程队列的唤醒器中,等待服务完成后才会再次轮询并返回Ready。

协程执行器

内核异步系统调用创建的所有异步协程都是由协程执行器来调度的。协程执行器维护一个协程队列,并循环轮询其中的所有任务,当任务完成时,相应的等待的用户线程状态也置为就绪,可以被内核调度继续执行。本节介绍协程执行器结构。

/// 执行器状态
#[derive(Default, PartialEq, Eq)]
pub enum ExecutorState {
    #[default]
    /// 无任务运行
    Idle = 0,
    /// 有任务运行
    Ready = 1,
    /// 有任务正在运行
    Running = 2,
}

/// 协程执行器
pub struct Executor {
    /// 任务队列
    tasks_queue: Mutex<VecDeque<Arc<Task>>>,
    /// 执行器状态
    state: Arc<Mutex<ExecutorState>>,
}

协程执行器具有三个状态,Ready代表有任务就绪了,但当前不在运行状态。

impl Executor {
    /// 添加任务
    pub fn push_task(&self, task: Arc<Task>) {
        self.tasks_queue.lock().push_back(task);
    }

    /// 执行协程,直到任务队列中无就绪任务才停止
    pub fn run(&self) {
        while let Some(task) = self.pop_ready_task() {
            task.set_ready(false);
            // 由task创建waker
            let waker = waker_ref(&task);
            // 由waker创建context
            let mut context = Context::from_waker(&*waker);
            match task.poll(&mut context) {
                Poll::Ready(_) => continue,
                Poll::Pending => self.push_task(task),
            };
        }
    }

    /// 弹出第一个ready的任务
    pub fn pop_ready_task(&self) -> Option<Arc<Task>> {
        let mut tasks_queue = self.tasks_queue.lock();
        for _ in 0..tasks_queue.len() {
            let task = tasks_queue.pop_front().unwrap();
            if task.ready() {
                return Some(task);
            }
            tasks_queue.push_back(task);
        }
        return None;
    }
}

run方法循环地轮询任务队列中所有就绪任务,直到没有任何就绪任务时停止。

/// 全局协程执行器
static EXECUTOR: Lazy<Arc<Executor>> = Lazy::new(|| {
    // 创建内核协程执行器线程对象
    Kthread::new("executor".to_string(), executor_entry as _);

    Arc::new(Executor {
        tasks_queue: Mutex::new(VecDeque::new()),
        state: Arc::new(Mutex::new(ExecutorState::default())),
    })
});

/// 外部接口,执行协程
pub fn run() {
    // 若执行器状态为Ready,设置为Running
    {
        let state_lock = EXECUTOR.state();
        let mut state = wait_lock_or_yield(&state_lock);
        if *state == ExecutorState::Ready {
            *state = ExecutorState::Running;
        }
    }

    EXECUTOR.run();

    // 此时执行器任务队列中无就绪任务
    {
        let state_lock = EXECUTOR.state();
        let mut state = wait_lock_or_yield(&state_lock);
        if *state == ExecutorState::Running {
            *state = ExecutorState::Idle;
        }
    }
}

我们在内核中创建了一个全局协程执行器,其作为一个内核线程无限循环轮询所有的协程任务,处理所有用户线程的异步请求。

/// 协程执行器内核线程入口
pub fn executor_entry(_ktid: usize) {
    // 无限循环运行内核协程
    loop {
        executor::run();
        task::yield_current_kthread();
    }
}

可见,全局协程执行线程的线程函数便是循环地轮询所有异步任务,当任务队列没有就绪任务时,主动放弃CPU调度其他内核线程。

总结与计划

NUDT-OS目前只是一个简单的类UNIX系统,采用混合内核架构,本章简要总结已实现的各模块功能和特点,并给出后续的拓展方向和计划。

总结

NUDT-OS是一个x86_64架构的,使用Rust实现的64位分时多任务操作系统。试图平衡微内核性能低于宏内核可靠性低的问题,我们采用基于内核线程的混合内核架构,目前运行在单核CPU上,主要实现的模块和特点总结如下:

模块功能和特点
任务管理具有进程、内核线程、用户线程三种对象
内核统一调度内核线程和用户线程
采用多对一线程模型,一个协程执行器内核线程服务多个用户线程
支持互斥锁、信号量
内存管理每个进程有独立的地址空间
切换进程时切换地址空间
文件系统一个简易的文件系统
一切皆文件,将多种对象都抽象为文件
实现管道,命令行参数,重定向
异步管理实现异步系统调用
利用协程实现多对一线程模型

目前总共实现了24个系统调用,如下:

  • 任务管理类:
    • fork:复制当前进程
    • exec:当前进程加载可执行文件
    • waitpid:等待子进程结束并回收子进程资源
    • getpid:获取进程号
    • gettid:获取线程号
    • waittid:等待线程结束
    • thread_create:创建用户线程
    • kthread_req:向内核线程发送请求
    • exit:线程退出
    • sleep:线程睡眠
    • yield:线程放弃CPU,主动调度
    • get_time:获取系统时钟数
  • 文件类:
    • dup:复制文件描述符
    • open:打开文件
    • close:关闭文件
    • pipe:创建管道
    • read:从文件读取
    • write:向文件写入
  • 同步互斥:
    • mutex_create:创建互斥锁
    • mutex_lock:互斥锁上锁
    • mutex_unlock:互斥锁解锁
    • semaphore_create:创建信号量
    • semaphore_up:增加信号量资源
    • semaphore_down:减少信号量资源

计划

  • 添加多核支持
  • 实现更完善的文件系统
  • 添加更多内核线程
  • 添加C语言用户程序支持
  • 添加更多设备驱动