Collaborative Research: Rate-Based Resource Allocation Methods for Real-Time Embedded Systems

Principal Investigator: Kevin Jeffay, Don Smith 
Funding Agency: National Science Foundation 
Agency Number: CNS-0208924

Abstract
Run-time executives and operating system kernels for embedded systems have long relied exclusively on static priority scheduling of tasks to ensure timing constraints and other correctness conditions are met. Static priority scheduling is easy to understand and support but it suffers from a number of significant shortcomings such as: -the complexity of simultaneously mapping timing & importance constraints onto priority values, -the problem of dealing with tasks whose execution time is either unknown or may vary over time, -the problem of dealing with tasks whose execution time or execution rate deviates significantly at run-time from the behavior expected at design-time, -the problem of degrading system performance gracefully in times of overload, and -the problem of ensuring full utilization of the processor or other system resources in tightly resource constrained systems. Rate-based resource allocation schemes offer an attractive alternative to traditional static priority scheduling as they offer flexibility in specifying and managing timing and criticality constraints. We propose an investigation into the use of rate-based resource allocation methods for constructing embedded systems with real-time execution constraints. The investigation will have both an algorithm design and analysis component as well as an implementation and use component. In the design/analysis component we will develop a framework for analyzing and comparing different rate-based schedulers from the literature. Specifically, we consider a taxonomy of rate-based resource allocation consisting of proportional share scheduling, polling. server-based scheduling, and rate-based extensions to classical Liu and Layland scheduling. The goal here will be to relate the different scheduling models and abstractions to one another to understand the fundamental principles of rate-based resource allocation such as the form and nature of timing guarantees and the algorithmic overhead. In addition we will extend the existing theory of rate-based resource allocation to deal with practical considerations such as preemption constraints (critical sections, resource sharing). The implementation and use component of this research will consider the reduction to practice of rate-based resource allocation in operating system kernels and applications. The goal here will be to assess the fit between the formal task model used to develop a particular allocation algorithm and implementation constraints that arise in practice. To fully explore the utility of rate-based resource allocation, three scheduling problems will be considered: application-level scheduling (i.e., scheduling of user programs or application threads), scheduling the execution of system calls made by applications ("top-hair' operating system-level scheduling), and scheduling asynchronous events generated by devices ("bottom-half" operating system-level scheduling). This treatment is motivated by the logical structure of traditional, monolithic real-time (and general purpose) operating systems and kernels with hardware enforced protection boundaries. Moreover, this simple taxonomy of scheduling problems emphasizes that in real systems one must consider issues of intra-kernel resource allocation and scheduling (e.g.. buffer management) as well as application task scheduling. A sub-goal will be to prove the thesis that that "one size does not Fit all" - one rate-based resource allocation scheme does not suffice for all scheduling problems that arise within the layers of a real system. While there exist stylized execution environments wherein any given rate-based schemes here will perform well, for more realistic environments that are likely to be encountered in practice, the best results will be achieved by employing different rate-based allocation schemes at different levels in the operating system. The thesis will be shown by constructing small memory footprint versions of FreeBSD and Linux that employ different forms of rate-based scheduling and resource allocation at different levels in the system. We will work with external researchers from industry to use two commercial embedded systems to evaluate our rate-based allocation schemes and their implementation. The research proposed will be integrated into a broader program of outreach to underrepresented groups to involve members of these groups in the research process.