MOCA: A multiprocessor on-line competitive algorithm for real-time system scheduling
MOCA: A multiprocessor on-line competitive algorithm for real-time system scheduling
复制标题
MOCA：一种用于实时系统调度的多处理器在线竞争算法
DOI：
10.1109/real.1993.393503
复制
发表时间：
1993
期刊：
影响因子：
--
通讯作者：
D. Shasha
中科院分区：
文献类型：
--
作者：
G. Koren;D. Shasha
我们在多处理器实时环境中研究有竞争力的在线计划。在我们的模型中，每个任务都有一个截止日期和价值，仅在其截止日期完成时才能获得。可以将任务分配给任何处理器，所有处理器都同样强大。问题是要设计一种在线调度算法（即，在发布任务之前，调度程序不知道该算法），并且对系统获得的总价值保证了最坏情况。我们使用两个或多个处理器研究系统。我们提出了任何在线并行实时调度程序可以提供的最佳竞争保证的固有限制。然后，我们提出了一种具有竞争性算法，该算法获得了最坏的案例保证，这在许多情况下与最佳保证相比，这是一小部分。这些模型是具有集中调度程序和共享内存多处理器的分布式系统。<< etx >>
We study competitive on-line scheduling in multiprocessor real-time environments. In our model, every task has a deadline and a value that it obtains only if it completes by its deadline. A task can be assigned to any processor, all of which are equally powerful. The problem is to design an on-line scheduling algorithm (i.e., one in which the scheduler has no knowledge of a task until it is released) with worst case guarantees as to the total value obtained by the system. We study systems with two or more processors. We present an inherent limit on the best competitive guarantee that any on-line parallel real-time scheduler can give. Then we present a competitive algorithm that achieves a worst case guarantee which is within a small factor from the best possible guarantee in many cases. The models are a distributed system having a centralized scheduler as well as a shared memory multiprocessor.<<ETX>>