优先级调度程序中的适当时间

Question

我想写一个调度程序（用 Java，这对我的问题不重要）。每个任务都可以有一个优先级值（从 0.1 到 1.0 浮动）。该优先级值越高，任务应接收的处理时间越长。调度程序在一个永远运行的循环中调用，每次迭代都有最大处理时间（例如 10 毫秒）。

在一本书中我找到了这个调度算法（伪代码）：

update(timeToRun):
    # totalPrio has been set to the sum of all task priorities
    lastTime = time()
    for each task in tasks:
        currentTime = time()
        timeToRun -= currentTime - lastTime
        availableTime = timeToRun * task.prio / totalPrio
        task.process(availableTime)
        lastTime = currentTime

假设我有两个任务，每个任务的优先级都是 0.5，所以 totalPrio 设置为 1.0，两个任务的处理时间应该相等。 update() 函数被调用时值 timeToRun 为 10。

如果第一个任务确实在恰好 5 毫秒后停止，那么第二个任务也应该收到 5 毫秒 availableTime。但是，上面的算法不起作用：timeToRun 在第二次迭代中为 5，因此 availableTime 在第二次迭代中将设置为 2.5（这显然是错误的）。

此外，调度程序应该识别任务花费的时间是否长于或短于它收到的最长时间。例如，如果第一个任务收到的最大时间为 5 毫秒，但只用了 2 毫秒，那么其余任务将收到更多时间。

我将如何实施？

Answer 1

好的，我找到了解决方案。作为记录：上面的代码片段有效，但前提是您在 for 循环的每次迭代中更新 totalPriority 值。事实上，在调用 task.process(availableTime) 之后，您需要从 totalPriority 中减去任务的优先级。这样 availableTime 总是在每次循环迭代中正确计算。

优先级调度程序中的适当时间

Proper Timing in Priority Scheduler

algorithm

scheduling