单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,南京理工大学计算机学院,分布式系统与,WEB,服务,第三章 分布式系统的同步 和进程,第三章 分布式系统的同步 和进程,3,1,时钟同步,分布式算法的主要特征：,相关信息分布在多台机器上,进程仅依据局部的信息作出决定,一台机器的故障不应引起整个系统的失败,没有共用的全局时钟31 时钟同步 分布式算法的主要特征：,1,逻辑时钟,先看一个例子,:,0,6,12,18,24,30,36,42,48,54,60,0,8,16,24,32,40,48,56,64,72,80,0,10,20,30,40,50,60,70,80,90,100,A,B,C,D,三个有自己时钟的进程,时钟不同,运行的结果是消息,C,在时间,60,上被发送,却在时间点,54,上到达,1逻辑时钟000ABCD三个有自己时钟的进程,时钟不同,Lamport,的算法以,”,先于,”,关系,为基础，每个消息都携带它的发送时间,当它到达目的地时，如果目的地的时间早于它的发送时间，那么就把目的地的时间向前拔,至少要比发送时间大,1,个单位,.,0,6,12,18,24,30,36,42,48,70,76,0,8,16,24,32,40,48,61,69,77,85,80,0,10,20,30,40,50,60,70,80,90,100,A,B,C,D,用,Lamport,的算法纠正时钟,Lamport的算法以”先于”关系为基础，每个消,该算法解决了全局时钟问题，它的条件就是两个相关事件之间必须至少相差一个时间,2,时钟同步算法,逻辑时钟只给出事物的相对时间,与真实时间并不对应,故要引入外部物理时钟,常用的时钟同步算法,:,克里司帝安,(CRISTIAN),算法,具有国家标致时间接收器的机器,注意,:,调整的方法,通过调节单位时间内的中断的时间,来逐步完成时钟的调整,.,该算法解决了全局时钟问题，它的条件就,伯克利算法,计算平均时间,它是一个集中式算法,不能在大规模的分布式系统中使用,原理,:,定期轮询每台机器的时间,由结果计算平均时间,各机器依此调整时间,.,3,同步时钟的具体使用,至多一次消息传送,消息的时间戳比存储的时间戳的值早,就拒绝接受该消息,伯克利算法,基于时钟的缓冲存储器（,CACHE,）的一致性,使用,CACHE,会出现一致性问题，原解决的方法,:,区分读写缓存,现在可用同步时钟来解决。
即通过提供有效期（,利用有效的租约）,来控制,CACHE,一致性问题基于时钟的缓冲存储器（CACHE）的一致性,3.2,互斥操作,有多个进程的系统经常会碰到临界区的操作当一个进程要访问某个共享数据时，它要先进人临界区进行互斥操作，确保没有别的进程同时访问该数据在单机系统中，临界区可以用信号灯、管程来实现那么在分布式系统中，由于,不能共享主存,，怎么实现临界区和互斥操作呢,?,下面我们讨论几种算法集中式算法,该方法就是模拟单机系统,指定一个管理员进行许可管理,该算法保证了互斥,每个临界区只需三条消息,(,申请,许可,释放,),3.2 互斥操作 有多个进程的系统经常,1,0,2,OK,请求,C,管理员,队列空,管理员,1,0,2,不回答,请求,C,队列空,1,0,2,OK,释放,C,管理员,队列空,2,(A),进程,1,向管理员请求进入临界区,得到许可,(B),进程,2,向管理员请求进入临界区,管理员不回答,(C),进程,2,向管理员请求进入临界区,管理员许可,缺点,:,集中式算法管理员是系统的瓶颈,102OK请求C管理员队列空管理员102不回答请求C队列空1,分布式算法,算法的条件,:,系统中的事件必须有全局的顺序,算法的工作过程如下,:,当一个进程要进入临界区时，它构造一条包括临界区名、进程号和当前时间的请求消息，然后把该消息广播给其他的所有进程。
这里假设，消息的发送是可靠的当一个进程收到请求后，根据它的状态采取相应的动作：,(1),当接收者不在临界区，并且也不想进入临界区，就应答发送者,OK,消息2),如果接收者已经在临界区中，它不回答仅仅把请求加入队列3),如果接收者不在临界区，但它也想进入临界区，就要将收到消息的时间戳和它广播消息的时间戳比较,.,如果到来的消息时间戳早，接收者回答发送者,OK,消息；反之接收者把到来的请求加入队列，不回答,.,分布式算法,在发完进入临界区请求后，进程将等待所有的允许消息，一旦得到许可，就可进入临界区，当退出时向队列中的所有进程发,OK,消息，并将它从队列中删除所有进程都要参与决定是否进入临界区，若有进程不能做，算法将出错由于所有进程都要参加算法，所以比集中式算法慢，复杂，开销大改进算法：,不需所有进程同意，部分回答,OK,即可,令牌环算法,进程只有拥有令牌时,才能进入临界区,一个进程从相邻的进程收到令牌时先检查自己是非要进入临界区,;,如果要,就进入,否则就将令牌传递给下一个进程,.,缺点,:,令牌可能丢失且检测困难，一个要进入临界区的进程最差情况下要等待其他进程进入和退出临界区所用时间总和,在发完进入临界区请求后，进程将等待所有的允许消息，,三种算法的特点比较,集中式算法简单、高效，每次进入和离开临界区只需,3,次消息传递：,请求、许可；释放,，分布式算法中，,n,个进程需要,(n-1),个请求和,(n-1),个许可，总共要,2(n,1),个消息。
在令牌环算法中，所需的消息数是不固定的如果每个进程都要进入临界区，那么每个令牌都有一次进人和退出，平均每次进入有,个消息传递；如果令牌被一个进程占有很长时间，那么进入临界区需要的消息就不确定进程从它发出进入临界区的请求到它进入临界区的时间延迟在三个算法中是不同的,当临界区很短并且使用频率很低时，进入临界区时间延迟的决定因素是进人临界区的控制机制当临界区很长并且使用的频率很高时，决定因素在于等待时间，消息数就能说明这一点这三种算法出现故障时,都会有很大影响,要避免系统的崩溃,须注意,:,在容错系统中,次三种算法都不适用,.,三种算法的特点比较,3.3,选举算法,在分布式系统中，大多数算法要求有一个进程充当管理员或初始启动者等特殊角色前面几个算法就有这样的例子一般来说，由哪个进程充当特定角色无关紧要，但是必须有一个进程做这个工作下面我们来看如何选一个进程担当特定角色选举算法的目的是当选举完成后，能够让所有的进程知道谁是管理员,.,3.3选举算法 在分布式系统中，大多,1.,霸道算法,该算法提出当一个进程,P,注意到管理员不再对请求作出反应时，它就开始选举进程,P,执行下列步骤：,(1),向所有,进程号比它大,的进程发送,ELECTION,消息；,(2),如果没有进程响应，进程,P,成为管理员；,(3),如果有进程响应，该响应进程成为管理员，,P,结束选举。
注意：,一个进程只能从号码比它小的进程处得到一个选择消息,1.霸道算法,2,0,5,3,6,4,1,7,(A),进程,4,启动选举,2,0,5,3,6,4,1,7,(B),进程,5,6,响应,让,4,停止,2,0,5,3,6,4,1,7,(C),进程,5,6,都启动选举,2,0,5,3,6,4,1,7,(D),进程,6,让进程,5,停止选举,2,0,5,3,6,4,1,7,(E),进程,6,成为管理员,发通知,霸道算法图示,20536417(A)进程4启动选举20536417(B)进,2.,环形算法,这个算法使用环，但不是令牌环这里假定所有的进程都是有序号的，即每个进程都知道它的后继进程当一个进程发现管理员不能工作时，它把包含其进程号的,ELECTION,消息发给它的后继进程；接收消息的进程再向后继进程发送,ELECTION,消息如果接收进程没有反应，发送消息的进程便向下一个进程发消息每一次发送,ELECTION,，进程都要将自己的进程号加入消息2,0,4,6,5,1,3,7,使用环形选举算法,选举消息,选举消息,2,3,2,5,5,6,5,6,0,出现故障的管理员,2.环形算法20465137使用环形选举算法,最后，第一个发出该选举（,ELECTION,）消息进程收到该消息,再将其转换为协调（,COORDINATOR,）消息后，再循环一周,通知谁是管理员，谁是组成员，,这时消息包中进程号最高的进程将成为管理员。
当这个消息循环一周后，由发送进程把它从网上清除图中,2,和,5,都发现,7,失效，分别建立选举消息，两条消息都沿环运行，结果是一样的，只是浪费了带宽最后，第一个发出该选举（ELECTION）消息进程,3,4,线,程,进程因等待而挂起,使进程中可并行部分不能执行,从而使系统性能下降,故引入,-,线程,.,1.,线程：就是可以共享地址空间的轻型进程，它有自己的程序寄记数器栈和寄存器集合它与进程的主要区别是它的地址空间是共享的线程相对于进程，犹如进程相对于机器,2.,线程的使用，将并行性引入到顺序执行的系统,.,多线程组织的常用模型：,34 线 程 进程因等待而挂起,使进程中可,1),分配器工作者模型,有一个分配器线程唤醒工作者线程可用信号灯,2),团队模型,地位平等 线程各自获取和处理自己的请求,.,3),流水线模型,管道线模型，第一个线程产生一些数据传给下一个线程处理，且持续下去多线程可分时工作在单,CPU,上也可工作在多处理器系统上,而且多线程系统设计的好将可与多处理机工作性能相当,.,1)分配器工作者模型,共享缓冲区,到达的工作请求,邮箱,文件服务器进程,分配器线程,工作者线程,到达的工作请求,到达的工作请求,内核,分配器,/,工作者模型,流水线模型,团体模型,进程中线程三种组织方式,共享缓冲区到达的工作请求邮箱文件服务器进程分配器线程工作者线,3.,线程包的设计的相关问题,线程包就是供用户或程序员调用的关于线程的一组原语。
线程的管理方法有静态和动态方法两种静态,即开始就确定好线程的个数,，动态,个数,不定,线程的代码与进程一样，由多个过程组成线程包中临界区控制利用互斥体（,mutex),其总处于：,打开和锁住两种状态,lock mutex;,check data structures lock mutex,while(resource busy)mark resource as free;,wait(condition varable);unlock mutex;,mark resource as busy;wakeuo(condition variable);,unlock mutex;,互斥变量与条件变量的使用,3.线程包的设计的相关问题,线程可由算法进行调度，如优先级调度、循环调度等,4.,线程包的实现,在用户空间实现线程（如图）,这种方法是将线程包完全放在,用户空间,，内核对此一无所知，在这种方法中，内核只是管理普通的单线程进程这种方法最明显的优点,是它可以在一个不支持多线程的操作系统上实现用户线程包同时它还允许每个进程有自己特定的调度算法,.,线,程,1,线,程,2,线,程,3,线,程,4,线,程,5,线,程,6,运行期系统,内 核,内核空间,用户空间,线程可由算法进行调度，如优先级调度、循环调度等线线线线,缺点是：,数量太多会引起资源紧张,.,同时,(1),它也难实现阻塞系统的调用,.,(2),它的调度是非抢先式的,.,进程内部无时钟中断,无法进行时间片的调度,.,2),在操作系统内核实现（如图）,不需要运行系统,线程创建或撤销,只需一次系统调用,比在用户空间实现线程开销大,.,可通过在撤销时加标记，当做为新线程创建时仅需激活即可。
线,程,1,线,程,2,线,程,3,线,程,4,线,程,5,线,程,6,内 核,用户空间,内核空间,缺点是：线线线线线线内 核用户空间内核空间,3),调度员活动方法,结合前两种的优点,(,用户线程的高性能和内核线程的实现简单,),原理：当使用调度员活动方法时，内核给每个进分配。
