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

实时嵌入式系统的基于速率的资源分配方法提案#0208924 A.修订的项目摘要嵌入式系统的运行时执行者和操作系统内核长期以来一直完全依赖任务的静态优先级调度来确保满足定时约束和其他正确性条件。静态优先级调度很容易理解和支持，但它面临着许多重要问题，例如：同时将时间和重要性约束映射到优先级值的复杂性，处理执行时间未知或可能随时间变化的任务，处理执行时间(或速率)偏离设计时预期行为的任务，在过载时优雅地降低系统性能，以及在资源严格受限的系统中确保处理器或其他资源的充分利用。基于速率的资源分配方案为传统的静态优先级调度提供了一种有吸引力的替代方案，因为它们在指定和管理时间和关键度约束方面提供了灵活性。在基于速率的系统中，任务被保证根据明确定义的速率规范来取得进展，所述速率规范例如是“每秒处理x个样本”或“每秒处理x个消息，其中每个消息由3-5个连续的网络分组组成。”本研究探讨基于速率的资源分配方法在构建具有实时执行约束的嵌入式系统中的应用。该项目的重点有两个：一个是算法设计和分析组件，另一个是原型实现和使用组件。在设计/分析组件中，正在使用基于速率的资源分配的分类来开发框架，该分类包括比例份额调度、基于轮询服务器的调度以及对经典的Liu和Layland调度的基于速率的扩展。目标是将不同的调度模型和抽象彼此联系起来，并了解基于速率的资源分配的基本原则，例如定时保证的形式和性质以及算法开销。此外，对现有的基于速率的资源分配理论进行了扩展，以处理抢占限制等因素。这项研究的实现和使用部分探索了操作系统内核和应用程序中基于速率的资源分配。其目的是评估用于开发特定分配算法的正式任务模型与实践中出现的实施限制之间的匹配。考虑了三个调度问题：应用级调度(即，用户程序或应用线程的调度)、调度由应用进行的系统调用的执行(“上半部分”操作系统级调度)、以及调度由设备生成的异步事件(“下半”操作系统级调度)。这反映了具有硬件强制保护边界的传统、单一实时(和通用)操作系统和内核的逻辑结构。研究结果将作为FreeBSD的实验版本分发，该版本在系统的不同级别使用不同形式的基于速率的调度和资源分配。

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.