Improved Task and Resource Partitioning Under the Resource-Oriented Partitioned Scheduling  

作　　者：Ze-Wei Chen Hang Lei Mao-Lin Yang Yong Liao Jia-Li Yu 

机构地区：[1]School of Information and Software Engineering,University of Electronic Science and Technology of China Chengdu 610054,China [2]School of Mathematical Sciences,University of Electronic Science and Technology of China,Chengdu 610054,China

出　　处：《Journal of Computer Science & Technology》2019年第4期839-853,共15页计算机科学技术学报（英文版）

基　　金：the National Natural Science Foundation of China under Grant Nos.61572112 and 61802052;the Applied Basic Research Programs of Science and Technology Department in Sichuan Province of China under Grant No.2019YJ0185.

摘　　要：Coordinated partitioning and resource sharing have attracted considerable research interest in the field of real-time multiprocessor systems.However,finding an optimal partition is widely known as NP-hard,even for independent tasks.A recently proposed resource-oriented partitioned(ROP)fixed-priority scheduling that partitions tasks and shared resources respectively has been shown to achieve a non-trivial speedup factor guarantee,which promotes the research of coordinated scheduling to a new level.Despite the theoretical elegance,the schedulability performance of ROP scheduling is restricted by the heuristic partitioning methods used in the original study.In this paper,we address the partitioning problem for tasks and shared resources under the ROP scheduling.A unified schedulability analysis framework for the ROP scheduling is proposed in the first place.A sophisticated partitioning approach based on integer linear programming(ILP)is then proposed based on the unified analysis.Empirical results show that the proposed methods improve the schedulability of ROP scheduling significantly,and the runtime complexity for searching a solution is reduced prominently compared with other ILP-based approaches as well.

关 键 词：MULTIPROCESSOR real-time SCHEDULING partitioned fixed-priority SCHEDULING SHARED resource INTEGER linear pro-gramming 

分 类 号：TP[自动化与计算机技术]