如何在一段时间内传播流程,获得最少数量的"冲突"

Question

我正在为嵌入式系统开发调度程序.该调度程序将每隔X毫秒调用每个进程; 当然,这个时间可以为每个过程单独配置.

一切都被编码,并按照应有的方式调用每个进程; 我面临的问题是:想象一下我分别每10,15,5和30毫秒调用4个进程:

A: 10ms
B: 15ms  
C: 5ms 
D: 30ms

随着时间推移产生的呼叫将是:

                       A          |
       A   B   A       B          |
    C  C   C   C   C   C   C      | processes being called
                       D          |
----------------------------------
0   5  10  15  20  25  30  35...    ms

问题是当达到30ms时,所有进程都在同一时刻(一个接一个)被调用,这可能会延迟从这里开始的正确执行.

这可以通过为每个进程添加延迟(但保留其调用频率)来解决,因此频率停止是彼此的倍数.我的问题是我不知道如何计算应用于每个过程的延迟,因此最小化了碰撞次数.

是否有任何已知的算法或一些数学指导？

谢谢.

Answer 1

给定一组间隔，您可以通过找到 Jason 在您的帖子评论中提到的最小公倍数来找到开始时间重合的时间（假设没有偏移） 。您可以通过对一组任务的间隔进行质因数分解来找到 LCM。

不过，似乎最大公约数（或最大公约数 GCF）可能是最有用的计算数。该数字将为您提供重复发生的时间间隔。在您的示例中，GCF 为 5。当 GCF 为 5 时，可以向每个任务添加初始偏移量 1、2、3 等，以避免开始时间重叠。因此，当 GCF 为 5 时，您最多可以有 5 个任务，这些任务的开始时间永远不会重叠。如果 GCF 为 20，您最多可以安排 20 个任务，且开始时间不会重叠。如果两个（或更多）任务相对素数（GCF=1），那么如果间隔永不改变，无论您对这些任务使用什么偏移量，都肯定会发生重叠。