分布式系统时钟同步讲述.pptx

同 步;1.时钟同步;引入 时钟同步;引入 时钟同步;引入 时钟同步;引入 时钟同步;引入 时钟同步;引入 时钟同步;引入 时钟同步;引入 时钟同步;分布式系统 时钟同步;分布式系统 时钟同步;分布式系统 时钟同步;分布式系统 时钟同步;分布式系统 时钟同步;物理时钟;引入 时钟同步算法;时钟同步算法;时钟同步算法;时钟同步算法;时钟同步算法;时钟同步算法：Cristian 算法;时钟同步算法：Cristian 算法;时钟同步算法：Cristian 算法;时钟同步算法：Cristian 算法;时钟同步算法：Berkeley算法;时钟同步算法：Berkeley算法;时钟同步算法：Berkeley算法;时钟同步算法：Berkeley算法;时钟同步算法：平均值算法;时钟同步算法：平均值算法;2.逻辑时钟;逻辑时钟;逻辑时钟同步; Lamport 时间戳 为了同步逻辑时钟，Lamport定义了一个称作“先发生”的关系。 ;事件a先发生，然后b才发生 如果a和b是同一个进程的两个事件，如果a在b之前发生，则a→b为真 如果a是一个进程发生消息的事件， b是另一个进程的接收消息事件，则a→b也为真 先发生关系是一个传递关系，若a→b且b→c ，则a→c 。 ; 如果x和y事件发生在两个互不交换消息的进程中， x→y不真， y→x也不真。 这两个事件称为并发的，意味着无法说这两个事件什么时候发生，哪个事件先发生。; Lamport 时间戳 我们需要一种测量时间的方法，使得对于每个时间a，我们都能为它分配一个所有进程都认可的时间值C(a)。 这些时间值必须具有如下性质：如果a→b，那么C(a) C(b)。 若在同一进程中a在b之前发生，则C(a) C(b) 。 若a和b分别表示发送一个消息和接收该消息的事件，则C(a) C(b) 。; Lamport 时间戳 时间值C是一直向前走的（即增加），不会向后退（即减少）。 校正时间的操作总是给时间加上一个正值，而不能是减掉一个正值，时间的修改只能增加而不能减少。;在a)中有三个进程。 每一个进程都运行 在不同的机器上。 每一个机器都有一个自己的时钟。 并且以各自的速度向前走。 ;当进程0中的时钟滴答6次时； 进程1滴答了8次； 进程3滴答10次。 ;在时间为6时，进程0发送了一个消息A给进程1，进程1在时间为16时收到了消息。 如???消息中含有消息开始发送的时间值6，则进程1认为该消息的传输花费了10次滴答。 ;同理，消息B从进程1传输到进程2花费了16次滴答 ;但是，由进程2发送给进程1的消息C在发送时的时间值为60而在接收时时间值为56。 这样，消息C的传输时间为负值。 ;Lamport 算法 算法基本思想;因此 消息C到达进程1的时间改为61 消息D到达进程0的时间改为70。 ; Lamport算法还需满足一个要求： 任意两个事件的时间之差至少为1。如果一个进程连续发送或接受两个消息，则这两个消息的时间之差也至少为1。; 我们对不同进程内两个同时发生的事件是这样赋时间值的： 事件发生的时间值与该事件所属进程的进程号连接起来，中间用“.”加以分隔。 例如，进程1和进程2中两个事件恰好同时在时间为40时发生。进程1中的事件发生时间为40.1，而进程2中的事件发生时间为40.2 ;?;Thanks!