V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
liuguangxuan
V2EX  ›  算法

各位老哥,请教一个时间同步的算法问题。

  •  
  •   liuguangxuan · 2021-01-04 20:55:10 +08:00 · 1593 次点击
    这是一个创建于 1417 天前的主题,其中的信息可能已经有所发展或是发生改变。

    两台不同的电脑,可以相互通信,假设通信没有延迟。分别运行程序 A (服务端)和程序 B (客户端)。他们各自有自己的时间( timeA 、timeB ),各自的仿真速度( speedA 、speedB,可以理解为现实世界中的加速,如 10 倍速,则 1 秒相当于现实世界的 10 秒),仿真速度的最小刻度为 0.5 。

    现在客户端和服务端的时间和仿真速度都不一致,要求客户端通过不断改变自己仿真速度(加速、减速)的方式,不断的逼近程序 A 的时间,最终达成时间大体一致(允许有一定的误差)。

    但是每一次设置仿真速度,并不会立即响应,会有一个随机的延迟。如客户端初始的仿真速度为 5 倍速,通过对比服务端的时间,发现自己比服务端慢了,要加速追赶,所以在 t1 时刻设置了自己的仿真速度为 10 倍,则 t2 时刻才会真正的设置仿真速度为 10,t2=t1+rand(),rand()的值在 5 秒左右浮动。在 t1 到 t2 这段时间内,仍然以 5 倍速向前推进。

    现在想知道客户端: 1.在什么时刻? 2.设置多少倍速? 可以让客户端慢慢的和服务端时间追平。

    麻烦各位算法大佬提个思路。

    6 条回复    2021-01-06 20:58:08 +08:00
    chocovon
        1
    chocovon  
       2021-01-04 21:07:29 +08:00
    时间调节是靠不住的吧,应该有个调度程序记录两边的运行步数,A 的步数明显小于 B 了就给 A 加速,直到步数相近
    foool
        2
    foool  
       2021-01-04 21:33:55 +08:00
    B 的时钟是什么?类型是 monotonic 还是 realtime ?

    如果 A 仿真速率不变,为什么要不断逼近,直接调整为和 A 一致不行?
    即使 B 不知道 A 的仿真速率,也可以通过两次采样时间简单计算得到 A 的仿真速率,调整和其一样不行吗。

    为什么要有随机延迟,被仿真设备或者协议带来的延迟?
    3dwelcome
        3
    3dwelcome  
       2021-01-04 21:47:25 +08:00
    我做 ntp 时间同步的时候,由于互联网网络 IP 包有抖动的因素,不可能做到 0.1ms 级别的时间同步。
    只能不断重试,不断的逼近,一直到误差在符合的范围之内。
    说白了就是,ping 一次时间有误差,你 ping 10 次,ping 100 次,总能获得误差值,从而把不稳定因素给消除。
    liuguangxuan
        4
    liuguangxuan  
    OP
       2021-01-04 22:04:38 +08:00
    @chocovon 现在知道了运行步数,就是想知道加速的策略(要考虑设置加速会有 5 秒的延迟)。如果加速加大了,就会反超。然后又要减速。

    @foool B 的时间是由 B 机器上的一款模拟仿真软件产生的,设置仿真时间要通过这款软件,它有 5s 左右的随机延迟,5s 后才会真正的设置为指定的仿真速度,无法消除这个延迟。如果 A 和 B 刚开始就有时间误差的话,通过调整仿真速率一样,那么误差永远存在,无法消除。


    @3dwelcome 老哥,感谢回复。不过,不考虑这个网络的延迟,但是要考虑设置仿真速度的 5s 的延迟。
    lidlesseye11
        5
    lidlesseye11  
       2021-01-06 12:08:32 +08:00
    挺有意思的问题
    直觉上来说,假设 rand()的值为 2.5 去调整可能是最优的?
    不知道有没有数学大佬来证明下。。
    liuguangxuan
        6
    liuguangxuan  
    OP
       2021-01-06 20:58:08 +08:00
    @lidlesseye11 越研究越感觉这是个数学问题,期待数学大佬来解答。。。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   3000 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 14:13 · PVG 22:13 · LAX 06:13 · JFK 09:13
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.