在开始愉快的PA之旅之前

PA是一种全新的训练

我们从以下方面对不同的作业/实验/问题进行比较:

基本原理做事方案正确性风险代表例子
阐述明确基本正确高中物理实验
阐述明确可能出错程序设计作业
阐述需要思考基本正确数学证明/算法设计题
阐述需要思考可能出错PA, OSlab
需要探索需要思考可能出错业界和科研的真实问题

做PA的终极目标是通过构建一个简单完整的计算机系统, 来深入理解程序如何在计算机上运行. 和那些"用递归实现汉诺塔"的程序设计作业不同, 计算机系统比汉诺塔要复杂得多. 这意味着, 通过程序设计作业的训练方式是不足以完成PA的, 只有去尝试理解并掌握计算机系统的每一处细节, 才能一步步完成PA.

所以, 不要再用程序设计作业的风格来抱怨PA讲义写得不清楚, 之所以讲义的描述点到即止, 是为了强迫大家去理清计算机系统的每一处细节, 去推敲每一个模块之间的关系, 也是为了让大家积累对系统足够的了解来面对未知的bug.

这对你来说也许是一种前所未有的训练方式, 所以你也需要拿出全新的态度来接受全新的挑战.

做PA的正确姿势 - 从今天开始, 不要偷懒了 (这是一碗鸡汤, 当你将来觉得迷茫的时候, 回来这里看看吧)

我们先列举一些错误做法:

  • 遇到问题了, 随便改改试试, 说不定就过了
  • 随便改改过不了, 赶紧找大腿/助教/老师来搞定
  • 这个函数/文件/命令看不懂, 反正也不是我写的, 算了就这样吧
  • 宁愿在百度中舒服地浪费生命, 也不想用谷歌快速解决问题
  • 蓝框题不算分, 不看也没关系
  • 反正大阶段有一个月的时间, 最后一周开始做, 应该还能赶上

如果你采用了以上做法, 你也许真的能很快完成前期的实验内容, 但这是以放弃训练机会为代价的. 随着实验进度的推进, 你会感觉PA对你来说越来越吃力.

正确的做法是:

  • 多思考为什么
    • 从问题开始着手理解系统也是个不错的方法
  • 独立解决问题
    • 即使是调一个很弱智的bug, "顺带"能学到的东西也比你想象中多得多
    • 换句话说, 如果你选择抱大腿, 你失去的机会也比你想象中多得多
  • 尝试尽可能理解每一处细节
    • 将来调bug的时候, 这些细节就是你手中强有力的工具
    • 换句话说, 当你在调bug的时候感到无从下手, 一定是你不了解其中的细节
  • 用正确的工具做事情
    • 这才是节省时间的科学方法, 而不是偷懒
  • 多读讲义, 彩蛋很多
    • 讲义中特地设置了不少"不合时宜"的提示, 有的彩蛋要多次阅读才能明白其中的奥妙
    • 多看一道蓝框题, 也许能少调几天bug
  • 按时完成, 拒绝拖延
    • 这样你才有时间做到上面几点

事实上, 这些做法就是PA中的最本质的能力训练, 而这样的训练, 在PA0就已经开始了: PA0之所以让大家白手装机, 就是希望让大家在解决小问题的过程中收获经验, 用来解决更大的问题; 同时也给大家传播"我可以通过STFW和RTFM独立解决问题"的最初原的信念, 这种信念可以帮助大家驱散对未知的恐惧.

你用来应付程序设计作业的心态, 在PA这里是混不过去的, 问题暴露的速度比你想象中快得多. 所以, 从今天开始, 不要偷懒了.

NEMU是什么?

PA的目的是要实现NEMU, 一款经过简化的全系统模拟器. 但什么是模拟器呢?

你小时候应该玩过红白机, 超级玛丽, 坦克大战, 魂斗罗... 它们的画面是否让你记忆犹新? (希望我们之间没有代沟...) 随着时代的发展, 你已经很难在市场上看到红白机的身影了. 当你正在为此感到苦恼的时候, 模拟器的横空出世唤醒了你心中尘封已久的童年回忆. 红白机模拟器可以为你模拟出红白机的所有功能. 有了它, 你就好像有了一个真正的红白机, 可以玩你最喜欢的红白机游戏. 我们移植了一个红白机模拟器项目FCEUX在新窗口中打开, 你在PA0中已经克隆了它. 你可以在如今这个红白机难以寻觅的时代, 再次回味你儿时的快乐时光, 这实在是太神奇了!

不来玩一下吗?

我们在这里在新窗口中打开(可能需要在校园网内部访问)提供了一些游戏的ROM用于测试, 阅读并根据fceux-am/README.md中的内容进行操作, 即可在弹出的新窗口中运行超级玛丽.

你也可以将自己STFW获得的其它ROM文件放进来, 这样就可以运行其它游戏了.

检查画面, 按键和声音

在运行游戏的过程中, 你需要顺便检查一下是否可以看到画面, 响应按键并听到声音. 超级玛丽在初始界面中不会播放声音, 但会在正式进入关卡时播放声音. 如果没有声音, 会影响PA的部分选做内容, 但不会影响成绩; 但如果画面不能正常显示, 可能会影响PA必做部分的实验内容, 请自行搜索解决方案.

为了检查按键, 你需要克隆一个新的子项目am-kernels, 里面包含了一些测试程序:

cd ics2023
bash init.sh am-kernels

然后运行其中的按键测试程序:

cd am-kernels/tests/am-tests
make ARCH=native mainargs=k run

运行后会弹出一个新窗口, 在新窗口中按下按键, 你将会看到程序在终端输出相应的按键信息, 包括按键名, 键盘码, 以及按键状态. 如果你发现输出的按键信息与按下的按键不符, 请自行搜索解决方案(可采用关键字"SDL keystroke"等). 有网友提示问题可能与中文输入法兼容性问题在新窗口中打开相关, 供参考.

觉得编译有点慢?

make程序默认使用单线程来顺序地编译所有文件, 而FCEUX的源文件又非常多, 你可能需要等待十几秒来完成编译. 但现在的CPU都是多核多线程了, 不把这些计算能力用起来也是白白浪费. 为了加快编译的过程, 我们可以让make创建多个线程来并行地编译文件.

具体地, 首先你需要通过lscpu命令来查询你的系统中有多少个CPU. 然后在运行make的时候添加一个-j?的参数, 其中?为你查询到的CPU数量. 例如-j4表示创建4个线程来并行编译, 如果系统中CPU的数量大于等于4, 那么操作系统就可以将这4个线程调度到4个CPU上同时执行, 达到加速的效果; 但如果系统中只有2个CPU, 那操作系统最多能将2个线程调度到2个CPU上同时执行, 这时候的加速效果就和-j2差不多了.

为了查看编译加速的效果, 你可以在编译的命令前面添加time命令, 它将会对紧跟在其后的命令的执行时间进行统计, 你只需要关注total一栏的时间即可. 你可以通过make clean清除所有的编译结果, 然后重新编译并统计时间, 对比单线程编译和多线程编译的编译时间; 你也可以尝试不同的线程数量进行编译, 并对比加速比.

还是觉得编译有点慢?

我们清除所有编译结果之后重新编译, 源文件并没有发生任何变化, 按道理编译出来的目标文件也应该和上一次编译结果完全相同. 既然这样, 那我们能不能把这些目标文件以某种方式存起来, 下次编译的时候如果发现源文件没有变化, 就直接取出之前的目标文件作为编译结果, 从而跳过编译的步骤呢?

还真有工具专门做这件事! 这个工具叫ccache:

apt-get install ccache

如果你通过man阅读ccache的手册, 你会发现ccache是一个compiler cache. cache是计算机领域中的一个术语, 你将会在后续的ICS课程中学习相关的内容.

为了使用ccache, 你还需要进行一些配置的工作. 首先运行如下命令来查看一个命令的所在路径:

which gcc

它默认会输出/usr/bin/gcc, 表示当你执行gcc命令时, 实际执行的是/usr/bin/gcc. 作为一个RTFM的练习, 接下来你需要阅读man ccache中的内容, 并根据手册的说明, 在.bashrc文件中对某个环境变量进行正确的设置. 如果你的设置正确且生效, 重新运行which gcc, 你将会看到输出变成了/usr/lib/ccache/gcc. 如果你不了解环境变量和.bashrc, STFW.

现在就可以来体验ccache的效果了. 首先先清除编译结果, 然后重新编译并统计时间. 你会发现这次编译时间反而比之前要更长一些, 这是因为除了需要开展正常的编译工作之外, ccache还需要花时间把目标文件存起来. 接下来再次清除编辑结果, 重新编译并统计时间, 你会发现第二次编译的速度有了非常明显的提升! 这说明ccache确实跳过了完全重复的编译过程, 发挥了加速的作用. 如果和多线程编译共同使用, 编译速度还能进一步加快!

在开发项目的过程中, 有时确实会需要在清除编译结果后进行全新的编译(fresh build). 到了PA的后期, 你可能会多次编译一些包含数百个文件的库, 在这些场合下, ccache能够极大地节省编译的时间, 从而提高项目开发的效率.

你被计算机强大的能力征服了, 你不禁思考, 这到底是怎么做到的? 你学习完程序设计基础课程, 但仍然找不到你想要的答案. 但你可以肯定的是, 红白机模拟器只是一个普通的程序, 因为你还是需要像运行Hello World程序那样运行它. 但同时你又觉得, 红白机模拟器又不像一个普通的程序, 它究竟是怎么模拟出一个红白机的世界, 让红白机游戏在这个世界中运行的呢?

事实上, NEMU就是在做类似的事情! 它模拟了一个硬件的世界, 你可以在这个硬件世界中执行程序. 换句话说, 你将要在PA中编写一个用来执行其它程序的程序! 为了更好地理解NEMU的功能, 下面将

  • 在GNU/Linux中运行Hello World程序
  • 在GNU/Linux中通过红白机模拟器玩超级玛丽
  • 在GNU/Linux中通过NEMU运行Hello World程序

这三种情况进行比较.

                         +---------------------+  +---------------------+
                         |     Super Mario     |  |    "Hello World"    |
                         +---------------------+  +---------------------+
                         |    Simulated NES    |  |      Simulated      |
                         |       hardware      |  |       hardware      |
+---------------------+  +---------------------+  +---------------------+
|    "Hello World"    |  |     NES Emulator    |  |        NEMU         |
+---------------------+  +---------------------+  +---------------------+
|      GNU/Linux      |  |      GNU/Linux      |  |      GNU/Linux      |
+---------------------+  +---------------------+  +---------------------+
|    Real hardware    |  |    Real hardware    |  |    Real hardware    |
+---------------------+  +---------------------+  +---------------------+
          (a)                      (b)                     (c)

图中(a)展示了"在GNU/Linux中运行Hello World"的情况. GNU/Linux操作系统直接运行在真实的计算机硬件上, 对计算机底层硬件进行了抽象, 同时向上层的用户程序提供接口和服务. Hello World程序输出信息的时候, 需要用到操作系统提供的接口, 因此Hello World程序并不是直接运行在真实的计算机硬件上, 而是运行在操作系统(在这里是GNU/Linux)上.

图中(b)展示了"在GNU/Linux中通过红白机模拟器玩超级玛丽"的情况. 在GNU/Linux看来, 运行在其上的红白机模拟器NES Emulator和上面提到的Hello World程序一样, 都只不过是一个用户程序而已. 神奇的是, 红白机模拟器的功能是负责模拟出一套完整的红白机硬件, 让超级玛丽可以在其上运行. 事实上, 对于超级玛丽来说, 它并不能区分自己是运行在真实的红白机硬件之上, 还是运行在模拟出来的红白机硬件之上, 这正是"模拟"的障眼法.

图中(c)展示了"在GNU/Linux中通过NEMU执行Hello World"的情况. 在GNU/Linux看来, 运行在其上的NEMU和上面提到的Hello World程序一样, 都只不过是一个用户程序而已. 但NEMU的功能是负责模拟出一套计算机硬件, 让程序可以在其上运行. 事实上, 上图只是给出了对NEMU的一个基本理解, 更多细节会在后续PA中逐渐补充.

NEMU是什么?

上述描述对你来说也许还有些晦涩难懂, 让我们来看一个ATM机的例子.

ATM机是一个物理上存在的机器, 它的功能需要由物理电路和机械模块来支撑. 例如我们在ATM机上进行存款操作的时候, ATM机都会吭哧吭哧地响, 让我们相信确实是一台真实的机器. 另一方面, 现在第三方支付平台也非常流行, 例如支付宝. 事实上, 我们可以把支付宝APP看成一个模拟的ATM机, 在这个模拟的ATM机里面, 真实ATM机具备的所有功能, 包括存款, 取款, 查询余额, 转账等等, 都通过支付宝APP这个程序来实现.

同样地, NEMU就是一个模拟出来的计算机系统, 物理计算机中的基本功能, 在NEMU中都是通过程序来实现的. 要模拟出一个计算机系统并没有你想象中的那么困难. 我们可以把计算机看成由若干个硬件部件组成, 这些部件之间相互协助, 完成"运行程序"这件事情. 在NEMU中, 每一个硬件部件都由一个程序相关的数据对象来模拟, 例如变量, 数组, 结构体等; 而对这些部件的操作则通过对相应数据对象的操作来模拟. 例如NEMU中使用数组来模拟内存, 那么对这个数组进行读写则相当于对内存进行读写.

我们可以把实现NEMU的过程看成是开发一个支付宝APP. 不同的是, 支付宝具备的是真实ATM机的功能, 是用来交易的; 而NEMU具备的是物理计算机系统的功能, 是用来执行程序的. 因此我们说, NEMU是一个用来执行其它程序的程序.

NEMU的威力会让你感到吃惊! 它不仅仅能运行Hello World这样的小程序, 在PA的后期, 你将会在NEMU中运行经典RPG游戏仙剑奇侠传在新窗口中打开(很酷! %>_<%). 如果你完成了所有的选做编程内容, 你甚至可以在NEMU中运行现代文字冒险游戏CLANNAD在新窗口中打开! 完成PA之后, 你在程序设计课上对程序的认识会被彻底颠覆, 你会觉得计算机不再是一个神秘的黑盒, 甚至你会发现创造一个属于自己的计算机不再是遥不可及!

选择你的角色

新特性 - 多主线

PA有一个多主线的特性. 具体地, 你需要从x86在新窗口中打开/mips32在新窗口中打开/riscv32(64)在新窗口中打开这三种指令集架构(ISA)在新窗口中打开中选择一种, 来实现"创造属于自己的计算机"这一梦想.

但无论选择哪种ISA, 你最终都会体会到"软硬件共同协助来支持程序执行"的机理: 所谓的tradeoff, 只不过是决定将一件事情交给硬件来做, 还是交给软件来做. 但三种ISA毕竟各有特色, 它们对不同章节的攻略难度如下表所示(5星 - 容易, 1星 - 困难)

x86mips32riscv32(64)
PA1 - 简易调试器与ISA选择关系不大
PA2 - 冯诺依曼计算机系统
PA3 - 批处理系统
PA4 - 分时多任务

什么是ISA?

大部分课本上都会有类似"ISA是软件和硬件之间的接口"这种诠释, 但对于还不了解软件和硬件之间如何协同工作的你来说, "接口"这个词还是太抽象了.

为了理解ISA, 我们可以用现实生活中的例子来比喻: 螺钉和螺母是生活中两种常见的物品, 它们一般需要配对来使用. 给定一个螺钉, 那就要找到一个符合相同尺寸规范的螺母才能配合使用, 反之亦然.

在计算机世界中也是类似的: 不同架构的计算机(或者说硬件)好比不同尺寸的螺钉, 不同架构的程序(或者说软件)就相当于是不同尺寸的螺母, 如果一个程序要在特定架构的计算机上运行, 那么这个程序和计算机就必须是符合同一套规范才行.

因此, ISA的本质就是类似这样的规范. 所以ISA的存在形式既不是硬件电路, 也不是软件代码, 而是一本规范手册.

和螺钉螺母的生产过程类似, 计算机硬件是按照ISA规范手册构造出来的, 而程序也是按照ISA规范手册编写(或生成)出来的, 至于ISA规范里面都有哪些内容, 我们应该如何构造一个符合规范的计算机, 程序应该如何遵守这些规范来在计算机上运行, 回答这些问题正是做PA的一个目标.

我该如何选择?

如果你打算选熟悉的, 那就选x86, 毕竟ICS理论课主要围绕x86开展. 但你多半会被x86指令的复杂性折磨半死, 而且x86的最终性能其实并不高, 不能流畅地展示游戏的运行.

如果你打算选简单的, 那就选riscv32, 你将会体会到什么是"优雅的ISA设计". 由于riscv32的简单, 你可以比较轻松地获得近乎x86两倍的性能, 有着不错的展示效果.

如果你接下来打算设计一款riscv64的硬件处理器, 那就选riscv64, 你将会体会到DiffTest是如何帮你大幅提升硬件开发效率, 告别枯燥的波形调试.

如果你打算挑战极限, 那就选mips32: 相比于以上两者, 选择mips32需要了解更多细节才能正确构建出完整的计算机系统. 因此mips32仅供喜欢挑战, 或者攻略二周目的同学选择.

不过无论你选哪种ISA, 有一点是共通的, 那就是RTFM, 因为ISA的本质是规范手册. 另外, NEMU程序本身也是x86的(准确来说是x64), 不会随着你选择的ISA而变化, 变化的只是在NEMU中模拟的计算机.

如果你是修读本课程(计算机系统基础)的学生, 那么你就没有选择了

你必须选择riscv32, 否则你的代码提交到OJ上将会无法正确运行. 我们之所以这样要求大家, 是因为

  • riscv是模块化的, 选择riscv32只需要实现很少的指令
  • 大家已经在大一下学期的"数字逻辑与计算机组成"课程中学习过riscv32, 相比于其它ISA, 大家对riscv32会更加熟悉
  • 框架代码的基础设施对riscv有更好的支持

这些原因都可以帮助你更顺利地完成PA, 从而投入更多的时间到期末复习当中.

为了方便叙述, 讲义将用$ISA来表示你选择的ISA, 例如对于nemu/src/isa/$ISA/reg.c, 若你选择的是x86, 它将表示nemu/src/isa/x86/reg.c; 若你选择的是riscv32, 它将表示nemu/src/isa/riscv32/reg.c. 除非讲义明确说明, 否则$ISA总是表示你选择的ISA, 而不是$ISA这四个字符.

NEMU的框架代码会把riscv32作为默认的ISA, 如果你希望选择其它ISA, 你需要在NEMU的工程目录下执行make menuconfig, 然后在Base ISA一栏中切换到你选择的ISA, 然后保存配置并退出菜单.

最后, 你还需要领取新手礼包 - ISA相关的生存手册 (部分ISA无关的手册请到讲义首页领取):

ISA新手礼包
x86Intel 80386 Programmer's Reference Manual (简称i386手册) (PDF在新窗口中打开)(HTML在新窗口中打开)
System V ABI for i386在新窗口中打开
mips32MIPS32 Architecture For Programmers (Volume I在新窗口中打开, Volume II在新窗口中打开, Volume III在新窗口中打开)
System V ABI for mips32在新窗口中打开
riscv32(64)The RISC-V Instruction Set Manual (Volume I在新窗口中打开, Volume II在新窗口中打开)
ABI for riscv在新窗口中打开

riscv32和riscv64

事实上, riscv32和riscv64之间的区别非常小, 以至于它们的ISA手册都是相同的. 因此讲义中绝大部分针对riscv32的描述, 对riscv64也是适用的. 在描述不适用riscv64的场合, 我们会进行额外的补充说明. 因此如果你选择了riscv64, 当讲义中没有对riscv64进行额外说明的时候, 你只需要参考riscv32的相应说明即可.

还等什么呢?

让我们来开始这段激动人心的旅程吧!

做一个素质合格的CSer

PA除了给大家展示"程序如何在计算机中执行"这一终极目标之外, 还加入了很多科学的做事原则. PA在尝试制造场景让大家体会这些原则的重要性, 这也是作为一个素质合格的CSer的必修课. 如果你只是仅仅把PA作为一个编程大任务, 我们相信你确实吃了亏.

PA是一个值得打二周目的游戏, 在二周目的过程中, 你会对这些原则有更深刻的理解. 多主线的特性也让二周目不至于太过乏味, 同时讲义中也准备了一些适合在二周目思考的问题, 希望大家玩得开心!

随时记录实验心得

我们已经在你学长学姐的实验报告中多次看到类似的悔恨: 因为没有及时记录实验心得而在编写实验报告的时候忘记了自己经历趣事的细节. 为了和助教们分享你的各种实验经历, 我们建议你在实验过程中随时记录实验心得, 比如自己踩过的大坑, 或者是调了一周之后才发现的一个弱智bug, 等等.

我们相信, 当你做完PA回过头来阅读这些心得的时候, 就会发现这对你来说是一笔宝贵的财富.