Energy-Efficient, Utility Accrual Real-Time Scheduling
MetadataShow full item record
In this dissertation, we consider timeliness and energy optimization in battery-powered, mobile embedded real-time systems. We focus on real-time systems that operate in environments with dynamically uncertain properties, including context-dependent activity execution times and arbitrary activity arrival patterns. We consider an application model where activities are subject to time/utility function (or TUF) time constraints, mutual exclusion constraints on concurrent sharing of non-CPU resources, timeliness requirements including assurances on individual activity timeliness behavior, and system-level energy consumption requirements including a non-exhaustable energy budget. To account for uncertainties in activity properties in dynamic systems, we stochastically describe activity execution demands, and describe activity arrival behaviors using the unimodal arbitrary arrival model, which allows unbounded arrival frequencies. We consider the scheduling optimality criteria of: (1) probabilistically satisfying lower bounds on individual activities' maximal timeliness utilities, and (2) maximizing system-level energy efficiency, while ensuring that the system's energy consumption never exhausts the energy budget and resource mutual exclusion constraints are satisfied. For this multi-criteria scheduling problem, we present a DVS (dynamic voltage scaling)-based, real-time scheduling algorithm called the Energy-Bounded Utility Accrual Algorithm (or EBUA). Since the scheduling problem is NP-hard, EBUA heuristically (and dynamically) allocates CPU cycles to activities, computes activity schedules, and scales CPU voltage and frequency with a polynomial-time cost. If activities' cumulative execution demands exceed the available CPU time or may exhaust the system's energy budget, the algorithm defers and rejects jobs in a controlled fashion, minimizing system-level energy consumption and maximizing total accrued utility. We analytically establish several properties of EBUA. We prove that the algorithm never exhausts the specified energy budget. Further, we establish EBUA's timeliness optimality during under-loads, freedom from deadlocks, and correctness in mutually exclusive resource sharing. In particular, we prove that the algorithm's timeliness behavior subsumes the optimal timeliness behavior of deadline scheduling as a special case, and identify the conditions under which lower bounds on individual activity utilities are satisfied. In addition, we upper bound the time needed for mutually exclusively accessing shared resources under EBUA. We conduct experimental studies by simulating the algorithm on the DVS-enabled AMD k6 processor model, and by implementing it on QNX Neutrino 6.2.1 RTOS. Our experimental results validate our analytical results. Further, they confirm EBUA's superiority over other energy-efficient real-time scheduling algorithms on timeliness and energy consumption behaviors.
- Doctoral Dissertations 
Showing items related by title, author, creator and subject.
Attri, Hitesh (Virginia Tech, 2005-01-04)A software agents based manufacturing scheduling module for Advanced Planning and Scheduling (APS) is presented. The problem considered is scheduling of jobs with multiple operations, distinct operation processing times, ...
Optimal and Approximate Algorithms for the Multiple-Lots-per-Carrier Scheduling and Integrated Automated Material Handling and Lot Scheduling Problems in 300mm Wafer Fabs Wang, Lixin (Virginia Tech, 2008-08-20)The latest generation of semiconductor wafer fabs produce Integrated Circuits (ICs) on silicon wafers of 300mm diameter. In this dissertation, we address the following two types of (new) scheduling problems that are ...
How Does a Seventh-Grade Language Arts Teacher Adjust Instructionl Practices when Introduced to a Scheduling Change, Namely Block Scheduling Miller, Dale Jonathan (Virginia Tech, 1999-08-27)The influences of school reform on the instructional practices of a seventh-grade language arts teacher was the focus of this study. This study was conducted in three phases: an ethnographic study, a pilot study, and a ...