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

University Of Nebraska-Lincoln, Lincoln NE

Investigators

Abstract

Rate-Based Resource Allocation Methods for Real-Time Embedded Systems Proposal #0208924 A. Revised Project Summary 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 problems such as: the complexity of simultaneously mapping timing and importance constraints onto priority values, dealing with tasks whose execution time is either unknown or may vary over time, dealing with tasks whose execution time (or rate) deviates from the behavior expected at design-time, degrading system performance gracefully in times of overload, and ensuring full utilization of the processor or other 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. In a rate-based system a task is guaranteed to make progress according to a well-defined rate specification such as "process x samples per second," or "process x messages per second where each message consists of 3-5 consecutive network packets." This research investigates the use of rate-based resource allocation methods for constructing embedded systems with real-time execution constraints. The focus of the project is two-fold: an algorithm design and analysis component, and a prototype implementation and use component. In the design/analysis component, a framework is being developed using 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 is to relate the different scheduling models and abstractions to one another and 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, the existing theory of rate-based resource allocation is extended to deal with considerations such as preemption constraints. The implementation and use component of this research explores rate-based resource allocation in operating system kernels and applications. The objective is to assess the fit between the formal task model used to develop a particular allocation algorithm and implementation constraints that arise in practice. Three scheduling problems are considered: application-level scheduling (i.e., scheduling of user programs or application threads), scheduling the execution of system calls made by applications ("top-half" operating system-level scheduling), and scheduling asynchronous events generated by devices ("bottom-half" operating system-level scheduling). This reflects the logical structure of traditional, monolithic real-time (and general purpose) operating systems and kernels with hardware enforced protection boundaries. The research results will be distributed as an experimental version of FreeBSD that employs different forms of rate-based scheduling and resource allocation at different levels in the system.