ACM SIGOPS名人堂（第五期）
我爱计算机 本文转自 CNSys
在本期SOSP名人堂中，作者将向大家介绍2008年的最后一篇以及2009年的当选文章，它们分别是：
- The Multics Virtual Memory: Concepts and Design
- Leases: An Efficient Fault-Tolerant Mechanism for Distributed File Cache Consistency
- Experience with processes and monitors in Mesa
- VAXclusters: A Closely-Coupled Distributed System
这四篇文章中，第一篇于2008年被选入SOSP名人堂，发表于1996年第二届OSDI会议。之后的三篇都是2009年入选的，分别发表在1989年第十二届、1979年第七届及1985年第十届的SOSP会议。这些工作都对学术界和工业界产生了巨大而深远的影响，下面我们来依次看看每一篇文章以及它们背后的故事。
“The Multics Virtual Memory: Concepts and Design”
Andre Bensoussan
第一篇获奖文章的第一作者是Andre Bensoussan，曾在剑桥的霍尼韦尔从事Multics操作系统的研究工作。Andre及其他成员对Multics文件系统进行重大改变，实现了一个小型虚拟内存管理器。据同事回忆，Andre用铅笔而非终端完成了图表设计和代码编写，在输入终端进行编译时只出现了三个拼写错误，改正后便编译通过，并且程序运行完美。Andre在Multics操作系统的文件管理、初始化等方面做出了很多工作，完成了4篇论文、20个MTB、1个资料库和14个MSPM部分。
这篇文章讨论了Multics操作系统中分段和共享的设计与实现。在此之前，几个知名的系统已经实现了大的虚拟存储器，允许执行超过可用核心存储器大小的程序。Atlas计算机中的分页允许程序在物理上被划分为页面，只有一部分页面需要驻留在核心存储中。B5000计算机中的分段允许程序被逻辑分割，只有其中一部分段需要在驻留在核心存储中。霍尼韦尔645和IBM 360/67中分段和分页相组合，当程序运行时只有几页的几个片段需要在核心中驻留。然而，随着远程访问和多程序系统的经验逐渐积累，除了能够利用大型虚拟存储器实现大量信息的直接寻址之外，许多应用程序还需要迅速而有控制地共享存储在中央设备的信息。
文章指出，通过满足两个设计目标，可以为在线信息的直接访问和共享提供基础。首先，存储在系统中的所有在线信息必须可由处理器直接寻址；其次，必须能够控制对所有可访问信息的访问。直接可寻址的根本优点是信息复制不再是强制性的。由于系统中的所有指令和数据都是处理器可直接寻址的，因此不需要复制过程和数据。同时必须能够限制或控制对这些信息的访问，以实现计算过程自发事故的自我保护和使用相同的系统硬件设施的计算过程间的相互保护。因此，需要在可直接寻址的存储器中划分或封装所有信息，并且附加访问属性，以描述每个用户可以引用数据和过程的方式。在Multics中，段是直接寻址并以受控方式访问的信息包，与每个段相关联的是可以访问段的每个用户的一组访问属性。这些属性在任何用户对每个段引用时由硬件进行检查。此外，Multics中的所有在线信息都可以直接引用为段，而在其他系统中，大多数在线信息被引用为文件。
尽管早期的论文已经对Multics虚拟内存的概念层面或其早期形式等方面进行了讨论，但是这篇文章介绍的实现方式有效地实现了设计目标。文章提出的动态链接，灵活虚拟内存，设计安全性，分级文件系统等想法在现代操作系统中广泛使用。
“Leases: An Efficient Fault-Tolerant Mechanism for Distributed File Cache Consistency”
Cary G. Gray(左)和David R. Cheriton (右)
第二篇获奖文章的作者是Cary G. Grayz和David R. Cheriton。Cary G. Grayz现执教于伊利诺伊州惠顿学院数学与计算机科学系。David R. Cheriton是加拿大计算机科学家、数学家、慈善家和风险投资家，是斯坦福大学的计算机科学教授，创立并领导了分布式系统课题组。他已经创立并投资了多家技术公司，是Google的第一批投资者，Vmware的早期天使投资者，Arista的联合创始人兼首席科学家。截至2016年2月，Cheriton资助了至少20家公司，估计净值为34亿美元，在“福布斯”富豪榜中位列加拿大第13位，世界第62位。Cheriton为教育做出了慷慨的贡献，捐助2500万美元用于支持滑铁卢大学计算机科学学院的研究生和课题研究，向不列颠哥伦比亚大学捐赠750万美元作为计算机科学系的研究生奖学金和本科生奖学金，2016年捐赠1200万美元给斯坦福大学。
文中工作面对的是Cache引入的缓存与主存储之间的数据一致性问题。在共享内存多处理器架构的工作中已经广泛研究了缓存一致性协议，这项协议依赖于系统总线提供的可靠且同步的广播通信。然而，在分布式系统中可能会遇到一些新故障：主机可能会崩溃或丢失消息。原有的文件一致性方法分为两类：一类基于广播可靠的假设，因此不能容忍通信故障；另一类需要对每次读取进行一致性检查，因此无法提供良好的性能。
本文提议将lease作为使用物理时钟来处理主机和通信故障的一致性协议，lease是资源序列化锁的替代，它允许持有人在有限时间内为某些资源提供指定的权利。使用V系统文件访问特性的分析模型进行评估的结果表明，考虑容错的要求，lease仍能为大型系统提供接近最优的一致性效率。Lease是一个通信和协调机制的实例，除文件缓存一致性外还有其他应用，文章也将这种一般方法应用于其他领域，包括分布式事务管理协议和传输协议，这种机制的使用在分布式系统具有很大潜力。
Lease通常用于分布式系统中从DHCP地址分配到文件锁定的各类应用程序，但它本身不是一个完整的解决方案。首先，必须有一些通知lease持有人到期的方法，并阻止该持有人继续依赖该资源。通常要求所有请求都附有访问令牌，如果相关联的lease已过期，则该访问令牌无效。此外，如果lease持有人已经开始在资源上运行，而后撤销lease，撤销可能会使资源处于受损状态。在这种情况下，通常使用Atomic事务来确保不完成的更新不产生影响。
Gray和Cheriton这篇论文中分析的lease机制已经成为管理分布式高速缓存的最广泛机制之一。 本文对lease语义的仔细分析，详尽实验以及对容错问题深思熟虑的讨论特别引人注目。
“Experience with processes and monitors in Mesa”
Butler W. Lampson
第三篇获奖文章的第一作者Butler W. Lampson是美国计算机科学家，致力于开发和实现分布式个人计算，是Microsoft的技术研究员和麻省理工学院的兼职教授。1992年，他因为在个人计算机和计算机科学方面的贡献而获得ACM图灵奖。1994年被选为ACM会士，2001年获得IEEE约翰·冯·诺依曼奖章，2004年与Alan C. Kay，Robert W. Taylor和Charles P. Thacker一起因为在Alto的工作而获得Charles Stark Draper奖。2006年，因为在网络个人工作站、操作系统、计算机安全和文本格式化等计算机科学领域做出的基础性贡献，他被选为计算机历史博物馆成员。
Lampson经常被引用的名言是“计算机科学中的任何问题都可以用另一个间接的方式来解决”，不过在1993年的图灵奖讲座中，他把这句名言归功于David Wheeler。
这篇论文发表时，Lampson在Xerox 公司的PARC子公司工作，Xerox位于加利福尼亚州，在信息技术和硬件系统方面做出了卓越的贡献。作为Xerox公司成立于1970年的部门，PARC一直负责激光打印、以太网、现代个人电脑、图形用户界面、桌面范例、面向对象编程，普适计算和非晶硅应用等工作，并推进了半导体的大规模集成（VLSI）。
文章的工作基于Mesa语言和作者及所在团队此前已着手设计的个人计算机新操作系统Pilot，着重解决在已发表的监视器工作中没有明确解决的以下问题：程序结构，创建进程，创建监视器，嵌套监视器中的WAIT调用，异常，调度和I/O。论文中讨论了一套功能完备的语言特征，实现当时个人计算机上唯一的软件并发机制，可处理从不相关应用程序中的I/O中断到协作资源共享的情况。
在当时的编程语言会议和操作系统教科书中，监视器已经成为选择的同步方法。本文首次仔细观察了在大型生产系统中使用监控器时出现的实际问题。这些问题仍然存在，事务记忆机制的研究人员应当认真地重读这篇精彩的论文。
“VAXclusters: A Closely-Coupled Distributed System”
Henry M. Levy (左)和William D. Strecker(右)
第四篇文章的第一作者是Nancy P. Kronenber。第二作者Henry M. Levy是一名计算机科学家，是NAE院士，也是ACM和IEEE会士。Levy的研究涉及操作系统、分布式系统、互联网和计算机体系结构。在早期的职业生涯中，他曾在DEC工作，参与了VAX计算机VMS操作系统的设计实现。他于1983年加入华盛顿大学计算机科学与工程系，现任该部门主席，参与了几个早期的面向对象的分布式系统（Eden和Emerald），提出了同时多线程。Levy参与创立了两家创业公司Performant和Skytap。第三作者William Daniel Strecker是一名计算机工程师，是数字设备公司VAX的首席架构师。他是VAX小型机系列的主要架构师，还参与了PDP-11/70中缓存存储的开发。Strecker在DEC工作了28年，1985年以来陆续担任公司战略与技术高级副总裁。之后，他在康柏（Compaq）担任同一职务。2000年，他成为风险投资公司旗舰风险投资公司的合伙人和首席执行官。Strecker是NAE院士和ACM会士，1985年获得了华莱士麦克道尔奖。
VAXcluster是作为单个系统运行的VAX计算机的高可用性和可扩展配置。为了在多计算机环境中实现性能，设计了一种结合通信硬件和分布式软件的新通信架构，软件是分布式版本的VAX / VMS操作系统，使用分布式锁管理器来同步对共享资源的访问；硬件包括70Mb/s消息导向互连和执行传统上由软件处理的通信任务的互连端口。性能测量表明，该结构具有高效性，例如能够在VAX-11/780上每秒发送和接收3000条消息。VAXclusters的主要目标是开发由标准处理器和通用操作系统构建的可用且可扩展的多计算机系统。分布式软件、通信协议和硬件的联合设计获得了很大的成就。设计时一个重要的简化方面是使用分布式锁管理器进行资源同步。通过这种方式，诸如文件系统的较高级别服务不需要特殊代码来处理分布式环境中的共享。文中提供的性能测量表明VAXcluster系统在很大程度上成功实现了高效的通信架构。
VAXcluster是第一个支持分布式文件系统和分布式锁定服务等基本功能的现代集群系统。关于VAX集群的SOSP论文如今仍然是一个经典。VAXclusters是巨大的商业成功，并为今天的大型数据中心奠定了基础。
小结
纵观第五届获奖的四篇文章，为系统领域所贡献的都是实践性强且影响长远的工作，提出的理念在如今的操作系统设计中仍被广泛借鉴。Multics是一个主机时间共享操作系统，始于1965年，直到2000年，后续计算机操作系统主要受它影响；lease机制已经成为管理分布式高速缓存的最广泛使用的机制之一；在大型生产系统中使用监控器时出现的实际问题仍然存在；VAXcluster是第一个支持分布式文件系统和分布式锁定服务等基本功能的现代集群系统，为今天的大型数据中心奠定了基础。正是这些前辈用智慧和实践总结出来的科研经验，指引着更多的后来者在系统领域的不断探索，不断创新。我们将在下一期介绍第六届的获奖文章及其背后的故事。
作者
张诗情，国防科技大学计算机系，硕士生，研究方向为计算机体系结构、异构并行。
参考文献
[1] https://www.sigops.org/award-hof.html
[2] http://multicians.org/andre.html
[3] http://www.eecs.harvard.edu/~margo/cs261/notes/bensoussan-1972.html
[4] http://cs.wheaton.edu/~cgray/
[5] https://en.wikipedia.org/wiki/David_Cheriton
[6] https://en.wikipedia.org/wiki/Lease_(computer_science)
[7] https://en.wikipedia.org/wiki/Butler_Lampson
[8] https://en.wikipedia.org/wiki/PARC_(company)
[9] https://en.wikipedia.org/wiki/Hank_Levy_(computer_scientist)
[10] https://de.wikipedia.org/wiki/William_D._Strecker&prev=search
[11] http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.74.727&rep=rep1&type=pdf
