感觉面试会用到所以就统一整理一下。

PA（ICS2018）

一个x86全系统模拟器，分为nemu（x86模拟器），nexus-am（提供运行时环境），nanos-lite（简易操作系统）三大模块。

为课程《计算机系统基础》的课程实验，分为5个必做阶段+1个不算分的选做阶段：

• PA0：安装环境
• PA1：实现基础设施（调试器）
• PA2：实现模拟指令执行
• PA3：实现批处理操作系统
• PA4：实现分时多任务
• PA5（选做）：实现浮点运算与性能优化

各阶段简述

PA3和4部分有待细化

PA0：安装环境

PA1：调试器

• 带有打印寄存器和内存、表达式计算、单步执行、添加监视点等功能
• 表达式计算：朴素的递归分治策略
• 监视点：普通的链表

　PA2：指令执行

• 对于每一条指令，分为“取指令、译码、执行”三个阶段。
  • 每种指令对应一个译码函数和执行函数，保存在名为opcode_entry的结构体中。同时有一张opcode_table用来索引指令码对应的译码函数和执行函数。
  • 执行函数依靠一些封装好的rtl（寄存器传输语言）函数简化实现
  • 这一阶段的工作就相当于填空题
• AM：bare-metal运行时环境
  • 通过将运行程序所需的公共要素（如程序的终止退出）封装成API（库），使得同一份程序可以运行在不同的架构上
  • AM根据程序需求把库划分成以下模块：
    • TRM（图灵机）：最简单的运行时环境, 为程序提供基本的计算能力
    • IOE（输入/输出扩展）：为程序提供输出输入的能力
    • CTE（上下文扩展）：为程序提供管理上下文的能力
    • VME（虚存扩展）：为程序提供虚存管理的能力
    • MPE（多处理器扩展）：为程序提供多处理器通信的能力
• 实现常用库函数：
  • 包括一些字符串处理与打印的库函数
• diff-test：将程序看做状态机，与标准实现qemu对比每一步执行过后的状态（这一部分讲义引导较多，具体原理有待深挖）
• 输入输出
  • 端口映射与内存映射（NEMU都实现了）
• 设备
  • 包含串口、时钟、键盘与VGA

PA3：批处理系统

• 将上下文管理抽象成CTE
  • 定义“事件”数据结构
  • 当事件被触发时，cpu保存上下文，（x86）查阅相应的IDT，然后将事件打包给操作系统处理；操作系统处理完毕后恢复上下文
• 加载用户程序：实现loader
• 实现简易文件系统（建议观看oslab3）

PA4：分时多任务

• 进程调度（建议观看oslab2）
• 虚拟存储
  • 当NEMU遇到访存指令时需要增加地址查找动作
• 分时多任务（进程调度）

OSLab(2018)

各阶段简述

L0: amgame

• 一个运行在裸机上的游戏，略。

L1: 多处理器内核上的物理内存管理（pmm）

要点：内存块的组织方式与并发安全

• 内存块组织
  • 2018的OSLab性能尚未被纳入考量范围，因此我采用了最trivial的链表实现，分配策略为first-fit（返回第一块满足要求的内存块），且对每次kalloc与kfree操作上锁。
    • 每一块内存之前有一段存储元数据的header，用于标识当前内存是否空闲、存放前后指针等
    • 分配内存时将大块分裂为小块，回收内存时将相邻的小块合并为大块
  • 比较好的实现是层状分配（我自己取的名字，改日查查term）。
    • 一开始维护一些大的内存块（e.g. 16MB）。当需要分配的内存较小时，如果已经存在小的内存块时就优先选用小的，否则将大的内存块不断一分为二为小的内存块，直到刚好能装得下需要的空间。
    • 回收时遇到相邻的小内存块就合并为大内存块。

L2：多处理器内核上的线程管理 (kmt)

要点：自旋锁与信号量，进程的创建和销毁，进程上下文的保存与切换

• 自旋锁：参考xv6
  • 自旋锁的数据结构：locked，持有的cpu和名称
  • 上锁：lock xchgl原子地将1付给锁的locked变量
  • 通过pushcli和popcli处理多次关中断，只有当一个cpu的cli数目清零后才能打开中断sti
  • 判断一个cpu是否持有锁：需要push和pop　cli
  • 释放锁：与上锁相反
• 信号量：通过资源实现

L3：文件系统实现 (vfs)

要点：文件系统API的实现

• 文件系统主要分为ufs, devfs和procfs，后两者可以直接硬编码实现
• ufs是建立在设备 sda (磁盘) 上的持久数据结构，因此是基于磁盘上的block fs实现的。
  • 需要在block上维护inode信息
  • 文件和目录都有inode，但只有文件占有具体的块。
  • inode在磁盘头部区域单独管理
  • 通过调用block fs提供的API实现文件和目录的创建、读写与删除等操作

编译原理实验