home · mobile · calendar · defenses · 2008-2009 · 

Thesis Defense - Lin

Robust QoS Scheduler in the Open Real-Time Systems
Wang-Ting Lin
Computer Science PhD Candidate
5/28/2009
3:30pm-5:30pm

Obtaining accurate resource estimation for either cyber physical systems which interacts with the outside world or personal computers which run soft real-time applications from various vendors is not easy. Mapping any task to a server in those environments can lead to unexpected behavior, thereby imposing new challenges to slack reclamation schedulers. After defining open real-time systems, we identify and address the potential problems. Since slack claimers encourage tasks to reserve less resources than they require, some tasks can irresponsibly under book their resources. The unsteady execution rate caused by budget borrowing can be prevented by using a void server; a limit on consecutive budget borrowing may also be imposed if necessary. When a task execution pattern does not match its server's budget usage pattern, our slack time evaluation and tighter budget binding between slack time and its server prevent its server from losing budget. Denial-of-Service (DoS) attacks on the slack scheduler by a resource underbooking task are prevented by limiting the slack consumption based on a task's resource estimation error. We improve the existing budget borrowing by providing a server with a higher probability of meeting its overrun job's deadline. Once the budget reserved for a job is partially consumed by its preceding overrun job, the existing schedulers either lower its server's scheduling priority or hold its server in the idle state to regain the full bandwidth. We activate the server immediately when the budget deficit job is released and allow it to use the partial budget with a higher priority. In order to keep full bandwidth for an upcoming job, exiting algorithms activate a server when its job is released. Thus, the overbooked resources cannot be reclaimed from any server in the idle state. Our forward donation effectively reclaims the slack time from any full bandwidth server which remains in the idle state, and it does not jeopardize any upcoming jobs that require WCET to complete on a forward donated server.

Committee: Gary Nutt, Professor (Chair)
Amer Diwan, Associate Professor
Dirk Grunwald, Associate Professor
Douglas Sicker, Associate Professor
Samuel Siewert, Department of Electrical, Computer and Energy Engineering
Department of Computer Science
University of Colorado Boulder
Boulder, CO 80309-0430 USA
webmaster@cs.colorado.edu
www.cs.colorado.edu
May 5, 2012 (14:20)
XHTML 1.0/CSS2
©2012