第三章 分布式系统的同步

第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算法06121824303642487076081624324048616977850102030405060708090100ABCDLamport解决方案直接使用先发生关系，每条消息携带发送者的时钟以指出其发送的时刻，当消息到达时，接收者时钟若比消息发送时钟小，就立即将自己的时钟调到比发送时间大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/dt1UTC，t时钟时间C稍慢时钟最佳时钟稍快时钟dC/dt=1dC/dt11-ρ≤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_Brese