分布式系统中的时间问题.docx_第1页
分布式系统中的时间问题.docx_第2页
分布式系统中的时间问题.docx_第3页
分布式系统中的时间问题.docx_第4页
分布式系统中的时间问题.docx_第5页
已阅读5页,还剩3页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

分布式操作系统中的时间问题摘要实践表明,分布式操作系统的同步问题常常比单处理器或者多处理器系统中的同步问题更加困难。本文从时间同步问题开始着手讨论,分析在分布式系统中同步问题的重要性以及如何在分布式系统中实现时间的同步。本文讨论的问题及其解决方式本质上是比较常见的并且出现在分布式操作系统的不同情况下。关键词:分布式操作系统、同步、时间问题AbstractThe practice shows that the synchronization problems in distributedoperating systems often more difficult than synchronous problem of singleprocessor or multiprocessor system. This paperbegins todiscussfrom thetime synchronization problem, analysis of the importance ofsynchronization problemsin distributed systemand how to realize thetimesynchronizationin distributed system. This paper discusses theproblems and the solutions are relatively commonandoccur in differentsituationsunder thedistributedoperating system.Key Words: distributedoperating systems、synchronization、timing issue一、时钟同步问题分布式系统中的同步比集中式系统中的同步要复杂一些,因为分布式系统中的同步只能通过分布式算法来实现,如果像集中式系统一样,在某地收集有关系统的所有有关信息,让某个进程分析并做出决定是不切实际的,一般来说分布式算法有如下的性质: 相关的信息分布在多台机器中 进程决策仅仅依赖于本地信息 系统中单点故障应该避免 没有公共时钟和其他精确的全局时间资源存在 前三点都说明了收集所有的有关信息并对它进行处理是不可接受的。比如:资源分配(以一种无死锁的分配方式分配)向单一的管理进程发送所有俄I/O请求,由该管理进程来检查这些请求,但是根据表中的信息允许或者是拒绝请求是不切实际的,在一个大的系统中,这样就会给进程造成太大的负担。 进一步而言,一个故障点就会造成系统的不可靠。而对于分布式系统来说他应该比单机系统更可靠,也就是说最理想的情况是:一台机器的崩溃不会影响其他机器的使用,而不是因为一台机器的故障而系统停滞不前在集中式系统中,时间的概念很清楚,当进程想知道时间时,它使用由内核提供的系统调用。比如进程A先询问时间,然后进程B再询问时间,那么B得到的时间值就应该大于等于A得到的时间值,因此在分布式系统中获得一致的时间很不容易。output.o : cc C output.c例:make file误差 二、物理时钟问题在一些实时系统中,实际时钟时间很重要,对这些系统都需要用到外部的物理时钟,为了提高效率和冗余性,一般使用多个物理时钟,但是又会出现两个问题:1.如何使物理时钟与世界的时钟同步?2.物理时间之间如何保持同步? 太阳日:连续的两次日中天的时间 太阳秒:solar-day/86400 平均太阳秒:如,格林威治时间每天太阳都是从东方地平线升起,升到天空最高处,然后落到西边。太阳在最高点称为中天,它发生在每天的中午,连续两次中天之间的时间称为太阳日,每天24小时,每小时3600秒,所以精确的定义太阳秒为1/86400个太阳日,太阳日的几何计算方法如上图。 原子时钟:原子时钟能精确地计算时间。 国际原子时间(TAI):虽然TAI相对稳定但是也有各种问题 BIH:通过引入闺秒来解决问题。当原子秒计时与太阳秒计时差距增到800微秒时使用闺秒。如下图:三、逻辑时钟问题1.逻辑时钟简介 只关心时钟内部一致性,不关心时钟是否与实际时间一致 1978年 Lamport指出,系统中的时钟并不需要绝对的同步 重要的不是进程有完全一致的时间,而是事件发生的先后次序要一致发生之前(happens-before)关系定义2.Lamport算法 时钟时间C必须向前(不断增加),不能后退(减小) 对时间的更新,只能是在时钟上加一个正数,不能减正数四、时钟同步的几种算法1.时钟同步算法 条件: 如果某台机器有WWV接收器 时钟同步的目的是使其它机器与这台机器同步 如何与现实时钟同步? 如何使不同机器之间相互同步? 介绍时间同步算法: 设每台机器都有个计时器,该计时器每秒中断H次,计时器溢出时,中断处理程序就将软件时钟加1,软件时钟是从过去某一已知时间开始所经历的tick数,这个时钟的值称为C。当UTC时间为t时,机器p的时钟值为Cp(t),理想情况下dc/dt应为1。 真正的时钟计数器不是每秒精确地中断H次,当H = 60时,计时器应每小时生成216,000次ticks,实际上,计时器芯片的相对误差大约为10-5,即每小时的tick数的范围为215,998到216,002,准确地说,如果存在一个常数p ,使得1 - dC/dt 1 + 成立,就可以认为计时器是正常工作的。如果两个时钟偏离UTC的方向相反,那么在同步之后的t时刻时它们的时差为2t,要保证两个时钟间时间差不超过必须至少每隔/2秒重新同步。2.Cristian算法 简介 Cristian 算法 : 该算法非常适合只有一台机器上有WWV接收器而其他所有机器与他同步的系统。 系统中每台机器至少每隔/2秒就向时间服务器发送一条消息查询当前时间,服务器尽快将携带当前时间CUTC的消息返回给请求者一种近似方法,发送者得到时间服务器的响应后,直接将其时钟值设置为CUTC如下图: 该算法的问题: 时间决不能倒退 如果这个请求发送者的时钟比实际时间快,这时仅将CUTC设置为时钟的当前值会引起严重问题。比如:时钟发生变化后,编译产生的目标文件产生的时间早于时钟变化前源文件的修改时间。对时钟的调整必须逐步进行:假设计时器每秒中断100次正常情况下,每次中断将时钟时间增加10毫秒,如果要使时钟慢下来,中断程序就每次只将时间增加9,直到将时间矫正过来为止。如果时钟要加快时,中断程序就每次只将时间增加11毫秒,而不是立即把时间调整到所需要的值。 时间服务器将当前时间发送给查询时间的机器需要时间,这个延迟时间可能会很长,而且它也在变化,Cristian的处理方法就是计算出准确的延迟时间,为了提高估计值的准确性,建议要进行一系列的测量3.Berkeley UNIX算法 时间服务器是活动的,它定期向其他机器查询这些机器的时间,根据得到的响应,时间服务器计算出一个平均值,并通知其它机器调整其时钟,重复这个过程,直到达到一定的缩减量为止 这种方法适用于那些没有WWV接收器的系统在这样的系统中,操作员必须阶段性地手工设置时间的时间如下图:4.平均值算法非集中式算法1.所有机器广播自己的时钟时间2.启动本地计时器收集在S时间间隔中到达的其他机器广播的时间3.执行平均时间计算算法,得到新的时间值5.多重外部时间源法 例:OSF DCE方法1.接受所有时间源的当前UTC(世界统一时间)区间2.去掉与其他区间不相交的区间3.将相交部分的中点作为校准时间五、 同步时钟的应用1.最多一次消息提交 每个消息携带一个ID和一个时间印ts(timestamp) 服务器的表T中记录每个连接C最近的时间印t , 如果到达的消息m,ts(m)t, 则拒绝m2.服务器设置的全局变量G = CurrentTime MaxLifetime MaxClockSkew(当前时间-最大生存时间-最大时钟偏移) 所有G的时间印从表T中清除 对于具有新的ID的到达消息m,如果ts(m)G则拒绝m

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论