第三章分布式系统的同步

第3章分布式系统的同步

时钟同步互斥选举算法原子事务

分布式系统中的死锁3.1

时钟同步分布式算法的性质相关信息分散在多台机器上进程决策仅仅依赖于本地信息系统中单点故障应避免没有公用时钟和其他精确的全局时间资源存在21442145214621472142214321442145进行编译的计算机进行编译的计算机创建output.o创建output.c根据本地时钟的时间根据本地时钟的时间时间当每台机器都有自己的时钟，一个发生于另一个事件之后的事件可能会标记一个比另一个事件更早的时间3.1

时钟同步3.1.1逻辑时钟

计算机计时方法

◘

计算机上的计时器通常由一个精确的石英晶体制成，它以一定的频率震荡。

◘

每次震荡计数器减1，当计数器减为0时，产生一次中断（时钟点）。

◘

在多CPU系统中，不同计算机上的晶体以不同的频率震荡，导致时钟不同步。（时钟偏移）

问题：同步所有时钟产生一个单一的、无二义的时间标准可能吗？

——Lamport：时钟同步是可能的！！！

◘

如果两个进程无相互作用，它们的时钟无需同步。◘时钟同步不需要绝对同步，不需所有进程在时间上完全一致，而是它们在事件发生的顺序上要完全一致。◘只关心事件发生的顺序，而不关心是否与真实时间接近。（逻辑时钟）3.1

时钟同步3.1.1逻辑时钟

先发生关系

◘

a发生在b之前，记为：a→b。存在两种情况：

▪

如果a和b是同一进程中两个事件，且a发生在b之前，则a→b为真；

▪

如果a是一个进程发送消息的事件，b为另一个进程接收这一消息的事件，则a→b为真；◘性质：

▪

先发生关系具有传递性：若a→b且b→c，则a→c。

并发事件

如果两个事件x和y，出现在不同的进程中，但并不交换消息，则x→y为假，y→x也为假。则事件x和y称为并发事件。3.1

时钟同步3.1.1逻辑时钟

Lamport算法

06121824303642485460081624324048566472800102030405060708090100ABCD

对于对每一事件a，给它分配一个时间值C(a)。这些时间值具有下列性质：若a→b，则c(a)<c(b)。此外，时钟时间值C必须递增，不能倒退。

例子：三个进程，每个均有自己的时钟，每个时钟速率不同。进程0进程1进程23.1

时钟同步3.1.1逻辑时钟Lamport算法

06121824303642487076081624324048616977850102030405060708090100ABCD

Lamport解决方案直接使用先发生关系，每条消息携带发送者的时钟以指出其发送的时刻，当消息到达时，接收者时钟若比消息发送时钟小，就立即将自己的时钟调到比发送时间大1或更多的值。

Lamport解决方案：调整C到达的时间为５６-61，D到达的时间为５４-70进程0进程1进程23.1

时钟同步3.1.1逻辑时钟

Lamport算法补充说明◘在每两个事件之间，时钟必须至少滴答一下。如果一个进程以相当快的速度连续发送或接收两条消息，它必须在这中间至少嘀嗒一下。

◘附加条件：两个事件不会精确的同时发生。如果进程1和进程2同时发生了2个事件，发生时刻都是40，则前者记为40.1，后者为40.2。

lamport算法遵循的规则：◘若在同一进程中a发生在b之前，则C（a）<C（b）;◘若a和b分别代表发送消息和接收消息，则C（a）<C（b）；◘对所有的a和b，C（a）≠C（b）。3.1

时钟同步

3.1.2物理时钟

物理时钟：UTC（统一协调时间），它是所有现代人使用的时间。地球轨道在n天以后的中天点地球已经旋转了将近３６０度到银河系的距离到银河系的距离地球第n天到达中天地球第０天到达中天中天点：太阳到达一天的最高点3.1

时钟同步

3.1.3时钟同步算法dC/dt<1UTC，t时钟时间C稍慢时钟最佳时钟稍快时钟dC/dt=1dC/dt>11-ρ≤dC/dt≤1+ρ

若保证两个时钟之间的差不超过δ，时钟至少在每δ/2ρ秒内再同步一次。（ρ为最大漂移速度）图3-5不是所有的时钟都按正确的速率中断3.1

时钟同步

3.1.3时钟同步算法Cristian’s算法发送机器

T0

时间T1I，中断处理时间请求CUTC时间服务器T0和T1都是由相同时钟测量的

适合于只有一台机器上有WWV接收器

（时间服务器），其它所有机器与它同步的系统。

说明：每台机器以小于或等于δ/2ρ秒的周期定期地向时间服务器发送消息询问当前的时间，时间服务器接到消息后就尽快回答含有当前时间CUTC值的消息。3.1

时钟同步

3.1.3时钟同步算法Cristian’s算法

问题1：发送者如何根据时间服务器的返回值调整时间？由于时间不能倒退，因此一种方法是根据时钟快慢，中断服务程序调整（增大或减小）每次中断所加的时间值。

问题2：如何处理从时间服务器发送的应答到发送者存在的延迟？精确记录从向时间服务器发送请求的起始时间于时间T0和接收到应答的结束时间T1。

当前服务器时间估计值=CUTC+（T1-T0）/2

如果考虑服务器中断处理的时间I，那么传输的时间间隔为T1-T0-I，单向传输时间为它的一半。3.1

时钟同步3.1.3时钟同步算法Berkeley算法

3:003:003:003:003:252:50+153:00+5-203:053:05-103:000+253:252:50

时间守护进程（时间服务器）定期地询问每台机器的时间。然后基于这些回答计算出平均值并告诉所有的机器将它们的时钟拨快或拨慢到一个新的值。（适合于没有WWV接收器的系统）时间守护进程询问其它机器的时间值机器应答时间守护进程通知每个机器如何调整时间3.1

时钟同步3.1.3时钟同步算法平均值算法将时间分成固定长度的再同步间隔，第i次间隔开始于T0+iR，结束于T0+(i+1)R.T0是过去某一约定的时间，R是一个系统参数。在每次间隔开始处，每台机器根据自己的时钟广播发送当前的时间。

在机器广播发送时间之后，它启动本地计时器收集在S时间间隔中到达的其他广播。当所有广播到达后，执行一个算法，得到新的时间值。这个算法可以是求这些值得平均值，或者是去掉m个最大值和m个最小值，平均其余值。3.1

时钟同步3.1.4使用时钟同步至多一次消息传递

每台机器上保存一个全局变量G，任何比G早的时间戳都能安全地从表中移走。

G=当前时间-最大生存时间-最大时钟偏移

G是所有老消息的消息数目的梗概。每隔一定时间△T，将当前的时间写入磁盘。当服务器重启时，从磁盘上重新装载G，再加上△T。基于时钟的缓冲存储器的一致性

3.2

互斥3.2.1集中式算法优点：容易实现、需要交互的消息少（请求、允许、释放）。缺点：单点故障、瓶颈、无法辨认服务器崩溃。012C请求OK协调者空队列012C请求无应答协调者2OK012C释放协调者算法思想：选一个进程作为协调者，进程若要进入临界区，它向协调者发送请求消息，协调者负责处理。图3-8集中式算法3.2

互斥3.2.2分布式算法Ricart和Agrawale算法要求系统中所有的事件都是全序的。即对于任何事件组（如消息），哪个先发生，哪个后发生必须无歧异。算法如下：当一个进程想进入临界区，它要建立一个包括它要进入的临界区的名字、处理机号和当前时间的消息，然后将消息发给所有其他进程。（也包括发送给它自身）当一个进程接收到另一个进程请求消息时，它取决于接收方的状态以及临界区的命名。有三种情况要加以区别。①若接收者不在临界区中，也不想进入临界区，它就向发送者发送OK消息。3.2

互斥3.2.2分布式算法Ricart和Agrawale算法②若接收者已经在临界区中，它就不必回答，而是负责对请求队列排队。③若接收者要进入临界区，但是还没有进入时，它要将发来的消息和它发送给其余进程的时间戳对比，取小的那个。如果来得消息时间戳小，接收者发送OK消息。如果接收者本身的时间戳小，那么接收者负责排列请求队列而不发送任何消息。在发送完允许进入临界区的请求后，进程将不做任何事，仅等待所有的允许消息，一旦得到允许，它就进入临界区。从临界区退出时，向队列中所有进程发送OK消息，并将它从队列中删除。3.2

互斥3.2.2分布式算法Ricart和Agrawale算法012888121212012OKOKOK012OK图3-9(a)两个进程在同一时刻进入同一个临界区

(b)进程0的时间戳小，所以它获胜

(c)当进程0完成时，它发送消息OK，进程2现在可进入临界区3.2

互斥3.2.2分布式算法Ricart和Agrawale算法每次进入临界区需要2(n-1)条消息，n为系统中进程数。如何解决多点失效当请求到达时，不管是许可还是拒绝，都要发送应答。一旦请求或应答丢失，发送者的等待时间到，它继续发送直到得到应答或者认为目的进程已经崩溃为止。使用组通信原语算法改进当一个进程从大多数进程哪里获得允许而并不需要所有进程都允许时就可以进入临界区。3.2

互斥3.2.3令牌环算法0249716583进程网络2345678901令牌持有者可能进入临界区或将令牌往下传递用软件的方法构造出一个逻辑环，环中每个进程都有一个位置，每个进程都知道谁在自己的下一个位置。优点：消息比分布式算法少。缺点：令牌丢失、进程崩溃。

图3-10(a)网络中一组未排序的进程

(b)用软件构造进程的逻辑环3.2

互斥3.2.4三种算法的比较算法每次进出需要的消息进入前的延迟（按消息次数）问题集中式32协调者崩溃分布式2(n-1)2(n-1)任何一个进程崩溃令牌环1到无穷大0到n-1丢失令牌，进程崩溃集中式、分布式和令牌环三种算法的性质的比较：进程进入或退出临界区需要的消息数目，每次进入前的延迟以及一些与算法有关的问题。表3-1三种互斥算法比较3.3

选举算法3.3.1欺负(bully)算法假设每个进程有一个特殊的号码，通常选举算法总是找拥有最大号码的进程。欺负算法：当一个进程发现协调者不再相应请求时，它发起选举。进程P选举过程如下：P向所有号码比它大的进程发送选举(Election)消息若无人响应，P获胜成为协调者。若有号码比它大的进程响应，响应者接管，P的工作完成。由于最大的进程总能取胜，因而将该算法命名为欺负算法。3.3

选举算法3.3.1欺负(bully)算法42156037选举选举选举42156037OKOK以前的协调者崩溃42156037选举选举选举42156037OK42156037协调者协调者（a）（b）（c）（d）（e）3.3

选举算法3.3.2环算法10765560565234223选举过程

◘

发起者沿环发送选举消息，若某点失效则绕过。

◘每次发送者都将自己的进程号加入到消息中。

◘最后，消息到达始发者手中，沿环发送协调者消息。3.4

原子事务3.4.1原子事务简介两个例子老式磁带银行转帐

（1）提取（金额，账户1）（2）存入（金额，账户2）计算机输入磁带今天的更新以前的库存新的库存输出磁带3.4

原子事务3.4.2事务模型稳定存储器不受洪水地震之类大灾难之外的任何其他错误的影响，可以通过两个磁盘实现。适合于需高度容错的应用，例如事务。sahfwbtosahfwbtosa1hfwbtosahfwbtosahfwbtosafwbto错误的校验和驱动器1驱动器2(a)(b)(c)3.4

原子事务3.4.2事务模型事务原语BEGIN_TRANSACTION:标记一个事务的开始；END_TRANSACTION:结束事务并设法提交；ABORT_TRANSACTION;取消事务；恢复旧值；READ：从一个文件（或其他对象）读取数据；WRITE：将数据写入一个文件（或其他对象）。事务体在BEGIN_TRANSACTION和END_TRANSACTION之间的操作构成了事务体。这些操作要么全部执行，要么一个也不执行。3.4

原子事务3.4.2事务模型事务原语例子（航空订票系统）BEGIN_TRANSACTIONreserveA_BreserveB_CreserveC_DEND_TRANSACTIONBEGIN_TRANSACTIONreserveA_BreserveB_CC_DfullABORT_TRANSACTION(a)预定三个航班机票的事务(b)当第三个航班的机票预定失败后事务中止预定一张从A到D的机票：3.4

原子事务3.4.2事务模型事务的特性（ACID）原子性（Atomic）

对外部世界来说，事务的发生是不可分割的。确保了每个事务要么全部发生，要么全部发生。一致性（Consistent）

事务不会破坏系统的恒定。意味着如果系统拥有某种必须经常保持的不变性，那么一旦事务开始之前保持有这样的性质，则事务结束后该性质应还该存在。3.4

原子事务3.4.2事务模型事务的特性（ACID）独立性（Isolated）

并发的事务不会相互干扰。这个特性说明事务是独立的或连续的。BEGIN_TRANSACTIONx=0;x=x+1;END_TRANSACTIONBEGIN_TRANSACTIONx=0;x=+2;END_TRANSACTIONBEGIN_TRANSACTIONx=0;x=x+3;END_TRANSACTION调度1x=0;x=x+1;x=0;x=x+2;x=0;x=x+3合法调度2x=0;x=0;x=x+1;x=x+2;x=0;x=x+3合法调度3x=0;x=0;x=x+1;x=0;x=x+2;x=x+3不合法3.4

原子事务3.4.2事务模型事务的特性（ACID）持久性（Durable）

一旦一个事务提交，改变就是永远存在的。提交之后发生的任何错误都不可能使结果取消或丢失。嵌套事务嵌套事务

事务可以包含子事务，通常称作嵌套事务。顶层事务可以在不同的处理机上创建并行运行子事务，以提高性能简化编程。3.4

原子事务3.4.3实现私有工作空间在进程开始一个事务时给它分配一个包含了所有需要访问的文件的私有工作空间，在事务提交或中止前所有的读写操作都是在私有工作空间而不是在真正的文件系统中进行的。问题：所有内容拷贝到私有工作空间，代价难以承受。两种优化方法：

私有工作空间中只包含一个指向父辈工作区的指针。当事务处于最顶层时，它的工作区是真正的文件系统。使用索引节点。索引是一个与判断文件所在磁盘块位置有关的数据块。该方法不将全部文件拷入私有工作空间，而只是将其索引拷入。

3.4

原子事务3.4.3实现私有工作空间使用索引节点（优化方法）

120空闲块012磁盘一个有三个数据块的文件的文件索引和磁盘数据块（a）3.4

原子事务3.4.3实现私有工作空间使用索引节点（优化方法）

1200’3’012一个事务修改第0块和附加块3后的情况123’0’私有工作空间起初的索引（b）3.4

原子事务3.4.3实现私有工作空间使用索引节点（优化方法）

12０３1230（c）提交以后如果事务成功结束，私有索引将被自动移到父辈工作区中3.4

原子事务3.4.3实现写前日志（计划列表）文件真正被修改，但是在改动之前将一条记录写入稳定存储器的写前日志中。日志工作例子：对事务中三条语句中的每一条，在执行之前都要写入一条日志，以记录新值和旧值。

x=0;y=0;BEGIN_TRANSACTIONx=x+1;y=y+2;x=y*y;END_TRANSACTIONx=0/1x=0/1y=0/2x=0/1y=0/2x=1/4日志日志日志如果事务异常中止，可用日志备份初始状态，回滚。3.4

原子事务3.4.3实现两阶段提交协议问题背景：在分布式系统中，提交操作可能需要在不同的机器上的多个进程的协作。两阶段提交协议是一种分布式系统中实现原子性提交的协议。

将“准备”写入日志发送“准备”消息将“就绪”写入日志发送“就绪”消息

收集所有应答写日志记录发送“提交”消息将提交写入日志提交发送“完成”消息将“准备”写入日志发送“准备”消息将“就绪”写入日志发送“就绪”消息

收集所有应答写日志记录发送“提交”消息将提交写入日志提交发送“完成”消息阶段1阶段2协调者参与者3.4

原子事务3.4.4并发控制加锁法两阶段加锁法

进程在增长阶段先请求它需要的所有锁，然后在收缩阶段释放它们。如图所示：时间锁的数目锁点增长阶段收缩阶段3.4

原子事务3.4.4并发控制乐观的并发控制思想

：“做自己想做的，有问题出现再说！”处理冲突

记录下哪些文件被读写过，在提交时刻，检测其它事务以判断在本事务开始后，它的文件是否被其它事务修改过。如果被修改过，本事务将被终止；如果没有修改过，本事务可以提交。

优点：避免了死锁，允许最大的并行度。

缺点:有时可能会失效，这时所有的事务都必须退回重新运行一遍。3.4

原子事务3.4.4并发控制时间戳在一个事务开始做BEGIN_TRANSACTION时给它分配一个时间戳（唯一）。系统中每个文件都有一个相关的读取时间戳和写入时间戳，以判断哪个已提交的进程最近一次读取或写入过该文件。如果事务都很短小并且在时间间隔上比较大，那么当一个进程试图访问某个文件时，该文件的读写时间戳将低于当前事务的时间戳。（正常情况）如果次序不正确，表明一个晚于当前事务开始的事务试图插入、访问文件并提交。这意味着当前事务开始过早，将其终止。3.4

原子事务3.4.4并发控制时间戳时间戳方法举例：设有三个事务：α、β、γ。α

很早以前已开始运行，并且要使用β和γ需要的所有文件，因此这些文件都将设成α的时间戳。β和γ同时开始，但β的时间戳小于γ。TRDTWRT(α)(α)(β)TRDTWRT(α)(β)(a)(b)当γ未提交时β写文件的情况试验T(β)(γ)TTWR(c)(d)退出(β)(γ)TRD当γ既读取又写入文件并提交时，β写文件的情况写3.4

原子事务3.4.4并发控制时间戳时间戳方法举例：退出TWRT(α)(β)TTENTTWRT(α)(β)(e)(f)没有冲突OKT(β)(γ)T(g)(h)(β)(γ)TWR(γ)等待TTENT某个闯入者试图进入并写文件γ修改了文件并提交γ正在修改文件读3.5

分布式系统中的死锁分布式系统处理死锁问题的四种策略鸵鸟算法（忽略问题）检测（允许死锁发生，在检测到后想办法恢复）预防（静态的使死锁在结构上是不可能发生的）避免（通过仔细的分配资源以避免死锁）其中，鸵鸟算法在分布式系统中和在单处理机系统中一样好用。死锁检测与恢复算法也很流行。死锁预防可能实现。死锁避免在分布式系统中从来不采用。3.5分布式系统中的死锁3.5.1分布式死锁检测集中式死锁检测每台机器的资源图中只包含它自己的进程和资源。协调者节点保存整个系统（所有资源图的集合）的资源图，当协调者检测到环路时，它中止一个进程以解决死锁。假死锁

ABRS机器0CTS机器1ABRSCT协调者ABRSCT协调者图3-223.5分布式系统中的死锁3.5.1分布式死锁检测分布式死锁检测Chandy-Misra-Has算法：算法允许进程一次请求多个资