本科阶段课程回顾 By Stack

本科阶段课程回顾
Compiled by Stack,at February 18, 2006

1 汇编语言程序设计
1.1 课程介绍—闫宏飞老师
对于计算机科班的学生而言，汇编是一项基本技能和工具，体系结构、操作系统、编译程序等现代
计算的基础设施都离不开汇编语言。闫老师的汇编课程有别于其他老师的汇编课程：
1. 课程使用Linux作为编成环境，使用gcc，ld，nasm等一套开源编译链。
2. 保护模式下的汇编程序设计。
3. 除了汇编之外，还涉及到基本的Linux下程序开发的环境、工具和学习UNIX网络编程，系
统编程模型与接口。
4. 很好的把汇编语言和高级语言衔接了起来，强调了汇编语言实用的一面。
5. 一本非常好的教材，言简意赅，通俗易懂，把握要害。
6. 详细的讲解了搜索引擎的基本原理。汇编从语言的角度来说可以说是最简单的一门语言了，没有什么所谓的“语法糖衣”，数据段、操作数、指令就是全部。所以这门课的重点其实并不在汇编语言，而是在汇编如何与高级语言结合语言，发挥汇编最大的实用性。在介绍汇编语言特点的时候，重点很突出：控制流、C调用规范、数组和结构体的内存布局与取址方式、简明的介绍了IEEE浮点数和8087的汇编，最后以汇编为工具介绍了C++核心特征（多态、继承、名字变异）的实现。除了基本的汇编概念，也会接触到UNIX下的套接字编程，多路选择、异步I/O，多线程/进程，进程间通信等网络编程与系统编程的知识。为以后的学习准备了必备的知识。
1.2 项目介绍
课程使用开源社区非常流行的nasm汇编，nasm汇编和intel汇编非常相似，可以产生多种格式的目标文件（COFF、ELF……）。主要的编程任务使用C语言完成，课程对汇编的要求是，任选工程的一个部分使用汇编实现。一般都是先用C语言写，然后翻译成为汇编，其实在翻译的过程中，你会发现，C语言真的是一种抽象程度非常低的语言，正如K&R设计C语言的初衷“一种可移植的汇编语言”一样。在经过编译原理代码生成的学习之后，这种转换几乎是很直观的。但这种训练可以使你清楚地了解高级语言的实现机制，但如果想清楚程序的运行机制就需要更深的体系结构和操作系统知识。使用汇编语言，代码膨胀是很严重的，300行C语言代码大概可以膨胀到1500行汇编代码，所以应该尽量选取简单短小的模块。同时，课程还会介绍一些基本的汇编优化问题，比如说机器字对齐的字符串拷贝等，因为nasm并不像at&t汇编那样具有强大的嵌入式汇编支持，所以嵌入式汇编讲的不多，有兴趣可以自己看。
搜索引擎是一个非常综合的项目，大致可以分为四个部分，工程量视完成的程度而不同：
1. 网络爬虫（Crawler）
2. 中英文切词
3. 索引
4. 检索服务
网络爬虫负责搜集网页，主要用到的是多线程的异步I/O技术或者多路复用的I/O技术，还需要考虑避免重复搜集网页，去除重复网页，避免被防火墙误认为是DoS攻击（Deny of Service）等等细节问题。通过这部分的构造，可以系统地学习并实践UNIX网络编程、多线程编程，了解HTTP协议，基本的MD5 Hash算法（用于去除重复网页），DNS缓冲技术（避免DoS攻击）。
中英文切词是搜索引擎查全率和查准率的保证，主要作用是根据给定的字典，根据词的优先级（词频）把文本切分成由小的语法元素构成的字符串序列。最容易算法是“最长匹配”算法，但基本上不能够处理有歧义的语句，更好的算法是正向、反向最长匹配算法，但准确率和字典词频
索引主要进行文本处理，建立多级索引，一般而言由：数据文件、正排索引、倒排索引、Hash索引几个部分构成。
检索服务涉及到几方面的内容：提供检索服务的守护进程、提供界面的cgi脚本、对查询结构的关键字高亮显示和排序。这一部分有较高的技术含量，服务进程要处理进程间通信、I/O负载平衡、缓存查询结果等问题，检索模块需要根据和查询词的相关度对结果进行排序，排序算法有很多，可以使用GOOGLE的PageRank，也可以使用距离向量算法，实现都很简单。
你可以选择其中任意一个模块，使用汇编语言实现。
1.3 参考资料
UNP（Unix Network Programming）、APUE-（Advanced Programming Under Unix Environment），上课时助教还推荐了Linux内核源代码情景分析、Linux设备驱动程序开发两本书，但本课并不是操作系统课程，大可不必看。关于汇编语言，有一本比较经典的the Art of Assembly Language，剧厚，我不是很推荐看，对于汇编语言有点过了。如果关心Windows下的汇编，可以看看罗云彬写的Win32汇编，对于分析恶意代码、破解软件颇有裨益。此外，还需要阅读几个RFC文档，具体文档号我记不清了，可以google 一下，主要是关于URL和HTTP协议的，在解析URL和发送HTTP请求的时候需要用到。最后，bash、sed、awk、vi、make等实用的工具也推荐学习，OREILLY有一套书介绍这些工具。至于make，是UNIX/LINUX编程的基础，比较好的一篇文章是George Foot的GNU Make Tutorial，写的真不错，简单、易懂、全面。另外对于有兴趣的同学，可以看一下Eric S.Raymond的Unix 程序设计的艺术一书。Eric是开源社区最出名的旗手之一，有许多知名的文章：Cathedral and Bazaar，如何聪明的提问等。Unix程序设计艺术主要涉及到开源软件的开发方法，设计模式与工具等内容。

2 编译实习
2.1 课程介绍—丁文奎老师
实习课程一般而言都是上几周的课，剩下的时间都用来学习、设计、实现和文档。授课的内容和编译原理的内容重复，但侧重点不同。丁老师更注重讲运行时刻环境和语法制导翻译这两个部分。编译实习的目标语言是Pascal语言的一个子集，就语言的角度来讲，Pascal 比C/C++更适合做编译实习的源语言，首先是简洁，其次是名字的作用域更为灵活，有锻炼价值。但目前，这门课程忽略了很重要的一点，就是对虚拟机的重视。最终生成的可执行代码运行在抽象的“Pascal计算机”上，这个虚拟机本质上是一个栈式计算机，栈式计算机的一个特点就是指令集简单、紧凑。这个虚拟机有固定的堆栈，不支持多线程，没有堆空间，如果不进行扩展的话，并不支持浮点数。课程并不着重介绍虚拟机，只是介绍了指令集，虚拟机的实现已经给出。虚拟机是将来的一个热点，大家都知道，目前的硬件层出不穷，虽然8086系列占有巨大的比例，但在嵌入式设备方面arm、mips等也生机勃勃，所以Sun根据“一次编写到处运行观点”推出了java，大获成功，MS也推出了C#试图从根本上克服移植性这个问题。还有目前流行的一些脚本语言：python、ruby,也都是体系结构无关的。这些技术具有可移植性的关键就是虚拟机，虚拟机本身也涉及到一些基本的问题，比如说垃圾收集，安全模型，执行效率等等，都值得深入研究。遗憾的是这并不是课程的重点。
2.2 项目介绍
编译实习的项目包括几个部分：
1. 构造mini-pascal文法，设计符号表，根据pascal计算机的体系结构，编写语义动作。
2. 使用Parser Generater生成编译程序
3. 扩展虚拟机，提供对浮点数的支持
4. 直接生成可执行文件
其中，最后两个要求是可选的。核心的代码根据实现的程度和所作的扩展而不同，但实现基本的功能只需要1-2000左右代码。
老师推荐的Parser Generater是Lex/Yacc，这是非常经典的工具，在各种平台上都有移植的版本。但并不限制只能使用这一种，目前还有许多流行的Parser Generater，比如：javacc,antlr等，各有各的长处。比如javacc就是一个很好的工具，有丰富的语法库和实例，能够“向前看”任意个token，解决冲突问题非常方便，同时还能够生成堆上的语法树，使得编译程序的可用性和灵活性更强。目前已经有同学使用这个工具完成了编译实习。pascal计算机的体系结构本身比较简单，如果做过汇编语言程序设计的同学，对于虚拟机的指令系统理解起来更是得心应手，应该着重理解控制跳转指令、函数调用指令、数组取址指令等。至于符号表的设计，就是各显神通了，采用hash表或者链接结构都没有问题。
对于浮点数的支持，看似简单，实际上比较麻烦。仅仅考虑单精度的浮点数，就需要为虚拟机增加很多指令，主要是做基本运算和类型转换。此外，对浮点数的引入，也增加了类型检查的难度。直接生成可执行文件其实也不难，有两种选择，一种是生成PE（win下）格式的可执行文件，这比较难，需要深入了解PE文件格式，而且代码生成的难度也很大，因为要生成机器代码。另外一种就是把为Pascal计算机生成的可执行文件的每条指令都翻译为一个函数调用，操作数翻译为参数，最后在和虚拟机的函数链接起来，生成可执行文件。这种方法比较简单，也有人做了。
2.3 考资料
“恐龙书”，这就不用我多说了，除了基本的编译内容外，推荐看类型检查和数据流分析这两章，数据流分析在代码分析，软件维护等软件工程领域的科研方面有很普遍的应用。Lex/Yacc方面，OREILLY有一本书专门介绍，可以参考。至于其他的工具，去工具网站上可以找到丰富的例子和详细的文档。虚拟机方面，我推荐阅读深入Java虚拟机，这是一门概要介绍的书，虽然没有深入到实现的级别上，但介绍了jvm的基本特征：安全模型、byte code、垃圾收集、指令系统、管程模型等等。如果想进一步了解虚拟机的实现，有一本书叫做虚拟机的设计与实现：C/C++。我所说的虚拟机主要是指类似：java虚拟机、python虚拟机等，还有一类可以称作为“软件仿真机”，比如说vmware、bochs、simplesim等，这类虚拟机主要用于裸机的方针和软件的测试，有兴趣可以看一下，bochs是一个开源软件，评价颇高。

3 操作系统实习（2005之后）
3.1 课程介绍—陈向群老师
这门课程我个人认为是本科阶段最有价值的一门课之一。这门课本是牛校MIT的一门研究生课程，课号为6.828。可以在MIT 的Open Course Ware网站上找到这门课的所有实验用代码，但有一些问题，我一会儿会提到。在平常使用计算机的时候，我们可能都会有这样的疑问：当系统启动的时候，操作系统都做了什么工作？可执行程序是如何加载的，如何运行的，为什么同时有多个可执行程序可以运行？为什么有4G的虚拟地址空间而仅仅对应数百兆的物理地址空间？在shell中，管道是怎么实现的，重定向是怎么实现的？通过这门课，你可以完全的、清楚的得到这些问题的答案。除了基本的编程、调试能力之外，通过实践能够加深对操作系统原理的理解。通过之前的学习，我们首先接触了高级语言，之后学习了汇编语言和编译技术，知道了如何把高级语言映射到机器语言。通过体系结构的学习，我们了解了计算机指令系统的设计，知道了机器语言是如何在CPU上执行的。操作系统实习才真正完成了我们对计算机系统原理的认识。
汇编语言和编译技术让我们看到了高级语言的本质，体系结构让我们看到了计算的本质，操作系统让我们看到了计算机系统的本质。通过这门课程的学习，降低了我们学习其他系统编程技术的门槛，比如说：设备驱动，内存映射文件（动态链接库），内存管理，进城切换等等。
和其他所有实习课一样，这门课程的课上时间并不多。主要都是靠自己学习，当初学操作系统原理的时候，总觉得操作系统是一个很虚幻的东西，考试需要背很多的内容，但在实习课程中，大部分原来停留在概念阶段的东西，都会变为现实，比如说进程调度，文件系统，shell 等。
3.2 项目介绍
实习课程的主要任务是，实现一个基本完备的现代操作系统。具有以下几个组成部分：
1. Boot Loader
2. 虚拟内存管理
3. 多进程支持
4. 文件系统
5. 系统调用
6. Shell
通过实习，能够对Intel的IA32体系结构有一个清楚地认识。实习主要通过六次Lab来完成。在实习的过程中，会遇到很多的挑战，操作系统的实现是所有软件中最tricky的，每个Lab除了基本的任务之外，还会有各种挑战，就是有意思的功能扩展，如果能把所有的挑战都实现了，那你就不是一般的强人了。Lab1的内容主要是Boot Loader，在这个lab中，需要了解什么是实模式，什么是保护模式，位置无关代码等一系列非常有技巧性的问题。在Lab2中，主要是实现页表的初始化与维护，管理虚拟地址空间。在Lab3中，设置中断向量，并提供时钟中断，为多进程提供基本支持。在Lab4中，实现了fork系统调用，能够产生多个进程，这个lab中，会接触到一些比较有技巧性的技术，利用缺页中断实现的Copy on Write等。Lab5主要是实现文件系统，操作系统实习是一个设计非常先进的操作系统，文件系统采用C/S的方式实现，具有一些微内核的特征。这个操作系统本身也非常有意思，因为从用户态到内核态的切换具有很大的代价，所以陷入内核的中断和系统调用都是非常简短的。文件系统的服务程序作为一个特殊的进程，采用进程间共享内存的通信方式提供服务。在Lab5中还会实现一个重要的系统调用spawn，用来从文件系统装在可执行程序，并且产生独立进程，在这个系统调用中，操作系统找到入口点（main），分配并初始化堆栈，产生进程并进行调度。在Lab6中，实现了一个Shell，用来和用户进行交互，比如说创建文件，列出目录，执行程序，管道，重定向等。Open Course Ware上下载的代码并不能够直接开始实习，因为目前的操作系统生成a.out格式的可执行文件，而新版本的gcc已经不提供对这种可执行文件的支持了，需要自己进行定制。MIT的课程为了解决这个问题修改了gcc，但我们并不能得到这个gcc。所以，助教提供了产生a.out格式可执行文件的脚本。实际上，这个实习本身是非常难的，但为了降低难度，每次的Lab并不需要我们构造所有的代码，而是采用“填空”的方式，首先给出Lab代码的骨架，然后通过阅读参考文献实现欠缺的主要功能，但即便是这样，也需要首先理解代码的框架。
这个实习是对调试能力的一次很好的锻炼，因为在bochs上进行实习，bochs只提供很有限的运行时debug支持，很多的时候，我们需要汇编级的debug，这需要很多技巧，比如说使用objdump或nm察看符号表等等。在实现的过程中，有很多非常有意思也非常让人头痛的问题等待我们去解决，我只能很简单的说一下，真正的乐趣只有在做的时候才能体会到。
3.3 参考资料
关于IA32的主要资料就是Intel的System Programming Guide，基本上就比较完备了，其中对CPU对操作系统提供的支持讲的也比较清楚。市面上比较有参考价值的书是赵炯的Linux内核完全注释，赵炯是我比较欣赏的一个技术作家，他的书讲问题很清楚，简明扼要，而且比较负责，他的这本书专门配有一个网站：oldlinux.org。而且这本书分析的是早期的Linux内核，非常简单，能够让我们看到本质的东西，我并不推荐Linux内核源代码情景分析，太大了，看起来都不方便。在系统编程方面，虽然和这个实习不是很相关，但我推荐Windows核心编程，这是windows系统编程的经典之作，虽然windows和我们的实习是两个完全不同的操作系统，但我觉得很多东西的相同的，只有真正写过操作系统才会理解核心编程中的内容。此外还有一些技术文章需要看，Make一定要看，gcc的mannual一定要看，这是基本功，而且在这个实习中会大量的用到。如果有时间的话，我也推荐阅读Code Reading这本书，并不真对这一个实习，这本书的英文版写的很容易懂，介绍了一些经验和工具，对大系统的代码阅读有所帮助。
市面上最近流行一本书叫：自己动手写操作系统，很是受欢迎，但我拿过来一看，简直什么都不是，只要做完操作系统实习的人都可以写这么一本书，比他写的内容都要更丰富。我在wm的时候，还看到过有人叫嚣说什么用汇编写了个操作系统之类的，有很多人都不相信，但都说不出理由，只是b4一下了之（而且b4的很没水平）。做了实习后你就会知道，叫嚣的人充其量实现了一个bootloader，这样的教程网上到处是，非常简单，两百多行汇编就搞定了，初二小孩作出来确实不简单，但没什么可大惊小怪的。