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

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.