分布式操作系统3分析

分布式操作系统第三章分布式系统的同步3.1时钟同步分布式算法的特点：相关信息分散在多台机器中；远程决策仅仅依赖本地信息；系统中单点故障应该避免；没有公用时钟或其他精确的全局时间资源存在。当每台机器都有自己的时钟，一个发生在另一事件之后的事件可能会被标记为比后者更早的时间。3.1.1逻辑时钟时钟点(clocktick):一次时钟中断；时钟偏移(clockskew):因计时器频率不同而导致多台机器之间的时间偏差；Lamport提出时钟同步的可能时钟不需要绝对同步；若两进程间无相互作用，则不需要同步；若需要同步，则需要解决进程间事件发生顺序的一致性。相对时间——逻辑时钟绝对时间——物理时钟“先发生”(a→b)关系：如果a和b是在同一进程内的两个事件，且a发生在b之前，则a→b为真；如果a是一个进程发送消息，b是另一进程接收这一消息的事件，则a→b为真，即消息不能在发送之前接收，也不能在发送的同时接收，因为传送过程还需要一定时间；先发生是一个传递关系，即若a→b且b→c则a→c。为每一事件分配一时间值C，当a→b，则有C(a)C(b)06121824303642485460008162432404856647280101020304050607080901002“6”→“16”→“24”→“40”“60”→“56”→“64”→“54”06121824303642487076008162432404861697785101020304050607080901002“6”→“16”→“24”→“40”“60”→“61”→“69”→“70”Lamport的解决方案：直接利用先发生关系；每条消息都携带发送者的时刻值，当消息到达时，若接收者的时钟值比消息发送时钟小，就立刻将自己的时钟调整为比发送时间大1或更多的值；在某些条件下，将进程号附加在时间值之后，并以小数点隔开。分布式系统时间分配规则：若在同一进程内a发生在b之前，则C(a)C(b)；若a和b分别代表发送消息和接收消息，则C(a)C(b)；对所有事件a和b，C(a)C(b)。3.1.2物理时钟太阳日铯133原子钟：以铯原子133所9192631770次跃迁所用的时间为一秒，简称TAI(InternationalAtomicTime)闰秒(leapsecond)：因为原子钟时和太阳秒不同步，为减少误差，当原子钟时与太阳秒计时的误差增加到800微秒时，插入一秒。统一协调时间(UTC)3.1.3时钟同步算法完美情况：对于所有p和t，都有：Cp(t)＝tdC/dt＝1实际情况：1－þ≦dC/dt≦1+þ不同时钟的速率Cristian’s算法设立一台时间服务器，向其他机器提供标准时间。每台机器以σ/2þ秒的周期向服务器查询当前时间。服务器服务器在收到消息后尽快回答当前时间CUTC。时间不能倒退。当CUTC比请求者的C小时，通过减小计数器的值逐步缩小差距；传输需要时间开销。从一个时间服务器得到当前时间Berkeley算法时间服务器定期询问每台机器的时间，然后基于这些回答计算平均值并告诉每台机器将其时钟拨块或拨慢到一个新的值。平均值算法将时间划分为固定长度的再同步间隔，在间隔的开始处，每台机器根据自己的时钟广播发送当前时间。在发送后，启动本地计数器收集在S时间间隔内到达的其他广播，计算后得到新的时间值。多部外部时钟源3.1.4使用同步时钟至多一次消息传递传统消息中传递中，消息带有唯一的消息号，当系统故障后重起，将丢失消息号信息表。利用时间，每天消息都携带一个连接标识和时间戳，每次连接，服务器记录最后一次时间戳，根据时间戳判断消息先后。全局变量G：G＝当前时间－最大生存时间－最大时钟偏移基于时钟的缓冲存储器的一致性将缓冲分为读缓冲和写缓冲；客户需要文件时，服务器提供一个标注有拷贝有效期的租约，无租约或租约期满的文件不能再使用。当租约到期后，客户可向服务器查询拷贝的有效性(时戳未修改)，有效则可再续约。当文件需要被改动，服务器通知其使用者租约提前失效，如客户端没有回应，则等到租约期满后自动失效。3.2互斥在使用临界区时，通过互斥锁提供独享数据结构。在单机系统中，我们使用信号量(semaphores)、管程(monitors)和一些其他结构来保护临界区。3.2.1集中算法利用协调者提供临界区的管理。(a)进程1请求协调者允许它进入临界区，请求被应答(b)进程2请求协调者允许它进入临界区，请求者不应答(c)进程1退出临界区，通知协调者，协调者应答进程23.2.2分布式算法当一个进程想要进入临界区，需要向其他进程广播临界区的名字、处理机号和当前时间；当其他进程收到消息后，根据情况回应：若不在临界区也不想进入临界区，就向发送者发送OK消息；若已经在临界区，则不回答，并将请求队列排队；若需要进入临界区但还没有进入，根据时间戳判断，当来者时间戳小，则发送OK消息；如果时间戳大，则排列请求队列而不发送消息。问题：当有进程失效或消息丢失，则被解释为不能进入临界区。解决方法是修改应答机制，不论是否同意都应答。组通信要使用通信原语，或者每个进程必须维护一组成员表，包括进入组进程、离开组进程和崩溃进程；请求必须通过全体成员表决，可能产生瓶颈。修改为：不需要所有成员允许即可进入临界区，在临界区内的进程在退出临界区之前不能批准其他进程进入。3.2.3令牌环算法通过令牌控制进入权。谁获得令牌，谁就可以进入临界区。令牌在环路中传递，如不需要进入临界区，则直接将令牌传递到下一成员。容易出现的问题令牌再生问题；环成员退出时环的再构问题。三种算法比较算法每次进出需要的额外开销进入前的延迟(按消息次数)问题集中式32协调者崩溃分布式2(n+1)2(n-1)任何一个进程崩溃令牌环1到无穷大0到n-1丢失令牌，进程崩溃3.3选举算法利用地址或进程的其他有序特征数产生协调者或其他有特殊意义的成员。3.3.1欺负(Bully)算法当一个进程发现协调者不再响应，就发起选举：P向所有号码比他大的进程发送选举(ELECTION)消息；若无人相应，则P获胜成为协调者；若有号码比它大的进程响应，响应者接管，P的工作完成。3.3.2环算法每个进程都知道前驱者和后继者。进程向后继者发送包括自己进程号的消息，如果直接后继没有应答，则发给间接后继。在循环一周后，消息回到始发者手中。始发者将消息类型转变成协调者消息，再次绕环运行。当消息再次回到始发者手中时，所有成员都知道协调者的身份。消息被遗弃。3.4原子事务目的：提供更高层次的抽象，隐藏技术细节，允许编程人员将注意力集中在算法和进程如何运行上。这种抽象我们称之为原子事务，简称事务。3.4.1原子事务简介更新主磁带是容错的特点：事务执行后可以返回最初状态，所以在任何情况下，因任何原因引起运行错误，其工作都可以毫无损失地重新开始。3.4.2事务模型稳定存储器盘1更新后崩溃错误的地方sahfwbtosahfwbto12sa’hfwbtosahfwbto12sa’hfwbtosa’fwbto12错误的校验和事务原语原语描述BEGIN_TRANSACTION标记一个事务的开始END_TRANSACTION结束事务并设法提交ABORT_TRANSACTION取消事务并退回初始状态READ从一个文件(或其对象)读取数据WRITE将数据写入一个文件(或其对象)BEGIN_TRANSACTIONreserveWP-JFK;reserveJFK-Nairobi;reserveNairobi-Malindi;END_TRANSACTION(a)BEGIN_TRANSACTIONreserveWP-JFK;reserveJFK-Nairobi;reserveNairobi-Malindifull=ABORT_TRANSACTION(b)事务的特征特征说明原子性(Atomic)对外部世界来说，事务的发生是不可分割的一致性(Consistent)事务不会破坏系统的恒定独立性(Isolated)并发的事务不会相互干扰持久性(Durable)一旦事务提交，改变就永远存在BEGIN_TRANSACTIONx=0;x=x+1;END_TRANSACTION(a)BEGIN_TRANSACTIONx=0;x=x+1;END_TRANSACTION(b)BEGIN_TRANSACTIONx=0;x=x+1;END_TRANSACTION(c)调度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不合格上：(a)-©三个事务下：可能的调度嵌套事务事务中包含子事务，这就是嵌套事务。系统不可见父事务细节，父事务也不可见子事务细节。父事务终止，其子事务将被恢复。如果一个子事务提交后又开始一个子事务，那它就可以看到第一个子事务的结果。3.4.3实现如果每个进程执行一个事务仅仅只是更新它自己的对象(文件、数据库记录等),那么事务就不会是原子的，而且事务异常终止时它所作的更该也不会消失。此外，运行多个事务时也不会是串行的。私有工作空间当一个进程开始一个事务时，会给它一个包含了所有需要访问的文件(包含其他对象)的私有工作空间。在事务提交或终止前所有的读写操作都在私有工作空间而不是在真正的文件系统中进行。拷贝所有数据代价太大，为此使用多种优化方法：如果进程只读取文件，将不拷贝，只是拷贝文件指针；如果进程写入文件，不拷贝数据块，只拷贝文件索引。当文件第一次被修改，将生成该块的拷贝，其地址也将插入索引中。(a)一个有三个数据块的文件的文件索引和磁盘数据块(b)事务修改第0块和附加数据块3后的情况(c)提交以后写前日志写前日志(writeheadlog)也称计划列表(intentionslist)。使用这种方法，文件将真正修改。但在改动任何块之前，将一条记录写入稳定存储器的写前日志中，以判断哪一个事务在进行修改操作，哪一个文件的哪一块被改动，旧值与新值分别是什么。只有当日志成功的写入后才能进行文件修改。x=0;x=0;BEGIN_TRANSACTIONx=x+1;y=y+2;x=y*y;END_TRANSACTION(a)x=0/1x=0/1y=0/2x=0/1x=y/2x=1/4日志两阶段提交协议设立一个协调者进程；开始事务时，协调者写入一条记录表明事务开始；协调进程向每个参与者发送通知让其准备提交；参与者应答就绪消息；协调者根据应答的数目确定是否提交。如果所有参与者都准备好则提交，事务完成；如果某参与者没有准备好，则终止事务。最后，协调者再次向日志中写入记录，表明事务结束。将“准备”写入日志发送“准备”消息收集所有应答写日志记录发送“提交”消息发送“就绪”消息将“就绪”写入日志发送“完成”消息将提交”写入日志阶段1阶段23.4.4并发控制加锁法乐观的并发控制时间戳加锁法当进程需要读写文件时，首先将文件加锁；其他进程访问被加锁文件将被禁止。通过集中式的加锁管理或本地锁程序实现。加锁管理程序拥有一个被锁文件列表，禁止访问此列表中的文件。通过读文件锁和写文件锁区分文件访问类型。读文件锁可共享，写文件锁是互斥的。两阶段加锁：在增长阶段请求所有文件锁，在收缩阶段释放它们。优点：一个事务总是读由另一个已提交的事务写入的值，因此不会因为一个事务的计算是基于它本不应该看到的文件而终止它；所有锁的请求和释放都可以由系统来处理而无须事务关心。可能出现死锁。乐观的并发控制对文件访问不加限制。在重负载时，算法失效的可能性会直线上升。时间戳在事务开始时，分配一个时间戳。根据时间戳的先后次序判断事务是否按顺序访问文件。当一个事务碰到更大(晚)的时间戳时就要终止。利用时间戳不会引起死锁。3.5分布式系统中的死锁通