Feedback-Controlled Server for Scheduling Aperiodic Tasks

Authors: Shinpei Kato, Nobuyuki Yamasaki

Abstract:

This paper proposes a scheduling scheme using feedback control to reduce the response time of aperiodic tasks with soft real-time constraints. We design an algorithm based on the proposed scheduling scheme and Total Bandwidth Server (TBS) that is a conventional server technique for scheduling aperiodic tasks. We then describe the feedback controller of the algorithm and give the control parameter tuning methods. The simulation study demonstrates that the algorithm can reduce the mean response time up to 26% compared to TBS in exchange for slight deadline misses.

Keywords: Real-Time Systems, Aperiodic Task Scheduling, Feedback-Control Scheduling, Total Bandwidth Server.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1331701

References:

[1] G.C. Buttazzo and F. Sensini. Deadline Assignment Methods for Soft Aperiodic Scheduling in Hard Real-Time Systems. IEEE Trans. on Computers, 48:1035-1052, 1999.
[2] R.I. Davis, K.W. Tindell, and A. Burns. Scheduling Slack Time in Fixed Priority Pre-emptive Systems. In Proceedings of IEEE Real-Time Systems Symposium, pages 222-231, 1993.
[3] R.I. Davis and A. Wellings. Dual Priority Scheduling. In Proceedings of IEEE Real-Time Systems Symposium, pages 100-109, 1995.
[4] J.P. Lehoczky and S. Ramos-Thuel. An Optimal Algorithm for Scheduling Soft-Aperiodic Tasks in Fixed-Priority Preemptive Systems. In Proceedings of IEEE Real-Time Systems Symposium, pages 110-123, 1992.
[5] J.P. Lehoczky, L. Sha, and J.K. Strosnider. Enhanced aperiodic responsiveness in hard real-time environments. In Proceedings of IEEE Real- Time Systems Symposium, pages 261-270, 1987.
[6] C.L. Liu and J.W. Layland. Scheduling Algorithms for Multiprogramming in a Hard Real-Time Environment. Journal of ACM, 20:46-61, 1973.
[7] C. Lu, J.A. Stankovic, G. Tao, and S.H. Son. Design and Evaluation of a Feedback Control EDF Scheduling Algorithm. In Proceedings of Real-Time Systems Symposium, pages 56-67, 1999.
[8] C. Lu, J.A. Stankovic, G. Tao, and S.H. Son. Feedback Control Real- Time Scheduling: Framework, Modeling, and Algorithms. Journal of Real-Time Systems, Special Issue on Control-theoretical Approaches to Real-Time Computing, 23:85-126, 2002.
[9] R.A. Omari, G. Manimaran, M.V. Salapaka, and A.K. Somani. Novel Algorithms for Open-loop and Closed-loop Scheduling of Real-time Tasks in Multiprocessor Systems Based on Execution Time Estimation. In Proceedings of IEEE International Parallel and Distributed Proceesing Symposium, pages 7-14, 2003.
[10] S. Ramos-Thuel and J.P. Lehoczky. On-line Scheduling of Hard Deadline Aperiodic Tasks in Fixed-Priority Systems. In Proceedings of IEEE Real-Time Systems Symposium, pages 160-171, 1993.
[11] B. Sprunt, J. Lehoczky, and L. Sha. Exploiting Unused Periodic Time for Aperiodic Service using the Extended Priority Exchange Algorithm. In Proceedings of IEEE Real-Time Systems Symposium, pages 251-258, 1988.
[12] B. Sprunt, L. Sha, and J. Lehoczky. Aperiodic Task Scheduling for Hard Real-Time Systems. Journal of Real-Time Systems, 1:27-60, 1989.
[13] M. Spuri and G. Buttazo. Efficient Aperiodic Service under Earliest Deadline Scheduling. In Proceedings of IEEE Real-Time Systems Symposium, pages 2-11, 1994.
[14] M. Spuri and G.C. Buttazo. Scheduling Aperiodic Tasks in Dynamic Priority Systems. Journal of Real-Time Systems, 10:179-210, 1996.
[15] J.A. Stankovic, T. He, T. Abdelzaher, M. Marley, G. Tao, S.H. Son, and C. Lu. Feedback Control Scheduling in Distributed Real-Time Systems. In Proceedings of Real-Time Systems Symposium, pages 59-70, 2001.
[16] J.A. Stankovic, C. Lu, S.H. Son, and G. Tao. The Case for Feedback Control Real-Time Scheduling. In Proceedings of Euromicro Conference on Real-Time Systems, pages 11-20, 1999.
[17] Y. Takahashi and C.S. Chan. Parametereinstellung bei linearen DDCAlgorithmen. Regelungstechnik u. Prozess-Datenverarbeitung, 19:237- 284, 1971.
[18] J.G. Ziegler and N. B. Nichols. Optimum Setting for Automatic Controllers. Transation of ASME, 64:759-768, 1942.