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 ind...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.展开更多
基金the National Natural Science Foundation of China under Grant Nos.61572112 and 61802052the 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.
