第6章 高级操作系统同步化

1、第第6章章 同步化 2主要内容6.1 物理时钟同步6.2 逻辑时钟同步6.3 互斥控制6.4 选举算法36.1物理时钟同步n分布式协同处理n基于时间的同步n分布式算法的特点相关信息散布在多个场地上每个进程只能基于本地信息做决定应避免因单点失败造成整个系统的失败不存在公共时钟或精确的全局时间4时钟同步问题n例：makefile误差时间时间#脚本命令output.o ： cc C output.c5遥远的星系遥远的星系在n天后的日中天，地球旋转不到360物理时钟与现实时钟n日中天（transit of the sun）：太阳升到一天的最高点n太阳日：连续的两次日中天的时间n太阳年：地球围绕太阳旋转

2、360（一周）。n太阳秒：solar-day/24*3600=solar-day/86400n平均太阳秒：n solar-days/n*86400n如，格林威治时间第0个日中天第n个日中天6现实时钟nTAI秒：国际原子时间n铯133原子钟：9,192,631,770次跃迁/1秒n巴黎BIH统计50个实验室原子钟后的平均值nUTC秒：世界时间n在UTC秒中加入闰秒（TAI秒长度恒定，但比太阳秒长度少）n时间服务：n美国WWV电台(NIST)、GEOS卫星1020为了与TAI保持同步，在UTC中引入闰秒7例：时间的应用-GPS全球定位系统nGPS卫星n使用4个原子时钟n周期地广播定位消息n即，n接

3、收器n接收di = c(tnow ti)d =di+crd = r 时钟误差22)()(ririyyxx(1)(2)(3)8例：GPS全球定位系统n求解方程组（扩展到3维，需4颗卫星）n可求出（xr,yr,zr）,以及rn误差因素n卫星的位置n卫星、接收器的时钟精度；n信号传播速度4rr424243rr323232rr222221rr12121d)zz()()(d)zz()()(d)zz()()(d)zz()()(rrrrrrrryyxxyyxxyyxxyyxx9时钟同步算法如何与现实时钟同步如何使不同机器之间相互同步n设进程P的机器时钟值Cp(t),nt 为UTC时间n最大偏移率（）n精确时

4、钟： dC/dt =1n快时钟： dC/dt 1n慢时钟： dC/dt 110时钟同步算法时钟校正n设两个时钟都存在误差率，允许两者之间误差；n由于最大可能误差2t ，则t /2n需每隔/(2)校准时间，进行校正n校准原则：单调递增n假设：每秒产生100次中断，每次中断将时间加10毫秒n若调慢时钟，中断服务程序每次只加9毫秒；n若加快时钟，则加11毫秒。11网络时间协议nChristian算法n时间服务器，可接受WWV的UTC时间n每隔/(2)，客户机向服务器询问时间n服务器返回CUTCn客户机校正自己时间=CUTC+传播时间n传播时间=(T1-T0-I)/2nT0:请求时间，T1:到达时间n

5、I:中断处理时间n假定双向路径相同n优化处理n设定传播阈值,超出阈值，认定无效12网络时间协议n时间服务请求过程参数n假定双向路径相同nT1:A请求时间， T2:B接收时间nT3:B发送时间， T4:A接收时间n传输延时 = dTreqdTresn时间偏差nT1=T2 - dTreq + nT4=T3+dTres+ n平均延时=(dTreq+dTres)/2 n=T4-T3-dTres=T4 -T3 - =时间服务器客户2)TT()TT(2)TT()TT(341234122)TT()TT(342113Berkeley 算法 主动式方法1.时间监控器定期查询其他机器时间2.计算出平均值3.通知其

6、他机器调整时间14无线网络中的时钟同步q 参考广播同步协议（RBS）普通的网络延时关键路径RBS的网络延时关键路径15无线网络中的时钟同步q 参考广播同步协议（RBS）q 一个节点广播一个消息m后，其他节点p记录接收时间Tp,mMTTqpMkkqkp1,)(,偏差166.2 逻辑时钟同步n计时器：石英晶体+计数器n时钟偏差（clock skew）n物理时钟：真实时间n逻辑时钟：相对时间n“之前”关系: n事件a在b之前出现，则abna为发送消息m，b为接收m，则abn具有传递性：ab, bc,则acn并发事件（concurrent）n两个事件相互对立。既不ab，不 b a17Lamport算法

7、nC(a)表示事件a的时钟值。性质：nif ab;则C(a)C(b)na,b C(a) C(b)nC是递增的n校正算法nab，nif C(b)C(a), 则C(b) = C(a) +118Lamport算法时时间间慢慢快快慢慢快快a)三个进程，各有自己的局部时钟，它们速率不同b)通过Lamport算法，校正时钟19Lamport算法Pi在执行一个事件之前，Pi执行CiCi+1Pi在发送消息m给Pj时，时间戳ts(m) CiPj接受到消息m后，CjmaxCj，ts(m)20举例：全序多播（1）n 问题：两个进程分别对同一个复制数据库进行更新时，造成不一致状态n 原因：全局次序不一致。u1u2;

8、u2u121举例：全序多播（2）n解决方案：全序多播n发送进程多播发送消息m时，给m带上当前时间戳tsn当接收进程收到消息m后，存放其局部队列q，按时间戳排序n接收进程向所有进程多播发送应答n当消息m被所有进程应答，且排在队列q队首后，方可处理n定理：各个进程的局部队列的值最终都相同22举例：全序多播（3）n举例q1q2u1u2(1)u1u2u1u2(2）u1u2a11u1u2a22(3)q1q2u1u2a11a22u1u2a11a22(4)u1u2a11a22a12u1u2a11a22a21(5)q1q2u1u2a11a22a12a21u1u2a11a22a12a21(6)a11, a22本

9、地消息a12,a21远地消息23向量时钟n因果性(causality):n如果事件a，b存在因果关系。a为因，b为果，则C(a)C(b)nVector Clockn如果VC(a)n/2个协作者中获得多数投票。n通信量：3mk个消息，k表示可能需要进行多次尝试。n优点：当某个协作者崩溃时，能快速恢复n缺点：重置会导致协作者忘记它前面已授权某进程访问资源的许可，在其恢复后，可能错误地把该许可又赋给另外一个进程。31分布式算法（Ricart-Agrawala算法）1.在一个进程P打算进入临界区R之前，向所有其他进程广播消息 2.当一个进程P收到消息后，做如下决定：若P不在临界区R中，也不想进入R，它

10、就向P发送OK；若P已经在临界区R中，则不回答，并将P放入请求队列；若P也同时要进入临界区R，但是还没有进入时，则将发来的消息和它发送给其余进程的时间戳对比。如果P时间戳小，则向P发送OK;否则，不回答，并将P放入请求队列；3.当P收到所有的OK消息后，进入R。否则，等待。4.当P退出R时，如果存在等待队列，则取出一个请求者，向其发送OK消息。32分布式算法举例举例： 共有0，1，2三个进程。进程0，2申请进入临界区02002233分布式算法评价n缺点：n点失败n点瓶颈2（n-1)个消息n改进方案：n超时重发n组通信n简单多数同意（1/2）34令牌环算法构造一个逻辑环，得到令牌才可进入临界区问

11、题：令牌丢失检测35三种互斥算法的比较算法每次进出需要的消息进入前的延迟（按消息次数）存在问题集中式32协调者崩溃分布式2（n-1）2（n-1）任何一个进程崩溃令牌环1到0到n-1丢失令牌，进程崩溃366.4 选举算法n作用：n在分布式进程之间做出统一的的决定n例如：确定协调者n前提：n每个进程具有唯一的号码，如IP地址n每个进程知道其它进程的号码n选举标准：n确定具有最大号码的进程37霸道（Bully）算法v将进程进行排序P向高的进程发E消息如果没有响应，P选举获胜如果有进程Q响应,则P结束，Q接管选举并继续下去。45656465638环算法n所有进程按逻辑或物理次序排序，形成一个环1.当一

12、个进程P发现协调者C失效后，向后续进程发送E消息2.每个进程继续向后传递E消息，直到返回P3.P再将新确定的协调者C传给所有进程5239无线网络系统的选举算法n例：选举一个协调者，它具有最大的能力n1、发起者，提出选举40无线网络系统的选举算法n2、向邻居节点扩展，形成一个生成树（spanning tree）41无线网络系统的选举算法n3、沿生成树向父节点返回i，cmax，cmax为最大值n4、发起者，向其余节点发布协调者42大型系统的选举n大型系统中需要选举多个节点n如p2p系统中的超级节点n对如何选择超级节点（superpeer）的要求:u普通节点对超级节点的访问延迟要小u超级节点应均匀地分布在覆盖网络中u相对于覆盖网络中的节点数量，应有一定数量的预先定义好的超级节点u每个超级节点所服务的普通节点个数不能超过规定