分布式系统与WEB服务课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《分布式系统与WEB服务课件.ppt》由用户(晟晟文业)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 分布式 系统 WEB 服务 课件
- 资源描述:
-
1、南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务第三章第三章 分布式系统的同步分布式系统的同步 和进程和进程 南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务31 时钟同步时钟同步 分布式算法的主要特征:分布式算法的主要特征:相关信息分布在多台机器上相关信息分布在多台机器上 进程仅依据局部的信息作出决定进程仅依据局部的信息作出决定 一台机器的故障不应引起整个系统的失败一台机器的故障不应引起整个系统的失败 没有共用的全局时钟。没有共用的全局时钟。南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务1
2、 1逻辑时钟逻辑时钟先看一个例子先看一个例子:06121824303642485460081624324048566472800102030405060708090100ABCD三个有自己时钟的进程三个有自己时钟的进程,时钟不同时钟不同 运行的结果是运行的结果是消息消息C C在时间在时间6060上被上被发送发送,却在时间点却在时间点5454上到达上到达南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务 Lamport Lamport的算法以的算法以”先于先于”关系关系为基础,每个消息都为基础,每个消息都携带它的发送时间携带它的发送时间,当它到达目的地时,如果目的
3、地的时当它到达目的地时,如果目的地的时间早于它的发送时间,那么就把目的地的时间向前拔间早于它的发送时间,那么就把目的地的时间向前拔,至至少要比发送时间大少要比发送时间大1 1个单位个单位.0612182430364248707608162432404861697785800102030405060708090 100ABCD用用LamportLamport的算法的算法纠正时钟纠正时钟南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务 该算法解决了全局时钟问题,它的条件就是两个相关该算法解决了全局时钟问题,它的条件就是两个相关事件之间必须至少相差一个时间事件之间必
4、须至少相差一个时间 2 2时钟同步算法时钟同步算法 逻辑时钟只给出事物的相对时间逻辑时钟只给出事物的相对时间,与真实时间并不对与真实时间并不对应应,故要引入外部物理时钟故要引入外部物理时钟,常用的时钟同步算法常用的时钟同步算法:克里司帝安克里司帝安(CRISTIAN)(CRISTIAN)算法算法 具有国家标致时间接收器的机器具有国家标致时间接收器的机器,注意注意:调整的方法调整的方法,通过调节单位时间内的中断的时间通过调节单位时间内的中断的时间,来逐步完成时钟的调来逐步完成时钟的调整整.南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务 伯克利算法伯克利算法 计
5、算平均时间计算平均时间,它是一个集中式算法它是一个集中式算法,不能在大规模的不能在大规模的分布式系统中使用分布式系统中使用 原理原理:定期轮询每台机器的时间定期轮询每台机器的时间,由结果计算平均时间由结果计算平均时间,各机器依此调整时间各机器依此调整时间.3 3同步时钟的具体使用同步时钟的具体使用 至多一次消息传送至多一次消息传送 消息的时间戳比存储的时间戳的值早消息的时间戳比存储的时间戳的值早,就拒绝接受该就拒绝接受该消息消息南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务 基于时钟的缓冲存储器(基于时钟的缓冲存储器(CACHECACHE)的一致性)的一致性
6、 使用使用CACHECACHE会出现一致性问题,原解决的方法会出现一致性问题,原解决的方法:区分读区分读写缓存写缓存,现在可用同步时钟来解决。即通过提供有效期(现在可用同步时钟来解决。即通过提供有效期(利利用有效的租约)用有效的租约)来控制来控制CACHECACHE一致性问题。一致性问题。南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务3.2 3.2 互斥操作互斥操作 有多个进程的系统经常会碰到临界区的操作。当一个进有多个进程的系统经常会碰到临界区的操作。当一个进程要访问某个共享数据时,它要先进人临界区进行互斥操作,程要访问某个共享数据时,它要先进人临界区进行
7、互斥操作,确保没有别的进程同时访问该数据。在单机系统中,临界区确保没有别的进程同时访问该数据。在单机系统中,临界区可以用信号灯、管程来实现。那么在分布式系统中,由于可以用信号灯、管程来实现。那么在分布式系统中,由于不不能共享主存能共享主存,怎么实现临界区和互斥操作呢,怎么实现临界区和互斥操作呢?下面我们讨论下面我们讨论几种算法。几种算法。集中式算法集中式算法 该方法就是模拟单机系统该方法就是模拟单机系统,指定一个管理员进行许可管理指定一个管理员进行许可管理,该算法保证了互斥该算法保证了互斥,每个临界区只需三条消息每个临界区只需三条消息(申请申请,许可许可,释释放放)南京理工大学计算机学院南京理
8、工大学计算机学院分布式系统与分布式系统与WEB服务服务1 10 02 2OKOK请求请求C C管理员管理员队列空队列空管理员管理员1 10 02 2不回答不回答请求请求C C队列空队列空1 10 02 2OKOK释放释放C C管理员管理员队列空队列空2 2 (A)(A)进程进程1 1向管理员请求向管理员请求进入临界区进入临界区,得到许可得到许可 (B)(B)进程进程2 2向管理员请求进向管理员请求进入临界区入临界区,管理员不回答管理员不回答 (C)(C)进程进程2 2向管理员请求进向管理员请求进入临界区入临界区,管理员许可管理员许可缺点缺点:集中式算法管理员是系统的瓶颈集中式算法管理员是系统的
9、瓶颈南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务 分布式算法分布式算法 算法的条件算法的条件:系统中的事件必须有全局的顺序系统中的事件必须有全局的顺序 算法的工作过程如下算法的工作过程如下:当一个进程要进入临界区时,它构造一条包括临界区名、进程号和当一个进程要进入临界区时,它构造一条包括临界区名、进程号和当前时间的请求消息,然后把该消息广播给其他的所有进程。这里假设,当前时间的请求消息,然后把该消息广播给其他的所有进程。这里假设,消息的发送是可靠的。消息的发送是可靠的。当一个进程收到请求后,根据它的状态采取相应的动作:当一个进程收到请求后,根据它的状态采取
10、相应的动作:(1)(1)当接收者不在临界区,并且也不想进入临界区,就应答发送者当接收者不在临界区,并且也不想进入临界区,就应答发送者OKOK消消息。息。(2)(2)如果接收者已经在临界区中,它不回答仅仅把请求加入队列。如果接收者已经在临界区中,它不回答仅仅把请求加入队列。(3)(3)如果接收者不在临界区,但它也想进入临界区,就要将收到消息的时如果接收者不在临界区,但它也想进入临界区,就要将收到消息的时间戳和它广播消息的时间戳比较间戳和它广播消息的时间戳比较.如果到来的消息时间戳早,接收者回答如果到来的消息时间戳早,接收者回答发送者发送者OKOK消息;反之接收者把到来的请求加入队列,不回答消息;
11、反之接收者把到来的请求加入队列,不回答.南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务 在发完进入临界区请求后,进程将等待所有的允许消息,一旦得到许可,在发完进入临界区请求后,进程将等待所有的允许消息,一旦得到许可,就可进入临界区,当退出时向队列中的所有进程发就可进入临界区,当退出时向队列中的所有进程发OKOK消息,并将它从队列消息,并将它从队列中删除。中删除。所有进程都要参与决定是否进入临界区,若有进程不能做,算法将出错。所有进程都要参与决定是否进入临界区,若有进程不能做,算法将出错。由于所有进程都要参加算法,所以比集中式算法慢,复杂,开销大。由于所有进程
12、都要参加算法,所以比集中式算法慢,复杂,开销大。改进算法:改进算法:不需所有进程同意,部分回答不需所有进程同意,部分回答OKOK即可即可 令牌环算法令牌环算法 进程只有拥有令牌时进程只有拥有令牌时,才能进入临界区才能进入临界区,一个进程从相邻的进程一个进程从相邻的进程收到令牌时先检查自己是非要进入临界区收到令牌时先检查自己是非要进入临界区;如果要如果要,就进入就进入,否则否则就将令牌传递给下一个进程就将令牌传递给下一个进程.缺点缺点:令牌可能丢失且检测困难,一个要进入临界区的进程最令牌可能丢失且检测困难,一个要进入临界区的进程最差情况下要等待其他进程进入和退出临界区所用时间总和差情况下要等待其
13、他进程进入和退出临界区所用时间总和南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务 三种算法的特点比较三种算法的特点比较 集中式算法简单、高效,每次进入和离开临界区只需集中式算法简单、高效,每次进入和离开临界区只需3 3次消息传递:次消息传递:请求、许可;释放请求、许可;释放,分布式算法中,分布式算法中,n n个进程需要个进程需要(n-1)(n-1)个请求和个请求和(n-1)(n-1)个许可,总共要个许可,总共要2(n2(n1)1)个消息。在令牌环算法中,所需的消息数是不个消息。在令牌环算法中,所需的消息数是不固定的。如果每个进程都要进入临界区,那么每个令牌都
14、有一次进人和固定的。如果每个进程都要进入临界区,那么每个令牌都有一次进人和退出,平均每次进入有退出,平均每次进入有个消息传递;如果令牌被一个进程占有很长时个消息传递;如果令牌被一个进程占有很长时间,那么进入临界区需要的消息就不确定。间,那么进入临界区需要的消息就不确定。进程从它发出进入临界区的请求到它进入临界区的时间延迟在三个进程从它发出进入临界区的请求到它进入临界区的时间延迟在三个算法中是不同的算法中是不同的,当临界区很短并且使用频率很低时,进入临界区时间当临界区很短并且使用频率很低时,进入临界区时间延迟的决定因素是进人临界区的控制机制当临界区很长并且使用的频延迟的决定因素是进人临界区的控制
15、机制当临界区很长并且使用的频率很高时,决定因素在于等待时间,消息数就能说明这一点。率很高时,决定因素在于等待时间,消息数就能说明这一点。这三种算法出现故障时这三种算法出现故障时,都会有很大影响都会有很大影响,要避免系统的崩溃要避免系统的崩溃,须注须注意意:在容错系统中在容错系统中,次三种算法都不适用次三种算法都不适用.南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务3.3选举算法选举算法 在分布式系统中,大多数算法要求有一个进程充当管在分布式系统中,大多数算法要求有一个进程充当管理员或初始启动者等特殊角色。前面几个算法就有这样的理员或初始启动者等特殊角色。前面
16、几个算法就有这样的例子。一般来说,由哪个进程充当特定角色无关紧要,但例子。一般来说,由哪个进程充当特定角色无关紧要,但是必须有一个进程做这个工作。下面我们来看如何选一个是必须有一个进程做这个工作。下面我们来看如何选一个进程担当特定角色。进程担当特定角色。选举算法的目的是当选举完成后,能够让所有的进程知道选举算法的目的是当选举完成后,能够让所有的进程知道谁是管理员谁是管理员.南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务 1.霸道算法霸道算法 该算法提出。当一个进程该算法提出。当一个进程P P注意到管理员不再对请求作出反注意到管理员不再对请求作出反应时,它就开
17、始选举进程应时,它就开始选举进程P P执行下列步骤:执行下列步骤:(1)(1)向所有向所有进程号比它大进程号比它大的进程发送的进程发送ELECTIONELECTION消息;消息;(2)(2)如果没有进程响应,进程如果没有进程响应,进程P P成为管理员;成为管理员;(3)(3)如果有进程响应,该响应进程成为管理员,如果有进程响应,该响应进程成为管理员,P P结束选举。结束选举。注意:注意:一个进程只能从号码比它小的进程处得到一个选择一个进程只能从号码比它小的进程处得到一个选择消息消息南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务2 20 05 53 36 64
18、 41 17 7(A)(A)进程进程4 4启动选举启动选举2 20 05 53 36 64 41 17 7(B)(B)进程进程5,65,6响应响应,让让4 4停止停止2 20 05 53 36 64 41 17 7(C)(C)进程进程5,6,5,6,都启动都启动选举选举2 20 05 53 36 64 41 17 7(D)(D)进程进程6 6让进程让进程5 5停停止选举止选举2 20 05 53 36 64 41 17 7(E)(E)进程进程6 6成为管理员成为管理员,发通知发通知霸道算法图示霸道算法图示南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务 2.环
19、形算法环形算法 这个算法使用环,但不是令牌环。这个算法使用环,但不是令牌环。这里假定所有的进程都这里假定所有的进程都是有序号的,即每个进程都知道它的后继进程。当一个进程是有序号的,即每个进程都知道它的后继进程。当一个进程发现管理员不能工作时,它把包含其进程号的发现管理员不能工作时,它把包含其进程号的ELECTIONELECTION消息消息发给它的后继进程;接收消息的进程再向后继进程发送发给它的后继进程;接收消息的进程再向后继进程发送ELECTIONELECTION消息。如果接收进程没有反应,发送消息的进程便消息。如果接收进程没有反应,发送消息的进程便向下一个进程发消息。每一次发送向下一个进程发
20、消息。每一次发送ELECTIONELECTION,进程都要将自,进程都要将自己的进程号加入消息。己的进程号加入消息。2 20 04 46 65 51 13 37 7使用环形选举算法使用环形选举算法选举消息选举消息选举消息选举消息2 23 32 25 55 56 65 56 60 0 出现故障的出现故障的管理员管理员南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务 最后,第一个发出该选举(最后,第一个发出该选举(ELECTIONELECTION)消息进程收到该消息)消息进程收到该消息,再将其转换为协调(再将其转换为协调(COORDINATORCOORDINATO
21、R)消息后,再循环一周)消息后,再循环一周,通通知谁是管理员,谁是组成员,知谁是管理员,谁是组成员,这时消息包中进程号最高的进这时消息包中进程号最高的进程将成为管理员。程将成为管理员。当这个消息循环一周后,由发送进程把它当这个消息循环一周后,由发送进程把它从网上清除。从网上清除。图中图中2 2和和5 5都发现都发现7 7失效,分别建立选举消息,两条消息都失效,分别建立选举消息,两条消息都沿环运行,结果是一样的,只是浪费了带宽。沿环运行,结果是一样的,只是浪费了带宽。南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务34 线线 程程 进程因等待而挂起进程因等待而挂
22、起,使进程中可并行部分不能执行使进程中可并行部分不能执行,从而从而使系统性能下降使系统性能下降,故引入故引入-线程线程.1.1.线程:就是可以共享地址空间的轻型进程,它有自己线程:就是可以共享地址空间的轻型进程,它有自己的程序寄记数器栈和寄存器集合。的程序寄记数器栈和寄存器集合。它与进程的主要区别是它它与进程的主要区别是它的地址空间是共享的。的地址空间是共享的。线程相对于进程,犹如进程相对于机器线程相对于进程,犹如进程相对于机器 2.2.线程的使用,将并行性引入到顺序执行的系统线程的使用,将并行性引入到顺序执行的系统.多线程组织的常用模型:多线程组织的常用模型:南京理工大学计算机学院南京理工大
23、学计算机学院分布式系统与分布式系统与WEB服务服务 1)1)分配器工作者模型分配器工作者模型 有一个分配器线程唤醒工作者线程可用信号灯有一个分配器线程唤醒工作者线程可用信号灯 2)2)团队模型团队模型 地位平等地位平等 线程各自获取和处理自己的请求线程各自获取和处理自己的请求.3)3)流水线模型流水线模型 管道线模型,第一个线程产生一些数据传给下一个线管道线模型,第一个线程产生一些数据传给下一个线程处理,且持续下去。程处理,且持续下去。多线程可分时工作在单多线程可分时工作在单CPUCPU上也可工作在多处理器系上也可工作在多处理器系统上统上,而且多线程系统设计的好将可与多处理机工作性能而且多线程
24、系统设计的好将可与多处理机工作性能相当相当.南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务共享缓冲区共享缓冲区到达的工作请求到达的工作请求邮箱邮箱文件服务器进程文件服务器进程分配器线程分配器线程工作者线程工作者线程到达的工作请求到达的工作请求到达的工作请求到达的工作请求内核内核分配器分配器/工作者模型工作者模型流水线模型流水线模型团体模型团体模型进程中线程三种组织方式进程中线程三种组织方式南京理工大学计算机学院南京理工大学计算机学院分布式系统与分布式系统与WEB服务服务3.3.线程包的设计的相关问题线程包的设计的相关问题线程包就是供用户或程序员调用的关于线程
25、的一组原语。线程包就是供用户或程序员调用的关于线程的一组原语。线程的管理方法有静态和动态方法两种。线程的管理方法有静态和动态方法两种。静态静态即开始就确定好线程的个数即开始就确定好线程的个数,动态,动态个数个数不定不定 线程的代码与进程一样,由多个过程组成。线程的代码与进程一样,由多个过程组成。线程包中临界区控制利用互斥体(线程包中临界区控制利用互斥体(mutex),mutex),其总处于:其总处于:打开和锁住两种状态打开和锁住两种状态 lock mutex;lock mutex;check data structures lock mutex check data structures lo
展开阅读全文