Online real-time preemptive scheduling of jobs with deadlines
Online real-time preemptive scheduling of jobs with deadlines
复制标题
在线实时抢先调度有截止日期的作业
DOI：
--
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
M. Palis
中科院分区：
文献类型：
--
作者：
Bhaskar DasGupta;M. Palis
在本文中，我们在在线算法的性能保证方面得出了界限，以实时预先安排工作期限，当时在K机器上用最小拉伸因子α进行特征（或同样，其最大执行率r = 1） /α）。调度程序允许调度程序不完成工作，即使在在线调度程序中执行执行，目的是最大化执行工作的执行时间，在线调度程序必须立即决定，无论何时到达工作，是要执行还是拒绝。最好的离线算法。 α⌉）） +ɛ对于一台机器上的固件实时调度，即使允许算法知道α的值，我们也可能会提前一个简单的算法，即使该算法允许算法的值很小。在这两个模型中，在线调度仪至少达到1-（1/α）的竞争比率。实时调度程序K机器。进步。
In this paper, we derive bounds on performance guarantees of online algorithms for real-time preemptive scheduling of jobs with deadlines on K machines when jobs are characterized in terms of their minimum stretch factor α (or, equivalently, their maximum execution rate r = 1/α). We consider two well known preemptive models that are of interest from practical applications: the hard real-time scheduling model in which a job must be completed if it was admitted for execution by the online scheduler, and the firm real-time scheduling model in which the scheduler is allowed not to complete a job even if it was admitted for execution by the online scheduler. In both models, the objective is to maximize the sum of execution times of the jobs that were executed to completion, preemption is allowed, and the online scheduler must immediately decide, whenever a job arrives, whether to admit it for execution or reject it. We measure the competitive ratio of any online algorithm as the ratio of the value of the objective function obtained by this algorithm to that of the best possible offline algorithm. We show that no online algorithm can have a competitive ratio greater than 1-(1/α)+Ɛ for hard real-time scheduling with K ≥ 1 machines and greater than 1 - (3/(4⌈α⌉)) + Ɛ for firm real-time scheduling on a single machine, where Ɛ > 0 may be arbitrarily small, even if the algorithm is allowed to know the value of α in advance. On the other hand, we exhibit a simple online scheduler that achieves a competitive ratio of at least 1-(1/α) in either of these models with K machines. The performance guarantee of our simple scheduler shows that it is in fact an optimal scheduler for hard real-time scheduling with K machines. We also describe an alternative scheduler for firm real-time scheduling on a single machine in which the competitive ratio does not go to zero as a approaches 1. Both of our schedulers do not know the value of α in advance.