Optimal scheduling for real-time parallel tasks

被引：19

作者：

Lee, WY ^{[1
]}

Lee, H

机构：

[1] Hallym Univ, Dept Comp Engn, Chunchon 200702, South Korea

[2] Korea Univ, Dept Comp Sci & Engn, Seoul 136713, South Korea

来源：

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS | 2006年 / E89D卷 / 06期

关键词：

optimal algorithm; real-time scheduling; feasible schedule; bounded parallelism;

D O I：

10.1093/ietisy/e89-d.6.1962

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We propose an optimal algorithm for the real-time scheduling of parallel tasks on multiprocessors, where the tasks have the properties of flexible preemption, linear speedup, bounded parallelism, and arbitrary deadline. The proposed algorithm is optimal in the sense that it always finds out a feasible schedule if one exists. Furthermore, the algorithm delivers the best schedule consuming the fewest processors among feasible schedules. In this letter, we prove the optimality of the proposed algorithm. Also, we show that the time complexity of the algorithm is O(M-2 - N-2.) in the worst case, where M and N are the number of tasks and the number of processors, respectively.

引用

页码：1962 / 1966

页数：5