Feedback-based task scheduling in real-time systems.

摘要

Real-time computing is an enabling technology for many current and next generation applications. One of the key components of real-time systems is the scheduling of tasks, the objective of which is to meet task deadlines predictably. Traditional real-time task scheduling paradigms perform well in static or dynamic systems in which the workload can be accurately modeled. Unfortunately, in many complex applications, unpredictable dynamic factors exist due to which precise workload characterization is difficult. In recent years, feedback control techniques have been successfully applied to address the issue of unpredictable workload in computing systems. In this dissertation, we develop feedback-based algorithms and analysis for some important dynamic scheduling problems in real-time systems.; First, we address the problem of selective herbicide spraying in precision farming application. The goal is to achieve low weed miss ratio and high CPU utilization. We carry out system identification, vehicle modeling and controller design. In our design, the requested CPU utilization is fed back and the vehicle speed is controlled. The system model is verified and performance evaluation is carried out through simulation studies.; The second problem is task scheduling based on (m, k)-firm deadline constraints in real-time systems. The proposed solution feeds back the current dynamic failure rate (DFR) and adjusts the task's QoS based on DFR on-line. We also propose a novel fairness metric to evaluate the fairness in QoS among tasks achieved by the scheduler. The simulation results show that the QoS of tasks can be improved significantly while keeping the DFR below a certain threshold.; The third problem is combined task scheduling with fault tolerance in real-time systems. In our model, the rate monotonic scheduling algorithm and deferrable server algorithm are used to schedule periodic and aperiodic tasks, respectively. By using feedback control technique, we adjust the capacity of the deferrable servers based on the failure rate of the periodic tasks. The performances of the systems are evaluated through simulation studies.; The last problem is task scheduling in distributed real-time systems. We propose a double-loop scheme to keep the deadline miss ratio close to the set point and maximize the CPU utilization, and analyze the stability of the system in Z-domain. We also propose a global scheduling method to achieve load balancing by using a suitable load index. The performances of the systems are evaluated through simulation studies.; The feedback-based solutions proposed in this dissertation are based on the principle of controlling the trade-off between deadline miss ratio and resource utilization. This idea can be adapted not only to other scheduling problems in real-time systems, but also to scheduling problems in non-real-time systems.