Robust Adaptive Metrics for Deadline Assignment in Distributed Hard Real-Time Systems

Abstract

Distributed real-time applications usually consist of several component tasks and must be completed by its end-to-end (E-T-E) deadline. As long as the E-T-E deadline of an application is met, the strategy used for dividing it up for component tasks does not affect the application itself. One would therefore like to “slice” each application E-T-E deadline and assign the slices to component tasks so as to maximize the schedulability of the component tasks, and hence the application. Distribution of the E-T-E deadline over component tasks is a difficult and important problem since there exists a circular dependency between deadline distribution and task assignment. We propose a new deadline-distribution scheme which has two major improvements over the best scheme known to date. It can distribute task deadlines prior to task assignment and relies on new adaptive metrics that yield significantly better performance in the presence of high resource contention. The deadline-distribution problem is formulated for distributed hard real-time systems with relaxed locality constraints, where schedulability analysis must be performed at pre-run-time, and only a subset of the tasks are constrained by pre-assignment to specific processors. Although it is applicable to any scheduling policy, the proposed deadline-distribution scheme is evaluated for a non-preemptive, time-driven scheduling policy. Using extensive simulations, we show that the proposed adaptive metrics deliver much better performance (in terms of success ratio and maximum task lateness) than their non-adaptive counterparts. In particular, the simulation results indicate that, for small systems, the adaptive metrics can improve the success ratio by as much as an order of magnitude. Moreover, the new adaptive metrics are found to exhibit very robust performance over a large variety of application and architecture scenarios.