Garbage Collection Scheduling for Utility Accrual Real-Time Systems
|dc.contributor.author||Feizabadi, Shahrooz Shojania||en_US|
|dc.description.abstract||Utility Accrual (UA) scheduling is a method of dynamic real-time
scheduling that is designed to respond to overload conditions by
producing a feasible schedule that heuristically maximizes a
pre-defined metric of utility. Whereas utility accrual schedulers have
traditionally focused on CPU overload, this dissertation explores
memory overload conditions during which the aggregate memory demand
exceeds a system's available memory bandwidth.
Real-time systems are typically implemented in C or other languages that use explicit dynamic memory management. Taking advantage of modern type-safe languages, such as Java, necessitates the use of garbage collection (GC). The timeliness requirements of real-time systems, however, impose specific demands on the garbage collector. Garbage collection introduces a significant source of unpredictability in the execution timeline of a task because it unexpectedly interjects pauses of arbitrary length, at arbitrary points in time, with an arbitrary frequency.
To construct a feasible schedule, a real-time scheduler must have the ability to predict the collector's activities and plan for them accordingly. We have devised CADUS (Collector-Aware Dynamic Utility Scheduler), a utility accrual algorithm that tightly links CPU scheduling with the memory requirements -and the corresponding garbage collection activities - of real-time tasks. By constructing and storing memory time allocation profiles, we address the problem of GC activation strategy. We estimate GC latency by using a real-time collector and modeling its behavior. We project GC frequency by planning, at schedule construction time, the memory bandwidth available to the collector. CADUS can point the collector's activities to any specific task in the system. The runtime system provides this ability by maintaining separate logical heaps for all tasks.
We demonstrate the viability of CADUS through extensive simulation studies. We evaluated the behavior of CADUS under a wide range of CPU and memory load conditions and utility distributions. We compared its performance against an existing GC-unaware UA scheduler and found that CADUS consistently outperformed its GC-unaware counterpart. We investigated and identified the reasons for the superior performance of CADUS and quantified our results. Most significantly, we found that in an overloaded dynamic soft real-time system, a scheduler's preemption decisions have a highly significant impact on GC latency. A dynamic real-time scheduler therefore must predict the impact of its preemption decisions on GC latency in order to construct time-feasible schedules.
|dc.rights||I hereby certify that, if appropriate, I have obtained and attached hereto a written permission statement from the owner(s) of each third party copyrighted matter to be included in my thesis, dissertation, or project report, allowing distribution as specified below. I certify that the version I submitted is the same as that approved by my advisory committee. I hereby grant to Virginia Tech or its agents the non-exclusive license to archive and make accessible, under the conditions specified below, my thesis, dissertation, or project report in whole or in part in all forms of media, now or hereafter known. I retain all other ownership rights to the copyright of the thesis, dissertation or project report. I also retain the right to use in future works (such as articles or books) all or part of this thesis, dissertation, or project report.||en_US|
|dc.subject||Utility Accrual Scheduling||en_US|
|dc.title||Garbage Collection Scheduling for Utility Accrual Real-Time Systems||en_US|
|thesis.degree.grantor||Virginia Polytechnic Institute and State University||en_US|
|dc.contributor.committeechair||Back, Godmar Volker||en_US|
|dc.contributor.committeemember||Nance, Richard E.||en_US|
|dc.contributor.committeemember||Jensen, E. Douglas||en_US|
|dc.contributor.committeemember||Arthur, James D.||en_US|
|dc.contributor.committeemember||Cline, Benjamin E.||en_US|
|dc.contributor.committeecochair||Fox, Edward Alan||en_US|
Files in this item
This item appears in the following Collection(s)
Doctoral Dissertations