第5章分布式系统的同步.pptVIP

分布式系统同步算法 分布式系统进程同步 逻辑时钟 Lamport算法 物理时钟 Cristian算法 Berkeley算法 同步基本含义 同步是指两个或两个以上随时间变化的量在变化过程中保持一定的相对关系。 当两个设备一起工作并对时间有精确要求的时候，就需要在它们之间进行同步。同步是基于在两个设备之间规定一个共同的时间参考。 数据库同步的含义就是让两个或多个数据库内容保持一致，或者按需要部分保持一致。 文件同步的含义就是让两个或多个文件夹里的文件保持一致，或者按需要部分保持一致。 网络通信编程中常提到的“同步”，则主要指某函数的执行方式，即函数调用者需等待函数执行完成后才能进到下一步。 “同步通信”的通信双方必须先建立同步，即双方的时钟要调整到同一个频率。收发双方不停地发送和接收连续的同步比特流。 5.1分布式系统时钟同步 在分布式系统中： 进程之间的通信：采用消息传递(Message-passing) 进行通信。 与进程通信密切相关的问题：进程之间的协作和同步。 5.1分布式系统时钟同步 分布式系统中的同步比单机系统中的同步要复杂的多,这是由分布式算法决定的: 1.相关的信息是分布在多个机器上的。 2.进程根据局部信息来作出决定。 3.对系统中任一个机器的失败应能容错。 4.不存在公共时钟或其它全局时间源。 5.1分布式系统时钟同步 由一个机器收集所有的信息进行处理是不可能的。在分布式系统中必将造成某一个进程负担过重。 分布式系统应该比单机系统更可靠。如果一个机器崩溃了,其余的机器应能继续工作,而不至于使系统瘫痪。 在单机系统中,时间是确定的。如果一个进程想要知道时间,则它可以调用一个系统调用由内核告诉它当前的时间值。如果一个进程先得到时间值而另一个进程后得到时间值,那么,先得到的时间值一定比后得到的时间值小。 在分布式系统中,所有机器要在时间上达到一致是非常困难的。 5.1分布式系统时钟同步 在分布式系统中缺乏全局时间产生不良影响的例子： Unix中make程序的调用问题。假设实现程序编辑功能的进程与实现程序编译功能的进程在不同的两台计算机上运行。 Make程序的功能：自动完成对源文件的编译 Make工具最主要也是最基本的功能就是通过makefile文件来描述源程序之间的相互关系并自动维护编译工作 通常,一个大程序分成多个源文件。这样,对其中某一个文件的修改只需要对被修改的这个文件进行重编译,而无须对所有的源文件进行编译。 当调用make程序时，Make程序根据所有源文件和对应目标文件的修改时间来决定是否对某个源文件重新编译。 如果源文件input.c的修改时间为5155且对应目标文件input.o的修改时间为5151,那么,make程序知道input.c已被修改。input.c必须被重新编译。 如果output.c的修改时间为5144且对应目标文件output.o的修改时间为5145,则不需要对output.c进行重新编译。 Make程序在考察完所有源文件和其对应目标文件的修改时间后决定那些文件需要重新编译并调用编译器对其进行编译。 5.1分布式系统时钟同步 在分布式环境中,由于时间不同步造成程序不能正常运行： 假定output.o的修改时间为5144,output.c被修改并被赋予的时间为5143,原因是output.c所在机器上的时钟要比output.o所在机器上的时钟慢。 make程序不调用编译器进行编译。 结果,最终可执行二进制程序将含有由新老源文件所生成的目标文件，导致该可执行程序无法运行而程序员却不知道原因而一直寻找程序代码的错误。 结论：在分布式系统中，时钟同步是非常重要的，也是必不可少的。 时钟同步问题 例：makefile误差 5.1分布式系统时钟同步 5.1.1 逻辑时钟同步算法 在分布式系统中，n台计算机上的时钟值都不相同。因此,需要一种方法将所有机器上的时钟进行同步。 Lamport在1978年指出时钟同步是可能的并提出了一个逻辑时钟同步算法。在1990年,Lamport扩展了他的工作。Lamport指出时钟的同步不是绝对的。如果两个进程并不交互,则它们的时钟就无须同步。 逻辑时钟同步算法 系统中的进程不需要在事件发生的确切时间上达成一致而只需要在事件发生的先后顺序上达成一致即可。 在make例子中,make只需要知道input.c是否比input.o生成的早即可,而无须知道input.c和input.o确切的生成时间。 在许多应用中,只要所有机器都认可某一时间就足够了, 而这个时间无须与收音机每小时广播的时间相同 例如,尽管现在真正的时间是10:05,但只要所有机器都