Abstract
Partitioning and global scheduling are two approaches for scheduling real-time tasks in multiprocessor environments. Partitioning is the more favored approach, although it is sub-optimal. This is mainly due to the fact that popular uniprocessor real-time scheduling algorithms, such as EDF and RM, can be applied to the partitioning approach with low scheduling overhead. In recent years, much research has been done on global real-time multiprocessor scheduling algorithms based on the concept of “proportionate fairness”. Proportionate fair (Pfair) scheduling [5],[6] is the only known optimal algorithm for scheduling real-time tasks on multiprocessor. However, frequent preemptions caused by the small quantum length for providing optimal scheduling in the Pfair scheduling make it impractical. Deadline Fair Scheduling (DFS) [1] based on Pfair scheduling tried to reduce preemption-related overhead by means of extending quantum length and sharing a quantum among tasks. But extending quantum length causes a mis-estimation problem for eligibility of tasks and a non-work-conserving problem.
In this paper, we propose the Enhanced Deadline Fair Scheduling (E-DFS) algorithm to reduce preemption-related overhead. We show that E-DFS allows us to decrease quantum length by reducing overhead and save wasted CPU time that is caused by preemption-related overhead and miss-estimation of eligibility.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Chandra, A., Adler, M., Shenoy, P.: Deadline fair scheduling: Bridging the theory and practice of proportionateair scheduling in multiprocessor servers. In: Proceedings of the 7th IEEE Real-time Technology and Applications Symposium, pp. 3-14 (May 2001)
Chandra, A., Adler, M., Goyal, P., Shenoy, P.: Surplus fair scheduling: A proportional-share CPU scheduling algorithm for symmetric multiprocessors. In: Proceedings of the 4th ACM Symposium on Operating System Design and Implementation, October 2000, pp. 45–58 (2000)
Srinivasan, A., Holman, P., Anderson, J., Baruah, S.: The case for fair multiprocessor scheduling. In: Proceedings of the 11th International Workshop on Parallel and Distributed Real-Time Systems (April 2003)
Anderson, J., Srinivasan, A.: Early-release fair scheduling. In: Proceedings of the 12th Euromicro Conference on Real-time Systems, June 2000, pp. 35–43 (2000)
Anderson, J., Srinvasan, A.: Pair scheduling: Beyond periodic task systems. In: Proceedings of 7th International Conference on Real-time Computing Sysmtems and Applications, December 2000, pp. 297–306 (2000)
Baruah, S., Cohen, N., Plaxton, C.G., Varvel, D.: Proportioinate progress: A notion of fairness in resource allocation. Algorithmica 15, 600–625 (1996)
Dhall, S., Liu, C.: On a real-time scheduling problem. Operations Research 26(1), 127–140 (1978)
Parekh, A., Gallagher, R.: A generalized processor sharing approach to flow-control in integrated services networks: The single-node case. IEEE/ACM Transactioins on Networking 1(3), 344–357 (1993)
Anderson, J., Sriniasan, A.: Mixed Pair/ERfair scheduling of asynchronous periodic taks. In: Proceedings of the 13th Euromicro Conference on Real-time Systems, pp. 76–85 (2001)
Goyal, P., Guo, X., Vin, H.M.: A hierarchical CPU scheduler for multimedia operating systems. In: Proceedngs of Operating System Design and Implementation, October 1996, pp. 107–122 (1996)
McVoy, L., Staelin, C.: Lmbench: Portable tools for performance analysis. In: Proceedings of USENIX 1996 Technical Conference (January 1996), Available from http://www.bitmover.com/lmbench
Holman, P., Anderson, J.H.: Implementing Pfairness on a symmetric multiprocessor. In: Proceedings of the 10th IEEE Real-Time and Embedded Technology and Applications Symposium (May 2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Jung, K.J., Park, C. (2005). A Technique to Reduce Preemption Overhead in Real-Time Multiprocessor Task Scheduling. In: Srikanthan, T., Xue, J., Chang, CH. (eds) Advances in Computer Systems Architecture. ACSAC 2005. Lecture Notes in Computer Science, vol 3740. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11572961_46
Download citation
DOI: https://doi.org/10.1007/11572961_46
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-29643-0
Online ISBN: 978-3-540-32108-8
eBook Packages: Computer ScienceComputer Science (R0)