Feedback-Controlled Server for Scheduling Aperiodic Tasks

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.

Authors:

• Shinpei Kato
• Nobuyuki Yamasaki

Keywords:

• Real-Time Systems
• Aperiodic Task Scheduling
• Feedback-Control Scheduling
• Total Bandwidth Server.

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.