ACM SIGOPS名人堂（第一期）
我爱计算机 本文转载自公众号：CNSys
SIGOPS名人堂奖（Hall of Fame Award, HoF）是SIGOPS组织于2005年设立的奖项，用于评选一批发表10年以上对操作系统领域产生巨大影响力的文章，是系统领域至高无上的荣誉。该奖项每年评选一次，在每年系统领域顶级会议SOSP和OSDI上颁发（两会议隔年交替举办），起初两届奖项（SOSP 2005和OSDI 2006）由当年的SOSP和OSDI的程序委员会成员（Program Committees, PC）投票选出，后为减轻PC们沉重的工作负担，从2007年起成立名人堂奖项委员会，委员会成员由最近4届SOSP和最近4届OSDI的大会主席组成，以此保障奖项的公允性和含金量。
2005年作为HoF的第一届，SIGOPS组织慎重评选了4篇文章授予了该荣誉。它们分别是:
- Edsger W. Dijkstra “The Structure of the THE MultiprogrammingSystem”，SOSP'67
- Peter J. Denning “The Working Set Model for Program Behavior”，SOSP'67
- Dennis M. Ritchie and Ken Thompson “The UNIX Time-Sharing System”，SOSP'73
- Butler Lampson, “Hints for Computer System Design”，SOSP'83
这4篇文章，前两篇选自于1967年第一届SOSP会议，另两篇分别选自1973年第4届SOSP和1983年第9届SOSP，尽管奖项成立之初的初衷为了以一种追赶的方式最终达到新旧文章平分秋色的稳定状态，但由于首次评奖2005年距离第一届SOSP会议已有30多年的时间，因此直至2014年，所评选出的34篇文章中仅有5篇是1990年后发表的，故委员会也在2014年讨论重新修改评选规则，让奖项也可以关照到发表近10年左右的优秀工作。
而今天我们要介绍的第一年获奖的5位作者，每一位都可称之为计算机领域的泰山北斗，其中有4位均获得过计算机届的最高荣誉图灵奖，他们的工作也对学术界和工业界产生了巨大而深远的影响，下面我们来依次看看每一篇文章以及它们背后的故事。
Edsger W. Dijkstra
“The Structure of the THE Multiprogramming System“
Edsger W. Dijkstra
第一篇获奖文章的作者Edsger W. Dijkstra，可以算作计算机科学史上几位影响力最大的奠基人之一，无论从理论到系统工程，从Dijkstra最短路径算法，到“GOTO有害论”，再到信号量和PV原语、“哲学家就餐”问题等等，Dijkstra为计算机领域开拓了众多全新的研究方向，提出的许多概念成为当今每个计算机学科本科生耳熟能详的基础，而这篇THE多程序操作系统，是其在荷兰南部的艾恩德霍芬技术大学（Eindhoven Technical University）设计实现并发表的，系统的名称THE也是取自艾恩德霍芬技术大学荷兰文Technische Hoogeschool Eindhoven的首字母缩写。
THE多程序操作系统提出了一系列的理论和方法奠定了现代操作系统的基础，如，THE提出的多层体系结构，将操作系统划分为6层，每层负责各自的功能。处理器分配在第0层，当中断发生或定时器到期时，由该层进行进程切换，上层无需关心。第1层负责内存管理，由第1层分配进程的内存空间，进程不需考虑它运行在磁鼓还是内存。第2层负责进程与操作员控制台之间的通信。第3层管理I/O设备和相关的信息流缓冲区。第4层是用户程序层，有之下各层对于进程、内存、控制台或I/O设备管理等的封装，用户可以不用考虑这些管理细节。系统操作员进程位于第5层。
除了多层体系结构，THE还提出了同步互斥、信号量等重要思想和概念，都是如今我们所熟知的系统理论基础。THE多程序系统是针对1963/64年Dijkstra与他的同事 Carel S. Scholten 合作开发的Electrologica X8 系统而设计的，与此同时，IBM公司著名的 System/360 也是1964年发布的。这一美国人民引以为傲的跨时代产品，却并没有得到Dijkstra这一先驱的认可，他甚至在图灵奖获奖演说中直言，阅读 System 360 技术规范那段时间是他职业生涯最黑暗的一周。作为一名有才华有态度的大师，在这篇文章发表的1967年第一届SOSP会议后，他与Brian Randell 阐述了GOTO语句为程序引入复杂性的问题，受到了其建议，将此观点发表在ACM通讯（CACM），成为后来延续多年经典论战的里程碑论文“The GOTO Considered Harmful”。
1983年CACM 第25期年刊将这篇文章重新印刷发表，当时的主编评价THE多程序系统为“开启了多层系统架构的先河，也为管理大型复杂系统引入了多级模块化这一利剑”。
Peter J. Denning
“The Working Set Model for ProgramBehavior”
Peter J. Denning
第二篇获奖文章是Peter J.Denning的工作集模型（working set model），不同于Dijkstra发表THE多程序系统之前已是艾恩德霍芬技术大学教授并已名噪一时，Peter在1967年发表这篇文章的时候仅仅是一名麻省理工学院(MIT)的在读博士生，但这篇文章的价值并没有因此打折扣，甚至一经发表就引起学术和工业界强烈关注，在第二年即被 ACM Award Committee 评为1968年的最佳系统文章，并且经受住了时间的考验，成为虚拟内存管理的里程碑似的工作，也进一步印证了局部性（Locality）这一重要的系统领域设计思想。
工作集模型诞生于虚拟内存技术从概念走向实用的几年，早期程序员需要自己设计好的策略在多级存储设备之间搬运数据，给程序员带来沉重的负担，因而催生了虚拟内存这一概念，试图让程序员只需对虚拟内存进行操作，不用关心底层细节，由操作系统来完成多级存储设备的管理，这是一个非常诱人的尝试，IBM甚至专门做过实验表明虚拟内存确实可以提高程序员2到3倍的效率，而当大公司真正将这一功能实现在自己操作系统的时候，却遇到了很多意想不到的性能问题，而很快他们就意识到问题的关键在于替换策略。当上层请求的页面不在内存中，发生缺页错误而内存已满时，如何选择一个已有页面替换出去？一个低效的策略会导致频繁的I/O操作，严重影响性能，而理想的情况当然是选出在将来最长时间不会被访问的页面替换出去，而问题是，谁能预见未来？
在这个问题的驱动下，应运而生了众多替换策略，如FIFO，LRU，LFU，Random等，然而并没有一个常胜将军，而这个问题也同样吸引着年轻的博士生Peter，身处MIT在计算机领域最为辉煌灿烂的时代，兼容分时系统（Compatible Time Sharing Systme, CTSS）获得了巨大成功，而MULTICS（MULTIplexedInformation and Computing Service）刚刚启动，和所有有志青年学者一样，Peter也梦想着自己的研究成果能够辐射影响MULTICS。
在经过反复探讨和不断跌倒，Peter终于迎来了那个灵光一现的时刻，那是一个圣诞节假期，因为在家里反复踱步思考问题过于吵闹，被妻子赶出了卧室，就这样踱步到半夜，思考着所有可行和不可行的方案，突然意识到，实验数据中周期性的特征非常可能是由于不断复用之前用过的页面，那么为什么不把工作集定义为一段采样时间内使用过的页面的集合，在任一时刻t，都存在一个集合，它包含所有最近k次内存访问所访问过的页面，这个集合 w(k,t) 就是工作集。确定了这一时刻的工作集，就极有可能在下一时刻程序仍访问相同的页面，这样就可以科学的预测未来。工作集的概念将关注点从内存空间如何管理变成程序“想要”如何使用，同时也引入了时间的概念，极大的挖掘了程序局部性特性。
Dennis M. Ritchie and Ken Thompson
“The UNIXTime-Sharing System”
Ken Thompson(左) 和Dennis M. Ritchie(右)
第三个奖颁给了大名鼎鼎的UNIX系统，由Dennis M.Ritchie和Ken Thompson联合开发，说起UNIX系统的历史就不得不从MULTICS说起，对，就是Peter梦想能够辐射影响的那个MULTICS。
1965 年，麻省理工学院、贝尔实验室和美国通用电气公司一起合作，准备研发一个多用户、多任务、多层次（multi-user、multi-processor、multi-level）的超级操作系统，取名为MULTICS。但是由于目标设定过高，MULTICS项目一直都进展缓慢，最终在 1969 年被迫停止。
MULTICS项目停止后，贝尔实验室中参与项目的 Ken Thompson 也闲了下来。因为没事干了，Ken 就跑回去玩他自己写的一个叫做“星际旅行”的游戏，但是由于运行游戏的 GE-635 性能太差，所以玩起来非常不爽。这时贝尔实验室正好有一台性能好很多的 PDP-7 扔着没人用，Ken 就萌生了将游戏移植到 PDP-7 上的想法。从 1969 年起，Ken Thompson 开始为 PDP-7 开发操作系统。后来为了能早点儿玩上游戏，Dennis Ritchie 也参与了进来。
1970 年，两人实现了一个简单的操作系统，成功地将游戏移植到了 PDP-7 上。因为当时这个系统只能同时支持两个用户使用，就有人调侃他们，说你们这个东西离MULTICS差远了，就叫 Unics （UNiplexed Information and Computing Service）吧。后来，大家取其谐音，就称其为"UNIX"。
最初的 UNIX是用汇编语言写的，修改起来非常麻烦。随着对系统的不断完善，修改代码的工作量也变得越来越庞大，最终两人决定使用高级语言重写系统。他们一开始尝试使用 Fortran，后来又改用 BCPL，但始终觉得不够满意。既然现有的编程语言无法满足需要，那就自己创造新的语言。于是两人先改良 BCPL 创造出了 B 语言，再后来 Dennis 又进一步改进 B 语言，创造出了 C 语言，最后两人用 C 语言重写了第三版UNIX。
虽然说“有心栽花花不开，无心插柳柳成荫”，但MULTICS项目本身为UNIX系统做了许多非常有意义的探索，为UNIX系统的成功打下了坚实的基础，同时MULTICS也为系统界培养了一批如Ken Thompson这样优秀的人才，也是UNIX能够成功的前提。
Butler Lampson
“Hints for Computer System Design”
Butler Lampson
最后一个获奖文章的作者是ButlerLampson，这篇文章发表于1983，距今已有30多年，然而文章提出的系统设计经验至有仍很大的借鉴意义。这些经验涉及接口的设计与实现、系统的性能与容错等方面。
接口设计是系统设计中最重要的一部分，通常也是最难的一部分。文章提出接口设计需要考虑接口的简单、完整和高性能。为了保证高效的实现，可以采取分而治之将大问题化分成小问题来解决，并且尽可能地复用已有功能。资源利用率和性能通常是一对矛盾。对于设计系统而言，避免出现性能灾难比找寻最优的资源分配方案更加重要。想要保证系统的可靠性并不是一件很难的事情，但是提高已有系统的可靠性却非常困难，所以可靠性最好在系统设计之初就考虑进来。文章将所有的经验总结成了如下的表，帮助所有做系统设计的人在简单性、一致性、正确性和完整性之间做权衡。
系统设计经验列表
同样Butler也是一位兴趣广泛的计算机科学领域先驱，本科在哈佛读的是文科，毕业后进入加州大学伯克利分校物理系，由于对当时伯克利正在研发的商用系统SDS-940抱有极大的兴趣，主动争取进入该项目，最后转入计算机这一新兴领域。Butler一生在硬件、软件、程序设计语言、计算机应用、网络等诸多领域皆有建树，而其中最重要的一个成果可能就是Alto，世界上首台个人计算机系统。它是当时最先进的计算机系统，有一系列的新构思、新创造、新发明、新部件，其中最主要的是有高分辨率的全屏图形系统，在世界上首先实现了图形用户界面，打破了传统的只能用字符实现人机交互的限制，开创了计算机历史上有重大意义的新的一页。
小结
纵观第一届获奖的四篇文章，不仅仅因为其为系统领域贡献了里程碑似的工作，同时也为整个系统领域的发展引入了一批革命性的思想，如简单性、局部性、多层次模块化等，正是这样一批前人智慧凝练出来的系统设计哲学，指导着无数后来者在系统领域不断披荆斩棘，开拓创新。我们将在下一期为大家继续介绍第二届的获奖文章以及背后的故事。
作者
王卅，中国科学院计算技术研究所，助理研究员，主要研究方向为云计算、虚拟化、分布式系统等。
李文捷，中国科学院计算技术研究所，博士生，主要研究方向为资源管理、分布式系统、性能调优等。
参考文献：
[1] https://www.sigops.org/award-hof.html
[2] https://conservancy.umn.edu/handle/11299/107247
[3] http://doi.acm.org/10.1145/1141880.1837132
[4] http://www.ituring.com.cn/article/197925
[5] http://blog.sciencenet.cn/blog-1225851-841800.html
[6] https://en.wikipedia.org/wiki/Butler_Lampson
[7] https://en.wikipedia.org/wiki/Ken_Thompson
[8] https://en.wikipedia.org/wiki/Dennis_Ritchie
[9] https://en.wikipedia.org/wiki/Edsger_W._Dijkstra
[10] https://en.wikipedia.org/wiki/Peter_J._Denning
