信息与通信os之分布式系统中的同步问题.pptx

时钟同步例子;二、逻辑时钟(1);二、逻辑时钟(2);二、逻辑时钟(3);并发事件：;时钟时间C必须向前（不断增加），不能后退（减小） 对时间的更新，只能是在时钟上加一个正数，不能减正数;;例子说明(1);设，计时器每秒生成60次中断，每次中断称为一个时钟嘀嗒 从进程2发送该进程1的消息C，其发送时刻为60，到达时刻为56 同样，从进程1到进程0的消息D，其发送时刻为64，到达时刻为54 这显然是不可能的，也是必须避免出现的情况;消息c的发送时间为60，它的到达时间一定在时刻61或61之后 让每条消息??携带发送者时钟的发送时刻 当消息到达接收时，如果接收者的时钟指示值先于发送消息的时间 接受者的时钟值就应快于消息发送时刻加1之后时间值;Lamport算法(5)：;附加条件, 没有两个事件是精确地在同一时刻发生的： 1.在同一进程中，如果a在b前面发生， 那么C(a)C(b) 2.如果a与b分别代表消息的发送和接收， 那么C(a)C(b) 3.对于所有的事件a与b而言，C(a)≠C(b);算法给出系统中所有事件的整体定序方法 该算法在学术界中得到广泛认同;三、时钟(1);原子钟可以准确度量时间 世界时（Universal Coordinated Time）简称UTC UTC是现代计时的基础 National Institute of Standard Time NIXT, 国家标准时间组织短波电台，WWV 每个UTC秒的起始时刻，WWV就发送一个短脉冲 WWV本身的误差大约为+-1毫秒;四、时钟同步算法;时钟同步算法的基本模型(1);理论上，当H = 60时，计时器应每小时生成216,000次ticks 实际上，计时器芯片的相对误差大约为10-5， 即每小时的tick数的范围为215,998到216,002 准确地说，如果存在一个常数p 1 - ρ≤ dC/dt ≤ 1 + ρ 成立，就可以认为计时器是正常工作的;如果两个时钟偏离UTC的方向相反 那么在同步之后的△t时刻时 它们的时差为2ρ△t 要保证两个时钟间时间差不超过δ 必须至少每隔δ/2ρ秒重新同步;Cristian算法(1);Cristian算法(2);Cristian算法(3);Cristian算法(4);Cristian算法(5);Cristian算法(6);Berkeley UNIX算法(1);Berkeley UNIX算法(2);五、互斥问题;1. 集中式算法;集中式算法基本思路;;集中式算法评价;2. 分布式算法(1);;分布式算法(2);分布式算法(3);分布式算法(4);分布式算法评价;分布式算法评价(2);3. 令牌环网算法(1);令牌环网算法(2);;令牌环网算法评价(1);令牌环网算法评价(2);令牌环网算法评价(3);六、典型选举算法：威力(Bully)算法;威力(Bully)算法(1);威力(Bully)算法(2);威力(Bully)算法(3);威力(Bully)算法(4);威力(Bully)算法(5);七、原子事务;;修改在线数据库的银行应用程序(1);修改在线数据库的银行应用程序(2);修改在线数据库的银行应用程序(3);1. 事务模型;;稳定存储器的实现(1);稳定存储器的实现(2);稳定存储器的实现(3);事务原语(1);事务原语(2);事务原语(3)航班订票系统;事务原语属性(1);事务原语属性(2);事务原语属性(3);事务原语属性(3);嵌套事务;事务管理措施 ;2. 原子事务实现-私有工作空间(1);;私有工作空间(2);私有工作空间(2);原子事务实现 - 写前日志(1);x = 0; y = 0; Begin_transaction x = x + 1; y = y + 2; x = y * y; End_transcation;原子事务实现 - 写前日志(1);两段提交协议(1);两段提交协议(2);;两段提交协议(3); 两段提交协议(4);两段提交协议(5);八、并发控制;1.并发控制 - 加锁;最简单的加锁形式;并发控制 - 加锁的改进;读操作锁;写操作锁;加锁的粒度;2. 两段加锁方法;两段加锁;两段加锁方法被广泛应用的原因;严格的两段加锁机制;两段加锁的优点 ;九、常用的避免死锁的方法(1);常用的避免死锁的方法(2);并发控制优化;优化的并发控制方法(1);优化的并发控制方法(2);1. 时间戳(1);时间戳(2);;;时间戳(3);十、分布式系统中的死锁;资源死锁;处理死锁的通用策略：;1. 分布式死锁的检测;集中式死锁检测方法(1);集中式死锁检测方法(2);;虚假死锁 (1);虚假死锁 (2);2