分布式系统中的同步

一般来说，去中心化的算法具有以下特性。

• 相关信息分布在多台计算机上。
• 进程只根据本地信息做出决定。
• 不应该有一个单一的临界点，它的失败会导致算法的崩溃。
• 没有通用的时钟或其他准确的全球时间来源。

前三点都谈到了收集所有信息以在一个地方做出决定的不可接受性。在没有集中化的情况下提供同步需要与传统 *** 作系统中使用的方法不同的方法。最后一点也很重要——在分布式系统中，按时达成一致绝非易事。从 UNIX make 程序的例子可以看出时间一致的重要性。主要的理论问题是缺少全局时钟和无法修复全局状态（分析情况 - 检测死锁，组织中间存储）。 

---

时间同步

硬件时钟（而不是计时器 - 临时信号计数器和具有计数器初始值的寄存器）基于石英振荡器，并且在不同计算机中的频率可能会有所不同。

1978 年，Lamport 证明了时间同步是可能的，并提出了一种用于这种同步的算法。但是，他指出不需要绝对同步。如果两个进程不交互，那么它们不需要相同的时间。此外，在大多数情况下，约定的时间可能与广播中公布的天文时间没有任何关系。在这种情况下，可以说是逻辑时钟。

对于逻辑时钟同步，Lamport 定义了“发生在之前”的关系。表达式 a->b 读作“ a发生在b之前”，表示所有进程都同意事件“ a ”首先发生，然后是“ b ”。这种关系在两种情况下很明显：

1. 如果两个事件发生在同一个进程中。
2. 如果事件 a 是一个进程中的 SEND *** 作，事件b是另一个进程收到此消息。

关系->是可传递的。

如果两个事件x 和 y 发生在不交换消息的不同进程中，则关系 x->y 和 y->x无效，这些事件称为同时发生。

让我们以这样的方式引入逻辑时间 C，如果a->b，则C(a) < C(b)

算法：

1. 时钟 Ci 随着进程Pi中的每个事件递增：Ci=Ci+d ( d > 0, 通常为 1)
2. 如果事件 a是进程Pi 发送消息m，则将时间戳tm=Ci(a)写入该消息。当进程 Pj收到此消息时 ，其时间调整如下： Cj = max(Cj,tm+d)

 用一个例子来解释这个校正是如何进行的。

为了对所有事件进行排序，要求它们的时间从不重合是很方便的。这可以通过添加一个唯一的进程号（40.1、40.2）作为时间的一小部分来完成。然而，对于许多应用（实时控制系统）来说，逻辑时钟是不够的。

物理时钟。

17世纪发明机械钟后，时间是用天文方法测量的。太阳连续两次到达天空最高点的时间间隔称为一个太阳日。一个太阳秒等于一个太阳日的 1/86400(24*3600)。

在 1940 年代，人们发现地球的自转周期不是恒定的——地球由于潮汐和大气而减慢了自转速度。地质学家认为，3亿年前一年有400天。由于其他原因，一天的长度也会发生变化。因此，他们开始计算长期的平均太阳秒数。

随着 1948 年原子钟的发明，精确测量时间成为可能，而不受太阳日波动的影响。目前，全球有 50 个实验室拥有基于 Cesium-133 辐射频率的时钟。平均值为国际原子时 (TAI)，从 1958 年 7 月 1 日开始计算。

当差异大于 800 微秒时，TAI 与太阳时的延迟通过增加一秒来补偿。这个更正的时间，称为 UTC（通用协调时间），取代了旧标准（格林威治标准时间 - 天文时间）。在宣布向 UTC 增加一秒时，电力公司将频率从 60 Hz 更改为 61 Hz（从 50 到 51），持续 60 (50) 秒。为了确保准确的时间，WWV 信号由短波发射器（科罗拉多州柯林斯堡）在 UTC 的每一秒开始时发射。还有其他时间服务。

时间同步算法。

两个问题 - 时钟不应该倒退（需要加快或减慢以进行更正）和传递时间消息的非零时间（您可以重复测量传递的时间并取平均值)。

---

选择协调员

许多分布式算法需要其中一个进程充当协调者、发起者或其他一些特殊角色。这种特殊过程的选择将被称为协调器的选择。在这种情况下，通常选择哪个过程并不重要。我们可以假设通常选择具有最高唯一编号的进程。可以使用具有一个目标的不同算法 - 如果选举程序已经开始，那么它必须在所有关于新协调员的进程的同意下结束。

欺凌算法
如果进程检测到协调器很长时间没有响应，它就会发起选举。进程P进行如下选举：

1. P 向所有编号高于自身的进程发送“SELECT”消息。
2. 如果没有答案，则 P 被认为是获胜者并成为协调者。
3. 如果编号较大的进程之一响应，它将接管选举。进程 P参与选举结束。

在任何时候，一个进程都可以从它的一个具有较低编号的对等点接收“OPTIONS”消息。在这种情况下，他发送一个“OK”响应以表明他还活着并接管了选举的运行，然后开始选举（如果他还没有这样做的话）。因此，所有进程都将停止选举，除了一个 - 一个新的协调器。他通过消息“协调员”通知每个人他的胜利和上任。

如果一个进程被关闭，然后想要重新获得它的参与，那么它就会举行一次选举（因此是算法的名称）。

循环算法

该算法基于使用环（物理或逻辑）但没有标记。每个进程都知道循环列表中的下一个。当一个进程检测到没有协调者时，它会向下一个进程发送一个“ELECT”消息及其编号。如果下一个进程没有响应，则将消息发送到其后的进程，依此类推，直到找到正在运行的进程。每个正在运行的进程将自己的编号添加到正在运行的进程列表中，并将消息转发到更远的圆圈中。当进程在列表中找到自己的编号（循环完成）时，将消息类型更改为“COORDINATOR”并绕着循环，通知每个人有关工人列表和协调员（编号最高的进程）在列表中）。

---

相互排斥：集中式算法

• 所有进程都向协调者请求进入关键部分的许可，并等待这一许可。 协调器按照收到请求的顺序提供服务。 
• 获得许可后，该过程进入了关键部分。 在离开关键部分时，它通知协调人。
• 每个关键部分的信息数量为3。
• 该算法的缺点是集中式算法的通常缺点（协调器崩溃或信息过载）。

分散的基于时间戳的算法

    进入一个关键部分

• 当一个进程想进入一个临界区时，它向所有进程发送一个包含临界区名称、进程号和当前时间的请求消息。
• 发送请求后，该进程等待每个人给予它许可。在得到所有人的许可后，它进入了关键部分。 

    进程在收到请求时的行为

• 当一个进程收到一个请求消息时，根据它与指定的关键部分有关的状态，它以下列方式之一行事。
• 如果收件人不在关键部分内，也没有请求进入该部分的许可，它就会向发件人发送一个 "OK "消息。
• 如果收件人在一个关键部分内，它不会响应，但会记住该请求。
• 如果收件人发出了进入该部分的请求，但还没有进入，它就会比较其请求的时间戳和其他人的时间戳。时间戳小的一方获胜。如果外国请求获胜，该进程将发送一个 "OK "消息。 如果外国请求有更大的时间戳，则不发送响应，外国请求被记住。

    退出一个关键部分

•  在退出部分后，它向所有它记住的请求的进程发送一个 "OK "消息，然后删除所有记住的请求。
• 每节传递的信息数量是2(n-1)，其中n是进程的数量。
• 另外，一个临界点被n个点所取代（如果某些过程停止运作，缺乏来自它的决议将使所有人停止）。
• 最后，如果在集中式算法中存在协调器超载的危险，在这种算法中，任何进程的超载都会导致同样的后果。
• 对算法的一些改进（例如，等待大多数人的许可，而不是所有的人）需要不可分割的广播信息。

    该算法被命名为Ricart-Agrawala。 需要对系统中的所有事件进行全局时间排序。

 带有圆形标记的算法

•     所有的过程都形成了一个逻辑环，每个人都知道谁在遵循它们。 
•     一个令牌在环中循环，授予进入一个关键部分的权利。   
•     在收到令牌后（通过点对点消息），进程要么进入关键部分（如果它在等待许可），要么进一步转发令牌。   
•     在离开关键部分后，令牌被转发，不允许用同一令牌再次进入该部分。

广播标记算法(Suzuki-Kasami) 

该标记包含。

• 请求队列。
• 数组LN[1...N]，包含最后满足的请求的数量。

进入关键部分

• 如果请求关键部分的进程Pk没有令牌，它将增加其请求序列号RNk[k]并发送一个包含进程号（k）和请求号（Sn = RNk[k]）的广播消息 "REQUEST"。
• 如果进程Pk有（或收到）一个令牌，它就会执行关键部分。
   

收到请求时的处理行为

• 当进程Pj收到来自进程Pk的请求信息时，它设置RNjj[k]=max(RNjj[k],Sn)。
• 如果Pj有一个空闲的令牌，它只在RNjj[k]==LN[k]+1（请求不老）时才将其发送给Pk。

 
退出Pk进程的关键部分。

• 将令牌中的LN[k]设置为等于RNk[k]。
• 对于RNk[j]=LN[j]+1的每个Pj，它将其标识符添加到请求标记队列中（如果它还没有在那里）。
• 如果请求标记队列不是空的，那么第一个元素将被移除，标记将被发送到相应的进程（其请求是队列中的第一个）。

 

 

 

 

 ​​​​​​​

 

 

 

树标算法（Raymond）

所有进程都表示为平衡的二叉树。每个进程都有一个来自自身和相邻进程（第1、第2或第3）的请求队列和一个指向令牌所有者的指针。

关键部门的入口

• 如果有一个令牌，进程就执行COP。
• 如果没有令牌，这个进程:
  • 将其请求放在请求队列中。
  • 向令牌所有者发送一个 "REQUEST "消息，并等待消息的到来。

进程在接收信息时的行为 
不在CW中的进程必须对两种类型的信息做出反应--"MARKER "和 "REQUEST"。
A) "MARKER "信息已经到达。

• М1. 从队列中取出第1个请求，并将令牌发送给其作者（概念上，可能是发送给自己）。
• М2. 将指针的值向标记处改变。
• М3. 从队列中排除一个查询。
• М4. 如果队列中还有任何请求，就向标记者发送 "REQUEST "消息。

B) 收到REQUEST信息。

• 将请求放入队列。
• 如果没有标记，则向标记处发送 "REQUEST "信息，否则（如果有标记）转到M1点。

退出关键部分

• 如果请求队列是空的，退出时不做任何事情，否则 - 转到M1点。

​​​​​​​