ACM SIGOPS名人堂（第九期）
我爱计算机 本文转自CNSys
在本期SOSP名人堂中，作者将向大家介绍2013年当选的四篇文章，它们分别是：
- “Tenex, A Paged Time Sharing System for the PDP-10”
- “Distributed Snapshots: Determining Global States of a Distributed System”
- “A NonStop Kernel”
- “Exploiting Virtual Synchrony in Distributed Systems”
这四篇文章中，第一篇发表在1972年的“Communications of the ACM”，第二篇发表在1985年的“ACM Transactions on Computer Systems”，第三篇和第四篇分别选自第8届（1981年）和第11届（1987年）SOSP。下面我们依次对各篇文章进行简单的回顾。
“Tenex, A Paged Time Sharing System for the PDP-10”
Daniel G. Bobrow（左）, Daniel L. Murphy（中） and Raymond S. Tomlinson（右）
第一篇文章是由Daniel G. Bobrow, Jerry D. Burchfiel, Daniel L. Murphy 以及 Raymond S. Tomlinson共同完成的TEXEX。TENEX是一个新的分时系统，实现在由BBN开发的特殊分页硬件增强的DEC PDP-10上。它包括一个完整的虚拟内存系统，也就是说，程序不仅可以访问完整的内存空间，而且每个程序可以同时进行这样的访问。分页系统将像往常一样处理映射，根据需要将数据拷贝到后备存储或者从后备存储中拷贝出来。唯一需要改变的是分页器能够在RAM和存储之间维持多组映射，每组对应于一个正在使用系统的程序。TENEX的一个显着特点是其面向用户的命令行解释器。不同于那个时代的典型系统，TENEX故意使用长命令名称，甚至包括非重要噪声字，以进一步扩展命令。
本文描述了TENEX的设计和实现是如何实现一些对所有分时系统都很重要的目标的，包括详述一个强大的多进程大内存虚拟机，无隙的终端交互，全面的统一的文件和I / O功能，以及清晰灵活的系统结构。
本文的第一作者Daniel G. Borrow曾是美国人工智能协会（Association for the Advancement of Artificial Intelligence, AAAI）的主席，人工智能（Artificial Intelligence）杂志的主编，ACM研究员和AAAI研究员。因为他在Interlisp上的工作，他分享了1992年的ACM软件系统奖。Interlisp是一个基于Lisp编程语言的编程环境，1966年开始开发，1970年完成。它成为斯坦福大学和DARPA社区其他地方的AI研究人员中流行的Lisp开发工具。Interlisp原本叫BBN LISP，在1973年，当Daniel G. Borrow和Warren Teitelman以及Ronald Kaplan 从BBN到了Xerox PARC之后, 它被改名为Interlisp。Borrow于2017年3月份去世，享年82岁。
美国国防部高级研究计划局（Defense Advanced Research Projects Agency，DARPA ）是美国国防部的一个机构，负责开发新兴技术供军事用途。最初被称为高级研究计划署（Advanced Research Projects Agency，APRA）。DARPA资助的项目带来了许多重要的技术，影响了许多非军事领域，如计算机网络和现代互联网的基础，以及信息技术中的图形用户界面。
本文的第三作者Daniel L. Murphy在1965年加入了BBN。1972年10月，他作为承包人加入了数字设备公司（Digital Equipment Corporation，DEC），负责把TENEX移植到PDP-10系列的KI10型号上。1973年1月2日，他作为正式员工加入DEC，领导开发TOPS-20操作系统。
本文的第四作者Ray Tomlinson是国际知名的公认的电子邮件的发明者。他于1971年在因特网的前身阿帕网上实现了第一个电子邮件项目，这是第一个能够在连接到ARPANET的不同主机上的用户之间发送邮件的系统，在这之前，以前，邮件只能发送给使用同一台电脑的用户。为了实现该系统，他使用@符号将用户名和其机器名分开，自此，该方案一直用于电子邮件地址。Tomlinson于2016年3月去世，享年75岁。
“Distributed Snapshots: Determining Global States of a Distributed System”
Leslie Lamport
文本是由Mani Chandy 与 Leslie Lamport共同完成的，提出了一种用于在分布式系统中记录异步系统的一致全局状态的快照算法。该算法以两个作者的名字命名，称为Chandy-Lamport算法。
据Leslie Lamport的网站称，“这里描述的分布式快照算法是在我访问当时在德克萨斯大学奥斯丁分校的Chandy时诞生的。他在晚饭时向我提出了这个问题，但是我们两个当时都喝了太多的葡萄酒，没办法思考合适的解决办法。第二天早晨，在洗澡时，我想出了解决办法。当我到达Chandy的办公室时，他正在用相同的解决办法等着我。“
分布式系统的许多问题可以归于检测全局状态的问题。例如稳定性检测（stable property detection）和检查点（checkpointing）。
算法的假设如下：
- 没有故障，所有的消息到达的时候都是完整的但只有一次
- 通信信道是单向的，先进先出
- 在系统中的任何两个进程之间都有通信路径
- 任何进程都可以启动快照算法
- 快照算法不会干扰进程的正常执行
- 系统中的每个进程记录其本地状态和传入信道的状态
该算法使用标记消息工作。想要启动快照的进程记录其本地状态，并在其每个传出信道上发送一个标记。所有其他进程，在接收到一个标记后，会记录它们的本地状态，把标记传入信道的状态记为空，并在其所有的传出信道上发送标记消息。如果一个进程在记录了其本地状态之后接收到一个标记，那么它将标记传入信道的状态记录为它从首次记录其本地状态以来接收到的所有消息的序列。
算法的工作原理如下：
1.观察者进程（进程拍摄快照）：
- 保存自己的本地状态
- 向所有其他进程发送带有快照令牌的快照请求消息
2.在任何消息上首次接收快照令牌的进程：
- 向观察者进程发送自己保存的状态
- 将快照令牌附加到所有的后续消息上（以帮助传播快照令牌）
3.当已经接收到快照令牌的进程接收到不携带快照令牌的消息时，此进程会将该消息转发给观察者进程。该消息显然是在快照“切断”之前发送的（因为它不带有快照令牌，因此必然来自快照令牌发送之前），并且需要包含在快照中。
基于此，观察者建立了一个完整的快照：保存了每个进程的状态以及所有“在以太网”中的消息。
本文的第一作者K. Mani Chandy曾为霍尼韦尔和IBM工作，也曾担任过包括IBM和贝尔实验室在内的众多公司的顾问。他还是美国国家工程院院士。在该算法发表的前一年，也就是1984年，他和J Misra一起提出了一个解决哲学家就餐问题（Dining philosophers problem）的新方法。他出版了三本书和一百多篇关于分布式计算、并行程序验证、并行编程语言以及包括同名BCMP网络在内的计算和通信系统性能模型的论文。
本文的第二作者Lamport相信大家已经非常熟悉了。三次入选SIGOPS，大家可以在第二期中看到详细介绍。
“A NonStop Kernel”
本文的作者是Joel F. Bartlett，描述了NonStop操作系统内核的关键原语（primitive）。用这些原语描述了一个允许容错的资源接入的机制，进程对（process-pair）。
NonStop是由天腾电脑公司（Tandem Computers, Inc.）于1976年推出的一系列服务器计算机，从NonStop 产品线开始，其后是惠普Integrity NonStop 产品线扩展。NonStop系统是一个容错的、可扩展的、专为在线交易处理而设计的分布式计算机系统。由于NonStop系统是基于集成的硬件/软件堆栈，所以惠普还为他们开发了一种特殊的操作系统：NonStop OS。NonStop系统经常被银行，证券交易所，电信提供商和其他需要极高运行时间的企业使用。
Tandem的NonStop系统在一定程度上是自我修复的。它使用多个独立的相同处理器和冗余存储设备和控制器，以在硬件或软件故障的情况下提供自动高速“ 故障转移 ”。
NonStop系统具有大规模并行处理（MPP）架构，并提供线性可扩展性。每个CPU（系统可以扩展到多达4000个CPU）运行自己的操作系统副本。
传统的多计算机系统都使用共享存储器并直接在共享数据对象上工作。但是NonStop是一个“无共享”架构，这种“无共享”的安排也被称为松散耦合的多处理。除了处理故障之外，这种“无共享 ”的消息传递系统的设计也极大地适应了商业对于高负载的需求。处理器总数每增加一倍会让系统吞吐量翻番，最多达到4000个处理器的顶配。相比之下，传统的多处理器系统的性能受到某些共享存储器，总线或开关的速度的限制。增加超过4到8个处理器也不会再提升系统速度。尽管是由较简单的小型计算机技术构建，NonStop能够很好地与IBM最大的大型机竞争。
天腾电脑公司于1974年在加州Cupertino成立。该公司在1976年发布了第一代NonStop，1981年发布了NonStop II，1986年发布了第三代通用CPU，NonStop VLX，并于同年发布了第一款容错的SQL数据库，NonStop SQL。它在1997年之前一直是一个独立的公司，在97年被康柏（Compaq）收购成为该公司旗下的服务器部门。2002年康柏又被惠普（HP）公司收购。现在，NonStop成为了HP的产品。
Joel F. Bartlett一直参与NonStop的开发。除了这篇文章外，他于1978年作为唯一作者发表了 “A NonStop Operating System”，于1987年以第一作者身份发表了“Fault Tolerance in Tandem Computer Systems”。
“Exploiting Virtual Synchrony in Distributed Systems”
Kenneth P. Birman and Thomas A. Joseph
这篇文章描述了用于分布式编程的虚拟同步环境的应用，这是ISIS2系统中分布式编程工具集的基础。虚拟同步环境允许进程被组织为进程组，使诸如广播到组的事件成为一个实体，组成员变化，甚至一个活动从一个地方迁移到另一个地方似乎会立即发生。 换句话说，是同步地发生。这种方法的主要优点是分布式应用程序的许多方面可以被独立处理，而不会影响正确性。而且，在假设是同步系统的基础上设计的用户代码通常可以并行执行。作者表明，这种方法在构建分布式和容错软件时比其他方法更直接，更灵活，更有可能产生正确的解决方案。
ISIS项目和该研究的提出是因为当时的软件开发方法不足以应对分布式系统应用的开发需求。该研究旨在为分布式编程提供一个工具包，以帮助解决分布式系统中最常见的子问题。在本文中提到的子问题有流程组和组通信，决定如何回应请求，并发，同步，复制数据，检测和响应故障，动态重新配置，稳定存储，恢复，事务，保护，一致性。每个子问题都对应了ISIS2中的一个单独工具。
设计工具包的关键问题是确保这些工具的功能是正交的，因为正是这一点允许程序员将应用程序分解成可以独立解决的组件，再逐渐将组件扩展成一个完整的系统。
本文的第一作者Birman是ACM 和IEEE 会士，他还是1993-1998年间ACM Transactions on Computer Systems的主编。Birman以开发ISIS工具包而闻名。他后来建立了Isis Distributed Systems使得该软件商业化，用于证券交易所、空中交通管制和工厂自动化。Isis软件在纽约和瑞士证券交易所运作了十多年之久，且仍应用在法国空中交通管制系统和美国海军AEGIS军舰上。本文的第二作者Joseph是Birman的第一个博士生。
作者
郭莎莎，国防科技大学计算机系，硕士生，研究方向为计算机系统结构。
参考文献
[1]https://en.wikipedia.org/wiki/NonStop_(server_computers)
[2]https://en.wikipedia.org/wiki/Tandem_Computers
[3]https://en.wikipedia.org/wiki/Daniel_Murphy_(computer_scientist)
[4]http://www.cs.cornell.edu/ken/
[5]https://en.wikipedia.org/wiki/Ray_Tomlinson
[6]https://en.wikipedia.org/wiki/Daniel_G._Bobrow
[7]https://en.wikipedia.org/wiki/Ken_Birman
[8]https://en.wikipedia.org/wiki/K._Mani_Chandy
[9]https://en.wikipedia.org/wiki/Chandy-Lamport_algorithm
[10]https://en.wikipedia.org/wiki/Leslie_Lamport
[11]https://www.linkedin.com/in/thomasajoseph/
[12]https://en.wikipedia.org/wiki/DARPA
