分布式系统与WEB服务(2)

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