Pessimism in multicore global schedulability analysis

When it comes to multicore real-time systems, the global scheduling that allows tasks to migrate between different cores and the partitioned scheduling that statically allocates tasks to individual cores are two popular policies. However, due to the complexity and pessimism of multicore schedulability tests, there is no simple way to compare the effectiveness of global versus partitioned scheduling, and it is hard to improve existing analysis methods. In this paper, we formally prove that, according to state-of-the-art global schedulability tests, if a multicore task system (with D_i ≤ T_i) is deemed schedulable under global fixed priority policy, we can easily find a schedulable partitioning for it too. This result holds also for self-suspending tasks that can suspend its own execution voluntarily. Such a fact reveals the high pessimism in current global schedulability tests. To tackle this, we propose a 2-part execution scenario, by simply considering the task execution into two parts, that helps better estimate the interference a task suffers. Using this method, a new global schedulability test can detect schedulable tasksets that will be non-schedulable by any partitioned scheduling algorithm. Our proposed method indicates a new direction for designing global schedulability tests. In the experiments, comparisons with other global and partitioned schedulability tests confirm the improvement by using our new test.