Email this article Two-level Hierarchical Scheduling Algorithm for Real-time Multiprocessor Systems
Abstract
algorithm has the least runtime complexity among joblevel
fixed-priority algorithms for scheduling tasks on multiprocessor
architectures. However, EDF suffers from suboptimality
in multiprocessor systems. This paper proposes
a new restricted migration-based scheduling algorithm for
multiprocessor real-time systems, called Two-level Hierarchical
Scheduling Algorithm (2L-HiSA), to address this
sub-optimality. 2L-HiSA algorithm divides the problem of
multiprocessor scheduling into a two-level hierarchy of
schedulers. This algorithm works in two phases: i- A taskpartitioning
phase in which, each task from application task
set is assigned to a specific processor by following simple
bin-packing approach. If a task can not be partitioned on
any processor in the platform, it qualifies as migrating
task. ii- A processor-grouping phase in which, processors
are clustered together such that, per cluster, the unused
fragmented computation power equivalent to at most one
processor is available. We provide schedulability analysis
and experimental evaluation to support our proposition.
Moreover, our simulation results show an average difference
of 18-folds in the number of preemptions and 10-folds in
the number of task migrations under 2L-HiSA and PD2
algorithm.
Keywords
References
J. M. Calandrino, J. H. Anderson, and D. P. Baumberger,
“A hybrid real-time scheduling approach for large-scale
multicore platforms,” in Proceedings of the ECRTS’07
conference, 2007, pp. 247–256.
C. Farivar, “Intel Developers Forum roundup:
four cores now, 80 cores later.” 2006,
http://www.engadget.com/2006/09/26/intel-developersforum-
roundup-four-cores-now-80-cores-later/.
S. H. Funk, “Edf scheduling on heterogeneous multiprocessors,”
in PhD thesis, department of computer science.
University of North Carolina at Chapel Hill, 2004.
J. Carpenter, S. Funk, P. Holman, A. Srinivasan, J. Anderson,
and S. Baruah, “A categorization of real-time
multiprocessor scheduling problems and algorithms,” in
Handbook of Scheduling: Algorithms, Models, and Performance
Analysis. CRC Press LLC, 2003.
S. Kato, N. Yamasaki, and Y. Ishikawa, “Semi-partitioned
scheduling of sporadic task systems on multiprocessors,”
in Proceedings of the 2009 21st Euromicro Conference
on Real-Time Systems. Washington, DC, USA: IEEE
Computer Society, 2009, pp. 249–258. [Online]. Available:
http://portal.acm.org/citation.cfm?id=1581378.1581524
J. H. Anderson, V. Bud, and U. C. Devi, “An edf-based
scheduling algorithm for multiprocessor soft real-time systems,”
in Proceedings of the 17th Euromicro Conference
on Real-Time Systems. Washington, DC, USA: IEEE
Computer Society, 2005, pp. 199–208. [Online]. Available:
http://portal.acm.org/citation.cfm?id=1084012.1084161
S. K. Baruah, N. K. Cohen, C. G. Plaxton, and
D. A. Varvel, “Proportionate progress: a notion of
fairness in resource allocation,” in Proceedings of
the twenty-fifth annual ACM symposium on Theory
of computing, ser. STOC ’93. New York, NY,
USA: ACM, 1993, pp. 345–354. [Online]. Available:
http://doi.acm.org/10.1145/167088.167194
J. H. Anderson and A. Srinivasan, “Early-release fair
scheduling,” in In Proceedings of the 12th Euromicro
Conference on Real-Time Systems, 2000, pp. 35–43.
H. Cho, B. Ravindran, and E. D. Jensen, “An optimal
real-time scheduling algorithm for multiprocessors,” in Proceedings of the 27th IEEE International Real-
Time Systems Symposium. Washington, DC, USA: IEEE
Computer Society, 2006, pp. 101–110. [Online]. Available:
http://portal.acm.org/citation.cfm?id=1193218.1194408
F. Muhammad, “Ordonnancement de tˆaches efficace et ˆa
complexit`e maˆıtris`ee pour des syst`emes temps r`eel,” in
PhD thesis. University of Nice-Sophia Antipolis, 2009.
S. Kato and N. Yamasaki, “Portioned edf-based
scheduling on multiprocessors,” in Proceedings of
the 8th ACM international conference on Embedded
software, ser. EMSOFT ’08. New York, NY,
USA: ACM, 2008, pp. 139–148. [Online]. Available:
http://doi.acm.org/10.1145/1450058.1450078
F. Dorin, P. Meumeu Yomsi, J. Goossens, and P. Richard,
“Semi-partitioned hard real-time scheduling with restricted
migrations upon identical multiprocessor platforms,” in
Operating Systems (cs.OS), arXiv:1006:2637v1 [cs.OS],
Cornell University Library Archives, Technical Report,
June, 2010.
K. Funaoka, S. Kato, and N. Yamasaki, “A context cache
replacement algorithm for pfair scheduling,” in Proceedings
of the 15th International Conference on Real-Time
and Network Systems (RTNS), 2007, pp. 57 – 64.
D. Johnson, “Near-optimal bin packing algorithms,” in
PhD thesis, Department of Mathematics, Massachusetts
Institute of Technology, 1973.
B. Andersson and E. Tovar, “Multiprocessor scheduling
with few preemptions,” in Proceedings of the 12th
IEEE International Conference on Embedded and
Real-Time Computing Systems and Applications, ser.
RTCSA ’06. Washington, DC, USA: IEEE Computer
Society, 2006, pp. 322–334. [Online]. Available:
http://dx.doi.org/10.1109/RTCSA.2006.45
P. Tan, J. Shu, and Z. Wu, “A hybrid real-time scheduling
approach on multi-core architectures,” in Journal of software,
vol. 5, No. 9, September 2010. Academy Publisher,
, pp. 958–965.
M. Dertouzos and A. Mok, “Multiprocessor scheduling in
a hard real-time environment,” in IEEE Transactions on
Software Engineering, 1989, p. 1497 1506.
K. S. Hong and J. Y.-T. Leung, “On-line scheduling of
real-time tasks,” in IEEE Real-Time Systems Symposium,
Huntsville,Alabama, 1988, p. 244 250.
S. Baruah, N. Cohen, G. Plaxton, and D. Varvel, “Proportionate
progress: A notion of fairness in resource allocation,”
in Algorithmica, 1996, p. 600 625.
A. Srinivasan and J. Anderson, “Fair scheduling of
dynamic task systems on multiprocessors,” J. Syst. Softw.,
vol. 77, pp. 67 – 80, July 2005. [Online]. Available:
http://dx.doi.org/10.1016/j.jss.2003.12.041
B. Andersson, S. Baruah, and J. Jonsson, “Staticpriority
scheduling on multiprocessors,” in Proceedings
of the 22nd IEEE Real-Time Systems Symposium,
ser. RTSS ’01. Washington, DC, USA: IEEE
Computer Society, 2001, pp. 93–. [Online]. Available:
http://portal.acm.org/citation.cfm?id=882482.883823
S. K. Baruah, A. K. Mok, and L. E. Rosier, “Preemptively
scheduling hard-real-time sporadic tasks on one processor,”
in In Proceedings of the 11th Real-Time Systems Symposium.
IEEE Computer Society Press, 1990, pp. 182–190.
STORM, “STORM simulation tool,” http://storm.rtssoftware.
org.
Marvell, “Marvell’s XScale Microarchitecture,”
http://www.marvell.com/.
Full Text: PDF