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

协作研究：实时嵌入式系统基于速率的资源分配方法

• 批准号: 0208619
• 负责人: Stephen Goddard
• 金额: $ 12万
• 依托单位: University of Nebraska-Lincoln
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2002
• 资助国家: 美国
• 起止时间: 2002-09-01 至 2005-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0208619&HistoricalAwards=false
• 关键词: Collaborative; Research; Rate; Based; Resource

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.

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