Mixed-Criticality Scheduling to Minimize Makespan

Baruah, Sanjoy; Easwaran, Arvind; Guo, Zhishan

doi:10.4230/LIPIcs.FSTTCS.2016.7

File

LIPIcs.FSTTCS.2016.7.pdf

Filesize: 0.5 MB
13 pages

Document Identifiers

DOI: 10.4230/LIPIcs.FSTTCS.2016.7
URN: urn:nbn:de:0030-drops-68429

Author Details

Sanjoy Baruah

Arvind Easwaran

Zhishan Guo

Cite AsGet BibTex

Sanjoy Baruah, Arvind Easwaran, and Zhishan Guo. Mixed-Criticality Scheduling to Minimize Makespan. In 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 65, pp. 7:1-7:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.FSTTCS.2016.7

Abstract

In the mixed-criticality job model, each job is characterized by two execution time parameters, representing a smaller (less conservative) estimate and a larger (more conservative) estimate on its actual, unknown, execution time. Each job is further classified as being either less critical or more critical. The desired execution semantics are that all jobs should execute correctly provided all jobs complete upon being allowed to execute for up to the smaller of their execution time estimates, whereas if some jobs need to execute beyond their smaller execution time estimates (but not beyond their larger execution time estimates), then only the jobs classified as being more critical are required to execute correctly. The scheduling of collections of such mixed-criticality jobs upon identical multiprocessor platforms in order to minimize the makespan is considered here.

Keywords

Scheduling
Mixed criticality
Identical parallel machines
Makespan minimization
Approximation algorithm.

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

References

Sanjoy Baruah, Arvind Easwaran, and Zhishan Guo. MC-Fluid: simplified and optimally quantified. In Real-Time Systems Symposium (RTSS), 2015 IEEE, Dec 2015.
Sanjoy K. Baruah, Liliana Cucu-Grosjean, Robert I. Davis, and Claire Maiza. Mixed Criticality on Multicore/Manycore Platforms (Dagstuhl Seminar 15121). Dagstuhl Reports, 5(3):84-142, 2015. URL: http://dx.doi.org/10.4230/DagRep.5.3.84.
Alan Burns and Robert Davis. Mixed-criticality systems: A review. Available at http://www-users.cs.york.ac.uk/~burns/review.pdf, 2013.
Chandra Chekuri and Sanjeev Khanna. On multi-dimensional packing problems. In Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 185-194, January 1999.
Chandra Chekuri and Sanjeev Khanna. On multidimensional packing problems. SIAM J. Comput., 33(4):837-851, 2004. URL: http://dx.doi.org/10.1137/S0097539799356265.
Jr. E. Coffman and P. J. Denning. Operating Systems Theory. Prentice-Hall, Englewood Cliffs, NJ, 1973.
Georgia Giannopoulou, Nikolay Stoimenov, Pengcheng Huang, and Lothar Thiele. Scheduling of mixed-criticality applications on resource-sharing multicore systems. In International Conference on Embedded Software (EMSOFT), pages 17:1-17:15, Montreal, Oct 2013.
Lee Jaewoo, Kieu-My Phan, Xiaozhe Gu, Jiyeon Lee, A. Easwaran, Insik Shin, and Insup Lee. MC-Fluid: Fluid model-based mixed-criticality scheduling on multiprocessors. In Real-Time Systems Symposium (RTSS), 2014 IEEE, pages 41-52, Dec 2014.
Jing Li, David Ferry, Shaurya Ahuja, Kunal Agrawal, Christopher Gill, and Chenyang Lu. Mixed-criticality federated scheduling for parallel real-time tasks. In Proceedings of the 22nd IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), April 2016.
R. McNaughton. Scheduling with deadlines and loss functions. Management Science, 6:1-12, 1959.
Steve Vestal. Preemptive scheduling of multi-criticality systems with varying degrees of execution time assurance. In Proceedings of the Real-Time Systems Symposium, pages 239-243, Tucson, AZ, December 2007. IEEE Computer Society Press.
Tjark Vredeveld. Vector scheduling problems. In Min-Yang Kao, editor, Encyclopedia of Algorithms. Springer, 2014.