ACM SIGOPS名人堂（第七期）
我爱计算机 本文转自CNSys
在本期SIGOPS名人堂中，作者将向大家介绍2011年当选的四篇文章，它们分别是：
- Why Do Computers Stop and What Can Be Done About It?
- Reflections on Trusting Trust
- Programming Semantics for Multiprogrammed Computations
- A Case for Redundant Arrays of Inexpensive Disks(RAID)
这四篇文章中，第一篇是1985年天腾电脑公司的技术报告，第二篇发表于1984 年第8期的ACM通讯，第三篇发表于1965年的ACM程序语言和语用会议，第四篇发表于1988年的ACM SIGMOD数据管理会议。
“Why Do Computers Stop and What Can Be Done About It?”
Jim Gray
这篇文章的作者是1998年图灵奖得主Jim Gray，这也是他第二次出现在我们SIGOPS名人堂介绍的系列文章中。 这篇文章并不是发表在学术期刊或会议上，而是天腾电脑公司（Tandem Computers，1997年被康柏收购）的技术报告。它因为给出了第一个大规模的关于计算机故障的量化分析以及实现高容错计算机系统的最佳实践而选入。
Jim Gray 的科研工作主要在公司完成， 包括IBM、天腾电脑、DEC、微软。这篇文章便是他在天腾电脑公司完成的，天腾是最早从事容错服务器研发制造的厂商，它采用多CPU、不共享内存的冗余设计来实现高容错。Jim Gray 根据公司客户的反馈完成了这篇文章，在很长时间里它都是构建可靠计算机系统的唯一参考。
文章首先分析了导致系统宕机的原因，指出软件错误和操作员的操作失误是相比硬件和环境故障更为主要的原因；然后讨论了多种实现可靠性的技术。文章第一次提出了以进程对（process-pair）和事务（transaction）为基础，实现软件的容错。对于事务处理的贡献也是Jim Gray获得图灵奖的原因之一。
文中，Jim Gray还很幽默地用物理学术语给软件bug 分类。 比如，波尔bug指能够轻易重现的bug，因为波尔的原子模型是固定可预测的；海森堡bug指在测试时难以重新的bug，影射海森堡的不确定性原理对物理粒子的测量会改变粒子的状态。
不过，随着Web 和云计算的发展，当年辉煌的服务器厂商大多日渐式微。天腾、DEC，以及曾经收购了天腾的康柏，都已被惠普收购了。
“Reflections on Trusting Trust”
Ken Thompson
这篇“对深信不疑之信任的反思”是著名的Unix 和C语言之父Ken Thompson 在1984 获得图灵奖的获奖演讲。它展示了如何在软件中植入后门，这种方式被称为 Thompson Hack 或Trusting trust hack。
为了在系统中植入后门，使/bin/login 二进制程序在黑客输入特殊密码时允许其进入，Thompson Hack 在编译器中加入两段代码：一、在编译器发现在编译login程序时，将后门插入到编译出的程序；二、在编译器发现在编译疑似另一个编译器的源码时，会加入第一段代码和第二段代码本身。这样，世界上由该编译器编译而成的程序（包括编译器程序）都会自带后门。用污染的编译器去编译不含恶意代码的编译器源码，得到的仍然是被污染的编译器。
Ken Thompson 指出这种Hack不仅可以在编译器上实现，还可以在Linker、assembler 等工具链上实现。这种Hack的提出告诉我们，仅对程序源码的检查是不能保证得到的二进制是安全的，系统的整个编译链都需要是安全的。也许我们只有从最简单的逻辑电路一步一步向上构建才能保证最后的编译结果的安全性。
这篇文章实际上表达了Ken Thompson对当时软件产业的担忧。幸运的是，今天来看 Thompson Hack 的威胁并没有那么大了。它提出的背景是，当时Unix 被广泛使用，因为硬件架构多种多样，软件安装很少通过二进制来分发，而主要通过源代码编译安装，所以编译工具成为系统安全的关键所在。现在的硬件平台基本上都是x86或ARM等，软件的安全可以通过二进制分发和校验数字签名或哈希值来保证。但是，Ken Thompson这种抱有怀疑的态度，仍旧值得每个程序员学习。
“Programming Semantics for Multiprogrammed Computations”
Jack B. Dennis and Earl C. Van Horn
第三篇论文的作者是MIT的 Jack B. Dennis 和Earl C. Van Horn。这篇论文描述了一系列的元指令与系统设计，以实现操作系统的多道程序（multiprogramming） 功能。多道程序指操作系统并发执行和调度多个任务，当一个任务被IO阻塞，系统可以调度另一个任务以充分利用CPU。在 1965年，OS/360才刚出现一年，Multics分时操作系统也还没有诞生。如今写入计算机课本的操作系统知识与术语在当时并不是常识，论文使用的术语也和现在有所不同。这篇文章因为其奠定了多道程序系统和进程权限的概念基础而入选名人堂奖。
这篇论文先讨论了底层内存的权限管理，使用C-List（Capacity-List）描述进程的权限；然后，描述系统中的管理者（supervisor）如何进行进程、线程的调度与资源分配，以及fork、quit、join、lock等基本操作。对于进程的保护，作者提出采用层级的管理，允许高层次进程访问低层次进程资源而不会暴露自己的资源。
作者Jack B. Dennis 在MIT取得本硕博学位而后留校，1969年提为正教授。他也是Multics 操作系统项目的创始者之一。
“A Case for Redundant Arrays of Inexpensive Disks(RAID)”
David A. Patterson, Garth Gibson, Randy H. Katz
第四篇论文是 David A. Patterson, Garth Gibson, Randy H. Katz合作发表于1988年。就是这篇论文提出了RAID的概念，被引用次数达到将近四千，其重要性与地位不言而喻。
RAID 指用许多独立的含冗余的磁盘组成的阵列。该论文提出用廉价的磁盘组成RAID来替代昂贵的高质量硬盘，而且能同样实现可靠存储。这篇文章给出了RAID1 – RAID5，5个层级的设置。RAID1 将每个磁盘镜像备份，缺点是大量冗余，硬盘利用率低；RAID2使用比RAID1更少的冗余加上汉明码，在小文件读写上性能不佳；RAID3使用相对简单的奇偶校验代替RAID2的汉明码校验，磁盘冗余更少，但小文件读写性能仍不好；RAID4 将RAID3的按位访问改为按块访问，进一步提升小文件读写性能；RAID5 将RAID4的分块错开放置在磁盘阵列上，将小文件读写性能提升到一个正常水平。
本文第一作者David Patterson 也是《计算机体系结构：量化方法》和《计算机组成与设计：硬件/软件接口》两本广泛使用的计算机教材的作者以及RISC 指令集的主要倡导者之一。
小结
纵观获奖的四篇文章，一些是系统领域里具有开创性的工作。比如第三篇 多道程序 和第四篇的RAID 已经写入到计算机的教材；另一些则是具有重要的时代意义，比如第一篇作为系统可靠性的第一次大型调研、第二篇对于当时计算机系统安全性的思考。在下一期的名人堂中，我们将继续为大家介绍2012年的入选文章。
作者
郭兴，中国科学技术大学计算机科学与技术学院，研究生，主要研究方向：程序分析、软件漏洞检测。
