Allocating hard real-time tasks: an NP-hard problem made easy
作者： K. W. Tindell , A. Burns , A. J. Wellings
DOI: 10.1007/BF00365407
关键词:
摘要: A distributed hard real time system can be composed from a number of communicating tasks. One the difficulties with building such systems is problem where to place In general there are PT ways allocating T tasks P processors, and finding an optimal feasible allocation (where all meet physical timing constraints) known NP-Hard. This paper describes approach solving task using technique as simulated annealing. It also defines real-time architecture presents new analysis which enables requirements guaranteed.
springer.com
acm.org
sci-hub.se 参考文章(18)
N.C. Audsley, A. Burns, M.F. Richardson, A.J. Wellings, Hard Real-Time Scheduling: The Deadline-Monotonic Approach IFAC Proceedings Volumes. ,vol. 24, pp. 127- 132 ,(1991) , 10.1016/S1474-6670(17)51283-5
Chu, Lan, Task Allocation and Precedence Relations for Distributed Real-Time Systems IEEE Transactions on Computers. ,vol. 36, pp. 667- 679 ,(1987) , 10.1109/TC.1987.1676960
A. Damm, J. Reisinger, W. Schwabl, H. Kopetz, The real-time operating system of MARS Operating Systems Review. ,vol. 23, pp. 141- 157 ,(1989) , 10.1145/71021.71029
S. Kirkpatrick, C. D. Gelatt, M. P. Vecchi, Optimization by Simulated Annealing Science. ,vol. 220, pp. 671- 680 ,(1983) , 10.1126/SCIENCE.220.4598.671
Joseph Y.-T. Leung, Jennifer Whitehead, On the complexity of fixed-priority scheduling of periodic, real-time tasks Performance Evaluation. ,vol. 2, pp. 237- 250 ,(1982) , 10.1016/0166-5316(82)90024-4
A. Burns, Scheduling hard real-time systems: a review Software Engineering Journal. ,vol. 6, pp. 116- 128 ,(1991) , 10.1049/SEJ.1991.0015
P. Roussel-Ragot, G. Dreyfus, A problem independent parallel implementation of simulated annealing: models and experiments IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. ,vol. 9, pp. 827- 835 ,(1990) , 10.1109/43.57790
Valmir C Barbosa, Maria Cristina S Boeres, An Occam-based evaluation of a parallel version of simulated annealing Microprocessing and Microprogramming. ,vol. 30, pp. 85- 92 ,(1990) , 10.1016/0165-6074(90)90222-U
S.W. Bollinger, S.F. Midkiff, Heuristic technique for processor and link assignment in multicomputers IEEE Transactions on Computers. ,vol. 40, pp. 325- 333 ,(1991) , 10.1109/12.76410
C. C. Price, Scheduling of Precedence-Constrained Tasks on Multiprocessors The Computer Journal. ,vol. 33, pp. 219- 229 ,(1990) , 10.1093/COMJNL/33.3.219