THEORETICAL ANALYSIS OF REAL-TIME SCHEDULING ON RESOURCES WITH PERFORMANCE DEGRADATION AND PERIODIC REJUVENATION

In 1973, Liu and Layland [81] published their seminal paper on schedulability analysis of real-time system for both EDF and RM schedulers. In this work, they provide schedulability conditions and schedulability utilization bounds for both EDF and RM scheduling algorithms, respectively. In the following four decades, scheduling algorithms, utilization bounds and schedulability analyses for real-time tasks have been studied intensively. Amongst those studies, most of the research rely on a strong assumption that the performance of a computing resource does not change during its lifetime. Unfortunately, for many long standing real-time systems, such as data acquisition systems (DAQ) [74, 99], deep-space exploration programs [120, 119] and SCADA systems for power, water and other national infrastructures [121, 26], the performance of computational resources suffer notably performance degradations after a long and continuous execution period [61]. To overcome the performance degradation in long standing systems, countermeasures, which are also called system rejuvenation approaches in the literature [123, 61, 126], were introduced and studied in depth in the last two decades. Rejuvenation approaches recover system performance when being invoked and hence benefit most long standing applications [30, 102, 11, 12, 39]. However, for applications with real-time requirements, the system downtime caused by rejuvenation process, along with the decreasing performance during the system’s available time, makes the existing real-time scheduling theories difficult to be applied directly. To address this problem, this thesis studies the schedulability issues of a realtime task set running on long standing computing systems that suffers performance degradation and uses rejuvenation mechanism to recover. Our first study in the thesis focus on a simpler resource model, i.e. the periodic resource model, which only considers periodic rejuvenations. We introduce a method, i.e., Periodic Resource Integration, to combine multiple periodic resources into a single equivalent periodic resource and provide the schedulability analysis based on the combined periodic resource for real-time tasks. By integrating multiple periodic resources into one, existing real-time scheduling researches on single periodic resource can be directly applied on multiple periodic resources. In our second study, we extend the periodic resource mode to a new resource model, the P2-resource model, in our second work to characterize resources with both the performance degradation and the periodic rejuvenation. We formally define the P2-resource and analyze the schedulability of real-time task sets on a P2-resource. In particular, we first analyze the resource supply status of a given P2-resource and provide its supply bound and linear supply bound functions. We then developed the schedulability conditions for a task set running on a P2-resource with EDF or RM scheduling algorithms, respectively. We further derive utilization bounds of both EDF and RM scheduling algorithms, respectively, for schedulability test purposes. With the P2-resource model and the schedulability analysis on a single P2- resource, we further extend our work to multiple P2-resources. In this research, we 1) analyze the schedulability of a real-time task set on multiple P2-resources under fixedpriority scheduling algorithm, 2) introduce the GP-RM-P2 algorithm and 3) provide the utilization bound for this algorithm. Simulation results show that in most cases, the sufficient bounds we provide are tight. As the rejuvenation technology keeps advancing, many systems are now able to perform rejuvenations in different system layers. To accommodate this new advances, we study the schedulability conditions of a real-time task set on a single P2-resource with both cold or warm rejuvenations. We introduce a new resource model, the P2-resource with duel-level rejuvenation, i.e., P2D-resource, to accommodate this new feature. We first study the supply bound and the linear supply bound of a given P2D-resource. We then study the sufficient utilization bounds for both RM and EDF scheduling algorithms, respectively.Ph.D. in Computer Science, July 201