Budgeted generalized rate monotonic analysis for the partitioned, yet globally scheduled uniprocessor model
Budgeted generalized rate monotonic analysis for the partitioned, yet globally scheduled uniprocessor model
复制标题
分区但全局调度的单处理器模型的预算广义速率单调分析
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
L. Sha
中科院分区：
文献类型：
--
作者：
Jung;T. Abdelzaher;L. Sha
本文解决了在通用的速率单声音调度下，在软件开发周期初期，在软件开发周期初期的离线响应时间分析的挑战。 CPU预算分配给不同的应用程序，每个应用程序由必须共享相同预算的多个定期任务组成。物理应用要求从一开始就对任务期和截止日期施加了规格，但是与传统响应时间分析中的共同假设不同，任务执行时间尚不清楚。这是因为任务执行时间取决于确切的系统实现，该实现直到开发周期后期才确定。设计师面临的问题成为：由于缺乏对其他任务的执行时间的了解，我的任务是否会符合其截止日期？我的任务可以完成的最小截止日期是什么？这些问题传统上是通过使用两个级别的调度程序来解决的：CPU已分配并分配给应用程序，并在应用程序范围内确定任务优先级，并且当服务器开始活动时，它会在本地调度任务。这种两个级别的调度方法引入了跨应用程序的优先级反演。在我们的方法中，不同的应用程序的任务是全球安排的，但CPU资源仍被分区并分配给应用程序作为CPU预算。我们在执行申请预算的同时，在全球安排所有任务。拟议的新形式的响应时间分析称为预算的通用速率单调分析，以计算仅给定应用程序预算和任务段的每个任务的最大响应时间，但不知道任务执行时间。我们将此调度性问题提出为混合整数线性编程问题，并演示了计算确切最坏情况响应时间的解决方案。评估表明，我们的解决方案在可调度性方面优于通过资源分配实现时间模块的全局利用界限和机制。
This paper solves the challenge of offline response time analysis of independent periodic tasks with constrained deadlines early in the software development cycle, under generalized rate-monotonic scheduling. CPU budgets are allocated to different applications and each application is composed of multiple periodic tasks that must share the same budget. Physical application requirements impose specifications on task periods and deadlines from the very beginning, but unlike the common assumption in traditional response time analysis, task execution times are not known. This is because task execution times depend on the exact system implementation, which is not finalized until later in the development cycle. Questions facing designers become: will my task meet its deadline given lack of knowledge of other tasks' execution times? What is the smallest deadline that my task can meet? These questions are traditionally addressed by using a two level scheduler: CPU is partitioned and assigned to application, and task priorities are determined within the scope of an application, and when server becomes active it schedules the tasks locally. Such two level scheduling approach introduces priority inversion across applications. In our approach, different applications' tasks are globally scheduled and yet the CPU resource is still partitioned and assigned to applications as a CPU budget. We schedule all the tasks globally while enforcing application budgets. The proposed new form of response time analysis is called budgeted generalized rate-monotonic analysis to compute the maximum response time for each task given only application budgets and task periods, but without knowledge of task execution times. We formulate this schedulability problem as a mixed integer linear programming problem and demonstrate a solution that computes the exact worst-case response times. Evaluation shows that our solution outperforms, in terms of schedulability, both global utilization bounds and mechanisms that attain temporal modularity via resource partitioning.