操作系统中 Ring 算法与 Bully 算法的区别

在本文中，我们将讨论操作系统中环形算法与霸道算法的区别。但在讨论它们的区别之前，我们必须先了解这两种算法在操作系统中的概念。

什么是环形算法？

环形算法是一种分布式算法，用于分布式系统中进程间的协调和通信等任务。其原理是消息在一个逻辑环形拓扑中以闭环方式重复传递，其中每个进程都只与其两个邻居相连。这种拓扑结构形成一个消息循环，使得消息能够通过一个环路到达其目标。

环形算法将进程按逻辑环形顺序排列；因此，进程都知晓自己的邻居。如果数据传输机制希望与其他进程通信，它会向其邻近进程发送请求。然后，消息被获取并转发给下一个对等进程，直到到达预定接收者。这个信息循环会重复进行，直到消息停止并返回给发送者。

环形算法机制通过使用一个传递的符号来工作，该符号用于维持通信秩序。令牌是一种特殊的代码，它传递权限，允许当前节点向下一个节点发送消息。首先，确定令牌停留在哪个进程或正在沿环传递。试图通信的进程持有资源，在此期间，该进程必须持续持有令牌。传输完成后，进程会将其消息发送给下一个进程，然后令牌会被传递下去。

什么是霸道算法？

霸道算法是一种用于分布式系统中的协调和选举算法，用于从一组进程中确定领导者。它非常适用于需要选举领导者或执行权威来控制资源并在系统内执行某些任务的多种应用场景。

• 这种权力安排框架被称为霸道算法，它旨在让进程根据分配的等级按优先级排序。如果领导进程发现当前领导者不再能够解决认知问题或无法访问，它会发起新领导者的选举。通过在剩余进程中选择最高优先级，具有最高优先级的进程将成为领导者。
• 领导者故障检测： 当算法检测到竞选中的进程数量达到指定数目，并且当前领导者已经失败或无法访问时，选举开始。这可以通过超时机制或通过接收到其他进程的故障报告来触发。
• 选举的发起： 当领导者进程失败时，选举过程被触发，通过选举消息广播周期将此情况传达给其余进程。该消息也包含每个进程的ID和优先级。
• 优先级比较： 在收到消息确认后，每个进程检查该进程是否具有最高优先级或自身优先级最高。之后，如果低优先级的接收进程从高优先级的发起进程收到一个“OK”消息，它将停止管理该组，并接替其成为领导者。
• 选举完成： 当新领导者被选出，并且所有进程都承认新领导者的权威时，选举过程被视为完成。系统在选举出的新领导者的控制下恢复正常运行。

环形算法与霸道算法的主要区别

操作系统中的环形算法与霸道算法存在若干区别。一些主要区别如下：

可扩展性

• 环形算法： 环形算法的可扩展性取决于系统中的进程数量和消息流量。如果需要处理的进程数量足够多，整个环可能会面临过多的流量，导致性能下降。然而，该算法并未受到严格的可扩展性限制，可以应用于中等规模的分布式系统。
• 霸道算法： 当发生多次领导者选举时，环形算法特别有用。根据霸道算法，在存在分层领导的情况下，系统执行的可扩展性受进程数量的影响较小。然而，随着进程数量的大幅增加，领导者选举消息、同步和协调的成本可能会影响性能。

容错性

• 环形算法： 环形算法通过允许进程识别问题并绕过环中无法访问的进程来提供容错能力。如果一个进程崩溃或变得不可访问，消息可以使用环形拓扑绕过它。然而，该技术可能难以从多个并发故障或网络分区中恢复。
• 霸道算法： 霸道算法通过在领导者发生故障时选举新领导者来确保强大的容错能力。当当前领导者失败时，霸道算法会立即发起选举，从其余进程中选择一个新领导者。这可以维持操作的连续性，并减少因故障引起的中断。此外，该算法的分层结构通过在不同进程间分散领导角色，增强了容错能力。

效率

• 环形算法： 环形算法的延迟问题是由于消息在进程间传递需要经过多个周期。在环形算法中，该算法与传统算法不同，因为消息是按预定顺序环绕传递的。因此，与其他通信模式相比，它使用的开销更少，并能维持通信秩序。然而，在高消息流量下，该算法可能会变慢，并且当进程频繁加入和离开环时，进程的同步也是一个问题。
• 霸道算法： 霸道算法在选举领导者和协调任务方面非常有效。当领导者失败时，系统会根据既定优先级迅速选举一个替代领导者，减少了与领导者选择相关的时间和消息开销。此外，该算法的分层结构允许有效划分领导任务，从而提高整体系统效率。

复杂度

• 环形算法： 环形算法比需要更复杂协调的算法更容易部署。由于其去中心化的特性和内置的令牌传递机制，该算法实现起来很简单。然而，消息排序、验证和处理来自不同节点的故障会增加一定程度的复杂性，尤其是在高度分布式的系统中。
• 霸道算法： 霸道算法稍微复杂一些，因为其结构涉及分层领导，并且在选择领导者方面需要处理一些复杂性。该算法的实现包括：
  • 分配进程优先级。
  • 处理选举内部和选举之间的通信。
  • 协调领导者的继任顺序。

消息开销

• 环形算法： 与环形算法相比，生成树协议通过向网络中所有进程广播消息，实现了更高的消息开销，而环形算法中消息仅转发给已离开的环所属的节点链。每个进程都应该知道其直接邻居，并且当环拓扑发生变化时，可能需要额外的发送和接收消息来保持环的同步运行。
• 霸道算法： 由于霸道算法的数据结构简单，在算法的常规操作期间产生的消息开销相对较小。另一方面，尽管领导者失败，后续的选举也不会需要更多的流量；其他进程仍将获得更多的参与。

动态性与适应性

• 环形算法： 环形算法可能难以适应系统中的动态变化，例如进程频繁加入和退出环。重新配置环结构以适应这些变化可能很困难，并且可能需要操作之间更多的协调。
• 霸道算法： 霸道算法的分层结构使其对系统中的动态变化更具响应性。当一个进程失败或进入系统时，算法可以通过发起全新的领导者选举（如果必要）来快速响应。这种适应性使系统能够在动态变化面前保持稳定和连续。

资源利用

• 环形算法： 在某些情况下，环形算法可能导致资源利用效率低下，特别是在消息流分布不均或进程间工作负载变化时。靠近令牌持有者的进程可能比其他进程处理更多的消息，从而导致资源争用和瓶颈。
• 霸道算法： 霸道算法通常导致进程间的资源使用更加均衡，特别是在领导者选举期间。由于所有进程都根据其优先级参与选举，该算法公平有效地分配了工作负载。这种均衡的利用提高了整体系统性能和响应能力。

对网络拓扑的适应性

• 环形算法： 环形算法天然适用于具有逻辑环形拓扑的系统。虽然在这种情况下构建简单容易，但在具有非环形拓扑的分布式系统中可能会遇到问题。使该算法适应各种网络拓扑可能需要额外的协调和通信机制。
• 霸道算法： 与环形协议不同，霸道协议在网络拓扑方面更具灵活性。这项技术不同于环形、星形、网状或树形等传统拓扑，因为它不仅仅依赖于这些拓扑。其灵活性使得霸道算法能够服务于各种复杂的连接系统设置。

延迟与消息传播时间

• 环形算法： 环形网络算法指的是延迟和消息分发时间由环的大小以及消息到达目的地所需的中间跳转次数决定。长的环段或已发布的消息可能导致更高的延迟或消息传播时间，从而影响系统响应时间。
• 霸道算法： 虽然霸道算法通常表现出较低的延迟和更快的消息分发中间过程——有时，在领导者选举期间，它可能会超过环形算法。事实上，进程也可以直接相互联系，而无需使用环结构。反过来，这使它们能够执行更快的决策和协调，这些功能在时间敏感的情况下增强了整体系统性能。