如何随着时间的推移分散进程以获得最少数量的“冲突”？
我正在为嵌入式系统开发调度程序。 该调度程序将每 X 毫秒调用一次每个进程；当然这个时候可以为每个进程单独配置。
一切都经过编码并按其应有的方式调用每个流程；我面临的问题是这样的： 想象一下，我设置 4 个进程分别每 10、15、5 和 30 毫秒调用一次：
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
问题是，当达到 30 毫秒时，所有进程都会在同一时刻（一个接一个）被调用，并且这可能会延迟此处的正确执行。
这可以通过向每个进程添加延迟（但保留其调用频率）来解决，这样频率就不再是彼此的倍数。我的问题是我不知道如何计算应用于每个进程的延迟，以便最大限度地减少冲突数量。
是否有任何已知的算法，或者一些数学指导？
谢谢。
I'm developing a scheduler for an embedded system.
This scheduler will call each process every X milliseconds; this time can be configured separately for each process, of course.
Everything is coded and calls every process as it should; the problem I'm facing is this:
Imagine I set 4 processes to be called every 10, 15, 5 and 30 milliseconds respectively:
A: 10ms
B: 15ms
C: 5ms
D: 30ms
The resulting calling over time will be:
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
The problem is that when 30ms is reached, all processes are called at the same moment (one after another) and this can delay the correct execution from here.
This can be solved by adding a delay to each process (but preserving its calling frequency), so the frequencies stops being multiples of each other. My problem is that I don't know how to calculate the delay to apply to each process so the number of collisions is minimized.
Is there any known algorithm for this, or some mathematical guidance?
Thank you.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
给定一组间隔，您可以通过查找 最小公倍数正如杰森在对您的帖子的评论中提到的。您可以通过对一组任务的间隔进行质因数分解来找到 LCM。
不过，似乎最大公约数（或最大公约数GCF）可能是最重要的计算有用的数字。该数字将为您提供重复发生的时间间隔。在您的示例中，GCF 为 5。当 GCF 为 5 时，可以向每个任务添加初始偏移量 1、2、3 等，以避免开始时间重叠。因此，当 GCF 为 5 时，您最多可以有 5 个任务，这些任务的开始时间永远不会重叠。如果 GCF 为 20，您最多可以安排 20 个任务，且开始时间不会重叠。如果两个（或更多）任务相对素数（GCF=1），那么如果间隔永远不会改变，无论您对这些任务使用什么偏移量，都肯定会发生重叠。
Given a set of intervals, you can find the time at which the start times would coincide (assuming no offsets) by finding the least common multiple as mentioned by Jason in a comment to your post. You can find the LCM by doing the prime factorization of the intervals for a set of tasks.
It seems, though, that the greatest common divisor (or greatest common factor GCF) might be the most useful number to compute. That number will give you interval at which repeats will happen. In your example, the GCF is 5. With a GCF of 5, it is possible to add an initial offset of 1, 2, 3, etc. to each task to avoid overlapping start times. Thus, with a GCF of 5, you can have up to 5 tasks that have start times that would never overlap. With a GCF of 20, you could have up to 20 tasks scheduled with no overlapping start times. If two (or more) tasks are relatively prime (GCF=1), then an overlap will definitely occur no matter what offset you use for those tasks if the intervals never change.
对此没有完美的解决方案，它们时不时会发生冲突。
我建议在周期长度中添加微小（0.01-0.1ms）随机值，因此从长远来看，它们实际上很少会同时被调用。
或者，如果您有 5ms 调度程序粒度，则第一个线程始终在 X+1ms 处调用，第二个线程在 X+2 处调用，依此类推，因此始终保证 1ms 的不间断运行（如果您有 10 个线程，那么它将是 X+ 0.5、X+1、X+1.5）。但这实施起来可能会相当棘手。
There is no perfect solution for this, they will collide from time to time.
I would suggest to add tiny(0.01-0.1ms) random value to cycle length, so in the long term they will really rarely called at the same time.
Alternatively, if you have 5ms scheduler granularity, first thread is always called at X+1ms, second at X+2, e.t.c, so that it is always guaranteed 1ms of uninterrupted run (if you have 10 threads, then it will be X+0.5, X+1, X+1.5). But this might get quite tricky to implement.
这类问题直接涉及实时编程和调度算法领域。我在大学上过关于这个主题的课程，如果我没记错的话，速率单调调度 是您正在寻找的算法类型。
这个想法是，您为与其周期成反比的作业分配优先级，即周期越小，优先级越高。但如果您可以中断工作并稍后再恢复，效果会更好。
不过，还有其他替代方案，例如 EDF（最早截止日期优先），但这些都是动态调度算法（即在执行期间分配优先级）。
This kind of problem relates directly the domain of real-time programming and scheduling algorithms. I took a class on this subject in college, and if I remember well, Rate-monotonic scheduling is the kind of algorithm you are looking for.
The idea is that you assign priorities to jobs that are inversely proportional to their period, ie the smaller the period, the higher the priority. But this works better if you can interrupt your jobs and resume them later.
There are other alternatives, though, like EDF (earliest deadline first), but these are dynamic scheduling algorithms (ie the priorities are assigned during the execution).
简单的解决方案是更改调用子例程的时间表。即，您可以接受 5、15、15 和 30 毫秒，而不是 5、10、15 和 30 毫秒吗？然后您可以使用以下模式：（A = 5 ms proc，B，C = 15 ms proc，D = 30 ms proc）：
我确信您可以推广这个想法，但只有当您实际上可以更改静态间隔。
如果您无法更改间隔，并且还需要严格遵守它们，那么我有点运气不好，因为没有参数可以更改:)
The easy solution is to change the schedule in which you call the subroutines. I.e. instead of 5, 10, 15, and 30 ms, can you live e.g. with 5, 15, 15 and 30? Then you can use the following pattern: (A=5 ms proc, B,C=15 ms proc, D=30 ms proc):
I'm sure you can generalize this idea, but it works only if you can actually change the static intervals.
If you can't change the intervals, and also you need to obey them strictly, then I you are kind of out of luck as there are no parameters to change :)