In Distributed Real-Time Systems (DRTSs), computation and communication are the main operations contained in activities. The timeliness of activities depends on that of computations and communications. Furthermore, the timeliness of computations relies on that of communications, and vice versa. Hence, the interplay between computation and communication is inherently a key factor in determining the timeliness of activities. This paper proposes a class of general utility functions under the utility accrual model UAM+to capture and characterize this interplay. Accordingly, a technique called Dynamic Deadline Adjustment (DDA) is proposed to fully explore such interplay and help resource managers proceed toward utility accrual. An online algorithm called IDRSA, which integrates the DDA technique, is developed to perform resource scheduling for DRTSs. IDRSA adopts a two-level scheduling framework to decompose resource scheduling into subprocesses and distribute them to processing nodes so as to reduce the cost of resource scheduling through parallel processing. In addition, IDRSA incorporates a new data structure called testing interval tree to effectively reduce the costs of schedulability tests for tasks and messages. Simulation results reveal the effectiveness of IDRSA, especially when the load of computation is heavy and/or the interplay between computation and communication is tight.

In distributed real-time systems, both computation and communication are critical factors. The timeliness of activities relies on both the computation and the communication involved in them. Moreover, the timeliness of computation relies on that of communication, and vice versa. This property requires that both computation and communication be integrated into the resource allocation model and that the model be able to capture the interplay between them. Unfortunately, the utility/benefit/value accrual models employed in current distributed real-time systems are constructed solely on computation. They are inadequate for capturing the interplay between computation and communication. This paper extends previous research on utility-based model by proposing a new utility accrual model, which integrates both computation and communication. Most importantly, the interplay between computation and communication is fully characterized in the model. Under the new model, resource managers are guided towards maximizing system-wide utility by exploring the interplay between computation and communication instead of traditional meeting the timing constraint on computation and the deadline of communication separately. To validate the effectiveness of this model, a resource allocation algorithm called CAUASA is developed under it. The performance of CAUASA is compared to that of another resource allocation algorithm that is developed according to existing utility accrual models. Simulation results reveal that CAUASA is far superior to its counterpart. Therefore, the new utility accrual model provides a more effective framework for the resource allocation in distributed real-time systems.

In real-time systems, the efficiency of scheduling modules (SM) is of critical importance. While efficient algorithms result in efficient SMs, this will not occur without appropriate implementations of the algorithms. Moreover, an algorithm with good implementation could further improve the efficiency of the SM. Therefore, creative implementations of algorithms are well worthy of exploring. In this paper, we propose novel data structures (i.e., testing interval trees (TIT)) to help build efficient algorithms for schedulability test and admission control in some real-time SMs. With the testing interval tree for vacancy analysis (TIT-V), the complexities of the schedulability tests in a class of parallel/distributed real-time systems can be effectively reduced from O(m2nlogn) to O(mlogn+mlogm) (where m is the number of processors, and n is the number of tasks). Similarly, with the testing interval tree for release time and laxity analysis (TIT-RL), the complexity of the online admission control in a uni-processor based real-time system can be reduced from O(n2) to O(nlogn) (where n is the number of tasks). Furthermore, the TIT-RL tree can also be applied to a class of parallel/distributed real-time systems. Therefore, the TIT trees are effective approaches to building efficient real-time SMs.