A Framework for Hierarchical Scheduling on Multiprocessors: From Application Requirements to Run-Time Allocation
A Framework for Hierarchical Scheduling on Multiprocessors: From Application Requirements to Run-Time Allocation
复制标题
多处理器分层调度框架：从应用程序需求到运行时分配
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Enrico Bini
中科院分区：
文献类型：
--
作者：
Giuseppe Lipari;Enrico Bini
分层调度是设计和部署实时应用程序的一种很有前途的方法，因为它支持基于组件的设计和分析，并支持竞争应用程序之间的时间隔离。在分层调度中，应用程序通过临时接口来描述。设计人员面临的问题是如何导出接口参数，使应用程序具有可调度性，同时最大限度地减少计算资源的浪费。这个问题在多处理器系统中尤为重要，因为目前还不清楚接口参数如何影响应用程序的可调度性和物理平台上的分配。本文提出了对多处理机系统分层调度的三个新贡献。首先，我们提出了有界延迟多分区（BDM），这是一种新的接口规范模型，允许设计人员在选择虚拟平台参数时平衡资源使用与灵活性。其次，我们探索了基于通用虚拟平台的实时应用程序的可调度区域，并推导了接口参数。最后，我们提出了流体最佳拟合算法，该算法利用BDM提供的额外灵活性来计算虚拟平台参数并将其分配到物理平台上。通过仿真对算法的性能进行了评价。
Hierarchical scheduling is a promising methodology for designing and deploying real-time applications, since it enables component-based design and analysis, and supports temporal isolation among competing applications. In hierarchical scheduling an application is described by means of a temporal interface. The designer faces the problem of how to derive the interface parameters so to make the application schedulable, at the same time minimizing the waste of computational resources. The problem is particularly relevant in multiprocessor systems, where it is not clear yet how the interface parameters influence the schedulability of the application and allocation on the physical platform. In this paper we present three novel contributions to hierarchical scheduling for multiprocessor systems. First, we propose the Bounded-Delay Multipartition (BDM), a new interface specification model that allows the designer to balance resource usage versus flexibility in selecting the virtual platform parameters. Second, we explore the schedulability region of a real-time application on top of a generic virtual platform, and derive the interface parameter. Finally, we propose Fluid Best-Fit, an algorithm that takes advantage of the extra degree of flexibility provided by the BDM to compute the virtual platform parameters and allocate it on the physical platform. The performance of the algorithm is evaluated by simulations.