Approved by:

ii BIPASA CHATTOPADHYAY: Integrating pragmatic constraints and behaviors into real-time scheduling theory. (Under the direction of Sanjoy K. Baruah) Scheduling theory has been studied and developed extensively in prior research. In some existing scheduling theory results, the focus is primarily on demonstrating interesting theoretical properties, thus these results are not always cognizant of pragmatic constraints. We seek to determine how existing scheduling theory can be improved with respect to pragmatic constraints and behaviors. The goal of this research is to study and design scheduling algorithms for scheduling real-time workload under constraints and behaviors found in real-time systems. Based on our study we derive a scheduling algorithm for partitioning a collection of real-time tasks in a manner that is cognizant of multiple resource constraints. We apply the above scheduling algorithm for partitioning mixed-criticality tasks. In real-time systems the scheduling algorithm must schedule workload such that all timing constraints are met; we verify this using schedulability tests. We describe schedulability tests for each of the scheduling algorithms that we derive. We also propose a new schedulability test for an existing scheduling algorithm that is commonly used in real-time systems research for scheduling tasks with limited-preemptivity. Finally, we propose a scheduling algorithm and schedulability test for scheduling real-time workload on processors that allow dynamic overclocking. iii Dedicated to my family and friends. iv ACKNOWLEDGEMENTS I would like to thank the following people for their continued help and support through out m