链接：https://pan.baidu.com/s/15EEL0lZrCigURhDAEfB_nA 

提取码：t8au 

 

第一章：共享内存和烘焙算法 兰波特在20世纪70年代和80年代的有影响力的作品是在并行编程的基本问题没有得到 很好的理解的时候出现的。 第一章，由HagitAttiya和JenniferL。 韦尔奇，从开创 性的烘焙算法[Lamport1974a]开始解决“互斥”，这是多处理器编程中的一个基本要 求。 在开发了Bakery算法之后，Lamport将其作为一种工具，用于形式化许多概 念，从而促进对并发程序的推理。 本章进一步涵盖了兰波特在研究烘焙算法时发 展起来的相关概念。 当时已知，正确的执行可能需要并行活动，以便在操作相同数据的“关键部分”期 间相互排除，以防止不希望的操作交织。 相互排斥问题起源于EdsgerDijkstra的开创 性工作，其中包括

4 导言 他的解决办法[Dijkstra，1965年]。 Dijkstra的算法虽然是正确的，但取决于共享内存 访问是原子的——当另一个正在写入时，一个处理器读取将被要求等待，而不是返回 一个可能混乱的值。 从某种意义上说，它从硬件已经实现的低级互斥中构造了一个高 级解决方案。 兰波特的面包店算法不依赖于低级的相互排斥。 特别是，当一个处理器从共享变 量读取数据时，同一变量被另一个处理器更新时，前者读取垃圾是可以接受的，该算 法仍然有效！ 烘焙算法已经成为教科书材料，大多数计算机科学本科生在学习过程中 都会遇到它。 烘焙算法研究产生的概念贡献之一是，进程可以独立于其他进程的速度取得进展。 Bakery算法不会预先分配轮流到进程，而是按照进程到达的顺序分配轮流到进程。 使 用面包房的类比，预先分配的转弯将类似于到达一个空的面包店，并被要求等待一个甚至 还没有到达面包店的客户。 独立进步是一个关键的概念，已被用于许多后续算法的设计 和内存体系结构。 等待自由，一个需要独立进步的条件，尽管失败，有其明确的根 源，这一概念和面包店门口的概念。 后来赫利希[1991]和其他人对它进行了广泛的探 索。Bakery算法还导致Lamport怀疑多个进程与共享数据交互时内存的精确语义。 其结 果是原子、规则和安全寄存器的抽象[Lamport1986c，1986d]。 寄存器基本上是一个共享内存位置，可以由多个进程并发读取（加载）和写入(存 储。 兰波特的理论给共享寄存器上的每个操作一个明确的持续时间，从调用开始，以 结果结束。 寄存器可以通过各种技术来实现，例如复制寄存器的数据以容忍故障。 然而，进程与原子寄存器的交互应该“看起来”串行访问实际共享内存。 该理论还包 括弱于原子性的相互作用的语义，即规则寄存器和安全寄存器的相互作用。 常规寄存 器捕获进程在更新时读取寄存器的不同副本的情况。 在任何时候，一些副本可能会 被更新，而另一些副本则不会更新，最终，所有副本都会持有更新的值。 更弱的 安全寄存器概念允许读取重叠写入以获得任意值。 重要的是，这些薄弱的语义就足够 了

第二章：分布式系统中时间和全局状态的概念 5 为了实现互斥：烘焙算法与安全寄存器正确工作。 值得注意的是，Lamport对第1章所涵盖的原子对象的研究仅限于寄存器，它只支持 读和写操作。 原子性的概念被Herlihy和Wing[1990]推广到其他数据类型，它们的 术语线性化成为它的同义词。 在共享寄存器理论完成之前，Lamport在多处理器中处理了相干缓存行为的条件。 这项工作通过引入顺序一致性[Lamport1979b]，给这一领域的混乱带来了一些秩序， 这是本章所涵盖的最后一个概念。 这个简单而直观的概念提供了正确的“原子性”水 平，允许软件工作，并已成为内存一致性模型的金标准。 今天，我们设计了具有时间 戳排序或部分存储排序的硬件系统，并添加了内存围栏指令，允许程序员使硬件显示 顺序一致。 顺序一致性是为Java和C++等编程语言定义的内存一致性模型的基础。 因 此，我们的多核软件运行基于莱斯利兰波特在1979年描述的原则。 此外，基本上所有由亚马逊、谷歌和Facebook等公司开发的非关系存储系统都采用 线性化和顺序一致性作为数据一致性保证。 第二章：分布式系统中时间和全局状态的概念 一个突出的并发系统类型是分布式系统，其中进程使用消息相互交互。 第二章，由 Karolos Antoniadis和Rachid Guerraoui，涵盖了Lamport引入的强大概念，这些概念 塑造了我们对分布式系统的思考方式以及该领域的工程实践。 其中第一个是“逻辑时钟”和相应的“逻辑时间戳”，事实上，这些时间戳通常被 称为“Lamport时间戳”。许多人意识到，对于分布式系统来说，全局时间概念并不自 然，但Lamport是第一个正式确定精确替代方案的人。 他定义了事件上的“发生前” 关系-一个部分顺序捕捉消息交换所引起的因果关系。 例如，考虑旧金山的一个从传 感器读取温度的过程，以及伦敦的一个在屏幕上打印旧金山温度的过程。 如果加州进 程在读取传感器后发送消息，并且此消息在温度之前在伦敦收到