该算法是现有的实时系统算法吗？

Question

我已经开发了一种调度算法,它提供了概率的软实时保证,但它看起来太新而且简单明了.虽然我把它与已发布的实时调度算法(EDF,零星服务器等)联系起来很困难.以下调度算法是否为已知的实时算法？

假设:

• 所有任务都来自一个分布,其中X百分比的任务需要少于R cpu-seconds
• 所有任务都有相同的截止日期.如果任务花费的时间超过T秒,则该任务失败
• 任务到达由已知的最小到达间隔时间MIN_INTER_ARRIVE_T分隔
• 调度程序有一个任务集,可以随时保存最多H个任务(在每个时间步骤中,任务集中的所有任务通过平均共享CPU来实现相同的进度)
• 任务不能相互影响

保证:

• (1)如果X的任务百分比要求少于R cpu-seconds和(2)R <= T/H,(3)MIN_INTER_ARRIVE_T> = T/H,那么至少X个百分比的任务将在T秒内完成

算法:

• 如果任务到达且任务集已满,则逐出已使用最多CPU的任务.假设保证这样的任务至少使用R cpu-seconds.因此,可以驱逐的唯一任务将是失败的任务.任何需要少于R cpu-seconds的任务都将按时完成.

Answer 1

我不是硬实时调度方面的专家，但这就是你的算法对我来说的感觉。

它与航空航天系统中发生的情况非常相似。您的系统看起来更灵活，但基本上这一切都归结为提前知道您有资源来运行您需要运行的任务。

关键的嵌入式航空航天系统更喜欢确定性，但为了防止潜在的缺陷（如果允许的话，任务的运行时间可能比分配的时间长），任务分配引擎将中断这些任务以让其他任务完成。有时剩余的空闲周期可以用来完成中断的任务，或者任务被视为失败。

请注意，您只能失败不重要的任务，因此您必须仔细构建关键任务，或者拥有一个优先级系统，使关键任务无论如何都有机会完成。

您现在回到了第一个方面：您需要确保资源足以运行提前所需的任务。

嗯，
声音动起来。