操作系统中 Huang 的终止检测算法

在本文中，我们将讨论操作系统中的黄氏终止检测算法，包括其关键原理、算法以及许多其他内容。

引言

黄氏终止检测算法由黄福锟设计并命名。它提出了在所有计算和任务完成时，如何确定分布式系统中所有进程的最终状态。该算法的创建源于分布式计算领域的持续研究，其中需要快速准确的终止检测，以确保分布式程序的正确性和可扩展性。

• 黄氏算法的出现和演变史，应该从更广阔的计算机科学早期分布式系统理论发展视角来看待。随着分布式系统在网络计算、并行处理和云计算等不同领域的普及，对能够进行高效可靠计算过程的数学模型（如终止检测机制）的需求日益增长。
• 终止检测算法可以被视为系统对分布式系统固有挑战的反应，这些挑战包括通信延迟、进程故障和网络分区。基于集中监控和协调的经典终止检测方式，在可扩展性和容错性方面通常效率低下，这促使研究人员需要寻找不同的解决方案。
• 黄氏算法提供了一种分散式的终止检测方法，它将每个进程终止的监控活动委托给运行在其间的进程。该算法详细阐述了消息传递和分布式协调，允许进程通过本地观察和本地信息交换来推断终止状态。
• 黄氏算法的另一个优点是，它可以在不过多协调和消息开销的情况下实现强大的终止保证。该算法能够通过维护本地状态信息和使用高效的消息传递协议来扩展并部分容忍故障，同时保持性能。

1. 消息传递模型

消息传递模型是分布式系统中的第一个抽象，其中进程通过网络交换消息进行通信。在黄氏算法中，参与者仅通过消息传递进行划分，每个进程都有自己的本地状态并独立进行。通过这种网络类型，进程可以在不使用共享内存或集中控制的情况下交换信息并协调它们的动作。

在黄氏算法中，消息传递模型是进程间通信的基础，用于进行终止检测。进程通过消息相互通信，以发送有关其活动的信息并列出它们所依赖的任务。通常，消息包含发送进程的状态信息，这些信息对于检查特定任务如何结束或是否收到了来自另一个进程的消息至关重要。进程之间的消息使它们能够共同推导出当前系统中的终止状态。

2. 依赖跟踪

依赖跟踪是黄氏算法等终止检测算法的核心。它涉及到查看任务之间的依赖关系或关系，这些关系是确定任务是否完成的基础。在黄氏算法中，进程可以接收发送或接收的任何消息；因此，它们可以检测到自身和其他进程的依赖关系及终止情况。

无论是消息还是请求，一个进程发送消息并期望接收进程进行确认或响应；同样，另一个进程依赖于发送消息的进程在收到另一进程的消息后完成其任务。它们跟踪这一点，以确定何时所有进程间依赖关系都已满足，这意味着终止已发生。

黄氏算法中的依赖跟踪是分散的，每个进程都拥有自己与其他进程的进程本地依赖视图。通过这种方式，分担工作可以及时有效地识别终止，而无需全局协调或集中控制。进程利用其本地依赖记录的信息来本地决定其终止，并为终止检测过程做出贡献。

3. 本地状态维护

保持本地状态对于黄氏算法是必需的：它意味着必须跟踪和遵循每个进程的执行流程，因为它们与其他进程相关联。每个进程都跟踪其本地信息，并了解它已经发送和接收了哪些消息，以及它正在从其他进程等待哪些消息。这种本地控制代表了文档进行自我审查并证明其终止状态的过程，因此终止检测过程包括本地控制。

黄氏算法基于本地状态存储的原则。因此，消息被存储在它们到达的节点上，并且计算可以沿着相同的线程堆栈从其源头追溯到它们在内存中的当前位置。原则上，进程通过交换消息来生成它们的公共状态，并且这些信息用于决定何时完成进程的工作，从而使其安全退出。它允许所有进程彼此独立，并且每个进程都可以独立运行，就像它自己的系统一样，不受限制或加速，但仍然能够找到有意义的答案。

算法

各步骤解释

• 初始化：逻辑从所有参与处理单元的本地状态变量初始化开始。这些变量是状态、依赖关系、消息发送计数器和消息接收计数器。状态变量显示进程的状态，可以是正在执行任务，也可以是仅等待探索性消息。进程变量是一组当前正在处理并等待与消息连接的进程。
• 主循环：算法运行一个主循环，该循环会重复执行，直到假定终止。在此循环中，每个进程执行两种状态：主动工作（执行计算和发送消息）和被动工作（等待传入消息）。在活动状态下，进程运行其分配的任务，并在必要时向其他进程发送消息。它通过注册一个 message_sent 计数器来记录已发送消息的数量来实现这一点。在被动模式下，进程将等待传入消息，处理收到的消息并相应地递增其 message_received 计数器。如果消息符合标准，进程将确定其精确的依赖级别。
• 终止检测：在检测之后，终止可以是全局的（通过全局终止条件）或局部的（由各个进程本地检测到）。之后，算法继续终止。这意味着该进程通过显示停止信号或结果，不为其他进程留下未完成的任务。

算法的假设

• 异步消息传递：黄氏算法底层的消息传递模型是异步的，并使用消息在网络上连接进程。假设会延迟消息的加载；某些消息可能会丢失，并且进程可能在不同的时间范围内执行。算法的异步特性使其能够适应各种网络条件，并进一步确保分布式系统的正确性。
• .
• 可靠的通信通道：黄氏算法提供了消息丢失和延迟的可能性。但是，它假定通信通道是可靠的，因为消息最终会被传递和处理，这些是进程之间的操作。如果通信传输通道变得不可靠，算法的终止检测机制可能会受到损害，导致不正确的终止决定。
• 有限网络：算法假设进程之间是有限连接的，而不是无限的，其中每个进程都有有限数量的邻居或对等方可以通过通信到达。此假设限制了资源使用，主要是通信和计算开销，并导致算法在实际的合理规模的分布式系统中可行。
• 有限计算时间：黄氏算法中进程的时间复杂度假定执行任务和处理消息的计算时间是有限的。该算法专门设计用于处理可能涉及消息或计算交换的长运行进程。

算法正确运行所需的前提条件

算法在操作系统中正确运行需要几个前提条件。其中一些如下：

• 正确实现：黄氏算法的正常运行假定所有参与进程都正确地实现了该算法。这还包括正确初始化本地状态变量，遵循消息传递协议，并确保状态更新正确跟踪依赖关系和消息交换。不正确的实现可能会破坏终止检测的一致性，并可能偶尔产生不正确的解决方案。
• 一致的消息排序：由于黄氏算法要求进程之间消息排序一致，因此必须确保进程的消息排序正确性。不同消息序列的顺序可能会导致依赖关系跟踪的模糊，并做出错误的终止决定。因此，算法的验证取决于消息因果关系和FIFO（先进先出）消息传递等前提条件。
• 足够的连通性：该算法认为进程之间有足够高的互连是维持开放通信渠道和正确满足依赖关系所必需的。在任务未传达或通信路线不可靠的情况下，检测时间可能会延迟。因此，连接到网络和有效的通信网络等前提条件对于算法的正确运行至关重要。
• 进程终止：黄氏发展的理论假定所有进程的运行最终都会使它们进入被动状态。在应用程序不活动后，或者当其他进程仍未得知进程终止时，该算法将延迟正确检测全局终止。因此，进程的活跃性（liveness）和基于终止的保证等前提条件对于算法的执行变得非常重要。黄氏终止检测算法具有许多重要的属性，这些属性有助于其在分布式系统中的有效性和可靠性。
• 完备性：最终，黄氏算法的完备性得到保证，并且它将在终止发生的各种可能情况下检测到终止。完备性确保算法不会忽略任何终止事件，并正确陈述分布式系统的当前状态。借助该算法，可以确保终止检测过程的正确性。此外，保证没有进程无限期地保持活动状态。
• 终止保证：该算法提供终止保证，这意味着尽管存在消息延迟、进程故障或同步问题，它也能在有限的时间内终止。终止保证该算法不会进入无限循环或无限期挂起。之后，分布式系统的至少一部分将得到处理，并取得进展，避免陷入僵局。
• 安全性：该算法不会产生误报，也就是说，它不会错误地将已终止的进程报告为仍在活动。算法还会处理误报，这意味着当发生这种情况时，没有进程继续执行其任务。
• 活性（Liveness）：无论通信媒介的延迟交付，还是进程故障或进程并非完全异步，该算法最终都会完成并产生终止检测结果。算法在任何时候都不会进入无限循环或卡住，因此可以保证进展。
• 适用性证明通常包括在消息传递、进程故障和终止事件等不同执行场景下验证算法的行为。正确性证明描绘了安全性和活性属性；它为分布式系统的正确性和完整性提供了数学保证。

与其他算法的比较

1. Chandy-Lamport 算法

• 基于消息：Chandy-Lamport算法是一种消息传递算法，它基于标记消息的交换来检测分布式系统的终止。
• 集中式协调器：该算法使用一个集中式主节点，通过向系统中的所有进程发送标记来启动终止状态消息的计算。
• 全局快照：Chandy-Lamport算法通过在收到标记信号时记录每个进程的状态和正在传递的消息，来将分布式系统保留为全局快照。

2. Ricart-Agrawala 算法

• 请求-回复模型：Ricart-Agrawala算法是一种基于请求-回复的算法，它保证了安全终止检测的辅助。
• 分布式互斥：该算法允许一次只有一个进程进入临界区，并防止多个进程在同一实例中运行终止检测。
• 集中式协调器：Ricart-Agrawala算法在没有中心协调器协助的情况下运行，以自主级别促进进程请求和释放对共享资源的访问。
• 消息复杂度：可实现的*消息复杂度*比Chandy-Lamport算法低，因为不需要标记消息和全局快照。
• 死锁避免：Ricart-Agrawala算法使用死锁避免机制，以防止进程在互斥下卡在死锁状态。

3. 比较

• 去中心化：黄氏算法和Ricart-Agrawala算法都被认为是去中心化的，因为它们会持续运行，而没有一个中心化的终止检测器。虽然Chandy-Lamport算法使用一个中心化的控制器来启动终止检测执行，但混合算法利用一个分布式协调器来实现相同的目的。
• 消息复杂度：通常，黄氏算法和 Ricart-Agrawala 算法需要传输的消息数量比 Chandy-Lamport 算法少。
• 可扩展性：Ricart-Agrawala 算法的一个突出特点是它在大型分布式系统中具有良好的可扩展性，不仅在于减少通信开销，还在于它避免了单一中心协调器瓶颈。黄氏方法也很有效，因为它是一个分布式系统，所有的计算能力都分布在网络参与者之间。
• 死锁避免：Ricart-Agrawala算法实现了死锁检测诊断机制，以在进程执行互斥时防止锁定状态。这个组件被 Moore 认可，但在 Chandy-Lamport 或黄氏算法中不存在。

黄氏终止检测算法的优点

黄氏终止检测算法有几个优点，如下所示：

• 去中心化方法：黄氏终止检测算法从去中心化的角度处理问题，从而消除了使用中心化指针作为协调器。这种分布式处理导致终止检测负载在进程之间分配，从而提高了大型系统的容错性和可扩展性。
• 低消息复杂度：对Chandy-Lamport 算法和黄氏算法的终止检测算法的调查表明，后者带来了更好的性能。这是因为这些算法不依赖于交换标记消息或进行全局快照；因此，实现了最优的通信开销。
• 可扩展性：此外，黄氏算法具有可扩展的能力。因此，它可用于包含大量进程的分布式系统。由于该算法的多节点特性以及分布式通信也很复杂的分布式环境，该终止算法对于各种网络拓扑 [跨越一系列分布式网络] 都非常高效。
• 容错性：黄氏算法的容错性在于算法的架构是可归约的，因此分布式系统对故障具有容忍性。算法处理终止检测的方式是每个进程平等地参与；因此，进程失败或网络分区 Thus, the possibility of process failure or network partition will be reduced without global system reliability as its effect.
• 高效的资源利用：黄氏算法是一种本地终止算法，它允许每个进程根据进程的状态和外部接收的消息来决定是否终止。本地方法使得并行性有助于减少协调开销并保证最佳的资源分配方式。

黄氏终止检测算法的缺点

黄氏终止检测算法有几个缺点，如下所示：

• 协调复杂性增加：使用黄氏算法进行终止检测可能比集中式算法引起更高的协调复杂性。在这些情况下，流程必须协调并通信消息以检测终止，确保依赖关系得到管理，并确保进程行为的正确性，这是一个巨大的挑战。
• 缺乏死锁避免：与 Ricart-Agrawala 算法等终止检测算法不同，黄氏算法不包含死锁避免机制。这表明该算法在某些分布式系统配置中可能会遇到容易出错的死锁。
• 全局视图有限：黄氏算法不处理分布式系统的全局视图，因为它基于本地状态和接收到的消息进行决策。对于需要全局系统概览来进行决策或分析的场景，提供全局快照视图的算法可能比此算法更有帮助。
• 在某些情况下效率可能低下：总的来说，黄氏算法在时间和资源方面都很高效，但在进程紧密互连或进程之间存在高消息交换频率的情况下，效率可能会降低。在这些情况下，算法将面临更多的消息流量和更长的终止检测时间。

黄氏终止检测算法的性能考虑

• 在大规模系统中的效率：可扩展性对黄氏算法至关重要，它是大型分布式系统中实用性的典范。这种可扩展性使黄氏算法能够管理数千个进程，而性能几乎没有下降。
• 通信开销：黄氏算法区别于其他一些集中式终止检测算法的特点是其通信开销低。该算法利用本地状态信息和消息交换，不需要全局参与或消息传递。因此，通信开销降低，从而提高了消息延迟、网络带宽利用率和整体系统响应能力。
• 异步执行：黄氏算法设计用于在异步分布式系统的框架下工作，其中进程可以随时执行和通信。这些进程可以异步执行并以不同的速度进行，因此争用减少，资源利用率更高。当适应动态和不确定的操作时，黄氏算法可以实现高性能和响应能力。
• 内存占用：总的来说，黄氏算法占用的内存空间比其他集中式终止检测算法要小。由于该算法仅使用本地状态信息，并且不需要远程消息传递，因此运行该算法可以节省大量用于进程状态和消息缓冲区的内存空间。减少的内存占用将转化为更好的整体系统性能和资源利用率，特别是在资源受限的嵌入式系统或设备中。
• 并行性和并发性：黄氏算法本质上是合作的，可以在分布式系统中并发工作。通过这种方式，多个进程可以并发地执行终止检测任务。这种并行性有助于利用多核架构和分布式计算资源，从而提高黄氏算法的高性能和可扩展性。由于并行性和并发性，黄氏算法可以实现更高的吞吐量和终止检测时间，尤其是在高度并发或需要密集并行处理的结构化系统中。