Processing math: 100%
We use cookies to improve your experience with our site.

Indexed in:

SCIE, EI, Scopus, INSPEC, DBLP, CSCD, etc.

Submission System
(Author / Reviewer / Editor)
Yong Liao, Xu-Dong Chen, Guang-Ze Xiong, Qing-Xin Zhu, Nan Sang. End-to-End Utilization Control for Aperiodic Tasks in Distributed Real-Time Systems[J]. Journal of Computer Science and Technology, 2007, 22(1): 135-146.
Citation: Yong Liao, Xu-Dong Chen, Guang-Ze Xiong, Qing-Xin Zhu, Nan Sang. End-to-End Utilization Control for Aperiodic Tasks in Distributed Real-Time Systems[J]. Journal of Computer Science and Technology, 2007, 22(1): 135-146.

End-to-End Utilization Control for Aperiodic Tasks in Distributed Real-Time Systems

More Information
  • Received Date: June 23, 2005
  • Revised Date: March 22, 2006
  • Published Date: January 14, 2007
  • An increasing number of {DRTS} (Distributed Real-Time Systems) areemploying an end-to-end aperiodic task model. The key challenges of such{DRTS} are guaranteeing utilization on multiple processors toachieve overload protection, and meeting the end-to-end deadlines ofaperiodic tasks. This paper proposes an end-to-end utilization controlarchitecture and an {IC-EAT} (Integration Control for End-to-EndAperiodic Tasks) algorithm, which features a distributed feedback loopthat dynamically enforces the desired utilization bound on multipleprocessors. IC-EAT integrates admission control with feedbackcontrol, which is able to dynamically determine the QoS (Quality ofService) of incoming tasks and guarantee the end-to-end deadlines ofadmitted tasks. Then an LQOCM (Linear Quadratic Optimal Control Model) ispresented. Finally, experiments demonstrate that, for the end-to-end{DRTS} whose control matrix GG falls into the stable region, the{IC-EAT} is convergent and stable. Moreover, it is capable of providingbetter QoS guarantees for end-to-end aperiodic tasks and improving thesystem throughput.
  • [1]
    Lu Chenyang, Wang Xiaorui, Xenofon Koutsoukos. End-to-end utilization control in distributed real-time systems. -\it IEEE Trans. Parallel and Distributed Systems}, 2005, 16(6): 550--561.
    [2]
    Liao Yong, Chen Xu-Dong, Sang Nan \it et al. \rm Optimal reward based adaptive CPU resource allocation for computing devices in pervasive environment. -\it Journal of Information and Computational Science}, Mar. 2005, 2(1): 75--80.
    [3]
    Zhao Wei. Challenges in design and implementation of middlewares for real-time systems. -\it Journal of Real-Time Systems}, March 2001, 20(20): 1--2.
    [4]
    Agrawal M, Cofer D, Samad T. Real-time adaptive resource management for advanced avionics. -\it IEEE Control Systems Magazine}, February, 2003, 23(1): 76--86.
    [5]
    Atdelzater T F, Atkins E M, Shin K G. QoS negotiation in real-time systems and its application to automated flight control. -\it IEEE Trans. Computers}, Nov. 2000, 49(11): 1170--1183.
    [6]
    Sun J, Liu J W S. Synchronization protocols in distributed real-time systems. In -\it Proc. Int. Conf. Distributed Computing Systems}, Hong Kong, May 1996, pp.38--45.
    [7]
    Rajkumar R, Sha L, Lehoczky J P. Real-time synchronization protocol for multiprocessors. In -\it Proc. IEEE Real-Time Systems Symposium}, Alabama, USA, 1988, pp.259--269.
    [8]
    Strosnider J K, Lehoczky J P, Sha L. The deferrable server algorithm for enhanced aperiodic responsiveness in hard real-time environments. -\it IEEE Trans. Computers}, January 2004, 44(1): 73--91.
    [9]
    Tgywk A R, Lehoczky J P. Algorithm for scheduling hard aperiodic tasks in fixed-priority systems using slack stealing. In -\it Proc. IEEE Real-Time Systems Symposium,} Puerto Rico, December 1994, pp.22--33.
    [10]
    Lehoczky J P. Real-time queuing theory. In -\it Proc. IEEE Real-Time Systems Symposium}, Washington DC, USA, December 1996, pp.186--189.
    [11]
    Abdelzaher T F, Sharma V, Lu Chenyang. A utilization bound for aperiodic tasks and priority driven scheduling. -\it IEEE Trans. Computers}, March 2004, 53(3): 334--350.
    [12]
    Abdelzaher T F, Thaker Gautam, Lardieri Patrick. A feasible region for meeting aperiodic end-to-end deadlines in resource pipelines. In -\it IEEE Int. Conf. Distributed Computing Systems}, Tokyo, Japan, March 2004, pp.436--445.
    [13]
    Wang Xiaorui, Huang Huang-Ming, Subramonian Venkita \it et al. \rm CAMRIT: Control-based adaptive middleware for real-time image transmission. In -\it Proc. IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS 2004)}, Toronto, Canada, May 2004, pp.296--305.
    [14]
    Lu C, Stankovic J A, Tao G, Son S H. Feedback control real-time scheduling: Framework, modeling, and algorithms. -\it Journal of Real-Time Systems}, 2002, 23(1/2): 85--126.
    [15]
    Stankovic J A -\it et al}. Feedback control real-time scheduling in distributed real-time systems. In -\it Proc. IEEE Real-Time Systems Symposium}, London, UK, Dec. 2001, pp.59--70.
    [16]
    Goel Ashvin, Walpole Jonathan, Shor Molly H. Real-rate scheduling. In -\it Proc. Real-Time Application Symposium (RTAS 04)}, Toronto, Canada, May 2004, pp.434--441.
    [17]
    Li Yiushan. Principle of Automatic Control. 2nd Edition, Beijing: National Defense Publishing, 1998, pp.99--100.
    [18]
    Lu Chenyang. Feedback control real-time scheduling
    [Dissertation]. Virginia University, May 2001, pp.36--73.
    [19]
    Abdelzaher T F, Shin K G, Bhatti N. Performance guarantees for Web server end-systems: A control-theoretical approach. -\it IEEE Trans. Parallel and Distributed Systems}, January 2002, 13(1):80--96.
  • Related Articles

    [1]Shi-Hong Hu, Qu-Yuan Luo, Guang-Hui Li, Weisong Shi, Bao-Liu Ye. CA-DTS: A Distributed and Collaborative Task Scheduling Algorithm for Edge Computing Enabled Intelligent Road Network[J]. Journal of Computer Science and Technology, 2023, 38(5): 1113-1131. DOI: 10.1007/s11390-023-2839-0
    [2]Jia-Qing Dong, Ze-Hao He, Yuan-Yuan Gong, Pei-Wen Yu, Chen Tian, Wan-Chun Dou, Gui-Hai Chen, Nai Xia, Hao-Ran Guan. SMART: Speedup Job Completion Time by Scheduling Reduce Tasks[J]. Journal of Computer Science and Technology, 2022, 37(4): 763-778. DOI: 10.1007/s11390-022-2118-5
    [3]Han Lin, Ming-Fan Li, Cheng-Fan Jia, Jun-Nan Liu, Hong An. Degree-of-Node Task Scheduling of Fine-Grained Parallel Programs on Heterogeneous Systems[J]. Journal of Computer Science and Technology, 2019, 34(5): 1096-1108. DOI: 10.1007/s11390-019-1962-4
    [4]Xiao-Min Zhu, Pei-Zhong Lu. Multi-Dimensional Scheduling for Real-Time Tasks on Heterogeneous Clusters[J]. Journal of Computer Science and Technology, 2009, 24(3): 434-446.
    [5]LI Guodong, ZHANG Defu. Distributing and Scheduling Divisible Task on Parallel Communicating Processors[J]. Journal of Computer Science and Technology, 2002, 17(6).
    [6]ZHANG Yaoxue, WANG Xiaochun, GU Jun. An End-to-End QoS Control Model for Enhanced Internet[J]. Journal of Computer Science and Technology, 2000, 15(6): 497-508.
    [7]Ju Jiubin, Wang Yong, Yin Yu. Scheduling PVM Tasks[J]. Journal of Computer Science and Technology, 1997, 12(2): 167-176.
    [8]Yan Yong, Jin Canming. A Theory for the Initial Allocating of Real Time Tasks in Distributed Systems[J]. Journal of Computer Science and Technology, 1992, 7(2): 185-188.
    [9]Zhang Zhongyun, Li Guojie. Optimal Partitioning and Granularity of Uniform Task Graphs[J]. Journal of Computer Science and Technology, 1991, 6(2): 185-194.
    [10]Samuel T. Chanson, Prem S. Sinha. A Feedback Macro-Scheduler[J]. Journal of Computer Science and Technology, 1989, 4(3): 255-274.

Catalog

    Article views (24) PDF downloads (20420) Cited by()
    Related

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return