A real-time system must generate computation results and transmit message packets in a timely manner. A large body of literature has been developed to guarantee the timely execution of periodic real-time tasks, where instance invocation rate is considered the most important timing constraint. However, some real-time tasks require relative timing constraints between the consecutive instances, which is called distance constraints. We propose a new task model, that combines the characteristics of both the periodic task model and the distance constraint task model. In the new model, a task has a rate requirement and a distance constraint.; A classical real-time system scheduling paradigm, template-based scheduling, is widely used in many time-critical systems. In this scheduling paradigm, an effective scheduling template is generated off-line, and the tasks (or message streams) are executed (or transmitted) cyclically according to the schedule. Template-based scheduling is also used in network systems, such as the media access control protocol TDMA (Time Division Multiplexing Access). We adopt template-based paradigm to solve scheduling problems for both computation tasks and communication tasks under the following three system configurations.; In this dissertation, we first study a system consisting of a static set of tasks, with all parameters of the tasks known in advance. We present a time slot allocation scheme to schedule a single resource, such as a processor or a broadcast bus. Moreover, we extend the scheme to schedule real-time traffic on crossbar switches and on WDMA (Wavelength Division Multiplexing Access) optical star couplers. In both the crossbar and the star coupler cases, input conflicts and output conflicts are taken into consideration in the scheduling algorithm, in addition to the rate requirements and the distance constraint specifications of the message streams. Simulation performance results of the algorithms are presented and analyzed. The results show that, by decoupling the rate requirements from the distance constraint specifications of the real-time message streams, high schedulability is achieved.; Our second scheduling problem is to satisfy rate requirements and distance constraints of dynamically arriving and departing tasks. Given a set of tasks already scheduled and a newly arriving task, three algorithms are presented to make greedy choices, heuristic but non-greedy choices, and optimal choices, respectively. The performances of the three algorithms are evaluated via simulation and compared in terms of time complexity, acceptance ratio and scheduling jitter.; The third scenario is a distributed system where isochronous message streams are transmitted from a source node to a destination node. In this scenario, end-to-end (ETE) delay is the main QoS (Quality of Service) concern. Since distance constraint is related to scheduling jitter, the algorithms derived to satisfy distance constraints are adapted to minimize the scheduling jitter. Once a scheduling template is generated at every node, the packets of a stream are delivered in an allocated time slot according to one of three delivery protocols proposed in this work. A worst-case ETE delay bound is derived for each protocol. The simulation studies show that by minimizing the scheduling jitter, we can achieve an end-to-end delay which is much better than the estimated one provided in the worst-case analysis.
展开▼
