Virginia Tech
    • Log in
    View Item 
    •   VTechWorks Home
    • ETDs: Virginia Tech Electronic Theses and Dissertations
    • Doctoral Dissertations
    • View Item
    •   VTechWorks Home
    • ETDs: Virginia Tech Electronic Theses and Dissertations
    • Doctoral Dissertations
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Garbage Collection Scheduling for Utility Accrual Real-Time Systems

    Thumbnail
    View/Open
    dissertation.pdf (1.425Mb)
    Downloads: 114
    Date
    2006-12-07
    Author
    Feizabadi, Shahrooz Shojania
    Metadata
    Show full item record
    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.
    URI
    http://hdl.handle.net/10919/30233
    Collections
    • Doctoral Dissertations [14868]

    If you believe that any material in VTechWorks should be removed, please see our policy and procedure for Requesting that Material be Amended or Removed. All takedown requests will be promptly acknowledged and investigated.

    Virginia Tech | University Libraries | Contact Us
     

     

    VTechWorks

    AboutPoliciesHelp

    Browse

    All of VTechWorksCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    Log inRegister

    Statistics

    View Usage Statistics

    If you believe that any material in VTechWorks should be removed, please see our policy and procedure for Requesting that Material be Amended or Removed. All takedown requests will be promptly acknowledged and investigated.

    Virginia Tech | University Libraries | Contact Us