并发计算中的串行思考

软件系统性能的提升的重要方法之一是支持并发性编程，尤其是采用多核体系结构的时候。在全局数据库、云计算和区块链应用程序中，并发性对于实现容错和分布式服务也是至关重要的。然而，对并发性的掌握一直是令人畏惧的挑战之一。并发编程是困难的，要同时处理许多可能任务的非确定性行为，包括故障、操作系统、共享内存架构和异步。

互斥锁

并发的出现是为了有效地利用顺序执行的计算机，顺序执行的计算机一次只能执行一条指令，让用户认为他们的程序通过操作系统同时运行。

一旦并发运行的程序开始相互交互，危机就会浮现，当时的并发编程没有任何概念基础，程序错误百出，还会并会导致程序行为的不一致。1965年，Dijkstra 发现部分代码的互斥锁是编程的一个基本概念，从而打开了并发编程的道路。

锁

互斥锁/代码算法包含了进程调用类似acquire ()和 release ()的代码，这些代码用于称为临界区的一段代码。通常执行它的环境是异步的，其中进程速度是任意的，彼此独立。互斥锁算法保证了两个性质。

• 没有两个进程同时执行临界互斥锁。

• 如果一个或多个进程调用并发执行的 acquire ()操作，则只有一个进程调用并执行临界区。

锁并不能防止出现某些进程永远不能进入临界区的特定场景。

互斥锁算法

假设两个进程 p1和 p2共享三个读/写原子寄存器，F1、 F2和 L，最初的 F1和F2是关闭的，而 L不需要初始化。这两个进程都可以读取所有寄存器。原子寄存器味着寄存器上的读写操作是按顺序执行的。

当进程 p1 调用 acquire ()时，它首先设置自己的标志，从而表明它在竞争，然后在 L中写入自己的名字，表明它是这个寄存器的最后一个写入者。接下来，进程p1重复读取所有寄存器，直到它看到 F1或F2的标志不是p1， 或者p1不再是 LAST 的最后一个写入者。当这种情况发生时，p1终止它的调用，操作 release ()。

互斥锁是通过顺序思维掌握并发编程的第一种机制，导致了开始为并发计算提供了科学的基础概念，例如竞争条件和原子性的概念。使用锁控制对数据的访问(例如，两阶段锁) ，是并发控制的起源。

基于消息系统的读写寄存器

最基本的共享对象就是读/写寄存器。在共享内存中，简单的寄存器支持只有一个进程可以写，另一个进程可以读，而多写多读(MWMR)寄存器则支持每个进程都可以写，每个进程都可以读。

分布式消息系统通常支持共享内存的抽象，并得到了广泛接受，这种抽象提供了单处理器概念的自然转换，并简化了编程任务。在可靠的异步消息传递系统上构建原子读/写寄存器相对容易，但如果进程可能崩溃，则需要更复杂的算法：

• 一种在 n 个异步消息进程系统上实现原子读/写寄存器的算法，其中最多小于n/2的进程可能崩溃。

• 不可能在 n/2的进程崩溃时构建原子读/写寄存器。

这样的算法说明了减少并发对顺序执行的重要性，其设计原则是每个写入的值都有一个标识，每个进程既是客户端又是服务器，构建的多写多读(MWMR)寄存器——R，任何进程都可以读写寄存器。在客户端，进程P可以调用操作 R.write (v)在 REG 中写一个值 v，R.read ()以获取其当前值。在服务器端，进程P管理两个本地变量: 本地实现 R-i和 Timestamp-i (包含由序列 和进程标识组成的时间戳)。时间戳构成了在 R-i 中保存值 v 的“标识”,也就是说，这个值在此时是由这个进程写入的，任何两个时间戳完全是按照它们的字典序排序的。

进程 P向所有进程广播查询，并等待大多数进程的确认即投票仲裁，这就意味着读/写寄存器 R具有原子性属性。

当流程P调用 R.write (v)时，它首先创建一个标记，该标记将标识由此写操作调用生成的查询/响应消息。然后，它执行查询/响应模式，了解在大多数进程的本地变量 Timestamp-j 中保存的最高序列 。完成后，进程P计算时间戳 ts，这个时间戳将与它要在 R中写入的值 v 相关联。最后，进程P启动第二个查询/响应模式，在该模式中将(v，ts)广播给所有进程。当它从投票仲裁者收到相关的确认时，才会终止这一操作。

在服务器端，其他进程在写操作的第一阶段接收进程P发送的 WRITE R 消息，并发送回一个确认，该确认带有与它在 R-i 中保存的新值相关的序列 。当在写操作的第二阶段接收到由进程P发送的 WRITE R消息时，如果接收到的时间戳比保存在时间戳中的时间戳更新，这些进程就会更新实现本地数据 R-i，并且，在所有情况下，它都会发送回P和确认，因此 ，P终止了它的写操作。

因此，调用进程P与值 v 相关联的时间戳大于在P发出写操作之前的写操作时间戳。此外，虽然并发写操作可以将相同的序列 与它们的值关联，但是这些值具有不同的有序时间戳。异步消息系统中实现原子读/写寄存器也是串行计算在抽象层上的使用。

状态机复制

并发堆栈可以通过使用互斥锁执行 pop ()和 push ()操作来实现。但是，如果进程崩溃，这种策略将不起作用。状态机复制机制是通过异步进程通信实现的一种通用方法。其基本思想是让进程在并发调用的顺序上达成一致，然后每个进程在本地模拟串行计算的状态机。

假设把To-broadcast 抽象为分布式计算中的一个原语，它确保所有正确的进程以相同的顺序接收消息。进程调用 Tobroadcast (m) ，向所有其他进程发送消息 m，那么，进程在收到完全有序的消息时执行 Todeliver ()。在基于串行计算的并发编程中，To-broadcast 是一个普遍的概念，这种通信抽象促进了基于串行计算并发对象的构建。

对于基于 To-broadcast 的状态机复制而言，每个进程Px都有一个对象的拷贝状态，To-broadcast 抽象用于确保所有进程Px 对其对象 o 的本地状态采用相同的操作序列。实现协商一致的 To-broadcast，如果调用进程在调用期间没有崩溃，则所有流程都会收到 m，如果流程的任意子集收到 m。算法的核心是后台任务，一个进程会一直等待, 会对消息进行排序。

小结

在分布式系统中，最终一致性被广泛地部署以实现高可用性数据，最终所有对该数据项的访问都将返回最后更新的值(。在区块链中，通过放松控制并发性的串行控制可以获得的好处，区块链末端的分支暂时违反了分类账对象的一致性。尽管如此，区块链还是受到了性能瓶颈的困扰，因为它需要将所有的交易排序在一个单一的列表中，这促进了部分有序列表的探索，例如基于有向无环图的Tangle 或 Hashgraph。

CAP 定理形式化了通过顺序推理掌握并发性方法的一个基本限制，另一种选择是可用性成本。只要只有少数程序可能失败，该系统就会继续运作，并维护其一致性保障。

另外，基于串行计算的并发性方法有一个基本的限制，并非所有并发问题都有顺序规范。事实上，如今我们也没有好的工具来构建高效、可伸缩和可靠的并发系统。

[关联阅读]

• 计算机体系结构的一知半解

• WebAssembly一知半解

• 服务可用性的一知半解

• DHT算法的一知半解

• 稳定币的一知半解

• NFT 的一知半解

• ES的一知半解

• 数据存储的趣事

• NoSQL 之于大数据

• 从应用架构看大数据

• 面向AI 的数据生态系统

• 老曹眼中的面向数据架构

• ?tataUFO 大数据 应用实践

• 基于CRDT的数据最终一致性

• web 系统中——结构化数据标记

• 知新温故，从知识图谱到图数据库

• 清单管理机器学习中的数据集

• Crash——软件崩溃后的数据一致性

• 华为数据之道 ——  数据分类管理框架和经验

• 这是你所了解的FaaS 无服务计算的10个思考

• 没有被了解的API老码农眼中的API世界

• 关于软件开发，都应该知道的10个常识

• Crash——软件崩溃后的数据一致性

• 关于软件研发生产力的误区与思考

• 远程软件工程师的10个最佳实践

• 翻译如重构期待您的单元测试

• 如何提高团队的研发效率呢p>

• 性能，10点系统性思考

• 如何进入一个新领域

• 全栈必备 敏捷估点

• 一个函数的自白

文章知识点与官方知识档案匹配，可进一步学习相关知识算法技能树首页概览34693 人正在系统学习中