本仓库包含本人于2022年北航操作系统课设中的代码和文档。课设实现了1个完整的操作系统MOS，包含内存管理、进程管理、系统调用、文件系统等功能，同时包含一个Shell。MOS的实现过程共分布在6个Lab中，位于同名分支上，其中Lab6为完整的OS。
另外本人完成了Lab4挑战性任务，根据POSIX标注实现了线程和加锁机制，具体实现方法见Lab4-Challenge-实验报告。下面对本OS做个简要介绍。
OS环境：
- CPU：32位MIPS CPU R3000
- 运行环境：GXemul仿真环境
不同于使用BootLoader的真实操作系统，本OS运行在GXemul仿真环境，操作系统内核的加载过程被大大简化。Gxemul启动后，PC会跳转到位于boot/start.S中的内核入口_start函数，而后通过jal汇编命令跳转到init/main.c下的main函数中。MIPS CPU中，程序地址空间分为4个区域，如下图：
内核位于kseg0位置，CPU发出的逻辑地址到物理地址的映射不经过MMU，而是直接将地址高位清零，通过cache对该区域访问。
更全面的地址映射规则为：
- 虚拟地址位于kseg0，则高位清0通过cache访存，该区域存放内核代码和数据结构
- 虚拟地址位于kseg1，则高3位清0不通过cache访存，用于映射外设
- 虚拟地址位于kuseg，则通过TLB获取物理地址后通过cache访存
当PC跳转到main函数中时，首先会调用mips_init()函数，该函数完成的主要功能是：
- 为内核一级页表、物理内存管理用到的Page结构体和进程管理用到的Env结构体分配物理内存
- 初始化Page结构体和空闲链表，将所有Page结构体插入到空闲链表
本OS采用页式内存管理，使用双向链表管理空闲物理页框。
上面提到的Page结构体就是内存控制块，一个内存控制块对应和管理一页物理内存。Page结构体代码如下：
struct Page {
//链表项，包含下一个Page块和上一个Page块的指针
Page_LIST_entry_t pp_link;
//该页物理内存被引用的次数，即有多少虚拟页映射到该物理页
u_short pp_ref;
};这些结构体初始化时都会被插入到空闲链表page_free_list中，当进程需要分配内存时，将链表头部的Page对应的一块物理内存分配出去，同时从空闲链表头部删去。当物理内存使用完毕（引用次数为0），则将其对应的内存控制块重新插入到空闲链表的头部。
对于kuseg的虚拟地址，MOS采用两级页表进行管理。其地址变换机制如下图：
访问kuseg内的地址时，CPU只会查询TLB，如果查找失败，则会触发TLB中断，相应机制会对其进行重填。
- TLB
TLB是一个硬件，存放在MMU中，每个TLB表项都有64位，高32位是Key，低32位是Data。
其中Key有两个信息，VPN和ASID，VPN指虚拟页号（共20位），ASID标识该页所属进程。
Data包含PFN物理页号和一些权限位，包括是否可写、是否可以访问、是否通过cache访存。
软件必须通过CP0与TLB交互，分为两步：
- 填写CP0寄存器，如EntryHi、EntryLo
- 使用TLB相关指令，如tlbr（将TLB对应表项填入EntryHi和Lo中）、tlbwi等
在之前提到的mips_init()函数中， 除了对内存管理的初始化操作之外，还会通过env_init函数对进程管理进行初始化。该函数将PCB都插入到进程空闲链表中。
- 创建进程
初始完成之后，通过调用ENV_CREATE_PRIORITY创建进程。创建进程的流程为：
- 将一个PCB从空闲链表中取出
- 为新进程初始化地址空间，包括为页目录分配内存，建立自映射页表机制，并将部分内核空间暴露给进程（将进程的部分页目录项填入部分内核空间的物理地址），暴露的目的是允许进程不切换到内核态就可以访问一些内核的数据，符合本OS的微内核设计。
- 为新进程分配进程ID，修改进程状态为就绪态，并设置堆栈指针（虚拟地址），初始化SR寄存器（允许时钟中断），最后将该PCB从空闲链表中移出。
- 在
load_icode函数中为进程分配一页堆栈空间，并将指定的程序代码（elf文件）载入到进程空间中，并设置进程上下文环境中的pc为该代码的入口地址。 - 进程全部初始化完毕后，将PCB插入到0号调度队列。
可能你会有个疑问，通过ENV_CREATE_PRIORITY创建进程后，进程什么时候开始执行呢？别着急，进程的切换和执行，都是时钟中断发生时才进行的，而我们现在还没有初始化异常处理函数。
- 异常处理函数初始化
因此，在mips_init函数中可以找到函数trap_init，它对5类异常分别指定了不同的异常处理函数。当发生异常时，R3000 CPU会自动跳转到0x80000080，开始执行异常分发函数，根据CAUSE寄存器的值，判断是何种异常，从而转到对应的异常处理函数中去执行。其中0号异常处理函数就是中断处理程序handle_int，包括时钟中断等。
- 时钟中断机制
要想产生时钟中断，还需要执行kclock_init函数完成时钟的初始化。该函数向0xb5000100（模拟器gxemul映射实时钟的位置）写入0xc8（表示1s中断200次）。这样，每当时钟中断发生时，中断处理程序handle_int会判断CP0_CAUSE寄存器是否是4号中断（时钟中断），如果是，则执行timer_irq时钟中断处理程序。
timer_irq首先会通过向0xb5000110写入0，承认这次中断，并跳转到sched_yield函数（位于lib/sched.c）。该函数为调度函数，采用的调度算法为时间片轮转算法，每个PCB的优先级为该进程每次运行的时间片数量。
- 进程调度
进程调度共设置了2个调度链表，创建进程时会将PCB插入到第一个调度队列中。这两个链表分别为active和expired，如果发生时钟中断时，本进程时间片被用完，则插入到expired的尾部。之后判断active是否为空，如果为空则切换到expired进行调度，并取队列头部的进程作为要调度的进程。当然，省略了一些细节，比如要判断进程的状态，一个进程的状态共有3种：
- FREE：该进程已经被销毁
- RUNNABLE：该进程就绪，可以执行
- NOT_RUNNABLE：该进程被阻塞了，如果是这样则将该进程插入到另一个队列的尾部
另外，调度链表并没有物理上的active和expired之分，这只是逻辑上的一种看法。active作为当前调度链表，expired则存放时间片用完被替换下来的进程，当active为空时，互换active和expired。
- 进程执行
当调度算法选择好可以执行的进程后，会执行env_run函数，该函数包括两部分：
- 保存当前进程上下文
- 当发生时钟中断时，中断处理函数会执行SAVE_ALL程序将程序的上下文信息（除了CP0.PC之外的所有寄存器）等保存到内存的TIMESTACK位置，要切换进程时就要将TIMESTACK中的上下文信息保存到被替换的PCB中
- 恢复要启动的进程的上下文，然后运行该进程
- 对应lcontext和env_pop_tf函数
进程控制块PCB，是系统感知进程存在的唯一标志，与进程一一对应。该结构体包含几个内容:
- 进程的上下文环境，用于发生内核陷入或进程被调度时保存上下文
- 进程的唯一标识符：进程id
- 父进程id
- 两个链表项，分别用于构建空闲进程链表和调度队列
- 进程状态
- 进程页目录的内核虚拟地址、物理地址
与进程相关的链表有3个，第一个是空闲进程链表，第2和3个均为调度链表。
系统调用实际上是操作系统为用户态提供的一组接口，进程在用户态下通过系统调用可以访问内核提供的操作外设、进程间通信等服务。
用户进程调用的最接近系统调用的用户态函数位于user/syscall_lib.c中，函数名为syscall_*。通过调用msyscall函数，并传递系统调用号，就可以使用不同类型的系统调用。
msyscall函数执行了syscall指令，这是一条汇编指令，CPU陷入内核态，PC寄存器指向异常处理入口，之后跳转到处理系统调用异常的handle_sys函数（位于lib/syscall.S），该函数首先执行SAVE_ALL宏函数，将栈指针寄存器指向内核空间的KERNEL_SP，并将原用户进程的运行现场保存到内核空间。之后根据系统调用号，跳转到不同的系统调用函数。
- 基础系统调用函数
系统调用函数位于lib/syscall_all.c, 共实现了xx个系统调用：
int sys_mem_alloc(int sysno,u_int envid, u_int va, u_int perm)， 为envid进程的虚拟地址va申请一块内存。int sys_mem_map(int sysno,u_int srcid, u_int srcva, u_int dstid, u_int dstva, u_int perm)，将进程srcid的srcva对应的物理页面映射到进程dstid的dstva虚拟地址 (若dstva已经对应了一块物理页面则取消映射关系)，也就是实现共享内存。int sys_mem_unmap(int sysno,u_int envid, u_int va), 解除进程envid虚拟内存和物理内存之间的映射关系void sys_yield(void)，实现用户进程对CPU的放弃， 从而调度其他的进程。
可以看到，系统调用并没有切换CPU的地址空间，也不需要将进程上下文保存到PCB中。仅仅是切换到内核态执行一些内核代码，因此系统调用时内核仍然是代表当前进程的，这也是系统调用与时钟中断的本质区别。
IPC机制目的是要实现两个进程之间的通信，是实现fork、文件系统、管道和Shell的重要基础。
通信即交换数据，可以通过共享空间实现。在env_setup_vm函数中，用户进程的页目录项存放了内核所在的高2G空间，即所有进程共享内核所在的2G空间。因此发送进程可以通过系统调用，在内核空间中写入数据，接收进程通过系统调用，在内核相应部分读出数据。由于内核中的进程控制块与进程直接相关，因此在PCB中存放传递的消息。
IPC流程图：
接收方首先调用ipc_recv函数，表示准备接收，并阻塞等待接收。
发送方调用Ipc_send函数，将数据或页面传递给接收方，并改变接收方运行状态恢复其运行。
Fork，即叉子，是用户态创建新进程的一种方式。创建出的新进程（子进程）拥有独立的虚拟地址空间，但代码段、数据段、堆栈等都被映射到父进程相同的物理页。
其实最初的Unix设计Fork时，是直接将父进程所有资源复制给子进程，但这样效率过低。因此，后来引入一种写时复制机制，Fork时父子进程共享同样的物理页面，当任意一方对某个虚拟页进行修改时，触发页写入异常，操作系统进行写时复制，将该虚拟页映射到新的物理页面。
Fork函数位于user/fork.c，其中执行的核心函数为syscall_env_alloc，该函数创建一个新的进程控制块，并进行相应的初始化，包括进程上下文中的pc寄存器，使得子进程运行时从syscall的下一条指令开始运行。
这里还涉及到页写入异常等非常杂多的内容，可以参见指导书或我的笔记。
文件系统将文件作为数据存储和访问的单位，可以屏蔽访问外存上数据的复杂性。MOS文件系统采用微内核设计，位于用户空间，包含3个部分：
- 外部存储设备驱动
- 文件系统结构
- 文件系统的用户接口
MOS驱动程序采用内存映射I/O技术，通过读写外设寄存器（I/O端口）来进行数据通信，这些外设寄存器被映射到指定的内存空间，因此，对某个特定地址（kseg1内）进行读写就可以实现与外设的交互。user/syscall_lib.c中保存了用户态下读写外设的系统调用函数。
磁盘读写的基本单位是扇区，但操作系统与磁盘交互的基本单位是磁盘块，由多个扇区组成。MOS把第一个磁盘块作为引导扇区和分区表，第二个磁盘块为超级块，描述系统基本信息，如磁盘大小、根目录位置。之后的磁盘块作为位图，判断和标记磁盘块的使用情况。
MOS采用文件控制块（File结构体）描述和管理文件，其功能与Unix中的inode类似，但MOS的文件控制块存放在目录项中。
MOS采用微内核设计，文件系统是一个用户态进程，以服务的形式共其他进程调用。该进程在内核初始化时被创建，用户进程通过IPC请求文件系统服务。
Lab4中IPC机制是一种共享内存的通信方式，而管道是另一种进程间通信方式。它只能在具有公共祖先的进程之间使用，通常用于父子进程通信。
管道通过int pipe(int pfd[2])函数创建：
int pipe(int fd[2]);//成功返回0， 否则-1
//参数fd返回两个文件描述块编号，fd[0]对应读端，fd[1]对应写端管道是一种只存在于内存的文件。首先执行pipe函数，执行fork后，父子进程可以共享这两个文件描述符以及管道缓冲区所在的页面，而其他进程无法连接该管道，这也是为何管道只能在具有公共祖先的进程之间使用。
管道由一个Pipe结构体来表示，包含读指针、写指针以及一个环形缓冲区。
- 实现了spawn函数，可调用文件系统中的可执行文件并执行
- 其他内容详见指导书以及xxx
- 不同.o文件链接时是由谁指导？
顶层Makefile中指定了link_script，它是链接所用的脚本，为tools/scse0_3.lds。linker script会指导所有.o文件的链接，使得各模块按照指定的内存排布顺序进行链接。
链接后的程序从何处开始执行，也是由linker script通过ENTRY指令来指定的。
- 几组核心概念
用户态与内核态：CPU 运行的两种状态，根据R3000 CPU，该状态由SR寄存器中$\rm KU_c$位标志
用户进程与内核：进程是资源分配与调度的基本单位，拥有独立的地址空间， 而内核负责管理系统资源和调度进程，使进程能够并发运行。
- 微内核
本操作系统采用微内核设计方案：
微内核设计主张将传统操作系统中的设备驱动、文件系统等可在用户空间实现的功能，移出内核，作为普通 的用户程序来实现。这样，即使它们崩溃，也不会影响到整个系统的稳定。其他应 用程序通过进程间通讯来请求文件系统等相关服务。因此，在微内核中 IPC 是一个 十分重要的机制。
- MOS内存布局图