| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
DPR, LPR: Proactive Resource Allocation Algorithms for Asynchronous Real-Time Distributed Systems
February 2004 (vol. 53 no. 2)
pp. 201-216
Abstract— We present two proactive resource allocation algorithms, called DPR and LPR, for satisfying the timeliness requirements of real-time tasks in asynchronous real-time distributed systems. The algorithms are proactive in the sense that they allow application-specified and user-triggered resource allocation by allowing anticipated task workloads to be specified for future time intervals. When proactively triggered, the algorithms allocate resources to maximize the aggregate deadline-satisfied ratio for the future time interval under the anticipated workload. While DPR uses the Earliest Deadline First scheduling algorithm as the underlying algorithm for process scheduling and packet scheduling, LPR uses a modified Least Laxity First scheduling algorithm. We show that LPR is computationally more expensive than DPR. Further, our experimental studies reveal that LPR yields a higher deadline-satisfied ratio than DPR.
[1] 201 G.C. Buttazzo, Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications. Academic Publishers, 1997.[2] J.W.S. Liu, Real-Time Systems. Prentice Hall, 2000.[3] E.D. Jensen, Asynchronous Decentralized Real-Time Computer Systems Real-Time Computing, Proc. NATO Advanced Study Inst., W.A. Halang and A.D. Stoyenko, eds., Springer Verlag, Oct. 1992.[4] D. ITO, Quorum DARPA ITO, Aug. 1997, http://www.ito. darpa.mil/research/quorum projlist.html.[5] T.F. Abdelzaher, E.M. Atkins, and K.G. Shin, “QoS Negotiation in Real-Time Systems and Its Applications to Automated Flight Control,” Proc. IEEE Real-Time Technology and Applications Symp., June 1997.[6] T. Abdelzaher and K. Shin, "End-Host Architecture for QoS-Adaptive Communication," Proc. IEEE Real-Time Technology and Applications Symp., IEEE Press, Piscataway, N.J., June 1998, pp. 121-130.[7] S. Brandt, G. Nutt, T. Berk, and J. Mankovich, “A Dynamic Quality of Service Middleware Agent for Mediating Application Resource Usage,” Proc. IEEE Real-Time Systems Symp., pp. 307-317, Dec. 1998.[8] M. Humphrey, S. Brandt, G. Nutt, and T. Berk, The DQM Architecture: Middleware for Application Centered QoS Resource Management Proc. IEEE Workshop Middleware for Distributed Real-Time Systems and Services, pp. 97-104, Dec. 1997.[9] D. Hull, A. Shankar, K. Nahrstedt, and J.W.S. Liu, An End-to-End QoS Model and Management Architecture Proc. IEEE Workshop Middleware for Distributed Real-Time Systems and Services, pp. 82-89, Dec. 1997.[10] C. Lee, On Quality of Service Management PhD dissertation, Carnegie Mellon Univ., Aug. 1999.[11] C. Lee, J. Lehoczky, R. Rajkumar, and D. Siewiorek, “On Quality of Service Optimization with Discrete QoS Options,” Proc. IEEE Real-Time Technology and Applications Symp., pp. 276-286, June 1999.[12] C. Lee, J. Lehoczky, D. Siewiorek, R. Rajkumar, and J. Hansen, “A Scalable Solution to the Multi-Resource QoS Problem,” Proc. 20th IEEE Real-Time Systems Symp., Dec. 1999.[13] B. Ravindran, Engineering Dynamic Real-Time Distributed Systems: Architecture, System Description Language, and Middleware IEEE Trans. Software Eng., vol. 28, no. 2, pp. 30-57, Jan. 2002.[14] R. Rajkumar, C. Lee, J. Lehoczky, and D. Siewiorek, A Resource Allocation Model for QoS Management Proc. 19th IEEE Real-Time Systems Symp. (RTSS), pp. 298-307, 1997.[15] R. Rajkumar, C. Lee, J. Lehoczky, and D. Siewiorek, Practical Solutions for QoS-Based Resource Allocation Problems Proc. IEEE Real-Time Systems Symp., pp. 296-306, Dec. 1998.[16] D.I. Rosu, K. Schwan, S. Yalamanchili, and R. Jha, “On Adaptive Resource Allocation for Complex Real-Time Applications,” Proc. 18th IEEE Real-Time Systems Symp., pp. 320–329, Dec. 1997.[17] D. Rosu, K. Schwan, and S. Yalamanchili, FARA: A Framework for Adaptive Resource Allocation in Complex Real-Time Systems Proc. IEEE Real-Time Technology and Applications Symp., 1998.[18] D. Rosu and K. Schwan, Faracost: An Adaptation Cost Model Aware of Pending Constraints Proc. 20th IEEE Real-Time Systems Symp., pp. 224-233, Dec. 1999.[19] B. Ravindran, L.R. Welch, and B. Shirazi, Resource Management Middleware for Dynamic, Dependable Real-Time Systems J. Real-Time Systems, vol. 20, no. 2, pp. 183-196, Mar. 2001.[20] J.A. Stankovic, M. Spuri, K. Ramamritham, and G.C. Buttazzo, Deadline Scheduling for Real-Time Systems. Kluwer Academic, 1998.[21] S.-H. Oh and S.-M. Yang, A Modified Least-Laxity-First Scheduling Algorithm for Real-Time Tasks Proc. Fifth Int'l Conf. Real-Time Computing Systems and Applications, pp. 31-36, Oct. 1998.[22] L.R. Welch, B. Ravindran, B. Shirazi, and C. Bruggeman, “Specification and Modeling of Dynamic, Distributed Real-Time Systems,” Proc. IEEE Real-Time Systems Symp., pp. 72-81, Dec. 1998.[23] L.R. Welch and B.A. Shirazi, “A Dynamic Real-Time Benchmark for Assessment of QoS and Resource Management Technology,” Proc. Fifth IEEE Real-Time Technology and Applications Symp., June 1999.[24] B. Shirazi, L.R. Welch, B. Ravindran, C. Cavanaugh, and E. Huh, Dynbench: A Benchmark Suite for Dynamic Real-Time Systems J. Parallel and Distributed Computing Practics, vol. 3, no. 1, pp. 89-107, Mar. 2000.[25] T. Abdelzaher, An Automated Profiling Subsystem for QoS-Aware Services Proc. IEEE EEE Real-Time Technology and Applications Symp. (RTAS), pp. 208-217, 2000.[26] R. Devarasetty, Heuristic Algorithms for Adaptive Resource Management of Periodic Tasks in Soft Real-Time Distributed Systems master's thesis, Virginia Polytechnic Inst. and State Univ., Feb. 2001.[27] D.L. Mills, Improved Algorithms for Synchronizing Computer Network Clocks IEEE/ACM Trans. Networking, vol. 3, pp. 245-254, June 1995.[28] B. Kao and H. Garcia-Molina, “Deadline Assignment in a Distributed Soft Real-Time System,” IEEE Trans. Parallel and Distributed Systems, vol. 8, no. 12, pp. 1268-1274, Dec. 1997.[29] C.D. Locke, Best-Effort Decision Making for Real-Time Scheduling PhD dissertation, Carnegie Mellon Univ., CMU-CS-86-134, 1986.
Index Terms:
Asynchronous real-time systems, distributed real-time systems, proactive resource allocation, aperiodic tasks, switched real-time Ethernet, EDF, MLLF.
Citation:
Binoy Ravindran, Peng Li, "DPR, LPR: Proactive Resource Allocation Algorithms for Asynchronous Real-Time Distributed Systems," IEEE Transactions on Computers, vol. 53, no. 2, pp. 201-216, Feb. 2004, doi:10.1109/TC.2004.1261829
