ACM SIGOPS名人堂(第十期)

本文转自CNSys

在本期SOSP名人堂中,作者将向大家介绍2013年的最后一篇以及2015年当选的三篇文章,它们分别是:

  1. The Click Modular Router.
  2. A virtual machine time-sharing system
  3. On the criteria to be used in decomposing systems into modules
  4. On optimistic methods for concurrency control

 “The Click Modular Router”

Eddie Kohler,Robert Morris and Frans Kaashoek

本期介绍的第一篇文章是由Eddie Kohler, Robert Morris, Benjie Chen, John Jannotti和Frans Kaashoek五人共同撰写的“The Click Modular Router”。这篇文章提出了一个开放的、可扩展的、可配置的路由器框架——Click。在此之前,大多数路由器的设计都是封闭而不灵活的,网络管理员和第三方软件供应商难以扩展具有新功能的路由器。Click是一种新的软件体系结构,它被用于建立灵活而可配置的路由器。Click路由器集成了许多被称为element的分组处理模块。每个element实现一个简单的路由功能,例如对分组进行分类、排队、调度,以及与网络设备实现连接等。一个路由器的配置就是一张element位于顶点处的有向图;分组沿着图中的边进行传送。一些特性使element功能更加强大,并且更容易编写复杂的配置,包括pull连接和基于流的路由器上下文(flow-based router context)。模块化的Click配置易于扩展,扩展IP路由器以支持复杂排队或差异化服务只需要在合适的地方添加和重新排列几个element。同时,Click这种模块化和灵活的架构也拥有良好的性能。

Click定义了一个用于构建具有不同服务和属性的网络路由器的简单、模块化且高效的框架。自本文发表以来,Click已经成为网络和系统研究社区的一个基本工具, 有几十个甚至数以百计的系统和论文建立在Click的基础上,这其中也包括数个成功的商业系统。

本文的第一作者Eddie Kohler是一名致力于网络和操作系统的计算机科学家,目前是哈佛大学工程与应用科学学院的计算机科学教授。在此之前,Eddie是加州大学洛杉矶分校的教授。第二作者Robert Morris和第五作者Frans Kaashoek是Eddie Kohler的两位博士生导师。

Eddie于2000年同他人共同创立了Mazu Networks公司并担任首席科学家, 2009年该公司被收购。2006年,33岁的Eddie进入了MIT技术评论杂志发表的年度TR35名单,该名单代表世界前35名35岁以下的创新者。2013年Eddie获得了SIGOPS Mark Weiser奖。Eddie也是HotCRP会议管理软件的作者,目前HotCRP会议管理软件被用于所有的USENIX会议以及许多ACM SIGCOMM和SIGPLAN会议。

“A virtual machine time-sharing system”

本期介绍的第二篇文章是来自R. A. Meyer和L. H. Seawright的“A virtual machine time-sharing system”。文章介绍了首个虚拟机系统CP/CMS的第二代CP-67/CMS。CP-67/CMS是一种多访问系统,它管理用于分时的计算机的资源,使得每个远程用户似乎掌握着完整而专用的计算机。该概念被称为虚拟机,并且允许每个用户选择他希望运行的操作系统。

在上世纪60年代末至70年代初,IBM剑桥科学中心开发出了具有标志性意义的分时虚拟机操作系统CP/CMS,开启了分时操作系统的发展之旅。CP/CMS拥有3个版本,分别是CP-40/CMS、CP-67/CMS以及CP-370/CMS。此首个虚拟机系统最初建于1966年,用于具有自定义虚拟内存硬件的IBM 360/40,然后移植到具有内置虚拟内存的360/67。这个系统拥有一个虚拟机监视器CP,以及一个深受CTSS影响的单用户交互式系统CMS;为了支持多个用户,系统为各个用户在单独的VM中运行CMS。得益于360清晰的架构,CP可以完美地虚拟化硬件(除了时序依赖性和自修改通道程序),而无需进行二进制转换(尽管它需要翻译通道程序)。CP/67之后演变成了VM/370,成为IBM主机的主要分时系统,为此后的系统(比如z/VM)保持多用途、高性能奠定了基础。

(备注:  图片来自于  https://en.wikipedia.org/wiki/CP/CMS)

CP/CMS虚拟机概念的提出是操作系统设计中非常重要的一步。通过隔离用户,CP/CMS可以显著提升系统的可靠性和安全性;通过为每个用户模拟一个完整而独立的计算机,CP/CMS可以在分时环境中运行任何一个S/360软件;通过使用轻量级的CMS作为用户接口,CP/CMS实现了前所未有的分时性能,此外,简单的CMS相比于传统操作系统更有助于改进用户接口。

“On the criteria to be used in decomposing systems into modules”

David. L. Parnas

本期介绍的第三篇文章是来自David. L. Parnas的“On the criteria to be used in decomposing systems into modules”。这篇论文首次提出了信息隐藏的概念,截止目前被引用次数达到6131,其地位和重要性不言而喻。这篇文章介绍了一种将一个复杂的系统分解为模块的技术。文章提出,模块化的有效性取决于将系统分为模块所使用的标准。这篇论文通过一个简单的例子,表明现在被称为“信息隐藏”的模块化要优于就软件工程生命周期而言更为明显的模块分解,提出可以通过最小的性能开销去实现最有益的分解。

在计算机科学中,信息隐藏是对计算机程序中最有可能改变的设计决策进行隔离的原则,从而当设计决策发生变化的时候,信息隐藏能够保护程序的其他部分不需要被大量修改。这种保护包括提供一个稳定的接口。换句话说,信息隐藏是利用编程语言特性(如私有变量)或显式的导出策略,来避免类或软件构件的某些部分被其客户端访问的能力。通常,信息隐藏与封装可互换使用。信息隐藏的常见用途是隐藏数据的物理存储布局,从而当布局发生变化的时候,所要做的更改仅限于整个程序的一小部分。在面向对象程序设计中,信息隐藏将代码对不确定的实现(也即设计决策)的依赖,转移到一个定义明确的接口上,从而降低软件开发风险。接口的客户端完全通过接口来执行操作,即使接口的实现改变了,客户端也不必做出更改。这篇文章提出的信息隐藏方法对软件工程领域(包括操作系统、分布式系统、数据库和编程语言)产生了很大的影响。

David Parnas教授是软件工程界知名的学者和先驱,是模块化编程中信息隐藏概念的创始人,为面向对象程序设计的发展奠定了基础。Parnas教授先后在卡耐基梅隆大学、北卡罗莱纳大学Chapel Hill分校、德国达姆施塔特工业大学等任教。在20世纪80年代中期,Parnas公开反对美国战略防御计划(也称为“星球大战”),他认为编写一个可信任的能防止核攻击的高质量应用程序是不可能的。Parnas教授对于学术评估方法也有着自己的立场,他同其他一些科学家一起公开批评用基于出版数量的方法来评价学术成果的方式。 在Parnas教授2007年写的一篇名为“top the Numbers Game”的文章中,他详细阐述了为什么目前在全球各个大学广泛使用的基于数量的学术评估体系(无论是面向出版物的数量还是各出版物的引文数量)是有缺陷的,认为这种评估体系会导致知识的停滞,而不是带来更多的科学进步。

“On optimistic methods for concurrency control”

H. T. Kung (中文名: 孔祥重)

本期介绍的最后一篇文章是来自H. T. Kung和John T. Robinson的“On optimistic methods for concurrency control”。这篇论文首次提出了乐观并发控制的概念,在不锁定要访问的数据项的情况下进行事务处理,主要依赖事务备份作为控制机制,期望事务之间不会发生冲突。

乐观并发控制是一种应用于事务系统的并发控制方法,如关系数据库管理系统和软件事务内存。在运行时,事务使用数据资源,但不上锁。在提交之前,每个事务都要进行验证,检查其他事务是否修改了此事务已使用(读或写)的数据。如果验证结果表明发生了有冲突的修改,则回滚提交的事务并重新开始。如果没有冲突,则使所有更改生效。

乐观并发控制通常用于数据竞争较少的环境中。当冲突很少时,由于事务可以在无需管理锁的开销以及无需等待其他事务释放锁的情况下完成,从而使乐观并发控制具有比其他并发控制方法更高的吞吐量。但是,如果数据资源争用频繁,反复重启事务会极大地降低性能。

乐观并发控制,这个最初在传统数据库背景下引入的想法,在事务被应用于通用系统时就被证明是非常强大的。乐观并发控制是许多事务内存和数据库实现的核心原理,包括Google App Engine和Ruby on Rails的数据管理协议。

这篇获奖文章的第一作者是H. T. Kung,中文名是孔祥重,美籍华人计算机科学家,美国国家工程院院士,台湾中央研究院院士。1968年获得清华大学数学学士学位,1974年获得卡耐基梅隆大学博士学位并留校任教,1992年加入哈佛大学,是计算机科学与电气工程的William H. Gates Professor。Kung还是哈佛“信息,技术与管理博士”计划的联合主席。Kung的贡献包括:收缩阵列;iWarp;乐观并发控制;Read-Copy-Update;贪婪周边无状态路由;一种避免通信的最优分布矩阵乘法算法;Kung-Traub算法等。

小结

本期介绍的四篇获奖文章均为系统领域中影响深远的工作。Click框架已经成为网络和系统研究社区的一个基本工具;分时虚拟机操作系统CP/CMS开启了分时操作系统的发展之旅;信息隐藏方法对软件工程领域产生了很大的影响,为面向对象程序设计的发展奠定了基础;乐观并发控制是许多事务内存和数据库实现的核心原理(如Google App Engine)。正是前辈们这些优秀而创新的科研工作与思想,让后来者能够站在前人肩膀上不断探索,继续前行。在下一期SIGOPS名人堂中,我们将继续为大家介绍2015年入选的部分论文及其背后的故事。

作者

刘心馨,华中科技大学武汉光电国家实验室,博士生,研究方向为计算机系统结构和存储系统。

转载请注明:《 ACM SIGOPS名人堂(第十期) | 我爱计算机