Title :
Time/utility function decomposition techniques for utility accrual scheduling algorithms in real-time distributed systems
Author :
Wu, Haisang ; Ravindran, Binoy ; Jensen, E. Douglas ; Li, Peng
Author_Institution :
Dept. of Electr. & Comput. Eng., Virginia Tech, Blacksburg, VA, USA
Abstract :
We consider Real-Time CORBA 1.2\´s distributable threads (DTs), whose time constraints are specified using time/utility functions (TUFs), operating in legacy environments. In legacy environments, system node resources - both physical and logical - are shared among time-critical DTs and local applications that may also be time-critical. Hence, DTs that are scheduled using their propagated TUFs, as mandated by Real-Time CORBA 1.2\´s Case 2 approach, may suffer performance degradation, if a node utility accrual (UA) scheduler achieves higher locally accrued utility by giving higher eligibility to local threads than to DTs. To alleviate this, we consider decomposing TUFs of DTs into "sub-TUFs" for scheduling segments of DTs. We present five decomposition techniques, called UT, SCEQF, SCALL, OPTCON, and TUFS, which are specific to different classes of UA scheduling algorithms, such as those that use utility density and those that use deadline as their key decision metric. Our experimental studies identify the decomposition technique that performs best for each class of UA scheduling algorithms. In particular, our studies show that OPTCON and TUFS perform best for utility density-based UA algorithms, while SCEQF and SCALL perform best for deadline-based UA algorithms.
Keywords :
distributed object management; multi-threading; real-time systems; resource allocation; scheduling; utility programs; Real-Time CORBA 1.2; deadline scheduling; distributable threads; embedded system; legacy environment; real-time distributed system; resource sharing; time constraints; time function decomposition; utility accrual scheduling algorithm; utility function decomposition; Central Processing Unit; Degradation; Helium; Java; Optimal control; Phased arrays; Real time systems; Scheduling algorithm; Time factors; Yarn; Index Terms- Distributable thread; Real-Time CORBA 1.2.; time constraint decomposition; time/utility function; value function;
Journal_Title :
Computers, IEEE Transactions on
DOI :
10.1109/TC.2005.153