A New Scheduling Algorithm for Shortening Response Time of Static Priority Task
Article Sidebar
Main Article Content
Abstract
In scheduling algorithms based on the Rate Monotonic (RM) method which are widely used in development of real-time systems, tasks with shorter periods have higher priorities. In contrast, ones with longer periods are likely to suffer from increased response times and jitter due to their lower priorities. We propose an Execution Right Delegation (ERD) method based on RM where a high-priority server for particular (or important) task is introduced to shorten response time and jitter of the task. In the evaluation, it is confirmed that response times and jitter of a particular (important) task are reduced. We also show Response Time Analysis (RTA), which assures worst-case response time of the task. This paper shows the algorithm and RTA of ERD and evaluates it by comparing it to a Deadline Monotonic method. The evaluation by simulation shows that ERD can reduce the average worst-case response time by 13.45% at maximum compared to the Deadline Monotonic scheduling. In addition, we confirm that the RTA provides a worst-case response time close to the simulation results.
Article Details
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
References
C. L. Liu and J. W. Layland, "Scheduling algorithms for multiprogramming in a hard-real-time environment," Journal of the ACM (JACM), vol. 20, no. 1, pp. 46-61, 1973.
N. C. Audsley, A. Burns, M. F. Richardson
and A. J. Wellings, "Hard real-time scheduling: The deadline-monotonic approach," IFAC Proceedings, vol. 24, no.2, pp. 127-132, 1991.
J. P. Lehoczky, L. Sha and J. K. Strosnider, "Enhanced Aperiodic Responsiveness in Hard Real- Time Environments," Proc. of IEEE Real-Time Systems Symposium, pp.261-270, 1987.
B. Sprunt, J. Lehoczky and L. Sha, "Exploiting unused periodic time for aperiodic service using the extended priority exchange algorithm," Proceedings. Real-Time Systems Symposium, pp. 251- 258, 1988.
R. Davis and A. Wellings, "Dual priority scheduling," Proceedings 16th IEEE Real-Time Systems Symposium, pp. 100-109, 1995.
D. de Niz, K. Lakshmanan and R. Rajkumar, "On the Scheduling of Mixed-Criticality Real-Time Task Sets," 2009 30th IEEE Real-Time Systems Symposium, pp. 291-300, 2009.
J. Y-T. Leung and J. Whitehead, "On the complexity of "xed-priority scheduling of periodic, real-time tasks," Performance evaluation, vol. 2, no. 4, pp. 237-250, 1982.
R. I. Davis, L. Cucu-Grosjean, M. Bertogna and A. Burns, "A review of priority assignment in real- time systems," Journal of systems architecture, vol. 65, pp. 64-82, 2016.
E. Bini, G. Buttazzo and G. Buttazzo, "A hyperbolic bound for the rate monotonic algorithm," Proceedings 13th Euromicro Conference on Real- Time Systems, pp. 59-66, 2001.
M. Joseph and P. Paritosh, "Finding response times in a real-time system," The Computer Journal, vol. 29, no. 5, pp. 390-395, 1986.
M. Coutinho, J. Rufino and C. Almeida, "Response Time Analysis of Asynchronous Periodic and Sporadic Tasks Sheduled by a Fixed Priority Preemptive Algorithm," 2008 Euromicro Conference on Real-Time Systems, pp. 156-167, 2008.
M. Bertogna and M. Cirinei, "Response-Time Analysis for Globally Scheduled Symmetric Multiprocessor Platforms," 28th IEEE International Real-Time Systems Symposium (RTSS 2007), pp. 149-160, 2007.
N. Guan, M. Stigge, W. Yi and G. Yu, "New Response Time Bounds for Fixed Priority Multiprocessor Scheduling," 2009 30th IEEE Real-Time Systems Symposium, pp. 387-397, 2009.
Youcheng Sun, G. Lipari, N. Guan and W. Yi, "Improving the response time analysis of global fixed-priority multiprocessor scheduling," 2014 IEEE 20th International Conference on Embedded and Real-Time Computing Systems and Applications, pp. 1-9, 2014.
Y. Sun and D. N. Marco, "Pessimism in multicore global schedulability analysis," Journal of Systems Architecture, vol. 97, pp. 142-152, 2019.
Q. Zhou, G. Li, J. Li, C. Deng and L. Yuan, "Response Time Analysis for Tasks with Fixed Pre-emption Points under Global Scheduling," ACM Transactions on Embedded Computing Systems (TECS), vol. 18, no. 5, pp. 1-23, 2019.
P. Marti, J. M. Fuertes, G. Fohler and K. Ramamritham, "Jitter compensation for real-time control systems," Proceedings 22nd IEEE Real- Time Systems Symposium (RTSS 2001) (Cat. No.01PR1420), pp. 39-48, 2001.
G. Buttazzo and C. Anton, "Comparative assessment and evaluation of jitter control methods," 15th International Conference on Real- Time and Network Systems, 2007.
K. Tanaka, "Real-time scheduling for reducing jitters of periodic tasks," Journal of Information Processing, vol. 23, no. 5, pp. 542-552, 2015.
G. C. Buttazzo, "Rate monotonic vs. EDF: Judgment day. Real-Time Systems," Springer Science + Business Media Inc. Manufactured in The Netherlands, vol. 29, no. 1, pp. 5-26, 2005.