Multi-rate fluid scheduling of mixed-criticality systems on multiprocessors
Multi-rate fluid scheduling of mixed-criticality systems on multiprocessors
复制标题
多处理器上混合关键性系统的多速率流体调度
作者：
Saravanan Ramanathan;A. Easwaran;Hyeonjoong Cho
本文研究了同构多处理器平台上隐式截止日期偶发任务系统的混合临界调度问题。针对双临界系统，过去已经提出了基于流体调度模型的算法。这些算法根据系统模式对每个高临界任务使用双速率执行模型。一旦系统切换到高临界模式，这些任务的执行速度就会增加，以满足它们增加的需求。虽然这些算法是加速最优的，但它们不能调度多个可行的双临界任务系统。这是因为在模式切换后，每个高临界任务的单一固定执行率无法有效地处理模式切换后的过渡期间需求的高度可变性。只要高临界任务的结转作业（即在模式切换之前释放的作业）尚未完成，这种需求可变性就存在。针对这一缺点，本文提出了一种双临界任务系统的多速率流体执行模型。在该模型下，高临界任务在模式切换后的过渡期内被分配不同的执行率，以有效地处理需求的可变性。我们对所提出的模型进行了充分的可调度性检验，并证明了其优于双速率流体执行模型。此外，我们还提出了一种多速率模型的加速最优速率分配策略，实验表明，该模型优于现有的所有已知加速边界的MC调度算法。
In this paper we consider the problem of mixed-criticality (MC) scheduling of implicit-deadline sporadic task systems on a homogenous multiprocessor platform. Focusing on dual-criticality systems, algorithms based on the fluid scheduling model have been proposed in the past. These algorithms use a dual-rate execution model for each high-criticality task depending on the system mode. Once the system switches to the high-criticality mode, the execution rates of such tasks are increased to meet their increased demand. Although these algorithms are speed-up optimal, they are unable to schedule several feasible dual-criticality task systems. This is because a single fixed execution rate for each high-criticality task after the mode switch is not efficient to handle the high variability in demand during the transition period immediately following the mode switch. This demand variability exists as long as the carry-over jobs of high-criticality tasks, that is jobs released before the mode switch, have not completed. Addressing this shortcoming, we propose a multi-rate fluid execution model for dual-criticality task systems in this paper. Under this model, high-criticality tasks are allocated varying execution rates in the transition period after the mode switch to efficiently handle the demand variability. We derive a sufficient schedulability test for the proposed model and show its dominance over the dual-rate fluid execution model. Further, we also present a speed-up optimal rate assignment strategy for the multi-rate model, and experimentally show that the proposed model outperforms all the existing MC scheduling algorithms with known speed-up bounds.