Our Research Project's Published Professional Documents

This page contains an annotated bibliography of (primarily) my FY 2003-2008 research projects'  documents co-authored by my colleagues and I, that have been published (or have been accepted and are awaiting publication) in professional society journals and conference proceedings.

Most are about expanding the scope and formal basis of my timeliness paradigm, but some are about other topics of interest to my research project — e.g., real-time failure recovery, multiprocessor scheduling, real-time P2P and Pub/Sub protocols, lock- and wait-free synchronization, software transactional memory. A few earlier papers are included because of their relevance to my recent projects.

In most cases the entry includes abstracts, my comments, and links that allow browsing or downloading the documents.

(Beware that conversions from PDF to HTML are awful for anything other than simple text, so browsing a paper is only for casual perusal; and that I am very behind in doing the conversions.)

Comments: TBD

Comments: TBD

Channakeshava et al. 06
Utility Accrual Real-Time Channel Establishment in Multi-hop Networks

Karthik Channakeshava, Binoy Ravindran, and E. Douglas Jensen

IEEE Transactions on Computers, 2006

Abstract. We consider Real-Time CORBA 1.2 (Dynamic Scheduling) distributable threads operating in multi-hop networks. When distributable threads are subject to time/utility function time constraints, and timeliness optimality criteria such as maximizing accrued system-wide utility is desired, utility accrual real-time channels must be established. Such channels transport messages that are generated as distributable threads transcend nodes, in a way that maximizes system-wide, message-level utility. We present (1) a localized utility accrual channel establishment algorithm called Localized Decision for Utility accrual Channel Establishment (or LocDUCE) and (2) a distributed utility accrual channel establishment algorithm called Global Decision for Utility accrual Channel Establishment (or GloDUCE). Since the channel establishment problem is NP-complete, LocDUCE and GloDUCE heuristically compute channels with LocDUCE making decisions based on local information pertaining to the node and GloDUCE making global decisions. We simulate the performance of both the algorithms and compare them with the Open Shortest Path First (OSPF) routing algorithm and the optimal algorithm. We also implement these algorithms in a prototype test-bed and experimentally compare their performance with OSPF. Our simulation and experimental measurements reveal that GloDUCE and LocDUCE accrues significantly higher utility than OSPF, and also perform close to the optimal for some cases. Furthermore, GloDUCE outperforms LocDUCE under high downstream traffic.

Browse (HTML), Download (PDF)

Comments: TBD

Channakeshava et al. 05
IP Quality of Service Support for Soft Real-Time Applications

K. Channakeshava, K. Phanse, L. A. DaSilva, B. Ravindran, S. F. Midkiff, and E. D. Jensen

International Workshop on Real-Time Networks (RTN), IEEE Euromicro Conference on Real-Time Systems, 2006

Abstract. To obtain acceptable timeliness performance for emerging large-scale distributed real-time control applications operating in large IP internetworks, a scalable quality of service (QoS) architecture is needed. In this paper, we propose a scalable QoS architecture (abbreviated as RTQoS) in support of real-time systems, one that implements real-time scheduling at end-hosts and stateless QoS in the core routers. We address challenges and explore potential benefits achieved by integrating network services with real-time systems, through the use of a network testbed. Experimental evaluation demonstrates the RTQoS architecture as a promising approach for soft real-time applications that are subject to time/utility function time constraints and utility accrual optimality criteria.

Browse (HTML), Download (PDF)

Comments: TBD

Cho et al. 10
T-N Plane-Based Real-Time Scheduling for Homogeneous Multiprocessors

Hyeonjoong Cho, Binoy Ravindran, and E. Douglas Jensen

Journal of Parallel and Distributed Computing, to appear 2010

Abstract. We consider optimal real-time scheduling of periodic tasks on multiprocessors — i.e., satisfying all task deadlines, when the total utilization demand does not exceed the utilization capacity of the processors. We introduce a novel abstraction for reasoning about task execution behavior on multiprocessors, called T-N plane, and present T-N plane-based real-time scheduling algorithms. We show that scheduling for multiprocessors can be viewed as scheduling on repeatedly occurring T-N planes, and feasibly scheduling on a single T-N plane results in an optimal schedule. Within a single TN plane, we analytically show a sufficient condition to provide a feasible schedule. Based on these, we provide two examples of T-N plane-based real-time scheduling algorithms, including non-work-conserving and work-conserving approaches. Further, we establish that the algorithms have bounded overhead. Our simulation results validate our analysis of the algorithm overhead. In addition, we experimentally show that our approaches have a reduced number of task migrations among processors, compared to a previous algorithm.

Browse (HTML), Download (PDF)

Comments:TBD

Cho et al. 08
Lock-Free Synchronization for Dynamic Embedded Real-Time Systems

Hyeonjoong Cho, Binoy Ravindran, and E. Douglas Jensen

ACM Transactions on Embedded Computing Systems, to appear 2009

Abstract. We consider lock-free synchronization for dynamic embedded real-time systems that are subject to resource overloads and arbitrary activity arrivals. We model activity arrival behaviors using the unimodal arbitrary arrival model (or UAM). UAM embodies a stronger “adversary” than most traditional arrival models. We derive an upper bound on lock-free retries under the UAM with utility accrual scheduling — the first such result. We establish the tradeoffs between lock-free and lock-based sharing under UAM. These include conditions under which activities’ accrued timeliness utility is greater under lock-free than lock-based, and the consequent lower and upper bound on the total accrued utility that is possible with lock-free and lock-based sharing. We confirm our analytical results with a POSIX RTOS implementation.

Browse (HTML), Download (PDF)

Comments:This is the journal-length version of Cho et al. 06. It also was selected to appear as "On Lock-Free Synchronization for Dynamic Embedded Real-Time Software," in the book Design, Automation, and Test in Europe: The Most Influential Papers of 10 Years, ISBN: 978-1-4020-6487-6, Rudy Lauwereins and Jan Madsen (Editors), Section 1: System Level Design, Springer-Verlag, January 2008

Cho et al. 07b
On Scheduling Garbage Collector in Dynamic Real-Time Systems with Statistical Timeliness Assurances

Hyeonjoong Cho, Binoy Ravindran, and E. Douglas Jensen

Journal of Real-Time Systems

Abstract. We consider garbage collection (GC) in dynamic real-time sys- tems. We consider the time-based GC approach of running the collector as a separate, concurrent thread, and focus on real-time scheduling to obtain assurances on mutator timing behavior, while ensuring that memory is never exhausted. We present a scheduling algorithm called GCUA. The algorithm considers mutator activities that are subject to time/utility function time constraints, variable execution time demands, the unimodal arbitrary arrival model that allows a strong adversary, and resource overloads. We establish several properties of GCUA including probabilistically-satisfied utility lower bounds for each mutator activity, a lower bound on the system-wide total accrued utility, bounded sensitivity for the assurances to variations in mu- tator execution time demand estimates, and no memory exhaustion at all times. Our simulation experiments validate our analytical results and con- ¯rm the algorithm's e®ectiveness and superiority.

Browse (HTML), Download (PDF)

Comments: TBD

Cho et al. 07a
Synchronization for an Optimal Real-Time Scheduling Algorithm on Multiprocessors

Hyeonjoong Cho, Binoy Ravindran, and E. Douglas Jensen

Proc. of the IEEE Second International Symposium on Industrial Embedded Systems

Abstract. We consider several object sharing synchronization mechanisms including lock-based, lock-free, and wait-free sharing for LNREF [Cho et al. 06e], an optimal real-time scheduling algorithm on multiprocessors. We derive LNREF’s minimum-required space cost for wait-free synchronization using the space-optimal waitfree algorithm. We then establish the feasibility conditions for lock-free and lock-based sharing under LNREF, and the concomitant tradeoffs. While the tradeoff between wait-free versus the other sharing is obvious, i.e., space and time costs, we show that the tradeoff between lock-free and lock-based sharing for LNREF hinges on the cost of the lock-free retry, blocking time under lock-based. Finally, we numerically evaluate lock-free and lock-based sharing for LNREF.

Browse (HTML), Download (PDF)

Comments: TBD

Cho et al. 07
Space-Optimal Wait-Free Real-Time Synchronization

Hyeonjoong Cho, Binoy Ravindran, Haisang Wu, and E. Douglas Jensen

IEEE Transaction on Computers, Volume 56, Number 3, pages 385-401, March 2007

Abstract. We present a wait-free protocol for the single-writer/multiple-reader problem in small-memory embedded real-time systems. We analytically establish that our protocol requires lesser (or equal) number of buffers than previously best wait-free protocols for this problem. Further, we prove that our protocol is space-optimal — the first space optimality established for wait-free protocols that consider a' priori knowledge of preemptions. Our evaluation studies and implementation measurements using the SHaRK RTOS kernel confirm the protocol’s superiority and effectiveness.

Browse (HTML), Download (PDF)

Comments: TBD

Cho et al. 06d
An Optimal Real-Time Scheduling Algorithm for Multiprocessors

Hyeonjoong Cho, Binoy Ravindran, and E. Douglas Jensen

Proc. of the 2006 Real-Time Systems Symposium

Abstract. We present an optimal real-time scheduling algorithm for multiprocessors — one that satisfies all task deadlines, when the total utilization demand does not exceed the utilization capacity of the processors. The algorithm called LLREF, is designed based on a novel abstraction for reasoning about task execution behavior on multiprocessors: the Time and Local Execution Time Domain Plane (or TL plane). LLREF is based on the fluid scheduling model and the fairness notion, and uses the T-L plane to describe fluid schedules without using time quanta, unlike the optimal Pfair algorithm (which uses time quanta). We show that scheduling for multiprocessors can be viewed as repeatedly occurring T-L planes, and feasibly scheduling on a single T-L plane results in the optimal schedule. We analytically establish the optimality of LLREF. Further, we establish that the algorithm has bounded overhead, and this bound is independent of time quanta (unlike Pfair). Our simulation results validate our analysis on the algorithm overhead.

Browse (HTML), Download (PDF)

Comments: TBD

Cho et al. 06c
On Multiprocessor Utility Accrual Real-Time Scheduling With Statistical Timing Assurances

Hyeonjoong Cho, Binoy Ravindran, Haisang Wu, and E. Douglas Jensen

Proc. of the IFIP International Conference on Embedded And Ubiquitous Computing, 2006

Abstract. We present the first Utility Accrual (or UA) real-time scheduling algorithm for multiprocessors, called gMUA. The algorithm considers an application model where real-time activities are subject to time/utility function time constraints, variable execution time demands, and resource overloads where the total activity utilization demand exceeds the total capacity of all processors. We consider the scheduling objective of (1) probabilistically satisfying lower bounds on each activity’s maximum utility and (2) maximizing the system-wide, total accrued utility. We establish several properties of gMUA including optimal total utility (for a special case), conditions under which individual activity utility lower bounds are satisfied, a lower bound on system-wide total accrued utility, and bounded sensitivity for assurances to variations in execution time demand estimates. Our simulation experiments validate our analytical results and confirm the algorithm’s effectiveness and superiority.

Browse (HTML), Download (PDF)

Comments: TBD

Cho et al. 06b
On Utility Accrual Processor Scheduling with Wait-Free Synchronization for Embedded Real-Time Software

Hyeonjoong Cho, Binoy Ravindran, and E. Douglas Jensen

Proc. of the ACM Symposium On Applied Computing, 2006

Abstract. We present the first wait-free utility accrual (UA) real-time scheduling algorithms for embedded real-time systems. UA scheduling algorithms allow application activities to be subject to time/utility function (TUF) time constraints, and optimize criteria such as maximizing the sum of the activities' attained utilities. We present UA algorithms that use wait-free synchronization for mutually exclusively accessing shared data objects. We derive upper bounds on the maximum possible increase in activity utility with wait-free over their lock-based counterparts, while incurring the minimum possible additional space costs, and thereby establish the tradeoffs between wait-free and lock-based object sharing for UA scheduling. Our implementation measurements on a POSIX RTOS reveal that (during under-loads), the wait-free algorithms yield optimal utility for step TUFs and significantly higher utility (than lock-based) for non-step TUFs.

Browse (HTML), Download (PDF)

Comments: TBD

Cho et al. 06a
On Scheduling A Garbage Collector in Dynamic Real-Time Systems With Statistical Timeliness Assurances

Hyeonjoong Cho, C. Na, Binoy Ravindran, and E. Douglas Jensen

Proc. of the IEEE International Symposium on Object and component-oriented Real-time distributed Computing (ISORC), 2006

Abstract. We consider garbage collection (GC) in dynamic real-time systems. We consider the time-based GC approach of running the collector as a separate, concurrent thread, and focus on real-time scheduling to obtain assurances on mutator timing behavior, while ensuring that memory is never exhausted. We present a scheduling algorithm called GCUA. The algorithm considers mutator activities that are subject to time/utility function time constraints, variable execution time demands, the unimodal arbitrary arrival model that allows a strong adversary, and resource overloads. We establish several properties of GCUA including probabilistically-satisfied utility lower bounds for each mutator activity, a lower bound on the system-wide total accrued utility, bounded sensitivity for the assurances to variations in mutator execution time demand estimates, and no memory exhaustion at all times. Our simulation experiments validate our analytical results and confirm the algorithm’s effectiveness and superiority.

Browse (HTML), Download (PDF)

Comments: TBD

Cho et al. 06
Lock-Free Synchronization for Dynamic Embedded Real-Time Systems

Hyeonjoong Cho, Binoy Ravindran, and E. Douglas Jensen

Proc. of the ACM Design Automation and Test in Europe, 2006

Abstract. We consider non-blocking synchronization for dynamic embedded real-time systems such as those that are subject to resource overloads and arbitrary activity arrivals. The multi-writer/multi-reader problem inherently occurs in such systems, when their activities must concurrently and mutually exclusive share data objects. We consider lock-free synchronization for this problem under the unimodal arbitrary arrival model (or UAM). UAM embodies a "stronger" adversary than most traditional arrival models. We establish the fundamental tradeoffs between lock-free and lock-based object sharing under UAM — the first such result. Our tradeoffs include analytical conditions under which activities’ accrued timeliness utility is greater under lock-free than lock-based, and the consequent upper bound on the increase in accrued utility. Our implementation experience on a POSIX RTOS reveals that the lock-free scheduling algorithm yields higher accrued utility, by as much as 65%, and critical time satisfactions, by as much as 80%, over lock-based.

Browse (HTML), Download (PDF)

Comments: TBD

Cho et al. 05
A Space-Optimal, Wait-Free Real-Time Synchronization Protocol

Hyeonjoong Cho, Binoy Ravindran, and E. Douglas Jensen

Proc. of the 17th Euromicro Conference on Real-Time Systems, 2005

Abstract. We present a wait-free protocol for the single-writer, multiple-reader problem in small-memory, embedded real-time systems. We analytically establish that our protocol requires lesser (or equal) number of buffers than what is needed by previously best wait-free protocols for this problem. Further, we prove that our protocol is space-optimal -- the first such bound established for wait-free protocols that consider a' priori knowledge of preemptions. Our evaluation studies and implementation measurements (from an implementation using the SHaRK real-time OS kernel) confirm the protocol's superiority and effectiveness.

Browse (HTML), Download (PDF)

Comments: TBD

Clark et al. 04
Software Organization to Facilitate Dynamic Processor Scheduling

Raymond K. Clark, E. Douglas Jensen, and Nicolas F. Rouquette

Proc. of the IEEE Workshop on Parallel and Distributed Real-Time Systems, 2004

Abstract. The NASA Jet Propulsion Laboratory (JPL) is developing the Mission Data System (MDS) for potential use in future space missions, where it is expected to reduce the complexity and effort required to produce mission and ground support software, while also enabling greater autonomy for remotely deployed systems, including future planetary rovers. The MDS software architecture includes two levels of processor scheduling: a high-level planner and a low level execution manager. JPL and MITRE are investigating  the use of Time-Utility Functions to manage low-level scheduling, since they promise to enable adaptive, short term processor scheduling based on mission utility. Recent development work on MDS has focused on organizing the software so that low-level processor scheduling will be most effective. This paper describes the major organizing principles that have shaped this work.

Browse (HTML), Download (PDF)

Comments: This paper is the first public announcement of the new collaboration between the MITRE Corporation and NASA JPL to implement time/utility function time constraints and utility accrual scheduling optimality criteria in JPL's Mission Data System. This paper summarizes our initial goal and principles for adapting the MDS software to accommodate dynamic scheduling in general and TUF/UA scheduling in particular. The work was performed in the last quarter of FY03. Our on-going work in FY04 was to include the design and implementation of the TUF/UA scheduler in the MDS, and its experimental evaluation in the JPL prototype Mars rover. That work has been deferred to FY05 due to new management at JPL making major changes to the 2009 Mars Science Lab mission, which was expected to be the first application of the MDS.

Clark et al. 02
The Distributed Real-Time Specification for Java: Overview and Status

Raymond Clark, E. Douglas Jensen, Doug Wells, and Andy Wellings

TBD

Abstract. None, see Comments below.

Browse (HTML), Download (PDF)

Comments: The Distributed Real-Time Specification for Java (DRTSJ) is being developed under Sun’s Java Community Process. It is focused on adaptively supporting application-specific predictability of end-to-end timeliness for sequentially distributed computations (e.g., chains of invocations) in dynamic distributed object systems. This presentation includes new and revised material about the objectives and direction of the DRTSJ, plus updated material on the technical approach and status. For details about some of the technical approach, see [Wellings et al 02]. The DRTSJ work slowed significantly for about 18 months due to higher priority demands for the principals at MITRE. It resumed in September 2004 due to one of the principals (Jonathan Anderson) becoming a Ph.D. student at Virginia Institute of Technology (with whom Jensen has a close working relationship). Jonathan will focus his first year on getting the DRTSJ completed, with participation by people at VA Tech, MITRE, and several other organizations.

Clark et al. 99
An Adaptive, Distributed Airborne Tracking System
("Process the Right Tracks at the Right Time")

Raymond Clark, E. Douglas Jensen, Arkady Kanevsky, John Maurer, Paul Wallace, Thomas Wheeler, Yun Zhang, Douglas Wells, Tom Lawrence, and Pat Hurley

Proc. of the IEEE Workshop on Parallel and Distributed Real-Time Systems, April 1999

Abstract. This paper describes a United States Air Force sponsored Advanced Technology Demonstration that applied value-based scheduling to produce an adaptive, distributed tracking component appropriate for consideration by the Airborne Warning and Control System (AWACS) program. This tracker was designed to evaluate application-specific Quality of Service (QoS) metrics to quantify its tracking services in a dynamic environment and to derive scheduling parameters directly from these QoS metrics to control tracker behavior. The prototype tracker was implemented on the MK7 operating system, which provided native value-based processor scheduling and a distributed thread programming abstraction. The prototype updates all of the tracked-object records when the system is not overloaded, and gracefully degrades when it is. The prototype has performed extremely well during demonstrations to AWACS operators and tracking system designers. Quantitative results are presented.

Browse (HTML), Download (PDF)

Comments: Recently people have begun to accept the notion that QoS is a valid and valuable concept above the network layers where the term originated and is most frequently used (referring to bit error rate, latency, bandwidth, jitter, etc.). In particular, QoS is proving to be an extremely effective technique for expressing application level functional and non-functional behavioral requirements and driving resource management to achieve them. However, virtually all the papers in the literature about application level QoS focus on multimedia applications, where the application level QoS properties are essentially identical to the network level QoS properties. This paper is a rare example of using QoS at the application level of a non-multimedia application -- i.e., track quality and number of dropped tracks in an airborne tracking system. Since this paper was published, the application has been rewritten in Java and in RTSJ-compliant real-time Java, and the performance of these implementations quantitatively evaluated against the original C++ implementation reported on in this paper. The Java version's performance with respect to the AQoS metrics was only slightly lower than that of the C++ version.

Clark et al. 93a
Effects of Multilevel Security on Real-Time Applications

Raymond K. Clark, Douglas M. Wells, Ira B. Greenberg, E. Douglas Jensen, Peter K. Boucher, and Teresa F. Lunt

Proc. of the IEEE Computer Security and Applications Conference, 1993

Abstract. This paper presents a brief overview of a notional
airborne application scenario that requires both multilevel
security and real-time processing. It was used to guide decisions related to formation of the security policy interpretation, the operating system interface, and the system services design for a multilevel secure real-time distributed operating system (MLS RT DOS) called Secure Alpha. We compare secure and nonsecure application designs for the scenario to assess the effects of MLS RT DOS security features on the structure of the application. The comparison reveals that the security features make real-time scheduling and the construction of robust applications more difficult for
this scenario.

Browse (HTML), Download (PDF)

Comments: Aside from the obvious interest this paper has for distributed real-time systems that must meet the DoD Orange Book requirements for multilevel security, it also provides insight into the application of distributed threads.

Curley et al. 09
Recovering from Distributable Thread Failures in Real-Time Java

Ed Curley, Binoy Ravindran, Jonathan Anderson, and E. Douglas Jensen

ACM Transactions on Embedded Computing Systems, to appear

Abstract. We consider the problem of recovering from failures of distributable threads (“threads”) in distributed realtime systems that operate under run-time uncertainties including those on thread execution times, thread arrivals, and node failure occurrences. When a thread experiences a node failure, the result is broken thread having an orphan. Under a termination model, the orphans must be detected and aborted, and exceptions must be delivered to the farthest, contiguous surviving thread segment for resuming thread execution. Our application/scheduling model includes the proposed distributable thread programming model for the emerging Distributed Real-Time Specification for Java (DRTSJ), together with an exception handler model. Threads are subject to time/utility function (TUF) time constraints and an utility accrual (UA) optimality criterion. A key underpinning of the TUF/UA scheduling paradigm is the notion of “best-effort” where higher importance threads are always favored over lower importance ones, irrespective of thread urgency as specified by their time constraints. We present a thread scheduling algorithm called HUA and a thread integrity protocol called TPR. We show that HUA and TPR bound the orphan cleanup and recovery time with bounded loss of the best-effort property. Our implementation experience of HUA/TPR in the Reference Implementation of the proposed programming model for the DRTSJ demonstrates the algorithm/protocol’s effectiveness.

Browse (HTML), Download (PDF)

Comments: TBD.

Curley et al. 07
On Best-Effort Real-Time Assurances for Recovering from Distributable Thread Failures

Ed Curley, Binoy Ravindran, and E. Douglas Jensen

2007 IEEE International Symposium on Object and component-oriented Real-time distributed Computing

Abstract. We consider the problem of recovering from failures of distributable threads in distributed real-time systems that operate under run-time uncertainties including those on thread execution times, thread arrivals, and node failure occurrences. When a thread encounters a node failure, it causes orphans. Under a termination model, the orphans must be detected and aborted, and exceptions must be delivered to farthest, contiguous surviving thread segment for resuming thread execution. Our application/scheduling model includes distributable threads and their exception handlers that are subject to time/utility function (TUF) time constraints and an utility accrual (UA) optimality criterion. A key underpinning of the TUF/UA scheduling paradigm is the notion of “best-effort” where high importance threads are always favored over low importance ones, irrespective of thread urgency. (This is in contrast to classical admission control models which favor feasible completion of admitted threads over admitting new ones, irrespective of thread importance.) We present a scheduling algorithm called HUA and a thread integrity protocol called TPR. We show that HUA and TPR bound the orphan cleanup and recovery time with bounded loss of the best-effort property. Our implementation experience of HUA/TPR using the emerging Reference Implementation of Sun’s Distributed Real-Time Specification for Java demonstrates the algorithm/protocol’s effectiveness.

Browse (HTML), Download (PDF)

Comments: TBD.

Curley et al. 06
Recovering from Distributable Thread Failures with Assured Timeliness in Real-Time Distributed Systems

E. Curley, J. Anderson, B. Ravindran, and E. D. Jensen

Proc. IEEE Symposium on Reliable Distributed Systems, October 2006

Abstract. We consider the problem of recovering from failures of distributable threads with assured timeliness. When a node hosting a portion of a distributable thread fails, it causes orphans — i.e., segments of distributable threads that are disconnected from the thread’s root. We consider a termination model for recovering from such failures, where the orphans must be detected and aborted, resources held by them must be released and rolled back to safe states, and exceptions must be delivered to farthest, contiguous surviving thread segment from where execution can be resumed. Since distributable threads are subject to time constraints in real-time distributed systems, such recovery must be conducted with assured timeliness. Toward this, we present 1) a real-time scheduling algorithm called AUA, and 2) a distributable thread integrity protocol called TP-TR. We show that AUA and TP-TR bound the orphan cleanup and recovery time (thereby bounding thread starvation durations), maximize total thread accrued timeliness utility, and satisfy thread mutual exclusion constraints. We implement AUA and TPTR in a real-time middleware that supports distributable threads. Our experimental studies with the implementation validate the algorithm/protocol’s time-bounded recovery property and confirm their effectiveness.

Browse (HTML), Download (PDF)

Comments: TBD.

Fahmy et al. 09a
On Bounding Response Times under Software Transactional Memory in Distributed Multiprocessor Real-Time Systems

Sherif Fahmy, Binoy Ravindran, and E. Douglas Jensen

ACM Design, Automation, and Test in Europe, Real-Time Systems Track, April 2009

Abstract. We consider multiprocessor distributed real-time systems where concurrency control is managed using software transactional memory (or STM). For such a system, we propose an algorithm to compute an upper bound on the response time. The proposed algorithm can be used to study the behavior of systems where node crash failures are possible. We compare the result of the proposed algorithm to a simulation of the system being studied in order to determine its efficacy. The results of our study indicate that it is possible to provide timeliness guarantees for multiprocessor distributed systems programmed using STM.

Browse (HTML), Download (PDF)

Comments: TBD.

Fahmy et al. 09
Response time analysis of software transactional memory-based distributed real-time systems

Sherif Fahmy, Binoy Ravindran, and E. Douglas Jensen

ACM Symposium on Applied Computing (SAC), Track on Operating Systems, March 2009

Abstract. We consider distributed real-time systems where concurrency control is managed using software transactional memory (or STM). For such a method we propose an algorithm to compute an upper bound on the response time. The proposed algorithm can be used to study the behavior of systems where node crash failures are possible. We compare the result of the proposed algorithm to a simulation of the system being studied in order to determine its efficacy. The results of our study indicate that it is possible to provide timeliness guarantees for systems programmed using STM.

Browse (HTML), Download (PDF)

Comments: TBD.

Fahmy et al. 08d
On Scalable Synchronization for Distributed Embedded Real-time Systems

Sherif Fahmy, Binoy Ravindran, and E. Douglas Jensen

IFIP Workshop on Software Technologies for Future Embedded & Ubiquitous Systems (SEUS 2008), invited paper, October 2008

Abstract. We consider the problem of programming distributed embed- ded real-time systems with distributed dependencies. We show that the de facto standard of using locks and condition variables in conjunction with threads can have signi¯cant overhead and semantic difficulty and suggest alternative programming abstractions to alleviate these prob- lems. We also discuss several alternatives for implementing these programming abstractions and discuss the algorithms and protocols needed.

Browse (HTML), Download (PDF)

Comments: TBD.

Fahmy et al. 08c
Scheduling Dependent Distributable Real-Time Threads in Dynamic Networked Embedded Systems

Sherif Fahmy, Binoy Ravindran, and E. Douglas Jensen

IFIP Working Conference on Distributed and Parallel Embedded Systems, September 2008

Abstract. We consider scheduling distributable real-time threads with dependencies (e.g, due to synchronization) in partially synchronous systems in the presence of node failures. We present a distributed real-time scheduling algorithm called DQBUA. The algorithm uses quorum systems to coordinate nodes’ activities when constructing a global schedule. DBQUA detects and resolves distributed deadlock in a timely manner and allows threads to access resources in order of their potential utility to the system. Our main contribution is handling resource dependencies using a distributed scheduling algorithm.

Browse (HTML), Download (PDF)

Comments: TBD. A full-length version of the paper is available as a technical report here.

Fahmy et al. 08b
On Collaborative Scheduling of Distributable Real-Time Threads in Dynamic, Networked Embedded Systems

Sherif Fahmy, Binoy Ravindran, and E. Douglas Jensen

IEEE International Symposium on Object and component-oriented Real-time distributed Computing 2008, May 2008

Abstract. Some emerging networked embedded real-time applications have relatively long reaction time magnitudes -- e.g., milliseconds to minutes. These longer execution time magnitudes allow opportunities for more computationally expensive scheduling algorithms than what is traditionally considered for device-level real-time control sub-systems. In this paper, we review recent research conducted on collaborative scheduling algorithms in such systems that are subject to dynamic behavior such as transient and sustained resource overloads, arbitrary activity arrivals, and arbitrary node failures and message loss. We show that collaborative scheduling algorithms have an advantage over non-collaborative scheduling algorithms.

Browse (HTML), Download (PDF)

Comments: TBD

Fahmy et al. 08a
Fast Scheduling of Distributable Real-Time Threads with Assured End-to-End Timeliness

Sherif Fahmy, Binoy Ravindran, and E. Douglas Jensen

13th International Conference on Reliable Software Technologies - Ada-Europe 2008, March 2008

Abstract. We consider networked, embedded real-time systems that operate under run-time uncertainties on activity execution times and arrivals, node failures, and message losses. We consider the distributable threads abstraction for programming and scheduling such systems, and present a thread scheduling algorithm called QBUA. We show that QBUA satisfies (end-to-end) thread time constraints in the presence of crash failures and message losses, has efficient message and time complexities, and lower overhead and superior timeliness properties than past thread scheduling algorithms. Our experimental studies validate our theoretical results, and illustrate the algorithm's effectiveness.

Browse (HTML), Download (PDF)

Comments: TBD. A full length version is available here.

Fahmy et al. 08
Scheduling Distributable Real-Time Threads in the Presence of Crash Failures and Message Losses

Sherif Fahmy, Binoy Ravindran, and E. Douglas Jensen

ACM Symposium On Applied Computing (Track on Embedded Systems), March 2008

Abstract. We consider the problem of scheduling distributable real-time threads under run-time uncertainties including those on thread execution times, thread arrivals, node failures, and message losses. We present a distributed scheduling algorithm called ACUA that is designed under a partially synchronous model, allowing for probabilistically-described message delays. We show that ACUA satisfies thread time constraints in the presence of crash failures and message losses, is early-deciding, and has an efficient message and time complexity. The algorithm has also better "best-effort" real-time property than past thread scheduling algorithms.

Browse (HTML), Download (PDF)

Comments: 

Feizabadi et al. 05
MSA: A Memory-Aware Utility Accrual Scheduling Algorithm

S. Feizabadi, B. Ravindran, and E. D. Jensen

ACM Symposium On Applied Computing (Track on Embedded Systems), March 2005

Abstract. Whereas fairness can be the basis for general-purpose operating system scheduling policies, timeliness is the primary concern for real-time systems. As such, real-time schedulers permit uninterrupted, exclusive access to the CPU by a specific task to ensure its timely completion of execution. Only a subset of tasks, however, can satisfy their timing constraints during processor overload conditions in a real-time system. Utility accrual (UA) scheduling disciplines assure scalability and graceful performance degradation by identifying – based on a pre-defined set of criteria – the subset of tasks to be granted the heavily contended system resources. Furthermore, whereas general-purpose operating systems treat memory monolithically and indiscriminately service dynamic allocation requests, UA schedulers can benefit from special memory management considerations during memory overload conditions. MSA, the scheduling algorithm here presented is the first of its kind to treat memory as a UA scheduler-managed resource. The scheduler is made aware of memory allocation requirements of each task throughout runtime and accordingly makes appropriate CPU and resource scheduling decisions. The algorithm is well-suited for use in resource constrained embedded systems in a soft real-time environment. We have implemented MSA in a POSIX real-time operating environment and measured its performance under various load conditions. Our experimental results show overall performance gains over other memory-unaware UA scheduling algorithms during memory overload.

Browse (HTML), Download (PDF)

Comments: This paper discusses the first utility accrual algorithm that takes memory requirements into account.

Goldberg et al. 95
Adaptive Fault Resistant Systems

Jack Goldberg, Ira Greenberg, Raymond Clark, E. Douglas Jensen, Kane Kim, and Douglas M. Wells

Technical Report CSL-95-02, Computer Science Lab, SRI International, Menlo Park, CA. January 1995

Abstract. In future distributed computing systems, data-arrival rates, fault types, resource availability and user preferences among performance and dependability objectives, all may vary dynamically during operation. The report describes architectural approaches and techniques for building computer systems that dynamically adapt their structure to changing operating conditions and user preferences. The concepts of stability management and system identification from modern control theory are given digital-system interpretations. These are reflective control and real-time fault diagnosis. Several cases were studied and demonstrated, including adaptive distributed recovery blocks, and adaptive distributed thread maintenance. A formal scheme was developed for adaptive, hybrid byzantine-backup fault tolerance.

Browse (HTML), Download (PDF)

Comments: This technical report includes the first publication of techniques for adaptive maintenance of the distributed threads programming abstraction pioneered in the Alpha distributed real-time OS kernel [Clark et al. 93].

Gouda et al. 77
Chapter 3, Radar Scheduling: Section 1, The Scheduling Problem

Mohammed G. Gouda, Yi-Wu Han, E. Douglas Jensen, Wesley D. Johnson, Richard Y. Kain

Distributed Data Processing Technology, Vol. IV, Applications of DDP Technology to BMD: Architectures and Algorithms, Honeywell Systems and Research Center, Minneapolis, MN. September 1977. NTIS ADA047475.

Abstract. to be supplied

Browse (HTML) not available, Download (PDF) not available

Comments: This is the unclassified (and now unlimited distribution) summary technical report that included the first mention of Jensen's concept of scheduling based on utility function time constraints. The application was Ballistic Missile Defense radar -- specifically the U.S. Army Safeguard Command's AN/FPQ-16 Perimeter Acquisition Radar Characterization System at what is now the USAF Space Command's Cavalier Air Force Station, in Cavalier, North Dakota. The radar was scheduled by a supercomputer of that time, but the efficiency of the radar was unacceptably low. Jensen devised the concept of time/utility function time constraints, and this team simulated scheduling the radar with both software and hardware implementations of these functions. The simulated radar efficiency was much higher -- so much so that someone in the Federal government decided that it was enough to potentially be considered by the USSR as a violation of the 1972 ABM treaty (SALT II). The antiballistic missile defense system was terminated about that same time. Hence, the technology was not deployed, and the detailed technical reports about our research on this topic remain classified to this day -- with the exception of a passing mention in this highly sanitized summary document. When I left Honeywell's Systems and Research Center and joined the Computer Science faculty at Carnegie Mellon University, I resuscitated the concept; two of my students (Doug Locke and Ray Clark) wrote their Ph.D. theses on the topic [Locke 87][Clark 90]. CMU and General Dynamics (the Ft. Worth division now part of Lockheed Martin) successfully applied time/utility function scheduling to a notional coastal air defense battle management application [Maynard et al. 88] (see the GD BM/C2 demo page); then MITRE applied time/utility function scheduling to an  AWACS airborne radar tracking application with great effectiveness [Clark et al. 99]; see the AWACS ATD page. Advancement of the theory and application (including to radar scheduling) of time/utility functions is on-going at MITRE and a number of universities, especially collaboratively between MITRE and Virginia Institute of Technology (as can be seen by the many papers we have published in conference proceedings and journals). (More about this is gradually appearing on my time/utility function history page.)

Han 08a
RTRD: Real-Time and Reliable Data Delivery in Ad Hoc Networks

Kai Han, Guanhong Pei, Hyeonjoong Cho, Binoy Ravindran, and E. Douglas Jensen

Proc. of the IEEE Wireless Communications and Networking Conference, March/April 2008

Abstract. In this paper, we present a reliable real-time data delivery (communication) mechanism for ad-hoc networks, called RTRD. The mechanism makes use of a proactive wireless routing protocol (DSDV) for path finding and maintenance, and timely delivers data through a' priori bandwidth reservation. In addition, to be robust to network failures, or to deliver large data chunks, it simultaneously delivers data in multiple paths. The simulation results conducted by NS-2 validate RTRD's effectiveness.

Browse (HTML), Download (PDF)

Comments: To be supplied.

Han 08
LRTG: Scheduling Distributed Real-Time Tasks in Unreliable and Untrustworthy Systems

Kai Han, Binoy Ravindran, and E. Douglas Jensen

Proc. of the IEEE International Symposium on Frontiers in Networking with Applications (FINA), IEEE International Conference on Advanced Information Networking and Applications, March 2008

Abstract. We consider scheduling distributed real-time tasks in unreliable (e.g., those with arbitrary node and network failures) and untrustworthy systems (e.g., those with Byzantine node behaviors). We present a distributed real-time scheduling algorithm called LRTG. The algorithm makes two novel contributions. First, LRTG uses gossip for reliably propagating task scheduling parameters and for discovering task execution nodes. Second, the algorithm guards against potential disruption of message propagation due to Byzantine attacks using a mechanism called LASIRC. By doing so, the algorithm provides assurances on task timeliness behaviors, despite system unreliability and untrustworthiness. Our performance evaluation shows LRTG's effectiveness.

Browse (HTML), Download (PDF)

Comments: To be supplied.

Han 07c
RTG-L: Dependably Scheduling Real-Time Distributable Threads in Large-Scale, Unreliable Networks

Kai Han, Binoy Ravindran, and E. Douglas Jensen

Proc. of the IEEE Pacific Rim International Symposium on Dependable Computing, December 2007

Abstract. We consider scheduling real-time distributable threads in the presence of node/link failures and message losses in large-scale network systems. We present a distributed scheduling algorithm called RTG-L. The algorithm uses gossip-based communication for dynamically and dependably discovering eligible nodes. Traditionally, gossip protocols incur high message overhead. We explain that this problem is not that serious. We present a gossip-based message propagation protocol with lower message overhead. In scheduling local thread sections, RTG-L exploits slacks to optimize gossip time utilization. Thereby, it satisfies end-to-end time constraints with probabilistic assurance. Our simulation studies verify our analytical results.

Browse (HTML), Download (PDF)

Comments: To be supplied.

Han 07b
Byzantine-Tolerant Point-To-Point Information Propagation in Untrustworthy and Unreliable Networks

Kai Han, Binoy Ravindran, and E. Douglas Jensen

Proc. of the International Conference on Network-Based Information Systems, 2007

Abstract. In a decentralized network system, an authenticated node is referred to as a Byzantine node, if it is fully controlled by a traitor or an adversary, and can perform destructive behavior to disrupt the system. Typically, Byzantine nodes together or individually attack point-to-point information propagation by denying or faking messages. In this paper, we assume that Byzantine nodes are of some intelligence — that is, they can protect themselves from being identified by authentication mechanisms, including encryption mechanisms. Therefore, a node cannot trust any other node in the system. We present an authentication-free, gossip-based application-level propagation mechanism called LASIRC, in which “healthy” nodes utilize Byzantine features to defend against Byzantine attacks. We show that LASIRC is robust against message-denying and message-faking attacks. Our experimental studies verify LASIRC’s effectiveness.

Browse (HTML), Download (PDF)

Comments: To be supplied.

Han 07a
Probabilistic, Real-Time Scheduling of Distributable Threads Under Dependencies in Ad Hoc Networks

Kai Han, Binoy Ravindran, and E. Douglas Jensen

Proc. of the IEEE Wireless Communications and Networking Conference , 2007

Abstract. We consider scheduling distributable real-time threads that are subject to dependencies (e.g., due to mutual exclusion constraints) in ad hoc networks, in the presence of node and link failures, message losses, and dynamic node joins and departures. We present a gossip-based dis- tributed scheduling algorithm, called RTG-D. We prove that thread blocking times under RTG-D are probabilistically bounded, thereby probabilistically bounding thread time constraint satisfactions'. Our simulation results validate RTG-D's e®ectiveness.

Browse (HTML), Download (PDF)

Comments: To be supplied.

Han 07
Exploiting Slack for Scheduling Dependent, Distributable Real-Time Threads in Mobile Ad Hoc Networks

Kai Han, Binoy Ravindran, and E. Douglas Jensen

Proc. of the International Conference on Real-Time and Network Systems, pages 225-234, March 2007

Abstract. In a decentralized network system, an authenticated node is referred to as a Byzantine node, if it is fully controlled by a traitor or an adversary, and can perform destructive behavior to disrupt the system. Typically, Byzantine nodes together or individually attack point-to-point information propagation by denying or faking messages. In this paper, we assume that Byzantine nodes are of some intelligence — that is, they can protect themselves from being identified by authentication mechanisms, including encryption mechanisms. Therefore, a node cannot trust any other node in the system. We present an authentication-free, gossip-based application-level propagation mechanism called LASIRC, in which “healthy” nodes utilize Byzantine features to defend against Byzantine attacks. We show that LASIRC is robust against message-denying and message-faking attacks. Our experimental studies verify LASIRC’s effectiveness.

Browse (HTML), Download (PDF)

Comments: To be supplied.

Huang 08a
RT-P2P: A Scalable Real-Time Peer-to-Peer System with Probabilistic Timing Assurances

Fei Huang, Binoy Ravindran, and E. Douglas Jensen

Proc. of the IEEE/IFIP International Conference on Embedded And Ubiquitous Computing (EUC), December 2008

Abstract. We present RT-P2P, a real-time peer-to-peer (P2P) system that allows application-level end-to-end timing requirements to be satisfied in P2P systems. P2P systems are fundamentally characterized by: a large number of geographically distributed nodes that require little infrastructural support from the underlying network; an unbounded number of nodes (a permanently evolving set of nodes); and consequently no process/node with global knowledge of the system structure. Interesting features of such networks include the fact that they allow a rich set of nodes to act as relay points for other nodes, and a rich set of overlay paths (selected by peers) to be constructed. These features have traditionally made overlay routing — where end hosts have the flexibility of routing traffic to their destinations through the desired choice of intermediate overlay nodes (unlike in IP routing) — a very attractive approach for end-to-end performance optimizations in P2P networks. Key aspects of our RT-P2P infrastructure include a real-time P2P protocol, real-time communication algorithm, and analytical performance models. We analytically establish the timing properties of RT-P2P. Our simulation studies validate our analytical results.

Browse (HTML), Download (PDF)

Comments: To be supplied.

Huang 08
Integrated Real-Time Scheduling and Communication with Probabilistic Timing Assurances in Unreliable Distributed Systems

Fei Huang, Kai Han, Binoy Ravindran, and E. Douglas Jensen

Proc. of the IEEE International Conference on Engineering of Complex Computer Systems, March/April 2008

Abstract. We consider distributed real-time systems that operate under run-time uncertainties including those on execution times and communication delays, and subject to arbitrary node failures and message losses. We present an integrated real-time scheduling and communication algorithm called Real-Time Scheduling with Reliable Data Delivery (RTSRD) that provides probabilistic end-to-end assurances on distributed task timeliness behaviors in such systems. RTSRD considers distributed tasks with end-to-end timing requirements that are expressed using time/utility functions and the optimality criterion of maximizing the total accrued utility. The algorithm decomposes end-to-end time constraints into local time constraints, and uses local slack time for node-local real-time scheduling and node-to-node real-time communication. We analytically establish RTSRD's properties including probabilistic satisfaction of task time constraints. We also compare RTSRD with a prior algorithm called RTG-L for the same problem. Our comparisons show that RTSRD outperforms RTG-L in terms of timeliness assurances (stronger) and algorithm overhead (lower).

Browse (HTML), Download (PDF)

Comments: To be supplied.

Jensen 04b
Application QoS Based Time-Critical Machine-to-Machine Resource Management in BM/C² Systems

E. Douglas Jensen

Proc. of the 2004 International Command and Control Research and Technology Symposium, September 14-17, 2004

Abstract. This paper summarizes a novel paradigm for expressing, enforcing, and formally reasoning about time-criticality of machine-to-machine resource management in battle management (BM) and C² systems. Such systems are largely dynamic and asynchronous, and have time frames of O(10^-1) seconds and higher. Thus they fall into a neglected gap between traditional static periodic “real-time” systems, and traditional “any time” scheduling/planning systems (e.g., for logistics). The paradigm uses application-level QoS metrics (such as track quality, circular error probable, etc.) to derive utility functions for completing tasks, and then uses those utility functions for resource management. This paradigm has been successfully employed in several experimental BM/C² demonstration systems, and is the topic of on-going research by industry and academia.

Browse (HTML), Download (PDF)

Comments: This paper exposes the Time/Utility Function/Utility Accrual resource management paradigm to the larger international MoD BM/C² community. Almost the same paper was accepted by the 2004 Command and Control Research and Technology Symposium for a primarily U.S. DoD audience.

Jensen 04a
Application QoS Based Time-Critical Machine-to-Machine Resource Management in BM/C² Systems

E. Douglas Jensen

Proc. of the 2004 Command and Control Research and Technology Symposium, May 12-14, 2004

Abstract. This paper summarizes a novel paradigm for expressing, enforcing, and formally reasoning about time-criticality of machine-to-machine resource management in battle management (BM) and C² systems. Such systems are largely dynamic and asynchronous, and have time frames of O(10^-1) seconds and higher. Thus they fall into a neglected gap between traditional static periodic “real-time” systems, and traditional “any time” scheduling/planning systems (e.g., for logistics). The paradigm uses application-level QoS metrics (such as track quality, circular error probable, etc.) to derive utility functions for completing tasks, and then uses those utility functions for resource management. This paradigm has been successfully employed in several experimental BM/C² demonstration systems, and is the topic of on-going research by industry and academia.

Browse (HTML), Download (PDF)

Comments: This paper exposes the Time/Utility Function/Utility Accrual resource management paradigm to the larger DoD BM/C² community. Almost the same paper was  accepted by the International Command and Control Research and Technology Symposium for an international MoD audience.

Jensen 04
Timeliness in Mesosynchronous Real-Time Distributed Systems

E. Douglas Jensen

Proc. of the 7th IEEE International Symposium on Object-Oriented Real-Time Computing, May 12-14, 2004

Abstract. Traditional real-time computing concepts and techniques are focused on static, synchronous, relatively small-scale, mostly centralized, device-level subsystems. Many real-time systems, particularly distributed ones, are relatively large-scale, above the device level, and at least partially dynamic and asynchronous. We call such systems “mesosynchronous.” For example, mesosynchronous systems often are found in military surveillance and force projection platforms, and in network-centric warfare (plus civilian domains). Hence the lives of both friends and foes depend on the timeliness properties of such systems being dependably acceptable according to application- and situation-specific criteria. The real-time research community has historically failed to perceive and appreciate this – admittedly difficult and domain-knowledge intensive – problem, especially for end-to-end timeliness in distributed mesosynchronous real-time systems.

Browse (HTML), Download (PDF)

Comments: This is my invited position paper for a panel session titled "Major push needed in real-time distributed computing research." It being a position paper enabled me to include some of my viewpoints that would otherwise not fit well into a conference proceedings paper.

Jensen 03c
Application QoS-Based Time-Critical Automated Resource Management in Battle Management Systems

E. Douglas Jensen

Proc. of the IEEE Workshop on Object-Oriented Real-Time Dependable Systems, October 1-3, 2003

Abstract. This paper summarizes some of our unclassified work on concepts and techniques for performing automated run-time time-critical resource management (especially scheduling) in large scale, dynamic, control systems such as for battle management. The approach described here is based on application-level quality of service metrics, such as track quality and weapon spherical error probable. These metrics are used to derive parameters for thread time constraints in the form of time/utility functions. Threads are scheduled according to application-specific optimality criteria that seek to maximize accrued utility to the system. Two worked examples illustrate the cost-effectiveness of this approach for this class of application.

Browse (HTML), Download (PDF)

Comments: This is an update of my paper in the Proceedings. The major revision is improvements in the worked examples sections.

Jensen 03b
The Evolution of Real-Time CORBA: The Good, the Bad, and the Ugly

E. Douglas Jensen

OMG Workshop on Distributed Object Computing for Real-time and Embedded Systems, July 15, 2003

Abstract. None -- see Comments below

Browse (HTML), Download (PDF)

Comments: This invited keynote presentation established a new precedent for an OMG technical meeting. Each OMG event has a sponsor, almost always a CORBA vendor. The sponsor is allowed to give a 60-minute keynote presentation. Traditionally, an employee of the sponsor gives somewhat of a marketing presentation for his company. The sponsors of this workshop were PrismTech and DARPA, so each was allowed a 30-minute presentation. PrismTech decided that instead of the traditional vendor marketing presentation, they would create a precedent and invite someone else - me - to give a non-marketing presentation. The topic they specified was "The Evolution of Real-Time CORBA;" I added "The Good, the Bad, and the Ugly." The rationale for the topic was that as real-time CORBA has gotten increasingly popular, and consequently as the participation in this annual workshop has grown and diversified, many if not most of the attendees are relative new-comers to real-time CORBA. Most of them didn't participate in the creation of the real-time CORBA 1.0 and 1.2 standards, much less from the beginning of the process; and thus they know little if anything about how it happened. I was a major contributor to the real-time CORBA 1.0 and 1.2 standards from the beginning, so I was PrismTech's choice to provide a historical overview. These slides without the narrative leave a lot of material out, so eventually I'll add some notes at least. (Doug Schmidt provided an overview of relevant DARPA programs.)

Jensen 03a
A Timeliness Paradigm for Mesosynchronous Real-Time Systems

E. Douglas Jensen

9th Embedded and Real-Time Applications and Systems Symposium, May 2003.

Abstract. None -- see Comments below

Browse (HTML), Download (PDF)

Comments: This was an invited plenary presentation that covers a little of the material on this web site. It includes the first use of the term mesosynchronous. By mesosynchronous real-time systems I mean those that are in the middle ground between

The real world has many real-time systems at various points in this mesosynchronous middle ground. The derivation of "mesosynchronous" from "mesodynamics" also reflects that synchronous real-time computing, like classical physics, is well understood, but asynchronous real-time computing, like quantum mechanics, requires a paradigm shift.

Jensen 03
Real-Time for the Real World

E. Douglas Jensen

NASA JPL Center for Space Mission Information and Software Systems, IT Seminar Series, January 22, 2003

Jensen et al. 02a
Guest Editors' Introduction to Special Section on Asynchronous Real-Time Distributed Systems

E. Douglas Jensen and Binoy Ravindran

IEEE Transactions on Computers, August 2002

Abstract. None -- see Comments below

Browse (HTML) -- requires IEEE Xplore or IEEE Computer Society Digital Library subscription

Download (PDF) -- requires IEEE Xplore or IEEE Computer Society Digital Library subscription

Comments: The August 2002 issue of IEEE Transactions on Computers (ToC) contains a special section on asynchronous distributed real-time computers, edited by myself and Binoy Ravindran. It also contains a paper on that topic (involving time/utility functions) by Hegazy and Ravindran that was omitted from the special section to avoid any potential for perceived conflict of interest. (There are also two unrelated Brief Contributions.) To my knowledge, this is the first compilation of papers on this topic. It is a short compilation: the ToC has a strict page limit; and suitable papers were not easy to find because there is not yet much research on this topic, and most of that is either more empirical than theoretical (and hence at least perceived by those researchers to be inappropriate for submission to ToC) or too much more related to the theory of distributed computing than to the theory of real-time computing. This set of papers clearly illuminated the interesting fact that there are two distinct schools of thought about asynchronous distributed real-time computer systems, each firmly held and avidly defended by its proponents; we discuss this in the Guest Editors' Introduction to the Special Section. We decided to do something unusual (perhaps unprecedented) in ToC: with the permission of the ToC Editor and the Special Section authors, we sent each author copies of the other papers and asked them to include some comparative material in their own papers. We believe that this provided for valuable insight about the topic of asynchronous distributed real-time computer systems to the readers of that ToC issue. The abstracts of the five papers (in the order in which they appear in the issue):

Jensen et al. 02
The Distributed Real-Time Specification for Java: A Status Report

E. Douglas Jensen, Andy Wellings, Ray Clark, and Doug Wells

Proc. Embedded Systems Conference/San Francisco, 2002

Abstract (slightly revised). This paper summarizes the status as of December 2001 of the Distributed Real-Time Specification for Java (DRTSJ), being developed by the JSR-50 Expert Group in Sun’s Java Community Process. The paper first defines what “real-time,” “distributed,” and “distributed real-time” mean in the context of the DRTSJ, since those terms are commonly used in widely different ways. The DRTSJ is focused on supporting predictability of end-to-end timeliness for sequentially trans-node behaviors (e.g., chains of invocations) in dynamic distributed object systems. The DRTSJ introduces the Distributed Real-Time Remote Method Invocation (RMI) model, based on the Alpha distributed real-time OS kernel’s distributed threads model. The OMG Real-Time CORBA/Dynamic Scheduling specification also employs a subset of the distributed threads model, so these two distributed real-time computing system programming model standards are relatively congruent. The DRTSJ consists of extensions to the Real-Time Specification for Java (RTSJ), Java’s RMI, and the RTSJ Java Virtual Machine.

Browse (HTML), Download (PDF)

Comments: This paper contains the material from [Wellings et al. 01] plus substantial motivational material about real-time, distributed systems, and distributed real-time. For additional detail about the DRTSJ status as of December 2001, see [Wellings et al. 02]; for additional detail about the DRTSJ status as of September 2002, see [Clark et al. 02]. The DRTSJ work, including the reference implementation, was in hibernation for 18 months due to MITRE staff over commitment, but resumed in Fall 2004 and is expected to be released in Spring 2005.

Jensen 01
The Distributed Real-Time Specification for Java – An Initial Proposal

E. Douglas Jensen

Journal of Computer Systems Science and Engineering, March 2001

Abstract (slightly revised). Work has begun on the Distributed Real-Time Specification for Java, as part of Sun’s Java Community Process. This paper summarizes some ideas about an initial approach to the specification. The approach is based on providing a natural and minimal mechanistic extension to Remote Method Invocation (RMI) to support the end-to-end timeliness (and other) properties of distributed – in the sense of trans-node – behaviors. These timeliness properties must be preserved for any distributed real-time computing system, regardless of its application programming model – whether RPC, mobile objects, or whatever. In particular, the proposed extension facilitates writing real-time distributed Java programs using a distributed threads programming abstraction [Jensen 00b] derived from the Alpha OS's distributed threads model [Clark et al. 93], and very similar to the distributable threads subset in the OMG specification for Real-Time CORBA 2/Dynamic Scheduling.

Browse (HTML), Download (PDF)

Comments: This paper describes the initial proposal submitted to Sun as Java Specification Request 50. For a status report as of December 2001, see [Jensen et al. 02] and for additional detail see [Wellings et al. 02]; for additional detail about the DRTSJ status as of September 2002, see [Clark et al. 02]. The DRTSJ work, including the reference implementation, was in hibernation for 18 months due to MITRE staff over commitment, but resumed in Fall 2004 and is expected to be released in Spring 2005.

Li et al. 06a
Utility Accrual Real-Time Resource Access Protocols with Assured Individual Activity Timeliness Behavior

Peng Li, Haisang Wu, Binoy Ravindran, and E. Douglas Jensen

International Conference on Real-Time and Network Systems, May 2006

Abstract. We present a class of utility accrual resource access protocols for real-time embedded systems. The protocols consider application activities that are subject to time/utility function time constraints, and mutual exclusion constraints for concurrently sharing non-CPU resources. We consider the timeliness optimality criteria of probabilistically satisfying individual activity utility lower bounds and maximizing total accrued utility. The protocols allocate CPU bandwidth to satisfy utility lower bounds; activity instances are scheduled to maximize total utility. We establish the conditions under which utility lower bounds are satisfied.

Browse (HTML), Download (PDF)

Comments. comment text.

Li et al. 06
A Utility Accrual Scheduling Algorithm for Real-Time Activities With Mutual Exclusion Resource Constraints

Peng Li, Haisang Wu, Binoy Ravindran, and E. Douglas Jensen

IEEE Transactions on Computers, 2006

Abstract. This paper presents a uni-processor real-time scheduling algorithm called the Generic Utility Scheduling algorithm (which we will refer to simply as GUS). GUS solves a previously open real-time scheduling problem - scheduling application activities that have time constraints specified using arbitrarily shaped time/utility functions, and have mutual exclusion resource constraints. A time/utility function is a time constraint specification that describes an activity's utility to the system as a function of that activity's completion time. Given such time and resource constraints, we consider the scheduling objective of maximizing the total utility that is accrued by the completion of all activities. Since this problem is NP-hard, GUS heuristically computes schedules with a polynomial-time cost of O(n3) at each scheduling event, where n is the number of activities in the ready queue. We evaluate the performance of GUS through simulation and by an actual implementation on a real-time POSIX operating system. Our simulation studies and implementation measurements reveal that GUS performs close to, if not better than, the existing algorithms for the cases that they apply. Furthermore, we analytically establish several properties of GUS.

Browse (HTML), Download (PDF)

Comments. comment text.

Li et al. 05a
Stochastic Utility Accrual Real-Time Scheduling with Task- Level and System-Level Timeliness Assurances

Peng Li, Hyeonjoong Cho, Binoy Ravindran, and E. Douglas Jensen

International Symposium on Object-oriented Real-time distributed Computing, May 2005

Abstract. Heuristic algorithms have enjoyed increasing interest and success in the context of Utility Accrual (UA) scheduling. However, few analytical results, such as bounds on task-level and system-level accrued utilities are known. In this paper, we propose the S-UA algorithm that can provide probabilistic bounds on task-level accrued utilities. Lower bound on system-level accrued utility ratio is also derived and maximized by S-UA.

Browse (HTML), Download (PDF)

Comments. comment text.

Li et al. 05
Utility Accrual Resource Access Protocols with Assured Timeliness Behavior for Real-Time Embedded Systems

Peng Li, Binoy Ravindran, and E. Douglas Jensen

ACM SIGPLAN/SIGBED 2005 Conference on Languages, Compilers, and Tools for Embedded Systems , June 2005

Abstract. We present a class of utility accrual resource access protocols for real-time embedded systems. The protocols consider real-time application activities that are subject to time/utility function time constraints, and mutual exclusion constraints for concurrently accessing shared, non-CPU resources. We consider the timeliness optimality criteria of probabilistically satisfying individual activity utility lower bounds and maximizing total accrued utility. The protocols use an approach, where CPU bandwidth is allocated to activities to satisfy utility lower bounds, and activity instances are scheduled to maximize total utility. We analytically establish upper bounds on resource access blocking times, and establish the conditions under which utility lower bounds are satisfied.

Browse (HTML), Download (PDF)

Comments. We have previously published UA scheduling algorithms that allow concurrent sharing of resources. However, these algorithms do not provide any timeliness assurances on individual activity behavior, only on collective behavior. On the other hand, we have previously published UA scheduling algorithms that provide timeliness assurances on individual activities that provide probabilistically assured satisfaction of lower bounds on individual activities' accrued utilities. However, these algorithms do not allow concurrent resource sharing. Thus, prior UA scheduling algorithms address two extremes: (1) those that allow concurrent resource sharing, but provide no timeliness assurances on individual activity behavior; and (2) those that provide timeliness assurances on individual activity behavior, but without allowing concurrent resource sharing. There have been no UA algorithms that bridge these extremes by providing individual activity timeliness assurances under concurrent resource sharing. We solve this exact problem in this paper.

Li et al. 04c
Utility Accrual Scheduling of Distributable Threads: The Tempus Approach

Peng Li, Binoy Ravindran, and E. Douglas Jensen

Eighth Annual Workshop on High Performance Embedded Computing, September 2004

Abstract. We have developed the Tempus middleware that supports Distributed Threads as a programming and scheduling abstraction for system-wide, end-to-end scheduling in real-time distributed systems. Distributed Threads in Tempus can be subject to time constraints including those specified using arbitrarily-shaped TUFs and timeliness optimality criteria including maximizing accrued utility.

Browse (HTML), Download (PDF)

Comments. This is a brief overview of the Tempus testbed at Virginia Tech. Tempus provides the Real-Time CORBA 1.2 distributable threads programming model, and the Real-Time CORBA 1.2 scheduling framework into which arbitrary scheduling disciplines can be plugged. Tempus allows experimentation with scheduling distributable threads -- especially using time/utility functions and utility accrual disciplines -- using the Real-Time CORBA 1.2 API's without requiring all the rest of Real-Time CORBA.

Li et al. 04b
Adaptive Time-Critical Resource Management Using Time/Utility Functions: Past, Present, and Future

Peng Li, Binoy Ravindran, and E. Douglas Jensen

28th International Computer Software and Applications Conference (COMPSAC), September 2004

Abstract. Time/utility function time constraints (or TUFs) and utility accrual (UA) scheduling optimality criteria, constitute, arguably, the most effective and broadest approach for adaptive, dynamic time-critical resource management. A TUF, which is a generalization of the classical deadline constraint, specifies the utility of completing an application activity as an application- or situation-specific function of that activity's completion time. With TUF time constraints, timeliness optimality criteria can be specified in terms of accrued (e.g., summed) activity utilities. This paper overviews past and recent advances on adaptive resource management for dynamic time-critical systems using UA algorithms. Emerging challenges and new research directions are also identified.

Browse (HTML), Download (PDF)

Comments: This extended abstract provides a brief overview of the history of time/utility functions and utility accrual scheduling disciplines from their invention by Jensen at Honeywell for radar scheduling, through their initial exposition by two of Jensen's Ph.D. students at CMU, to the present major advances by a collaboration between Virginia Institute of Technology and the MITRE Corporation, to a glimpse of some of the next steps.

Li et al. 04a
Utility Accrual Real-Time Scheduling with Probabilistically Assured Timeliness Performance

Peng Li, Binoy Ravindran, and E. Douglas Jensen

Proc. of the 2004 International Workshop on Probabilistic Analysis Techniques for Real-Time and Embedded Systems, in conjunction with the 4th International Conference on Embedded Software, September 2004

Abstract. We present time/utility function (TUF) algorithms that provide probabilistic assurance on timeliness behavior. A TUF, which is a generalization of the classical deadline constraint, specifies the utility of completing an application activity as a function of that activity’s completion time. The algorithms consider a stochastic model where activity execution times and arrivals are probabilistically described. Further, activity time constraints are specified using TUFs. We consider the dual optimization objective of probabilistically satisfying application specified lower bounds on individual activity utility, and maximizing system-wide total utilities. We present algorithms that achieve this dual objective.

Browse (HTML), Download (PDF)

Comments. This paper briefly summarizes the first steps toward a major generalization of the TUF/utility accrual scheduling paradigm. Until this work, all extant UA algorithms sought only maximal accrued utility. So, for example, two tasks T₁ and T₂ might be scheduled such that they contributed utilities U₁ and U₂ accruing (typically summing) to U₁₂. This schedule might result in task T₃ contributing utility U₃ < U₁₂ or even preclude task T₃ from being scheduled at all. Although this is to be expected, and indeed is the intent of the optimality criterion, it is not always what is desired. Suppose that the maximum possible utilities of T₁ and T₂ are less than that of T₃ -- say 4, 5, and 8, respectively. If the utility magnitudes were assigned to reflect the relative importance of the tasks, a more appropriate scheduling optimality criterion might take these maximum utilities into account -- e.g., with weighting. But there is a more expressive and powerful generalization of TUF/UA scheduling that encompasses not just this case but many others. The first generalization is a 2-criterion approach: allow lower bounds to be specified for each TUF's attained utility and for the accrued utility; the scheduling discipline must provide for the appropriate application-specific trade-off between these two criteria since in general they will not both be satisfied optimally. The second generalization is to make the first generalization stochastic: in addition to specifying the lower bounds on utilities, specify lower bounds for probabilities that the utility lower bounds will be satisfied. This paper addresses a subset of both these generalizations: for non-increasing TUF's, an algorithm has been devised which allows probabilistic satisfaction of task utility lower bounds, while also maximizing accrued utility. Theorems are proved about the timeliness properties of this algorithm. A next step toward these two generalizations -- accommodating probabilistic accrued utility -- plus additional TUF/UA scheduling advances, appears in Peng Li's Ph.D. thesis. Probabilistic lower bounds on individual and accrued utilities are also accommodated -- along with utility-based management of system energy -- by an algorithm described in two papers by Wu et al., Wu et al. 04b and Wu et al. 04c.

Na et al. 06
Garbage Collector Scheduling in Dynamic, Real-Time Multiprocessor Systems

C. Na, H. Cho, B. Ravindran, and E. D. Jensen

Proc. IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, August 2006

Abstract. We consider garbage collection in dynamic, multiprocessor real-time systems, and present a scheduling algorithm called GCMUA. The algorithm considers mutator activities that are subject to time/utility function time constraints, stochastic execution-time and memory demands, and overloads. We establish that GCMUA probabilistically lower bounds each mutator activity’s accrued utility, lower bounds the system-wide total accrued utility, and upper bounds the timing assurances’ sensitivity to variations in mutator execution-time and memory demand estimates. Our simulation experiments validate our analytical results and confirm GCMUA’s effectiveness and superiority.

Comments:TBD

Northcutt 87
Mechanisms for Reliable Distributed Real-Time Operating Systems — The Alpha Kernel

J. Duane Northcutt

Academic Press, 1987. Out of print, available used.

Abstract. To be supplied

Browse (HTML), Download (PDF)

Comments: This book is essentially the thesis by one of my Ph.D. students. To be continued...

Pei et al. 08a
Self-organizing and Self-reconfigurable Event Routing in Ad Hoc Networks with Causal Dependency Awareness

Guanhong Pei, Binoy Ravindran, and E. Douglas Jensen

ACM Transactions on Autonomous and Adaptive Systems, December 2008

Abstract. Publish/subscribe (P/S) is a communication paradigm of growing popularity for information dissemination in large-scale distributed systems. The weak coupling between information producers and consumers in P/S systems is attractive for loosely coupled and dynamic network infrastructures such as ad hoc networks. However, achieving end-to-end timeliness and reliability properties when P/S events are causally dependent is an open problem in ad hoc networks. In this paper, we present, evaluate bene¯ts of, and compare with past work, an architecture design that can effectively support timely and reliable delivery of events and causally related events in ad hoc environments, and especially in mobile ad hoc networks (MANETs). With observations from both realistic application model and simulation experiments, we reveal causal dependencies among events and their significance in a typical use notional system. We also examine and propose engineering methodologies to further tailor an event-based system to facilitate its self-reorganizing capability and self-reconfiguration. Our design features a two-layer structure, including novel distributed algorithms and mechanisms for P/S tree construction and maintenance. The trace-based experimental simulation studies illustrate our design's effectiveness in both cases with and without causal dependencies.

Pei et al. 08
On A Self-organizing MANET Event Routing Architecture with Causal Dependency Awareness

Guanhong Pei, Binoy Ravindran, and E. Douglas Jensen

IEEE International Conference on Self-Adaptive and Self-Organizing Systems (SASO), October 2008. (Full version of the paper is available as a Technical Report.)

Abstract. Publish/subscribe (P/S) is a communication paradigm of growing popularity for information dissemination in largescale distributed systems. The strong decoupling between information producers and consumers in P/S systems is attractive for loosely coupled and dynamic network infrastructures such as mobile ad hoc networks (MANETs). However, achieving end-to-end timeliness and reliability properties when P/S events are causally dependent is an open problem in MANETs. In this paper, we propose an architecture design for event routing in MANET that can effectively support timely and reliable event delivery with awareness of event causal dependencies. Our design features a two layer structure, including novel distributed algorithms and mechanisms for P/S tree construction and maintenance with self-organization capabilities. Our simulation-based experimental studies illustrate the architecture’s effectiveness.

Browse (HTML), Download (PDF)

Comments: To be supplied.

Ravindran et al. 07b
Assured-Timeliness Integrity Protocols for Distributable Real-Time Threads with in Dynamic Distributed Systems

Binoy Ravindran, Edward Curley, Jonathan Anderson, and E. Douglas Jensen

International Workshop on Embedded Software Optimization (ESO), IFIP International Conference on Embedded and Ubiquitous Computing (EUC), December 2007

Abstract. Networked embedded systems present unique challenges for system designers composing distributed applications with dyanmic, real-time, and resilience requirements. We consider the problem of recovering from failures of distributable threads with assured timeliness in dynamic systems with overloads, and node and (permanent/transient) network failures. When a distributable thread encounters a failure that prevents its timely execution, the thread must be terminated. Thread termination involves detecting and aborting thread orphans, and delivering exceptions to the farthest, contiguous surviving thread segment for possible execution resumption. Thread termination operations must optimize system-wide timeliness. We present a scheduling algorithm called HUA and two thread integrity protocols called D-TPR and W-TPR. We show that they bound the orphan cleanup and recovery time with bounded loss of the best-effort property—i.e., high importance threads are always favored over low importance ones (for feasible completion), irrespective of thread urgency. Our implementation experience using the emerging Reference Implementation of Sun’s Distributed Real-Time Specification for Java (DRTSJ) demonstrates the algorithm/protocols’ effectiveness.

Browse (HTML), Download (PDF)

Comments: To be supplied.

Ravindran et al. 07a
On Distributed Real-Time Scheduling in Networked Embedded Systems in the Presence of Crash Failures

Binoy Ravindran and E. Douglas Jensen

IFIFP Workshop on Software Technologies for Future Embedded and Ubiquitous Systems (SEUS), IEEE International Symposium on Object-oriented Real-time distributed Computing, May 2007

Abstract. We consider the problem of scheduling distributable real-time threads in networked embedded systems that operate under run-time uncertainties including those on thread execution times, thread arrivals, and node failure occurrences. We present a distributed scheduling algorithm called CUA. We show that CUA satisfies thread time constraints in the presence of crash failures, is early-deciding, has an efficient message complexity of O(fn) (where f is the number of crashes that actually occur and n is the number of nodes), and is time-optimal with a time lower bound of O(D+fd+nk) (where D is the message delay upper bound, d is the failure detection bound, and k is the maximum number of threads). In crash-free runs, the algorithm constructs schedules within O(D + nk), and yields optimal total utility if nodes are also not overloaded. The algorithm is also “best-effort” in that a high importance thread that may arrive at any time has a very high likelihood for feasible completion (in contrast to classical admission control algorithms which favor feasible completion of admitted threads over admitting new ones, irrespective of thread importance).

Browse (HTML), Download (PDF)

Comments: To be supplied.

Ravindran et al. 07
On Scheduling Exception Handlers in Dynamic Real-Time Systems

Binoy Ravindran, Ed Curley, and E. Douglas Jensen

International Conference on Embedded Software and Systems, Springer LNCS 4523, pages 510-529, May 2007

Abstract. We consider the problem of scheduling exception handlers in real-time systems that operate under runtime
uncertainties including those on execution times, activity arrivals, and failure occurrences. The application/
scheduling model includes activities and their exception handlers that are subject to time/utility function
(TUF) time constraints and an utility accrual (UA) optimality criterion. A key underpinning of the TUF/UA
scheduling paradigm is the notion of “best-effort” where high importance activities are always favored over
low importance ones, irrespective of activity urgency. (This is in contrast to classical admission control
models which favor feasible completion of admitted activities over admitting new ones, irrespective of activity
importance.) We consider a transactional style activity execution paradigm, where handlers that are released
when their activities fail (e.g., due to time constraint violations) abort the failed activities after performing
recovery actions. We present a scheduling algorithm called Handler-assured Utility accrual Algorithm (or
HUA) for scheduling activities and their handlers. We show that HUA’s properties include bounded-time
completion for handlers and bounded loss of the best-effort property. Our implementation experience on a
RTSJ (Real-Time Specification for Java) Virtual Machine demonstrates the algorithm’s effectiveness.

Browse (HTML), Download (PDF)

Comments: To be supplied.

Ravindran et al. 05
On Recent Advances in Time/Utility Function Scheduling and Resource Management

Binoy Ravindran, E. Douglas Jensen, and Peng Li

International Symposium on Object-oriented Real-time distributed Computing, May 2005

Abstract. We argue that the key underpinning of the current state-of-the real-time practice — the priority artifact — and that of the current state-of-the real-time art — deadline-based timeliness optimality — are entirely inadequate for specifying timeliness objectives, for reasoning about timeliness behavior, and for performing resource management that can dependably satisfy timeliness objectives in many dynamic real-time systems. We argue that time/utility functions and the utility accrual scheduling paradigm provide a more generalized, adaptive, and flexible approach. Recent research in the utility accrual paradigm have significantly advanced the state-of-the-art of that paradigm. We survey these advances.

Browse (HTML), Download (PDF)

Comments: During the years of 2003 and 2004, the MITRE/Virginia Tech team performing collaborative research on time/utility functions and utility accrual based scheduling made major advances in the state of the art as documented in eighteen published papers. This paper summarizes those advances into a single reference. The team has many additional papers still in the reviewing process, but has not included information about them in this paper.

Ravindran et al. 04
The Case for TUFs and UA Scheduling in RT UML Profile: A Real-Time Scheduling/Operating System Perspective

Binoy Ravindran, Peng Li, Haisang Wu, E. Douglas Jensen, and Shahrooz Feizabadi

Workshop on the Usage of the UML Profile for Scheduling, Performance and Time, IEEE Real-Time and Embedded Technology and Applications Symposium, May 2004

Abstract. This position paper makes the case for incorporating time/utility functions (TUFs) and the paradigm of utility accrual real-time scheduling in the planned, updated version of the UML Profile for Schedulability, Performance, and Time. The case is made by arguing that the key underpinning of the current state-of-the real-time practice -- the priority artifact -- and that of the current state-of-the real-time art -- deadline-based timeliness optimality -- are grossly inadequate for specifying application timeliness objectives, for reasoning about timeliness behavior, and for performing resource management that can dependably satisfy timeliness objectives in many large-scale, dynamic real-time systems. We argue that TUFs and utility accrual scheduling provide a more generalized, adaptive, and exible approach. Further, new research on utility accrual scheduling have significantly advanced the state-of-the-art of that paradigm. We survey these recent advances to provide the rationale for our case.

Browse (HTML), Download (PDF)

Comments: TUF/UA scheduling is now included as an issue in the Finalization Task Force for OMG's UML Profile for Modeling Quality of Service and Fault Tolerance Characteristics and Mechanisms. The OMG process states that "A Finalization Task Force is responsible for drafting the changes that turn an Adopted Specification into an Available Specification. An Issue is recorded against an adopted specification when someone in industry wishes to bring before the FTF one of the following: a recommended technical change (e.g., resolving technical error or omission or introducing enhancement); an editorial change."

Wellings et al. 02
A Framework for Integrating the Real-Time Specification for Java and Java's Remote Method Invocation

Andy Wellings, Raymond Clark, E. Douglas Jensen, and Doug Wells

Proc. of the 5th IEEE International Symposium on Object Oriented Real-Time Distributed Computing, April 2002

Abstract. The Distributed Real-Time Specification for Java (DRTSJ) is being developed under Sun’s Java Community Process. It is focused on supporting predictable, end-to-end timeliness for sequentially distributed computations (e.g., chains of invocations) in dynamic distributed object systems. This paper reports on an investigation to integrate and extend the existing Real-Time Specification for Java and Java’s Remote Method Invocation facility to provide the basis for the DRTSJ.

Browse (HTML), Download (PDF)

Comments: This paper is a summary of one of the work products produced by the authors of the DRTSJ. From experience we've discovered that it requires the readers to have a fairly good understanding of the RTSJ, Java, RMI, and real-time distributed computing -- especially of the Distributed Thread model from the Alpha distributed real-time OS kernel, and of the issues that programming model addresses [Clark 93][Jensen 00b]. This ISORC paper was preceded by a very short identically named paper at the Work in Progress session of the Real-Time Systems Symposium (RTSS), 2001 [Wellings et al. 01]. Concurrently with this ISORC paper was a paper at the Embedded Systems Conference/San Francisco 2002 [Jensen 02] which included the material from the RTSS paper plus substantial motivational material about real-time and distributed systems and real-time distributed systems.

Wu et al. 07a
Utility Accrual, Real-Time Scheduling Under the Unimodal Arbitrary Arrival Model with Energy Bounds

Haisang Wu, Binoy Ravindran, and E. Douglas Jensen

IEEE Transactions on Computers, October 2007

Abstract. In this paper, we consider timeliness and energy optimization in battery-powered, dynamic, embedded real-time systems, which must remain functional during an operation/mission with a bounded energy budget. We consider application activities that are subject to time/utility function time constraints, statistical assurance requirements on timeliness behavior, and an energy budget, which cannot be exceeded at run-time. To account for the inevitable variability in activity arrivals in dynamic systems, we describe arrival behaviors using the unimodal arbitrary arrival model (or UAM). For such a model, we present a DVS (dynamic voltage scaling)-based, CPU scheduling algorithm called Energy-Bounded Utility Accrual Algorithm (or EBUA). Since the scheduling problem is intractable, EBUA allocates CPU cycles, scales clock frequency, and heuristically computes schedules using statistical estimates of cycle demands, in polynomial-time. We analytically establish EBUA's properties including satisfaction of energy bounds, statistical assurances on individual activity timeliness behavior, optimal timeliness during under-loads, and bounded time for mutually exclusively accessing shared non-CPU resources. Our simulation experiments validate our analytical results and illustrate the algorithm's effectiveness and superiority over past algorithms.

Wu et al. 07
Utility Accrual Real-Time Scheduling Under Variable Cost Functions

Haisang Wu, Umut Balli, Binoy Ravindran, and E. Douglas Jensen

IEEE Transactions on Computers, March 2007

Abstract. We present a utility accrual real-time scheduling algorithm called CIC-VCUA, for tasks whose execution times are functions of their starting times (and potentially other factors). We model such variable execution times using variable cost functions (VCFs). The algorithm considers application activities that are subject to time/utility function time constraints, execution times described using VCFs, and mutual exclusion constraints on concurrent sharing of non-CPU resources. We consider the two-fold scheduling objective of (1) assure that the maximum interval between any two consecutive, successful completions of job instances in an activity must not exceed the activity period (an application-specific objective), and (2) maximizing the system's total accrued utility, while satisfying mutual exclusion resource constraints. Since the scheduling problem is intractable, CIC-VCUA is a polynomial-time heuristic algorithm. The algorithm statically computes worst-case task sojourn times, dynamically selects tasks for execution based on their potential utility density, and completes tasks at specific times. We establish that CIC-VCUA achieves optimal timeliness during under-loads, and tightly upper bounds inter- and intra-task completion times. Our simulation experiments confirm the algorithm's effectiveness and superiority.

Wu et al. 06a
Utility Accrual, Real-Time Scheduling with Energy Bounds

Haisang Wu, Binoy Ravindran, and E. Douglas Jensen

Proc. ACM Symposium On Applied Computing, 2006

Abstract. In this paper, we consider timeliness and energy optimization in battery-powered, dynamic embedded real-time systems, which must remain functional during an operation/mission with a bounded energy budget. We consider application activities that are subject to time/utility function time constraints, statistical assurance requirements on timeliness behavior, and an energy budget, which cannot be exceeded at run-time. To account for the inevitable variability in activity arrivals in dynamic systems, we describe arrival behaviors using the unimodal arbitrary arrival model. For such a model, we present a CPU scheduling algorithm, called the Energy-Bounded Utility Accrual Algorithm (or EBUA). EBUA is a polynomial-time algorithm that satisfies energy bounds, and provides statistical assurances on individual activity timeliness behavior. We analytically establish several timeliness properties of EBUA. Further, our simulation experiments confirm the algorithm's effectiveness and superiority.

Wu et al. 06
Energy-Efficient, Utility Accrual Scheduling under Resource Constraints for Mobile Embedded Systems

Haisang Wu, Binoy Ravindran, E. Douglas Jensen, and Peng Li

ACM Transactions on Embedded Computing Systems, V5N3, August 2006

Abstract. We present an energy-e±cient, utility accrual, real-time scheduling algorithm called ReUA. ReUA considers an application model where activities are subject to time/utility function time constraints, mutual exclusion constraints on shared non-CPU resources, and statistical performance requirements on individual activity timeliness behavior. The algorithm targets mobile embedded systems where system-level energy consumption is also a major concern. For such a model, we consider the scheduling objectives of (1) satisfying the statistical performance requirements and (2) maximizing the system-level energy efficiency, while respecting resource constraints. Since the problem is NP-hard, ReUA allocates CPU cycles using statistical properties of application cycle demands, and heuristically computes schedules with a polynomial-time cost. We analytically establish several timeliness and non-timeliness properties of the algorithm. Further, our simulation experiments illustrate ReUA's effectiveness and superiority.

Wu et al. 05b
Utility Accrual Real-Time Scheduling Under Variable Cost Functions

Haisang Wu, Umut Balli, Binoy Ravindran, and E. Douglas Jensen

Proc. IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, August 2005

Abstract. We present an utility accrual real-time scheduling algorithm called VCUA, for tasks whose execution times are functions of their starting times. We model such variable execution times with variable cost functions (or VCF). The algorithm considers application activities that are subject to time/utility function time constraints, VCFs, and the multi-criteria scheduling objective of assuring that the maximum interval between any two consecutive, successful completion of jobs of a task must not exceed a specified bound, and maximizing the system's total utility. Since the scheduling problem is intractable, VCUA off-line selects tasks based on their potential utility density, and dynamically promotes jobs to accrue more utility, in polynomial-time. We establish that VCUA achieves optimal timeliness during under-loads, and identify the conditions under which timeliness assurances hold. Our simulation experiments illustrate VCUA's superiority.

Wu et al. 05a
Time/Utility Function Decomposition Techniques for Utility Accrual Scheduling Algorithms in Real-Time Distributed Systems

Haisang Wu, Binoy Ravindran, and E. Douglas Jensen

IEEE Transactions on Computers, Volume 54, Number 9, pages 1138 - 1153, September 2005

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 decomposition techniques called UT, SCEQF, SCALL, OPTCON, and TUFS, which are specific to different classes of UA algorithms, such as those that use utility density, and those that use deadline as their key decision metric. Our experimental studies show that OPTCON and TUFS perform best for utility density-based UA algorithms, and SCEQF and SCALL perform best for deadline-based UA algorithms.

Browse (HTML), Download (PDF)

Comments: TBD.

Wu et al. 05
Energy-Efficient Scheduling with Statistically-Assured Performance for Dynamic Real-Time Systems

Haisang Wu, Binoy Ravindran, and E. Douglas Jensen

Proc. Design, Automation, and Test in Europe, March 2005

Abstract. In the context of battery-powered dynamic embedded real-time systems, the constraints of energy and timeliness should be addressed. In this paper, we consider repeatedly occurring application activities with the unimodal arbitrary arrival model (UAM) to describe the inevitable variability of activity (e.g., task) arrivals in such systems. The activities are subject to time/utility function time constraints and statistical performance requirements. For battery powered embedded systems, system-level energy consumption is also a primary concern. We present a scheduling algorithm, called Energy-efficient Utility Accrual Algorithm* (or EUA*). EUA* considers utility maximization under energy constraints during system overloads, and considers the dual criterion problem, minimizing energy while achieving the given utility within the given time constraint, during under-loads. We analytically establish several timeliness properties of the algorithm. Further, our simulation experiments illustrate EUA*’s effectiveness.

Browse (HTML), Download (PDF)

Comments: See the Comments for the first [Wu et al. 04c] and second [Wu et al. 04d] papers in this series. Deterministically recurring task models, such as the periodic task model, are not appropriate for describing the inevitable variability of activity arrivals in dynamic real-time applications. Thus, in this paper, we extend the task arrival model from a  periodic model to a unimodal arrival model (UAM), which describes the maximal number of a task’s instance arrivals during any sliding time window. We consider independent tasks with non-increasing TUFs. The algorithm here is EUA*, and it considers utility maximization under energy constraints during system overloads, and addresses the dual optimality criterion problem of minimizing energy while achieving the given utility within the given time constraint, during under-loads.

Wu et al. 04d
Energy Efficient, Utility Accrual Scheduling under Resource Constraints for Mobile Embedded Systems

Haisang Wu, Binoy Ravindran, E. Douglas Jensen, and Peng Li

Proc. Fourth ACM International Conference on Embedded Software, September 2004

Abstract. We present an energy-efficient, utility accrual, real-time scheduling algorithm called the Resource-constrained Energy-Efficient Utility Accrual Algorithm (or ReUA). ReUA considers an application model where activities are subject to time/utility function (TUF) time constraints, resource dependencies including mutual exclusion constraints, and statistical performance requirements including activity (timeliness) utility bounds that are probabilistically satisfied. Further, ReUA targets mobile embedded systems where system-level energy consumption is also a major concern. For such a model, we consider the scheduling objectives of (1) satisfying the statistical performance requirements; and (2) maximizing the system-level energy efficiency. At the same time, resource dependencies must be respected. Since the problem is NP-hard, ReUA makes resource allocations using statistical properties of application cycle demands and heuristically computes schedules with a polynomial-time cost. We analytically establish several timeliness and non-timeliness properties of the algorithm. Further, our simulation experiments illustrate the algorithm's effectiveness.

Browse (HTML), Download (PDF)

Comments:

See the Comments for the first paper in this series [Wu et al. 04c]. In this paper, we extend the work of Wu et al. 04c to non-increasing TUFs, and consider tasks with resource dependencies. We describe our Resource-constrained, Energy-efficient Utility Accrual algorithm (ReUA) in this paper. ReUA has the same timeliness properties as the  EUA algorithm in Wu et al. 04c. In this paper, we additionally establish its non-timeliness properties, such as deadlock-freedom and correctness.

An extended journal version of Wu et al 04c and Wu et al 04d has been submitted for publication. In that, we provide more complete experimental results, and analytically establish more timeliness and non-timeliness properties, such as sufficiency on probabilistic satisfaction of timeliness utility lower bounds, lower-bounded system-wide utility, bounded blocking time for resource access, deadlock-freedom, and correctness.

Wu et al. 04c
CPU Scheduling for Statistically-Assured Real-Time Performance and Improved Energy-Efficiency

Haisang Wu, Binoy Ravindran, and E. Douglas Jensen

Proc. IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis, September 2004

Abstract. We present an energy-efficient, utility accrual, real-time scheduling algorithm called the Resource-constrained Energy-Efficient Utility Accrual Algorithm (or ReUA). ReUA considers an application model where activities are subject to time/utility function (TUF) time constraints, resource dependencies including mutual exclusion constraints, and statistical performance requirements including activity (timeliness) utility bounds that are probabilistically satisfied. Further, ReUA targets mobile embedded systems where system-level energy consumption is also a major concern. For such a model, we consider the scheduling objectives of (1) satisfying the statistical performance requirements; and (2) maximizing the system-level energy efficiency. At the same time, resource dependencies must be respected. Since the problem is NP-hard, ReUA makes resource allocations using statistical properties of application cycle demands and heuristically computes schedules with a polynomial-time cost. We analytically establish several timeliness and non-timeliness properties of the algorithm. Further, our simulation experiments illustrate the algorithm's effectiveness.

Browse (HTML), Download (PDF)

Comments: The two major contributions of this paper are: generalization of the conventional utility accrual optimality criterion to include probabilistic lower bounds on individual and accrued utilities (see the Comment for Li et al. 04a); and the addition of a second utility-based optimality criterion, maximizing the system-level energy efficiency.

Thus far we have published three papers on energy-efficient utility accrual scheduling for embedded real-time systems [Wu et al. 04c][Wu et al 04d][Wu et al. 05]; an extended version of the first two of these papers has been submitted for publication, and currently a fifth paper is in preparation for a conference. These papers reflect our sequence of advances in utility accrual/energy-efficiency scheduling: from downward step TUFs to non-increasing TUFs; from periodic tasks to tasks with the unimodal arrival model; from independent tasks to tasks with resource dependencies; from unlimited energy budget to energy-bounded systems. Usually the latter papers are extending the earlier ones in some aspects of embedded real-time systems.
 
In all the papers, we consider system-level energy consumption instead of only the CPU’s energy consumption. We adopt Martin’s energy consumption model, where each system component’s energy consumption is individually modeled and aggregated to obtain system-level energy consumption. To better account for uncertainties in activity behaviors, we consider a stochastic model, where activity execution demand is stochastically expressed using mean and variance. Our scheduling objectives are (1) provide statistical assurances on individual activity timeliness behavior, including application-defined, probabilistic, lower bounds on individual activity utility; and (2) maximize system-level energy efficiency.
 
This is our first paper published on this topic. We describe our Energy-efficient Utility Accrual algorithm (EUA) in this paper, to deal with independent periodic tasks whose time constraints are specified using binary-valued, downward step TUFs. We analytically establish several timeliness properties of EUA in this paper. These include timeliness optimality during under-loads, and assurances on timeliness behavior including lower bounds on individual activity utility and system-wide collective utility.

Wu et al. 04b
Utility Accrual Scheduling under Arbitrary Time/Utility Functions and Multiunit Resource Constraints

Haisang Wu, Binoy Ravindran, E. Douglas Jensen, and Umut Balli

Proc. of the 10th Real-Time and Embedded Computing Systems and Applications, August 2004

Abstract. We present a uni-processor real-time scheduling algorithm called Resource-contrainted Utility Accrual algorithm (or RUA). RUA considers an application model, where activities can be subject to arbitrarily-shaped time/utility function (TUF) time constraints and resource constraints including mutual exclusion under a multi-unit resource request model. For such a model, we consider the scheduling objective of maximizing the total utility accrued by all activities. This problem was previously open. Since the problem is NP-hard, RUA heuristically computes schedules with a polynomial-time cost. We analytically establish several timeliness and non-timeliness properties of the algorithm, including upper bound on blocking time (under multi-unit request model) and deadlock-freedom. We also implement RUA on a POSIX RTOS and conduct experimental comparisons with other TUF scheduling algorithms that address a subset of RUA's model. Our implementation measurements show that RUA performs generally better than, or as good as, other TUF algorithms for the applicable cases.

Browse (HTML), Download (PDF)

Comments: This paper extends the authors' previous work to include multi-unit resources.

Wu et al. 04a
Utility Accrual Scheduling Under Joint Utility and Resource Constraints

Haisang Wu, Binoy Ravindran, and E. Douglas Jensen

Proc. of the 7th IEEE International Symposium on Object-Oriented Real-Time Distributed Computing, May 2004

Abstract. We extend time/utility functions and utility accrual model with the concept of joint utility functions (or JUFs) that allow an activity’s utility to be described as a function of the completion times of other activities and their progress. We also specify the concept of progressive utility that generalizes the previously studied imprecise computational model, by describing an activity’s utility as a function of its progress. Given such an extended utility accrual model, we consider the scheduling criterion of maximizing the weighted sum of completion time, progressive, and joint utilities. We present an algorithm called the Combined Utility Accrual algorithm (or CUA) for this criterion. Experimental measurements with an implementation of CUA on a POSIX RTOS illustrate the effectiveness of JUFs in a class of applications of interest to us.

Browse (HTML), Download (PDF)

Comments: TBD.

Wu et al. 04
On the Joint Utility Accrual Model

Haisang Wu, Binoy Ravindran, and E. Douglas Jensen

Proc. of the 12th International Workshop on Parallel and Distributed Real-Time Systems, April 2004

Abstract. We extend Jensen’s time/utility functions and utility accrual model with the concept of joint utility functions (or JUFs) that allow an activity’s utility to be described as a function of the completion times of other activities and their progress. We also specify the concept of progressive utility that generalizes the previously studied imprecise computational model, by describing an activity’s utility as a function of its progress. Given such an extended utility accrual model, we consider the scheduling criterion of maximizing the weighted sum of completion time, progressive, and joint utilities. We present an algorithm called the Combined Utility Accrual algorithm (or CUA) for this criterion. Experimental measurements with an implementation of CUA on a POSIX RTOS illustrate the effectiveness of JUFs in a class of applications of interest to us.

Browse (HTML), Download (PDF)

Comments: This paper is part of the workshop's special session on TUF/UA scheduling. Although its main contribution is to introduce the concept of joint utility functions, it also shows that Liu's "imprecise computation" model is a special case of our progressive utility model.

Zhang et al. 08
RTQG: Real-Time Quorum-based Gossip Protocol for Unreliable Networks

Bo Zhang, Kai Han, Binoy Ravindran, and E. Douglas Jensen

Proc. of the 12th IEEE International Conference on Availability, Reliability and Security, March 2008

Abstract. We consider scheduling real-time tasks in the presence of message loss and Byzantine node failures in unreliable networks. We present scheduling algorithms called RTQG and RTQG-B. The algorithms use quorum-based gossip communication strategies for dynamically and dependably discovering eligible nodes. Compared with its predecessors, our protocol exhibits better performance. RTQG utilizes quorum systems to limit the range of each gossip round. Using the intersection property of quorum systems, RTQG has advantages in message propagation and robustness to Byzantine node failures. Our simulation studies verify our analytical results.

Browse (HTML), Download (PDF)

Comments: TBD.

Add to Favorites

Print Page