Research On Key Technology In Weakly-Hard Real-Time System

With the development of computing technology, the number of the types of real-time applications is increased day by day, the application area is wider and wider, and the system is more and more complicated. Espescially, with the development of network technology, the networking real-time applications are put forward, e.g., networking multimedia, distance education, telesurgery, etc., which also have the time constraint on the task completion. But, the time constraint is neither as hard as hard real-time, nor as fuzzy as soft real-time. It is based on some definitive QoS requirement.To deal with the new characters of the real-time system, such as kinds and kinds of tasks, complicated constraints and transient overload, the theory of weakly-hard real-time is brought forward. The theory is taken as a specification, which enriches the real-time system theory and uniforms all existed real-tiem systems. Either hard real-time or soft real-time is a special case of weakly-hard real-time system.Weakly-hard real-time system can satisfy the emerging characters. Since it can uniform hard real-time and soft real-time into one description, it is a convenient tool for handling the integrated schedule with various tasks. The QoS requirement is described by two parameters in weakly-hard real-time constraint, which can define and differentiate the tasks' QoS more clearly. When the system is in overload conditions, weakly-hard real-time scheduling algorithms can provide graceful degradation of QoS.Therefore, in this thesis, the weakly-hard real-time theory is enriched, and the algorithms are deeply researched. The main contributions of this paper are summarized as follows.1) This thesis enriches the weakly-hard real-time constraint specification. The (p,k) constraint is proposed, of which the equivalance with the ( m ,p) constraint is proved and the relations with other constraints can be derived. The emphases of the ( m ,p) constraint and the (p,k) one are different, the former emphasizes the number of continuous missing deadlines, and the latter emphsizes the minimum window size. Furthermore, the (p,k) loss rate is defined, by which the necessary condition of satisfying the (p,k) constraint is presented. The (p,k) loss rate also provides the theoretical basis for the class selection algorithm.2) Based on the ( m ,p) constraint, this thesis proposes a kind of algorithms which is named as CDBS (Cut-Down Based Scheduling) and is used to solve the discrimination of window constraint with variable sizes. In CDBS, the execution state sequence is cut down effectively and the notion of turnpoint is introduced, which makes the discrimination of the satisfiability of ( m ,p) constraint much easier and the complexity of judgment is not relevant to the length of sequence. The correctness of the algorithm is proved and the effectiveness is verified in experiments. This thesis proroses a concise way to assign the priorities, which is based on the distance from m times continuous misses. The tasks are also scheduled with consideration of four possible states. Finally, we compare CDBS with other classical algorithms, such as EDF, DBP, DWCS, and the results show its competence and its compromise in dynamic failure ratio and minimum success ratio.3) Beginning with the loss rate gruarntee in variable window, this thesis proposes an algorithm named as Any Window Constraint Scheduling (AWCS), which can provide fair and discriminatory service in overload conditions. AWCS is based on the (p,k) constraint, its complexity is analyzed. Unfortunately, the computation of AWCS in heavily overload conditions is too complicated to schedule, a simple version of AWCS is put forward, which is called K-Window Constraint Scheduling (KWCS). Extensive experiments show that KWCS can supersede AWCS, and not only achieve comparative performance but also get lower complexity. In this thesis, the properties of two algorithms are addressed, and the difference of success ratio is defined, by which a general representation of delay bound of the scheduling algorithms is brought forward. Results show that both AWCS and KWCS can provide better performance than other weakly-hard real-time scheduling algorithms in heavily overload circumstances, that is, the QoS is degraded gracefully and the service is both fair and discriminatory.4) This thesis extends K-Window Constaint Scheduling algorithm for practice. The mixed algorithm of KWCS and DBP is put forward. The states of system overload are classified into light overload, critical overload and heavily overload. The system overload state is monitored dynamically. According to different overload state, the different policy is adopted. The mixed algorithm overcomes the poor performance of KWCS in light overload conditions. KWCS needs to maintain the history of execution, and so the overhead is too heavy to emit when the system becomes larger and larger. For this reason, the class selection algorithm is brought forward, which classifies the (p,k) streams accroding to the (p,k) loss rate. Results show that the performance of the algorithms, and the class selection algorithms can both decrease the overhead effectively and guarantee the QoS. Furthermore, the Multihop K-Window Constraint Scheduling (M-KWCS) algorithm is presented, which is applied into the end-to-end system.5) This thesis tries to use weakly-hard real-time scheduling algorithms into new application areas. The weakly-hard real-time scheduling algorithm for multiprocessor is brought forward, which is used to schedule various tasks in the multiprocessor integratedly. The algorithm also considers the resource constraints. A mixed static/dynamic energy-aware weakly-hard real-time scheduling algorithm with simple feedback mechanism is put forward. Since the actual execution time is far less than the Worst Case Execution Time (WCET), the mixed static/dynamic energy-aware weakly-hard real-time scheduling algorithm is modified. The task partition is introduced, and the simple feedback mechanism is used to estimate the actual execution time. The whole speed is decreased and the execution time is prolonged, and so the new algorithm is more energy efficient. The experimental results show that the proposed algorithm outperforms the original one when the Average Case Execution Time (ACET) is much less than the WCET, which can improve energy savings about 60% to 70% at most and about 10% at least. Unfortunately, when the ACET is close to the WCET, the proposed algorithm consumes more energy than the original one.Finally, some concluding remarks are given, and the future research works are pointed out.