Exploring the Interplay between Computation and Communication in Distributed Real-Time Scheduling

摘要

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 {rm UAM}^{rm + } 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.