Aravind Chandrashekar, for the Master of Science degree in Electrical and Computer, presented on 02/09/2011, at Southern Illinois University Carbondale. TITLE: Reduction of Cache Related Preemption Delay using DVS in Real Time Systems MAJOR PROFESSOR: Dr. Harini Ramaprasad Embedded/real-time systems are ubiquitous in today's world. Providing temporal guarantees is paramount in such systems. In several multi-tasking real-time systems, tasks are assigned varying priorities and scheduled in accordance with a preemptive scheduling policy. When a task is preempted, a significant number of memory blocks belonging to the particular task are displaced from the cache memory between the time that the task is preempted and the time that the task resumes execution. Upon resumption, a corresponding amount of time is spent in reloading the cache with previously replaced memory blocks, thereby incurring what is known as cache-related preemption delay (CRPD). CRPD of a task due to a given preemption depends on the position in the program where the preempted task is executing at the time of preemption. As such, CRPD at different preemption points may be significantly different. In this thesis, we exploit this difference in CRPD and use dynamic voltage/frequency scaling (DVFS) to control the execution speed of a task such that it gets preempted in regions where the CRPD is low, as far as is possible without jeopardizing system schedulability. Simulation results demonstrate that our algorithm reduces number of cache reloads due to preemption to a reasonable extent, thereby reducing the repeated usage of off-chip memory bandwidth.

During the past decades of research in Real-Time systems, non-preemptive scheduling and fully preemptive scheduling have been extensively investigated, as well as compared with each other. However, it has been shown that none of the two scheduling paradigms dominates over the other in terms of schedulability. In this context, Limited Preemptive Scheduling (LPS) has emerged as an attractive alternative with respect to, e.g., increasing the overall system schedu- lability, efficiently reducing the blocking by lower priority tasks (compared to non-preemptive scheduling) as well as efficiently controlling the number of preemptions, thus controlling the overall preemption-related delay (compared to fully-preemptive scheduling). Several approaches within LPS enable the above mentioned advantages. In our work, we consider the Fixed Preemption Point Scheduling (LP-FPP) as it has been proved to effectively reduce the preemption-related delay compared to other LPS approaches. In particular, LP-FPP facilitates more precise estimation of the preemption-related delays, since the preemption points of a task in LP-FPP are explicitly selected during the design phase, unlike the other LPS approaches where the preemption points are determined at runtime. The main goal of the proposed work is to improve the schedulability of real-time systems under the LP-FPP approach. We investigate its use in different domains, such as: single core hard real-time systems, partitioned multi-core systems and real-time systems which can occasionally tolerate deadline misses. We enrich the state of the art for the single core hard real-time systems by proposing a novel cache-related preemption delay analysis, towards reducing the pessimism of the previously proposed methods. In the context of partitioned multi-core scheduling we propose a novel partitioning criterion for the Worst-Fit Decreasing based partitioning, and we also contribute with the comparison of existing partitioning strategies for LP-FPP scheduling. Finally, in the context of real-time systems which can occasionally tolerate deadline misses, we contribute with a probabilistic response time analysis for LP-FPP scheduling and a preemption point selection method for reducing the deadline-misses of the tasks.