文档介绍：第三章 分布式系统同时 和进程
第1页
3．1 时钟同时
分布式算法主要特征：
①相关信息分布在多台机器上
②进程仅依据局部信息作出决定
③一台机器故障不应引发整个系统失败
缺点:令牌可能丢失且检测困难，一个要进入临界区进程最差情况下要等候其它进程进入和退出临界区所用时间总和
第11页
④三种算法特点比较
集中式算法简单、高效，每次进入和离开临界区只需3次消息传递：请求、许可；释放，分布式算法中，n个进程需要(n-1)个请求和(n-1)个许可，总共要2(n—1)个消息。在令牌环算法中，所需消息数是不固定。假如每个进程都要进入临界区，那么每个令牌都有一次进人和退出，平均每次进入有—个消息传递；假如令牌被一个进程占有很长时间，那么进入临界区需要消息就不确定。
进程从它发出进入临界区请求到它进入临界区时间延迟在三个算法中是不一样,当临界区很短而且使用频率很低时，进入临界区时间延迟决定原因是进人临界区控制机制．当临界区很长而且使用频率很高时，决定原因在于等候时间，消息数就能说明这一点。
这三种算法出现故障时,都会有很大影响,要防止系统瓦解,须注意:在容错系统中,次三种算法都不适用.
第12页
在分布式系统中，大多数算法要求有一个进程充当管理员或初始开启者等特殊角色。前面几个算法就有这么例子。普通来说，由哪个进程充当特定角色无关紧要，不过必须有一个进程做这个工作。下面我们来看怎样选一个进程担当特定角色。
选举算法目标是当选举完成后，能够让全部进程知道谁是管理员.
第13页
1. 霸道算法
该算法提出。当一个进程P注意到管理员不再对请求作出反应时，它就开始选举．进程P执行以下步骤：
(1)向全部进程号比它大进程发送ELECTION消息；
(2)假如没有进程响应，进程P成为管理员；
(3)假如有进程响应，该响应进程成为管理员，P结束选举。
注意：一个进程只能从号码比它小进程处得到一个选择消息
第14页
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成为管理员,发通知
霸道算法图示
第15页
2. 环形算法
这个算法使用环，但不是令牌环。这里假定全部进程都是有序号，即每个进程都知道它后继进程。当一个进程发觉管理员不能工作时，它把包含其进程号ELECTION消息发给它后继进程；接收消息进程再向后继进程发送ELECTION消息。假如接收进程没有反应，发送消息进程便向下一个进程发消息。每一次发送ELECTION，进程都要将自己进程号加入消息。
2
0
4
6
5
1
3
7
使用环形选举算法
选举消息
选举消息
2
3
2
5
5
6
5
6
0
出现故障管理员
第16页
最终，第一个发出该选举（ELECTION）消息进程收到该消息,再将其转换为协调（COORDINATOR）消息后，再循环一周,通知谁是管理员，谁是组组员，这时消息包中进程号最高进程将成为管理员。当这个消息循环一周后，由发送进程把它从网上去除。
图中2和5都发觉7失效，分别建立选举消息，两条消息都沿环运行，结果是一样，只是浪费了带宽。
第17页
3．4 线 程
进程因等候而挂起,使进程中可并行部分不能执行,从而使系统性能下降,故引入---线程.
1. 线程：就是能够共享地址空间轻型进程，它有自己程序寄记数器栈和存放器集合。它与进程主要区分是它地址空间是共享。
线程相对于进程，如同进程相对于机器
2. 线程使用，将并行性引入到次序执行系统.
多线程组织惯用模型：
第18页
1)分配器／工作者模型
有一个分配器线程唤醒工作者线程可用信号灯
2)团体模型
地位平等 线程各自获取和处理自己请求.
3)流水线模型
管道线模型，第一个线程产生一些数据传给下一个线程处理，且连续下去。