我已经开发了一种调度算法,它提供了概率的软实时保证,但它看起来太新而且简单明了.虽然我把它与已发布的实时调度算法(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的任务都将按时完成.